Time-dependent Hamiltonian simulation with $L^1$-norm scaling

Abstract

The difficulty of simulating quantum dynamics depends on the norm of the Hamiltonian. When the Hamiltonian varies with time, the simulation complexity should only depend on this quantity instantaneously. We develop quantum simulation algorithms that exploit this intuition. For sparse Hamiltonian simulation, the gate complexity scales with the $L^1$ norm ${\int }_0^t\mathrm{d}\tau {\Vert H(\tau )\Vert }_{\max }$, whereas the best previous results scale with $t{\max }_{\tau \in [0,t]}{\Vert H(\tau )\Vert }_{\max }$. We also show analogous results for Hamiltonians that are linear combinations of unitaries. Our approaches thus provide an improvement over previous simulation algorithms that can be substantial when the Hamiltonian varies significantly. We introduce two new techniques: a classical sampler of time-dependent Hamiltonians and a rescaling principle for the Schrödinger equation. The rescaled Dyson-series algorithm is nearly optimal with respect to all parameters of interest, whereas the sampling-based approach is easier to realize for near-term simulation. These algorithms could potentially be applied to semi-classical simulations of scattering processes in quantum chemistry.

40 pages, 1 figure

References in corpus (30)

• Quantum algorithm for solving linear systems of equations
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Quantum computational chemistry
• Quantum Chemistry in the Age of Quantum Computing
• Hamiltonian Simulation by Qubitization
• Exponential algorithmic speedup by quantum walk
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Toward the first quantum simulation with quantum speedup
• Quantum Algorithms for Quantum Field Theories
• From Classical to Quantum Shannon Theory
• Simulation of Electronic Structure Hamiltonians Using Quantum Computers
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• Hamiltonian simulation with nearly optimal dependence on all parameters
• A random compiler for fast Hamiltonian simulation
• Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
• Low Depth Quantum Simulation of Electronic Structure
• Exponential improvement in precision for simulating sparse Hamiltonians
• Quantum algorithm for linear differential equations with exponentially improved dependence on precision
• Optimal adaptive control for quantum metrology with time-dependent Hamiltonians
• Nearly optimal lattice simulation by product formulas
• Faster quantum simulation by randomization
• Higher Order Decompositions of Ordered Operator Exponentials
• Optimal control, geometry, and quantum computing
• Preparing ground states of quantum many-body systems on a quantum computer
• Locality and digital quantum simulation of power-law interactions
• Simulating the dynamics of time-dependent Hamiltonians with a truncated Dyson series
• Compilation by stochastic Hamiltonian sparsification
• Hamiltonian simulation with nearly optimal dependence on spectral norm

Cited by in corpus (72)

• A Theory of Trotter Error
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Standard Model Physics and the Digital Quantum Revolution: Thoughts about the Interface
• Faster quantum simulation by randomization
• Quantum Algorithms for Simulating the Lattice Schwinger Model
• Quantum Simulation of Quantum Field Theory in the Light-Front Formulation
• Quantum simulation of partial differential equations via Schrodingerisation: technical details
• Learning many-body Hamiltonians with Heisenberg-limited scaling
• Concentration for random product formulas
• Time-dependent unbounded Hamiltonian simulation with vector norm scaling
• Time-marching based quantum solvers for time-dependent linear differential equations
• Quantum Algorithms for Estimating Physical Quantities using Block-Encodings
• Subspace Variational Quantum Simulator
• Compilation by stochastic Hamiltonian sparsification
• Hybridized Methods for Quantum Simulation in the Interaction Picture
• Reducing molecular electronic Hamiltonian simulation cost for Linear Combination of Unitaries approaches
• Fast-forwarding quantum evolution
• Variational quantum eigensolvers for sparse Hamiltonians
• Time-dependent Hamiltonian Simulation of Highly Oscillatory Dynamics and Superconvergence for Schrödinger Equation
• Miniaturizing transmon qubits using van der Waals materials
• Well-conditioned multi-product formulas for hardware-friendly Hamiltonian simulation
• Quantum algorithm for time-dependent Hamiltonian simulation by permutation expansion
• Digitized Adiabatic Quantum Factorization
• Quantum simulation of real-space dynamics
• Quantum Circuits for partial differential equations via Schrödingerisation
• Nearly-optimal state preparation for quantum simulations of lattice gauge theories
• Second-quantized fermionic operators with polylogarithmic qubit and gate complexity
• Low-depth Hamiltonian Simulation by Adaptive Product Formula
• Composite Quantum Simulations
• Exponential improvements in the simulation of lattice gauge theories using near-optimal techniques
• Efficient Hamiltonian Simulation for Solving Option Price Dynamics
• Efficient quantum imaginary time evolution by drifting real time evolution: an approach with low gate and measurement complexity
• Importance sampling for stochastic quantum simulations
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Quantum Simulation of Second-Quantized Hamiltonians in Compact Encoding
• Compact quantum algorithms for time-dependent differential equations
• Analysis of quantum Krylov algorithms with errors
• Continuous Hamiltonian dynamics on digital quantum computers without discretization error
• Optimal Hamiltonian simulation for time-periodic systems
• Efficient and precise quantum simulation of ultra-relativistic quark-nucleus scattering
• Efficient Quantum Simulation of QCD Jets on the Light Front
• Quantum Langevin Dynamics for Optimization
• Quantum Error Correction from Complexity in Brownian SYK
• Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
• Parallel Quantum Algorithm for Hamiltonian Simulation
• Calculating the many-body density of states on a digital quantum computer
• Quantum simulation for time-dependent Hamiltonians -- with applications to non-autonomous ordinary and partial differential equations
• Multi-nucleon structure and dynamics via quantum computing
• Practicality of quantum adiabatic algorithm for chemistry applications
• A Comprehensive Cross-Model Framework for Benchmarking the Performance of Quantum Hamiltonian Simulations
• Time-dependent Hamiltonian Simulation via Magnus Expansion: Algorithm and Superconvergence
• TE-PAI: Exact Time Evolution by Sampling Random Circuits
• Statistics of topological defects across a phase transition in a digital superconducting quantum processor
• Quantum simulation of time-dependent Hamiltonians via commutator-free quasi-Magnus operators
• Solvent distribution effects on quantum chemical calculations with quantum computers
• Coarse-grained effective Hamiltonian via the Magnus Expansion for a three-level system
• Some Error Analysis for the Quantum Phase Estimation Algorithms
• Quantum eigenvalue processing
• Systematic many-fermion Hamiltonian input scheme and spectral calculations on quantum computers
• Cost of Emulating a Small Quantum Annealing Problem in the Circuit-Model
• Digital simulation of convex mixtures of Markovian and non-Markovian single qubit Pauli channels on NISQ devices
• Unifying framework for quantum simulation algorithms for time-dependent Hamiltonian dynamics
• Expanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding
• Unstructured Adiabatic Quantum Optimization: Optimality with Limitations
• Digital Simulation of Single Qubit Markovian Open Quantum Systems: A Tutorial
• On the Trotter Error in Many-body Quantum Dynamics with Coulomb Potentials
• Simulating quantum collision models with Hamiltonian simulations using early fault-tolerant quantum computers
• Blockwise Optimization for Projective Variational Quantum Dynamics (BLOP-VQD): Algorithm and Implementation for Lattice Systems
• Benchmarking a heuristic Floquet adiabatic algorithm for the Max-Cut problem
• Discrete Superconvergence Analysis for Quantum Magnus Algorithms of Unbounded Hamiltonian Simulation
• Improved Strategies for Fermionic Quantum Simulation with Global Interactions