����ֱ��

Researchers at the ����ֱ�� Applied Physics Laboratory (APL) in Laurel, Maryland, have demonstrated that a quantum algorithm can be used to speed up an information analysis task that classical computers struggle to perform.

The innovation tackles a key element of information operations: tracking and attributing topics and narratives as they emerge and evolve online, which can help analysts spot indications of potential terrorist acts, for example. This involves using computers to perform what’s known as semantic text similarity analysis, or comparing the similarities within a textual dataset — not just the similarity of the words, but the meaning behind them, which makes it possible to identify related texts even if they don’t share any common keywords.

“The amount of open-source text data online — on social media platforms especially — is growing dramatically, and our ability to analyze all of that data has not kept pace with our ability to collect it,” said Roxy Holden, a mathematician at APL and principal investigator of this effort. “Intelligence analysts have limited resources, so finding better ways to automate this kind of analysis is critical for the military and the intelligence community.”

Most approaches to this problem apply machine learning models, but those models tend to be difficult to use and ill-suited for analysis. A newer approach explored in the research literature is to apply “random walks” — a mathematical process in which data is represented by a graph with nodes and connecting lines — but large compute requirements limit the practicality of this approach. The path through that graph is created by a series of random steps; for text analysis, the nodes represent words and the lines connect words based on their semantic relations.

“Imagine a person standing on a node of the graph and flipping a coin to decide which node to move through next,” Holden said. “Only it’s more like a multisided die that can be generalized to any number of potential directions.” Inspired by this approach, the APL team explored the use of quantum random walks to overcome the computational limitations.

Walking the Lines

The lines of the graph represent how semantically close two words are, so the random walk will tend to favor words that are semantically similar. Over time, the walks taken through the graph become less “random,” producing a probability distribution, which can then be analyzed to reveal the semantic relationships between words and sentences.

Project technical lead Jake Doody said the process resembles a word association game — but on a much larger scale.

“Say for each word in a social media post, you’re picking another word that’s somehow related,” he said. “From that, you end up with a word cloud for each word. And by comparing those word clouds with one another, you can identify semantic relationships.”

Previous uses of random walks to perform semantic text similarity have scored well against WordNet, a large, publicly available database of English words that are linked by a variety of semantic relationships, such as synonyms, antonyms, homonyms and metonyms.

“We were very interested in those results, but because of how big the graphs are — you’re potentially looking at hundreds of thousands of words — it’s a very slow process using classical computing. We were curious if we could speed it up by doing a quantum random walk instead,” Holden said, noting that quantum algorithms have the potential to be quadratically faster than their classical counterparts.

Heads and Tails

Quantum computers are especially well suited to random walks, thanks to superposition, the property that makes quantum bits (or qubits) unique. A classical bit can take one of two binary values: 0 or 1. Superposition means a qubit can take both values simultaneously, potentially making quantum algorithms much, much faster than their classical counterparts.

“In the coin-flipping analogy, it’s as if a quantum algorithm allows a coin flip to give you both heads and tails in one flip, allowing you to explore multiple paths at once,” Holden said. Based on this principle, the APL team demonstrated that there is a potential for speedup with the use of quantum random walks.

A Generalizable Approach

The researchers shared their results in a recent IEEE . In addition to demonstrating the potential speedup from using a quantum algorithm, the team shared a generalizable approach to setting up a graph to perform random walks — an accomplishment that could add value to a wide variety of quantum algorithm work, according to team member David Zaret.

“We found that the results depend on how the graph is initially set up, which is a prerequisite for defining a quantum random walk at all,” Zaret said. “Our approach to the graph decomposition is one that could be applied in many different use cases.”

“Today, there are a limited number of use cases where quantum computing offers a clear speed advantage,” said Kevin Schultz, assistant manager for APL’s Alternative Computing Paradigms program. “Our team at APL is applying quantum computing to mission-critical national security challenges. Leveraging quantum random walks for semantic text analysis is a novel approach that showcases the unique capabilities of quantum algorithms and could open opportunities for real-world application in new and impactful ways.”

Holden said additional work could include extending the quantum algorithm into multiple languages.

“This approach has the potential to be a lot more interesting in a multilingual case,” she said. “If we were analyzing texts in five languages, would a quantum random walk be more interpretable than a classical computing approach? It’s an open question.”