Nearly optimal lattice simulation by product formulas

Abstract

We consider simulating an $n$-qubit Hamiltonian with nearest-neighbor interactions evolving for time $t$ on a quantum computer. We show that this simulation has gate complexity $(nt{)}^{1+o(1)}$ using product formulas, a straightforward approach that has been demonstrated by several experimental groups. While it is reasonable to expect this complexity---in particular, this was claimed without rigorous justification by Jordan, Lee, and Preskill---we are not aware of a straightforward proof. Our approach is based on an analysis of the local error structure of product formulas, as introduced by Descombes and Thalhammer and further simplified here. We prove error bounds for canonical product formulas, which include well-known constructions such as the Lie-Trotter-Suzuki formulas. We also develop a local error representation for time-dependent Hamiltonian simulation, and we discuss generalizations to periodic boundary conditions, constant-range interactions, and higher dimensions. Combined with a previous lower bound, our result implies that product formulas can simulate lattice Hamiltonians with nearly optimal gate complexity.

24 pages, 3 figures

References in corpus (14)

• Chiral effective field theory and nuclear forces
• Many-body localization edge in the random-field Heisenberg chain
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Digital quantum simulation of fermionic models with a superconducting circuit
• Simulating Large Quantum Circuits on a Small Quantum Computer
• Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
• Chemical Basis of Trotter-Suzuki Errors in Quantum Chemistry Simulation
• Nearly optimal lattice simulation by product formulas
• The Dynamics of 1D Quantum Spin Systems Can Be Approximated Efficiently
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Locality in Quantum Systems
• On the simulation of quantum circuits
• Optimal Trotterization in universal quantum simulators under faulty control
• Efficient certification and simulation of local quantum many-body Hamiltonians

Cited by in corpus (111)

• Quantum algorithms for quantum chemistry and quantum materials science
• A Theory of Trotter Error
• Quantum Simulation for High Energy Physics
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• A Trailhead for Quantum Simulation of SU(3) Yang-Mills Lattice Gauge Theory in the Local Multiplet Basis
• Real- and imaginary-time evolution with compressed quantum circuits
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Nearly optimal lattice simulation by product formulas
• Emerging quantum computing algorithms for quantum chemistry
• Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization
• Digital Quantum Simulation of the Schwinger Model and Symmetry Protection with Trapped Ions
• Time-dependent Hamiltonian simulation with $L^1$-norm scaling
• Digital Quantum Simulation, Trotter Errors, and Quantum Chaos of the Kicked Top
• Observation of separated dynamics of charge and spin in the Fermi-Hubbard model
• Quantum Computing for Molecular Biology
• Holographic quantum algorithms for simulating correlated spin systems
• Hamiltonian simulation in the low-energy subspace
• Simulating Quantum Materials with Digital Quantum Computers
• Classically optimized Hamiltonian simulation
• Provably accurate simulation of gauge theories and bosonic systems
• Hamiltonian Simulation Algorithms for Near-Term Quantum Hardware
• Time-dependent unbounded Hamiltonian simulation with vector norm scaling
• Time-marching based quantum solvers for time-dependent linear differential equations
• Nearly tight Trotterization of interacting electrons
• Simulating periodic systems on quantum computer
• General quantum algorithms for Hamiltonian simulation with applications to a non-Abelian lattice gauge theory
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model
• Hamiltonian simulation with random inputs
• Bounds in Nonequilibrium Quantum Dynamics
• First-Order Trotter Error from a Second-Order Perspective
• Randomizing multi-product formulas for Hamiltonian simulation
• Destructive Error Interference in Product-Formula Lattice Simulation
• Time-dependent Hamiltonian Simulation of Highly Oscillatory Dynamics and Superconvergence for Schrödinger Equation
• Quantum dynamics simulations beyond the coherence time on NISQ hardware by variational Trotter compression
• Quantum simulation of exact electron dynamics can be more efficient than classical mean-field methods
• Well-conditioned multi-product formulas for hardware-friendly Hamiltonian simulation
• On the complexity of implementing Trotter steps
• A single $T$-gate makes distribution learning hard
• Self-healing of Trotter error in digital adiabatic state preparation
• Efficient Product Formulas for Commutators and Applications to Quantum Simulation
• Resource estimate for quantum many-body ground-state preparation on a quantum computer
• A quantum hamiltonian simulation benchmark
• Creating and manipulating a Laughlin-type $\nu =1/3$ fractional quantum Hall state on a quantum computer with linear depth circuits
• Low-depth Hamiltonian Simulation by Adaptive Product Formula
• Entanglement accelerates quantum simulation
• Tailoring Term Truncations for Electronic Structure Calculations Using a Linear Combination of Unitaries
• Quantum computation of molecular structure using data from challenging-to-classically-simulate nuclear magnetic resonance experiments
• Quantum circuits for the preparation of spin eigenfunctions on quantum computers
• Assessment of various Hamiltonian partitionings for the electronic structure problem on a quantum computer using the Trotter approximation
• Continuous Hamiltonian dynamics on digital quantum computers without discretization error
• Average-case Speedup for Product Formulas
• Double-bracket quantum algorithms for diagonalization
• Quantum differential equation solvers: limitations and fast-forwarding
• Success of digital adiabatic simulation with large Trotter step
• Efficient Quantum Simulation of QCD Jets on the Light Front
• Well-conditioned multiproduct Hamiltonian simulation
• Quantifying $T$-gate-count improvements for ground-state-energy estimation with near-optimal state preparation
• Site-by-site quantum state preparation algorithm for preparing vacua of fermionic lattice field theories
• Scattering and perturbation theory for discrete-time dynamics
• Time Evolution of Uniform Sequential Circuits
• Simple and high-precision Hamiltonian simulation by compensating Trotter error with linear combination of unitary operations
• Experimental Quantum Learning of a Spectral Decomposition
• Trotter error with commutator scaling for the Fermi-Hubbard model
• Accelerating Quantum Optimal Control of Multi-Qubit Systems with Symmetry-Based Hamiltonian Transformations
• Parallel Quantum Algorithm for Hamiltonian Simulation
• Efficient and practical Hamiltonian simulation from time-dependent product formulas
• Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
• Partonic distribution functions and amplitudes using tensor network methods
• Scalable simulation of non-equilibrium quantum dynamics via classically optimised unitary circuits
• Exploiting anticommutation in Hamiltonian simulation
• Lower Bounds for the Trotter Error
• Double-bracket quantum algorithms for quantum imaginary-time evolution
• Complexity of Digital Quantum Simulation in the Low-Energy Subspace: Applications and a Lower Bound
• Polynomial Equivalence of Complexity Geometries
• End-to-end complexity for simulating the Schwinger model on quantum computers
• Time-dependent Hamiltonian Simulation via Magnus Expansion: Algorithm and Superconvergence
• A Quantum Search Decoder for Natural Language Processing
• Block encoding bosons by signal processing
• Quantum simulation of time-dependent Hamiltonians via commutator-free quasi-Magnus operators
• Digital Quantum Simulation, Learning of the Floquet Hamiltonian, and Quantum Chaos of the Kicked Top
• Quantum Algorithm for Estimating Betti Numbers Using Cohomology Approach
• Uniform observable error bounds of Trotter formulae for the semiclassical Schrödinger equation
• Trotterization is substantially efficient for low-energy states
• Quantum Phase Estimation by Compressed Sensing
• A Partially Random Trotter Algorithm for Quantum Hamiltonian Simulations
• Sequency Hierarchy Truncation (SeqHT) for Adiabatic State Preparation and Time Evolution in Quantum Simulations
• Some Error Analysis for the Quantum Phase Estimation Algorithms
• Double-bracket algorithm for quantum signal processing without post-selection
• Efficient implementation of unitary transformations
• Faster Algorithmic Quantum and Classical Simulations by Corrected Product Formulas
• Extracting the spin excitation spectrum of a fermionic system using a quantum processor
• Simulating quantum field theories on gate-based quantum computers
• On the Trotter Error in Many-body Quantum Dynamics with Coulomb Potentials
• Investigating the Exchange of Ising Chains on a Digital Quantum Computer
• Quantum science with arrays of metastable helium-3 atoms
• Hybrid quantum gap estimation algorithm using a filtered time series
• Discrete Superconvergence Analysis for Quantum Magnus Algorithms of Unbounded Hamiltonian Simulation
• Trotter error and gate complexity of the SYK and sparse SYK models
• Prethermalization, shadowing breakdown, and the absence of Trotterization transition in quantum circuits
• On the commutator scaling in Hamiltonian simulation with multi-product formulas
• Phase Estimation with Compressed Controlled Time Evolution
• Trotter error time scaling separation via commutant decomposition
• The Complexity of Approximating Critical Points of Quantum Phase Transitions
• Quantum Simulation via Stochastic Combination of Unitaries
• Noninvertible Kramers-Wannier duality symmetries for the discrete-time quantum Ising chain
• Perturbational Decomposition Analysis for Quantum Ising Model with Weak Transverse Fields
• Quantum simulation of massive Thirring and Gross--Neveu models for arbitrary number of flavors
• Revisiting the Effects of Stochasticity for Hamiltonian Samplers
• Error Interference in Quantum Simulation
• Vertex Lattice Models Simulated with Quantum Circuits
• Double-bracket quantum algorithms for high-fidelity ground state preparation