Quantum annealing can beat classical computing in limited cases
Under most conditions, according to a new proof, algorithms on a quantum annealing computer don’t offer quantum speed-up.
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 quantum annealing 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 analytical approach 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 algorithm.
The reason is that efficient quantum computing relies on quantum effects, 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.
The Paper: Analytical solution for nonadiabatic quantum annealing to arbitrary Ising spin Hamiltonian, in Nature Communications, by Bin Yan & Nikolai A. Sinitsyn, in Nature Communications. DOI: 10.1038/s41467-022-29887-0
LA-UR-22-28266
Media Contact
Charles Poling
DOE/Los Alamos National Laboratory
cpoling@lanl.gov
Cell: 505-257-8006
All latest news from the category: Information Technology
Here you can find a summary of innovations in the fields of information and data processing and up-to-date developments on IT equipment and hardware.
This area covers topics such as IT services, IT architectures, IT management and telecommunications.
Newest articles
Record Efficiency – Tandem Solar Cells made from Perovskite and Organic Material
Trying to improve the efficiency of solar cells to become independent from fossil energy sources is a major goal of solar cell research. A team around the physicist Dr. Felix…
Better response to infectious diseases and pandemics through data
The Leibniz Institute DSMZ is now a partner in the global consortium for the development of the ‘Pathogen Data Network’. The US National Institute of Health (NIH) has funded the…
Cosmic cartography – mapping the gravitational wave background
The most sensitive map of the gravitational wave sky to date was produced by an international collaboration of researchers including numerous scientists from the Max Planck Institute for Radio Astronomy…