How powerful is adiabatic quantum computation?

By Wim van Dam, Michele Mosca, Umesh V. Vazirani. Proceedings IEEE International Conference on Cluster Computing, 2001

321 citations recorded by the source corpus.

The authors analyze the computational power and limitations of the recently proposed 'quantum adiabatic evolution algorithm'. Adiabatic quantum computation is a novel paradigm for the design of quantum algorithms; it is truly quantum in the sense that it can be used to speed up searching by a quadratic factor over any classical algorithm. On the question of whether this new paradigm may be used to efficiently solve NP-complete problems on a quantum computer, we show that the usual query complexity arguments cannot be used to rule out a polynomial time solution. On the other hand, we argue that the adiabatic approach may be thought of as a kind of 'quantum local search'. We design a family of minimization problems that is hard for such local search heuristics, and establish an exponential lower bound for the adiabatic algorithm for these problems. This provides insights into the limitations of this approach. It remains an open question whether adiabatic quantum computation can establish an exponential speed-up over traditional computing or if there exists a classical algorithm that can simulate the quantum adiabatic process efficiently.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics

View Paper: https://www.semanticscholar.org/paper/8a1be838f1da5f332b494b62f8c787dd55210471

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Atomic and Molecular Physics, and Optics

Citations in the corpus

Quantum algorithms: an overview (2015, unknown): “One can construct problem instances on which the standard adiabatic algorithm provably takes exponential time [94, 39]; however, changing the algorithm can evade some of these arguments [36, 29].”
Minor-embedding in adiabatic quantum computation: I. The parameter setting problem (2008, background): “Despite several serious investigations, the power of AQC remains an open question [24, 25, 22, 16, 1].”
Coherent Ising machine based on degenerate optical parametric oscillators (2013, methodology): “aling, quantum adiabatic computation was devised according to the adiabatic theorem of quantum mechanics [13], with computational power equivalent to that of a quantum computer based on unitary gates [14, 15]. Despite the fact that none of these methods are generally proven to be eﬃcient, taking adv”
Adiabatic quantum computation is equivalent to standard quantum computation (2004, background): “From the algorithmic point of view, these result show that all quantum algorithmic questions can be framed in the language of eigenstates and spectral gaps of local or even sparse Hermitian matrices.”
Challenges and opportunities in quantum optimization (2023, unknown): “The amount of time needed to ensure that quantum annealing produces optimal solutions is proportional to the minimum gap in the eigenspectrum of the quantum Hamiltonian during the evolution process, which is known to shrink exponentially with n for many interesting optimization problems 46 .”
Digitized adiabatic quantum computing with a superconducting circuit (2015, background): “As quantum hardware improves, the implementation of near-optimal schemes such as this becomes increasingly viable.”