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

Direct Equivalence between Dynamics of Quantum Walks and Coupled Classical Oscillators

Lilith Zschetzsche, Refik Mansuroglu, András Molnár, Norbert Schuch

quant-phSubmitted Dec 3, 2025• Announced Dec 4, 2025• 0 citations
arXivHTMLPDF

Abstract

Continuous time quantum walks on exponentially large, sparse graphs form a powerful paradigm for quantum computing: On the one hand, they can be efficiently simulated on a quantum computer. On the other hand, they are themselves BQP-complete, providing an alternative framework for thinking about quantum computing -- a perspective which has indeed led to a number of novel algorithms and oracle problems. Recently, simulating the dynamics of a system of harmonic oscillators (that is, masses and springs) was set forth as another BQP-complete problem defined on exponentially large, sparse graphs. In this work, we establish a direct and transparent mapping between these two classes of problems. As compared to linking the two classes of problems via their BQP-completeness, our mapping has several desirable features: It is transparent, in that it respects the structure of the problem, including the geometry of the underlying graph, initialization, read-out, and efficient oracle access, resulting in low overhead in terms of both space and time; it allows to map also between restricted subsets of instances of both problems which are not BQP-complete; it provides a recipe to directly translate any quantum algorithm designed in the quantum walk paradigm to harmonic oscillators (and vice versa); and finally, it provides an alternative, transparent way to prove BQP-completeness of the harmonic oscillator problem by mapping it to BQP-completeness construction for the quantum walk problem (or vice versa).

Comments
17 pages, 3 figures

Related papers

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

Complexity of Quadratic Bosonic Hamiltonian Simulation: BQP-Completeness and PostBQP-Hardness

Lilith Zschetzsche, Refik Mansuroglu, Norbert Schuch

The computational complexity of simulating the dynamics of physical quantum systems is a central question at the interface of quantum physics and computer science. In this work, we address this question for the simulation of exponentially large bosonic Hamiltonians with quadratic interactions. We present two results: First, we introduce a broad class of quadratic bosonic problems for which we prove that they are BQP-complete. Importantly, this class includes two known BQP-complete problems as special cases: Classical oscillator networks and continuous-time quantum walks. Second, we show that extending the aforementioned class to even more general quadratic Hamiltonians results in a PostBQP-complete problem, which constitutes a jump in the complexity of simulating large quantum systems on a quantum computer, as well as in the difference in complexity between their simulation on classical and quantum computers.

quant-pharXiv:2603.26561•Mar 30, 2026•0 citations

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 Coupled Harmonic Oscillators: From Theory to Implementation

Viraj Dsouza, Weronika Golletz, Dimitrios Kranas +3 more

We investigate the quantum algorithm of Babbush et al. (arXiv:2303.13012v3) for simulating coupled harmonic oscillators, which promises exponential speedups over classical methods. Focusing on linearly connected oscillator chains, we bridge the gap between theory and implementation by developing and comparing three concrete realizations of the algorithm. First, we implement a sparse initial state preparation combined with product-formula (Suzuki-Trotter) Hamiltonian simulation. Second, we implement a fully quantum, oracle-based framework in which classical data are accessed via oracles, the Hamiltonian is block-encoded, and time evolution is performed using QSVT-based Hamiltonian simulation. Third, we propose an efficient alternative that combines the sparse state-preparation routine of the first approach with the oracle and block-encoding-based simulation pipeline of the second. We provide these implementations on Classiq, a high-level quantum design platform and provide appropriate resource benchmarks. Our simulation results show that the complex initial state preparation proposed by Babbush et al. can be circumvented at least in the linear-chain case. Finally, we illustrate two physical applications-extracting normal modes and simulating coarse-grained energy propagation-demonstrating how the algorithm connects to measurable observables. Our results clarify the resource requirements of the algorithm and provide concrete pathways toward practical quantum advantage.

quant-pharXiv:2603.05479•Mar 6, 2026•0 citations

Efficient Simulation of Szegedy Quantum Walk Formulations and Algorithms

Sergio A. Ortega, Daniel K. Park

Quantum walks provide a versatile framework for quantum algorithms across a wide range of applications. We develop efficient classical simulation methods for Szegedy quantum walks that avoid explicit construction of the full unitary evolution operator. Unlike previous approaches restricted to a particular walk formulation, our framework is built from fundamental update and reflection operators, enabling the simulation of a broader class of Szegedy walk formulations. We further extend these methods to phase-estimation-based algorithms coupled to the walk, including implementations suitable for large sparse graphs. The resulting methods achieve optimal $O(N^2)$ complexity for dense graphs with $N$ nodes. For sparse graphs, the computational cost scales linearly with the number of edges, which is $O(N)$ in many cases. We implement the framework in the Python package SQWLib and illustrate its capabilities through simulations of representative algorithms, including quantum simulated annealing and quantum search on graphs. These results provide a practical tool for studying Szegedy-walk-based algorithms numerically beyond purely analytical treatments.

quant-pharXiv:2606.14226•Jun 15, 2026•0 citations

Efficient sparse state preparation via quantum walks

Alvin Gonzales, Rebekah Herrman, Colin Campbell +4 more

Continuous-time quantum walks (CTQWs) on dynamic graphs, referred to as dynamic CTQWs, are a recently introduced universal model of computation that offers a new paradigm in which to envision quantum algorithms. In this work, we develop an algorithm that converts single-edge and self-loop dynamic CTQWs to the gate model of computation. We use this mapping to introduce an efficient sparse quantum state preparation framework based on dynamic CTQWs. Our approach utilizes combinatorics techniques such as minimal hitting sets, minimum spanning trees, and shortest Hamiltonian paths to reduce the number of controlled gates required to prepare sparse states. We show that our framework encompasses the current state of the art ancilla-free sparse state preparation method by reformulating this method as a CTQW. This CTQW-based framework offers an alternative to the uniformly controlled rotation method used by Qiskit by requiring fewer CX gates when the target state has a polynomial number of non-zero amplitudes.

arXiv:2405.20273•npj Quantum Information•Aug 21, 2025•2 citations
Continuous time quantum walks on exponentially large, sparse graphs form a powerful paradigm for quantum computing: On the one hand, they can be efficiently simulated on a quantum computer. On the other hand, they are themselves BQP-complete, providing an alternative framework for thinking about quantum computing -- a perspective which has indeed led to a number of novel algorithms and oracle problems. Recently, simulating the dynamics of a system of harmonic oscillators (that is, masses and springs) was set forth as another BQP-complete problem defined on exponentially large, sparse graphs. In this work, we establish a direct and transparent mapping between these two classes of problems. As compared to linking the two classes of problems via their BQP-completeness, our mapping has several desirable features: It is transparent, in that it respects the structure of the problem, including the geometry of the underlying graph, initialization, read-out, and efficient oracle access, resulting in low overhead in terms of both space and time; it allows to map also between restricted subsets of instances of both problems which are not BQP-complete; it provides a recipe to directly translate any quantum algorithm designed in the quantum walk paradigm to harmonic oscillators (and vice versa); and finally, it provides an alternative, transparent way to prove BQP-completeness of the harmonic oscillator problem by mapping it to BQP-completeness construction for the quantum walk problem (or vice versa).
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.
The computational complexity of simulating the dynamics of physical quantum systems is a central question at the interface of quantum physics and computer science. In this work, we address this question for the simulation of exponentially large bosonic Hamiltonians with quadratic interactions. We present two results: First, we introduce a broad class of quadratic bosonic problems for which we prove that they are BQP-complete. Importantly, this class includes two known BQP-complete problems as special cases: Classical oscillator networks and continuous-time quantum walks. Second, we show that extending the aforementioned class to even more general quadratic Hamiltonians results in a PostBQP-complete problem, which constitutes a jump in the complexity of simulating large quantum systems on a quantum computer, as well as in the difference in complexity between their simulation on classical and quantum computers.
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.
We investigate the quantum algorithm of Babbush et al. (arXiv:2303.13012v3) for simulating coupled harmonic oscillators, which promises exponential speedups over classical methods. Focusing on linearly connected oscillator chains, we bridge the gap between theory and implementation by developing and comparing three concrete realizations of the algorithm. First, we implement a sparse initial state preparation combined with product-formula (Suzuki-Trotter) Hamiltonian simulation. Second, we implement a fully quantum, oracle-based framework in which classical data are accessed via oracles, the Hamiltonian is block-encoded, and time evolution is performed using QSVT-based Hamiltonian simulation. Third, we propose an efficient alternative that combines the sparse state-preparation routine of the first approach with the oracle and block-encoding-based simulation pipeline of the second. We provide these implementations on Classiq, a high-level quantum design platform and provide appropriate resource benchmarks. Our simulation results show that the complex initial state preparation proposed by Babbush et al. can be circumvented at least in the linear-chain case. Finally, we illustrate two physical applications-extracting normal modes and simulating coarse-grained energy propagation-demonstrating how the algorithm connects to measurable observables. Our results clarify the resource requirements of the algorithm and provide concrete pathways toward practical quantum advantage.
Quantum walks provide a versatile framework for quantum algorithms across a wide range of applications. We develop efficient classical simulation methods for Szegedy quantum walks that avoid explicit construction of the full unitary evolution operator. Unlike previous approaches restricted to a particular walk formulation, our framework is built from fundamental update and reflection operators, enabling the simulation of a broader class of Szegedy walk formulations. We further extend these methods to phase-estimation-based algorithms coupled to the walk, including implementations suitable for large sparse graphs. The resulting methods achieve optimal O(N2)O(N^2)O(N2) complexity for dense graphs with NNN nodes. For sparse graphs, the computational cost scales linearly with the number of edges, which is O(N)O(N)O(N) in many cases. We implement the framework in the Python package SQWLib and illustrate its capabilities through simulations of representative algorithms, including quantum simulated annealing and quantum search on graphs. These results provide a practical tool for studying Szegedy-walk-based algorithms numerically beyond purely analytical treatments.
Continuous-time quantum walks (CTQWs) on dynamic graphs, referred to as dynamic CTQWs, are a recently introduced universal model of computation that offers a new paradigm in which to envision quantum algorithms. In this work, we develop an algorithm that converts single-edge and self-loop dynamic CTQWs to the gate model of computation. We use this mapping to introduce an efficient sparse quantum state preparation framework based on dynamic CTQWs. Our approach utilizes combinatorics techniques such as minimal hitting sets, minimum spanning trees, and shortest Hamiltonian paths to reduce the number of controlled gates required to prepare sparse states. We show that our framework encompasses the current state of the art ancilla-free sparse state preparation method by reformulating this method as a CTQW. This CTQW-based framework offers an alternative to the uniformly controlled rotation method used by Qiskit by requiring fewer CX gates when the target state has a polynomial number of non-zero amplitudes.