Limits of Short-Time Evolution of Local Hamiltonians
arXiv:2104.12808 · doi:10.22331/q-2022-06-27-744
Abstract
Evolutions of local Hamiltonians in short times are expected to remain local and thus limited. In this paper, we validate this intuition by proving some limitations on short-time evolutions of local time-dependent Hamiltonians. We show that the distribution of the measurement output of short-time (at most logarithmic) evolutions of local Hamiltonians are \emph{concentrated} and satisfy an \emph{isoperimetric inequality}. To showcase explicit applications of our results, we study the \textsc{MaxCut} problem and conclude that quantum annealing needs at least a run-time that scales logarithmically in the problem size to beat classical algorithms on \textsc{MaxCut}. To establish our results, we also prove a Lieb-Robinson bound that works for time-dependent Hamiltonians which might be of independent interest.
arXiv comment25 pages, 4 figures
References in corpus (34)
- Quantum Annealing in the Transverse Ising Model
- A Quantum Approximate Optimization Algorithm
- Adiabatic Quantum Computing
- Lieb-Robinson bounds and the generation of correlations and topological quantum order
- Quantum Computation by Adiabatic Evolution
- Benchmarking an 11-qubit quantum computer
- A Theory of Trotter Error
- Demonstrating a Continuous Set of Two-qubit Gates for Near-term Quantum Algorithms
- Experimental signature of programmable quantum annealing
- Obstacles to State Preparation and Variational Optimization from Symmetry Protection
- Propagation of Correlations in Quantum Lattice Systems
- Quantum annealing of the Traveling Salesman Problem
- Error corrected quantum annealing with hundreds of qubits
- Application of Quantum Annealing to Training of Deep Neural Networks
- Quantum Speedup by Quantum Annealing
- Quantum annealing versus classical machine learning applied to a simplified computational biology problem
- Quantum annealing with a network of all-to-all connected, two-photon driven Kerr nonlinear oscillators
- Prospects for Quantum Enhancement with Diabatic Quantum Annealing
- Optimal Protocols in Quantum Annealing and QAOA Problems
- Extremal Cuts of Sparse Random Graphs
- Quantum annealing correction for random Ising problems
- Hybrid quantum-classical algorithms for approximate graph coloring
- Quantum Annealing for Constrained Optimization
- The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
- Classical algorithms for quantum mean values
- Optimization by Quantum Annealing: Lessons from Simple Cases
- The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
- Local Hamiltonians Whose Ground States are Hard to Approximate
- The Power of Adiabatic Quantum Computation with No Sign Problem
- Operator growth bounds from graph theory
- Optimal Control for Closed and Open System Quantum Optimization
- Ramanujan Coverings of Graphs
- Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs
- Behavior of Analog Quantum Algorithms