Recognition: unknown
SYK thermal expectations are classically easy at any temperature
read the original abstract
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/\epsilon))}$ 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.
This paper has not been read by Pith yet.
Forward citations
Cited by 4 Pith papers
-
The free energy limit of the SYK model at high temperature
Rigorous high-temperature free energy limit for the SYK model established via random graph components and cavity method, matching physics heuristics.
-
A rigorous quasipolynomial-time classical algorithm for SYK thermal expectations
A rigorous quasipolynomial-time classical algorithm computes SYK local thermal expectations at high constant temperature using a new Wick-pair cluster expansion.
-
Rapid mixing for high-temperature Gibbs states with arbitrary external fields
High-temperature Gibbs states with arbitrary external fields admit O(log n) quantum mixing via a detailed-balance Lindbladian and exhibit classical sampling hardness for β < 1.
-
Quantum Gibbs sampling through the detectability lemma
Detectability lemma enables Gibbs sampling without Lindbladian simulation, yielding O(M) cost reduction for M-term local Lindbladians and quadratic speedup in spectral gap for frustration-free and commuting cases.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.