Classical and Quantum Simulation of All-to-All Quantum Dynamics in Logarithmic Space
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 𝒪(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 𝒪(log N) quantum and classical space. We show that any classical algorithm matching these resources would imply 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.
Related
- Classical and Quantum Dynamics in State Space: Projective Hilbert Space, Measurement, and Classical Emergence
- A Validation Framework for Quantum Simulation of Spin Dynamics against Inelastic Neutron Scattering and Classical Simulation
- Dissipation accelerates quantum and classical simulation of open-system dynamics
- Logarithmic-depth quantum simulation of boson sampling
- Simulation of quantum entangled states by classical probabilistic models
BibTeX
@misc{lutz2026classical,
title = {{Classical and Quantum Simulation of All-to-All Quantum Dynamics in Logarithmic Space}},
author = {Maximilian Lutz and Rahul Trivedi and J. Ignacio Cirac},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.40162},
eprint = {2609.40162},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.40162},
}
RIS
TY - UNPB
TI - Classical and Quantum Simulation of All-to-All Quantum Dynamics in Logarithmic Space
AU - Maximilian Lutz
AU - Rahul Trivedi
AU - J. Ignacio Cirac
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.40162
UR - https://arxiv.org/abs/2609.40162
AB - 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 𝒪(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 𝒪(log N) quantum and classical space. We show that any classical algorithm matching these resources would imply 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.
ER -