The first exponential quantum advantage for a natural streaming problem

As the hare learned from the tortoise, speed isn’t everything. Theoretical computer scientists at Sandia National Laboratories 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.

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,” Parekh said.

The team presented its findings at the Symposium on Theory of Computing, which ran from June 24–28 in Vancouver, British Columbia. The mathematical proof is available on the arXiv preprint server.

Value of quantum computers could be 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?” Parekh said.

What a natural streaming problem is, and why it matters

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

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

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.

Discovery hints at 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,” Parekh said.