Inital Draft
Adiabatic computation (AC) encodes the solution of a problem in the (product) ground-state of a specially crafted Hamiltonian. Directly solving for the ground-state of an arbitary Hamiltonian is hard, but one may try to use a physical system to generate the ground-state, and then by measurement, deduce the solution.
One begins with starting a physical system in an easily generated ground state of an initial Hamiltonian. If the Hamiltonian is changed slowly enough (the so-called adiabatic limit), the adiabatic theorem guarantees that the state of the system will evolve so that it remains the ground state of the instantaneous Hamiltonian. At the end of the process, the final Hamiltonian is made to have a ground-state which encodes the solution of the problem that requires solving.
The main question is how slowly do you need to change the Hamiltonian in order to satisfy the adiabatic theorem and have the system stay in the ground state. The algorithmic complexity of AC depends on the behaviour of the energy gap between the (non)degenerate ground state and the first excited state(s), as the time required to change from the initial to the final Hamiltonian in an adiabatic manner depends inversely on the minimum energy gap. Ideally, the time required to run the algorithm would only grow polynomially in the size of the problem to be solved.
This model was proved to be polynomially equivalent to the standard model [2].
References:
[1] Quantum Computation by Adiabatic Evolution, Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Michael Sipser, quant-ph/0001106
[2] Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation, Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev,quant-ph/0405098
 |
This article is a stub. You can help by |
