Thermally assisted adiabatic quantum computation beyond the two-level Markovian anticrossing: multi-level spectra, non-Markovian and low-frequency-noise environments, and physically realizable super-Ohmic baths

Amin, Love, and Truncik [Phys. Rev. Lett. 100, 060503 (2008)] showed, using a two-level (anticrossing) reduction and a Markovian, secular Bloch-Redfield treatment of a thermal bosonic bath, that a super-Ohmic environment (spectral density $S(\omega)\propto\omega^{s}$ with $0<s<1$) can introduce a thermal-mixing time scale $t_d\propto g_m^{-4/(3-s)}$ at the minimum gap $g_m$ that scales better than the closed-system adiabatic time $t_a\sim g_m^{-2}$, potentially improving the scaling of adiabatic quantum computation (demonstrated for adiabatic Grover search), while post-anticrossing relaxation yields only a prefactor improvement. The authors themselves flag the assumptions as unresolved: the two-level reduction fails for generic multi-level spectra (computing the relaxation time scale for a general problem is, in their words, very difficult); sub-Ohmic baths and strong low-frequency noise invalidate the Markovian and secular approximations; and low-frequency spin-like environments are expected to remove the enhancement. Which realistic physical systems provide the required suppressed low-frequency spectral weight at scale is a closely related question. The literature since 2008 contains substantial but partial progress: refined Markovian adiabatic master equations, numerical open-system simulations of multi-level anneals, specific models and experiments where dissipation helps (prefactor-level so far), and engineered-reservoir proposals. No general theory or refutation of environment-assisted scaling enhancement exists for generic multi-level, non-Markovian, realistic-bath settings, and no scaling-level (rather than prefactor) advantage has been demonstrated in any physical system. The problem in its original generality remains open.

Background

Adiabatic quantum computation (AQC) encodes the answer to a computational problem in the ground state of a final Hamiltonian $H_1$ and reaches it by slowly deforming an easy-to-prepare initial Hamiltonian $H_0$ into $H_1$; quantum annealing is the practical version of this idea used, e.g., in superconducting annealers built from flux qubits (superconducting loops whose two persistent-current states encode a qubit). Performance is limited by the minimum spectral gap $g_m$ between the ground state and first excited state, which typically occurs at an avoided level crossing (anticrossing): the closed-system adiabatic theorem requires an anneal time $t_a$ scaling roughly as $g_m^{-2}$, so exponentially small gaps are fatal. The elementary process at a single anticrossing is a Landau-Zener transition, the well-characterized excitation dynamics of a two-level system swept through an avoided crossing.

Real devices are coupled to an environment (bath) characterized by a noise spectral density $S(\omega)$, classified by its low-frequency exponent: Ohmic ($S\propto\omega^0$ at low frequency), super-Ohmic (suppressed low-frequency weight, $S\propto\omega^{s}$ with $s>0$), and sub-Ohmic (enhanced low-frequency weight). The Bloch-Redfield formalism is a weak-coupling master equation for the system density matrix; it relies on the Markovian approximation (bath correlation time much shorter than the system's decay times) and usually the secular approximation (rotating-wave approximation, which neglects rapidly oscillating terms). Solid-state environments also contain discrete microscopic degrees of freedom (nuclear spins, paramagnetic defects, flux or charge fluctuators), modeled as spin baths, which generate strong low-frequency (often $1/f$-like) noise that violates these approximations.

Amin, Love, and Truncik analyzed AQC near an isolated anticrossing using two-level Bloch-Redfield equations and identified three time scales: the adiabatic time $t_a\sim g_m^{-2}$, a thermal-mixing time $t_d$ (the time for the bath to thermally equilibrate the two crossing states near the anticrossing), and a post-anticrossing relaxation time $t_r$. For a super-Ohmic bath with $0<s<1$ and $g_m\ll\tilde{\gamma}(0)$ (gap much smaller than the dephasing rate at zero frequency), they derived $t_d\propto g_m^{-4/(3-s)}$, which beats the adiabatic scaling, so thermal mixing at the anticrossing can improve the scaling of the computation itself; they applied this to adiabatic Grover search (the adiabatic implementation of Grover's quantum algorithm for unstructured database search), finding $t_d\sim N^{2/(3-s)}$ in the database size $N$, better than classical search. Relaxation after the anticrossing gives only $t_r=t_a/\kappa_s$, a prefactor improvement. Earlier open-system work (Sarandy and Lidar) had established adiabatic conditions for open systems but not this scaling mechanism.

The result rests on assumptions the authors themselves identified as unverified: (i) the two-level reduction, valid only in a narrow parameter window (for their Grover example it requires temperature $T\ll E/\log N$), whereas generic many-body spectra contain multi-level crossings and dense excited-state structures, and computing the relaxation time scale for a general problem was described as very difficult; (ii) the Markovian and secular approximations, which fail for sub-Ohmic baths ($s<0$), strong low-frequency noise, or other non-Markovian environments, leaving behavior in those regimes untreated; and (iii) the super-Ohmic scaling advantage requires suppressed low-frequency spectral weight and $0<s<1$ simultaneously, and low-frequency noise, as supplied by spin-like environments, is acknowledged to remove the enhancement. Beyond the caveats enumerated by the authors, no realistic physical bath has been shown to satisfy the required spectral and Markovian conditions for large-scale AQC. Reviews (Albash and Lidar, Rev. Mod. Phys. 90, 015002 (2018)) confirm that thermally assisted tunneling observed in experiments so far contributes only prefactor improvements, not scaling advantages.

Problem Statement

Determine whether, and under what general conditions, a thermal environment can improve the performance of adiabatic quantum computation beyond the restricted regime analyzed by Amin, Love, and Truncik (2008) - or prove that it cannot. The 2008 result established, within a two-level anticrossing reduction and a weak-coupling Markovian secular Bloch-Redfield treatment of a bath with spectral density $S(\omega)\propto\omega^{s}$, that a super-Ohmic bath with $0<s<1$ and $g_m\ll\tilde{\gamma}(0)$ yields a thermal-mixing time $t_d\propto g_m^{-4/(3-s)}$ at the minimum gap that outperforms the adiabatic time $t_a\sim g_m^{-2}$, improving the scaling of the computation (as illustrated by adiabatic Grover search), while post-anticrossing relaxation gives only a prefactor improvement. The unresolved problem, as left by the source, has two jointly supporting components: (1) generalize the time-scale analysis ($t_d$, $t_r$) beyond the two-level approximation to generic multi-level spectra - the source states that calculating the relaxation time for a general problem is very difficult - and establish whether any scaling advantage of thermal mixing survives; and (2) treat the regimes in which the Markovian and secular approximations fail - sub-Ohmic spectral densities, strong low-frequency noise, and spin-like environments - and determine quantitatively when the low-frequency noise they supply removes the predicted enhancement, including whether any non-Markovian environment can assist rather than degrade AQC. A closely related question is whether physically realizable baths possessing the required suppressed low-frequency spectral weight exist that satisfy the Markovian validity criteria at the temperatures, system sizes, and noise levels of large-scale AQC implementations. A complete answer must resolve both components (1) and (2); the physical-realizability question above is supplementary - an answer should address it where possible, but it is not required for closure. An answer may take the form of a general theory with derived time-scale scalings and validity conditions, a rigorous negative result for the whole class of baths and spectra addressed by components (1) and (2) - generic multi-level spectra together with non-Markovian, sub-Ohmic, and spin-like environments - or a combination of these. A negative result holding only for a single model or a proper subclass of that class does not close the problem: like a quantitative demonstration in a physically realistic system, or any other partial answer restricted to specific models, it constitutes progress toward the general conditions asked for but does not by itself close the problem as stated.

References

1. M. H. S. Amin, Peter J. Love, C. J. S. Truncik, Thermally Assisted Adiabatic Quantum Computation, Phys. Rev. Lett. 100, 060503 (2008). DOI:10.1103/PhysRevLett.100.060503, https://arxiv.org/abs/cond-mat/0609332
2. M. S. Sarandy, D. A. Lidar, Adiabatic Quantum Computation in Open Systems, Phys. Rev. Lett. 95, 250503 (2005). DOI:10.1103/PhysRevLett.95.250503, https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.95.250503
3. Tameem Albash, Sergio Boixo, Daniel A. Lidar, Paolo Zanardi, Quantum adiabatic Markovian master equations, New J. Phys. 14, 123016 (2012). DOI:10.1088/1367-2630/14/12/123016, https://iopscience.iop.org/article/10.1088/1367-2630/14/12/123016
4. Tameem Albash, Daniel A. Lidar, Decoherence in adiabatic quantum computation, Phys. Rev. A 91, 062320 (2015). DOI:10.1103/PhysRevA.91.062320, https://journals.aps.org/pra/abstract/10.1103/PhysRevA.91.062320
5. Tameem Albash, Daniel A. Lidar, Adiabatic quantum computation, Rev. Mod. Phys. 90, 015002 (2018). DOI:10.1103/RevModPhys.90.015002, https://arxiv.org/abs/1611.04471
6. N. G. Dickson, M. W. Johnson, M. H. Amin, R. Harris, et al., Thermally assisted quantum annealing of a 16-qubit problem, Nat. Commun. 4, 1903 (2013). DOI:10.1038/ncomms2920, https://www.nature.com/articles/ncomms2920
7. S. Boixo, T. F. Rønnow, S. V. Isakov, Z. Wang, D. Wecker, D. A. Lidar, J. M. Martinis, M. Troyer, Evidence for quantum annealing with more than one hundred qubits, Nat. Phys. 10, 218 (2014). DOI:10.1038/nphys2900, https://www.nature.com/articles/nphys2900
8. I. de Vega, M. C. Bañuls, A. Pérez, Effects of dissipation on an adiabatic quantum search algorithm, New J. Phys. 12, 123010 (2010). DOI:10.1088/1367-2630/12/12/123010, https://iopscience.iop.org/article/10.1088/1367-2630/12/12/123010
9. Anurag Mishra, Tameem Albash, Daniel A. Lidar, Finite temperature quantum annealing solving exponentially small gap problem with non-monotonic success probability, Nat. Commun. 9, 2917 (2018). DOI:10.1038/s41467-018-05239-9, https://www.nature.com/articles/s41467-018-05239-9
10. G. Passarelli, G. De Filippis, V. Cataudella, P. Lucignano, Dissipative environment may improve the quantum annealing performances of the ferromagnetic p-spin model, Phys. Rev. A 97, 022319 (2018). DOI:10.1103/PhysRevA.97.022319, https://journals.aps.org/pra/abstract/10.1103/PhysRevA.97.022319
11. Leonardo Novo, Shantanav Chakraborty, Masoud Mohseni, Yasser Omar, Environment-assisted analog quantum search, Phys. Rev. A 98, 022316 (2018). DOI:10.1103/PhysRevA.98.022316, https://journals.aps.org/pra/abstract/10.1103/PhysRevA.98.022316
12. Feng-Hua Ren, Zhao-Ming Wang, Lian-Ao Wu, Accelerated adiabatic quantum search algorithm via pulse control in a non-Markovian environment, Phys. Rev. A 102, 062603 (2020). DOI:10.1103/PhysRevA.102.062603, https://journals.aps.org/pra/abstract/10.1103/PhysRevA.102.062603
13. X. Dai, R. Trappen, H. Chen, et al., Dissipative Landau-Zener tunneling in the crossover regime from weak to strong environment coupling, Nat. Commun. 16, 329 (2025). DOI:10.1038/s41467-024-55588-x, https://www.nature.com/articles/s41467-024-55588-x
14. Mojdeh S. Najafabadi, Daniel Schumayer, Chee-Kong Lee, Dieter Jaksch, David A. W. Hutchinson, Improving quantum annealing by engineering the coupling to the environment, EPJ Quantum Technol. 10, 44 (2023). DOI:10.1140/epjqt/s40507-023-00202-0, https://epjquantumtechnology.springeropen.com/articles/10.1140/epjqt/s40507-023-00202-0
15. Tadashi Kadowaki, Masayuki Ohzeki, Experimental and Theoretical Study of Thermodynamic Effects in a Quantum Annealer, J. Phys. Soc. Jpn. 88, 061008 (2019). DOI:10.7566/JPSJ.88.061008, https://journals.jps.jp/doi/10.7566/JPSJ.88.061008
16. Lorenzo Campos Venuti, Tameem Albash, Milad Marvian, Daniel Lidar, Paolo Zanardi, Relaxation versus adiabatic quantum steady-state preparation, Phys. Rev. A 95, 042302 (2017). DOI:10.1103/PhysRevA.95.042302, https://journals.aps.org/pra/abstract/10.1103/PhysRevA.95.042302
17. Yuanyang Zhou, Biao Wu, Engineered dissipation for faster adiabatic state preparation (2026). arXiv:2606.05815, https://arxiv.org/abs/2606.05815