Adiabatic quantum computation

Adiabatic quantum computation (AQC) is a form of quantum computing which relies on the adiabatic theorem to perform calculations^[1] and is closely related to quantum annealing.^[2][3][4][5]

Description

First, a (potentially complicated) 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 desired complicated 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. Adiabatic quantum computing has been shown to be polynomially equivalent to conventional quantum computing in the circuit model.^[6]

The time complexity for an adiabatic algorithm is the time taken to complete the adiabatic evolution which is dependent on the gap in the energy eigenvalues (spectral gap) of the Hamiltonian. Specifically, if the system is to be kept in the ground state, the energy gap between the ground state and the first excited state of ${\displaystyle H(t)}$  provides an upper bound on the rate at which the Hamiltonian can be evolved at time ${\displaystyle t}$ .^[7] When the spectral gap is small, the Hamiltonian has to be evolved slowly. The runtime for the entire algorithm can be bounded by:

${\displaystyle T=O\left({\frac {1}{g_{min}^{2}}}\right)}$ 

where ${\displaystyle g_{min}}$  is the minimum spectral gap for ${\displaystyle H(t)}$ .

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.^[8] QMA-hardness results are known for physically realistic lattice models of qubits such as^[9]

${\displaystyle H=\sum _{i}h_{i}Z_{i}+\sum _{i<j}J^{ij}Z_{i}Z_{j}+\sum _{i<j}K^{ij}X_{i}X_{j}}$ 

where ${\displaystyle Z,X}$  represent the Pauli matrices ${\displaystyle \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^[10] or a line of quantum particles with 12 states per particle.^[11] If such models were found to be physically realizable, 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 behavior 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.

Adiabatic quantum computation in satisfiability problems

Adiabatic quantum computation solves satisfiability problems and other combinatorial search problems. Specifically, these kind of problems seek a state that satisfies ${\displaystyle C_{1}\wedge C_{2}\wedge \cdots \wedge C_{M}}$ . This expression contains the satisfiability of M clauses, for which clause ${\displaystyle C_{i}}$  has the value True or False, and can involve n bits. Each bit is a variable ${\displaystyle x_{j}\in \{0,1\}}$  such that ${\displaystyle C_{i}}$  is a Boolean value function of ${\displaystyle x_{1},x_{2},\dots ,x_{n}}$ . QAA solves this kind of problem using quantum adiabatic evolution. It starts with an Initial Hamiltonian ${\displaystyle H_{B}}$ :

${\displaystyle H_{B}=H_{B_{1}}+H_{B_{2}}+\dots +H_{B_{M}}}$ 

where ${\displaystyle H_{B_{i}}}$  shows the Hamiltonian corresponding to the clause ${\displaystyle C_{i}}$ . Usually, the choice of ${\displaystyle H_{B_{i}}}$  won't depend on different clauses, so only the total number of times each bit is involved in all clauses matters. Next, it goes through an adiabatic evolution, ending in the Problem Hamiltonian ${\displaystyle H_{P}}$ :

${\displaystyle H_{P}=\sum \limits _{C}^{}H_{P,C}}$ 

where ${\displaystyle H_{P,C}}$  is the satisfying Hamiltonian of clause C.

It has eigenvalues:

${\displaystyle h_{C}(z_{1C},z_{2C}\dots z_{nC})={\begin{cases}0&{\mbox{clause }}C{\mbox{ satisfied}}\\1&{\mbox{clause }}C{\mbox{ violated}}\end{cases}}}$ 

For a simple path of adiabatic evolution with run time T, consider:

${\displaystyle H(t)=(1-t/T)H_{B}+(t/T)H_{P}}$ 

and let ${\displaystyle s=t/T}$ . This results in:

${\displaystyle {\tilde {H}}(s)=(1-s)H_{B}+sH_{P}}$ , which is the adiabatic evolution Hamiltonian of the algorithm.

In accordance with the adiabatic theorem, start from the ground state of Hamiltonian ${\displaystyle H_{B}}$  at the beginning, proceed through an adiabatic process, and end in the ground state of problem Hamiltonian ${\displaystyle H_{P}}$ .

Then measure the z-component of each of the n spins in the final state. This will produce a string ${\displaystyle z_{1},z_{2},\dots ,z_{n}}$  which is highly likely to be the result of the satisfiability problem. The run time T must be sufficiently long to assure correctness of the result. According to the adiabatic theorem, T is about ${\displaystyle \varepsilon /g_{\mathrm {min} }^{2}}$ , where ${\displaystyle g_{\mathrm {min} }=\min _{0\leq s\leq 1}(E_{1}(s)-E_{0}(s))}$  is the minimum energy gap between ground state and first excited state.^[12]

Comparison to gate-based quantum computing

Adiabatic quantum computing is equivalent in power to standard gate-based quantum computing that implements arbitrary unitary operations. However, the mapping challenge on gate-based quantum devices differs substantially from quantum annealers as logical variables are mapped only to single qubits and not to chains.^[13]

D-Wave quantum processors

The D-Wave One is a device made by Canadian company D-Wave Systems, which claims that it uses quantum annealing to solve optimization problems.^[14][15] On 25 May 2011, Lockheed-Martin purchased a D-Wave One for about US$10 million.^[15] In May 2013, Google purchased a 512 qubit D-Wave Two.^[16]

The question of whether the D-Wave processors offer a speedup over a classical processor is still unanswered. Tests performed by researchers at Quantum Artificial Intelligence Lab (NASA), USC, ETH Zurich, and Google show that as of 2015, there is no evidence of a quantum advantage.^[17][18][19]

Notes

1. Farhi, E.; Goldstone, Jeffrey; Gutmann, S.; Sipser, M. (2000). "Quantum Computation by Adiabatic Evolution". arXiv:quant-ph/0001106v1.
2. Kadowaki, T.; Nishimori, H. (November 1, 1998). "Quantum annealing in the transverse Ising model". Physical Review E. 58 (5): 5355. arXiv:cond-mat/9804280. Bibcode:1998PhRvE..58.5355K. doi:10.1103/PhysRevE.58.5355. S2CID 36114913.
3. Finilla, A. B.; Gomez, M. A.; Sebenik, C.; Doll, D. J. (March 18, 1994). "Quantum annealing: A new method for minimizing multidimensional functions". Chemical Physics Letters. 219 (5): 343–348. arXiv:chem-ph/9404003. Bibcode:1994CPL...219..343F. doi:10.1016/0009-2614(94)00117-0. S2CID 97302385.
4. Santoro, G. E.; Tosatti, E. (September 8, 2006). "Optimization using quantum mechanics: quantum annealing through adiabatic evolution". Journal of Physics A. 39 (36): R393. Bibcode:2006JPhA...39R.393S. doi:10.1088/0305-4470/39/36/R01. S2CID 116931586.
5. Das, A.; Chakrabarti, B. K. (September 5, 2008). "Colloquium: Quantum annealing and analog quantum computation". Reviews of Modern Physics. 80 (3): 1061. arXiv:0801.2193. Bibcode:2008RvMP...80.1061D. doi:10.1103/RevModPhys.80.1061. S2CID 14255125.
6. Aharonov, Dorit; van Dam, Wim; Kempe, Julia; Landau, Zeph; LLoyd, Seth (April 1, 2007). "Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation". SIAM Journal on Computing. 37: 166. arXiv:quant-ph/0405098. doi:10.1137/s0097539705447323.
7. van Dam, Wim; van Mosca, Michele; Vazirani, Umesh. "How Powerful is Adiabatic Quantum Computation?". Proceedings of the 42nd Annual Symposium on Foundations of Computer Science: 279.
8. Kempe, J.; Kitaev, A.; Regev, O. (July 27, 2006). "The Complexity of the Local Hamiltonian Problem". SIAM Journal on Computing. 35 (5): 1070–1097. arXiv:quant-ph/0406180v2. doi:10.1137/S0097539704445226. ISSN 1095-7111.
9. Biamonte, J. D.; Love, P. J. (July 28, 2008). "Realizable Hamiltonians for Universal Adiabatic Quantum Computers". Physical Review A. 78 (1): 012352. arXiv:0704.1287. Bibcode:2008PhRvA..78a2352B. doi:10.1103/PhysRevA.78.012352. S2CID 9859204.
10. Oliveira, R.; Terhal, B. M. (November 1, 2008). "The complexity of quantum spin systems on a two-dimensional square lattice". Quantum Information & Computation. 8 (10): 0900–0924. arXiv:quant-ph/0504050. Bibcode:2005quant.ph..4050O. doi:10.26421/QIC8.10-2. S2CID 3262293.
11. Aharonov, D.; Gottesman, D.; Irani, S.; Kempe, J. (April 1, 2009). "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. S2CID 1916001.
12. Farhi, Edward; Goldstone, Jeffrey; Gutmann, Sam; Sipser, Michael (January 28, 2000). "Quantum Computation by Adiabatic Evolution". arXiv:quant-ph/0001106.
13. Zbinden, Stefanie (June 15, 2020). "Embedding Algorithms for Quantum Annealers with Chimera and Pegasus Connection Topologies". High Performance Computing. Lecture Notes in Computer Science. Vol. 12151. pp. 187–206. doi:10.1007/978-3-030-50743-5_10. ISBN 978-3-030-50742-8.
14. Johnson, M.; Amin, M. (May 11, 2011). "Quantum annealing with manufactured spins". Nature. 473 (7346): 194–198. Bibcode:2011Natur.473..194J. doi:10.1038/nature10012. PMID 21562559. S2CID 205224761. Retrieved February 12, 2021. Some of the authors are employees of D-Wave Systems Inc.
15. Campbell, Macgregor (June 1, 2011). "Quantum computer sold to high-profile client". New Scientist. Retrieved February 12, 2021.
16. Jones, Nicola (June 20, 2013). "Computing: The quantum company". Nature. 498 (7454): 286–288. Bibcode:2013Natur.498..286J. doi:10.1038/498286a. PMID 23783610.
17. Boixo, S.; Rønnow, T. F.; Isakov, S. V.; Wang, Z.; Wecker, D.; Lidar, D. A.; Martinis, J. M.; Troyer, M. (February 28, 2014). "Evidence for quantum annealing with more than one hundred qubits". Nature Physics. 10 (3): 218–224. arXiv:1304.4595. Bibcode:2014NatPh..10..218B. doi:10.1038/nphys2900. S2CID 8031023.
18. Ronnow, T. F.; Wang, Z.; Job, J.; Boixo, S.; Isakov, S. V.; Wecker, D.; Martinis, J. M.; Lidar, D. A.; Troyer, M. (July 25, 2014). "Defining and detecting quantum speedup". Science. 345 (6195): 420–424. arXiv:1401.2910. Bibcode:2014Sci...345..420R. doi:10.1126/science.1252319. PMID 25061205. S2CID 5596838.
19. Venturelli, D.; Mandrà, S.; Knysh, S.; O'Gorman, B.; Biswas, R.; Smelyanskiy, V. (September 18, 2015). "Quantum Optimization of Fully Connected Spin Glasses". Physical Review X. 5 (3): 031040. arXiv:1406.7553. Bibcode:2015PhRvX...5c1040V. doi:10.1103/PhysRevX.5.031040. S2CID 118622447.