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:2609.20721

Quantum Simulation of Dissipative Non-Markovian Coupled Classical Oscillators

Malte Schade, Sophia Simon, Nathan Wiebe, Scott Keating, Cyrill Bösch, Andreas Fichtner

quant-phSubmitted Sep 17, 2026• Announced Sep 18, 2026• 0 citations• Revised Oct 12, 2026 (v2)
v1 · Sep 17, 2026v2 · Oct 12, 2026
arXivHTMLPDF

Abstract

We present a quantum algorithm for simulating classical oscillator networks characterized by non-Markovian dissipation and time-varying material properties, extending recent speedups for undamped harmonic systems to viscoacoustic and viscoelastic media. We embed the history-dependent dynamics into a Markovian state space governed by a non-Hermitian operator by approximating memory kernels through a Prony series. We then use linear combination of Hamiltonian simulation to estimate the instantaneous kinetic and potential energy for a subset of oscillators at time $t$ within error $ε$ using a number of queries to the oscillator system that scales as $\widetilde{\mathcal{O}}(α_{\rm tot} t/ε)$, where $α_{\rm tot}$ is polynomial in the strength of the dissipation, spring constants, inverse masses, and sparsity of the connections in the network. We further show that this energy estimation task is in the worst-case classically hard (i.e., a corresponding decision problem is $\mathsf{BQP}$-complete), even in the presence of strong dissipation. For time-dependent materials, we show that changes in material properties appear as effective dissipation or growth in the energy representation. Additionally, we prove the infeasibility of exponential quantum advantages in locally coupled topologies through a novel form of Lieb-Robinson-like bounds that apply to differential equations. This allows our quantum algorithms to provide quartic speedups for locally coupled damped oscillator systems in three dimensions, raising the possibility of practical quantum speedups for realistically damped oscillator networks and approximated wave equations.

Comments
59 pages, 7 figures

Related papers

Exponential Quantum Speedup in Simulating Coupled Classical Oscillators

Ryan Babbush, Dominic William Berry, Robin Kothari +2 more

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 ΩðnÞ queries to the oracle, and when the oracles are instantiated by efficient quantum circuits, the problem is bounded-error quantum polynomial time 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:2303.13012•Physical Review X•Dec 4, 2023•58 citations

Quantum simulation of non-Markovian dynamical systems

Abtin Ameri, Arkopal Dutt, Hari Krovi

Existing quantum algorithms for simulating dynamical systems -- from Hamiltonian simulation to linear and nonlinear differential equations solvers -- simulate Markovian dynamics, in which the system's future evolution depends solely on its current state. We turn our attention to developing quantum algorithms for non-Markovian dynamical systems where the system's future evolution depends on its past history and thus has memory. Specifically, we develop efficient algorithms for linear Volterra integro-differential equations (VIDEs) with a convolution memory kernel that output a quantum state encoding the state description over a time interval or at a particular time. Given efficient circuits for the problem inputs, our algorithms achieve an exponential speedup in system size over existing classical algorithms. We develop an algorithm for general kernels assuming that $\textsf{M} < 1$, where $\textsf{M}$ characterizes the strength of the memory term relative to the dissipation of the Markovian part of the dynamics. We complement this with lower bounds for general-kernel VIDEs when $\textsf{M} \geq 1$, showing that the problem becomes intractable for a family of systems. However, by specializing to structured kernels which admit concise decompositions over exponentials, we develop efficient quantum algorithms even when $\textsf M \geq 1$ by converting the VIDE into a larger set of ODEs, a procedure which we call Markovianization. As an application of the overall framework, we discuss the Mori-Zwanzig formalism used in open quantum systems and fluid dynamics. Overall, our results expand the range of dynamical systems that quantum computers can simulate efficiently.

quant-pharXiv:2608.13533•Aug 14, 2026•0 citations

Quantum algorithms to simulate quadratic classical Hamiltonians and optimal control

Hari Krovi

Simulation of realistic classical mechanical systems is of great importance to many areas of engineering such as robotics, dynamics of rotating machinery and control theory. In this work, we develop quantum algorithms to estimate quantities of interest such as the kinetic energy in a given classical mechanical system in the presence of friction or damping as well as forcing or source terms, which makes the algorithm of practical interest. We show that for such systems, the quantum algorithm scales polynomially with the logarithm of the dimension of the system. We cast this problem in terms of Hamilton's equations of motion (equivalent to the first variation of the Lagrangian) and solve them using quantum algorithms for differential equations. We then consider the hardness of estimating the kinetic energy of a damped coupled oscillator system. We show that estimating the kinetic energy at a given time of this system to within additive precision is BQP hard when the strength of the damping term is bounded by an inverse polynomial in the number of qubits. We then consider the problem of designing optimal control of classical systems, which can be cast as the second variation of the Lagrangian. In this direction, we first consider the Riccati equation, which is a nonlinear differential equation ubiquitous in control theory. We give an efficient quantum algorithm to solve the Riccati differential equation well into the nonlinear regime. To our knowledge, this is the first example of any nonlinear differential equation that can be solved when the strength of the nonlinearity is asymptotically greater than the amount of dissipation. We then show how to use this algorithm to solve the linear quadratic regulator problem, which is an example of the Hamilton-Jacobi-Bellman equation.

arXiv:2404.07303•Apr 10, 2024•0 citations

Simulating dynamics of RLC circuits with a quantum differential-algebraic equations solver

Arkopal Dutt, Anirban Chowdhury, Kristan Temme +1 more

We introduce a quantum algorithm for simulating the dynamics of electrical circuits consisting of resistors, inductors and capacitors (aka RLC circuits) along with power sources. Given oracle access to the connectivity of the circuit and values of the electrical elements, our algorithm prepares a quantum state that encodes voltages and current values either at a specified time or the history of their evolution over a time-interval. For an RLC circuit with $N$ components, our algorithm runs in time $\textsf{polylog}(N)$ under mild assumptions on the connectivity of the circuit and values of its components. This provides an exponential speed-up over classical algorithms that take $\textsf{poly}(N)$ time in the worst-case. Our algorithm can be used to estimate energy across a set of components or dissipated power in $\textsf{polylog}(N)$ time, a problem that we prove is BQP-hard and therefore unlikely to be efficiently solved by classical algorithms. The main challenge in simulating the dynamics of RLC circuits is that they are governed by differential-algebraic equations (DAEs), a coupled system of differential equations with hidden algebraic constraints. Consequentially, existing quantum algorithms for ordinary differential equations cannot be directly utilized. We therefore develop a quantum DAE solver for simulating the time-evolution of linear DAEs. For RLC circuits, we employ modified nodal analysis to create a system of DAEs compatible with our quantum algorithm. We establish BQP-hardness by demonstrating that any network of classical harmonic oscillators, for which an energy-estimation problem is known to be BQP-hard, is a special case of an LC circuit. Our work gives theoretical evidence of quantum advantage in simulating RLC circuits and we expect that our quantum DAE solver will find broader use in the simulation of dynamical systems.

quant-pharXiv:2604.26945•Apr 30, 2026•0 citations

Exponential quantum speedup in simulating coupled classical oscillators*

Ryan Babbush, Dominic William Berry, Robin Kothari +2 more

We study the problem of simulating the time evolution of a system of 2nclassical coupled oscillators (e.g., 2nballs connected by springs) on a quantum computer. We map Newton’s equation for harmonic potentials to Schrödinger’s equation, such that the amplitudes of an $\mathcal{O}(n)$-qubit quantum state encode the momenta and displacements of the 2nclassical oscillators. Given oracle access to the masses and spring constants, we describe a quantum algorithm with query and time complexity poly (n) that solves this problem when certain parameters are polynomially bounded and the initial state is easy to prepare. As an example application, we apply our quantum algorithm to efficiently estimate the normalized kinetic energy of an oscillator at any time. We then show that any classical algorithm solving the same problem must make $2^{\Omega(n)}$ queries to the oracle and we also show that when the oracles are instantiated by poly (n)-size circuits, the problem is BQP-complete. Thus, our approach solves a potentially practical application with an exponential speedup over classical computers.

Annual Symposium on Foundations of Computer Science•Nov 6, 2023•6 citations

Exponential Quantum Advantage for Simulating Open Classical Systems

Agnes Villanyi, Yariv Yanay, Ari Mizel

A recent promising arena for quantum advantage is simulating exponentially large classical systems. Here, we show how this advantage can be used to calculate the dynamics of open classical systems experiencing dissipation, including the effects of non-Markovian baths. This is a particularly interesting class of systems since dissipation plays a key role in contexts ranging from fluid dynamics to thermalization. We adopt the Caldeira-Leggett Hamiltonian, a generic model for dissipation in which the system is coupled to a bath of harmonic oscillators with a large number of degrees of freedom. To date, the most efficient classical algorithms for simulating such systems have a polynomial dependence on the size of the bath. In this work, we give a quantum algorithm with an exponential speedup, capable of simulating $d$ system degrees of freedom coupled to $N = 2^n\gg d$ bath degrees of freedom, to within error $\varepsilon$, using $O({\rm poly}(d, n, t, \varepsilon^{-1}))$ quantum gates.

arXiv:2503.11483•Mar 14, 2025•0 citations
We present a quantum algorithm for simulating classical oscillator networks characterized by non-Markovian dissipation and time-varying material properties, extending recent speedups for undamped harmonic systems to viscoacoustic and viscoelastic media. We embed the history-dependent dynamics into a Markovian state space governed by a non-Hermitian operator by approximating memory kernels through a Prony series. We then use linear combination of Hamiltonian simulation to estimate the instantaneous kinetic and potential energy for a subset of oscillators at time ttt within error εεε using a number of queries to the oscillator system that scales as O~(αtott/ε)\widetilde{\mathcal{O}}(α_{\rm tot} t/ε)O(αtot​t/ε), where αtotα_{\rm tot}αtot​ is polynomial in the strength of the dissipation, spring constants, inverse masses, and sparsity of the connections in the network. We further show that this energy estimation task is in the worst-case classically hard (i.e., a corresponding decision problem is BQP\mathsf{BQP}BQP-complete), even in the presence of strong dissipation. For time-dependent materials, we show that changes in material properties appear as effective dissipation or growth in the energy representation. Additionally, we prove the infeasibility of exponential quantum advantages in locally coupled topologies through a novel form of Lieb-Robinson-like bounds that apply to differential equations. This allows our quantum algorithms to provide quartic speedups for locally coupled damped oscillator systems in three dimensions, raising the possibility of practical quantum speedups for realistically damped oscillator networks and approximated wave equations.
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 ΩðnÞ queries to the oracle, and when the oracles are instantiated by efficient quantum circuits, the problem is bounded-error quantum polynomial time 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.
Existing quantum algorithms for simulating dynamical systems -- from Hamiltonian simulation to linear and nonlinear differential equations solvers -- simulate Markovian dynamics, in which the system's future evolution depends solely on its current state. We turn our attention to developing quantum algorithms for non-Markovian dynamical systems where the system's future evolution depends on its past history and thus has memory. Specifically, we develop efficient algorithms for linear Volterra integro-differential equations (VIDEs) with a convolution memory kernel that output a quantum state encoding the state description over a time interval or at a particular time. Given efficient circuits for the problem inputs, our algorithms achieve an exponential speedup in system size over existing classical algorithms. We develop an algorithm for general kernels assuming that M<1\textsf{M} < 1M<1, where M\textsf{M}M characterizes the strength of the memory term relative to the dissipation of the Markovian part of the dynamics. We complement this with lower bounds for general-kernel VIDEs when M≥1\textsf{M} \geq 1M≥1, showing that the problem becomes intractable for a family of systems. However, by specializing to structured kernels which admit concise decompositions over exponentials, we develop efficient quantum algorithms even when M≥1\textsf M \geq 1M≥1 by converting the VIDE into a larger set of ODEs, a procedure which we call Markovianization. As an application of the overall framework, we discuss the Mori-Zwanzig formalism used in open quantum systems and fluid dynamics. Overall, our results expand the range of dynamical systems that quantum computers can simulate efficiently.
Simulation of realistic classical mechanical systems is of great importance to many areas of engineering such as robotics, dynamics of rotating machinery and control theory. In this work, we develop quantum algorithms to estimate quantities of interest such as the kinetic energy in a given classical mechanical system in the presence of friction or damping as well as forcing or source terms, which makes the algorithm of practical interest. We show that for such systems, the quantum algorithm scales polynomially with the logarithm of the dimension of the system. We cast this problem in terms of Hamilton's equations of motion (equivalent to the first variation of the Lagrangian) and solve them using quantum algorithms for differential equations. We then consider the hardness of estimating the kinetic energy of a damped coupled oscillator system. We show that estimating the kinetic energy at a given time of this system to within additive precision is BQP hard when the strength of the damping term is bounded by an inverse polynomial in the number of qubits. We then consider the problem of designing optimal control of classical systems, which can be cast as the second variation of the Lagrangian. In this direction, we first consider the Riccati equation, which is a nonlinear differential equation ubiquitous in control theory. We give an efficient quantum algorithm to solve the Riccati differential equation well into the nonlinear regime. To our knowledge, this is the first example of any nonlinear differential equation that can be solved when the strength of the nonlinearity is asymptotically greater than the amount of dissipation. We then show how to use this algorithm to solve the linear quadratic regulator problem, which is an example of the Hamilton-Jacobi-Bellman equation.
We introduce a quantum algorithm for simulating the dynamics of electrical circuits consisting of resistors, inductors and capacitors (aka RLC circuits) along with power sources. Given oracle access to the connectivity of the circuit and values of the electrical elements, our algorithm prepares a quantum state that encodes voltages and current values either at a specified time or the history of their evolution over a time-interval. For an RLC circuit with NNN components, our algorithm runs in time polylog(N)\textsf{polylog}(N)polylog(N) under mild assumptions on the connectivity of the circuit and values of its components. This provides an exponential speed-up over classical algorithms that take poly(N)\textsf{poly}(N)poly(N) time in the worst-case. Our algorithm can be used to estimate energy across a set of components or dissipated power in polylog(N)\textsf{polylog}(N)polylog(N) time, a problem that we prove is BQP-hard and therefore unlikely to be efficiently solved by classical algorithms. The main challenge in simulating the dynamics of RLC circuits is that they are governed by differential-algebraic equations (DAEs), a coupled system of differential equations with hidden algebraic constraints. Consequentially, existing quantum algorithms for ordinary differential equations cannot be directly utilized. We therefore develop a quantum DAE solver for simulating the time-evolution of linear DAEs. For RLC circuits, we employ modified nodal analysis to create a system of DAEs compatible with our quantum algorithm. We establish BQP-hardness by demonstrating that any network of classical harmonic oscillators, for which an energy-estimation problem is known to be BQP-hard, is a special case of an LC circuit. Our work gives theoretical evidence of quantum advantage in simulating RLC circuits and we expect that our quantum DAE solver will find broader use in the simulation of dynamical systems.
We study the problem of simulating the time evolution of a system of 2nclassical coupled oscillators (e.g., 2nballs connected by springs) on a quantum computer. We map Newton’s equation for harmonic potentials to Schrödinger’s equation, such that the amplitudes of an O(n)\mathcal{O}(n)O(n)-qubit quantum state encode the momenta and displacements of the 2nclassical oscillators. Given oracle access to the masses and spring constants, we describe a quantum algorithm with query and time complexity poly (n) that solves this problem when certain parameters are polynomially bounded and the initial state is easy to prepare. As an example application, we apply our quantum algorithm to efficiently estimate the normalized kinetic energy of an oscillator at any time. We then show that any classical algorithm solving the same problem must make 2Ω(n)2^{\Omega(n)}2Ω(n) queries to the oracle and we also show that when the oracles are instantiated by poly (n)-size circuits, the problem is BQP-complete. Thus, our approach solves a potentially practical application with an exponential speedup over classical computers.
A recent promising arena for quantum advantage is simulating exponentially large classical systems. Here, we show how this advantage can be used to calculate the dynamics of open classical systems experiencing dissipation, including the effects of non-Markovian baths. This is a particularly interesting class of systems since dissipation plays a key role in contexts ranging from fluid dynamics to thermalization. We adopt the Caldeira-Leggett Hamiltonian, a generic model for dissipation in which the system is coupled to a bath of harmonic oscillators with a large number of degrees of freedom. To date, the most efficient classical algorithms for simulating such systems have a polynomial dependence on the size of the bath. In this work, we give a quantum algorithm with an exponential speedup, capable of simulating ddd system degrees of freedom coupled to N=2n≫dN = 2^n\gg dN=2n≫d bath degrees of freedom, to within error ε\varepsilonε, using O(poly(d,n,t,ε−1))O({\rm poly}(d, n, t, \varepsilon^{-1}))O(poly(d,n,t,ε−1)) quantum gates.