Theoretical scientists John Kallaugher, left, and Ojas Parekh find tasks in which quantum computers outperform classical computers at Sandia. (Photo by Craig Fritz)
Theoretical scientists at Sandia National Laboratories and Boston University say they have discovered that quantum computers are unrivaled at solving an advanced math problem. But the big advantage delivered by quantum was not faster processing than classical HPC, it was the use of far less memory.
The finding upends the conventional wisdom that the value of a quantum computer is that it can — or may in the future — solve certain problems much faster than classical computers. It could also help researchers find more real-world uses for quantum technology.
“This is the first exponential quantum advantage for a natural streaming problem,” said Sandia’s Ojas Parekh, a member of the team.
Memory is important for any computer. The more memory it has, the bigger problems it can solve. For quantum computers, which store information in qubits, “Space really matters because it’s hard building quantum computers with lots of qubits,” Ojas said.
The team is presenting its findings at the Symposium on Theory of Computing, June 24-28 in Vancouver, British Columbia. The mathematical proof is available on the website arXiv.
Sandia’s Laboratory Directed Research and Development program and the DOE’s Office of Science, Office of Advanced Scientific Computing Research (ASCR), funded the work.
Memory Efficiency, Not Just Speed
In 1994, American scientist Peter Shor startled the world when he proved future quantum computers would be able to crack standard encryption algorithms alarmingly fast. In the 30 years since, however, researchers have only found a handful of other problems these computers can solve quicker than normal ones.
The research emerging from Sandia and Boston University now points to a different area where quantum advantage is possible.
“Much of the focus in quantum advantage research has been on achieving time advantage,” said Nadezhda Voronova, a Ph.D. candidate in Boston University’s department of computer science. “Research on quantum advantage with respect to other resources, like memory, has been relatively limited.”
Shifting attention to these other attributes, like efficiency, could help scientists find more practical uses for quantum computers.
“Are we currently missing important quantum advantages because we’re focused or biased toward certain kinds of problems?” Ojas said.
Natural Streaming Problems
The math problem at the center of the team’s claim, called maximum-directed cut, is significant because it is what researchers call a natural problem.
“When we talk about a natural problem,” said John Kallaugher from Sandia, “what we mean is that it’s a problem of independent interest — that people were already studying it in the classical setting.”
Ojas further explained, “The max-directed cut problem amounts to finding the two groups of agents in a network with the most communication directed from one group to another. This problem finds applications in cybersecurity and social network analysis and design.”
Nadezhda Voronova, a Ph.D. candidate in computer science at BU, shows results of her research at the Quantum Information Processing conference last Junary in Taipei, Taiwan. (Photo courtesy of QIP 2024)
Computers normally need lots more memory as this kind of problem grows more complex. But quantum computers don’t, the team found. They are exponentially more efficient with their memory usage, at least when data arrives in a stream. Streaming calculations are useful when data sets are too large to fit in a computer’s memory or when the data is being created continuously.
Kallaugher previously published that quantum computers could have a distinct but smaller advantage than what he and his team have now proven. The new finding of an exponential ratio is significant because an advantage needs to be very large to be worth the time and money it takes to build and run a quantum computer.
Like Shor’s algorithm, the new finding is still theoretical because it has not yet been demonstrated on a computer.
Future Roles of Quantum Computing
Maximum-directed cut is not very useful on its own. However, it is a widely known optimization problem in advanced mathematics, which the research team sees as a hint to the kinds of practical uses quantum computers could have in the future.
“In cybersecurity, for example, efficiently solving optimization problems could lead to better resource allocation, enhanced incident response strategies and more accurate risk assessments,” Voronova said.
Kallaugher added, “This could point the way to algorithms that can handle problems too large for any classical computer to process.”
“There could be more algorithms like this,” Voronova speculated.
“No one has, really, the complete picture,” Ojas said.
source: Troy Rummler, Sandia National Laboratories
Speak Your Mind