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 Labs and Boston University have discovered that quantum computers are unrivaled at solving a complex mathematical problem. Unusually, they proved that quantum computers are no faster than classical computers; in fact, they use much less memory.

The discovery overturns the conventional wisdom that the value of a quantum computer lies in its ability to solve certain problems much faster than a normal computer. It could also help researchers find more concrete applications for this evolving technology.

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

Memory is an important component of 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 their results at the Symposium on Theory of Computing, held June 24-28 in Vancouver, British Columbia. The mathematical proof is available at arXiv preprint server.

The value of quantum computers may lie in memory efficiency, not just speed

In 1994, American scientist Peter Shor surprised the world by proving that future quantum computers would be able to crack standard encryption algorithms at alarming speeds. In the 30 years since, however, researchers have discovered only a handful of other problems that these computers can solve faster than regular computers.

Research from Sandia and Boston University now points to another area where quantum advantage is possible.

“Research on quantum advantages has focused primarily on gaining a time advantage,” said Nadezhda Voronova, a doctoral student in the Department of Computer Science at Boston University. “Research on quantum advantages over other resources, such as memory, has been relatively limited.”

By focusing on these other attributes, such as efficiency, scientists might find more practical uses for quantum computers.

“Are we currently missing out on important quantum advantages because we focus or are biased toward certain types of problems?” Parekh said.

What is a natural streaming problem and why is it important?

The mathematical problem at the center of the team’s claim, called maximum directed cutting, is important because it is what the researchers call a natural problem.

“When we talk about a natural problem,” said John Kallaugher of Sandia, “what we mean is that it’s a problem of independent interest, that people were already studying it in the classical framework.”

Parekh then explained: “The maximum directed cutoff problem is to find the two groups of agents in a network with the most directed communication from one group to the other. This problem has applications in cybersecurity and social network analysis and design.”

Computers typically need much more memory as these types of problems become more complex. But that’s not the case with quantum computers, the team found. They use memory exponentially more efficiently, at least when the data arrives in a stream. Streaming computations are useful when data sets are too large to fit in a computer’s memory or when data is being created continuously.

Kallaugher had previously published a paper suggesting that quantum computers might have a distinct, but smaller, advantage than he and his team have proven so far. The new finding of an exponential ratio is important because an advantage would have to be very large to justify the time and money it would take to build and operate a quantum computer.

Like Shor’s algorithm, the new discovery is still theoretical because it has not yet been demonstrated on a computer.

Discovery hints at future roles of quantum computing

Directed maximum cutoff isn’t very useful on its own. However, it’s a well-known optimization problem in advanced mathematics, which the research team sees as a hint at the kinds of practical uses quantum computers might have in the future.

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

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

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

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