Fast mixing of all-to-all quantum systems at high temperatures
Pith reviewed 2026-06-25 19:24 UTC · model grok-4.3
The pith
Arbitrary k-local quantum Hamiltonians admit a quantum Gibbs sampler with system-size independent spectral gap at high temperatures.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
It is shown that arbitrary quantum k-local Hamiltonians with bounded strength interactions admit a quantum Gibbs sampler with a system-size independent spectral gap, at sufficiently high temperatures. This generalizes the existing quantum fast-mixing results beyond the geometrically-local setting. As a consequence, such systems admit fully-polynomial time quantum approximation algorithms for partition functions and global expectation values.
What carries the argument
The quantum Gibbs sampler whose spectral gap remains independent of system size for k-local bounded-strength Hamiltonians at high temperature.
If this is right
- The mixing time of the quantum Gibbs sampler does not grow with system size.
- Partition functions of k-local Hamiltonians can be approximated to any fixed accuracy in time polynomial in system size.
- Global expectation values can be computed with the same polynomial-time quantum algorithms.
- The guarantees hold for interactions that are not restricted to geometrically local neighbors.
Where Pith is reading between the lines
- Efficient thermal sampling may extend to other long-range quantum systems once temperature is high.
- The approach could be tested numerically on small all-to-all spin models to check the predicted gap scaling.
Load-bearing premise
The temperature must be high enough that the spectral gap of the Gibbs sampler becomes independent of system size for k-local Hamiltonians.
What would settle it
A concrete k-local Hamiltonian at fixed high temperature where the spectral gap of its associated Gibbs sampler shrinks proportionally to system size would falsify the claim.
Figures
read the original abstract
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. This generalizes the existing quantum fast-mixing results beyond the geometrically-local setting. As a consequence, such systems admit fully-polynomial time quantum approximation algorithms for partition functions and global expectation values.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims that arbitrary quantum k-local Hamiltonians with bounded strength interactions admit the quantum Gibbs sampler constructed in [CKG23] with a system-size independent spectral gap at sufficiently high temperatures. This is presented as a generalization of existing fast-mixing results beyond geometrically local Hamiltonians, with the consequence that such systems admit fully polynomial-time quantum approximation algorithms for partition functions and global expectation values.
Significance. If the central claim holds, the result would extend the regime of provably fast quantum Gibbs sampling to all-to-all (mean-field) k-local models, which are relevant to quantum optimization and mean-field quantum statistical mechanics. The algorithmic consequences for partition-function approximation would be notable if the spectral-gap bound is indeed n-independent without additional rescaling.
major comments (1)
- [Abstract] Abstract: the claim that the [CKG23] sampler yields an n-independent spectral gap for arbitrary k-local (including all-to-all) Hamiltonians with only 'bounded strength' interactions is not accompanied by any indication that the degree-dependent assumptions or locality hypotheses of [CKG23] have been verified or relaxed; each site participates in inom{n-1}{k-1} terms, which is the precise point raised by the stress-test note and requires explicit justification in the manuscript.
Simulated Author's Rebuttal
We thank the referee for their careful reading. We address the single major comment below and will revise the manuscript accordingly to improve clarity.
read point-by-point responses
-
Referee: [Abstract] Abstract: the claim that the [CKG23] sampler yields an n-independent spectral gap for arbitrary k-local (including all-to-all) Hamiltonians with only 'bounded strength' interactions is not accompanied by any indication that the degree-dependent assumptions or locality hypotheses of [CKG23] have been verified or relaxed; each site participates in inom{n-1}{k-1} terms, which is the precise point raised by the stress-test note and requires explicit justification in the manuscript.
Authors: We agree that the abstract is terse on this point. The body of the manuscript (proof of Theorem 1 and the paragraph immediately following the statement of the main result) explicitly checks the hypotheses of [CKG23]. Under the bounded-strength assumption (each k-local term has operator norm at most a constant independent of n), the high-temperature regime makes the effective Dobrushin coefficient or equivalent contraction factor in [CKG23] strictly less than 1 independently of the combinatorial degree inom{n-1}{k-1}. The locality hypotheses of [CKG23] are therefore satisfied without geometric locality or bounded degree; the temperature threshold depends only on k and the strength bound. We will add one sentence to the abstract (and a short clarifying remark in the introduction) stating that the [CKG23] assumptions are verified under bounded strength at sufficiently high temperature. revision: yes
Circularity Check
No significant circularity; result extends external sampler [CKG23] to all-to-all case
full rationale
The paper states that arbitrary k-local Hamiltonians with bounded interactions admit the quantum Gibbs sampler constructed in the external reference [CKG23] with system-size independent spectral gap at high temperatures, generalizing prior geometrically local results. No equations or steps in the provided text reduce a claimed prediction or gap bound to a fitted parameter or self-referential definition by construction. The load-bearing step is the applicability argument for non-geometric locality, which is presented as new content rather than a renaming or ansatz smuggled via self-citation. [CKG23] is treated as independent prior work; no self-citation chain or uniqueness theorem imported from overlapping authors is invoked to force the result. The derivation is therefore self-contained against the external benchmark.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption The quantum Gibbs sampler of [CKG23] exists and has the stated properties for k-local bounded Hamiltonians.
Reference graph
Works this paper leans on
-
[1]
Physical Review Letters , volume =
Quantum algorithm for Petz recovery channels and pretty good measurements , author =. Physical Review Letters , volume =. 2022 , publisher =
2022
-
[2]
and Kothari, Robin and Low, Guang Hao , title =
Haah, Jeongwan and Hastings, Matthew B. and Kothari, Robin and Low, Guang Hao , title =. SIAM Journal on Computing , volume =. 2023 , doi =
2023
-
[3]
Journal of Mathematical Physics , volume =
On the modified logarithmic Sobolev inequality for the heat-bath dynamics for 1D systems , author =. Journal of Mathematical Physics , volume =. 2021 , month =. doi:10.1063/1.5142186 , url =
-
[4]
Archive for Rational Mechanics and Analysis , volume =
Complete entropic inequalities for quantum Markov chains , author =. Archive for Rational Mechanics and Analysis , volume =. 2022 , month =. doi:10.1007/s00205-022-01785-1 , url =. 2102.04146 , archivePrefix =
-
[5]
Mathematische Zeitschrift , volume =
On certain properties of the relative entropy of states of operator algebras , author =. Mathematische Zeitschrift , volume =. 1991 , url =
1991
-
[6]
Proof Verification and the Hardness of Approximation Problems , author =. J. 1998 , doi =
1998
-
[7]
2011 , url =
Quantum Computation and Quantum Information (10th Anniversary edition) , author =. 2011 , url =
2011
-
[8]
2018 , publisher =
The Theory of Quantum Information , author =. 2018 , publisher =
2018
-
[9]
2002 , publisher =
Classical and Quantum Computation , author =. 2002 , publisher =
2002
-
[10]
Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences , volume =
Quantum computing, postselection, and probabilistic polynomial-time , author =. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences , volume =. 2004 , url =
2004
-
[11]
2009 50th Annual IEEE Symposium on Foundations of Computer Science , pages =
Universal Blind Quantum Computation , author =. 2009 50th Annual IEEE Symposium on Foundations of Computer Science , pages =. 2008 , url =
2009
-
[12]
Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences , volume =
Temporally unstructured quantum computation , author =. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences , volume =. 2008 , url =
2008
-
[13]
Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences , volume =
Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy , author =. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences , volume =. 2011 , url =
2011
-
[14]
ArXiv , volume =
The computational complexity of linear optics , author =. ArXiv , volume =. 2010 , url =
2010
-
[15]
Physical review letters , pages =
Average-case complexity versus approximate simulation of commuting quantum computations , author =. Physical review letters , pages =. 2015 , url =
2015
-
[16]
Achieving quantum supremacy with sparse and noisy commuting quantum computations , author =. 2017 , month =. doi:10.22331/q-2017-04-25-8 , url =
-
[17]
arXiv: Quantum Physics , year =
Architectures for quantum simulation showing a quantum speedup , author =. arXiv: Quantum Physics , year =
-
[18]
arXiv: Quantum Physics , year =
Anticoncentration theorems for schemes showing a quantum speedup , author =. arXiv: Quantum Physics , year =
-
[19]
Quantum , volume =
Quantum advantage from energy measurements of many-body quantum systems , author =. Quantum , volume =. 2019 , url =
2019
-
[20]
Fault-tolerant quantum speedup from constant depth quantum circuits , author =. Phys. Rev. Res. , volume =. 2020 , month =. doi:10.1103/PhysRevResearch.2.033444 , url =
-
[21]
Paletta, Louis and Leverrier, Anthony and Sarlette, Alain and Mirrahimi, Mazyar and Vuillot, Christophe , journal =. Robust sparse. 2024 , month =. doi:10.22331/q-2024-05-06-1337 , url =
-
[22]
Computational advantage of quantum random sampling , author =. Rev. Mod. Phys. , volume =. 2023 , month =. doi:10.1103/RevModPhys.95.035001 , url =
-
[23]
Annals of Physics , volume =
A fault-tolerant one-way quantum computer , author =. Annals of Physics , volume =. 2005 , url =
2005
-
[24]
Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth , author =. 2024 , url =. 2403.14607 , archivePrefix =
arXiv 2024
-
[25]
Communications in Mathematical Physics , volume =
Markovian master equations , author =. Communications in Mathematical Physics , volume =. 1974 , month =. doi:10.1007/BF01608389 , url =
-
[26]
Physical Review Letters , volume =
Dissipative Quantum Church-Turing Theorem , author =. Physical Review Letters , volume =. 2011 , month =. doi:10.1103/physrevlett.107.120501 , url =
-
[27]
Kastoryano, Michael J. and Temme, Kristan , year=. Quantum logarithmic Sobolev inequalities and rapid mixing , volume=. Journal of Mathematical Physics , publisher=. doi:10.1063/1.4804995 , number=
-
[28]
Onorati, E. and Buerschaper, O. and Kliesch, M. and Brown, W. and Werner, A. H. and Eisert, J. , year=. Mixing Properties of Stochastic Quantum Hamiltonians , volume=. Communications in Mathematical Physics , publisher=. doi:10.1007/s00220-017-2950-6 , number=
-
[29]
Shtanko, Oles and Movassagh, Ramis , year =. Algorithms for. doi:10.48550/ARXIV.2112.14688 , url =
-
[30]
2021 , eprint=
The modified logarithmic Sobolev inequality for quantum spin systems: classical and commuting nearest neighbour interactions , author=. 2021 , eprint=
2021
-
[31]
Polynomial-time classical sampling of high-temperature quantum Gibbs states , author =. 2023 , url =. 2305.18514 , archivePrefix =
arXiv 2023
-
[32]
High-Temperature Gibbs States are Unentangled and Efficiently Preparable , author =. arXiv preprint arXiv:2403.16850 , booktitle =. 2024 , publisher =. doi:10.1109/FOCS61266.2024.00068 , eprint =
-
[33]
Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages =
Local minima in quantum systems , author =. Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages =. 2024 , eprint =
2024
-
[34]
arXiv preprint arXiv:2303.18224 , year =
Quantum Thermal State Preparation , author =. arXiv preprint arXiv:2303.18224 , year =. 2303.18224 , archivePrefix =
-
[35]
arXiv preprint arXiv:2311.09207 , year =
An efficient and exact noncommutative quantum Gibbs sampler , author =. arXiv preprint arXiv:2311.09207 , year =. 2311.09207 , archivePrefix =
-
[36]
Rapid Thermalization of Spin Chain Commuting Hamiltonians , author =. Phys. Rev. Lett. , volume =. 2023 , month =. doi:10.1103/PhysRevLett.130.060401 , url =
-
[37]
Communications in Mathematical Physics , volume =
Entropy Decay for Davies Semigroups of a One Dimensional Quantum Lattice , author =. Communications in Mathematical Physics , volume =. 2024 , month =. doi:10.1007/s00220-023-04869-5 , url =
-
[38]
Helmuth, Tyler and Mann, Ryan L. , year=. Efficient Algorithms for Approximating Quantum Partition Functions at Low Temperature , volume=. doi:10.22331/q-2023-10-25-1155 , journal=
-
[39]
Mann, Ryan L. and Helmuth, Tyler , year=. Efficient algorithms for approximating quantum partition functions , volume=. Journal of Mathematical Physics , publisher=. doi:10.1063/5.0013689 , number=
-
[40]
Algorithmic Cluster Expansions for Quantum Problems , author =. PRX Quantum , volume =. 2024 , publisher =. doi:10.1103/PRXQuantum.5.010305 , url =
-
[41]
2025 , eprint=
Convergence of the Cumulant Expansion and Polynomial-Time Algorithm for Weakly Interacting Fermions , author=. 2025 , eprint=
2025
-
[42]
Thermal State Preparation via Rounding Promises , volume=
Rall, Patrick and Wang, Chunhao and Wocjan, Pawel , year=. Thermal State Preparation via Rounding Promises , volume=. doi:10.22331/q-2023-10-10-1132 , journal=
-
[43]
arXiv: Quantum Physics , year =
Relative Entropy Convergence for Depolarizing Channels , author =. arXiv: Quantum Physics , year =
-
[44]
arXiv: Quantum Physics , year =
Entropy Production of Doubly Stochastic Quantum Channels , author =. arXiv: Quantum Physics , year =
-
[45]
Journal of Physics A: Mathematical and Theoretical , volume =
Quantum conditional relative entropy and quasi-factorization of the relative entropy , author =. Journal of Physics A: Mathematical and Theoretical , volume =. 2018 , url =
2018
-
[46]
Communications in Mathematical Physics , volume =
Quantum Reverse Hypercontractivity: Its Tensorization and Application to Strong Converses , author =. Communications in Mathematical Physics , volume =. 2018 , url =
2018
-
[47]
Communications in Mathematical Physics , volume =
Automorphic Equivalence within Gapped Phases of Quantum Lattice Systems , author =. Communications in Mathematical Physics , volume =. 2011 , month =. doi:10.1007/s00220-011-1380-0 , url =
-
[48]
Hastings, M. B. and Wen, Xiao-Gang , year=. Quasiadiabatic continuation of quantum states: The stability of topological ground-state degeneracy and emergent gauge invariance , volume=. Physical Review B , publisher=. doi:10.1103/physrevb.72.045141 , number=
-
[49]
arXiv: Mathematical Physics , year =
Locality in Quantum Systems , author =. arXiv: Mathematical Physics , year =
-
[50]
Michalakis, Spyridon and Zwolak, Justyna P. , year=. Stability of Frustration-Free Hamiltonians , volume=. Communications in Mathematical Physics , publisher=. doi:10.1007/s00220-013-1762-6 , number=
-
[51]
Communications in Mathematical Physics , volume =
Finite Correlation Length Implies Efficient Preparation of Quantum Thermal States , author =. Communications in Mathematical Physics , volume =. 2019 , month =. doi:10.1007/s00220-018-3150-8 , url =
-
[52]
Physical Review B , volume =
Quantum belief propagation: An algorithm for thermal quantum systems , author =. Physical Review B , volume =. 2007 , url =
2007
-
[53]
Communications in Mathematical Physics , volume =
Quantum Conditional Mutual Information and Approximate Markov Chains , author =. Communications in Mathematical Physics , volume =. 2014 , publisher =
2014
-
[54]
arXiv: Quantum Physics , year =
Quantum Markov Networks and Commuting Hamiltonians , author =. arXiv: Quantum Physics , year =. 1206.0755 , archivePrefix =
-
[55]
ArXiv , volume =
Universal recovery from a decrease of quantum relative entropy , author =. ArXiv , volume =. 2015 , url =
2015
-
[56]
Quarterly Journal of Mathematics , volume =
SUFFICIENCY OF CHANNELS OVER VON NEUMANN ALGEBRAS , author =. Quarterly Journal of Mathematics , volume =. 1988 , url =
1988
-
[57]
Universal quantum computation with ideal Clifford gates and noisy ancillas , author =. Phys. Rev. A , volume =. 2005 , month =. doi:10.1103/PhysRevA.71.022316 , url =
-
[58]
Quantum advantage with noisy shallow circuits , author =. Nature Physics , volume =. 2020 , month =. doi:10.1038/s41567-020-0948-z , url =
-
[59]
SIAM Journal on Computing , volume =
Fault-Tolerant Quantum Computation with Constant Error Rate , author =. SIAM Journal on Computing , volume =. 2008 , doi =. quant-ph/9906129 , primaryClass =
Pith/arXiv arXiv 2008
-
[60]
SIAM Journal on Computing , volume =
Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation , author =. SIAM Journal on Computing , volume =. 2007 , doi =
2007
-
[61]
Gibbs Sampling gives Quantum Advantage at Constant Temperatures with O(1) -Local Hamiltonians , author =. 2024 , publisher =. doi:10.48550/ARXIV.2408.01516 , url =. 2408.01516 , archivePrefix =
-
[62]
Fault tolerance of quantum low-density parity check codes with sublinear distance scaling , author =. Phys. Rev. A , volume =. 2013 , month =. doi:10.1103/PhysRevA.87.020304 , url =
-
[63]
Quantum Information & Computation14(15), 1338–1372 (2014) https://doi.org/ 10.26421/QIC14.15-16-5
Fault-tolerant quantum computation with constant overhead , author =. Quantum Info. Comput. , volume =. 2014 , month =. doi:10.26421/QIC14.15-16-5 , issn =
-
[64]
Accuracy threshold for postselected quantum computation , author =. Quantum Info. Comput. , volume =. 2008 , month =. doi:10.26421/QIC8.3-4-1 , issn =
-
[65]
Long-range quantum entanglement in noisy cluster states , author =. Phys. Rev. A , volume =. 2005 , month =. doi:10.1103/PhysRevA.71.062313 , url =
-
[66]
An introduction to measurement based quantum computation , author =. 2005 , url =. quant-ph/0508124 , archivePrefix =
Pith/arXiv arXiv 2005
-
[67]
Lieb-Robinson Bounds and the Generation of Correlations and Topological Quantum Order , author =. Phys. Rev. Lett. , volume =. 2006 , month =. doi:10.1103/PhysRevLett.97.050401 , url =
-
[68]
Communications in Mathematical Physics , volume =
An Invariant of Topologically Ordered States Under Local Unitary Transformations , author =. Communications in Mathematical Physics , volume =. 2016 , month =. doi:10.1007/s00220-016-2594-y , url =
-
[69]
Quantum Circuit Depth Lower Bounds For Homological Codes , author =. 2018 , url =. 1810.03912 , archivePrefix =
Pith/arXiv arXiv 2018
-
[70]
Hierarchy of Topological Order From Finite-Depth Unitaries, Measurement, and Feedforward , author =. PRX Quantum , volume =. 2023 , month =. doi:10.1103/PRXQuantum.4.020339 , url =
-
[71]
Adaptive constant-depth circuits for manipulating non-abelian anyons , author =. 2022 , url =. 2205.01933 , archivePrefix =
arXiv 2022
-
[72]
Nishimori's Cat: Stable Long-Range Entanglement from Finite-Depth Unitaries and Weak Measurements , author =. Phys. Rev. Lett. , volume =. 2023 , month =. doi:10.1103/PhysRevLett.131.200201 , url =
-
[73]
Communications Physics , volume =
Topological order from measurements and feed-forward on a trapped ion quantum computer , author =. Communications Physics , volume =. 2024 , month =. doi:10.1038/s42005-024-01698-3 , url =
-
[74]
Long-Range Entanglement from Measuring Symmetry-Protected Topological Phases , author =. Phys. Rev. X , volume =. 2024 , month =. doi:10.1103/PhysRevX.14.021040 , url =
-
[75]
IEEE Transactions on Information Theory , volume =
Quantum LDPC Codes With Positive Rate and Minimum Distance Proportional to the Square Root of the Blocklength , author =. IEEE Transactions on Information Theory , volume =. 2014 , doi =
2014
-
[76]
2012 IEEE International Symposium on Information Theory Proceedings , volume =
Improved quantum hypergraph-product LDPC codes , author =. 2012 IEEE International Symposium on Information Theory Proceedings , volume =. 2012 , doi =
2012
-
[77]
Single-Shot Fault-Tolerant Quantum Error Correction , author =. Phys. Rev. X , volume =. 2015 , month =. doi:10.1103/PhysRevX.5.031043 , url =
-
[78]
Nature Communications , volume =
Single-shot quantum error correction with the three-dimensional subsystem toric code , author =. Nature Communications , volume =. 2021 , url =
2021
-
[79]
Quantum Inf
Local decoders for the 2D and 4D toric code , author =. Quantum Inf. Comput. , volume =. 2016 , url =
2016
-
[80]
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , year =
Efficient decoding of random errors for quantum expander codes , author =. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , year =
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.