Quantum Computation by Adiabatic Evolution

By Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Michael Sipser. 2000

1,807 citations recorded by the source corpus.

We give a quantum algorithm for solving instances of the satisfiability problem, based on adiabatic evolution. The evolution of the quantum state is governed by a time-dependent Hamiltonian that interpolates between an initial Hamiltonian, whose ground state is easy to construct, and a final Hamiltonian, whose ground state encodes the satisfying assignment. To ensure that the system evolves to the desired final ground state, the evolution time must be big enough. The time required depends on the minimum energy difference between the two lowest states of the interpolating Hamiltonian. We are unable to estimate this gap in general. We give some special symmetric cases of the satisfiability problem where the symmetry allows us to estimate the gap and we show that, in these cases, our algorithm runs in polynomial time.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/3b75692ea8f3d29dfdd6eb250c6d5edae48c1f16

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 Computational Theory and Mathematics

Citations in the corpus

Quantum algorithms: an overview (2015, positive): “M+ p N) [70]. This is a superpolynomial speedup when Mis large. 3.3 Adiabatic optimisation An alternative approach to quantum combinatorial optimisation is provided by the quantum adiabatic algorithm [40]. The adiabatic algorithm can be applied to any constraint satisfaction problem (CSP) where we a”
Minor-embedding in adiabatic quantum computation: I. The parameter setting problem (2008, methodology): “Farhi et al. in their original paper [15] showed that AQC can be efﬁciently simulated by standard quantum computers.”
Challenges and opportunities in quantum optimization (2023, neutral): “The first quantum-computing approach proposed for solving unconstrained discrete-optimization problems was the quantum annealing algorithm 2,3,44 .”
Digitized adiabatic quantum computing with a superconducting circuit (2015, background): “In adiabatic quantum computing [4–6], the system is slowly evolved from the ground state of a simple initial Hamiltonian to a ﬁ-nal Hamiltonian that encodes a computational problem.”
Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design (2010, methodology): “Adiabatic quantum computation (AQC) was proposed by Farhi et al. [10,11] in 2000 as an alternative quantum paradigm to solve NP-hard optimization problems, which are believed to be classically intractable.”
Decoherence in adiabatic quantum computation (2015, methodology): “In the adiabatic quantum computing paradigm [2], or in quantum annealing [41, 42], a computation is performed by evolving a system using a time-dependent Hamiltonian, with the final ground state encoding the solution of the computational problem.”
Ising machines as hardware solvers of combinatorial optimization problems (2022, background): “The parameterized quantum circuit transfers the initial state to the ground state of the target problem Hamiltonian (in the ideal case) by alternately applying the unitary operator corresponding to the problem Hamiltonian e − i γ j H P and the unitary operator e − i β j H 0 .”
Quantum machine learning: a classical perspective (2017, methodology): “Another name which is frequently used in the literature as synonym of QAA and AQC is quantum annealing (QA).”
Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems (2019, methodology): “These machines have been developed by various approaches: quantum computers based on quantum annealing ( 8 , 9 ) or quantum adiabatic optimization ( 10 – 12 ) implemented with superconducting circuits ( 13 , 14 ), coherent Ising machines (CIMs) implemented with laser pulses ( 15 – 20 ), and Ising…”
The future of quantum computing with superconducting qubits (2022, methodology): “This is general enough to represent the circuit model 133 , the measurement model 134 , and the adiabatic model 135 of computation, and special routines such as teleportation.”
Optimal Hamiltonian Simulation by Quantum Signal Processing. (2016, background): “Access to two oracles ÔH , ÔF is commonly assumed: ÔH accepts the input (j, k) ∈ [2]× [2] on 2n-qubit registers and returns Hj,k = 〈j|Ĥ|k〉 in another m-qubit register.”
Adiabatic quantum state generation and statistical zero knowledge (2003, methodology): “For two classical distributions { p ( x ) } , { q ( x ) } deﬁne their ℓ 1 distance and their ﬁdelity (this measure is known by many other names as well): We also deﬁne the variation distance to be || p − q = | p − q 1 so that it is a value between 0 and 1. useful The following fact is very : Fact 1.”
Quantum Supremacy through the Quantum Approximate Optimization Algorithm (2016, methodology): “With the Quantum Adiabatic Algorithm in optimization mode, we are seeking the maximum of the cost function C given by (2).”
Quantum computing for finance: Overview and prospects (2018, methodology): “At the heart of quantum optimization algorithms is a method known as adiabatic quantum computation [7], which we will describe in the following.”
Hamiltonian simulation using linear combinations of unitary operations (2012, methodology): “Even before a fault-tolerant quantum computer is built, quantum simulation techniques can be used to prove equivalence between Hamiltonian-based models of quantum computing (such as adiabatic quantum computing [1] and continuous-time quantum walks [2]) and to develop novel quantum algorithms [3–7].”
Adiabatic Quantum Computing (2016, background): “The initial Hamiltonian is taken to be H0 = (n− 1)(n− 2) 2 (n 2 1 − Sx ) , (199) [the unconventional normalization is to ensure that both H1 and H0 scale similarly with n (Farhi et al., 2000)].”