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.40162

Classical and Quantum Simulation of All-to-All Quantum Dynamics in Logarithmic Space

Maximilian Lutz, Rahul Trivedi, J. Ignacio Cirac

quant-phSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

Abstract

We study both the classical and the quantum complexity of the problem of estimating disorder-averaged quench dynamics for all-to-all spin Hamiltonians such as quantum Hopfield, Sherrington--Kirkpatrick (SK) or Dicke-type models. Disorder averaging restores permutation invariance in this setting, so states of $N$ spins can be stored in $\mathcal O(\log N)$ qubits. While logarithmic-space quantum computations are known to be simulatable classically in polynomial time or in polylogarithmic space, whether a single algorithm can achieve both is open, raising the possibility of simultaneous quantum advantage. To this end, we give a quantum algorithm for permutation-invariant $k$-local dynamics without disorder using polynomial time and $\mathcal O(\log N)$ quantum and classical space. We show that any classical algorithm matching these resources would imply $\mathsf{BQL}\subseteq \mathsf{SC}$. For short times, however, we provide such algorithms, including for SK models. For Hopfield models, we discuss how dilating the disorder to ancilla qubits reduces the problem to the disorder-free case on an enlarged system, thus extending both classical and quantum results to them. We give some evidence that their long-time dynamics are non-trivial. They thus emerge as a candidate for a simultaneous time--space advantage in quantum simulation.

Comments
19+7 pages

Related papers

On the quantum computational complexity of classical linear dynamics with geometrically local interactions: Dequantization and universality

Kazuki Sakamoto, Keisuke Fujii

The simulation of large-scale classical systems in exponentially small space on quantum computers has gained attention. The prior work demonstrated that a quantum algorithm offers an exponential speedup over any classical algorithm in simulating classical dynamics with long-range interactions. However, many real-world classical systems, such as those arising from partial differential equations, exhibit only local interactions. The question remains whether quantum algorithms can still provide exponential speedup under this condition. In this work, we thoroughly characterize the computational complexity of simulating such geometrically local systems on quantum computers. First, we dequantize the quantum algorithm for simulating short-time (polynomial-time) dynamics of such systems. This implies that the problem of simulating this dynamics does not yield any exponential quantum advantage. Second, we show that simulating short-time dynamics is at least as hard as polynomial-time and linear-space probabilistic classical computation. Third, we show that the computational complexity of simulating long-time (exponential-time) dynamics is captured by exponential-time and polynomial-space quantum computation. This suggests a super-polynomial time advantage when restricting the computation to polynomial-space, or an exponential space advantage otherwise. This work offers new insights into the complexity of classical dynamics governed by partial differential equations, providing a pathway for achieving quantum advantage in practical problems.

arXiv:2505.10445•Quantum•Aug 3, 2026•0 citations

Exploiting emergent symmetries in disorder-averaged quantum dynamics

Mirco Erpelding, Adrian Braemer, Martin Gärttner

Symmetries are a key tool in understanding quantum systems, and, among many other things, can be exploited to increase the efficiency of numerical simulations of quantum dynamics. Disordered systems usually feature reduced symmetries and additionally require averaging over many realizations, making their numerical study computationally demanding. However, when studying quantities linear in the time-evolved state, i.e., expectation values of observables, one can apply the averaging procedure to the time evolution operator, resulting in an effective dynamical map, which restores symmetry at the level of superoperators. In this work, we develop schemes for efficiently constructing symmetric sectors of the disorder-averaged dynamical map using short-time and weak-disorder expansions. To benchmark the method, we apply it to an Ising model with random all-to-all interactions in the presence of a transverse field. After disorder averaging, this system becomes effectively permutation-invariant, and thus the size of the symmetric subspace scales polynomially in the number of spins, allowing for the simulation of large systems.

arXiv:2507.09614•Physical review. B./Physical review. B•Apr 2, 2026•0 citations

Classical Algorithms for Hamiltonian Dynamics Mean Value and Guided Local Hamiltonian Problem

Yusen Wu, Yukun Zhang, Wang, Chuan +1 more

The efficient simulation of quantum dynamics and ground states is a central challenge in physics and a key frontier for quantum advantage. While short-time evolution in one-dimensional systems can often be simulated classically, extending this to higher dimensions remains difficult. Here, we introduce an efficient classical algorithm for simulating the short-time dynamics of arbitrary local quantum systems. For any local Hamiltonian $H$ and constant evolution time $t$, our method estimates expectation values of the form $\langleψ|e^{iHt}Oe^{-iHt}|ψ\rangle$ for global Pauli observables $O$ and stabilizer states $|ψ\rangle$, with high precision and exponentially small failure probability. Furthermore, we present a classical dequantization of a tailored quantum algorithm that efficiently solves the guided local Hamiltonian (GLH) problem to constant additive error - previously considered classically hard and hence a promising candidate for quantum computational advantage. These results reveal unexpected classical tractability in constant-time quantum dynamics and fundamental connections between Hamiltonian dynamics mean value and the GLH problem. Our work refines the boundary between classical and quantum computational power, identifying sharper criteria for regimes where quantum advantage may genuinely emerge.

arXiv:2409.04161•Sep 6, 2024•1 citation

Simulatability of locally-interacting open quantum spin systems

Rahul Trivedi, J. I. Cirac

We analyze the complexity of classically simulating the dynamics of locally interacting quantum spin systems with a constant rate of entanglement breaking noise. We show that for a system with $n$ spins, a polynomial time classical algorithm can be used to sample within a $O(1/\text{poly}(n))$ total-variation distance of the state of the spins when the rate of noise is sufficiently high. Furthermore, by encoding a 1D fault tolerant quantum computation into the dynamics of open quantum spin systems, we show that for certain physically relevant channels, the problem of sampling from the output state is BQP-complete in the low noise regime. Our results rigorously show the presence of phase transitions in the classical simulatability of the continuous time dynamics of open quantum spin systems.

•Oct 20, 2021•1 citation

An (almost) efficient classical algorithm for sampling from typical Gibbs states

Saleh Naghdi, Eric R. Anschuetz

Gibbs state preparation has emerged as a potential avenue for quantum advantage in the study of physical systems. Although there is known advantage for computing local properties of worst-case Gibbs states, recent results suggest a different picture for average-case local systems: at temperatures where their Gibbs states can be efficiently prepared quantumly, quasi-polynomial time classical algorithms can also compute local expectation values. Yet this leaves open the possibility of an advantage under a stronger notion of simulation: sampling. Gibbs sampling underlies Boltzmann machine-based quantum learning algorithms and quantum supremacy proposals, but its classical average-case complexity for physically relevant models remains unresolved. Here, we give strong evidence against an exponential quantum advantage in Gibbs sampling for an ensemble of local systems known as the quantum $p$-spin model. We describe a classical algorithm for sampling from the Gibbs state to any polynomially small error in total variation distance. Our algorithm is based on a meta-algorithm known as algorithmic stochastic localization (ASL). Our main technical result is a generalized convergence theorem for ASL which reduces approximate sampling from any distribution on the hypercube to estimating the mean of a related "tilted distribution" to sufficiently low additive error. We then extend known quasi-polynomial time algorithms for computing local expectation values of a related disordered model to compute these "tilted means" for the quantum $p$-spin model. Finally, we give a non-rigorous physics argument that this mean-estimation algorithm works down to the spin glass transition temperature. As efficient quantum algorithms also fail at this transition, this suggests they cannot Gibbs sample the quantum $p$-spin model at temperatures below that for which classical algorithms are also (almost) efficient.

quant-pharXiv:2609.40250•Oct 1, 2026•0 citations

Classical Simulation of Short-Time Quantum Dynamics

Dominik S. Wild, Alvaro Martin Alhambra

Recent progress in the development of quantum technologies has enabled the direct investigation of the dynamics of increasingly complex quantum many-body systems.This motivates the study of the complexity of classical algorithms for this problem in order to benchmark quantum simulators and to delineate the regime of quantum advantage.Here, we present classical algorithms for approximating the dynamics of local observables and nonlocal quantities such as the Loschmidt echo, where the evolution is governed by a local Hamiltonian.For short times, their computational cost scales polynomially with the system size and the inverse of the approximation error.In the case of local observables, the proposed algorithm has a better dependence on the approximation error than algorithms based on the Lieb-Robinson bound.Our results use cluster-expansion techniques adapted to the dynamical setting, for which we give a novel proof of their convergence.This has important physical consequences besides our efficient algorithms.In particular, we establish a novel quantum speed limit, a bound on dynamical phase transitions, and a concentration bound for product states evolved for short times.

arXiv:2210.11490•PRX Quantum•Jun 12, 2023•33 citations
We study both the classical and the quantum complexity of the problem of estimating disorder-averaged quench dynamics for all-to-all spin Hamiltonians such as quantum Hopfield, Sherrington--Kirkpatrick (SK) or Dicke-type models. Disorder averaging restores permutation invariance in this setting, so states of NNN spins can be stored in O(log⁡N)\mathcal O(\log N)O(logN) qubits. While logarithmic-space quantum computations are known to be simulatable classically in polynomial time or in polylogarithmic space, whether a single algorithm can achieve both is open, raising the possibility of simultaneous quantum advantage. To this end, we give a quantum algorithm for permutation-invariant kkk-local dynamics without disorder using polynomial time and O(log⁡N)\mathcal O(\log N)O(logN) quantum and classical space. We show that any classical algorithm matching these resources would imply BQL⊆SC\mathsf{BQL}\subseteq \mathsf{SC}BQL⊆SC. For short times, however, we provide such algorithms, including for SK models. For Hopfield models, we discuss how dilating the disorder to ancilla qubits reduces the problem to the disorder-free case on an enlarged system, thus extending both classical and quantum results to them. We give some evidence that their long-time dynamics are non-trivial. They thus emerge as a candidate for a simultaneous time--space advantage in quantum simulation.
The simulation of large-scale classical systems in exponentially small space on quantum computers has gained attention. The prior work demonstrated that a quantum algorithm offers an exponential speedup over any classical algorithm in simulating classical dynamics with long-range interactions. However, many real-world classical systems, such as those arising from partial differential equations, exhibit only local interactions. The question remains whether quantum algorithms can still provide exponential speedup under this condition. In this work, we thoroughly characterize the computational complexity of simulating such geometrically local systems on quantum computers. First, we dequantize the quantum algorithm for simulating short-time (polynomial-time) dynamics of such systems. This implies that the problem of simulating this dynamics does not yield any exponential quantum advantage. Second, we show that simulating short-time dynamics is at least as hard as polynomial-time and linear-space probabilistic classical computation. Third, we show that the computational complexity of simulating long-time (exponential-time) dynamics is captured by exponential-time and polynomial-space quantum computation. This suggests a super-polynomial time advantage when restricting the computation to polynomial-space, or an exponential space advantage otherwise. This work offers new insights into the complexity of classical dynamics governed by partial differential equations, providing a pathway for achieving quantum advantage in practical problems.
Symmetries are a key tool in understanding quantum systems, and, among many other things, can be exploited to increase the efficiency of numerical simulations of quantum dynamics. Disordered systems usually feature reduced symmetries and additionally require averaging over many realizations, making their numerical study computationally demanding. However, when studying quantities linear in the time-evolved state, i.e., expectation values of observables, one can apply the averaging procedure to the time evolution operator, resulting in an effective dynamical map, which restores symmetry at the level of superoperators. In this work, we develop schemes for efficiently constructing symmetric sectors of the disorder-averaged dynamical map using short-time and weak-disorder expansions. To benchmark the method, we apply it to an Ising model with random all-to-all interactions in the presence of a transverse field. After disorder averaging, this system becomes effectively permutation-invariant, and thus the size of the symmetric subspace scales polynomially in the number of spins, allowing for the simulation of large systems.
The efficient simulation of quantum dynamics and ground states is a central challenge in physics and a key frontier for quantum advantage. While short-time evolution in one-dimensional systems can often be simulated classically, extending this to higher dimensions remains difficult. Here, we introduce an efficient classical algorithm for simulating the short-time dynamics of arbitrary local quantum systems. For any local Hamiltonian HHH and constant evolution time ttt, our method estimates expectation values of the form ⟨ψ∣eiHtOe−iHt∣ψ⟩\langleψ|e^{iHt}Oe^{-iHt}|ψ\rangle⟨ψ∣eiHtOe−iHt∣ψ⟩ for global Pauli observables OOO and stabilizer states ∣ψ⟩|ψ\rangle∣ψ⟩, with high precision and exponentially small failure probability. Furthermore, we present a classical dequantization of a tailored quantum algorithm that efficiently solves the guided local Hamiltonian (GLH) problem to constant additive error - previously considered classically hard and hence a promising candidate for quantum computational advantage. These results reveal unexpected classical tractability in constant-time quantum dynamics and fundamental connections between Hamiltonian dynamics mean value and the GLH problem. Our work refines the boundary between classical and quantum computational power, identifying sharper criteria for regimes where quantum advantage may genuinely emerge.
We analyze the complexity of classically simulating the dynamics of locally interacting quantum spin systems with a constant rate of entanglement breaking noise. We show that for a system with nnn spins, a polynomial time classical algorithm can be used to sample within a O(1/poly(n))O(1/\text{poly}(n))O(1/poly(n)) total-variation distance of the state of the spins when the rate of noise is sufficiently high. Furthermore, by encoding a 1D fault tolerant quantum computation into the dynamics of open quantum spin systems, we show that for certain physically relevant channels, the problem of sampling from the output state is BQP-complete in the low noise regime. Our results rigorously show the presence of phase transitions in the classical simulatability of the continuous time dynamics of open quantum spin systems.
Gibbs state preparation has emerged as a potential avenue for quantum advantage in the study of physical systems. Although there is known advantage for computing local properties of worst-case Gibbs states, recent results suggest a different picture for average-case local systems: at temperatures where their Gibbs states can be efficiently prepared quantumly, quasi-polynomial time classical algorithms can also compute local expectation values. Yet this leaves open the possibility of an advantage under a stronger notion of simulation: sampling. Gibbs sampling underlies Boltzmann machine-based quantum learning algorithms and quantum supremacy proposals, but its classical average-case complexity for physically relevant models remains unresolved. Here, we give strong evidence against an exponential quantum advantage in Gibbs sampling for an ensemble of local systems known as the quantum ppp-spin model. We describe a classical algorithm for sampling from the Gibbs state to any polynomially small error in total variation distance. Our algorithm is based on a meta-algorithm known as algorithmic stochastic localization (ASL). Our main technical result is a generalized convergence theorem for ASL which reduces approximate sampling from any distribution on the hypercube to estimating the mean of a related "tilted distribution" to sufficiently low additive error. We then extend known quasi-polynomial time algorithms for computing local expectation values of a related disordered model to compute these "tilted means" for the quantum ppp-spin model. Finally, we give a non-rigorous physics argument that this mean-estimation algorithm works down to the spin glass transition temperature. As efficient quantum algorithms also fail at this transition, this suggests they cannot Gibbs sample the quantum ppp-spin model at temperatures below that for which classical algorithms are also (almost) efficient.
Recent progress in the development of quantum technologies has enabled the direct investigation of the dynamics of increasingly complex quantum many-body systems.This motivates the study of the complexity of classical algorithms for this problem in order to benchmark quantum simulators and to delineate the regime of quantum advantage.Here, we present classical algorithms for approximating the dynamics of local observables and nonlocal quantities such as the Loschmidt echo, where the evolution is governed by a local Hamiltonian.For short times, their computational cost scales polynomially with the system size and the inverse of the approximation error.In the case of local observables, the proposed algorithm has a better dependence on the approximation error than algorithms based on the Lieb-Robinson bound.Our results use cluster-expansion techniques adapted to the dynamical setting, for which we give a novel proof of their convergence.This has important physical consequences besides our efficient algorithms.In particular, we establish a novel quantum speed limit, a bound on dynamical phase transitions, and a concentration bound for product states evolved for short times.