Quantum Computers Beat Classical at Math Problems

Researchers from Sandia National Laboratories and Boston University have demonstrated that quantum computers can solve an advanced math problem using much less memory.

While much of the search for a quantum advantage has focused on reducing the processing time for complex problems, efficient memory use could help develop quantum solutions to real-world issues sooner.

Memory is important in any computing paradigm. Generally, the more memory a computer has, the faster it can solve problems.

Quantum computers store memory in qubits but scaling to a usable number of error-corrected, usable qubits is one of the biggest challenges the industry currently faces. Using less memory means they may find solutions for practical use cases sooner than expected.

“Much of the focus in quantum advantage research has been on achieving time advantage,” said Boston University doctoral candidate Nadezhda Voronova.

“Research on quantum advantage with respect to other resources, like memory, has been relatively limited.”

The team used a mathematical problem called maximum directed cut. It is known as a natural problem, meaning people were already studying it in a classical environment, rather than one invented to demonstrate a certain capability.

“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,” said Sandia team member Ojas Parekh.

Related:Home Quantum Computer Emulator Launched on Kickstarter

Classical computers need more memory to solve this kind of problem as it gets more complex. The researchers found that quantum computers do not as they get exponentially more efficient with their memory usage when the data arrives in a stream, as in the maximum directed cut problem.

“This is the first exponential quantum advantage for a natural streaming problem,” said Parekh.