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

Fast mixing of the SYK model at high temperatures

Yiyi Cai, Yongtao Zhan, Alexander Zlokapa

quant-phcond-mat.dis-nncs.DSmath-phSubmitted Oct 5, 2026• Announced Oct 6, 2026• 4 citations• Revised Nov 3, 2026 (v2)
v1 · Oct 5, 2026v2 · Nov 3, 2026
arXivHTMLPDF

Abstract

The Sachdev-Ye-Kitaev (SYK) model is a strongly interacting fermionic system. Its dynamics are difficult to analyze with Lieb-Robinson bounds and cluster expansions due to its all-to-all disordered interactions. We prove that, with high probability over the disorder, the SYK model admits a quantum Gibbs sampler with a system-size-independent spectral gap at sufficiently high constant temperatures. This yields polynomial-time preparation of SYK Gibbs states on a quantum computer. While prior non-rigorous computations that suggested SYK thermalization were limited to studying local correlators, we emphasize that our result holds up to arbitrary inverse polynomial trace distance. Our proof introduces the pseudo-Lindbladian approach to fermions then applies two key new ideas: a Bochner inequality for quantum dynamics, and an especially simple SYK analysis based on a comparison to classical dynamics.

AI Summary

The paper asks whether SYK Gibbs states can be prepared efficiently with global trace-distance guarantees, despite dense random interactions that obstruct existing high-temperature mixing arguments. It studies an efficiently implementable, KMS-detailed-balanced quantum Gibbs sampler for the quartic Majorana SYK Hamiltonian, with coupling variance $6J^2/N^3$. For $0\leq\beta J\leq10^{-3}$, it proves that, with probability at least $1-2e^{-N}$ over disorder, the sampler has spectral gap at least $507/392>1$ and mixing time $O(N+\log(1/\epsilon))$ in trace norm, uniformly over initial states. These bounds use a generator normalized as a sum of $N$ dissipative terms, without a $1/N$ prefactor. Combined with existing implementation algorithms, this gives polynomial-time quantum preparation to inverse-polynomial trace-distance error. The proof extends pseudo-Lindbladian comparisons to fermions. A Clifford-derivative version of the integrated Bochner argument reduces an auxiliary spectral-gap bound to controlling the Jacobian of imaginary-time-evolved Majoranas. Disorder-averaged moments of its Taylor coefficients are bounded by those of an auxiliary classical quartic spin-glass gradient flow; Gaussian concentration and polynomial derivative estimates then give operator-norm bounds. Related estimates control Gaussian filtering and transfer the gap to the implementable sampler. The guarantee applies only at sufficiently high constant temperature, not throughout SYK’s temperature range, and concerns a designed sampler rather than intrinsic Hamiltonian thermalization. Mixing of order $O(\log N+\log(1/\epsilon))$ remains open. The paper also leaves open quantum advantage, possible classical representations or dequantization, and extensions to other strongly interacting fermionic models.

No sign of AI-generated textAI use disclosed
The main idea behind the proven theorem statement was proposed by ChatGPT 6.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
34 pages; v2 improves exposition and updates references

Related papers

A rigorous quasipolynomial-time classical algorithm for SYK thermal expectations

Alexander Zlokapa

Estimating local observables in Gibbs states is a central problem in quantum simulation. While this task is BQP-complete at asymptotically low temperatures, the possibility of quantum advantage at constant temperature remains open. The Sachdev-Ye-Kitaev (SYK) model is a natural candidate: at any constant temperature, its Gibbs states have polynomial quantum circuit complexity and are not described by Gaussian states. Rigorous analyses of the SYK model are difficult due to the failure of known techniques using random matrix theory, cluster expansions, and rigorous formulations of the quantum path integral and replica trick. Despite this, we give a rigorous proof of a quasipolynomial-time classical algorithm that estimates SYK local thermal expectations at sufficiently high constant temperature. Our result introduces a new Wick-pair cluster expansion that we expect to be broadly useful for disordered quantum many-body systems.

quant-pharXiv:2604.21089•Apr 24, 2026•14 citations

Learning SYK Hamiltonians

Anurag Anshu, Srinivasan Arunachalam, Sitan Chen +1 more

We study the problem of learning the dense Sachdev--Ye--Kitaev (SYK) Hamiltonian from copies of its Gibbs state. Existing algorithms for Hamiltonian learning typically rely on geometric locality or bounded interaction degree and therefore do not apply to SYK, where each quartic interaction overlaps with $Θ(n^3)$ others. We show that this obstruction can be overcome by exploiting the random mean-field structure of the model. At any constant temperature, we prove that with high probability over the SYK couplings, the entire Hamiltonian can be learned to inverse-polynomial accuracy using polynomially many samples. Furthermore, when the inverse temperature is restricted to be a sufficiently small constant, we construct a quasipolynomial-time learning algorithm which is qualitatively different from the sample-efficient algorithm.

quant-pharXiv:2610.02178•Oct 2, 2026•2 citations

Polynomial-time classical algorithms for mean-field models up to the glass transition

Alexander Schmidhuber, Alexander Zlokapa

The Sachdev-Ye-Kitaev model is a strongly interacting fermionic system that has been well-studied in condensed matter and high energy physics. It is highly quantum: Gaussian states are far from the thermal state (Hastings and O'Donnell, STOC'22) and representing the thermal state requires large polynomial-size quantum circuits (Anschuetz et al., QIP'25). Very recently, it was nonetheless proven that classical algorithms can estimate local thermal expectations at sufficiently high temperature in quasipolynomial time (Zlokapa, FOCS'26). We show that classical algorithms can in fact estimate local observables at all constant temperatures in polynomial time. Our techniques also extend straightforwardly to classical systems: we resolve an open question about computing thermal expectations of a classical spin glass up to its phase transition (Bencs et al., STOC'26). Our proof develops a fully rigorous quantum cavity method. Due to the success of the classical cavity method in optimization, sampling, inference and learning, we expect the quantum cavity method to find further applications of independent interest. As an example, we give a quantum algorithm that learns SYK Hamiltonians from the Gibbs state at any constant temperature with polynomial time and sample complexity.

quant-pharXiv:2610.06807•Oct 6, 2026•4 citations

Rapid Mixing of Quantum Gibbs Samplers for Weakly-Interacting Quantum Systems

Štěpán Šmíd, Meister, Richard, Mario Berta +1 more

Dissipative quantum algorithms for state preparation in many-body systems are increasingly recognised as promising candidates for achieving large quantum advantages in application-relevant tasks. Recent advances in algorithmic, detailed-balance Lindbladians enable the efficient simulation of open-system dynamics converging towards desired target states. However, the overall complexity of such schemes is governed by system-size dependent mixing times. In this work, we analyse algorithmic Lindbladians for Gibbs state preparation and prove that they exhibit rapid mixing, i.e., convergence in time poly-logarithmic in the system size. We first establish this for non-interacting spin systems, free fermions, and free bosons, and then show that these rapid mixing results are stable under perturbations, covering weakly interacting qudits and perturbed non-hopping fermions. Further, we adapt the techniques from separable qudits to the fermionic setting and prove rapid mixing of the strongly-interacting regime of the Fermi-Hubbard model, for which we also explicitly evaluate the guaranteed parameter regimes. Our results constitute the first efficient mixing bounds for non-commuting qudit models and bosonic systems at arbitrary temperatures. Compared to prior spectral-gap-based results for fermions, we achieve exponentially faster mixing, further featuring explicit constants on the maximal allowed interaction strength. This not only improves the overall polynomial runtime for quantum Gibbs state preparation, but also enhances robustness against noise. Our analysis relies on oscillator norm techniques from mathematical physics, where we introduce tailored variants adapted to specific Lindbladians $\unicode{x2014}$ an innovation that we expect to significantly broaden the scope of these methods.

arXiv:2510.04954•Oct 6, 2025•29 citations

Fast mixing of all-to-all quantum systems at high temperatures

Thiago Bergamaschi

It is shown that arbitrary quantum $k$-local Hamiltonians with bounded strength interactions admit a quantum Gibbs sampler [CKG23] with a system-size independent spectral gap, at sufficiently high temperatures. As a consequence, such systems admit fully-polynomial time quantum approximation algorithms for partition functions and global expectation values.

quant-pharXiv:2606.26090•Jun 25, 2026•19 citations

SYK thermal expectations are classically easy at any temperature

Alexander Zlokapa, Bobak T. Kiani

Estimating thermal expectations of local observables is a natural target for quantum advantage. We give a simple classical algorithm that approximates thermal expectations for Gibbs states of local Hamiltonians, and we show it has quasi-polynomial cost $n^{O(\log (n/ε))}$ for all temperatures above a phase transition in the free energy. For many natural models, this coincides with the entire fast-mixing, quantumly easy phase. Our results apply to the Sachdev-Ye-Kitaev (SYK) model at any constant temperature due to its absence of a phase transition -- despite its entanglement, sign problem, and polynomial quantum circuit lower bounds. Beyond SYK, we rigorously establish a universal classically easy high-temperature phase for all local, bounded-degree Hamiltonians and show that it extends to temperatures strictly colder than the death of entanglement transition.

quant-pharXiv:2602.22619•Feb 27, 2026•16 citations
The Sachdev-Ye-Kitaev (SYK) model is a strongly interacting fermionic system. Its dynamics are difficult to analyze with Lieb-Robinson bounds and cluster expansions due to its all-to-all disordered interactions. We prove that, with high probability over the disorder, the SYK model admits a quantum Gibbs sampler with a system-size-independent spectral gap at sufficiently high constant temperatures. This yields polynomial-time preparation of SYK Gibbs states on a quantum computer. While prior non-rigorous computations that suggested SYK thermalization were limited to studying local correlators, we emphasize that our result holds up to arbitrary inverse polynomial trace distance. Our proof introduces the pseudo-Lindbladian approach to fermions then applies two key new ideas: a Bochner inequality for quantum dynamics, and an especially simple SYK analysis based on a comparison to classical dynamics.
The paper asks whether SYK Gibbs states can be prepared efficiently with global trace-distance guarantees, despite dense random interactions that obstruct existing high-temperature mixing arguments. It studies an efficiently implementable, KMS-detailed-balanced quantum Gibbs sampler for the quartic Majorana SYK Hamiltonian, with coupling variance 6J2/N36J^2/N^36J2/N3.
For 0≤βJ≤10−30\leq\beta J\leq10^{-3}0≤βJ≤10−3, it proves that, with probability at least 1−2e−N1-2e^{-N}1−2e−N over disorder, the sampler has spectral gap at least 507/392>1507/392>1507/392>1 and mixing time O(N+log⁡(1/ϵ))O(N+\log(1/\epsilon))O(N+log(1/ϵ)) in trace norm, uniformly over initial states. These bounds use a generator normalized as a sum of NNN dissipative terms, without a 1/N1/N1/N prefactor. Combined with existing implementation algorithms, this gives polynomial-time quantum preparation to inverse-polynomial trace-distance error.
The proof extends pseudo-Lindbladian comparisons to fermions. A Clifford-derivative version of the integrated Bochner argument reduces an auxiliary spectral-gap bound to controlling the Jacobian of imaginary-time-evolved Majoranas. Disorder-averaged moments of its Taylor coefficients are bounded by those of an auxiliary classical quartic spin-glass gradient flow; Gaussian concentration and polynomial derivative estimates then give operator-norm bounds. Related estimates control Gaussian filtering and transfer the gap to the implementable sampler.
The guarantee applies only at sufficiently high constant temperature, not throughout SYK’s temperature range, and concerns a designed sampler rather than intrinsic Hamiltonian thermalization. Mixing of order O(log⁡N+log⁡(1/ϵ))O(\log N+\log(1/\epsilon))O(logN+log(1/ϵ)) remains open. The paper also leaves open quantum advantage, possible classical representations or dequantization, and extensions to other strongly interacting fermionic models.
Estimating local observables in Gibbs states is a central problem in quantum simulation. While this task is BQP-complete at asymptotically low temperatures, the possibility of quantum advantage at constant temperature remains open. The Sachdev-Ye-Kitaev (SYK) model is a natural candidate: at any constant temperature, its Gibbs states have polynomial quantum circuit complexity and are not described by Gaussian states. Rigorous analyses of the SYK model are difficult due to the failure of known techniques using random matrix theory, cluster expansions, and rigorous formulations of the quantum path integral and replica trick. Despite this, we give a rigorous proof of a quasipolynomial-time classical algorithm that estimates SYK local thermal expectations at sufficiently high constant temperature. Our result introduces a new Wick-pair cluster expansion that we expect to be broadly useful for disordered quantum many-body systems.
We study the problem of learning the dense Sachdev--Ye--Kitaev (SYK) Hamiltonian from copies of its Gibbs state. Existing algorithms for Hamiltonian learning typically rely on geometric locality or bounded interaction degree and therefore do not apply to SYK, where each quartic interaction overlaps with Θ(n3)Θ(n^3)Θ(n3) others. We show that this obstruction can be overcome by exploiting the random mean-field structure of the model. At any constant temperature, we prove that with high probability over the SYK couplings, the entire Hamiltonian can be learned to inverse-polynomial accuracy using polynomially many samples. Furthermore, when the inverse temperature is restricted to be a sufficiently small constant, we construct a quasipolynomial-time learning algorithm which is qualitatively different from the sample-efficient algorithm.
The Sachdev-Ye-Kitaev model is a strongly interacting fermionic system that has been well-studied in condensed matter and high energy physics. It is highly quantum: Gaussian states are far from the thermal state (Hastings and O'Donnell, STOC'22) and representing the thermal state requires large polynomial-size quantum circuits (Anschuetz et al., QIP'25). Very recently, it was nonetheless proven that classical algorithms can estimate local thermal expectations at sufficiently high temperature in quasipolynomial time (Zlokapa, FOCS'26). We show that classical algorithms can in fact estimate local observables at all constant temperatures in polynomial time. Our techniques also extend straightforwardly to classical systems: we resolve an open question about computing thermal expectations of a classical spin glass up to its phase transition (Bencs et al., STOC'26). Our proof develops a fully rigorous quantum cavity method. Due to the success of the classical cavity method in optimization, sampling, inference and learning, we expect the quantum cavity method to find further applications of independent interest. As an example, we give a quantum algorithm that learns SYK Hamiltonians from the Gibbs state at any constant temperature with polynomial time and sample complexity.
Dissipative quantum algorithms for state preparation in many-body systems are increasingly recognised as promising candidates for achieving large quantum advantages in application-relevant tasks. Recent advances in algorithmic, detailed-balance Lindbladians enable the efficient simulation of open-system dynamics converging towards desired target states. However, the overall complexity of such schemes is governed by system-size dependent mixing times. In this work, we analyse algorithmic Lindbladians for Gibbs state preparation and prove that they exhibit rapid mixing, i.e., convergence in time poly-logarithmic in the system size. We first establish this for non-interacting spin systems, free fermions, and free bosons, and then show that these rapid mixing results are stable under perturbations, covering weakly interacting qudits and perturbed non-hopping fermions. Further, we adapt the techniques from separable qudits to the fermionic setting and prove rapid mixing of the strongly-interacting regime of the Fermi-Hubbard model, for which we also explicitly evaluate the guaranteed parameter regimes. Our results constitute the first efficient mixing bounds for non-commuting qudit models and bosonic systems at arbitrary temperatures. Compared to prior spectral-gap-based results for fermions, we achieve exponentially faster mixing, further featuring explicit constants on the maximal allowed interaction strength. This not only improves the overall polynomial runtime for quantum Gibbs state preparation, but also enhances robustness against noise. Our analysis relies on oscillator norm techniques from mathematical physics, where we introduce tailored variants adapted to specific Lindbladians $\unicode{x2014}$ an innovation that we expect to significantly broaden the scope of these methods.
It is shown that arbitrary quantum kkk-local Hamiltonians with bounded strength interactions admit a quantum Gibbs sampler [CKG23] with a system-size independent spectral gap, at sufficiently high temperatures. As a consequence, such systems admit fully-polynomial time quantum approximation algorithms for partition functions and global expectation values.
Estimating thermal expectations of local observables is a natural target for quantum advantage. We give a simple classical algorithm that approximates thermal expectations for Gibbs states of local Hamiltonians, and we show it has quasi-polynomial cost nO(log⁡(n/ε))n^{O(\log (n/ε))}nO(log(n/ε)) for all temperatures above a phase transition in the free energy. For many natural models, this coincides with the entire fast-mixing, quantumly easy phase. Our results apply to the Sachdev-Ye-Kitaev (SYK) model at any constant temperature due to its absence of a phase transition -- despite its entanglement, sign problem, and polynomial quantum circuit lower bounds. Beyond SYK, we rigorously establish a universal classically easy high-temperature phase for all local, bounded-degree Hamiltonians and show that it extends to temperatures strictly colder than the death of entanglement transition.