Quantum annealing can beat classical computing in limited cases

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.