arXiv:2609.40162
Classical and Quantum Simulation of All-to-All Quantum Dynamics in Logarithmic Space
Maximilian Lutz, Rahul Trivedi, J. Ignacio Cirac
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.
AI Summary
The paper asks whether disorder-averaged all-to-all spin dynamics admit quantum simulation in polynomial time and logarithmic space without a classical algorithm achieving both resource bounds simultaneously. It studies permutation-invariant collective-spin Hamiltonians, fixed-rank quantum Hopfield models, and Gaussian-disordered SK/$p$-spin models, primarily for local observables following product-state quenches. For disorder-free permutation-invariant dynamics at polynomial times, a quantum algorithm uses $O(\log N)$ qubits and classical workspace, with runtime polynomial in $N,t,1/\epsilon$ for fixed local dimension and locality. Occupation-number encoding compresses the symmetric subspace; matrix entries, Pauli coefficients, and simulation circuits are generated on demand in logarithmic space. An explicit compilation of logarithmic-qubit circuits into piecewise-constant, two-local collective-spin controls establishes conditional hardness: deterministic classical simulation in polynomial time and polylogarithmic space would imply $\mathsf{BQL}\subseteq\mathsf{SC}$. Classically, truncated evolution expansions permit computational-basis sampling for $t=O(\log N/N)$ in polynomial time and logarithmic space. Cluster expansions and analytic continuation yield the same resource bounds for local expectation values at any fixed $t=O(1)$ and constant error, including disorder-averaged SK/$p$-spin dynamics; the required expansion order grows as $e^{O(1+t^2)}\log(2/\epsilon)$ for fixed model parameters. Promoting each Hopfield pattern sign to an ancilla operator reduces rank-$r$ disorder averaging exactly to permutation-invariant dynamics with local dimension $2^{r+1}$, extending the quantum algorithm for fixed $r$. Hardness is established for controlled, time-dependent disorder-free models, not fixed Hopfield quenches. Long-time Hopfield advantage remains a candidate; no analogous long-time logarithmic-space quantum algorithm is provided for SK.
Central claim may not hold: The abstract does not disclose that its classical-hardness conclusion is proved only for piecewise-constant Hamiltonian schedules, rather than for the time-independent quench dynamics motivating the paper.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 19+7 pages