Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2203.17006 · Quantum

Quantum simulation of real-space dynamics

Andrew M. Childs, Jiaqi Leng, Tongyang Li, Jin-Peng Liu, Chenyi Zhang

Published Nov 17, 2022• 55 citations
arXivHTMLPDF

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 η particles can be simulated with gate complexity O~(ηdFpoly(log⁡(g′/ϵ))) , where ϵ is the discretization error, g′ 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 ϵ and g′ from poly(g′/ϵ) to poly(log⁡(g′/ϵ)) and polynomially improves the dependence on T and d , while maintaining best known performance with respect to η . For the case of Coulomb interactions, we give an algorithm using η3(d+η)Tpoly(log⁡(ηdTg′/(Δϵ)))/Δ one- and two-qubit gates, and another using η3(4d)d/2Tpoly(log⁡(ηdTg′/(Δϵ)))/Δ one- and two-qubit gates and QRAM operations, where T is the evolution time and the parameter Δ 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.

DOI
10.22331/q-2022-11-17-860

Related papers

Quantum Simulation of Electronic Structure via Quantum Fast Multipole Method

Dominic William Berry, Kianna Wan, Andrew Baczewski +3 more

Here we describe an approach for simulating electronic structure on quantum computers with significantly lower asymptotic complexity than prior work. The approach uses a real-space first-quantized representation of the molecular Hamiltonian, which we propagate using high-order product formulas. Essential for this low complexity is the use of a technique similar to the fast multipole method for computing the Coulomb operator with O ˜ ( η ) complexity for a simulation with η particles. We show how to modify this algorithm so that it can be implemented on a quantum computer. We ultimately demonstrate an approach with t ( η 4 / 3 N 1 / 3 + η 1 / 3 N 2 / 3 ) ( η N t / ϵ ) o ( 1 ) gate complexity, where N is the number of grid points, ϵ is target precision, and t is the duration of time evolution. This is roughly a speedup by O ( η ) over most prior algorithms. We provide lower complexity than all prior work for N < η 7 (the regime of practical interest), with only first-quantized interaction-picture simulations providing better performance for N > η 7 . As with the classical fast multipole method, large particle numbers η ≳ 10 3 would be needed to realize this advantage.

arXiv:2510.07380•PRX Quantum•May 1, 2026•10 citations

What Limits the Simulation of Quantum Computers?

Yiqing Zhou, E. Miles Stoudenmire, Xavier Waintal

An ultimate goal of quantum computing is to perform calculations beyond the reach of any classical computer.It is therefore imperative that useful quantum computers be very difficult to simulate classically, otherwise classical computers could be used for the applications envisioned for the quantum ones.Perfect quantum computers are unarguably exponentially difficult to simulate: the classical resources required grow exponentially with the number of qubits N or the depth D of the circuit.This difficulty has triggered recent experiments on deep, random circuits that aim to demonstrate that quantum devices may already perform tasks beyond the reach of classical computing.These real quantum computing devices, however, suffer from many sources of decoherence and imprecision which limit the degree of entanglement that can actually be reached to a fraction of its theoretical maximum.They are characterized by an exponentially decaying fidelity F ∼ ð1 -ϵÞ ND with an error rate ϵ per operation as small as ≈1% for current devices with several dozen qubits or even smaller for smaller devices.In this work, we provide new insight on the computing capabilities of real quantum computers by demonstrating that they can be simulated at a tiny fraction of the cost that would be needed for a perfect quantum computer.Our algorithms compress the representations of quantum wave functions using matrix product states, which are able to capture states with low to moderate entanglement very accurately.This compression introduces a finite error rate ϵ so that the algorithms closely mimic the behavior of real quantum computing devices.The computing time of our algorithm increases only linearly with N and D in sharp contrast with exact simulation algorithms.We illustrate our algorithms with simulations of random circuits for qubits connected in both one-and twodimensional lattices.We find that ϵ can be decreased at a polynomial cost in computing power down to a minimum error ϵ ∞ .Getting below ϵ ∞ requires computing resources that increase exponentially with ϵ ∞ =ϵ.For a two-dimensional array of N ¼ 54 qubits and a circuit with control-Z gates, error rates better than state-of-the-art devices can be obtained on a laptop in a few hours.For more complex gates such as a SWAP gate followed by a controlled rotation, the error rate increases by a factor 3 for similar computing time.Our results suggest that, despite the high fidelity reached by quantum devices, only a tiny fraction ð∼10 -8 Þ of the system Hilbert space is actually being exploited.

arXiv:2002.07730•Physical Review X•Nov 23, 2020•301 citations

Quantum simulation in the semi-classical regime

Shi Jin, Xiantao Li, Nana Liu

Solving the time-dependent Schrödinger equation is an important application area for quantum algorithms. We consider Schrödinger's equation in the semi-classical regime. Here the solutions exhibit strong multiple-scale behavior due to a small parameter ℏ , in the sense that the dynamics of the quantum states and the induced observables can occur on different spatial and temporal scales. Such a Schrödinger equation finds many applications, including in Born-Oppenheimer molecular dynamics and Ehrenfest dynamics. This paper considers quantum analogues of pseudo-spectral (PS) methods on classical computers. Estimates on the gate counts in terms of ℏ and the precision ε are obtained. It is found that the number of required qubits, m , scales only logarithmically with respect to ℏ . When the solution has bounded derivatives up to order ℓ , the symmetric Trotting method has gate complexity O ( ( ε ℏ ) − 1 2 p o l y l o g ( ε − 3 2 ℓ ℏ − 1 − 1 2 ℓ ) ) , provided that the diagonal unitary operators in the pseudo-spectral methods can be implemented with p o l y ( m ) operations. When physical observables are the desired outcomes, however, the step size in the time integration can be chosen independently of ℏ . The gate complexity in this case is reduced to O ( ε − 1 2 p o l y l o g ( ε − 3 2 ℓ ℏ − 1 ) ) , with ℓ again indicating the smoothness of the solution.

arXiv:2112.13279•Quantum•Jun 17, 2022•18 citations

Bounding the costs of quantum simulation of many-body physics in real space

Ian D Kivlichan, Nathan Wiebe, Ryan Babbush +1 more

Abstract We present a quantum algorithm for simulating the dynamics of a first-quantized Hamiltonian in real space based on the truncated Taylor series algorithm. We avoid the possibility of singularities by applying various cutoffs to the system and using a high-order finite difference approximation to the kinetic energy operator. We find that our algorithm can simulate η interacting particles using a number of calculations of the pairwise interactions that scales, for a fixed spatial grid spacing, as O ~ ( η 2 ) , versus the O ~ ( η 5 ) time required by previous methods (assuming the number of orbitals is proportional to η ), and scales super-polynomially better with the error tolerance than algorithms based on the Lie–Trotter–Suzuki product formula. Finally, we analyze discretization errors that arise from the spatial grid and show that under some circumstances these errors can remove the exponential speedups typically afforded by quantum simulation.

arXiv:1608.05696•Journal of Physics A Mathematical and Theoretical•Jun 7, 2017•81 citations

Efficient quantum simulation algorithms in the path integral formulation

Serene Shum, Nathan Wiebe

Abstract We provide a new paradigm for quantum simulation based on path integration that allows quantum speedups to be observed for problems that are more naturally expressed using the path integral formalism rather than the conventional Hamiltonian formalism. We provide two novel quantum algorithms based on Hamiltonian versions of the path integral formulation and another for Lagrangians of the form m 2 x ˙ 2 − V ( x ) , while avoiding the sign problems that preclude efficient Monte-Carlo algorithms for such problems. This Lagrangian path integral algorithm is based on a new rigorous derivation of a discrete version of the Lagrangian path integral. Our first Hamiltonian path integral method breaks up the paths into short timesteps. It is efficient under appropriate sparsity assumptions and requires a number of queries to oracles that give the eigenvalues and overlaps between the eigenvectors of the Hamiltonian terms that scales as t o ( 1 ) / ϵ o ( 1 ) for simulation time t and error ϵ . The second approach uses long-time path integrals for near-adiabatic systems and has query complexity that scales as O ( 1 / ϵ ) if the energy eigenvalue gaps and simulation time is sufficiently long. Finally, we show that our Lagrangian simulation algorithm requires a number of queries to an oracle that computes the discrete Lagrangian that scales for a system with η particles in D + 1 dimensions as O ~ ( η D t 2 / ϵ ) if V ( x ) is bounded and finite and the wavefunction obeys appropriate position and momentum cutoffs. This shows that Lagrangian dynamics can be efficiently simulated on quantum computers and opens up the possibility for quantum field theories for which the Hamiltonian is unknown to be efficiently simulated on quantum computers.

arXiv:2405.07042•Journal of Physics A Mathematical and Theoretical•May 29, 2026•1 citation

Faster quantum simulation of quantum chemistry with tailored algorithms and Hamiltonians

Ian Kivlichan

With quantum computers on the horizon, it is essential to understand what problems they can be used to solve. One potential application is simulating quantum systems, in particular, systems with many interacting electrons. However, there is a disparity between the computational resources required to study these problems and the capabilities of modern experimental quantum devices. In this thesis, we make progress toward closing this gap by reducing the cost of quantum simulation of quantum chemistry on a number of fronts. In the first half, we develop three improved quantum simulation algorithms by approximating time evolution under the Hamiltonian using a truncated Taylor series rather than the Trotter-Suzuki decomposition. We do this first for the molecular electronic structure Hamiltonian in two representations, obtaining asymptotic improvements in terms of both the number of orbitals and the required precision. We also apply the truncated Taylor series paradigm to quantum simulation in real space, where we consider simulation of general wave functions discretized on a uniform grid. In the second half, by working with Hamiltonians tailored specifically to quantum algorithms, we demonstrate that Trotter steps of the electronic structure Hamiltonian can be simulated in exactly N depth and with only linear connectivity, where N is the number of spin-orbitals. This resolves the problem of non-locality in fermion-to-qubit mappings, and has wide-ranging applications for variational and phase estimation-based quantum simulation of quantum chemistry. We further study this algorithm on an error-corrected quantum computer using the surface code. Benchmarking it alongside other product formula approaches, we show that quantum simulation of scientifically important instances of the electronic structure problem that are classically intractable can be performed with only a few hundred thousand physical qubits and fewer than one billion costly fault-tolerant gates. Finally, we study the effect of using randomized Hamiltonians in iterative phase estimation, and how this allows us to reduce the costs of simulation as well as to exploit knowledge of the ground state in how we design our simulation algorithm.

•Jan 8, 2020•0 citations
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 η particles can be simulated with gate complexity O~(ηdFpoly(log⁡(g′/ϵ))) , where ϵ is the discretization error, g′ 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 ϵ and g′ from poly(g′/ϵ) to poly(log⁡(g′/ϵ)) and polynomially improves the dependence on T and d , while maintaining best known performance with respect to η . For the case of Coulomb interactions, we give an algorithm using η3(d+η)Tpoly(log⁡(ηdTg′/(Δϵ)))/Δ one- and two-qubit gates, and another using η3(4d)d/2Tpoly(log⁡(ηdTg′/(Δϵ)))/Δ one- and two-qubit gates and QRAM operations, where T is the evolution time and the parameter Δ 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.
Here we describe an approach for simulating electronic structure on quantum computers with significantly lower asymptotic complexity than prior work. The approach uses a real-space first-quantized representation of the molecular Hamiltonian, which we propagate using high-order product formulas. Essential for this low complexity is the use of a technique similar to the fast multipole method for computing the Coulomb operator with O ˜ ( η ) complexity for a simulation with η particles. We show how to modify this algorithm so that it can be implemented on a quantum computer. We ultimately demonstrate an approach with t ( η 4 / 3 N 1 / 3 + η 1 / 3 N 2 / 3 ) ( η N t / ϵ ) o ( 1 ) gate complexity, where N is the number of grid points, ϵ is target precision, and t is the duration of time evolution. This is roughly a speedup by O ( η ) over most prior algorithms. We provide lower complexity than all prior work for N < η 7 (the regime of practical interest), with only first-quantized interaction-picture simulations providing better performance for N > η 7 . As with the classical fast multipole method, large particle numbers η ≳ 10 3 would be needed to realize this advantage.
An ultimate goal of quantum computing is to perform calculations beyond the reach of any classical computer.It is therefore imperative that useful quantum computers be very difficult to simulate classically, otherwise classical computers could be used for the applications envisioned for the quantum ones.Perfect quantum computers are unarguably exponentially difficult to simulate: the classical resources required grow exponentially with the number of qubits N or the depth D of the circuit.This difficulty has triggered recent experiments on deep, random circuits that aim to demonstrate that quantum devices may already perform tasks beyond the reach of classical computing.These real quantum computing devices, however, suffer from many sources of decoherence and imprecision which limit the degree of entanglement that can actually be reached to a fraction of its theoretical maximum.They are characterized by an exponentially decaying fidelity F ∼ ð1 -ϵÞ ND with an error rate ϵ per operation as small as ≈1% for current devices with several dozen qubits or even smaller for smaller devices.In this work, we provide new insight on the computing capabilities of real quantum computers by demonstrating that they can be simulated at a tiny fraction of the cost that would be needed for a perfect quantum computer.Our algorithms compress the representations of quantum wave functions using matrix product states, which are able to capture states with low to moderate entanglement very accurately.This compression introduces a finite error rate ϵ so that the algorithms closely mimic the behavior of real quantum computing devices.The computing time of our algorithm increases only linearly with N and D in sharp contrast with exact simulation algorithms.We illustrate our algorithms with simulations of random circuits for qubits connected in both one-and twodimensional lattices.We find that ϵ can be decreased at a polynomial cost in computing power down to a minimum error ϵ ∞ .Getting below ϵ ∞ requires computing resources that increase exponentially with ϵ ∞ =ϵ.For a two-dimensional array of N ¼ 54 qubits and a circuit with control-Z gates, error rates better than state-of-the-art devices can be obtained on a laptop in a few hours.For more complex gates such as a SWAP gate followed by a controlled rotation, the error rate increases by a factor 3 for similar computing time.Our results suggest that, despite the high fidelity reached by quantum devices, only a tiny fraction ð∼10 -8 Þ of the system Hilbert space is actually being exploited.
Solving the time-dependent Schrödinger equation is an important application area for quantum algorithms. We consider Schrödinger's equation in the semi-classical regime. Here the solutions exhibit strong multiple-scale behavior due to a small parameter ℏ , in the sense that the dynamics of the quantum states and the induced observables can occur on different spatial and temporal scales. Such a Schrödinger equation finds many applications, including in Born-Oppenheimer molecular dynamics and Ehrenfest dynamics. This paper considers quantum analogues of pseudo-spectral (PS) methods on classical computers. Estimates on the gate counts in terms of ℏ and the precision ε are obtained. It is found that the number of required qubits, m , scales only logarithmically with respect to ℏ . When the solution has bounded derivatives up to order ℓ , the symmetric Trotting method has gate complexity O ( ( ε ℏ ) − 1 2 p o l y l o g ( ε − 3 2 ℓ ℏ − 1 − 1 2 ℓ ) ) , provided that the diagonal unitary operators in the pseudo-spectral methods can be implemented with p o l y ( m ) operations. When physical observables are the desired outcomes, however, the step size in the time integration can be chosen independently of ℏ . The gate complexity in this case is reduced to O ( ε − 1 2 p o l y l o g ( ε − 3 2 ℓ ℏ − 1 ) ) , with ℓ again indicating the smoothness of the solution.
Abstract We present a quantum algorithm for simulating the dynamics of a first-quantized Hamiltonian in real space based on the truncated Taylor series algorithm. We avoid the possibility of singularities by applying various cutoffs to the system and using a high-order finite difference approximation to the kinetic energy operator. We find that our algorithm can simulate η interacting particles using a number of calculations of the pairwise interactions that scales, for a fixed spatial grid spacing, as O ~ ( η 2 ) , versus the O ~ ( η 5 ) time required by previous methods (assuming the number of orbitals is proportional to η ), and scales super-polynomially better with the error tolerance than algorithms based on the Lie–Trotter–Suzuki product formula. Finally, we analyze discretization errors that arise from the spatial grid and show that under some circumstances these errors can remove the exponential speedups typically afforded by quantum simulation.
Abstract We provide a new paradigm for quantum simulation based on path integration that allows quantum speedups to be observed for problems that are more naturally expressed using the path integral formalism rather than the conventional Hamiltonian formalism. We provide two novel quantum algorithms based on Hamiltonian versions of the path integral formulation and another for Lagrangians of the form m 2 x ˙ 2 − V ( x ) , while avoiding the sign problems that preclude efficient Monte-Carlo algorithms for such problems. This Lagrangian path integral algorithm is based on a new rigorous derivation of a discrete version of the Lagrangian path integral. Our first Hamiltonian path integral method breaks up the paths into short timesteps. It is efficient under appropriate sparsity assumptions and requires a number of queries to oracles that give the eigenvalues and overlaps between the eigenvectors of the Hamiltonian terms that scales as t o ( 1 ) / ϵ o ( 1 ) for simulation time t and error ϵ . The second approach uses long-time path integrals for near-adiabatic systems and has query complexity that scales as O ( 1 / ϵ ) if the energy eigenvalue gaps and simulation time is sufficiently long. Finally, we show that our Lagrangian simulation algorithm requires a number of queries to an oracle that computes the discrete Lagrangian that scales for a system with η particles in D + 1 dimensions as O ~ ( η D t 2 / ϵ ) if V ( x ) is bounded and finite and the wavefunction obeys appropriate position and momentum cutoffs. This shows that Lagrangian dynamics can be efficiently simulated on quantum computers and opens up the possibility for quantum field theories for which the Hamiltonian is unknown to be efficiently simulated on quantum computers.
With quantum computers on the horizon, it is essential to understand what problems they can be used to solve. One potential application is simulating quantum systems, in particular, systems with many interacting electrons. However, there is a disparity between the computational resources required to study these problems and the capabilities of modern experimental quantum devices. In this thesis, we make progress toward closing this gap by reducing the cost of quantum simulation of quantum chemistry on a number of fronts. In the first half, we develop three improved quantum simulation algorithms by approximating time evolution under the Hamiltonian using a truncated Taylor series rather than the Trotter-Suzuki decomposition. We do this first for the molecular electronic structure Hamiltonian in two representations, obtaining asymptotic improvements in terms of both the number of orbitals and the required precision. We also apply the truncated Taylor series paradigm to quantum simulation in real space, where we consider simulation of general wave functions discretized on a uniform grid. In the second half, by working with Hamiltonians tailored specifically to quantum algorithms, we demonstrate that Trotter steps of the electronic structure Hamiltonian can be simulated in exactly N depth and with only linear connectivity, where N is the number of spin-orbitals. This resolves the problem of non-locality in fermion-to-qubit mappings, and has wide-ranging applications for variational and phase estimation-based quantum simulation of quantum chemistry. We further study this algorithm on an error-corrected quantum computer using the surface code. Benchmarking it alongside other product formula approaches, we show that quantum simulation of scientifically important instances of the electronic structure problem that are classically intractable can be performed with only a few hundred thousand physical qubits and fewer than one billion costly fault-tolerant gates. Finally, we study the effect of using randomized Hamiltonians in iterative phase estimation, and how this allows us to reduce the costs of simulation as well as to exploit knowledge of the ground state in how we design our simulation algorithm.