Exponential improvement in precision for simulating sparse Hamiltonians

Abstract

We provide a quantum algorithm for simulating the dynamics of sparse Hamiltonians with complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Specifically, we show that a $d$-sparse Hamiltonian $H$ acting on $n$ qubits can be simulated for time $t$ with precision $\epsilon$ using $O\left(\tau \frac{\log (\tau /\epsilon )}{\log \log (\tau /\epsilon )}\right)$ queries and $O\left(\tau \frac{{\log }^2(\tau /\epsilon )}{\log \log (\tau /\epsilon )}n\right)$ additional 2-qubit gates, where $\tau =d^2\Vert H{\Vert }_{\max }t$. Unlike previous approaches based on product formulas, the query complexity is independent of the number of qubits acted on, and for time-varying Hamiltonians, the gate complexity is logarithmic in the norm of the derivative of the Hamiltonian. Our algorithm is based on a significantly improved simulation of the continuous- and fractional-query models using discrete quantum queries, showing that the former models are not much more powerful than the discrete model even for very small error. We also simplify the analysis of this conversion, avoiding the need for a complex fault correction procedure. Our simplification relies on a new form of "oblivious amplitude amplification" that can be applied even though the reflection about the input state is unavailable. Finally, we prove new lower bounds showing that our algorithms are optimal as a function of the error.

v1: 27 pages; Subsumes and improves upon results in arXiv:1308.5424. v2: 28 pages, minor changes

References in corpus (8)

• Quantum algorithm for solving linear systems of equations
• Exponential algorithmic speedup by quantum walk
• Preconditioned quantum linear system algorithm
• Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
• Exponential improvement in precision for simulating sparse Hamiltonians
• Hamiltonian Oracles
• Efficient discrete-time simulations of continuous-time quantum query algorithms
• Symmetry-assisted adversaries for quantum state generation

Cited by in corpus (116)

• Quantum computational chemistry
• Quantum Chemistry in the Age of Quantum Computing
• Hamiltonian Simulation by Qubitization
• Quantum algorithms for quantum chemistry and quantum materials science
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• A Theory of Trotter Error
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
• Exponential improvement in precision for simulating sparse Hamiltonians
• Emerging quantum computing algorithms for quantum chemistry
• Faster quantum simulation by randomization
• High-precision quantum algorithms for partial differential equations
• Improved Techniques for Preparing Eigenstates of Fermionic Hamiltonians
• Exponentially more precise quantum simulation of fermions I: Quantum chemistry in second quantization
• Time-dependent Hamiltonian simulation with $L^1$-norm scaling
• Quantum Simulation of Chemistry with Sublinear Scaling in Basis Size
• Hamiltonian simulation in the low-energy subspace
• Fast-forwarding of Hamiltonians and Exponentially Precise Measurements
• Exponentially More Precise Quantum Simulation of Fermions in the Configuration Interaction Representation
• Product Decomposition of Periodic Functions in Quantum Signal Processing
• Quantum algorithm for calculating molecular vibronic spectra
• Provably accurate simulation of gauge theories and bosonic systems
• Concrete resource analysis of the quantum linear system algorithm used to compute the electromagnetic scattering cross section of a 2D target
• Single-particle digitization strategy for quantum computation of a ${\varphi }^4$ scalar field theory
• The ghost in the radiation: Robust encodings of the black hole interior
• Time-dependent unbounded Hamiltonian simulation with vector norm scaling
• Time-marching based quantum solvers for time-dependent linear differential equations
• 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
• Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation
• Variational quantum simulations of stochastic differential equations
• Fast-forwarding quantum evolution
• Hybrid quantum algorithms for flow problems
• Probabilistic Nonunitary Gate in Imaginary Time Evolution
• Hunting for quantum-classical crossover in condensed matter problems
• Randomizing multi-product formulas for Hamiltonian simulation
• Quantum Bootstrapping via Compressed Quantum Hamiltonian Learning
• Time-dependent Hamiltonian Simulation of Highly Oscillatory Dynamics and Superconvergence for Schrödinger Equation
• Quantum Computing for Fusion Energy Science Applications
• A Trotter-Suzuki approximation for Lie groups with applications to Hamiltonian simulation
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Quantum algorithm for time-dependent Hamiltonian simulation by permutation expansion
• Symmetry breaking/symmetry preserving circuits and symmetry restoration on quantum computers: A quantum many-body perspective
• Efficient quantum Gibbs samplers with Kubo--Martin--Schwinger detailed balance condition
• Optimal large-scale quantum state tomography with Pauli measurements
• Quantum algorithms from fluctuation theorems: Thermal-state preparation
• Quantum Genetic Algorithm with Individuals in Multiple Registers
• Quantum Circuits for partial differential equations via Schrödingerisation
• Fragmented imaginary-time evolution for early-stage quantum signal processors
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• Fast Quantum Methods for Optimization
• Bootstrap Embedding on a Quantum Computer
• Tailoring Term Truncations for Electronic Structure Calculations Using a Linear Combination of Unitaries
• Circuit complexity of quantum access models for encoding classical data
• Simulating fluid flows with quantum computing
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Magic State Distillation and Gate Compilation in Quantum Algorithms for Quantum Chemistry
• Variational quantum algorithms for Poisson equations based on the decomposition of sparse Hamiltonians
• Continuous Hamiltonian dynamics on digital quantum computers without discretization error
• Analysis of quantum Krylov algorithms with errors
• Efficient and precise quantum simulation of ultra-relativistic quark-nucleus scattering
• An Ancilla Based Quantum Simulation Framework for Non-Unitary Matrices
• Direct Application of the Phase Estimation Algorithm to Find the Eigenvalues of the Hamiltonians
• Hamiltonian simulation for low-energy states with optimal time dependence
• Classical and Quantum Algorithms for Tensor Principal Component Analysis
• Efficient quantum circuits for Toeplitz and Hankel matrices
• Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
• Parallel Quantum Algorithm for Hamiltonian Simulation
• 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
• Selection and improvement of product formulae for best performance of quantum simulation
• A quantum algorithm for track reconstruction in the LHCb vertex detector
• Succinct Description and Efficient Simulation of Non-Markovian Open Quantum Systems
• How Quantum is the Speedup in Adiabatic Unstructured Search?
• End-to-end complexity for simulating the Schwinger model on quantum computers
• Exploiting anticommutation in Hamiltonian simulation
• Quantum and classical query complexities of functions of matrices
• Complexity of Digital Quantum Simulation in the Low-Energy Subspace: Applications and a Lower Bound
• Polynomial Equivalence of Complexity Geometries
• Halving the Cost of Quantum Algorithms with Randomization
• A Quantum Search Decoder for Natural Language Processing
• TE-PAI: Exact Time Evolution by Sampling Random Circuits
• Simulating nonlinear optical processes on a superconducting quantum device
• Lower bound for simulation cost of open quantum systems: Lipschitz continuity approach
• Quantum Algorithms for the Pathwise Lasso
• Fault-tolerant simulation of Lattice Gauge Theories with gauge covariant codes
• Identifying Bottlenecks of NISQ-friendly HHL algorithms
• Quantum simulation of time-dependent Hamiltonians via commutator-free quasi-Magnus operators
• Review of Quantum Algorithms for Systems of Linear Equations
• Eliminating Intermediate Measurements in Space-Bounded Quantum Computation
• Dictionary-based Block Encoding of Sparse Matrices with Low Subnormalization and Circuit Depth
• Full-Dimensional Schrödinger Wavefunction Calculations using Tensors and Quantum Computers: the Cartesian component-separated approach
• Quantum Simulation of Nonlinear Dynamical Systems Using Repeated Measurement
• The Short Path Algorithm Applied to a Toy Model
• Quantum eigenvalue processing
• Hybrid Quantum-Classical Algorithm For Robust Optimization via Stochastic-Gradient Online Learning
• Double-bracket algorithm for quantum signal processing without post-selection
• Convergence Rates for the Trotter Splitting for Unbounded Operators
• Expanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding
• Non-unitary Coupled Cluster Enabled by Mid-circuit Measurements on Quantum Computers
• 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
• Quantized Markov Chain Couplings that Prepare Qsamples
• Controlled Gate Networks: Theory and Application to Eigenvalue Estimation
• Finding eigenvectors with a quantum variational algorithm
• Learning the structure of any Hamiltonian from minimal assumptions
• Quantum algorithms based on quantum trajectories
• Quantum Simulation via Stochastic Combination of Unitaries
• Numerical investigation of the quantum inverse algorithm on small molecules
• Quantum simulation in the entanglement picture
• Diagonal-Budgeted Trotterization for Efficient Quantum Hamiltonian Simulation
• Quantum Merlin-Arthur proof systems for synthesizing quantum states
• Quantum Routing and Entanglement Dynamics Through Bottlenecks
• A simple quantum simulation algorithm with near-optimal precision scaling
• Toward Density Functional Theory on Quantum Computers?