Adiabatic quantum computation is equivalent to standard quantum computation

Dorit Aharonov, Wim Van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev

Research output: Contribution to journalReview article

Abstract

The model of adiabatic quantum computation is a relatively recent model of quantum computation that has attracted attention in the physics and computer science communities. We describe an efficient adiabatic simulation of any given quantum circuit. This implies that the adiabatic computation model and the standard circuit-based quantum computation model are polynomially equivalent. Our result can be extended to the physically realistic setting of particles arranged on a two-dimensional grid with nearest neighbor interactions. The equivalence between the models allows one to state the main open problems in quantum computation using well-studied mathematical objects such as eigenvectors and spectral gaps of Hamiltonians.

Original languageEnglish (US)
Pages (from-to)755-787
Number of pages33
JournalSIAM Review
Volume50
Issue number4
DOIs
StatePublished - 2008

Keywords

  • Adiabatic computation
  • Nearest neighbor interactions
  • Quantum computation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Adiabatic quantum computation is equivalent to standard quantum computation'. Together they form a unique fingerprint.

  • Cite this

    Aharonov, D., Van Dam, W., Kempe, J., Landau, Z., Lloyd, S., & Regev, O. (2008). Adiabatic quantum computation is equivalent to standard quantum computation. SIAM Review, 50(4), 755-787. https://doi.org/10.1137/080734479