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 journalArticle

Abstract

Adiabatic quantum computation has recently attracted attention in the physics and computer science communities, but its computational power was unknown. We describe an efficient adiabatic simulation of any given quantum algorithm, which implies that the adiabatic computation model and the conventional 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 stating the main open problems in quantum computation using well-studied mathematical objects such as eigenvectors and spectral gaps of sparse matrices.

Original languageEnglish (US)
Pages (from-to)166-194
Number of pages29
JournalSIAM Journal on Computing
Volume37
Issue number1
DOIs
StatePublished - 2007

Keywords

  • Adiabatic computation
  • Nearest neighbor interactions
  • Quantum computation

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

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

  • Cite this