BREAKTHROUGH – Better Algorithms for Classical Computers to Efficiently Compete With Quantum Computers

A new algorithm can further exploit the twin challenges of information loss and translation to mimic a quantum computer with far fewer resources than previously thought.

It was previously though that quantum computers with 50-100 logical low error qubits would be able to surpass regular supercomputers. New algorithms are showing that regular computers could beat low error quantum computers with 127 qubits and possibly more.

PRX Quantum – Efficient Tensor Network Simulation of IBM’s Eagle Kicked Ising Experiment

Above -Tensor network state for the infinite heavy hex lattice. The unit cell is a five-site tensor network. By adding in appropriate periodic boundary conditions and simulating the kicked Ising model with the BP-approximated TNS method we recover results for simulation of the infinite lattice with the BP-approximated TNS method.

ABSTRACT
We report an accurate and efficient classical simulation of a kicked Ising quantum system on the heavy hexagon lattice. A simulation of this system was recently performed on a 127-qubit quantum processor using noise-mitigation techniques to enhance accuracy. Here we show that, by adopting a tensor network approach that reflects the geometry of the lattice and is approximately contracted using belief propagation, we can perform a classical simulation that is significantly more accurate and precise than the results obtained from the quantum processor and many other classical methods. We quantify the treelike correlations of the wave function in order to explain the accuracy of our belief propagation-based approach. We also show how our method allows us to perform simulations of the system to long times in the thermodynamic limit, corresponding to a quantum computer with an infinite number of qubits. Our tensor network approach has broader applications for simulating the dynamics of quantum systems with treelike correlations.

Quantum Advantage Discussion

Quantum computers have plenty of potential as tools for carrying out complex calculations. But exactly when their abilities will surpass those of their classical counterparts is an ongoing debate. Recently, a 127-qubit quantum computer was used to calculate the dynamics of an array of tiny magnets, or spins—a problem that would take an unfathomably long time to solve exactly with a classical computer. The team behind the feat showed that their quantum computation was more accurate than nonexact classical simulations using state-of-the-art approximation methods. But these methods represented only a small handful of those available to classical-computing researchers. Now Joseph Tindall and his colleagues at the Flatiron Institute in New York show that a classical computer using an algorithm based on a so-called tensor network can produce highly accurate solutions to the spin problem with relative ease. The results show that the classical-computing field still has many tricks up its sleeve, making it hard to predict when the quantum-computing field will gain the upper hand.

The new classical method uses tensor networks—series of data arrays connected through links. Physicists have long used tensor networks to study many-body quantum systems, such as the electrons in a superconductor or the atoms in a molecule. The networks allow them to compress the enormous amounts of information contained in a full description of the wave function of such a system. “A tensor network is essentially like a zip file for the wave function,” Tindall says.

Tindall and his colleagues designed a “zip file” that simulates the 127 qubits in IBM’s computer. To fully represent the wave function of these qubits would require 2^127≈ 10^38 numbers, which in bytes would be trillions and trillions of times more data than are stored on all the computers in the world. The researchers reduced the amount of data needed to less than about a billion numbers by assuming that some of the wave function’s information—specifically some of the information about the quantum entanglement between qubits—could be neglected.

Applying their network to the Ising-model problem, Tindall and his colleagues solved the problem on a classical computer with greater accuracy than achieved using the quantum one. Tindall notes that Kandala and his colleagues also performed tensor-network computations as part of their classical comparison. But he says that the network they chose wasn’t explicitly designed to have the same geometry as their computer. Making a different choice meant that Tindall and his colleagues did not require a supercomputer to run their tests. “You could run some of the simulations on a mobile phone,” he says.

Tindall and his colleagues “have successfully applied a novel classical algorithm to a timely problem that is of relevance to a large part of the physics community,” says Michael Lubasch, a scientist at the quantum-computing company Quantinuum. But Lubasch stresses that the classical algorithm the team used is tailored to work for a particular Ising-model problem. Researchers cannot use this algorithm to simulate every computation that a quantum computer can do.

He calls the back and forth between the quantum- and classical-computing communities a “symbiotic relationship,” in which the two sides challenge each other by developing ever-more sophisticated computing methods. The challenge of quantum computers forces classical computer researchers to push harder to improve calculation and algorithms.

Quantum computing is not the only thing that’s improving. Classical methods are also improving and have been improving for decades.

The scientists’ results show that classical computing can be reconfigured to perform faster and more accurate calculations than state-of-the-art quantum computers.

This breakthrough was achieved with an algorithm that keeps only part of the information stored in the quantum state—and just enough to be able to accurately compute the final outcome.

“This work shows that there are many potential routes to improving computations, encompassing both classical and quantum approaches,” explains Dries Sels, an assistant professor in New York University’s Department of Physics and one of the paper’s authors. “Moreover, our work highlights how difficult it is to achieve quantum advantage with an error-prone quantum computer.”

In seeking ways to optimize classical computing, Sels and his colleagues at the Simons Foundation focused on a type of tensor network that faithfully represents the interactions between the qubits. Those types of networks have been notoriously hard to deal with, but recent advances in the field now allow these networks to be optimized with tools borrowed from statistical inference.

The authors compare the work of the algorithm to the compression of an image into a JPEG file, which allows large images to be stored using less space by eliminating information with barely perceivable loss in the quality of the image.

“Choosing different structures for the tensor network corresponds to choosing different forms of compression, like different formats for your image,” says the Flatiron Institute’s Joseph Tindall, who led the project. “We are successfully developing tools for working with a wide range of different tensor networks. This work reflects that, and we are confident that we will soon be raising the bar for quantum computing even further.”