Quantum simulation of real-space dynamics

Abstract

Quantum simulation is a prominent application of quantum computers. While there is extensive previous work on simulating finite-dimensional systems, less is known about quantum algorithms for real-space dynamics. We conduct a systematic study of such algorithms. In particular, we show that the dynamics of a $d$-dimensional Schrödinger equation with $\eta$ particles can be simulated with gate complexity $\tilde{O}(\eta dF\text{poly}(\log (g^{\prime }/\epsilon )))$, where $\epsilon$ is the discretization error, $g^{\prime }$ controls the higher-order derivatives of the wave function, and $F$ measures the time-integrated strength of the potential. Compared to the best previous results, this exponentially improves the dependence on $\epsilon$ and $g^{\prime }$ from $\text{poly}(g^{\prime }/\epsilon )$ to $\text{poly}(\log (g^{\prime }/\epsilon ))$ and polynomially improves the dependence on $T$ and $d$, while maintaining best known performance with respect to $\eta$. For the case of Coulomb interactions, we give an algorithm using ${\eta }^3(d+\eta )T\text{poly}(\log (\eta dT{g}^{\prime }/(\Delta \epsilon )))/\Delta$ one- and two-qubit gates, and another using ${\eta }^3(4d{)}^{d/2}T\text{poly}(\log (\eta dT{g}^{\prime }/(\Delta \epsilon )))/\Delta$ one- and two-qubit gates and QRAM operations, where $T$ is the evolution time and the parameter $\Delta$ regulates the unbounded Coulomb interaction. We give applications to several computational problems, including faster real-space simulation of quantum chemistry, rigorous analysis of discretization error for simulation of a uniform electron gas, and a quadratic improvement to a quantum algorithm for escaping saddle points in nonconvex optimization.

References in corpus (41)

• Quantum Chemistry in the Age of Quantum Computing
• Simulated Quantum Computation of Molecular Energies
• Hamiltonian Simulation by Qubitization
• Quantum algorithms for quantum chemistry and quantum materials science
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Elucidating Reaction Mechanisms on Quantum Computers
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Toward the first quantum simulation with quantum speedup
• The Bravyi-Kitaev transformation for quantum computation of electronic structure
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Quantum Algorithms for Quantum Field Theories
• A Theory of Trotter Error
• Simulation of Electronic Structure Hamiltonians Using Quantum Computers
• Polynomial-time quantum algorithm for the simulation of chemical dynamics
• Efficient Simulation of Quantum Systems by Quantum Computers
• A random compiler for fast Hamiltonian simulation
• Gate count estimates for performing quantum chemistry on small quantum computers
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Low Depth Quantum Simulation of Electronic Structure
• Quantum computing enhanced computational catalysis
• Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
• Efficient Distributed Quantum Computing
• Chemical Basis of Trotter-Suzuki Errors in Quantum Chemistry Simulation
• Low rank representations for quantum simulation of electronic structure
• High-precision quantum algorithms for partial differential equations
• Exponentially more precise quantum simulation of fermions I: Quantum chemistry in second quantization
• Quantum algorithm for simulating real time evolution of lattice Hamiltonians
• Exploiting locality in quantum computation for quantum chemistry
• Fault-Tolerant Quantum Simulations of Chemistry in First Quantization
• Fast quantum algorithm for numerical gradient estimation
• Time-dependent Hamiltonian simulation with $L^1$-norm scaling
• Quantum Simulation of Chemistry with Sublinear Scaling in Basis Size
• Exponentially More Precise Quantum Simulation of Fermions in the Configuration Interaction Representation
• Bounding the costs of quantum simulation of many-body physics in real space
• Nearly tight Trotterization of interacting electrons
• Quantum algorithms and lower bounds for convex optimization
• Time-dependent Hamiltonian Simulation of Highly Oscillatory Dynamics and Superconvergence for Schrödinger Equation
• Convex optimization using quantum oracles
• Exploiting fermion number in factorized decompositions of the electronic structure Hamiltonian
• On quantum algorithms for the Schrödinger equation in the semi-classical regime
• Quantum algorithms for escaping from saddle points

Cited by in corpus (19)

• Grid-based methods for chemistry simulations on a quantum computer
• Roadmap for Molecular Benchmarks in Nonadiabatic Dynamics
• Quantum simulation of exact electron dynamics can be more efficient than classical mean-field methods
• Noisy intermediate-scale quantum simulation of the one-dimensional wave equation
• Quantum differential equation solvers: limitations and fast-forwarding
• Quantum Langevin Dynamics for Optimization
• Efficient solution of the non-unitary time-dependent Schrodinger equation on a quantum computer with complex absorbing potential
• Explicit block encodings of boundary value problems for many-body elliptic operators
• Time-dependent Hamiltonian Simulation via Magnus Expansion: Algorithm and Superconvergence
• Measuring Trotter error and its application to precision-guaranteed Hamiltonian simulations
• Observable Error Bounds of the Time-splitting Scheme for Quantum-Classical Molecular Dynamics
• Uniform observable error bounds of Trotter formulae for the semiclassical Schrödinger equation
• Quantum algorithms for linear and non-linear fractional reaction-diffusion equations
• Optimized synthesis of circuits for diagonal unitary matrices with reflection symmetry
• On the Trotter Error in Many-body Quantum Dynamics with Coulomb Potentials
• Approximate real-time evolution operator for potential with one ancillary qubit and application to first-quantized Hamiltonian simulation
• Expanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding
• Discrete Superconvergence Analysis for Quantum Magnus Algorithms of Unbounded Hamiltonian Simulation
• Calculating potential energy surfaces with quantum computers by measuring only the density along adiabatic transitions