Exponential quantum speedup in simulating coupled classical oscillators

Abstract

We present a quantum algorithm for simulating the classical dynamics of $2^n$ coupled oscillators (e.g., $2^n$ masses coupled by springs). Our approach leverages a mapping between the Schrödinger equation and Newton's equation for harmonic potentials such that the amplitudes of the evolved quantum state encode the momenta and displacements of the classical oscillators. When individual masses and spring constants can be efficiently queried, and when the initial state can be efficiently prepared, the complexity of our quantum algorithm is polynomial in $n$, almost linear in the evolution time, and sublinear in the sparsity. As an example application, we apply our quantum algorithm to efficiently estimate the kinetic energy of an oscillator at any time. We show that any classical algorithm solving this same problem is inefficient and must make $2^{\Omega (n)}$ queries to the oracle and, when the oracles are instantiated by efficient quantum circuits, the problem is BQP-complete. Thus, our approach solves a potentially practical application with an exponential speedup over classical computers. Finally, we show that under similar conditions our approach can efficiently simulate more general classical harmonic systems with $2^n$ modes.

arXiv comment43 pages, 4 figures. v3 changes include improved presentation, discussion of applications related to potential energies, and new appendix discussing relation to prior work

References in corpus (23)

• Quantum algorithm for solving linear systems of equations
• Strengths and Weaknesses of Quantum Computing
• Quantum Algorithms Revisited
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Preconditioned quantum linear system algorithm
• High-order quantum algorithm for solving linear differential equations
• Fixed-point quantum search with an optimal number of queries
• Optimal Quantum Measurements of Expectation Values of Observables
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• High-precision quantum algorithms for partial differential equations
• Quantum Algorithm for Simulating the Wave Equation
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Improved Techniques for Preparing Eigenstates of Fermionic Hamiltonians
• Black-box quantum state preparation without arithmetic
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Improved quantum algorithms for linear and nonlinear differential equations
• Fast-forwarding of Hamiltonians and Exponentially Precise Measurements
• QMA-complete problems for stoquastic Hamiltonians and Markov matrices
• Persymmetric Jacobi matrices with square-integer eigenvalues and dispersionless mass-spring chains

Cited by in corpus (25)

• Drug design on quantum computers
• Noisy intermediate-scale quantum simulation of the one-dimensional wave equation
• Hybrid Oscillator-Qubit Quantum Processors: Instruction Set Architectures, Abstract Machine Models, and Applications
• Hamiltonian simulation for hyperbolic partial differential equations by scalable quantum circuits
• Circuit complexity of quantum access models for encoding classical data
• Quantum algorithm for partial differential equations of non-conservative systems with spatially varying parameters
• A Perspective on Quantum Computing Applications in Quantum Chemistry using 25--100 Logical Qubits
• Quantum algorithm for the advection-diffusion equation and the Koopman-von Neumann approach to nonlinear dynamical systems
• Localized Virtual Purification
• A quantum computing concept for 1-D elastic wave simulation with exponential speedup
• Gate-based quantum simulation of Gaussian bosonic circuits on exponentially many modes
• The cost of solving linear differential equations on a quantum computer: fast-forwarding to explicit resource counts
• Solving Free Fermion Problems on a Quantum Computer
• Hamiltonian Learning via Shadow Tomography of Pseudo-Choi States
• Dictionary-based Block Encoding of Sparse Matrices with Low Subnormalization and Circuit Depth
• Calculating response functions of coupled oscillators using quantum phase estimation
• Unification of Finite Symmetries in Simulation of Many-body Systems on Quantum Computers
• Quantum circuits for partial differential equations in Fourier space
• Unbounded quantum-classical separation in sample complexity for sphere center finding
• An Efficient Decomposition of the Carleman Linearized Burgers' Equation
• A Quantum-Inspired Algorithm for Wave Simulation Using Tensor Networks
• Divergence-free algorithms for solving nonlinear differential equations on quantum computers
• Quantum community detection via deterministic elimination
• Synthesis of Single Qutrit Circuits from Clifford+R
• Simulating plasma wave propagation on a superconducting quantum chip