REVIEW
Classical and Quantum Simulation of All-to-All Quantum Dynamics in Logarithmic Space
Quantum Physics · Submitted 30 Sep 2026 · 29 references
Pith's verdict: Two real advances (log-space compressed quantum simulation with on-the-fly gate generation, and a cluster expansion pushed to all-to-all degree) with a conditional hardness reduction that survives re-derivation; the one concrete defect is a constant-factor typo in the ancilla dimension, not a load-bearing failure.
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
Disorder averaging compresses N-spin quench dynamics to O(log N) qubits, where a classical log-space match would imply BQL ⊆ SC.
The reading
What carries the argument
Three mechanisms carry the argument. First, the compressed encoding: the occupation numbers n = (n₀, …, n_{χ−1}) of the symmetric subspace are stored as binary numbers in (χ−1)⌈log₂(N+1)⌉ qubits, and the partial isometry V maps labels to Dicke states |n⟩_N, so a permutation-invariant Hamiltonian H and observable O become small matrices h = V†HV and o = V†OV. Second, logarithmic-space element access: every entry of h and o is computed on the fly as a sum over at most $χ^{{2k}}$ single-site move paths (Lemmas 2 and 3), each Pauli coefficient α_P = tr(Pa)/Q is accumulated without ever storing the matrix (Lemma 4), and a first-order product formula emits a stream of Pauli rotations from a log-space controller (Lemma 5). Third, the hardness side rests on selective resonance pulses: a two-local permutation-invariant Hamiltonian N(h_x m_x + h_y m_y + h_z m_z + m_z²/4) applied for τ = 8πNR realises a rotation of one adjacent pair of Dicke states exactly in the resonance limit (Lemma 7), and routing past signed swaps (Lemma 9) lets any logarithmic-qubit circuit be compiled into a piecewise-constant schedule (Lemma 6). For the fixed-rank disorder (quantum Hopfield) regime, replacing disorder signs v_{iℓ} by ancilla Pauli operators σ^z_{iℓ} reduces the problem to the disorder-free case on qudits of local dimension χ = 2r+1 (Lemma 1), and a cluster expansion with Gaussian integration by parts and analytic continuation (Lemmas 13 and 14) delivers the constant-time classical results.
Extended reading notes
Core claim
The central claim is that permutation-invariant, all-to-all k-local quantum dynamics, including disorder-averaged Dicke, quantum Hopfield, and short-time Sherrington–Kirkpatrick models, can be simulated using only O(log N) qubits and logarithmic classical workspace in polynomial time, and that this regime is conditionally hard for classical algorithms. The compression is made constructive: entries of the compressed Hamiltonian and observable on the symmetric subspace are computed on the fly in logarithmic space (Lemmas 2 and 3), the compressed operators are expanded into Pauli strings that are never stored but generated one at a time (Lemmas 4 and 5), and the time evolution is realised as a gate stream emitted by a logarithmic-space classical controller (Theorem 1). Complementing the algorithm, the authors prove that simulating such dynamics is at least as hard as running an arbitrary logarithmic-qubit quantum circuit under polynomial-time, logarithmic-space reductions; a classical algorithm meeting the same time and space bounds would therefore imply BQL ⊆ SC (or BQL = BPL for log-space randomised algorithms), as stated in Theorem 2. For short evolution times the situation differs: sampling is classically simulable up to t = O(log N/N) and expectation values to constant accuracy at t = O(1), and the same bounds cover fixed-rank disorder through the ancilla-dilation reduction of Lemma 1. The claim, in one line: disorder averaging compresses N-spin dynamics into logarithmic space, and no classical algorithm is known to match that compression in both time and space simultaneously.
Load-bearing premise
The conditional hardness claim rests on the explicit compilation of Lemma 6, in which an arbitrary logarithmic-qubit quantum circuit must be turned, in polynomial time and logarithmic classical workspace, into a piecewise-constant schedule of two-local permutation-invariant Hamiltonians whose evolution reproduces the circuit in the Dicke encoding; this compilation inherits the resonance condition τ μ_n ∈ 2πZ of Lemma 7, which forces pulse lengths τ = 8πNR with R ≥ 4N n_PR/η, and if the exact match between the selected resonant transition and all detuned integer cycles fails, the reduction and with it the BQL-hardness claim collapse.
Editorial extensions
If this is right
- Theorem 1 gives a bounded-error quantum algorithm that estimates disorder-averaged dynamics of permutation-invariant k-local Hamiltonians, including piecewise-constant schedules, in polynomial time with simultaneously O(log N) qubits and O(log N) bits of classical workspace.
- Theorem 2 makes the classical side conditional: a deterministic classical algorithm with polynomial time and polylog space would imply BQL ⊆ SC, and a log-space randomised one would imply BQL = BPL, so the problem is a candidate for a simultaneous time-space quantum advantage rather than a mere compression.
- Theorems 3 and 4 delimit the short-time classical regime — sampling up to t = O(log N/N) and constant-accuracy expectation values at t = O(1) — so the advantage, if it exists, sets in only at longer polynomial times and inverse-polynomial accuracy.
- Theorems 5–7 transfer both the quantum and classical results to quantum Hopfield models through the ancilla dilation of Lemma 1, at the price of local dimension χ = 2r+1.
- Theorem 8 covers p-spin and Sherrington–Kirkpatrick models at constant times classically, leaving only the long-time, high-precision regime as the open candidate for advantage.
Reading between the lines
- The conditional nature of Theorem 2 is load-bearing: if BQL ⊆ SC were settled in the affirmative, the paper's results would still provide an efficient logarithmic-space quantum compression but no advantage, so the interest of the problem is tied to the unresolved BQL versus SC question.
- The r = 1 gauge transformation of Section III G shows long-time Hopfield magnetisation revives at t = πN/(4µ₁), strong qualitative evidence that the long-time regime the classical algorithms cannot reach is genuinely structured — a testable prediction.
- One testable extension is whether the logarithmic-space classical short-time results survive for rank r growing with N, which would sharpen the boundary between the classically simulable and potentially advantaged regimes.
Original 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.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | 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. | contribution 0.65 | 0.72 | 0.05 | asserted 0.85 |
| s1 | Disorder averaging restores permutation invariance in this setting, so states of $N$ spins can be stored in $\mathcal O(\log N)$ qubits. | background 0.81 | 0.32 | 0.05 | asserted 1.00 |
| s2 | 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. | gap 0.98 | 0.07 | 0.08 | hedged possibility 0.54 |
| s3 | 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. | contribution 0.95 | 0.96 | 0.25 | asserted 1.00 |
| s4 | We show that any classical algorithm matching these resources would imply $\mathsf{BQL}\subseteq \mathsf{SC}$. | interpretation 0.74 | 0.83 | 0.17 | asserted 1.00 |
| s5 | For short times, however, we provide such algorithms, including for SK models. | limitation 0.58 | 0.93 | 0.10 | asserted 0.99 |
| s6 | 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. | method 0.64 | 0.86 | 0.06 | asserted 0.66 |
| s7 | We give some evidence that their long-time dynamics are non-trivial. | result 0.84 | 0.76 | 0.07 | hedged possibility 0.93 |
| s8 | They thus emerge as a candidate for a simultaneous time--space advantage in quantum simulation. | interpretation 1.00 | 0.53 | 0.54 | hedged possibility 0.72 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
Figures
Figures reproduced from arXiv:2609.40162 by the authors.
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.