REVIEW 6 cited by
Polynomial-time classical sampling of high-temperature quantum Gibbs states
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
The computational complexity of simulating quantum many-body systems generally scales exponentially with the number of particles. This enormous computational cost prohibits first principles simulations of many important problems throughout science, ranging from simulating quantum chemistry to discovering the thermodynamic phase diagram of quantum materials or high-density neutron stars. We present a classical algorithm that samples from a high-temperature quantum Gibbs state in a computational (product state) basis. The runtime grows polynomially with the number of particles, while error vanishes polynomially. This algorithm provides an alternative strategy to existing quantum Monte Carlo methods for overcoming the sign problem. Our result implies that measurement-based quantum computation on a Gibbs state can provide exponential speed up only at sufficiently low temperature, and further constrains what tasks can be exponentially faster on quantum computers.
Forward citations
Cited by 6 Pith papers
-
When quantum thermal states look classical
Long-range Pauli Gibbs states lose entanglement, magic, and infinite-temperature analyticity at distinct constant inverse temperatures Θ(1/sk), Θ(log(1/ε)/sk), and Θ(1/s√k), with matching classical algorithms.
-
Exponential Lindbladian fast forwarding and exponential amplification of certain Gibbs state properties
Quantum algorithms achieve exponential fast-forwarding for structured Lindbladian dynamics and coherence-dependent exponential speedup in Gibbs state property estimation.
-
Post-measurement Quantum Monte Carlo
Post-measurement SSE QMC is introduced to study measurement effects on thermal states of the square-lattice Heisenberg antiferromagnet, showing efficient computation of Bell pairs and enhanced antiferromagnetic correl...
-
Fast mixing of all-to-all quantum systems at high temperatures
k-local quantum Hamiltonians admit system-size-independent spectral gap for Gibbs samplers at high temperature, enabling FPT quantum approximation algorithms for partition functions.
-
Dissipative Quantum Multiplicative Weights with Sampling Feedback: A Classically Hard Primitive Realized via Engineered Open-System Dynamics
DQMW-Sample realizes a classically hard online learning primitive via dissipative quantum dynamics with sublinear regret and proven hardness for classical simulation including PH collapse.
-
Efficient Algorithms for Weakly-Interacting Quantum Spin Systems
A cluster-expansion FPTAS for the partition function and an approximate sampler for weakly-interacting quantum spin systems at arbitrary temperature are claimed, but a key bound in the proof fails.
Discussion (0). Sign in to comment.