Skip to content

Quantum adiabatic algorithm

Rough overview (in words)

The quantum adiabatic algorithm (QAA) [1], sometimes referred to as adiabatic state preparation, is a continuous-time procedure for (approximately) preparing an eigenstate (typically the ground state) of a particular Hamiltonian of interest on a quantum device. The QAA also forms the basis for a model of quantum computation called adiabatic quantum computation which acts as an alternative to the standard quantum circuit model.

The main idea of the QAA is to begin in an eigenstate of a simpler Hamiltonian that is easy to prepare, and then slowly change the Hamiltonian to be equal to the more complex Hamiltonian of interest. The adiabatic theorem (see [2] and references therein), a celebrated concept from physics, dictates that if the evolution is sufficiently slow, the system will evolve to (approximately) remain in the instantaneous eigenstate of the continuously varying Hamiltonian and thus finish in the desired state. The length of time required for the evolution to succeed depends on the spectral properties of the Hamiltonian path and in particular on the minimum spectral gap. The adiabatic algorithm can be simulated on a gate-based quantum computer with time-dependent Hamiltonian simulation.

Rough overview (in math)

Let \(H(s)\), where \(s\) varies as \(0 \leq s \leq 1\), denote a single-parameter path through the space of Hamiltonians, and let \(\ket{\phi_j(s)}\) and \(E_j(s)\) denote the eigenstates and eigenvalues of \(H(s)\), indexed by \(j\) in increasing order. The goal of the QAA is to prepare a certain eigenstate \(\ket{\phi_j(1)}\) of \(H(1)\). Let \(\ket{\psi(t)}\) denote the state of our system at time \(t\) and let \(T\) be the total evolution time. The procedure calls for beginning in the state \(\ket{\psi(0)} = \ket{\phi_j(0)}\) and allowing \(\ket{\psi(t)}\) to evolve by the Schrödinger equation according to the Hamiltonian \(H(t/T)\), that is \(i\frac{d}{dt}\ket{\psi(t)} = H(t/T)\ket{\psi(t)}\) from \(t=0\) to \(t=T\). Thus, as \(T\) is made larger, the path from \(H(0)\) to \(H(1)\) is traversed increasingly slowly.

Dominant resource cost (gates/qubits)

The main resource for the continuous-time QAA is the total evolution time \(T\). The adiabatic theorem suggests that if \(T\) is chosen sufficiently large, and as long as eigenvalue \(E_j\) is nondegenerate along the entire path, then \(\ket{\psi(T)} \approx \ket{\phi_j(1)}\) will hold. The often-quoted heuristic condition [2] for success is that

\[\begin{equation} \label{eq:adiabatic_condition} T \gg \max_{0 \leq s \leq 1} \frac{\left\lVert \frac{dH}{ds}\right\rVert}{\Delta(s)^2} \end{equation}\]

where \(\Delta(s)\) is the spectral gap, i.e. \(\min_{i}|E_i(s)-E_j(s)|\), and \(\lVert \cdot \rVert\) denotes the spectral norm. Thus, the runtime needed for the QAA to have small error is primarily governed by the minimum size of the spectral gap along the adiabatic path. This aspect of the QAA is a common sticking point as it is often difficult to produce lower bounds on \(\Delta(s)\) that would suffice for proving upper bounds on \(T\). In practice, the value of \(T\) can be chosen heuristically, or by trial-and-error, but a more detailed understanding of \(\Delta(s)\) would inform smarter choices of Hamiltonian path \(H(s)\).

The QAA is typically formulated as a continuous-time procedure, but a gate-based quantum computer can simulate the QAA by discretizing the path and approximately implementing the evolution from time \(t\) to \(t+ \delta t\) with product formulae or with more advanced techniques for time-dependent Hamiltonian simulation. This incurs error in addition to the adiabatic error of the continuous-time QAA. The number of gates needed to do this can be made proportional to \(T\) (up to logarithmic corrections), polynomial in the number of qubits needed to hold the state \(\ket{\psi(t)}\), and logarithmic in the approximation error incurred (e.g., [3]).

Caveats

A technical caveat of the QAA is that rigorous formulations of sufficient conditions for success (e.g., [4, 5]) are more complex than Eq. \(\eqref{eq:adiabatic_condition}\) and likely looser than what is necessary in practice. Also, in most cases, the dependence of the runtime \(T\) on the final approximation error \(\epsilon = \lVert \ket{\psi(T)}-\ket{\phi_j(1)}\rVert\) goes as \(T = \mathrm{poly}(1/\epsilon)\), rather than \(T = \mathrm{polylog}(1/\epsilon)\). To circumvent this and achieve \(\mathrm{polylog}(1/\epsilon)\) dependence, one can choose more sophisticated Hamiltonian paths \(H(s)\) for which all time derivatives vanish at \(s=0\) and \(s=1\) [6, 2].

A practical caveat of the QAA is that the spectral gap—the main determiner of the resource cost for the QAA—is difficult to study theoretically. Numerically, it can often be computed only for small system sizes, and it is unclear whether extrapolations to larger system sizes would be accurate.

NISQ implementations

The QAA is closely related to the concept of quantum annealing [7], a term used especially in the context of near-term implementations on existing quantum hardware. In quantum annealing, the system is exposed to a time-dependent Hamiltonian, typically a transverse-field Ising model. The strength of the transverse field is slowly reduced, eventually to zero, where the Hamiltonian is equal to a classical Ising model encoding a hard combinatorial optimization problem. If implemented perfectly and sufficiently slowly, this would be a manifestation of the QAA, and one would obtain the solution to the problem. However, the typical setting of quantum annealing is to consider faster implementations, and to possibly allow for some amount of control noise and finite-temperature effects (rather than evolving under a closed system at zero temperature), which induce transitions from the ground state to excited states. The goal is relaxed from ending in the exact ground state of the final Hamiltonian to ending in a low-energy state that can be considered an approximately optimal solution to the problem. The success metric is often the quality of the solution produced rather than the runtime required to find the best solution. As such, it is a heuristic algorithm and must be compared with classical heuristic algorithms, where evidence of a scalable advantage is mixed. See, e.g., [8] for a perspective on quantum annealing and the most promising related directions.

Separately, the QAA can be related to variational quantum algorithms, which are NISQ friendly. In particular, by applying product formulae to the QAA, one obtains alternating time evolutions by \(H(0)\) and by \(H(1)\); in the case that \(H(0)\) is a transverse field and \(H(1)\) is a classical cost function, this is precisely an instance of the Quantum Approximate Optimization Algorithm (QAOA) [9], a leading NISQ algorithm. In the limit of large depth, the QAOA can fully simulate the QAA to arbitrarily small precision. However, in a NISQ setting, the depth of the QAOA would need to be restricted, and the QAOA would not exactly follow the QAA.

Example use cases

  • Combinatorial optimization: The QAA was first invented [1] as a way to solve hard classical combinatorial optimization problems on a quantum computer. An example is constraint satisfaction problems, where one is given a Hamiltonian \(H(1)\) that is diagonal in the computational basis (i.e. "classical") and equal to the sum of various constraints on \(n\) bits. The ground state of \(H(1)\) is the bit string that violates the fewest constraints. One typically chooses the initial Hamiltonian to be \(H(0) = -\sum_{i=1}^n X_i\), where \(X_i\) denotes the Pauli-\(X\) operator on qubit \(i\), whose ground state is an easy-to-prepare product state. The QAA is guaranteed to find the ground state of \(H(1)\) if it is run with sufficiently large evolution time. However, in general it is expected that the spectral gaps along the adiabatic path become exponentially small in \(n\) [10, 11, 12, 13, 14], indicating that the QAA requires exponentially long runtime.
  • Quantum chemistry and condensed matter physics: A central problem of quantum chemistry and computational condensed matter physics is the problem of finding the ground state energy of a molecule, material, or lattice model. This can be solved efficiently with quantum phase estimation so long as one can prepare a state that has substantial overlap with the ground state of the Hamiltonian. Adiabatic state preparation has been proposed as a method for producing such a state (see, e.g., [15, 16, 17, 18, 19, 20, 21]). This initial state preparation is often the bottleneck in the end-to-end quantum solution, as it can require exponential time for systems of interest (see, e.g., [22]).
  • Quantum linear systems solvers: the state-of-the-art quantum linear systems solvers [23] leverage the QAA to produce a quantum state \(\ket{x}\) corresponding to the solution of a linear system \(Ax = b\) (see also [24, 25, 26, 27]). In particular, this method allows the runtime to scale linearly in the condition number of the matrix \(A\).

Further reading

  • See [2] for a comprehensive 2018 review of the QAA and adiabatic quantum computation more generally.
  • See [28] for a digital version of the QAA for a gate-based quantum computer, but distinct from a direct simulation of the QAA. The idea is to choose a sequence of \(s\) values \(0 = s_0 < s_1 < s_2 < \ldots < s_T = 1\) and perform measurements of \(H(s_t)\) for \(t=0, \ldots, T\) in sequence using quantum phase estimation (QPE). As long as the difference between consecutive values of \(s\) is sufficiently small, the quantum Zeno effect guarantees that each measurement will project onto the correct eigenstate \(\ket{\phi_j(s_t)}\) with high probability (see also [29]). One can also take larger jumps, and amplify their success probability with fixed-point amplitude amplification. The resource cost has a similar dependence on the spectral gap as the continuous-time QAA: if the "path length" traced by the eigenstate \(\ket{\phi_j(s)}\) is \(L\), the minimum gap is \(\Delta\), and the target error is \(\epsilon\), then the gate cost of the algorithm is \(\mathcal{O}\left( L\log(L/\epsilon)/\Delta \right)\). The path length \(L\) can be upper bounded by \(\lVert dH/ds \rVert/\Delta\), which roughly recovers Eq. \(\eqref{eq:adiabatic_condition}\).
  • Along these lines, [30] gives an alternative way to effect adiabatic state preparation on a gate-based computer with \(\mathrm{polylog}(1/\epsilon)\) overall error dependence, via quasi-adiabatic continuation.

Bibliography

  1. Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Quantum computation by adiabatic evolution. arXiv: https://arxiv.org/abs/quant-ph/0001106, 2000.

  2. Tameem Albash and Daniel A. Lidar. Adiabatic quantum computation. Reviews of Modern Physics, 90:015002, 1 2018. arXiv: https://arxiv.org/abs/1611.04471. doi:10.1103/RevModPhys.90.015002.

  3. Mária Kieferová, Artur Scherer, and Dominic W. Berry. Simulating the dynamics of time-dependent hamiltonians with a truncated dyson series. Physical Review A, 99:042314, 4 2019. arXiv: https://arxiv.org/abs/1805.00582. URL: https://link.aps.org/doi/10.1103/PhysRevA.99.042314, doi:10.1103/PhysRevA.99.042314.

  4. Sabine Jansen, Mary-Beth Ruskai, and Ruedi Seiler. Bounds for the adiabatic approximation with applications to quantum computation. Journal of Mathematical Physics, 48(10):102111, 2007. arXiv: https://arxiv.org/abs/quant-ph/0603175. doi:10.1063/1.2798382.

  5. Alexander Elgart and George A. Hagedorn. A note on the switching adiabatic theorem. Journal of Mathematical Physics, 53(10):102202, 2012. arXiv: https://arxiv.org/abs/1204.2318. doi:10.1063/1.4748968.

  6. Yimin Ge, András Molnár, and J. Ignacio Cirac. Rapid adiabatic preparation of injective projected entangled pair states and gibbs states. Physical Review Letters, 116:080503, 2 2016. arXiv: https://arxiv.org/abs/1508.00570. doi:10.1103/PhysRevLett.116.080503.

  7. Tadashi Kadowaki and Hidetoshi Nishimori. Quantum annealing in the transverse ising model. Physical Review E, 58:5355–5363, 11 1998. arXiv: https://arxiv.org/abs/cond-mat/9804280. URL: https://link.aps.org/doi/10.1103/PhysRevE.58.5355, doi:10.1103/PhysRevE.58.5355.

  8. EJ Crosson and DA Lidar. Prospects for quantum enhancement with diabatic quantum annealing. Nature Reviews Physics, 3(7):466–489, 2021. arXiv: https://arxiv.org/abs/2008.09913. doi:10.1038/s42254-021-00313-6.

  9. Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv: https://arxiv.org/abs/1411.4028, 2014.

  10. Sergey Knysh and Vadim Smelyanskiy. On the relevance of avoided crossings away from quantum critical point to the complexity of quantum adiabatic algorithm. arXiv: https://arxiv.org/abs/1005.3011, 2010. doi:10.48550/arXiv.1005.3011.

  11. A. P. Young, S. Knysh, and V. N. Smelyanskiy. First-order phase transition in the quantum adiabatic algorithm. Physical Review Letters, 104:020502, 1 2010. arXiv: https://arxiv.org/abs/0910.1378. URL: https://link.aps.org/doi/10.1103/PhysRevLett.104.020502, doi:10.1103/PhysRevLett.104.020502.

  12. Itay Hen and A. P. Young. Exponential complexity of the quantum adiabatic algorithm for certain satisfiability problems. Physical Review E, 84:061152, 2011. arXiv: https://arxiv.org/abs/1109.6872. URL: https://link.aps.org/doi/10.1103/PhysRevE.84.061152, doi:10.1103/PhysRevE.84.061152.

  13. Boris Altshuler, Hari Krovi, and Jérémie Roland. Anderson localization makes adiabatic quantum optimization fail. Proceedings of the National Academy of Sciences, 107:12446–12450, 2010. arXiv: https://arxiv.org/abs/0912.0746. doi:10.1073/pnas.1002116107.

  14. Dave Wecker, Matthew B. Hastings, and Matthias Troyer. Training a quantum optimizer. Physical Review A, 94:022309, 2016. arXiv: https://arxiv.org/abs/1605.05370. doi:10.1103/PhysRevA.94.022309.

  15. L.-A. Wu, M. S. Byrd, and D. A. Lidar. Polynomial-time simulation of pairing models on a quantum computer. Physical Review Letters, 89:057904, 7 2002. arXiv: https://arxiv.org/abs/quant-ph/0108110. URL: https://link.aps.org/doi/10.1103/PhysRevLett.89.057904, doi:10.1103/PhysRevLett.89.057904.

  16. Markus Reiher, Nathan Wiebe, Krysta M. Svore, Dave Wecker, and Matthias Troyer. Elucidating reaction mechanisms on quantum computers. Proceedings of the National Academy of Sciences, 114(29):7555–7560, 2017. arXiv: https://arxiv.org/abs/1605.03590. URL: https://www.pnas.org/doi/abs/10.1073/pnas.1619152114, arXiv:https://www.pnas.org/doi/pdf/10.1073/pnas.1619152114, doi:10.1073/pnas.1619152114.

  17. Libor Veis and Jiří Pittner. Adiabatic state preparation study of methylene. The Journal of Chemical Physics, 140(21):214111, 2014. arXiv: https://arxiv.org/abs/1401.3186.pdf. URL: https://doi.org/10.1063/1.4880755, arXiv:https://doi.org/10.1063/1.4880755, doi:10.1063/1.4880755.

  18. Vladimir Kremenetski, Carlos Mejuto-Zaera, Stephen J. Cotton, and Norm M. Tubman. Simulation of adiabatic quantum computing for molecular ground states. The Journal of Chemical Physics, 155(23):234106, 2021. arXiv: https://arxiv.org/abs/2103.12059. URL: https://doi.org/10.1063/5.0060124, arXiv:https://doi.org/10.1063/5.0060124, doi:10.1063/5.0060124.

  19. Kenji Sugisaki, Kazuo Toyota, Kazunobu Sato, Daisuke Shiomi, and Takeji Takui. Adiabatic state preparation of correlated wave functions with nonlinear scheduling functions and broken-symmetry wave functions. Communications Chemistry, 5(1):84, 7 2022. URL: https://doi.org/10.1038/s42004-022-00701-8, doi:10.1038/s42004-022-00701-8.

  20. Dave Wecker, Matthew B. Hastings, Nathan Wiebe, Bryan K. Clark, Chetan Nayak, and Matthias Troyer. Solving strongly correlated electron models on a quantum computer. Physical Review A, 92:062318, 12 2015. arXiv: https://arxiv.org/abs/1506.05135. URL: https://link.aps.org/doi/10.1103/PhysRevA.92.062318, doi:10.1103/PhysRevA.92.062318.

  21. Hongye Yu, Deyu Lu, Qin Wu, and Tzu-Chieh Wei. Geometric quantum adiabatic methods for quantum chemistry. Physical Review Research, 4:033045, 7 2022. arXiv: https://arxiv.org/abs/2112.15186. URL: https://link.aps.org/doi/10.1103/PhysRevResearch.4.033045, doi:10.1103/PhysRevResearch.4.033045.

  22. Seunghoon Lee, Joonho Lee, Huanchen Zhai, Yu Tong, Alexander M. Dalzell, Ashutosh Kumar, Phillip Helms, Johnnie Gray, Zhi-Hao Cui, Wenyuan Liu, Michael Kastoryano, Ryan Babbush, John Preskill, David R. Reichman, Earl T. Campbell, Edward F. Valeev, Lin Lin, and Garnet Kin-Lic Chan. Evaluating the evidence for exponential quantum advantage in ground-state quantum chemistry. Nature Communications, 14(1):1952, 2023. arXiv: https://arxiv.org/abs/2208.02199. URL: https://doi.org/10.1038/s41467-023-37587-6, doi:10.1038/s41467-023-37587-6.

  23. Pedro C.S. Costa, Dong An, Yuval R. Sanders, Yuan Su, Ryan Babbush, and Dominic W. Berry. Optimal scaling quantum linear-systems solver via discrete adiabatic theorem. PRX Quantum, 3:040303, 10 2022. arXiv: https://arxiv.org/abs/2111.08152. URL: https://link.aps.org/doi/10.1103/PRXQuantum.3.040303, doi:10.1103/PRXQuantum.3.040303.

  24. Yiğit Subaşı, Rolando D. Somma, and Davide Orsucci. Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing. Physical Review Letters, 122(6):060504, 2019. arXiv: https://arxiv.org/abs/1805.10549. doi:10.1103/PhysRevLett.122.060504.

  25. Dong An and Lin Lin. Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm. ACM Transactions on Quantum Computing, 2022. arXiv: https://arxiv.org/abs/1909.05500. doi:10.1145/3498331.

  26. Lin Lin and Yu Tong. Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems. Quantum, 4:361, 2020. arXiv: https://arxiv.org/abs/1910.14596. doi:10.22331/q-2020-11-11-361.

  27. David Jennings, Matteo Lostaglio, Sam Pallister, Andrew T. Sornborger, and Yigit Subasi. Efficient quantum linear solver algorithm with detailed running costs. arXiv: https://arxiv.org/abs/2305.11352, 2023.

  28. Sergio Boixo, Emanuel Knill, and Rolando D Somma. Fast quantum algorithms for traversing paths of eigenstates. arXiv: https://arxiv.org/abs/1005.3034, 2010.

  29. Rolando Somma, Sergio Boixo, and Howard Barnum. Quantum simulated annealing. arXiv: https://arxiv.org/abs/0712.1008, 2007.

  30. Kianna Wan and Isaac Kim. Fast digital methods for adiabatic state preparation. arXiv: https://arxiv.org/abs/2004.04164, 2020.