The first exponential quantum advantage for the natural streaming problem

As the hare learned from the tortoise, speed is not everything. Theoretical computer scientists at Sandia National Laboratories and Boston University have found that quantum computers have no competition in solving an advanced mathematical problem. Unusually, they proved that quantum computers are not faster than ordinary computers; instead, they use much less memory.

The revelation confirms the conventional wisdom that the value of a quantum computer is that it can solve certain problems much faster than a regular computer. It could also help researchers find more realistic uses for the rapidly developing technology.

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

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

The team presented their findings at the Symposium on Theory of Computing, held June 24-28 in Vancouver, British Columbia. A mathematical proof is available at arXiv prepress server.

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

In 1994, American scientist Peter Shor startled the world when he proved that future quantum computers would be able to break standard encryption algorithms alarmingly fast. However, over the past 30 years, researchers have found just a few other problems that these computers can solve faster than normal computers.

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

“Much of the focus of quantum advantage research has been on achieving a time advantage,” said Nadezhda Voronova, Ph.D. candidate in the Department of Computer Science at Boston University. “Research on the quantum advantage with respect to other resources such as memory has been relatively limited.”

Shifting the focus to these other attributes, such as efficiency, could help scientists find more practical uses for quantum computers.

“Are we currently missing important quantum advantages because we are focused or biased toward certain kinds of problems?” Parekh said.

What is a natural streaming problem and why does it matter?

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

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

Parekh further explained, “The maximum directed constraint problem amounts to finding two groups of agents in a network with the most communication directed from one group to the other. This problem finds applications in cybersecurity and social network analysis and design.”

Computers usually need a lot more memory as this kind of problem becomes more complex. But quantum computers don’t, the team found. They are exponentially more efficient with memory usage, at least when the data is coming in a stream. Streaming calculations are useful when data sets are too large to fit in computer memory or when data is generated continuously.

Kallaugher previously published that quantum computers could have a significant but smaller advantage than what he and his team have now demonstrated. The new finding of the exponential ratio is significant because the benefit must be very large to be worth the time and money it takes to build and operate a quantum computer.

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

Discovery hints at future roles for quantum computers

A maximum directed cut is not very useful by itself. However, it is a well-known optimization problem in advanced mathematics that the research team sees as an indication of the practical use of quantum computers in the future.

“For example, in the field of cyber security, effectively solving optimization problems could lead to better resource allocation, better incident response strategies and more accurate risk assessment,” said Voronová.

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

“There could be more such algorithms,” speculated Voronová.

“No one really has the full picture,” Parekh said.