Improved Bounds for Eigenpath Traversal

Abstract

We present a bound on the length of the path defined by the ground states of a continuous family of Hamiltonians in terms of the spectral gap G. We use this bound to obtain a significant improvement over the cost of recently proposed methods for quantum adiabatic state transformations and eigenpath traversal. In particular, we prove that a method based on evolution randomization, which is a simple extension of adiabatic quantum computation, has an average cost of order 1/G^2, and a method based on fixed-point search, has a maximum cost of order 1/G^(3/2). Additionally, if the Hamiltonians satisfy a frustration-free property, such costs can be further improved to order 1/G^(3/2) and 1/G, respectively. Our methods offer an important advantage over adiabatic quantum computation when the gap is small, where the cost is of order 1/G^3.

10 pages, 1 figure

References in corpus (14)

• Criticality, the area law, and the computational power of PEPS
• Bounds for the adiabatic approximation with applications to quantum computation
• The power of quantum systems on a line
• Simple proof of equivalence between adiabatic quantum computation and the circuit model
• Quantum Simulations of Classical Annealing Processes
• Adiabatic approximation with exponential accuracy for many-body systems and quantum computation
• Speed-up via Quantum Sampling
• A Quantum Approach to Classical Statistical Mechanics
• Simulating sparse Hamiltonians with star decompositions
• Preparing projected entangled pair states on a quantum computer
• Spectral Gap Amplification
• Quantum Computation Beyond the Circuit Model
• Period Finding with Adiabatic Quantum Computation
• An exact real-space renormalization method and applications

Cited by in corpus (8)

• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Necessary and sufficient condition for quantum adiabatic evolution by unitary control fields
• Fast Quantum Methods for Optimization
• Success of digital adiabatic simulation with large Trotter step
• Quantum adiabatic optimization without heuristics
• Quantum speed limits for adiabatic evolution, Loschmidt echo and beyond
• Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs