On the complexity of implementing Trotter steps

Abstract

Quantum dynamics can be simulated on a quantum computer by exponentiating elementary terms from the Hamiltonian in a sequential manner. However, such an implementation of Trotter steps has gate complexity depending on the total Hamiltonian term number, comparing unfavorably to algorithms using more advanced techniques. We develop methods to perform faster Trotter steps with complexity sublinear in the number of terms. We achieve this for a class of Hamiltonians whose interaction strength decays with distance according to power law. Our methods include one based on a recursive block encoding and one based on an average-cost simulation, overcoming the normalization-factor barrier of these advanced quantum simulation techniques. We also realize faster Trotter steps when certain blocks of Hamiltonian coefficients have low rank. Combining with a tighter error analysis, we show that it suffices to use $\left({\eta }^{1/3}{n}^{1/3}+\frac{n^{2/3}}{{\eta }^{2/3}}\right)n^{1+o(1)}$ gates to simulate uniform electron gas with $n$ spin orbitals and $\eta$ electrons in second quantization in real space, asymptotically improving over the best previous work. We obtain an analogous result when the external potential of nuclei is introduced under the Born-Oppenheimer approximation. We prove a circuit lower bound when the Hamiltonian coefficients take a continuum range of values, showing that generic $n$-qubit $2$-local Hamiltonians with commuting terms require at least $\Omega (n^2)$ gates to evolve with accuracy $\epsilon =\Omega (1/poly(n))$ for time $t=\Omega (\epsilon )$. Our proof is based on a gate-efficient reduction from the approximate synthesis of diagonal unitaries within the Hamming weight-$2$ subspace, which may be of independent interest. Our result thus suggests the use of Hamiltonian structural properties as both necessary and sufficient to implement Trotter steps with lower gate complexity.

arXiv comment69 pages, 7 figures. Tightened gate complexity analysis with no amplitude amplification prefactors. Discussed ancilla space complexity. Added master theorem analysis of the recursive low-rank algorithm. Enhanced version of the article published in PRX Quantum at https://journals.aps.org/prxquantum/abstract/10.1103/PRXQuantum.4.020323

References in corpus (69)

• Quantum algorithm for solving linear systems of equations
• Quantum information with Rydberg atoms
• Quantum computational chemistry
• Quantum Chemistry in the Age of Quantum Computing
• Engineered 2D Ising interactions on a trapped-ion quantum simulator with hundreds of spins
• Realizing a lattice spin model with polar molecules
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Synthesis of Quantum Logic Circuits
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Toward the first quantum simulation with quantum speedup
• Quantum many-body models with cold atoms coupled to photonic crystals
• Strongly correlated 2D quantum phases with cold polar molecules: controlling the shape of the interaction potential
• A Theory of Trotter Error
• Quantum Simulation of Electronic Structure with Linear Depth and Connectivity
• Polynomial-time quantum algorithm for the simulation of chemical dynamics
• A random compiler for fast Hamiltonian simulation
• A Grand Unification of Quantum Algorithms
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Entanglement entropy for the long range Ising chain
• Low Depth Quantum Simulation of Electronic Structure
• Quantum computing enhanced computational catalysis
• A Quantum Computing View on Unitary Coupled Cluster Theory
• Cold polar molecules in 2D traps: Tailoring interactions with external fields for novel quantum phases
• Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
• Mapping local Hamiltonians of fermions to local Hamiltonians of spins
• 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
• Near-optimal ground state preparation
• Low rank representations for quantum simulation of electronic structure
• Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization
• Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices
• Simulating chemistry efficiently on fault-tolerant quantum computers
• Quantum Algorithms for Simulating the Lattice Schwinger Model
• Efficient synthesis of universal Repeat-Until-Success circuits
• Improved Techniques for Preparing Eigenstates of Fermionic Hamiltonians
• Quantum localization bounds Trotter errors in digital quantum simulation
• Repulsive shield between polar molecules
• Fault-Tolerant Quantum Simulations of Chemistry in First Quantization
• Preparing ground states of quantum many-body systems on a quantum computer
• Efficient Quantum Circuits for Diagonal Unitaries Without Ancillas
• Quantum Algorithm for Spectral Measurement with Lower Gate Count
• Quantum Simulation of Chemistry with Sublinear Scaling in Basis Size
• Nearly Optimal Measurement Scheduling for Partial Tomography of Quantum States
• A randomized quantum algorithm for statistical phase estimation
• Hamiltonian simulation in the low-energy subspace
• Fast-forwarding of Hamiltonians and Exponentially Precise Measurements
• On the representation of Boolean and real functions as Hamiltonians for quantum computing
• Locality and digital quantum simulation of power-law interactions
• Quantum Simulation of the Sachdev-Ye-Kitaev Model by Asymmetric Qubitization
• Provably accurate simulation of gauge theories and bosonic systems
• 1D Quantum Liquids with Power-Law Interactions: a Luttinger Staircase with Polar Molecules
• Concentration for random product formulas
• Time-dependent unbounded Hamiltonian simulation with vector norm scaling
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition
• Improved thermal area law and quasi-linear time algorithm for quantum Gibbs states
• Bounding the costs of quantum simulation of many-body physics in real space
• Nearly tight Trotterization of interacting electrons
• Hybridized Methods for Quantum Simulation in the Interaction Picture
• Algebraic Compression of Quantum Circuits for Hamiltonian Evolution
• Fast-forwarding quantum evolution
• First-Order Trotter Error from a Second-Order Perspective
• Universal algebraic growth of entanglement entropy in many-body localized systems with power-law interactions
• Tailoring Term Truncations for Electronic Structure Calculations Using a Linear Combination of Unitaries
• State-dependent error bound for digital quantum simulation of driven systems
• Exploiting anticommutation in Hamiltonian simulation
• Quantum simulation by qubitization without Toffoli gates

Cited by in corpus (19)

• Quantum simulation of exact electron dynamics can be more efficient than classical mean-field methods
• Quantum computation of stopping power for inertial fusion target design
• Improved Accuracy for Trotter Simulations Using Chebyshev Interpolation
• HamLib: A library of Hamiltonians for benchmarking quantum algorithms and hardware
• Continuous Hamiltonian dynamics on digital quantum computers without discretization error
• Parallel Quantum Algorithm for Hamiltonian Simulation
• Selection and improvement of product formulae for best performance of quantum simulation
• Time-dependent Hamiltonian Simulation via Magnus Expansion: Algorithm and Superconvergence
• Lower Bounds for the Trotter Error
• A Comprehensive Cross-Model Framework for Benchmarking the Performance of Quantum Hamiltonian Simulations
• Quantum Dynamics Simulation of the Advection-Diffusion Equation
• Matrix product state ansatz for the variational quantum solution of the Heisenberg model on Kagome geometries
• Quantum Simulation of the First-Quantized Pauli-Fierz Hamiltonian
• Scalable Quantum Computational Science: A Perspective from Block-Encodings and Polynomial Transformations
• Phase estimation with partially randomized time evolution
• Quantum Computing Beyond Ground State Electronic Structure: A Review of Progress Toward Quantum Chemistry Out of the Ground State
• Discrete Superconvergence Analysis for Quantum Magnus Algorithms of Unbounded Hamiltonian Simulation
• Dissipative ground state preparation in ab initio electronic structure theory
• Benchmarking Quantum Simulation of Chemical Hamiltonians using the Sorted-List Encoding