Simulating quantum circuits by adiabatic computation: Improved spectral gap bounds
- 1 April 2020
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review A
- Vol. 101 (4) , 042302
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 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 . 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 is , an improvement over previous bounds. Our first method is a direct approach based on an eigenstate ansatz, while 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.
Keywords
All Related Versions
Funding Information
- Science Foundation Ireland (15/CDA/3240)
- Japan Society for the Promotion of Science (JP18K03445, JP18H04478)
This publication has 15 references indexed in Scilit:
- Adiabatic quantum computationReviews of Modern Physics, 2018
- Introduction to Topological Quantum Computation2012
- Landau–Zener–Stückelberg interferometryPhysics Reports, 2010
- Adiabatic Quantum Computation Is Equivalent to Standard Quantum ComputationSIAM Review, 2008
- Simple Proof of Equivalence between Adiabatic Quantum Computation and the Circuit ModelPhysical Review Letters, 2007
- Improved Gap Estimates for Simulating Quantum Circuits by Adiabatic EvolutionQuantum Information Processing, 2006
- A One-Way Quantum ComputerPhysical Review Letters, 2001
- Eigenvalues and eigenvectors of some tridiagonal matricesActa Mathematica Hungarica, 1992
- Quantum computational networksProceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 1989
- Quantum mechanical computersFoundations of Physics, 1986