LANL Research finds quantum annealing can beat classical computing in limited cases

LOS ALAMOS, New Mexico, August 15, 2022 — Recent research proves that under certain conditions, quantum annealing computers can run algorithms, including Shor’s famous algorithm, faster than classical computers. In most cases, however, quantum annealing does not provide a speedup over classical computation when time is limited, according to a study in Nature Communications.

“We have proven that you can be sure of reaching a quick solution from the initial problem, but this is only true for a certain class of problems that can be set up in such a way that the many stories of evolution of the quantum system interfere constructively. Then the different quantum histories mutually enhance the likelihood of reaching the solution,” said Nikolai Sinitsyn, a theoretical quantum physicist at Los Alamos National Laboratory and co-author of the paper with his Los Alamos colleague Bin Yan.

Although examples of superior quantum performance in quantum annealing simulations are regularly reported, they lack definitive evidence. Sometimes researchers infer that they have achieved a quantum advantage, but they cannot prove that this superiority is superior to any competing classical algorithm, Sinitsyn said. Such results are often contradictory.

Quantum computing transforms a simple quantum state into a state with a computational result. In a handful of quantum algorithms, this process is tuned to outperform classical algorithms. A suitable algorithm is specially designed to ensure the constructive interference of different system histories during computation, which is the key to quantum computing. For example, in quantum annealing, one can tune the time-dependent path for specific problems. Untuned quantum algorithms, called heuristics, are used in quantum annealing computers. They do not guarantee such interference.

“Any problem can be solved heuristically for an infinite time,” Sinitsyn said. “In practice, however, the computation time is always limited. The researchers hope that the quantum effects will at least reduce the number of errors to make the heuristic approach viable.

To address the uncertainties of the heuristic method, Sinitsyn and co-author Bin Yan established a different, purely analytical approach to demonstrate a simple, untuned process that solves any computational problem that can be considered by an annealing computer. quantum. The precision of this calculation can be characterized at any moment of the execution time of the calculation.

Unfortunately, Sinitsyn and Yan found that this accuracy is almost always no better than the performance of a classical algorithm.

The reason for this is that efficient quantum computing relies on quantum effects, such as constructive interference, when many different quantum stories, which are simultaneously experienced by a quantum processor, interfere to amplify useful information in the final state. Without fine tuning, proper interference becomes unlikely. There are, however, rare exceptions, which leave room for higher quantum computing.

Another inspiring discovery was the observation that the considered process does not encounter the so-called spin glass transition, which corresponds to an extremely slow elimination of computational errors, and which is a big drawback of classical annealing computational strategies. .

Thus, heuristic approaches to quantum computing may finally work but must be considered with great caution.

The paper: Analytical solution for non-adiabatic quantum annealing at an arbitrary Ising spin Hamiltonian, in Nature Communications, by Bin Yan & Nikolai A. Sinitsyn, in Nature Communications. DOI: 10.1038/s41467-022-29887-0

Funding : US Department of Energy, Office of Science, Basic Energy Sciences, Materials Sciences, and Engineering Division, Condensed Matter Theory Program.

Source: LANL

Sherry J. Basler