The first quantum exponential advantage for a natural transmission 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 are unmatched in solving an advanced mathematical problem. Unusually, they proved that quantum computers are no faster than ordinary computers; instead, they use much less memory.

The discovery overturns the conventional wisdom that the value of a quantum computer is that it can solve some problems much faster than a normal computer. It can also help researchers find more real-world uses for the rapidly advancing technology.

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

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 to build multi-qubit quantum computers,” 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 math test is available at arXiv preprint server.

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

In 1994, American scientist Peter Shor shocked the world when he proved that future quantum computers would be able to break standard encryption algorithms in an alarming way. However, in the 30 years since then, researchers have found only a handful of other problems that these computers can solve faster than normal computers.

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

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

Shifting attention 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 types of problems?” Parekh said.

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

The math problem at the heart of the team’s claim, called maximum directed shear, is significant because it is what researchers call a natural problem.

“When we talk about a natural problem,” said Sandia’s John Kallaugher, “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 maximal directed truncation problem is to find two groups of agents in a network with the largest directed communication from one group to the other. This problem finds applications in cyber security and social network analysis and design. “

Computers usually need more memory as this type of problem becomes 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 into a computer’s memory or when data is generated continuously.

Kallaugher previously published that quantum computers may have a distinct but smaller advantage than what he and his team have now tested. The new discovery of an exponential ratio is important because an advantage would have to be very large to be worth the time and money needed 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.

The discovery suggests future roles for quantum computing

Maximum directional shear is not very useful on its own. Still, it’s a well-known optimization problem in advanced mathematics that the research team sees as a hint at the kinds of practical uses quantum computers might have 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 too large for any classical computer to process.”

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

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