Adiabatic quantum computation (AQC) relies on the adiabatic theorem to do calculations[1] and is closely related to quantum annealing.[2][3][4][5] First, a complex Hamiltonian is found whose ground state describes the solution to the problem of interest. Next, a system with a simple Hamiltonian is prepared and initialized to the ground state. Finally, the simple Hamiltonian is adiabatically evolved to the complex Hamiltonian. By the adiabatic theorem, the system remains in the ground state, so at the end the state of the system describes the solution to the problem.

AQC is a possible method to get around the problem of energy relaxation. Since the quantum system is in the ground state, interference with the outside world cannot make it move to a lower state. If the energy of the outside world (that is, the "temperature of the bath") is kept lower than the energy gap between the ground state and the next higher energy state, the system has a proportionally lower probability of going to a higher energy state. Thus the system can stay in a single system eigenstate as long as needed.

Universality results in the adiabatic model are tied to quantum complexity and QMA-hard problems. The k-local Hamiltonian is QMA-complete for k ≥ 2.[6] QMA-hardness results are known for physically realistic lattice models of qubits such as [7] $H = \sum_{i}h_i Z_i + \sum_{i where $Z, X$ represent the Pauli matrices $\sigma_z, \sigma_x$. Such models are used for universal adiabatic quantum computation. The Hamiltonians for the QMA-complete problem can also be restricted to act on a two dimensional grid of qubits[8] or a line of quantum particles with 12 states per particle.[9] and if such models were found to be physically realisable, they too could be used to form the building blocks of a universal adiabatic quantum computer.

In practice, there are problems during a computation. As the Hamiltonian is gradually changed, the interesting parts (quantum behaviour as opposed to classical) occur when multiple qubits are close to a tipping point. It is exactly at this point when the ground state (one set of qubit orientations) gets very close to a first energy state (a different arrangement of orientations). Adding a slight amount of energy (from the external bath, or as a result of slowly changing the Hamiltonian) could take the system out of the ground state, and ruin the calculation. Trying to perform the calculation more quickly increases the external energy; scaling the number of qubits makes the energy gap at the tipping points smaller.

For a theoretical study of the performance of an adiabatic optimization processor see.[10]

## D-Wave quantum processors

The D-Wave One is an adiabatic quantum annealer made by a Canadian company D-Wave Systems. In 2011, Lockheed-Martin purchased one for about US\$10 million; in May 2013, Google purchased a D-Wave Two with 512 qubits.[11] As of now, the question of whether the D-Wave processors offer a speedup over a classical processor is still unanswered. Tests performed by researchers at USC, ETH Zurich, and Google show that as of now, there is no evidence of a quantum advantage.[12][13]

## Notes

1. ^ Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Michael Sipser (2000). "Quantum Computation by Adiabatic Evolution". arXiv:quant-ph/0001106v1.
2. ^ T. Kadowaki and H. Nishimori, "Quantum annealing in the transverse Ising model" Phys. Rev. E 58, 5355 (1998)
3. ^ A. B. Finilla, M. A. Gomez, C. Sebenik and D. J. Doll, "Quantum annealing: A new method for minimizing multidimensional functions" Chem. Phys. Lett. 219, 343 (1994)
4. ^ G. E. Santoro and E. Tosatti, "Optimization using quantum mechanics: quantum annealing through adiabatic evolution" J. Phys. A 39, R393 (2006)
5. ^ A. Das and B. K. Chakrabarti, "Colloquium: Quantum annealing and analog quantum computation" Rev. Mod. Phys. 80, 1061 (2008)
6. ^ Kempe, Julia; Kitaev, Alexei; Regev, Oded (2006). "The Complexity of the Local Hamiltonian Problem". SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics) 35 (5): 1070–1097. arXiv:quant-ph/0406180v2. doi:10.1137/S0097539704445226. ISSN 1095-7111..
7. ^ Biamonte, Jacob; Love, Peter (2008). "Realizable Hamiltonians for Universal Adiabatic Quantum Computers". Phys. Rev. A (Physical Review) 78 (1): 012352. arXiv:arXiv:0704.1287. Bibcode:2008PhRvA..78a2352B. doi:10.1103/PhysRevA.78.012352..
8. ^ Oliveira, Roberto; Barbara M Terhal (2008). "The complexity of quantum spin systems on a two-dimensional square lattice". arXiv:quant-ph/0504050 [quant-ph].
9. ^ Aharonov, Dorit; Daniel Gottesman; Sandy Irani; Julia Kempe (2009-04-01). "The Power of Quantum Systems on a Line". Communications in Mathematical Physics 287 (1): 41–65. arXiv:0705.4077. Bibcode:2009CMaPh.287...41A. doi:10.1007/s00220-008-0710-3.
10. ^ Kamran Karimi, Neil .G. Dickson, Firas Hamze, et al., Investigating the Performance of an Adiabatic Quantum Optimization Processor, Quantum Information Processing, Volume 11, Number 1, 2012, http://arxiv.org/abs/1006.4147
11. ^ Jones, Nicola (19 June 2013). "Computing: The quantum company". Nature. Nature Publishing Group. pp. 286–288. Retrieved 2 January 2014.
12. ^ Boixo et al. (April 2013). Quantum annealing with more than one hundred qubits.
13. ^ Ronnow et al. (January 2014). Defining and detecting quantum speedup.