The first exponential quantum advantage for a natural flow problem

As the hare learned from the tortoise, speed isn’t everything. Theoretical computer scientists from Sandia National Laboratories and Boston University have discovered that quantum computers are unmatched at solving a sophisticated mathematical problem. Unusually, they proved that quantum computers are no faster than regular computers; instead, they use much less memory.

The revelation turns on its head 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 applications for the rapidly advancing technology.

“This is the first exponential quantum advantage for a natural flow problem,” said Sandia’s Ojas Parekh, a member of the team.

Memory is important to any computer. The more memory, the bigger the problems it can solve. For quantum computers, which store information in qubits, “space is really important, because it’s hard to build quantum computers with lots of qubits,” Parekh said.

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

The value of quantum computers could be memory efficiency, not just speed

In 1994, American scientist Peter Shor surprised the world when he proved that future quantum computers could crack standard encryption algorithms at an alarmingly fast rate. In the 30 years since, however, researchers have found only a handful of other problems that these computers can solve faster than normal computers.

The Sandia and Boston University research now points to another area where quantum advantage is possible.

“A lot of the focus in quantum advantage research has been on gaining a time advantage,” said Nadezhda Voronova, a Ph.D. candidate in Boston University’s computer science department. “Research on quantum advantage with respect to other resources, such as memory, has been relatively limited.”

By shifting attention to these other properties, such as efficiency, scientists may be able to find more practical applications for quantum computers.

“Are we currently missing out on important quantum advances because we focus on or favor certain types of problems?” Parekh said.

What a Natural Streaming Problem Is and Why It Matters

The mathematical problem at the heart of the team’s claim, called the “maximum directed cut,” is important because the researchers call it a “natural problem.”

“When we talk about a natural problem,” says Sandia’s John Kallaugher, “we mean it’s a problem of independent interest that people have already studied in the classical setting.”

Parekh further explained: “The max directed cut problem boils down to finding the two groups of agents in a network with the most communication directed from one group to the other. This problem has applications in cybersecurity and social network analysis and design.”

Computers typically require much more memory as these types of problems become more complex. But quantum computers, the team found, are not. They are exponentially more efficient with their memory usage, at least when data arrives in a stream. Streaming computation is 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 clear but smaller advantage than what he and his team have now proven. The new finding of an exponential ratio is significant because an advantage has 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, as it has not yet been run on a computer.

Discovery hints at future role of quantum computing

Maximum directed cut is not very useful by itself. However, it is a well-known optimization problem in advanced mathematics, which the research team sees as a hint at the kinds of practical applications of quantum computers in the future.

“In cybersecurity, for example, efficiently solving optimization problems can lead to better resource allocation, improved incident response strategies, and more accurate risk assessments,” Voronova said.

Kallaugher added: “This could point the way to algorithms that can handle problems that are too big for a classical computer.”

“There could be more algorithms like this,” Voronova speculated.

“Nobody really has a complete picture,” Parekh said.