Spectral gap of Lee-Yang Hamiltonians

Chaithanya Rayudu; Jun Takahashi

Any Lee-Yang Hamiltonian in a uniform Z-field of strength h has a ground-state gap of at least h/4, independent of system size and couplings.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-14 09:24 UTC pith:OARYHI3E

load-bearing objection Clean, size-independent gap h/4 for the full Lee-Yang class, with a complete analytic chain that puts EPR ground-state energy in BQP.

arxiv 2607.10765 v1 pith:OARYHI3E submitted 2026-07-12 quant-ph cond-mat.stat-mechcs.CCmath-phmath.MP

Spectral gap of Lee-Yang Hamiltonians

Chaithanya Rayudu , Jun Takahashi This is my paper

classification quant-ph cond-mat.stat-mechcs.CCmath-phmath.MP

keywords Lee-Yang theoremspectral gapquantum Max-Cutadiabatic quantum computationimaginary-time correlationsTrotterizationpartition-function zeros

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that a large class of quantum Heisenberg-type Hamiltonians, called Lee-Yang Hamiltonians, acquire a uniform spectral gap once a magnetic field of any strength h is applied along the Z direction. The gap is at least h/4 no matter how large the system is and no matter how strong the two-body couplings are. The argument starts from the classical and quantum Lee-Yang theorems, which guarantee that the partition function never vanishes inside the unit polydisc of complex magnetic fields. Keeping every intermediate Trotter layer uncontracted, the authors extract exponential decay of imaginary-time correlations for every product of Pauli-Z operators, then pass to the continuum limit with an adaptive Trotter step. The resulting gap immediately yields a polynomial-time adiabatic quantum algorithm that prepares the ground state and estimates its energy to inverse-polynomial precision, placing several previously open ground-state problems, including bipartite quantum Max-Cut and phase-shifted EPR Hamiltonians, inside BQP.

Core claim

For every Lee-Yang Hamiltonian H on n qubits and every field strength h > 0, the perturbed operator Hh = H - h sum_i Zi has a unique ground state whose spectral gap is bounded from below by h/4, uniformly in n and in all coupling constants that satisfy the Lee-Yang inequalities.

What carries the argument

Multivariate zero-freeness of the fully Trotterized partition function Z_epsilon(y) on the open unit polydisc (Asano-Suzuki-Fisher). Analyticity of log Z_epsilon plus a support lemma on its Taylor coefficients force every monomial that links distant imaginary-time layers to have high degree, producing the exponential decay of Trotterized correlators that survives the continuum limit.

Load-bearing premise

The argument needs the partition function to stay free of zeros even when every intermediate Trotter layer is kept as an independent complex variable; if that multivariate zero-free region fails, the correlation decay and the gap both collapse.

What would settle it

Exhibit a concrete Lee-Yang Hamiltonian (finite n, couplings obeying the stated inequalities) for which the ground-state gap of Hh falls below h/4 for some h > 0, or show that the Trotterized multivariate partition function acquires a zero inside the unit polydisc.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

The ground-state energy of any Lee-Yang Hamiltonian can be approximated to inverse-polynomial additive error by a polynomial-time adiabatic quantum algorithm.
Bipartite quantum Max-Cut and the EPR Hamiltonian ground-state energy problem both lie in BQP.
Phase-shifted EPR Hamiltonians, previously proposed as candidates for quantum advantage, also become efficiently solvable on a quantum computer.
The same gap bound holds for every product of Z-operators, so every diagonal observable has exponentially decaying imaginary-time correlations at rate proportional to h.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If classical algorithms can already exploit the same zero-free region, the BQP membership may collapse further into BPP for the stoquastic subclass, but the paper leaves the non-stoquastic members as genuine quantum candidates.
The uniform rate of decay for every diagonal operator suggests that the entire algebra of Z-diagonal observables is gapped, which may simplify classical tensor-network or Monte-Carlo methods even without quantum hardware.
Extending the argument from products of Z's to transverse observables would recover or strengthen earlier decay results of Bjornberg-Ueltschi and close the remaining gap to full clustering.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

Clean, size-independent gap h/4 for the full Lee-Yang class, with a complete analytic chain that puts EPR ground-state energy in BQP.

read the letter

The punchline is simple: any Lee-Yang Hamiltonian in a uniform field h > 0 has a nondegenerate ground state and gap at least h/4, independent of n and of the couplings. That is new. Classical zero-freeness-to-decay is old, and the quantum Lee-Yang theorems are known; what they add is uniform imaginary-time decay for every product of Z operators, the explicit continuum limit with adaptive Trotter step, and the spectral-gap extraction. The algorithmic payoff is real: bipartite quantum Max-Cut / EPR (and the phase-shifted variants) land in BQP, improving the StoqMA upper bound, via a straightforward adiabatic path from −∑ Zi.

The proof is written carefully. Multivariate zero-freeness of the uncontracted Trotterized Z_ε gives analyticity of log Z_ε; the support lemma forces high degree on monomials that link distant layers; maximum modulus plus Borel–Carathéodory give the Trotterized decay; adaptive ε ~ exp(−hτ/2) plus the additive Trotter error upgrade it to exact decay at rate h/2 for all diagonal products; spectral representation at β/2 and β → ∞ force the low-energy window of width < h/4 to be one-dimensional. Appendices carry the elementary norm and Hölder bounds. Constants are loose (h/4, prefactors polynomial in n, β, W, 1/h), but they are explicit and the chain has no free parameters and no circular fitting.

The only load-bearing external input is the Asano / Suzuki–Fisher zero-freeness kept for all intermediate-layer variables. The authors flag that the contracted continuum version may not suffice, and the literature supplies the multi-layer statement they use. That is a soft spot only in the sense that the result inherits whatever caveats attach to that classical theorem; it is not a gap in their argument. Citation pattern is clean and the related-work discussion is honest about Penrose–Lebowitz, Fröhlich–Rodriguez, Björnberg–Ueltschi, Harrow–Mehraban–Soleimanifar, and the recent Wong–Bravyi–Gosset–Liu conjecture.

This is for people who care about Hamiltonian complexity, adiabatic algorithms, or rigorous spectral gaps in quantum spin systems. The math is solid enough that a serious editor should send it to referees. I would bring it to reading group and I would cite the gap theorem and the BQP placement. Engage with it.

Referee Report

0 major / 5 minor

Summary. The paper proves that any Lee-Yang Hamiltonian H (Definition 1: 2-local Heisenberg-type terms whose ZZ couplings dominate the transverse couplings in the Asano–Suzuki–Fisher sense) subject to a uniform longitudinal field of strength h > 0 has a non-degenerate ground state and spectral gap at least h/4, independent of system size and of the interaction strengths (Theorem 11). The argument proceeds by establishing exponential decay of imaginary-time correlators of every product of Z operators (Theorem 10) from the multivariate zero-freeness of the fully Trotterized partition function (Lemma 2), via a support lemma on the Taylor coefficients of log Z_ε (Lemma 6), maximum-modulus bounds, and an adaptive Trotter-step comparison (Lemma 9). The gap is then read off from the spectral representation of the correlator at separation β/2 by sending β → ∞. As a corollary the authors obtain a polynomial-time adiabatic quantum algorithm for the ground-state energy of every such Hamiltonian, placing bipartite quantum Max-Cut and the EPR Hamiltonian in BQP.

Significance. If correct, the result supplies the first uniform, size-independent spectral-gap lower bound for a broad and natural class of quantum spin Hamiltonians that includes models with a sign problem. The algorithmic consequence is concrete: it improves the previous StoqMA upper bound for bipartite quantum Max-Cut / EPR ground-state energy to BQP and gives an efficient quantum algorithm for the phase-shifted EPR family previously proposed as a candidate for quantum advantage. The proof is fully analytic, parameter-free, and written with explicit constants; the only external input is the classical multivariate Lee–Yang theorem of Asano and Suzuki–Fisher retained for uncontracted intermediate Trotter layers. These features make the manuscript a substantial contribution to both mathematical physics and Hamiltonian complexity.

minor comments (5)

In the proof of Lemma 6 the phrase “at least min(k,M-k)-1 layers” is slightly loose when min(k,M-k)=1; the subsequent counting |q|≥min(k,M-k)+1 remains correct, but a one-line clarification would remove any ambiguity.
Lemma 7 invokes Borel–Carathéodory on the ray ζ ↦ log Z_ε(ζ e^{εh} y). A short parenthetical recalling the precise statement used would help readers who are not specialists in complex analysis.
The constant G in Theorem 10 absorbs several factors of 2; a brief remark that the final gap h/4 is not claimed to be optimal would set expectations correctly.
A few typographical slips appear (e.g., “Noe that” in the proof of Lemma 16, “the the variables” in the introduction). They do not affect readability but should be cleaned.
The algorithmic discussion in §1.1 would benefit from an explicit citation of the adiabatic theorem (with the precise inverse-gap dependence) that is being invoked.

Circularity Check

0 steps flagged

No circularity: spectral gap is derived analytically from external Lee-Yang zero-freeness, with all intermediate estimates written out.

full rationale

The load-bearing chain is: multivariate zero-freeness of the uncontracted Trotterized partition function Z_ε (Lemma 2, citing Asano and Suzuki–Fisher) ⇒ analyticity of log Z_ε ⇒ support lemma on Taylor coefficients (Lemma 6, proved from dead-layer factorization) ⇒ maximum-modulus/Borel–Carathéodory decay of Trotterized Z_S correlators (Proposition 8) ⇒ adaptive Trotter step plus additive error (Lemma 9) ⇒ exact imaginary-time decay at rate h/2 (Theorem 10) ⇒ spectral representation at β/2 and β o∞ forcing a one-dimensional low-energy subspace of width <h/4 (Theorem 11). No parameter is fitted to data; the constant h/4 is produced by explicit estimates. Self-citations (e.g. the authors’ QMC work) are not used in the gap proof. The only external inputs are classical zero-freeness theorems used as black boxes, which is independent support rather than circularity. The derivation is self-contained against its stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 1 invented entities

The paper rests on one classical domain theorem (multivariate Lee-Yang zero-freeness of the Trotterized partition function) plus standard complex analysis and operator-norm estimates. No free parameters are fitted; the constant 1/4 is derived. The only invented entity is the named class 'Lee-Yang Hamiltonians', which is simply the set of couplings already known to satisfy the classical circle theorem.

axioms (4)

domain assumption For Lee-Yang Hamiltonians the Trotterized partition function Z_ε(y) has no zeros when |yi,m| < 1 for all sites i and layers m (Lemma 2, Asano / Suzuki-Fisher).
Invoked as the starting analyticity region for log Z_ε; every subsequent maximum-modulus and support argument lives inside this polydisc.
standard math Borel-Carathéodory inequality and maximum-modulus principle for holomorphic functions on polydiscs.
Used in Lemma 7 and Proposition 8 to convert real-part bounds into modulus bounds and to extract the exponential decay from high-degree vanishing.
standard math Tracial matrix Hölder inequality for Schatten norms (Fact 15).
Controls the one- and two-insertion moments that appear in the Trotter comparison lemmas.
domain assumption Operator-norm bounds ||Hij|| ≤ 3 wz_ij and the resulting ||Hh|| ≤ Γ = 3W + nh.
Used throughout the elementary Trotter estimates (Appendix A) and the adaptive step-size choice.

invented entities (1)

Lee-Yang Hamiltonians (Definition 1) independent evidence
purpose: Names the precise class of 2-local Heisenberg-type couplings for which the classical circle theorem holds and for which the gap is proved.
The definition is exactly the set of couplings already known to satisfy Asano/Suzuki-Fisher; it is not a new physical postulate.

pith-pipeline@v1.1.0-grok45 · 24758 in / 2754 out tokens · 41059 ms · 2026-07-14T09:24:24.004901+00:00 · methodology

0 comments

read the original abstract

The Lee-Yang theorem and its quantum extensions state that, for a broad class of Hamiltonians on any graph, the partition function's zeros in the complex magnetic field plane lie only on the imaginary axis. For these Hamiltonians, we prove that under a uniform Z-field of any strength h, the ground state has a spectral gap of at least h/4, independent of the system size and of the coupling strengths. The proof uses the zero-freeness of the partition function as given by Asano and Suzuki-Fisher to show exponential decay of the imaginary-time correlations for any product of Z-operators. Our result gives a polynomial-time quantum algorithm for computing the ground state energy of any Lee-Yang Hamiltonian.

discussion (0)

Reference graph

Works this paper leans on

49 extracted references · 7 linked inside Pith

[1]

Spectral gap and exponential decay of correlations

Matthew B Hastings and Tohru Koma. Spectral gap and exponential decay of correlations. Communications in Mathematical Physics, 265(3):781–804, 2006

2006
[2]

Lieb-Robinson bounds and the exponential clustering theorem.Communications in Mathematical Physics, 265:119–130, 2006

Bruno Nachtergaele and Robert Sims. Lieb-Robinson bounds and the exponential clustering theorem.Communications in Mathematical Physics, 265:119–130, 2006. 13

2006
[3]

Topological quantum order: stability under local perturbations.Journal of Mathematical Physics, 51(9):093512, 2010

Sergey Bravyi, Matthew B Hastings, and Spyridon Michalakis. Topological quantum order: stability under local perturbations.Journal of Mathematical Physics, 51(9):093512, 2010

2010
[4]

Stability of frustration-free Hamiltonians.Commu- nications in Mathematical Physics, 322:277–302, 2013

Spyridon Michalakis and Justyna P Zwolak. Stability of frustration-free Hamiltonians.Commu- nications in Mathematical Physics, 322:277–302, 2013

2013
[5]

Quasiadiabatic continuation of quantum states: The stability of topological ground-state degeneracy and emergent gauge invariance.Physical Review B, 72(4):045141, 2005

Matthew B Hastings and Xiao-Gang Wen. Quasiadiabatic continuation of quantum states: The stability of topological ground-state degeneracy and emergent gauge invariance.Physical Review B, 72(4):045141, 2005

2005
[6]

Local unitary transformation, long-range quantum entanglement, wave function renormalization, and topological order.Physical Review B, 82(15):155138, 2010

Xie Chen, Zheng-Cheng Gu, and Xiao-Gang Wen. Local unitary transformation, long-range quantum entanglement, wave function renormalization, and topological order.Physical Review B, 82(15):155138, 2010

2010
[7]

Cambridge University Press, 2 edition, 2011

Subir Sachdev.Quantum Phase Transitions. Cambridge University Press, 2 edition, 2011

2011
[8]

Cambridge University Press, 2013

Eduardo Fradkin.Field theories of condensed matter physics. Cambridge University Press, 2013

2013
[9]

F Duncan M Haldane. Nonlinear field theory of large-spin Heisenberg antiferromagnets: semiclassically quantized solitons of the one-dimensional easy-axis Néel state.Physical Review Letters, 50(15):1153–1156, 1983

1983
[10]

M. P. Nightingale and H. W. J. Blöte. Gap of the linear spin-1 heisenberg antiferromagnet: A monte carlo calculation.Phys. Rev. B, 33:659(R)–661(R), Jan 1986

1986
[11]

White and David A

Steven R. White and David A. Huse. Numerical renormalization-group study of low-lying eigenstates of the antiferromagnetic s=1 heisenberg chain.Phys. Rev. B, 48:3844–3852, Aug 1993

1993
[12]

Ground state of the s = 1antiferromagnetic heisenberg chain is topologically nontrivial if gapped.Phys

Hal Tasaki. Ground state of the s = 1antiferromagnetic heisenberg chain is topologically nontrivial if gapped.Phys. Rev. Lett., 134:076602, Feb 2025

2025
[13]

Quantum annealing in the transverse ising model

Tadashi Kadowaki and Hidetoshi Nishimori. Quantum annealing in the transverse ising model. Phys. Rev. E, 58:5355–5363, Nov 1998

1998
[14]

Quantum computation by adiabatic evolution, 2000

Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Quantum computation by adiabatic evolution, 2000

2000
[15]

Kinget al

Andrew D. Kinget al. Beyond-classical computation in quantum simulation.Science, 388(6743):199–204, 2025

2025
[16]

Adiabatic quantum computation is equivalent to standard quantum computation.SIAM Journal on Computing, 37(1):166–194, 2007

Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev. Adiabatic quantum computation is equivalent to standard quantum computation.SIAM Journal on Computing, 37(1):166–194, 2007

2007
[17]

Bounds for the adiabatic approximation with applications to quantum computation.Journal of Mathematical Physics, 48(10), 2007

Sabine Jansen, Mary-Beth Ruskai, and Ruedi Seiler. Bounds for the adiabatic approximation with applications to quantum computation.Journal of Mathematical Physics, 48(10), 2007

2007
[18]

Near-optimal ground state preparation.Quantum, 4:372, 2020

Lin Lin and Yu Tong. Near-optimal ground state preparation.Quantum, 4:372, 2020. 14

2020
[19]

An area law for one-dimensional quantum systems.Journal of Statistical Mechanics: Theory and Experiment, 2007(08):P08024, 2007

Matthew B Hastings. An area law for one-dimensional quantum systems.Journal of Statistical Mechanics: Theory and Experiment, 2007(08):P08024, 2007

2007
[20]

An area law and sub-exponential algorithm for 1D systems.arXiv preprint arXiv:1301.1162, 2013

Itai Arad, Alexei Kitaev, Zeph Landau, and Umesh Vazirani. An area law and sub-exponential algorithm for 1D systems.arXiv preprint arXiv:1301.1162, 2013

Pith/arXiv arXiv 2013
[21]

A polynomial time algorithm for the ground state of one-dimensional gapped local hamiltonians.Nature Physics, 11(7):566–569, 2015

Zeph Landau, Umesh Vazirani, and Thomas Vidick. A polynomial time algorithm for the ground state of one-dimensional gapped local hamiltonians.Nature Physics, 11(7):566–569, 2015

2015
[22]

Undecidability of the spectral gap

Toby S Cubitt, David Perez-Garcia, and Michael M Wolf. Undecidability of the spectral gap. Nature, 528(7581):207–211, 2015

2015
[23]

Guest column: The 7 faces of quantum NP.ACM SIGACT News, 54(4):54–91, 2023

Sevag Gharibian. Guest column: The 7 faces of quantum NP.ACM SIGACT News, 54(4):54–91, 2023

2023
[24]

An improved approximation algorithm for quantum max-cut on triangle-free graphs.Quantum, 7:1180, 2023

Robbie King. An improved approximation algorithm for quantum max-cut on triangle-free graphs.Quantum, 7:1180, 2023

2023
[25]

Improved approximation algorithms for the EPR hamiltonian

Nathan Ju and Ansh Nagda. Improved approximation algorithms for the EPR hamiltonian. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025), volume 353 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 24:1–24:9. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025

2025
[26]

Improved algorithms for quantum MaxCut via partially entangled matchings

Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, and James Sud. Improved algorithms for quantum MaxCut via partially entangled matchings. In33rd Annual European Symposium on Algorithms (ESA 2025), volume 351 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 101:1–101:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025

2025
[27]

A 0.8395-approximation algorithm for the EPR problem.arXiv preprint arXiv:2512.09896, 2025

Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, Lennart Sinjorgo, and James Sud. A 0.8395-approximation algorithm for the EPR problem.arXiv preprint arXiv:2512.09896, 2025

arXiv 2025
[28]

Lee-Yang tensors and Hamiltonian complexity.arXiv preprint arXiv:2602.03605, 2026

Benjamin Wong, Sergey Bravyi, David Gosset, and Yinchen Liu. Lee-Yang tensors and Hamiltonian complexity.arXiv preprint arXiv:2602.03605, 2026

arXiv 2026
[29]

A complexity phase transition at the EPR hamiltonian.arXiv preprint arXiv:2604.13026, 2026

Kunal Marwaha and James Sud. A complexity phase transition at the EPR hamiltonian.arXiv preprint arXiv:2604.13026, 2026

Pith/arXiv arXiv 2026
[30]

Complexity classification of local hamiltonian problems

Toby Cubitt and Ashley Montanaro. Complexity classification of local hamiltonian problems. SIAM Journal on Computing, 45(2):268–316, 2016

2016
[31]

Rapidly mixing loop representation quantum monte carlo for heisenberg models on star-like bipartite graphs.arXiv preprint arXiv:2411.01452, 2024

Jun Takahashi, Sam Slezak, and Elizabeth Crosson. Rapidly mixing loop representation quantum monte carlo for heisenberg models on star-like bipartite graphs.arXiv preprint arXiv:2411.01452, 2024

Pith/arXiv arXiv 2024
[32]

Fast mixing of operator-loop path-integral quantum Monte Carlo for stoquastic XY hamiltonians.arXiv preprint arXiv:2509.21683, 2025

Chaithanya Rayudu and Jun Takahashi. Fast mixing of operator-loop path-integral quantum Monte Carlo for stoquastic XY hamiltonians.arXiv preprint arXiv:2509.21683, 2025

arXiv 2025
[33]

Computational studies of quantum spin systems

Anders W Sandvik. Computational studies of quantum spin systems. InAIP Conference Proceedings, volume 1297, pages 135–338. American Institute of Physics, 2010. 15

2010
[34]

On the exponential decay of correlation functions

Oliver Penrose and Joel L Lebowitz. On the exponential decay of correlation functions. Communications in Mathematical Physics, 39(3):165–184, 1974

1974
[35]

Completely analytical interactions: constructive description.Journal of Statistical Physics, 46(5-6):983–1014, 1987

Roland Dobrushin and Senya Shlosman. Completely analytical interactions: constructive description.Journal of Statistical Physics, 46(5-6):983–1014, 1987

1987
[36]

Some applications of the Lee-Yang theorem

Jürg Fröhlich and Pierre-François Rodriguez. Some applications of the Lee-Yang theorem. Journal of Mathematical Physics, 53(9):095218, 2012

2012
[37]

On cluster properties of classical ferromagnets in an external magnetic field.Journal of Statistical Physics, 166:828–840, 2017

Jürg Fröhlich and Pierre-François Rodriguez. On cluster properties of classical ferromagnets in an external magnetic field.Journal of Statistical Physics, 166:828–840, 2017

2017
[38]

Decay of transverse correlations in quantum Heisenberg models.Journal of Mathematical Physics, 56(4):043303, 2015

Jakob E Björnberg and Daniel Ueltschi. Decay of transverse correlations in quantum Heisenberg models.Journal of Mathematical Physics, 56(4):043303, 2015

2015
[39]

Randomlooprepresentationsforquantumspinsystems.Journal of Mathematical Physics, 54(8), 2013

DanielUeltschi. Randomlooprepresentationsforquantumspinsystems.Journal of Mathematical Physics, 54(8), 2013

2013
[40]

Locality of temperature.Physical Review X, 4(3):031019, 2014

Martin Kliesch, Christian Gogolin, Michael J Kastoryano, Arnau Riera, and Jens Eisert. Locality of temperature.Physical Review X, 4(3):031019, 2014

2014
[41]

Efficient algorithms for approximating quantum partition functions.Journal of Mathematical Physics, 62(2):022201, 2021

Ryan L Mann and Tyler Helmuth. Efficient algorithms for approximating quantum partition functions.Journal of Mathematical Physics, 62(2):022201, 2021

2021
[42]

High-temperature Gibbs states are unentangled and efficiently preparable

Ainesh Bakshi, Allen Liu, Ankur Moitra, and Ewin Tang. High-temperature Gibbs states are unentangled and efficiently preparable. In2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2024

2024
[43]

Fast mixing of all-to-all quantum systems at high temperatures.arXiv preprint arXiv:2606.26090, 2026

Thiago Bergamaschi. Fast mixing of all-to-all quantum systems at high temperatures.arXiv preprint arXiv:2606.26090, 2026

Pith/arXiv arXiv 2026
[44]

A rigorous quasipolynomial-time classical algorithm for SYK thermal expectations.arXiv preprint arXiv:2604.21089, 2026

Alexander Zlokapa. A rigorous quasipolynomial-time classical algorithm for SYK thermal expectations.arXiv preprint arXiv:2604.21089, 2026

Pith/arXiv arXiv 2026
[45]

SYK thermal expectations are classically easy at any temperature.arXiv preprint arXiv:2602.22619, 2026

Alexander Zlokapa and Bobak T Kiani. SYK thermal expectations are classically easy at any temperature.arXiv preprint arXiv:2602.22619, 2026

Pith/arXiv arXiv 2026
[46]

Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems

Aram W Harrow, Saeed Mehraban, and Mehdi Soleimanifar. Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems. InProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 378–386, 2020

2020
[47]

Theorems on the partition functions of the Heisenberg ferromagnets.Journal of the Physical Society of Japan, 29(2):350–359, 1970

Taro Asano. Theorems on the partition functions of the Heisenberg ferromagnets.Journal of the Physical Society of Japan, 29(2):350–359, 1970

1970
[48]

Zeros of the partition function for the Heisenberg, ferroelectric, and general Ising models.Journal of Mathematical Physics, 12(2):235–246, 1971

Masuo Suzuki and Michael E Fisher. Zeros of the partition function for the Heisenberg, ferroelectric, and general Ising models.Journal of Mathematical Physics, 12(2):235–246, 1971

1971
[49]

An inequality for the trace of matrix products, using absolute values

Bernhard Baumgartner. An inequality for the trace of matrix products, using absolute values. arXiv preprint arXiv:1106.6189, 2011. 16 A Elementary Trotter bounds In this appendix we prove the size bounds of Lemma 3 and the elementary bounds on the Trotterized objects that are used in the proofs of the Trotter comparison lemmas in Appendix B. These include...

Pith/arXiv arXiv 2011

[1] [1]

Spectral gap and exponential decay of correlations

Matthew B Hastings and Tohru Koma. Spectral gap and exponential decay of correlations. Communications in Mathematical Physics, 265(3):781–804, 2006

2006

[2] [2]

Lieb-Robinson bounds and the exponential clustering theorem.Communications in Mathematical Physics, 265:119–130, 2006

Bruno Nachtergaele and Robert Sims. Lieb-Robinson bounds and the exponential clustering theorem.Communications in Mathematical Physics, 265:119–130, 2006. 13

2006

[3] [3]

Topological quantum order: stability under local perturbations.Journal of Mathematical Physics, 51(9):093512, 2010

Sergey Bravyi, Matthew B Hastings, and Spyridon Michalakis. Topological quantum order: stability under local perturbations.Journal of Mathematical Physics, 51(9):093512, 2010

2010

[4] [4]

Stability of frustration-free Hamiltonians.Commu- nications in Mathematical Physics, 322:277–302, 2013

Spyridon Michalakis and Justyna P Zwolak. Stability of frustration-free Hamiltonians.Commu- nications in Mathematical Physics, 322:277–302, 2013

2013

[5] [5]

Quasiadiabatic continuation of quantum states: The stability of topological ground-state degeneracy and emergent gauge invariance.Physical Review B, 72(4):045141, 2005

Matthew B Hastings and Xiao-Gang Wen. Quasiadiabatic continuation of quantum states: The stability of topological ground-state degeneracy and emergent gauge invariance.Physical Review B, 72(4):045141, 2005

2005

[6] [6]

Local unitary transformation, long-range quantum entanglement, wave function renormalization, and topological order.Physical Review B, 82(15):155138, 2010

Xie Chen, Zheng-Cheng Gu, and Xiao-Gang Wen. Local unitary transformation, long-range quantum entanglement, wave function renormalization, and topological order.Physical Review B, 82(15):155138, 2010

2010

[7] [7]

Cambridge University Press, 2 edition, 2011

Subir Sachdev.Quantum Phase Transitions. Cambridge University Press, 2 edition, 2011

2011

[8] [8]

Cambridge University Press, 2013

Eduardo Fradkin.Field theories of condensed matter physics. Cambridge University Press, 2013

2013

[9] [9]

F Duncan M Haldane. Nonlinear field theory of large-spin Heisenberg antiferromagnets: semiclassically quantized solitons of the one-dimensional easy-axis Néel state.Physical Review Letters, 50(15):1153–1156, 1983

1983

[10] [10]

M. P. Nightingale and H. W. J. Blöte. Gap of the linear spin-1 heisenberg antiferromagnet: A monte carlo calculation.Phys. Rev. B, 33:659(R)–661(R), Jan 1986

1986

[11] [11]

White and David A

Steven R. White and David A. Huse. Numerical renormalization-group study of low-lying eigenstates of the antiferromagnetic s=1 heisenberg chain.Phys. Rev. B, 48:3844–3852, Aug 1993

1993

[12] [12]

Ground state of the s = 1antiferromagnetic heisenberg chain is topologically nontrivial if gapped.Phys

Hal Tasaki. Ground state of the s = 1antiferromagnetic heisenberg chain is topologically nontrivial if gapped.Phys. Rev. Lett., 134:076602, Feb 2025

2025

[13] [13]

Quantum annealing in the transverse ising model

Tadashi Kadowaki and Hidetoshi Nishimori. Quantum annealing in the transverse ising model. Phys. Rev. E, 58:5355–5363, Nov 1998

1998

[14] [14]

Quantum computation by adiabatic evolution, 2000

Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Quantum computation by adiabatic evolution, 2000

2000

[15] [15]

Kinget al

Andrew D. Kinget al. Beyond-classical computation in quantum simulation.Science, 388(6743):199–204, 2025

2025

[16] [16]

Adiabatic quantum computation is equivalent to standard quantum computation.SIAM Journal on Computing, 37(1):166–194, 2007

Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev. Adiabatic quantum computation is equivalent to standard quantum computation.SIAM Journal on Computing, 37(1):166–194, 2007

2007

[17] [17]

Bounds for the adiabatic approximation with applications to quantum computation.Journal of Mathematical Physics, 48(10), 2007

Sabine Jansen, Mary-Beth Ruskai, and Ruedi Seiler. Bounds for the adiabatic approximation with applications to quantum computation.Journal of Mathematical Physics, 48(10), 2007

2007

[18] [18]

Near-optimal ground state preparation.Quantum, 4:372, 2020

Lin Lin and Yu Tong. Near-optimal ground state preparation.Quantum, 4:372, 2020. 14

2020

[19] [19]

An area law for one-dimensional quantum systems.Journal of Statistical Mechanics: Theory and Experiment, 2007(08):P08024, 2007

Matthew B Hastings. An area law for one-dimensional quantum systems.Journal of Statistical Mechanics: Theory and Experiment, 2007(08):P08024, 2007

2007

[20] [20]

An area law and sub-exponential algorithm for 1D systems.arXiv preprint arXiv:1301.1162, 2013

Itai Arad, Alexei Kitaev, Zeph Landau, and Umesh Vazirani. An area law and sub-exponential algorithm for 1D systems.arXiv preprint arXiv:1301.1162, 2013

Pith/arXiv arXiv 2013

[21] [21]

A polynomial time algorithm for the ground state of one-dimensional gapped local hamiltonians.Nature Physics, 11(7):566–569, 2015

Zeph Landau, Umesh Vazirani, and Thomas Vidick. A polynomial time algorithm for the ground state of one-dimensional gapped local hamiltonians.Nature Physics, 11(7):566–569, 2015

2015

[22] [22]

Undecidability of the spectral gap

Toby S Cubitt, David Perez-Garcia, and Michael M Wolf. Undecidability of the spectral gap. Nature, 528(7581):207–211, 2015

2015

[23] [23]

Guest column: The 7 faces of quantum NP.ACM SIGACT News, 54(4):54–91, 2023

Sevag Gharibian. Guest column: The 7 faces of quantum NP.ACM SIGACT News, 54(4):54–91, 2023

2023

[24] [24]

An improved approximation algorithm for quantum max-cut on triangle-free graphs.Quantum, 7:1180, 2023

Robbie King. An improved approximation algorithm for quantum max-cut on triangle-free graphs.Quantum, 7:1180, 2023

2023

[25] [25]

Improved approximation algorithms for the EPR hamiltonian

Nathan Ju and Ansh Nagda. Improved approximation algorithms for the EPR hamiltonian. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025), volume 353 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 24:1–24:9. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025

2025

[26] [26]

Improved algorithms for quantum MaxCut via partially entangled matchings

Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, and James Sud. Improved algorithms for quantum MaxCut via partially entangled matchings. In33rd Annual European Symposium on Algorithms (ESA 2025), volume 351 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 101:1–101:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025

2025

[27] [27]

A 0.8395-approximation algorithm for the EPR problem.arXiv preprint arXiv:2512.09896, 2025

Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, Lennart Sinjorgo, and James Sud. A 0.8395-approximation algorithm for the EPR problem.arXiv preprint arXiv:2512.09896, 2025

arXiv 2025

[28] [28]

Lee-Yang tensors and Hamiltonian complexity.arXiv preprint arXiv:2602.03605, 2026

Benjamin Wong, Sergey Bravyi, David Gosset, and Yinchen Liu. Lee-Yang tensors and Hamiltonian complexity.arXiv preprint arXiv:2602.03605, 2026

arXiv 2026

[29] [29]

A complexity phase transition at the EPR hamiltonian.arXiv preprint arXiv:2604.13026, 2026

Kunal Marwaha and James Sud. A complexity phase transition at the EPR hamiltonian.arXiv preprint arXiv:2604.13026, 2026

Pith/arXiv arXiv 2026

[30] [30]

Complexity classification of local hamiltonian problems

Toby Cubitt and Ashley Montanaro. Complexity classification of local hamiltonian problems. SIAM Journal on Computing, 45(2):268–316, 2016

2016

[31] [31]

Rapidly mixing loop representation quantum monte carlo for heisenberg models on star-like bipartite graphs.arXiv preprint arXiv:2411.01452, 2024

Jun Takahashi, Sam Slezak, and Elizabeth Crosson. Rapidly mixing loop representation quantum monte carlo for heisenberg models on star-like bipartite graphs.arXiv preprint arXiv:2411.01452, 2024

Pith/arXiv arXiv 2024

[32] [32]

Fast mixing of operator-loop path-integral quantum Monte Carlo for stoquastic XY hamiltonians.arXiv preprint arXiv:2509.21683, 2025

Chaithanya Rayudu and Jun Takahashi. Fast mixing of operator-loop path-integral quantum Monte Carlo for stoquastic XY hamiltonians.arXiv preprint arXiv:2509.21683, 2025

arXiv 2025

[33] [33]

Computational studies of quantum spin systems

Anders W Sandvik. Computational studies of quantum spin systems. InAIP Conference Proceedings, volume 1297, pages 135–338. American Institute of Physics, 2010. 15

2010

[34] [34]

On the exponential decay of correlation functions

Oliver Penrose and Joel L Lebowitz. On the exponential decay of correlation functions. Communications in Mathematical Physics, 39(3):165–184, 1974

1974

[35] [35]

Completely analytical interactions: constructive description.Journal of Statistical Physics, 46(5-6):983–1014, 1987

Roland Dobrushin and Senya Shlosman. Completely analytical interactions: constructive description.Journal of Statistical Physics, 46(5-6):983–1014, 1987

1987

[36] [36]

Some applications of the Lee-Yang theorem

Jürg Fröhlich and Pierre-François Rodriguez. Some applications of the Lee-Yang theorem. Journal of Mathematical Physics, 53(9):095218, 2012

2012

[37] [37]

On cluster properties of classical ferromagnets in an external magnetic field.Journal of Statistical Physics, 166:828–840, 2017

Jürg Fröhlich and Pierre-François Rodriguez. On cluster properties of classical ferromagnets in an external magnetic field.Journal of Statistical Physics, 166:828–840, 2017

2017

[38] [38]

Decay of transverse correlations in quantum Heisenberg models.Journal of Mathematical Physics, 56(4):043303, 2015

Jakob E Björnberg and Daniel Ueltschi. Decay of transverse correlations in quantum Heisenberg models.Journal of Mathematical Physics, 56(4):043303, 2015

2015

[39] [39]

Randomlooprepresentationsforquantumspinsystems.Journal of Mathematical Physics, 54(8), 2013

DanielUeltschi. Randomlooprepresentationsforquantumspinsystems.Journal of Mathematical Physics, 54(8), 2013

2013

[40] [40]

Locality of temperature.Physical Review X, 4(3):031019, 2014

Martin Kliesch, Christian Gogolin, Michael J Kastoryano, Arnau Riera, and Jens Eisert. Locality of temperature.Physical Review X, 4(3):031019, 2014

2014

[41] [41]

Efficient algorithms for approximating quantum partition functions.Journal of Mathematical Physics, 62(2):022201, 2021

Ryan L Mann and Tyler Helmuth. Efficient algorithms for approximating quantum partition functions.Journal of Mathematical Physics, 62(2):022201, 2021

2021

[42] [42]

High-temperature Gibbs states are unentangled and efficiently preparable

Ainesh Bakshi, Allen Liu, Ankur Moitra, and Ewin Tang. High-temperature Gibbs states are unentangled and efficiently preparable. In2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2024

2024

[43] [43]

Fast mixing of all-to-all quantum systems at high temperatures.arXiv preprint arXiv:2606.26090, 2026

Thiago Bergamaschi. Fast mixing of all-to-all quantum systems at high temperatures.arXiv preprint arXiv:2606.26090, 2026

Pith/arXiv arXiv 2026

[44] [44]

A rigorous quasipolynomial-time classical algorithm for SYK thermal expectations.arXiv preprint arXiv:2604.21089, 2026

Alexander Zlokapa. A rigorous quasipolynomial-time classical algorithm for SYK thermal expectations.arXiv preprint arXiv:2604.21089, 2026

Pith/arXiv arXiv 2026

[45] [45]

SYK thermal expectations are classically easy at any temperature.arXiv preprint arXiv:2602.22619, 2026

Alexander Zlokapa and Bobak T Kiani. SYK thermal expectations are classically easy at any temperature.arXiv preprint arXiv:2602.22619, 2026

Pith/arXiv arXiv 2026

[46] [46]

Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems

Aram W Harrow, Saeed Mehraban, and Mehdi Soleimanifar. Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems. InProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 378–386, 2020

2020

[47] [47]

Theorems on the partition functions of the Heisenberg ferromagnets.Journal of the Physical Society of Japan, 29(2):350–359, 1970

Taro Asano. Theorems on the partition functions of the Heisenberg ferromagnets.Journal of the Physical Society of Japan, 29(2):350–359, 1970

1970

[48] [48]

Zeros of the partition function for the Heisenberg, ferroelectric, and general Ising models.Journal of Mathematical Physics, 12(2):235–246, 1971

Masuo Suzuki and Michael E Fisher. Zeros of the partition function for the Heisenberg, ferroelectric, and general Ising models.Journal of Mathematical Physics, 12(2):235–246, 1971

1971

[49] [49]

An inequality for the trace of matrix products, using absolute values

Bernhard Baumgartner. An inequality for the trace of matrix products, using absolute values. arXiv preprint arXiv:1106.6189, 2011. 16 A Elementary Trotter bounds In this appendix we prove the size bounds of Lemma 3 and the elementary bounds on the Trotterized objects that are used in the proofs of the Trotter comparison lemmas in Appendix B. These include...

Pith/arXiv arXiv 2011