Abstract
Real-life quantum computers are inevitably affected by intrinsic noise resulting in dissipative nonunitary dynamics realized by these devices. We consider an open-system quantum annealing algorithm optimized for such a realistic analog quantum device which takes advantage of noise-induced thermalization and relies on incoherent quantum tunneling at finite temperature. We theoretically analyze the performance of this algorithm considering a -spin model that allows for a mean-field quasiclassical solution and, at the same time, demonstrates the first-order phase transition and exponential degeneracy of states, typical characteristics of spin glasses. We demonstrate that finite-temperature effects introduced by the noise are particularly important for the dynamics in the presence of the exponential degeneracy of metastable states. We determine the optimal regime of the open-system quantum annealing algorithm for this model and find that it can outperform simulated annealing in a range of parameters. Large-scale multiqubit quantum tunneling is instrumental for the quantum speedup in this model, which is possible because of the unusual nonmonotonous temperature dependence of the quantum-tunneling action in this model, where the most efficient transition rate corresponds to zero temperature. This model calculation is the first analytically tractable example where open-system quantum annealing algorithm outperforms simulated annealing, which can, in principle, be realized using an analog quantum computer.
- Received 9 September 2015
DOI:https://doi.org/10.1103/PhysRevX.6.021028
This article is available under the terms of the Creative Commons Attribution 3.0 License. Further distribution of this work must maintain attribution to the author(s) and the published article’s title, journal citation, and DOI.
Published by the American Physical Society
- *The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of ODNI, IARPA, AFRL, or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purpose notwithstanding any copyright annotation thereon.
Physics Subject Headings (PhySH)
Popular Summary
Implementing universal quantum computation remains years away given the requirement of resource-intensive error correction to mitigate the effect of intrinsic hardware noise. Nevertheless, existing hardware is suitable for the implementation of optimization algorithms such as open-system quantum annealing in which the minimum value of a complex function of a large number of binary variables is sought. Open-system quantum annealing is closely related to classical simulated annealing that relies on stochastic dynamics and relaxation toward thermal equilibrium. Here, we present a tailored solvable example that demonstrates a regime in which the open-system quantum annealing algorithm outperforms simulated annealing.
We consider a model consisting of Ising spins that interact with each other; both pairwise interaction and interaction of triples of spins are included. Our model is characterized by a unique ground state and a metastable state with exponential degeneracy. Open-system quantum annealing includes quantum tunneling, which may improve the relaxation times. However, identifying a class of problems in which open-system quantum annealing provides a computational advantage remains an open question. We use a quasiclassical description to analyze the performance of the open-system quantum annealing algorithm optimized to take advantage of the noise-induced dissipative relaxation and quantum tunneling through potential barriers, and we identify a regime in which quantum annealing is superior. This work represents progress that could, in principle, be implemented on realistic hardware, and the speedup mechanism that we recover, which is most efficient at vanishing temperature, may have many applications.
We expect that the generic features identified in this example may make it possible to classify complex optimization problems in terms of open-system, quantum annealing performance.