Quantum annealing can beat classical computing in limited cases

Quantum annealing can beat classical computing in limited cases
Bin Yan (left) and Nikolai Sinitsyn (right) developed an analytical proof based on quantum theory constraining the conditions under which a quantum annealing computer can outperform a classical computer, but only when specific conditions are met. Credit: Los Alamos National Laboratory

Recent research proves that under certain conditions, quantum annealing computers can run algorithms—including the well-known Shor's algorithm—more quickly than classical computers. In most cases, however, quantum annealing does not provide a speed-up compared to classical computing when time is limited, according to a study in Nature Communications.

"We proved that you can be sure you will reach a fast solution from the initial problem, but that's only true for a certain class of problems that can be set up so that the many histories of evolution of the quantum system interfere constructively. Then the different quantum histories enhance each other's probability to reach the solution," said Nikolai Sinitsyn, a theoretical quantum physicist at Los Alamos National Laboratory and coauthor of the paper with his Los Alamos colleague Bin Yan.

While examples of superior quantum performance in simulations are routinely reported, they lack definite proof. Sometimes researchers infer that they have achieved quantum advantage, but they cannot prove that this superiority is over any competing classical algorithm, Sinitsyn said. Such results are often contradictory.

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

"Any problem can be solved heuristically during infinite time," Sinitsyn said. "In practice, though, computation time is always limited. Researchers hope that quantum effects at least reduce the number of errors to make the heuristic approach viable."

To address the uncertainties of the heuristic method, Sinitsyn and coauthor Bin Yan established a different, purely to demonstrate a simple untuned process that solves any computational problem that can be considered by a quantum annealing computer. The accuracy of this computation can be characterized at any point in the computation's run time.

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

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

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

So, the heuristic approaches to quantum computing may finally work but must be considered with lot of care.

Explore further

Anti-butterfly effect enables new benchmarking of quantum computer performance

Journal information: Nature Communications

Citation: Quantum annealing can beat classical computing in limited cases (2022, August 17) retrieved 1 October 2022 from https://phys.org/news/2022-08-quantum-annealing-classical-limited-cases.html
This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no part may be reproduced without the written permission. The content is provided for information purposes only.

Feedback to editors