Quantitative minimum-gap scaling for no-crossing adiabatic Hamiltonians: the efficiency problem of the Zhang–Yu–Tong gap theorem

Zhang, Yu, and Tong (Phys. Rev. A 90, 042321 (2014)) proved that for an adiabatic interpolation $H(s)=(1-s)H_i+sH_p$ whose problem Hamiltonian $H_p$ is diagonal in the computational basis, two checkable conditions — a unique ground state of $H_i$ of the form $U|r\rangle$ with $r_i>0$ and $U$ diagonal unitary, and nonpositive off-diagonal elements of $U^\dagger H_i U$ — guarantee a nonzero ground/excited gap for all $s\in[0,1)$. The theorem is only a sufficient no-crossing statement: it gives no information on the magnitude or system-size scaling of the minimum gap, and hence none on the runtime certified by the adiabatic bound; its conditions are sufficient, with necessity uncharacterized in the paper; and it is framed for diagonal $H_p$ as a modelling choice. The open problem posed by the authors is a quantitative a priori characterization of the minimum gap $\Delta_{\min}=\min_{s\in[0,1)}(\epsilon_1(s)-\epsilon_0(s))$ and its scaling with problem size for Hamiltonians in this no-crossing class, sufficient — via the adiabatic runtime bound $T\gtrsim 1/\Delta_{\min}^2$ — to assess whether the standard adiabatic guarantee yields polynomial runtime for instances of the class.

Background

Adiabatic quantum computation (AQC) computes by preparing the ground state of an easy initial Hamiltonian $H_i$ and slowly deforming it, $H(s)=(1-s)H_i+sH_p$ for $s\in[0,1]$, into a problem Hamiltonian $H_p$ whose ground state encodes the answer. The adiabatic theorem says the evolution stays near the instantaneous ground state provided the evolution is slow relative to the inverse square of the minimum spectral gap $\Delta_{\min}=\min_{s\in[0,1)}(\epsilon_1(s)-\epsilon_0(s))$, the energy difference between the ground and first excited states; the standard adiabatic runtime bound therefore scales as $T\gtrsim 1/\Delta_{\min}^2$, so the existence of a gap settles correctness while the gap's magnitude and its scaling with problem size control the runtime certified by this bound. The certification is one-directional: an inverse-polynomial gap certifies polynomial runtime under the standard condition, whereas an exponentially small gap does not by itself exclude an efficient schedule under refined adiabatic conditions — as the source authors note in a footnote, the Somma–Nagaj–Kieferová annealing schedule (Phys. Rev. Lett. 109, 050501 (2012)) for the glued-trees problem is still efficient even though the minimum energy gap is exponentially small in the problem size. A central difficulty is that the Hilbert space dimension grows exponentially with the number $n$ of bits or qubits, so a gap that is merely nonzero may still be exponentially small, making the algorithm inefficient. Zhang, Yu, and Tong considered Hamiltonians whose problem part $H_p$ is diagonal in the computational basis, with $H_i$ having a unique ground state $|\psi_0\rangle=U|r\rangle$ where all $r_i>0$ and $U$ is a diagonal unitary, and required that $U^\dagger H_i U$ have nonpositive off-diagonal matrix elements (the no-sign-problem or stoquastic situation — real matrices with nonpositive off-diagonal entries, here after a diagonal basis change). By a Perron–Frobenius argument (the classical theorem that a matrix with strictly positive entries has a simple top eigenvalue with a positive eigenvector, applied to a power of the propagator $F(s)$), they proved that under these two conditions the gap of $H(s)$ is nonzero for every $s\in[0,1)$: no level crossing can occur. Their Discussion is explicit that this leaves the decisive question open: they write that they do not attempt to resolve the efficiency issue, and they note it is quite difficult to theoretically analyze the changing trend of the energy gap for a general Hamiltonian because the dimension grows exponentially with problem size. The quantitative gap problem therefore survives as the author-posed open core: obtain a priori bounds on, or a characterization of, $\Delta_{\min}$ and its scaling with $n$ for Hamiltonians satisfying the no-crossing conditions, sufficient to assess the runtime certified by the adiabatic bound for instances of this class. That no uniform polynomial lower bound on $\Delta_{\min}$ can hold across the whole class is already known from within the paper's own examples: adiabatic unstructured search satisfies the hypotheses and has $\Delta_{\min}\sim N^{-1/2}=2^{-n/2}$, so the honest target is instance- or parameter-dependent bounds that nevertheless govern the class, not a blanket bound. Two further observations about the theorem's scope are context rather than author-posed open problems: the two conditions are sufficient for absence of level crossing, but the paper does not pose or settle their necessity (it only illustrates with a two-qubit example that crossing can occur when the second condition fails); and the restriction to diagonal $H_p$ is a modelling choice ("our discussion focuses on the Hamiltonians defined by Eq. (1) with Eq. (2)"), the only generalization the authors themselves announce being to general monotone interpolation schedules $H(t)=a(t)H_i+b(t)H_p$. Adjacent complexity results frame what a general answer can look like without answering it: AQC with inverse-polynomial gaps is polynomially equivalent to standard circuit computation (Aharonov, van Dam, Kempe, Landau, Lloyd, Regev), so gap estimation at inverse-polynomial precision for general local Hamiltonians is QMA-hard (hard for the quantum analogue of NP); spectral-gap determination is undecidable in the thermodynamic limit, even in one dimension (Cubitt, Perez-Garcia, Wolf; Bausch, Cubitt, Lucia, Perez-Garcia); and for stoquastic Hamiltonians the local-Hamiltonian problem sits in AM, a classical complexity class of interactive proofs with a randomized verifier (Arthur) and an all-powerful prover (Merlin) (Bravyi, DiVincenzo, Oliveira, Terhal), with no polynomial-time gap-estimation procedure known.

Problem Statement

For adiabatic interpolations $H(s)=(1-s)H_i+sH_p$, $s\in[0,1]$, with $H_p$ diagonal in the computational basis and $H_i$ satisfying the Zhang–Yu–Tong conditions (unique ground state $U|r\rangle$ with all $r_i>0$ and $U$ diagonal unitary; nonpositive off-diagonal elements of $U^\dagger H_i U$), the absence of level crossings is guaranteed but the gap's size is not. Determine, with proof, a quantitative a priori characterization of the minimum gap $\Delta_{\min}=\min_{s\in[0,1)}(\epsilon_1(s)-\epsilon_0(s))$ for Hamiltonians in this class — bounds or formulas capturing its magnitude and its scaling with the number of qubits/bits $n$ — sufficient to determine, via the adiabatic runtime bound $T\gtrsim 1/\Delta_{\min}^2$, the runtime certified by the standard adiabatic condition for instances of this class. Since adiabatic unstructured search lies within the class and has $\Delta_{\min}\sim 2^{-n/2}$, no uniform polynomial lower bound on $\Delta_{\min}$ can hold across the class; the requested characterization may therefore be instance- or parameter-dependent, but it must apply to every Hamiltonian in the class and be expressed through that Hamiltonian's data (for example, explicit dependence on the diagonal entries $f_z$ of $H_p$, the amplitudes $r_i$, or the diagonal unitary $U$), rather than amount to a closed-form solution of a single exactly solvable special case; a characterization resolves the task when the runtime it certifies through $T\gtrsim 1/\Delta_{\min}^2$ can be read off from it as an explicit function of the problem size $n$ and that Hamiltonian data — in particular, when it settles whether that certified runtime is polynomial or superpolynomial. This serves one objective: converting the qualitative no-crossing theorem into quantitative gap information from which the adiabatic runtime guarantee for algorithms in this class can be assessed.

References

1. Da-Jian Zhang, Xiao-Dong Yu, D. M. Tong, "Theorem on the existence of a nonzero energy gap in adiabatic quantum computation", Phys. Rev. A 90, 042321 (2014). DOI: 10.1103/PhysRevA.90.042321; arXiv:1410.3562, https://arxiv.org/abs/1410.3562
2. J. Roland and N. Cerf, "Quantum search by local adiabatic evolution", Phys. Rev. A 65, 042308 (2002). DOI: 10.1103/PhysRevA.65.042308; arXiv:quant-ph/0107015, https://arxiv.org/abs/quant-ph/0107015
3. 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; arXiv:quant-ph/0405098, https://arxiv.org/abs/quant-ph/0405098
4. T. Cubitt, D. Perez-Garcia, M. Wolf, "Undecidability of the spectral gap", Nature 528, 207 (2015). DOI: 10.1038/nature16059; arXiv:1502.04573, https://arxiv.org/abs/1502.04573
5. J. Bausch, T. Cubitt, A. Lucia, D. Perez-Garcia, "Undecidability of the Spectral Gap in One Dimension", Phys. Rev. X 10, 031038 (2020). DOI: 10.1103/PhysRevX.10.031038; arXiv:1810.01858, https://arxiv.org/abs/1810.01858
6. S. Bravyi, D. DiVincenzo, R. Oliveira, B. Terhal, "The complexity of stoquastic local Hamiltonian problems", Quantum Information and Computation 8, 361 (2008). DOI: 10.26421/QIC8.5-1; arXiv:quant-ph/0606140, https://arxiv.org/abs/quant-ph/0606140
7. Jie Sun and Songfeng Lu, "A family of system Hamiltonian in quantum adiabatic search type problem", Int. J. Quantum Inform. 17, 1950015 (2019). DOI: 10.1142/S0219749919500151, https://doi.org/10.1142/S0219749919500151