Adiabatic quantum computation (AQC) performs computation by slowly varying a local Hamiltonian whose ground state encodes the answer, but unlike the circuit model it has no threshold theorem: no proof that an adiabatic computer can carry out arbitrarily long computations reliably once noise and control imperfections are present. Lidar (2008) showed that a hybrid of dynamical decoupling, subsystem/stabilizer encoding, and energy-penalty gap protection makes the total AQC error arbitrarily small, but at the price of pulse intervals and widths that shrink as power laws in the problem size, with no correction of pulse imperfections and no threshold result. The open problem is to establish (or refute) an AQC analogue of the circuit-model threshold theorem: a protection architecture under which every polynomial-runtime adiabatic algorithm can be executed to arbitrarily small error with polynomial resource overhead, provided decoherence and control-error rates are below fixed constants. Partial results exist on each axis separately — encoded energy-penalty suppression of thermal errors, numerical dynamical decoupling, and threshold-type theorems for control errors in closed-system dynamics — but none combines decoherence, control noise, and polynomial overhead, so the problem remains open.

Background

Adiabatic quantum computation (AQC) solves a problem by preparing the ground state of a simple initial Hamiltonian H0H_0 and slowly interpolating to a final Hamiltonian H1H_1 whose ground state encodes the answer, via Had(s)=(1−f(s))H0+f(s)H1H_{\mathrm{ad}}(s)=(1-f(s))H_0+f(s)H_1 with s=t/T∈[0,1]s=t/T\in[0,1]. The adiabatic theorem guarantees that the evolution stays near the instantaneous ground state provided TT is large compared with the inverse square (or cube, depending on smoothness) of the minimum spectral gap Δ\Delta between the ground state and the rest of the spectrum. For universal AQC this gap shrinks as an inverse polynomial in the problem size nn, so the runtime TT grows polynomially. Aharonov, van Dam, Kempe, Landau, Lloyd, and Regev (2007) proved that AQC is polynomially equivalent to the standard circuit model, so AQC is in principle as powerful as gate-based quantum computing.

In the circuit model, fault-tolerance threshold theorems (beginning with Aharonov and Ben-Or, 1997) show that arbitrarily long quantum computations succeed with only polynomial overhead once physical error rates are below a fixed constant threshold, by combining error-correcting encodings with locality of faults. AQC lacks any analogous theorem. The difficulty is structural: computation is a continuous analog evolution, so there are no gates and no natural points at which to extract error syndromes; errors occur continuously during the interpolation; the energy gap that protects the computation shrinks polynomially with nn, so thermal excitation and noise must be compared with a vanishing energy scale; and the standard universality construction (history states plus perturbative gadgets, reductions of many-qubit interaction terms to two-qubit terms via ancillas and energy penalties) introduces unprotected ancillas, so compiling a fault-tolerant circuit into a Hamiltonian does not by itself yield a fault-tolerant analog device.

Lidar (2008) introduced a hybrid protection methodology for AQC combining: (a) dynamical decoupling (DD) — applying strong, fast control pulses whose net effect averages out the system-bath interaction; the pulses are chosen to commute with the adiabatic Hamiltonian so they do not disturb the computation; (b) encoding of the logical qubits into subsystem and stabilizer codes — encodings in which the noiseless information lives in a factor of the Hilbert space (the algebraic complement, or commutant, of the algebra generated by the decoupling group) that the bath-induced errors cannot reach; and (c) energy-penalty (gap) protection in the sense of Jordan, Farhi, and Shor (2006), where terms are added to raise the energy of states outside the code space. He proved a total error bound δS≤dD+δad\delta_S \le d_D + \delta_{\mathrm{ad}}, the sum of a decoupling error dDd_D and the closed-system adiabatic error δad\delta_{\mathrm{ad}}, and showed that periodic DD (PDD) with pulse interval τ\tau and width ww shrinking as power laws in nn (τ∼n−(ζ+ϵ1)/Δ0\tau \sim n^{-(\zeta+\epsilon_1)}/\Delta_0, w∼n−(2ζ+ϵ1+ϵ2)/Jw \sim n^{-(2\zeta+\epsilon_1+\epsilon_2)}/J, with Δ0\Delta_0 the Hamiltonian energy scale, JJ the system-bath coupling strength, and ζ\zeta set by the gap-scaling exponent) makes the total error arbitrarily small. However, the paper explicitly concludes that a threshold theorem for fault-tolerant AQC is still missing, that achieving one will most likely require incorporating feedback to correct DD pulse imperfections and other control noise (suggesting syndrome measurements on the commutant factor as in subsystem-code circuit fault tolerance), that the shrinking-pulse requirement is a shortcoming expected — but not proven — to be removable by concatenated DD (nesting of pulse sequences that suppresses low-frequency noise to higher perturbative order), that energy-penalty protection typically requires nn-local or more-than-two-body interactions that physical architectures cannot directly implement, and that noise acting on the interpolation function f(s)f(s) or introducing independent time scales is unaccounted for.

Problem Statement

Establish (or refute the possibility of) a fault-tolerance threshold theorem for adiabatic quantum computation, in the native analog Hamiltonian model, playing the role that circuit-model threshold theorems play for gate-based quantum computing. Specifically: exhibit a protection architecture for AQC — combining, for example, dynamical decoupling, subsystem or stabilizer encodings, energy-penalty gap protection, and possibly feedback or syndrome measurements on the commutant/subsystem factor — together with a proof that, under a specified class of local noise models for decoherence (system-bath coupling) together with a specified class of local control-error models (including dynamical-decoupling pulse imperfections such as finite pulse width and pulse-strength errors), every AQC algorithm whose runtime and minimum gap scale polynomially in the problem size nn can be executed with final error at most ϵ\epsilon using resources (qubits, pulses, energy scales, total time) polynomial in nn and 1/ϵ1/\epsilon, whenever the decoherence and control-error rates are below fixed positive constants. The stated models are the local (few-body) ones — decoherence as system-bath coupling and control errors as local perturbations of the Hamiltonian and of the dynamical-decoupling pulses, with nonvanishing coupling and error strengths — and the guarantee is to be established or refuted for the specified class as a whole rather than for a single instance selected to make it trivial. In accordance with the source, the known obstructions that a resolution is expected to confront include (these are context for the difficulty of the problem, not separate deliverables, and it is not necessary to address each of them independently; they bear chiefly on a constructive, affirmative resolution): (i) how active correction of DD pulse imperfections and other control noise (e.g., feedback and syndrome extraction compatible with the ongoing adiabatic evolution) is integrated; (ii) whether the requirement that pulse intervals and widths shrink as power laws in nn can be removed, e.g., by a rigorous demonstration that concatenated dynamical decoupling achieves the needed suppression with non-vanishing pulse scales in the AQC setting; (iii) whether gap protection can be implemented with physically feasible, locality-preserving (two-body or otherwise architecturally admissible) interactions rather than nn-local terms; and (iv) how noise acting on the interpolation function f(s)f(s) or introducing additional independent time scales is handled. A negative answer — a proof that for this class of local models no fixed positive constant exists below which such a guarantee with polynomial overhead holds for analog AQC (that is, that the threshold is zero) — would equally resolve the problem.

References

  1. Daniel A. Lidar, 'Towards Fault Tolerant Adiabatic Quantum Computation', Physical Review Letters 100, 160506 (2008), DOI: 10.1103/PhysRevLett.100.160506, arXiv:0707.0021, https://arxiv.org/abs/0707.0021
  2. Stephen P. Jordan, Edward Farhi, Peter W. Shor, 'Error-correcting codes for adiabatic quantum computation', Physical Review A 74, 052322 (2006), DOI: 10.1103/PhysRevA.74.052322, arXiv:quant-ph/0512170, https://arxiv.org/abs/quant-ph/0512170
  3. Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev, 'Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation', SIAM Journal on Computing 37, 166-194 (2007), DOI: 10.1137/S0097539705447323, arXiv:quant-ph/0405098, https://arxiv.org/abs/quant-ph/0405098
  4. Dorit Aharonov, Michael Ben-Or, 'Fault-tolerant quantum computation with constant error', Proceedings of the 29th annual ACM Symposium on Theory of Computing (STOC '97), 176 (1997), DOI: 10.1145/258533.258579
  5. Kevin C. Young, Mohan Sarovar, Robin Blume-Kohout, 'Error Suppression and Error Correction in Adiabatic Quantum Computation: Techniques and Challenges', Physical Review X 3, 041013 (2013), DOI: 10.1103/PhysRevX.3.041013, arXiv:1307.5893, https://arxiv.org/abs/1307.5893
  6. Mohan Sarovar, Kevin C. Young, 'Error suppression and error correction in adiabatic quantum computation: non-equilibrium dynamics', New Journal of Physics 15, 125032 (2013), DOI: 10.1088/1367-2630-15-12-125032, arXiv:1307.5892, https://arxiv.org/abs/1307.5892
  7. Gregory Quiroz, Daniel A. Lidar, 'High fidelity adiabatic quantum computation via dynamical decoupling', Physical Review A 86, 042333 (2012), DOI: 10.1103/PhysRevA.86.042333, arXiv:1205.2725, https://arxiv.org/abs/1205.2725
  8. Adam D. Bookatz, Edward Farhi, Leo Zhou, 'Error suppression in Hamiltonian based quantum computation using energy penalties', Physical Review A 92, 022317 (2015), DOI: 10.1103/PhysRevA.92.022317, arXiv:1407.1485, https://arxiv.org/abs/1407.1485
  9. Daniel A. Lidar, 'Arbitrary-time error suppression for Markovian adiabatic quantum computing using stabilizer subspace codes', Physical Review A 100, 022326 (2019), DOI: 10.1103/PhysRevA.100.022326, arXiv:1904.12028, https://arxiv.org/abs/1904.12028
  10. Kristen L. Pudenz, Tameem Albash, Daniel A. Lidar, 'Error-corrected quantum annealing with hundreds of qubits', Nature Communications 5, 3243 (2014), DOI: 10.1038/ncomms4243, arXiv:1307.8190, https://arxiv.org/abs/1307.8190
  11. Manaka Okuyama, Kentaro Ohki, Masayuki Ohzeki, 'Threshold theorem in isolated quantum dynamics with stochastic control errors', Philosophical Transactions of the Royal Society A 380, 20210412 (2022), DOI: 10.1098/rsta.2021.0412, arXiv:2009.11151, https://arxiv.org/abs/2009.11151
  12. Manaka Okuyama, Masayuki Ohzeki, 'Threshold theorem in quantum annealing with deterministic analog control errors', arXiv:2301.13075 (2023), https://arxiv.org/abs/2301.13075
  13. Tameem Albash, Daniel A. Lidar, 'Adiabatic Quantum Computing', Reviews of Modern Physics 90, 015002 (2018), DOI: 10.1103/RevModPhys.90.015002, arXiv:1611.04471, https://arxiv.org/abs/1611.04471
  14. R. Barends, A. Shabani, L. Lamata, J. Kelly, A. Mezzacapo, U. Las Heras, R. Babbush, A. G. Fowler, B. Campbell, Yu Chen, Z. Chen, B. Chiaro, A. Dunsworth, E. Jeffrey, E. Lucero, A. Megrant, J. Y. Mutus, M. Neeley, C. Neill, P. J. J. O'Malley, C. Quintana, P. Roushan, D. Sank, A. Vainsenker, J. Wenner, T. C. White, E. Solano, H. Neven, John M. Martinis, 'Digitized adiabatic quantum computing with a superconducting circuit', Nature 534, 222-226 (2016), DOI: 10.1038/nature17658, arXiv:1511.03316, https://arxiv.org/abs/1511.03316
  15. Naeimeh Mohseni, Marek Narozniak, Alexey N. Pyrkov, Valentin Ivannikov, Jonathan P. Dowling, Tim Byrnes, 'Error suppression in adiabatic quantum computing with qubit ensembles', npj Quantum Information 7, 53 (2021), DOI: 10.1038/s41534-021-00405-2, arXiv:1909.09947, https://arxiv.org/abs/1909.09947