The equivalence of adiabatic quantum computation and the circuit model rests on Feynman's circuit-to-Hamiltonian construction together with a proof that the minimum spectral gap of the resulting adiabatic Hamiltonian is at least inverse polynomial in the circuit length LL. Dooley, Kells, Katsura and Dorlas gave two simplified proofs of an improved bound min⁡sΔ(s)≳π2/[8(L+1)2]\min_s \Delta(s) \gtrsim \pi^2/[8(L+1)^2] for the standard construction with uniform clock couplings: an explicit eigenstate ansatz for the tridiagonal history-subspace Hamiltonian, and a decomposition of the Hamiltonian plus Weyl's eigenvalue-perturbation theorem. The paper states as an open direction whether these two techniques extend to generalisations of the adiabatic Hamiltonian considered there; concrete generalisations studied in the modified-construction literature include nonuniform clock (off-diagonal) terms, modified boundary/endpoint conditions, and generalized clocks (branching clocks, unitary labeled graphs, and pulse clocks), and the question for such constructions is to obtain approximate eigenstates, eigenvalues, and spectral-gap bounds. No extension of these methods to modified constructions is known in the literature: gap scalings for some modified classes have been obtained by other techniques, but the eigenstate-ansatz and Weyl-decomposition approaches have not been carried over.

Background

In the circuit model of quantum computing, a computation is a sequence of one- and two-qubit gates U1,…,ULU_1,\dots,U_L applied to an input state. Feynman's circuit-to-Hamiltonian construction maps such a circuit to a time-independent 'clock' Hamiltonian HcH_c on the logical qubits plus an ancillary clock register with basis states ∣l⟩c|l\rangle_c, l=0,…,Ll=0,\dots,L: propagation terms −12(Ul⊗∣l⟩c⟨l−1∣c+Ul†⊗∣l−1⟩c⟨l∣c)-\tfrac{1}{2}(U_l\otimes|l\rangle_c\langle l-1|_c + U_l^\dagger\otimes|l-1\rangle_c\langle l|_c) drive a quantum walk along the computation history, whose ground state is a uniform superposition ('history state') over the states ∣α(l)⟩=Ul⋯U1∣α(0)⟩|\alpha(l)\rangle=U_l\cdots U_1|\alpha(0)\rangle tagged by the clock. Aharonov, van Dam, Kempe, Landau, Lloyd and Regev used this construction to prove that adiabatic quantum computation — computation by slowly varying a Hamiltonian H(s)H(s), s∈[0,1]s\in[0,1], from an easy initial ground state to a final Hamiltonian encoding the circuit output — is computationally equivalent to the circuit model. The proof requires that the minimum spectral gap Δ(s)\Delta(s) between the two lowest eigenvalues of H(s)H(s) be at least inverse polynomial in LL, since the adiabatic runtime scales as an inverse power of the gap. On the (L+1)(L+1)-dimensional invariant history subspace, H(s)H(s) reduces to an (L+1)×(L+1)(L+1)\times(L+1) tridiagonal matrix with uniform diagonal entries and uniform off-diagonal entries −s/2-s/2. Aharonov et al. proved min⁡sΔ(s)≥1/144L2\min_s\Delta(s)\ge 1/144L^2 by a Gershgorin-circle argument (a standard theorem localizing a matrix's eigenvalues in discs centred on its diagonal entries) combined with a conductance bound from the theory of Markov chain mixing; Deift, Ruskai and Spitzer improved this to min⁡sΔ(s)>1/[2(L+1)2]\min_s\Delta(s)> 1/[2(L+1)^2] using exact spectral theory of tridiagonal matrices. Dooley, Kells, Katsura and Dorlas gave two elementary proofs of min⁡sΔ(s)≥ϵ2/2+O(ϵ4)\min_s\Delta(s)\ge \epsilon^2/2+O(\epsilon^4) with ϵ=π/(2L+2)\epsilon=\pi/(2L+2), i.e. π2/[8(L+1)2]\pi^2/[8(L+1)^2] to leading order. The first proof uses an ansatz [ψ]k=αzk+1+βz−k−1[\psi]_k=\alpha z^{k+1}+\beta z^{-k-1} for the eigenvectors, which closes exactly because of the Toeplitz (uniform) structure of the tridiagonal matrix and yields transcendental equations s=1−tanh⁡[(L+1)θ]tanh⁡(θ/2)s=1-\tanh[(L+1)\theta]\tanh(\theta/2) and s=1+tan⁡[(L+1)θ]tan⁡(θ/2)s=1+\tan[(L+1)\theta]\tan(\theta/2) for real z=eθz=e^{\theta} and unit-modulus z=eiθz=e^{i\theta} roots. The second proof decomposes H(s)H(s) into a sum of Hermitian matrices with known spectra and applies Weyl's theorem (which bounds how the eigenvalues of a Hermitian matrix shift under addition of a Hermitian perturbation in terms of the perturbation's extreme eigenvalues). Both methods, as the authors emphasise, are tailored to the uniform-coupling construction. Several modifications of the construction are known: Bausch and Crosson analysed circuit Hamiltonians with nonuniform, complex-weighted clocks and branching transitions, i.e. clocks that traverse a general directed graph with the gates attached to its edges ('unitary labeled graphs'), showing for instance that nonuniform linear clocks can implement an arbitrary distribution over time steps while retaining a gap scaling as Ω(T−2)\Omega(T^{-2}); Caha, Landau and Nagaj analysed quantum walks on a line with varying endpoint terms (boundary-condition modifications) and tuned 'pulse' clocks, improving Feynman-Hamiltonian gap lower bounds. These results use other techniques — variational bounds, matrix analysis, and exact tridiagonal spectra — and do not deliver the approximate eigenstates/eigenvectors or the Weyl-style decomposition that the source paper's methods provide. Whether the eigenstate ansatz and the Weyl-theorem decomposition themselves can be carried over to such modified Hamiltonians is the open question.

Problem Statement

For modified circuit-to-Hamiltonian constructions — in which the uniform off-diagonal clock couplings of Feynman's construction are replaced by nonuniform (site-dependent) terms, the boundary/endpoint terms of the clock are modified, or the linear clock is generalized to branching clocks, unitary labeled graphs, or pulse clocks — determine whether the two techniques introduced by Dooley, Kells, Katsura and Dorlas can be extended from the uniform construction: (i) the eigenstate ansatz, i.e. an explicit parametrized ansatz for the eigenvectors of the resulting adiabatic Hamiltonian H(s)H(s) restricted to its history subspace that yields approximate eigenstates and eigenvalues, and (ii) the Weyl-theorem decomposition, i.e. a decomposition of H(s)H(s) into Hermitian terms with known extremal spectra whose combination bounds the eigenvalues. The task is resolved by a complete treatment of both techniques for every modification family listed here: for each family, either an affirmative extension that derives approximate eigenstates and eigenvalues and a rigorous lower bound on the minimum spectral gap min⁡sΔ(s)\min_s \Delta(s) as a function of the circuit length LL and of the modification parameters (e.g. the clock distribution), or a justified obstruction showing that the technique does not carry over. These families overlap (unitary labeled graphs generalise nonuniform linear and branching clocks, and pulse tuning is a particular nonuniform coupling), so a complete treatment of a general family also discharges its special cases, and no listed family may be left untreated. The objective is a spectral-gap analysis of modified circuit-to-Hamiltonian adiabatic Hamiltonians by these methods.

References

  1. Shane Dooley, Graham Kells, Hosho Katsura, Tony C. Dorlas, 'Simulating quantum circuits by adiabatic computation: Improved spectral gap bounds', Physical Review A 101, 042302 (2020). DOI: 10.1103/PhysRevA.101.042302, https://arxiv.org/abs/1906.05233
  2. Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev, 'Adiabatic quantum computation is equivalent to standard quantum computation', SIAM Review 50, 755–787 (2008). DOI: 10.1137/080734479, https://doi.org/10.1137/080734479
  3. Percy Deift, Mary Beth Ruskai, Wolfgang Spitzer, 'Improved gap estimates for simulating quantum circuits by adiabatic evolution', Quantum Information Processing 6, 121–125 (2007). DOI: 10.1007/s11128-006-0045-y, https://doi.org/10.1007/s11128-006-0045-y
  4. Richard P. Feynman, 'Quantum mechanical computers', Foundations of Physics 16, 507–531 (1986). DOI: 10.1007/BF01886518, https://doi.org/10.1007/BF01886518
  5. Johannes Bausch, Elizabeth Crosson, 'Analysis and limitations of modified circuit-to-Hamiltonian constructions', Quantum 2, 94 (2018). DOI: 10.22331/q-2018-09-19-94, https://arxiv.org/abs/1609.08571
  6. Libor Caha, Zeph Landau, Daniel Nagaj, 'Clocks in Feynman's computer and Kitaev's local Hamiltonian: Bias, gaps, idling, and pulse tuning', Physical Review A 97, 062306 (2018). DOI: 10.1103/PhysRevA.97.062306, https://arxiv.org/abs/1712.07395
  7. Carlos E. González-Guillén, Toby S. Cubitt, 'History-state Hamiltonians are critical' (2018). arXiv:1810.06528, https://arxiv.org/abs/1810.06528
  8. James D. Watson, 'Detailed Analysis of Circuit-to-Hamiltonian Mappings' (2019). arXiv:1910.01481, https://arxiv.org/abs/1910.01481
  9. Ralph Jason Costales, Alex Gunning, Tony C. Dorlas, 'Efficiency of Feynman's quantum computer', Physical Review A 111, 022615 (2025). DOI: 10.1103/PhysRevA.111.022615, https://arxiv.org/abs/2309.09331
  10. Abhinav Deshpande, Alexey V. Gorshkov, Bill Fefferman, 'Importance of the spectral gap in estimating ground-state energies', PRX Quantum 3, 040327 (2022). DOI: 10.1103/PRXQuantum.3.040327, https://arxiv.org/abs/2007.11582
  11. Feng Qian, Peter J. Love, 'Universal Parent Hamiltonians for Adiabatic Warm Starts' (2026). arXiv:2607.16857, https://arxiv.org/abs/2607.16857