June 27, 2024 -- As the hare learned from the tortoise, speed isn’t everything. Theoretical scientists at Sandia and Boston University have discovered that quantum computers are unrivaled at solving an advanced math problem. Unusually, they proved quantum computers are not faster than regular computers; instead, they use far less memory.

The revelation upends the conventional wisdom that the value of a quantum computer is that it can solve certain problems much faster than a normal one. It could also help researchers find more real-world uses for the rapidly advancing tech.

“This is the first exponential quantum advantage for a natural streaming problem,” said Sandia’s Ojas Parekh, a member of the team. Like Shor’s algorithm, the new finding is still theoretical because it has not yet been demonstrated on a computer.

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.

“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.

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.

Ojas 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.”

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.

John 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.

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.