Quantum algorithm for simulating real time evolution of lattice Hamiltonians

Abstract

We study the problem of simulating the time evolution of a lattice Hamiltonian, where the qubits are laid out on a lattice and the Hamiltonian only includes geometrically local interactions (i.e., a qubit may only interact with qubits in its vicinity). This class of Hamiltonians is very general and is believed to capture fundamental interactions of physics. Our algorithm simulates the time evolution of such a Hamiltonian on $n$ qubits for time $T$ up to error $\epsilon$ using $\mathcal{O}(nT\mathrm{polylog}(nT/\epsilon ))$ gates with depth $\mathcal{O}(T\mathrm{polylog}(nT/\epsilon ))$. Our algorithm is the first simulation algorithm that achieves gate cost quasilinear in $nT$ and polylogarithmic in $1/\epsilon$. Our algorithm also readily generalizes to time-dependent Hamiltonians and yields an algorithm with similar gate count for any piecewise slowly varying time-dependent bounded local Hamiltonian. We also prove a matching lower bound on the gate count of such a simulation, showing that any quantum algorithm that can simulate a piecewise constant bounded local Hamiltonian in one dimension to constant error requires $\tilde{\Omega }(nT)$ gates in the worst case. The lower bound holds even if we only require the output state to be correct on local measurements. To our best knowledge, this is the first nontrivial lower bound on the gate complexity of the simulation problem. Our algorithm is based on a decomposition of the time-evolution unitary into a product of small unitaries using Lieb-Robinson bounds. In the appendix, we prove a Lieb-Robinson bound tailored to Hamiltonians with small commutators between local terms, giving zero Lieb-Robinson velocity in the limit of commuting Hamiltonians. This improves the performance of our algorithm when the Hamiltonian is close to commuting.

37 pages, 4 figures (v2) refs added (v3) FOCS 2018 (v4) minor corrections

References in corpus (8)

• Simulating Hamiltonian dynamics with a truncated Taylor series
• Synthesis of Quantum Logic Circuits
• Toward the first quantum simulation with quantum speedup
• Lieb-Robinson Bounds and the Exponential Clustering Theorem
• The Dynamics of 1D Quantum Spin Systems Can Be Approximated Efficiently
• Quantum Algorithm for Spectral Measurement with Lower Gate Count
• Product Decomposition of Periodic Functions in Quantum Signal Processing
• Simulating the dynamics of time-dependent Hamiltonians with a truncated Dyson series

Cited by in corpus (76)

• Standard Model Physics and the Digital Quantum Revolution: Thoughts about the Interface
• Quantum Circuits assisted by LOCC: Transformations and Phases of Matter
• Preparation of matrix product states with log-depth quantum circuits
• Holographic quantum algorithms for simulating correlated spin systems
• Provably accurate simulation of gauge theories and bosonic systems
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition
• Speed limits and locality in many-body quantum dynamics
• Efficient Fully-Coherent Quantum Signal Processing Algorithms for Real-Time Dynamics Simulation
• Primitive Quantum Gates for an SU(2) Discrete Subgroup: BT
• Primitive Quantum Gates for Dihedral Gauge Theories
• Measuring Arbitrary Physical Properties in Analog Quantum Simulation
• Reducing molecular electronic Hamiltonian simulation cost for Linear Combination of Unitaries approaches
• Algebraic Compression of Quantum Circuits for Hamiltonian Evolution
• Variational Hamiltonian simulation for translational invariant systems via classical pre-processing
• First-Order Trotter Error from a Second-Order Perspective
• Lattice Renormalization of Quantum Simulations
• Non-zero momentum requires long-range entanglement
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Efficient quantum Gibbs samplers with Kubo--Martin--Schwinger detailed balance condition
• Quantum simulation of real-space dynamics
• Probing Geometric Excitations of Fractional Quantum Hall States on Quantum Computers
• Nearly-optimal state preparation for quantum simulations of lattice gauge theories
• Exponential improvements in the simulation of lattice gauge theories using near-optimal techniques
• Quantum computation of molecular structure using data from challenging-to-classically-simulate nuclear magnetic resonance experiments
• Hierarchical Qubit Maps and Hierarchical Quantum Error Correction
• Problem specific classical optimization of Hamiltonian simulation
• Average-case Speedup for Product Formulas
• Optimal Hamiltonian simulation for time-periodic systems
• Continuous Hamiltonian dynamics on digital quantum computers without discretization error
• Optimal quantum algorithm for Gibbs state preparation
• Doubling the order of approximation via the randomized product formula
• Hamiltonian simulation for low-energy states with optimal time dependence
• Exactly solvable many-body dynamics from space-time duality
• Riemannian quantum circuit optimization for Hamiltonian simulation
• Quantum master equation for many-body systems: Derivation based on the Lieb-Robinson bound
• Eigenstate Fluctuation Theorem in the Short and Long Time Regimes
• Parallel Quantum Algorithm for Hamiltonian Simulation
• Efficient and practical Hamiltonian simulation from time-dependent product formulas
• Invertible subalgebras
• Scalable simulation of non-equilibrium quantum dynamics via classically optimised unitary circuits
• Digital quantum simulation of the BCS model with a central-spin-like quantum processor
• Generalising quantum imaginary time evolution to solve linear partial differential equations
• Heisenberg-limited metrology with perturbing interactions
• The dynamical $\alpha$-Rényi entropies of local Hamiltonians grow at most linearly in time
• End-to-end complexity for simulating the Schwinger model on quantum computers
• Optimal light cone for macroscopic particle transport in long-range systems: A quantum speed limit approach
• Polynomial Time Quantum Gibbs Sampling for Fermi-Hubbard Model at any Temperature
• TE-PAI: Exact Time Evolution by Sampling Random Circuits
• Quantum Simulation of the First-Quantized Pauli-Fierz Hamiltonian
• Exponential tail estimates for quantum lattice dynamics
• Tensor Network enhanced Dynamic Multiproduct Formulas
• Thermalization in open many-body systems and KMS detailed balance
• Quantum simulation of time-dependent Hamiltonians via commutator-free quasi-Magnus operators
• Recipes for the Digital Quantum Simulation of Lattice Spin Systems
• Semicoherent Symmetric Quantum Processes: Theory and Applications
• Coarse-grained effective Hamiltonian via the Magnus Expansion for a three-level system
• Phases of Matrix Product States with Symmetric Quantum Circuits and Symmetric Measurements with Feedforward
• Cost of Emulating a Small Quantum Annealing Problem in the Circuit-Model
• Enhanced Lieb-Robinson bounds for commuting long-range interactions
• State-dependent mobility edge in kinetically constrained models
• Performance and scaling analysis of variational quantum simulation
• High-precision and low-depth quantum algorithm design for eigenstate problems
• Frobenius light cone and the shift unitary
• Quantum science with arrays of metastable helium-3 atoms
• Trotter error time scaling separation via commutant decomposition
• Short-time simulation of quantum dynamics by Pauli measurements
• Lieb-Robinson bounds with exponential-in-volume tails
• On the commutator scaling in Hamiltonian simulation with multi-product formulas
• Phase Estimation with Compressed Controlled Time Evolution
• Davies equation without the secular approximation: Reconciling locality with quantum thermodynamics for open quadratic systems
• Locally accurate tensor networks for thermal states and time evolution
• Universal Decay of Mutual Information and Conditional Mutual Information in Gapped Pure- and Mixed-State Quantum Matter
• Integral fluctuation theorems and trace-preserving map
• Non-Equilibrium Quantum Many-Body Physics with Quantum Circuits
• Quantum simulation of massive Thirring and Gross--Neveu models for arbitrary number of flavors
• Tensor-based phase difference estimation on time series analysis