The Sachdev-Ye-Kitaev model is a system of N fermions with random all-to-all interactions, studied intensively because it is solvable in certain limits, maximally chaotic, and dual to a model of quantum gravity in two dimensions. Its thermal state at low temperature is highly entangled — preparing it on a quantum computer requires circuits of polynomial depth — and it exhibits a sign problem that makes naive classical Monte Carlo sampling exponentially costly. These properties have made it a candidate for quantum advantage: a physically motivated problem where quantum computers might outperform classical ones at computing thermal properties.
Zlokapa and Kiani (arXiv 2602.22619, February 2026) give a classical algorithm that computes thermal expectations of local observables in the SYK model at any constant temperature with quasi-polynomial cost — n raised to the power of O(log n), which is faster than any polynomial in n but slower than truly polynomial. The algorithm works despite the entanglement, despite the sign problem, and despite the circuit complexity lower bounds that say preparing the state on a quantum computer is unavoidably expensive.
The resolution is that computing expectations is not the same as preparing states. The thermal state of SYK may require deep circuits to prepare, but the numbers you want to extract from it — expectation values of local observables — can be accessed without ever constructing the state. The algorithm uses the replica trick from statistical mechanics: instead of computing the partition function directly, it analytically continues from integer numbers of replicas to extract the relevant quantities. The cost depends on controlling the complex zeros of the partition function, which the authors show are well-behaved in the SYK model above its phase transition.
The result applies more broadly than SYK. The algorithm works for any system at temperatures above a phase transition in the free energy, provided the system is in the fast-mixing phase where the quantum Gibbs sampler would also be efficient. This means the quantumly easy regime is also classically quasi-easy — quantum computers don't gain an advantage from the difficulty of the problem but only from the polynomial-vs-quasi-polynomial gap in the algorithm's cost. The advantage, if it exists, is quantitative rather than qualitative.
The sign problem deserves attention. A sign problem means the partition function involves cancellations between large positive and negative terms, making direct summation exponentially unstable. The conventional wisdom is that sign problems make classical computation exponentially hard. But sign problems are basis-dependent — they can appear or disappear depending on the representation — and their presence doesn't guarantee that all classical approaches fail. The replica trick sidesteps the sign problem entirely by working with the analytic structure of the partition function rather than sampling its terms.
The entanglement deserves equal attention. High entanglement in the thermal state is often cited as evidence of quantum advantage, because classical representations of highly entangled states require exponential resources. But computing an expectation value is not representing a state. A local observable probes a small part of the system, and its expectation value may be insensitive to the global entanglement structure. The entanglement is real. The classical difficulty it supposedly creates, for this particular task, is not.