Adiabatic quantum computation is equivalent to standard quantum computation

By Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev. 45th Annual IEEE Symposium on Foundations of Computer Science, 2004

964 citations recorded by the source corpus.

The model of adiabatic quantum computation has recently attracted attention in the physics and computer science communities, but its exact computational power has been unknown. We settle this question and describe an efficient adiabatic simulation of any given quantum algorithm. This implies that the adiabatic computation model and the standard quantum circuit model are polynomially equivalent. We also describe an extension of this result with implications to physical implementations of adiabatic computation. We believe that our result highlights the potential importance of the adiabatic computation model in the design of quantum algorithms and in their experimental realization.

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

View Paper: https://www.semanticscholar.org/paper/ab891721d230583649a4af16d8af6f602ff2f6b8

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 Supremacy through the Quantum Approximate Optimization Algorithm (2016, background): “It is known that adiabatic quantum computing is a universal form of quantum computing [5].”
Quantum information processing with superconducting circuits: a review (2016, background): “AQO is in principle universal [80] and equivalent to the digital circuit model.”
Adiabatic Quantum Computing (2016, methodology): “(73c) The full time independent Hamiltonian H(s) is given by (Aharonov et al., 2007): H(s) = (1− s)Hinit + sHfinal (74) = Hinput +Hc + (1− s)Hc−init + s 2 Hcircuit .”
Minor-embedding in adiabatic quantum computation: I. The parameter setting problem (2008, background): “In 2004, Aharonov et al [1] proved the more difﬁcult converse statement that standard quantum computation can be efﬁciently simulated by AQC.”
Qudits and High-Dimensional Quantum Computing (2020, methodology): “There are various approaches to quantum computing besides the gate-based model, such as the measurement-based [134]; adiabatic quantum computing [3, 55] and topological quantum computing [57].”
Spin- 1 ∕ 2 particles moving on a two-dimensional lattice with nearest-neighbor interactions can realize an autonomous quantum computer (2005, methodology): “rd model of the quantum computer is based on one- and two-qubit unitaries there is meanwhile a large number of alternative proposals, e.g. computing by measurements only [1, 2] or adiabatic computing [3, 4, 5, 6, 7]. The latter model encodes a computational problem into an interaction such that the ”
Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design (2010, background): “Later, it was shown by Aharonov et al. [1] that AQC is not just limited to optimization problems, and is polynomially equivalent to conventional quantum computation (quantum circuit model).”
Ising machines as hardware solvers of combinatorial optimization problems (2022, background): “The Reference for publication source of the plotted data is given. important from a computational complexity perspective as adiabatic quantum computation with non-stoquastic Hamiltonians is equivalent to the circuit model of quantum computing 208 .”