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.

arXiv comment24 pages, 3 figures

References in corpus (38)

• Chiral effective field theory and nuclear forces
• Many-body localization edge in the random-field Heisenberg chain
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Elucidating Reaction Mechanisms on Quantum Computers
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Universal digital quantum simulation with trapped ions
• Toward the first quantum simulation with quantum speedup
• Quantum Algorithms for Quantum Field Theories
• From Classical to Quantum Shannon Theory
• Quantum Simulation of Electronic Structure with Linear Depth and Connectivity
• Hamiltonian simulation with nearly optimal dependence on all parameters
• A random compiler for fast Hamiltonian simulation
• Digital quantum simulation of fermionic models with a superconducting circuit
• Gate count estimates for performing quantum chemistry on small quantum computers
• Simulating Large Quantum Circuits on a Small Quantum Computer
• Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
• Low Depth Quantum Simulation of Electronic Structure
• Chemical Basis of Trotter-Suzuki Errors in Quantum Chemistry Simulation
• Mapping local Hamiltonians of fermions to local Hamiltonians of spins
• Nearly optimal lattice simulation by product formulas
• The Dynamics of 1D Quantum Spin Systems Can Be Approximated Efficiently
• Higher Order Decompositions of Ordered Operator Exponentials
• Limitations of Quantum Simulation Examined by Simulating a Pairing Hamiltonian using Nuclear Magnetic Resonance
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Locality and digital quantum simulation of power-law interactions
• Mitigating algorithmic errors in Hamiltonian simulation
• Quantum-circuit design for efficient simulations of many-body quantum dynamics
• Simulating the dynamics of time-dependent Hamiltonians with a truncated Dyson series
• Locality in Quantum Systems
• Hamiltonian Simulation in the Interaction Picture
• On the simulation of quantum circuits
• A Trotter-Suzuki approximation for Lie groups with applications to Hamiltonian simulation
• Optimal Trotterization in universal quantum simulators under faulty control
• Stability of the Trotter-Suzuki decomposition
• Quantum Hamiltonian complexity and the detectability lemma
• Efficient certification and simulation of local quantum many-body Hamiltonians

Cited by in corpus (114)

• Quantum computational chemistry
• Hamiltonian Simulation by Qubitization
• 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
• Faster quantum simulation by randomization
• 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
• Hamiltonian simulation in the low-energy subspace
• Holographic quantum algorithms for simulating correlated spin systems
• Classically optimized Hamiltonian simulation
• Simulating Quantum Materials with Digital Quantum Computers
• 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
• Bounds in Nonequilibrium Quantum Dynamics
• Hamiltonian simulation with random inputs
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model
• 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
• Self-healing of Trotter error in digital adiabatic state preparation
• A single $T$-gate makes distribution learning hard
• 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 circuits for the preparation of spin eigenfunctions on quantum computers
• Quantum computation of molecular structure using data from challenging-to-classically-simulate nuclear magnetic resonance experiments
• Assessment of various Hamiltonian partitionings for the electronic structure problem on a quantum computer using the Trotter approximation
• Quantum differential equation solvers: limitations and fast-forwarding
• Double-bracket quantum algorithms for diagonalization
• Continuous Hamiltonian dynamics on digital quantum computers without discretization error
• Average-case Speedup for Product Formulas
• Efficient Quantum Simulation of QCD Jets on the Light Front
• Success of digital adiabatic simulation with large Trotter step
• Well-conditioned multiproduct Hamiltonian simulation
• Experimental Quantum Learning of a Spectral Decomposition
• Site-by-site quantum state preparation algorithm for preparing vacua of fermionic lattice field theories
• Simple and high-precision Hamiltonian simulation by compensating Trotter error with linear combination of unitary operations
• Quantifying $T$-gate-count improvements for ground-state-energy estimation with near-optimal state preparation
• Time Evolution of Uniform Sequential Circuits
• Scattering and perturbation theory for discrete-time dynamics
• Trotter error with commutator scaling for the Fermi-Hubbard model
• Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
• Accelerating Quantum Optimal Control of Multi-Qubit Systems with Symmetry-Based Hamiltonian Transformations
• Efficient and practical Hamiltonian simulation from time-dependent product formulas
• Parallel Quantum Algorithm for Hamiltonian Simulation
• Scalable simulation of non-equilibrium quantum dynamics via classically optimised unitary circuits
• Partonic distribution functions and amplitudes using tensor network methods
• Block encoding bosons by signal processing
• Polynomial Equivalence of Complexity Geometries
• End-to-end complexity for simulating the Schwinger model on quantum computers
• A Quantum Search Decoder for Natural Language Processing
• Complexity of Digital Quantum Simulation in the Low-Energy Subspace: Applications and a Lower Bound
• Double-bracket quantum algorithms for quantum imaginary-time evolution
• Exploiting anticommutation in Hamiltonian simulation
• Time-dependent Hamiltonian Simulation via Magnus Expansion: Algorithm and Superconvergence
• Lower Bounds for the Trotter Error
• Quantum Algorithm for Estimating Betti Numbers Using Cohomology Approach
• Digital Quantum Simulation, Learning of the Floquet Hamiltonian, and Quantum Chaos of the Kicked Top
• Trotterization is substantially efficient for low-energy states
• Quantum simulation of time-dependent Hamiltonians via commutator-free quasi-Magnus operators
• Uniform observable error bounds of Trotter formulae for the semiclassical Schrödinger equation
• A Partially Random Trotter Algorithm for Quantum Hamiltonian Simulations
• Quantum Phase Estimation by Compressed Sensing
• 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
• On the Trotter Error in Many-body Quantum Dynamics with Coulomb Potentials
• Faster Algorithmic Quantum and Classical Simulations by Corrected Product Formulas
• Extracting the spin excitation spectrum of a fermionic system using a quantum processor
• Investigating the Exchange of Ising Chains on a Digital Quantum Computer
• Efficient implementation of unitary transformations
• Simulating quantum field theories on gate-based quantum computers
• Trotter error and gate complexity of the SYK and sparse SYK models
• Hybrid quantum gap estimation algorithm using a filtered time series
• Trotter error time scaling separation via commutant decomposition
• Discrete Superconvergence Analysis for Quantum Magnus Algorithms of Unbounded Hamiltonian Simulation
• 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
• Quantum science with arrays of metastable helium-3 atoms
• The Complexity of Approximating Critical Points of Quantum Phase Transitions
• Noninvertible Kramers-Wannier duality symmetries for the discrete-time quantum Ising chain
• Quantum Simulation via Stochastic Combination of Unitaries
• Quantum simulation of massive Thirring and Gross--Neveu models for arbitrary number of flavors
• Error Interference in Quantum Simulation
• Perturbational Decomposition Analysis for Quantum Ising Model with Weak Transverse Fields
• Vertex Lattice Models Simulated with Quantum Circuits
• Double-bracket quantum algorithms for high-fidelity ground state preparation
• Revisiting the Effects of Stochasticity for Hamiltonian Samplers