Scalable robustness and asymptotic performance of adiabatic quantum computation: minimum-gap scaling, large-n noise resilience, and interpolation-path design

Adiabatic quantum computation (AQC) solves optimization problems by slowly interpolating a Hamiltonian from an easily prepared initial state to a problem Hamiltonian whose ground state encodes the solution; its efficiency and its fault tolerance are both governed by the minimum spectral gap between the ground and first excited states. Childs, Farhi, and Preskill [Phys. Rev. A 65, 012322 (2002)] gave numerical evidence at very small sizes (decoherence simulations at four qubits, control-error simulations up to ten qubits) that this model is intrinsically robust against decoherence and random unitary control errors, and posed the follow-up agenda that this problem records: (i) whether the adiabatic algorithm provides a definite asymptotic quantum speedup over the best classical algorithms, which reduces to how the minimum gap scales with problem size for hard instance distributions; (ii) whether the observed robustness persists, weakens, or fails at large system sizes and for instances with exponentially small gaps, including how control-error magnitudes must scale (e.g., whether random single-qubit errors must decay like 1/n to avoid exponentially degrading the ground state); (iii) how to model environmental couplings and control errors realistically, beyond a weak-coupling Markovian master equation and uncorrelated single-qubit perturbations; and (iv) how to systematically choose or optimize the interpolating Hamiltonian and path to enlarge the gap and reduce runtime. Twenty-five years of subsequent work has clarified but not closed any of these strands: worst-case instances provably defeat the algorithm, AQC was proven universal, engineered error correction and hybrid protection schemes were constructed, and the correct adiabatic master equation was derived, yet no problem class is known for which the adiabatic algorithm provably beats the best classical algorithm asymptotically, no general noise-threshold theorem exists for unprotected AQC at large n under realistic noise, and no constructive theory of gap-enlarging paths is available.

Background

Quantum computation by adiabatic evolution was introduced by Farhi, Goldstone, Gutmann, and Sipser as a framework for combinatorial search. One encodes the solution of an n-bit optimization problem (for example, an instance of satisfiability) as the ground state of a diagonal problem Hamiltonian $H_P=\sum_z h(z)|z\rangle\langle z|$, where $h(z)$ is the cost of bit string $z$; prepares the easily constructed ground state of an initial Hamiltonian $H_B$ (typically a transverse-field driver, a sum of single-qubit terms with no classical meaning, whose ground state is a uniform superposition); and slowly interpolates $H(s)=(1-s)H_B+sH_P$ as $s$ goes from 0 to 1 over a run time $T$. The quantum adiabatic theorem — the result that a system started in an eigenstate of a slowly varying Hamiltonian remains close to the corresponding instantaneous eigenstate — guarantees that the final state is close to the ground state of $H_P$ with high probability, provided $T$ is large compared to the inverse square of the minimum gap $\Delta=\min_s(E_1(s)-E_0(s))$ between the first excited state and the ground state along the path. Everything hinges on $\Delta$: if $\Delta$ shrinks only polynomially in $n$ for the instance distribution of interest the algorithm is efficient, while an exponentially small $\Delta$ forces an exponentially long run.

Childs, Farhi, and Preskill studied whether this model tolerates faults. Their numerical testbed was random instances of three-bit exact cover (EC3), an NP-complete constraint problem in which each clause over three bits is satisfied exactly when one of the three bits equals 1, and where the satisfying assignment is unique. Two error types were simulated. Decoherence — the loss of quantum information to an uncontrolled environment — was modeled by a weak-coupling Markovian master equation, the standard memoryless (Lindblad-type) open-system approximation in which the environment acts like a heat bath with a well-defined temperature and instantaneous relaxation and excitation rates. Unitary control errors were modeled as perturbations $C_j K_j$ added to the interpolation Hamiltonian: $K_1$ a sum of random single-qubit magnetic-field terms, $K_2$ a two-qubit version, and $K_3$ an error in the problem Hamiltonian itself. Their small-size data (decoherence restricted to $n=4$ by simulation cost, control errors to $n\le 10$) were consistent with strong intrinsic robustness. The mechanisms are plausible: dephasing in the energy eigenbasis is harmless because only the ground state matters; thermal excitation is Boltzmann-suppressed when temperature and coupling are small compared to $\Delta$, so a well-functioning algorithm is cooled by its own gap. But the authors also identified the failure mode: for $K_1$-type errors, if each qubit's ground-state overlap is degraded by a fixed amount $\epsilon$, the total overlap degrades like $(1-\epsilon)^n$, which is exponentially small in $n$; hence in factorized problems such errors must fall at least as fast as $1/n$ to be tolerable, and the general nonfactorized case was unresolved. The paper's Introduction states the open speedup question directly: whether the adiabatic algorithm provides a definite speedup over classical methods remains an interesting open question, and its Conclusions note that since the choices of $H_B$ and of the interpolation path are largely arbitrary, choosing a different route to $H_P$, or adding terms unrelated to $H_B$ and $H_P$ that increase $\Delta$, might speed up the algorithm — as Roland and Cerf demonstrated for unstructured search, where a locally adjusted interpolation recovers the quadratic speedup of Grover's search algorithm, which is provably optimal for that problem.

The four open issues in the source (speedup/gap scaling; robustness at large $n$, including control-error scaling; realistic noise modeling; systematic path design) are not separate research programs: they share one quantity, the minimum gap $\Delta$, and one objective, a verdict on the adiabatic model as a scalable, noise-robust, computationally useful paradigm — whether the device that works at four qubits is, as the authors put it, a powerful computational device at scale.

Problem Statement

Determine whether the adiabatic algorithm is a scalable, noise-robust, computationally useful paradigm, along the four linked directions posed by Childs, Farhi, and Preskill after their small-scale fault-tolerance study. (1) Speedup via gap scaling: characterize how the minimum gap $\Delta$ between the ground state and first excited state of the interpolation Hamiltonian scales with problem size $n$ for distributions of hard instances, and thereby determine whether the adiabatic algorithm provides a definite asymptotic quantum speedup over the best classical algorithms for some class of problems — or prove that it cannot; the affirmative target is existential, so exhibiting a single class of problems whose minimum gap scales polynomially and which is classically hard suffices, while the negative target requires showing that no such class exists. (2) Robustness at scale: establish, beyond the n ≤ 4 decoherence and n ≤ 10 control-error simulations of the source, whether the observed intrinsic robustness against decoherence and unitary control errors persists, weakens, or fails in the large-n regime and for instances with exponentially small gaps; in particular, determine for general (nonfactorized) problem Hamiltonians how the magnitudes of single-qubit random-field control errors (the source's K1 type) must scale with n — e.g., whether decay like 1/n or faster is required in general — to avoid exponentially small ground-state overlap. (3) Realistic noise models: assess the same robustness questions under experimentally relevant environmental couplings and control errors, beyond the weak-coupling Markovian master equation and uncorrelated single-qubit perturbations used in the source, including non-Markovian noise spectra and spatially correlated errors. (4) Path design: develop a systematic way to choose or optimize the interpolating Hamiltonians — the time-dependent path and additional terms beyond $H_B$ and $H_P$ — to increase $\Delta$ and reduce the runtime. These deliverables are jointly held together by the minimum gap, which simultaneously sets the runtime, the thermal-decoherence protection, and the sensitivity to perturbations; a solution is a single verdict on the source's scenario of a gap-protected device that is a powerful computational device at scale, and because that verdict is conjunctive — the paradigm is scalable, noise-robust, and computationally useful only if all four directions hold — a positive verdict requires all four directions to be settled affirmatively, a negative verdict is reached as soon as any single direction is refuted, and a result that settles one direction without refuting it resolves that sub-question while leaving the overarching verdict open.

References

1. A. M. Childs, E. Farhi, J. Preskill, "Robustness of adiabatic quantum computation", Phys. Rev. A 65, 012322 (2002), DOI 10.1103/PhysRevA.65.012322, https://doi.org/10.1103/PhysRevA.65.012322 (arXiv:quant-ph/0108048, https://arxiv.org/abs/quant-ph/0108048)
2. E. Farhi, J. Goldstone, S. Gutmann, M. Sipser, "Quantum computation by adiabatic evolution", arXiv:quant-ph/0001106 (2000), https://arxiv.org/abs/quant-ph/0001106
3. J. Roland, N. J. Cerf, "Quantum search by local adiabatic evolution", Phys. Rev. A 65, 042308 (2002), DOI 10.1103/PhysRevA.65.042308, https://doi.org/10.1103/PhysRevA.65.042308 (arXiv:quant-ph/0107015, https://arxiv.org/abs/quant-ph/0107015)
4. W. van Dam, M. Mosca, U. Vazirani, "How powerful is adiabatic quantum computation?", Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS 2001), DOI 10.1109/SFCS.2001.959902, https://doi.org/10.1109/SFCS.2001.959902
5. D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, O. Regev, "Adiabatic quantum computation is equivalent to standard quantum computation", SIAM J. Comput. 37, 166 (2007), DOI 10.1137/S0097539705447323, https://doi.org/10.1137/S0097539705447323
6. B. Altshuler, H. Krovi, J. Roland, "Anderson localization makes adiabatic quantum optimization fail", Proc. Natl. Acad. Sci. USA 107, 28 (2010), DOI 10.1073/pnas.1002116107, https://doi.org/10.1073/pnas.1002116107
7. N. G. Dickson, M. H. S. Amin, "Does adiabatic quantum optimization fail for NP-complete problems?", Phys. Rev. Lett. 106, 050502 (2011), DOI 10.1103/PhysRevLett.106.050502, https://doi.org/10.1103/PhysRevLett.106.050502
8. S. P. Jordan, E. Farhi, P. W. Shor, "Error-correcting codes for adiabatic quantum computation", Phys. Rev. A 74, 052322 (2006), DOI 10.1103/PhysRevA.74.052322, https://doi.org/10.1103/PhysRevA.74.052322
9. S. Ashhab, J. R. Johansson, F. Nori, "Decoherence in a scalable adiabatic quantum computer", Phys. Rev. A 74, 052330 (2006), DOI 10.1103/PhysRevA.74.052330, https://doi.org/10.1103/PhysRevA.74.052330
10. D. A. Lidar, "Towards fault tolerant adiabatic quantum computation", Phys. Rev. Lett. 100, 160506 (2008), DOI 10.1103/PhysRevLett.100.160506, https://doi.org/10.1103/PhysRevLett.100.160506 (arXiv:0707.0021, https://arxiv.org/abs/0707.0021)
11. S. Lloyd, "Robustness of adiabatic quantum computing", arXiv:0805.2757 (2008), https://arxiv.org/abs/0805.2757
12. T. Albash, S. Boixo, D. A. Lidar, P. Zanardi, "Quantum adiabatic Markovian master equations", New J. Phys. 14, 123016 (2012), DOI 10.1088/1367-2630/14/12/123016, https://doi.org/10.1088/1367-2630/14/12/123016
13. E. Farhi, D. Gosset, I. Hen, A. W. Sandvik, P. Shor, A. P. Young, F. Zamponi, "Performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs", Phys. Rev. A 86, 052334 (2012), DOI 10.1103/PhysRevA.86.052334, https://doi.org/10.1103/PhysRevA.86.052334
14. E. Farhi, J. Goldstone, D. Gosset, S. Gutmann, H. B. Meyer, P. Shor, "Quantum adiabatic algorithms, small gaps, and different paths", Quantum Inf. Comput. 11, 181 (2011), DOI 10.26421/QIC11.3-4-1, https://doi.org/10.26421/QIC11.3-4-1
15. K. C. Young, M. Sarovar, R. Blume-Kohout, "Error suppression and error correction in adiabatic quantum computation: Techniques and challenges", Phys. Rev. X 3, 041013 (2013), DOI 10.1103/PhysRevX.3.041013, https://doi.org/10.1103/PhysRevX.3.041013
16. K. W. Yip, T. Albash, D. A. Lidar, "Quantum trajectories for time-dependent adiabatic master equations", Phys. Rev. A 97, 022116 (2018), DOI 10.1103/PhysRevA.97.022116, https://doi.org/10.1103/PhysRevA.97.022116
17. T. Albash, D. A. Lidar, "Adiabatic quantum computation", Rev. Mod. Phys. 90, 015002 (2018), DOI 10.1103/RevModPhys.90.015002, https://doi.org/10.1103/RevModPhys.90.015002 (arXiv:1611.04471, https://arxiv.org/abs/1611.04471)
18. T. F. Rønnow, Z. Wang, J. Job, S. Boixo, S. V. Isakov, D. Wecker, J. M. Martinis, D. A. Lidar, M. Troyer, "Defining and detecting quantum speedup", Science 345, 420 (2014), DOI 10.1126/science.1252319, https://doi.org/10.1126/science.1252319
19. N. Ahmadiniaz, D. Kraft, G. Schaller, R. Schützhold, "Quantum Zeno effect versus adiabatic quantum computing and quantum annealing", New J. Phys. 28, 064502 (2026), DOI 10.1088/1367-2630/ae6e68, https://doi.org/10.1088/1367-2630/ae6e68 (arXiv:2509.04057, https://arxiv.org/abs/2509.04057)