Spectral Gap Amplification

Abstract

A large number of problems in science can be solved by preparing a specific eigenstate of some Hamiltonian H. The generic cost of quantum algorithms for these problems is determined by the inverse spectral gap of H for that eigenstate and the cost of evolving with H for some fixed time. The goal of spectral gap amplification is to construct a Hamiltonian H' with the same eigenstate as H but a bigger spectral gap, requiring that constant-time evolutions with H' and H are implemented with nearly the same cost. We show that a quadratic spectral gap amplification is possible when H satisfies a frustration-free property and give H' for these cases. This results in quantum speedups for optimization problems. It also yields improved constructions for adiabatic simulations of quantum circuits and for the preparation of projected entangled pair states (PEPS), which play an important role in quantum many-body physics. Defining a suitable black-box model, we establish that the quadratic amplification is optimal for frustration-free Hamiltonians and that no spectral gap amplification is possible, in general, if the frustration-free property is removed. A corollary is that finding a similarity transformation between a stoquastic Hamiltonian and the corresponding stochastic matrix is hard in the black-box model, setting limits to the power of some classical methods that simulate quantum adiabatic evolutions.

14 pages. New version has an improved section on adiabatic simulations of quantum circuits

References in corpus (8)

• Spatial search by quantum walk
• 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
• Speed-up via Quantum Sampling
• A Quantum Approach to Classical Statistical Mechanics

Cited by in corpus (27)

• Adiabatic Quantum Computing
• Hamiltonian Simulation by Qubitization
• Computational Role of Multiqubit Tunneling in a Quantum Annealer
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Standard Model Physics and the Digital Quantum Revolution: Thoughts about the Interface
• Adiabatic state preparation study of methylene
• Local gap threshold for frustration-free spin systems
• Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
• Error suppression and error correction in adiabatic quantum computation II: non-equilibrium dynamics
• Fast quantum computation at arbitrarily low energy
• Fast-forwarding quantum evolution
• Quantum algorithms from fluctuation theorems: Thermal-state preparation
• An Integrated Programming and Development Environment for Adiabatic Quantum Optimization
• Preparing topological PEPS on a quantum computer
• Computing partition functions in the one clean qubit model
• Fast Quantum Methods for Optimization
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Improved Bounds for Eigenpath Traversal
• Speedup of the Quantum Adiabatic Algorithm using Delocalization Catalysis
• Hamiltonian simulation for low-energy states with optimal time dependence
• Fast quantum simulation of electronic structure by spectrum amplification
• Speeding up Quantum Annealing with Engineered Dephasing
• Nearly-frustration-free ground state preparation
• Exponential distillation of dominant eigenproperties
• On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number
• Fighting Exponentially Small Gaps by Counterdiabatic Driving
• An exact real-space renormalization method and applications