Simulating quantum circuits by adiabatic computation: improved spectral gap bounds

Abstract

Adiabatic quantum computing is a framework for quantum computing that is superficially very different to the standard circuit model. However, it can be shown that the two models are computationally equivalent. The key to the proof is a mapping of a quantum circuit to an an adiabatic evolution, and then showing that the minimum spectral gap of the adiabatic Hamiltonian is at least inverse polynomial in the number of computational steps $L$. In this paper we provide two simplified proofs that the gap is inverse polynomial. Both proofs result in the same lower bound for the minimum gap, which for $L\gg 1$ is ${\min }_s\Delta \gtrsim {\pi }^2/[8(L+1{)}^2]$, an improvement over previous estimates. Our first method is a direct approach based on an eigenstate ansatz, while the the second uses Weyl's theorem to leverage known exact results into a bound for the gap. Our results suggest that it may be possible to use these methods to find bounds for spectral gaps of Hamiltonians in other scenarios.

arXiv comment7 pages, 2 figures. Changes: Added a second proof of the bound. Added a new author. Other minor changes

References in corpus (7)

• Adiabatic Quantum Computing
• Landau-Zener-Stuckelberg interferometry
• Bounds for the adiabatic approximation with applications to quantum computation
• Simple proof of equivalence between adiabatic quantum computation and the circuit model
• Exact ground states and topological order in interacting Kitaev/Majorana chains
• The Feynman-Kitaev computer's clock: bias, gaps, idling and pulse tuning
• Analysis and limitations of modified circuit-to-Hamiltonian constructions

Cited by in corpus (2)

• Importance of the spectral gap in estimating ground-state energies
• Realization of Heisenberg models of spin systems with polar molecules in pendular states