A rigorous quasipolynomial-time classical algorithm for SYK thermal expectations
- URL: http://arxiv.org/abs/2604.21089v1
- Date: Wed, 22 Apr 2026 21:14:04 GMT
- Title: A rigorous quasipolynomial-time classical algorithm for SYK thermal expectations
- Abstract summary: Estimating local observables in Gibbs states is a central problem in quantum simulation.<n>We give a proof of a quasipolynomial-time classical algorithm that estimates SYK local thermal expectations at sufficiently high constant temperature.<n>Our result introduces a new Wick-pair expansion that we expect to be broadly useful for quantum many-body systems.
- Score: 51.660331450043806
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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.
Related papers
- SYK thermal expectations are classically easy at any temperature [49.788604174558564]
We give a simple classical algorithm that approximates thermal expectations.<n>We show it has quasi-polynomial cost $nO(log n/)$ for all temperatures above a phase transition in the free energy.
arXiv Detail & Related papers (2026-02-26T04:48:32Z) - Nonlinear quantum Kibble-Zurek ramps in open systems at finite temperature [0.0]
We analyze quantum systems under a broad class of protocols in which the temperature and a Hamiltonian control parameter are ramped simultaneously and, in general, in a nonlinear fashion toward a quantum critical point.<n>We show that, unlike finite-temperature protocols at fixed temperature, these protocols allow us to probe, in an out-of-equilibrium situation and at finite temperature.<n>Key to this is the identification of ramps in which both coherent excitation incoherent parts of the open-system dynamics affect the density in a non-negligible way.
arXiv Detail & Related papers (2026-01-15T14:51:20Z) - Krylov complexity as an order parameter for quantum chaotic-integrable transitions [0.0]
Krylov complexity has emerged as a new paradigm to characterize quantum chaos in many-body systems.<n>Recent insights have revealed that in quantum chaotic systems Krylov state complexity exhibits a distinct peak during time evolution.<n>We propose that this Krylov complexity peak (KCP) is a hallmark of quantum chaotic systems and suggest that its height could serve as an order parameter' for quantum chaos.
arXiv Detail & Related papers (2024-07-24T07:32:27Z) - Quantum computational advantage with constant-temperature Gibbs sampling [1.1930434318557157]
A quantum system coupled to a bath at some fixed, finite temperature converges to its Gibbs state.
This thermalization process defines a natural, physically-motivated model of quantum computation.
We consider sampling from the measurement outcome distribution of quantum Gibbs states at constant temperatures.
arXiv Detail & Related papers (2024-04-23T00:29:21Z) - Robust Extraction of Thermal Observables from State Sampling and
Real-Time Dynamics on Quantum Computers [49.1574468325115]
We introduce a technique that imposes constraints on the density of states, most notably its non-negativity, and show that this way, we can reliably extract Boltzmann weights from noisy time series.
Our work enables the implementation of the time-series algorithm on present-day quantum computers to study finite temperature properties of many-body quantum systems.
arXiv Detail & Related papers (2023-05-30T18:00:05Z) - Quantum Thermal State Preparation [39.91303506884272]
We introduce simple continuous-time quantum Gibbs samplers for simulating quantum master equations.
We construct the first provably accurate and efficient algorithm for preparing certain purified Gibbs states.
Our algorithms' costs have a provable dependence on temperature, accuracy, and the mixing time.
arXiv Detail & Related papers (2023-03-31T17:29:56Z) - Universality of critical dynamics with finite entanglement [68.8204255655161]
We study how low-energy dynamics of quantum systems near criticality are modified by finite entanglement.
Our result establishes the precise role played by entanglement in time-dependent critical phenomena.
arXiv Detail & Related papers (2023-01-23T19:23:54Z) - Probing finite-temperature observables in quantum simulators of spin
systems with short-time dynamics [62.997667081978825]
We show how finite-temperature observables can be obtained with an algorithm motivated from the Jarzynski equality.
We show that a finite temperature phase transition in the long-range transverse field Ising model can be characterized in trapped ion quantum simulators.
arXiv Detail & Related papers (2022-06-03T18:00:02Z) - Fast Thermalization from the Eigenstate Thermalization Hypothesis [69.68937033275746]
Eigenstate Thermalization Hypothesis (ETH) has played a major role in understanding thermodynamic phenomena in closed quantum systems.
This paper establishes a rigorous link between ETH and fast thermalization to the global Gibbs state.
Our results explain finite-time thermalization in chaotic open quantum systems.
arXiv Detail & Related papers (2021-12-14T18:48:31Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.