Hamiltonian simulation with nearly optimal dependence on all parameters

Abstract

We present an algorithm for sparse Hamiltonian simulation whose complexity is optimal (up to log factors) as a function of all parameters of interest. Previous algorithms had optimal or near-optimal scaling in some parameters at the cost of poor scaling in others. Hamiltonian simulation via a quantum walk has optimal dependence on the sparsity at the expense of poor scaling in the allowed error. In contrast, an approach based on fractional-query simulation provides optimal scaling in the error at the expense of poor scaling in the sparsity. Here we combine the two approaches, achieving the best features of both. By implementing a linear combination of quantum walk steps with coefficients given by Bessel functions, our algorithm's complexity (as measured by the number of queries and 2-qubit gates) is logarithmic in the inverse error, and nearly linear in the product $\tau$ of the evolution time, the sparsity, and the magnitude of the largest entry of the Hamiltonian. Our dependence on the error is optimal, and we prove a new lower bound showing that no algorithm can have sublinear dependence on $\tau$.

21 pages, corrects minor error in Lemma 7 in FOCS version

References in corpus (7)

• Quantum algorithm for solving linear systems of equations
• Exponential algorithmic speedup by quantum walk
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Synthesis of Quantum Logic Circuits
• Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
• A Quantum Algorithm for the Hamiltonian NAND Tree
• Symmetry-assisted adversaries for quantum state generation

Cited by in corpus (198)

• Quantum computational chemistry
• Quantum Chemistry in the Age of Quantum Computing
• Quantum algorithms: an overview
• Hamiltonian Simulation by Qubitization
• Quantum algorithms for quantum chemistry and quantum materials science
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Toward the first quantum simulation with quantum speedup
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• A Theory of Trotter Error
• Quantum speedup of Monte Carlo methods
• Variational Quantum Linear Solver
• Quantum algorithms and the finite element method
• 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
• Standard Model Physics and the Digital Quantum Revolution: Thoughts about the Interface
• Near-optimal ground state preparation
• Faster quantum simulation by randomization
• Quantum Algorithm for Simulating the Wave Equation
• Efficient phase-factor evaluation in quantum signal processing
• Quantum algorithm for simulating real time evolution of lattice Hamiltonians
• Noisy intermediate-scale quantum computers
• Applications of Near-Term Photonic Quantum Computers: Software and Algorithms
• Quantum Complexity of Time Evolution with Chaotic Hamiltonians
• Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
• Black-box quantum state preparation without arithmetic
• Quantum Simulation of Quantum Field Theory in the Light-Front Formulation
• Time-dependent Hamiltonian simulation with $L^1$-norm scaling
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• Lowering qubit requirements for quantum simulations of fermionic systems
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Linear Response on a Quantum Computer
• Digital Quantum Simulation, Trotter Errors, and Quantum Chaos of the Kicked Top
• Universal Quantum Hamiltonians
• Biology and medicine in the landscape of quantum advantages
• Quantum SDP-Solvers: Better upper and lower bounds
• Hamiltonian Simulation with Optimal Sample Complexity
• Quantum algorithm for association rules mining
• Quantum algorithm for association rules mining
• Product Decomposition of Periodic Functions in Quantum Signal Processing
• Linear combination of Hamiltonian simulation for nonunitary dynamics with optimal state preparation cost
• Quantum algorithm for calculating molecular vibronic spectra
• Quantum Simulation of the Sachdev-Ye-Kitaev Model by Asymmetric Qubitization
• Concrete resource analysis of the quantum linear system algorithm used to compute the electromagnetic scattering cross section of a 2D target
• Concentration for random product formulas
• Hamiltonian Simulation Algorithms for Near-Term Quantum Hardware
• Simulating the dynamics of time-dependent Hamiltonians with a truncated Dyson series
• Time-dependent unbounded Hamiltonian simulation with vector norm scaling
• Time-marching based quantum solvers for time-dependent linear differential equations
• Bayesian Deep Learning on a Quantum Computer
• Quantum linear systems algorithms: a primer
• Nearly tight Trotterization of interacting electrons
• Quantum Algorithms for Estimating Physical Quantities using Block-Encodings
• Simulating Hadronic Physics on NISQ devices using Basis Light-Front Quantization
• Review on Quantum Walk Computing: Theory, Implementation, and Application
• Centrality measure based on continuous-time quantum walks and experimental realization
• Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation
• Experimental quantum processing enhancement in modelling stochastic processes
• Practical Quantum Computing: solving the wave equation using a quantum approach
• Block-encoding structured matrices for data input in quantum computing
• Hybrid quantum algorithms for flow problems
• Fast-forwarding quantum evolution
• Hamiltonian Simulation by Uniform Spectral Amplification
• Machine learning \& artificial intelligence in the quantum domain
• Variational quantum eigensolvers for sparse Hamiltonians
• Quantum phase estimation for a class of generalized eigenvalue problems
• First-Order Trotter Error from a Second-Order Perspective
• Randomizing multi-product formulas for Hamiltonian simulation
• Time-dependent Hamiltonian Simulation of Highly Oscillatory Dynamics and Superconvergence for Schrödinger Equation
• Finding Angles for Quantum Signal Processing with Machine Precision
• Quantum Computing for Fusion Energy Science Applications
• Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits
• FABLE: Fast Approximate Quantum Circuits for Block-Encodings
• Random circuit block-encoded matrix and a proposal of quantum LINPACK benchmark
• Approximate Quantum Circuit Synthesis using Block-Encodings
• Quantum Computing: Lecture Notes
• New Quantum Algorithms for Computing Quantum Entropies and Distances
• Efficient quantum circuits for Szegedy quantum walks
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Quantum processing by remote quantum control
• Symmetry breaking/symmetry preserving circuits and symmetry restoration on quantum computers: A quantum many-body perspective
• Combinatorial Optimization on Gate Model Quantum Computers: A Survey
• Efficient Quantum Algorithms for Simulating Lindblad Evolution
• Superdiffusive quantum stochastic walk definable of arbitrary directed graph
• Efficient simulation of sparse Markovian quantum dynamics
• An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian Simulation
• Fast Black-Box Quantum State Preparation
• State preparation and measurement in a quantum simulation of the O(3) sigma model
• Hybrid Oscillator-Qubit Quantum Processors: Instruction Set Architectures, Abstract Machine Models, and Applications
• Quantum Circuits for partial differential equations via Schrödingerisation
• Toward simulating Superstring/M-theory on a quantum computer
• Fragmented imaginary-time evolution for early-stage quantum signal processors
• A quantum hamiltonian simulation benchmark
• Quantum Speed-ups for Semidefinite Programming
• Composite Quantum Simulations
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• Wave Matrix Lindbladization I: Quantum Programs for Simulating Markovian Dynamics
• Efficient quantum circuits for continuous-time quantum walks on composite graphs
• Simulating nonnative cubic interactions on noisy quantum machines
• Tailoring Term Truncations for Electronic Structure Calculations Using a Linear Combination of Unitaries
• Quantum Simulation of Second-Quantized Hamiltonians in Compact Encoding
• Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications
• Quantum Gradient Algorithm for General Polynomials
• Quantum differential equation solvers: limitations and fast-forwarding
• Holographic fluctuations and the principle of minimal complexity
• Pauli path simulations of noisy quantum circuits beyond average case
• Analysis of quantum Krylov algorithms with errors
• Quantum Gaussian filter for exploring ground-state properties
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• QED driven QAOA for network-flow optimization
• Optimal Hamiltonian simulation for time-periodic systems
• Complexity of Supersymmetric Systems and the Cohomology Problem
• Effects of Cosine Tapering Window on Quantum Phase Estimation
• Well-conditioned multiproduct Hamiltonian simulation
• Quantum Error Correction from Complexity in Brownian SYK
• Simple and high-precision Hamiltonian simulation by compensating Trotter error with linear combination of unitary operations
• Classical and Quantum Algorithms for Tensor Principal Component Analysis
• Quantum Merlin Arthur with Exponentially Small Gap
• Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis
• Quantum algorithms for escaping from saddle points
• Implementing smooth functions of a Hermitian matrix on a quantum computer
• Classical-Quantum Noise Mitigation for NISQ Hardware
• Parallel Quantum Algorithm for Hamiltonian Simulation
• Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
• Review of a Quantum Algorithm for Betti Numbers
• Tight Bound for Estimating Expectation Values from a System of Linear Equations
• Duality in Quantum Quenches and Classical Approximation Algorithms: Pretty Good or Very Bad
• A quantum algorithm for simulating non-sparse Hamiltonians
• Fast quantum simulation of electronic structure by spectrum amplification
• Improved amplitude amplification strategies for the quantum simulation of classical transport problems
• Selection and improvement of product formulae for best performance of quantum simulation
• Quantum simulation of discrete linear dynamical systems and simple iterative methods in linear algebra via Schrodingerisation
• An Improved Method for Quantum Matrix Multiplication
• Quantum Finite Volume Method for Computational Fluid Dynamics with Classical Input and Output
• Succinct Description and Efficient Simulation of Non-Markovian Open Quantum Systems
• Quantum Algorithms for Boolean Equation Solving and Quantum Algebraic Attack on Cryptosystems
• Graph Optimization Perspective for Low-Depth Trotter-Suzuki Decomposition
• Generalising quantum imaginary time evolution to solve linear partial differential equations
• Halving the Cost of Quantum Algorithms with Randomization
• Quantum advantage from energy measurements of many-body quantum systems
• Polynomial Equivalence of Complexity Geometries
• Time-dependent Hamiltonian Simulation via Magnus Expansion: Algorithm and Superconvergence
• Compressed variational quantum eigensolver for the Fermi-Hubbard model
• Quantum algorithms for powering stable Hermitian matrices
• Translationally-Invariant Universal Quantum Hamiltonians in 1D
• Lower bound for simulation cost of open quantum systems: Lipschitz continuity approach
• Approximating Hamiltonian dynamics with the Nyström method
• Molecular Properties from Quantum Krylov Subspace Diagonalization
• Quantum Algorithm for Estimating Betti Numbers Using Cohomology Approach
• On estimating the entropy of shallow circuit outputs
• Toward simulating quantum field theories with controlled phonon-ion dynamics: A hybrid analog-digital approach
• Modular quantum signal processing in many variables
• Going Beyond Gadgets: The Importance of Scalability for Analogue Quantum Simulators
• On the equivalence between quantum and random walks on finite graphs
• Ladder Operator Block-Encoding
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra
• Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation
• Empirical determination of the simulation capacity of a near-term quantum computer
• Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs
• Digital simulation of convex mixtures of Markovian and non-Markovian single qubit Pauli channels on NISQ devices
• The Short Path Algorithm Applied to a Toy Model
• Choco-Q: Commute Hamiltonian-based QAOA for Constrained Binary Optimization
• Quantum Simulation of Nonlinear Dynamical Systems Using Repeated Measurement
• Heisenberg-limited adaptive gradient estimation for multiple observables
• Some Error Analysis for the Quantum Phase Estimation Algorithms
• Quantum simulation of quantum mechanical system with spatial noncommutativity
• Digital Simulation of Single Qubit Markovian Open Quantum Systems: A Tutorial
• Resource-Dependent Complexity of Quantum Channels
• Security of quantum position-verification limits Hamiltonian simulation via holography
• Quantum Realization of the Finite Element Method
• Quantum and classical algorithms for nonlinear unitary dynamics
• Quantum Calculation for Two-Stream Instability and Advection Test of Vlasov-Maxwell Equations: Numerical Evaluation of Hamiltonian Simulation
• Parallel Quantum Signal Processing Via Polynomial Factorization
• Quantum implementation of non-unitary operations with biorthogonal representations
• A quantum algorithm for linear autonomous differential equations via Padé approximation
• Universal Hamiltonians for Exponentially Long Simulation
• Efficient quantum circuits for dense and non-unitary operators
• Quantum algorithms based on quantum trajectories
• Quantum Machine Learning For Classical Data
• Implications of Quantum Computing for Artificial Intelligence alignment research
• Quantum amplitude damping for solving homogeneous linear differential equations: A noninterferometric algorithm
• Fast algorithm for quantum polar decomposition, pretty-good measurements, and the Procrustes problem
• Improving quantum linear system solvers via a gradient descent perspective
• Benchmarking Quantum Simulators
• An adversary bound for quantum signal processing
• Quantum memory assisted observable estimation
• Quantum Heaviside Eigen Solver
• Quantum Algorithm for a Convergent Series of Approximations towards the Exact Solution of the Lowest Eigenstates of a Hamiltonian
• Quantum Money from Quaternion Algebras
• Quantum Merlin-Arthur proof systems for synthesizing quantum states
• Extremal jumps of circuit complexity of unitary evolutions generated by random Hamiltonians
• Quantum Algorithm to Cubic Spline Interpolation
• Quantum Algorithm For Solving Nonlinear Algebraic Equations
• Unitarization Through Approximate Basis