## References

**[AE11]**

Dorit Aharonov and Lior Eldar

On the complexity of Commuting Local Hamiltonians, and tight conditions for Topological Order in such systems

*IEEE 52nd Annual Symposium on Foundations of Computer Science*, 2011

**[AE14]**

Dorit Aharonov and Lior Eldar

The commuting local Hamiltonian on locally-expanding graphs is in NP

*Quantum Information Processing*, 2014

**[AKV18]**

Dorit Aharonov, Oded Kenneth and Itamar Vigdorovich

On the Complexity of Two Dimensional Commuting Local Hamiltonians

*Conference on the Theory of Quantum Computation, Communication and Cryptography*, 2018

**[AGIK09]**

Dorit Aharonov, Daniel Gottesman, Sandy Irani and Julia Kempe

The Power of Quantum Systems on a Line

*Communications in Mathematical Physics*, 2009

**[AS17]**

Rupam Acharyya and Daniel Stefankovic

Glauber Dynamics for Ising Model on Convergent Dense Graph Sequences

*Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques*, 2017

**[Bar82]**

Francisco Barahona

On the computational complexity of Ising spin glass models

*Journal of Physics A*, 1982

**[BBT06]**

Sergey Bravyi and Arvid J. Bessen and Barbara M. Terhal

Merlin–Arthur Games and Stoquastic Complexity

*arXiv*, 2006

**[BDOT08]**

Sergey Bravyi, David P. Divincenzo, Roberto Oliveira and Barbara M. Terhal

The Complexity of Stoquastic Local Hamiltonian Problems

*Quantum Information and Computation*, 2008

**[BG17]**

Sergey Bravyi and David Gosset

Polynomial-time classical simulation of quantum ferromagnets

*Physical Review Letters*, 2017

**[BH16]**

Sergey Bravyi and Matthew Hastings

On complexity of the quantum Ising model

*Communications in Mathematical Physics*, 2016

**[BL08]**

Jacob D. Biamonte and Peter J. Love

Realizable Hamiltonians for universal adiabatic quantum computers

*American Physical Society*, 78, 1, 2008

**[BP24]**

Vir B. Bulchandani and Stephen Piddock

The classical limit of Quantum Max–Cut

*arXiv*, 2024

**[Bra15]**

Sergey Bravyi

Monte Carlo Simulation of Stoquastic Hamiltonians

*Quantum Information and Computation*, 2015

**[BV03]**

Sergey Bravyi and Mikhail Vyalyi

Commutative version of the $k$–local Hamiltonian problem and common eigenspace problem

*arXiv*, 2004

**[CBBK15]**

Yudong Cao, Ryan Babbush, Jacob Biamonte, and Sabre Kais

Hamiltonian gadgets with reduced resource requirements

*Physical Review A*, 2015

**[BCH+19]**

Christian Borgs, Jennifer Chayes, Tyler Helmuth, Will Perkins, and Prasad Tetali

Efficient sampling and counting algorithms for the Potts model on ℤᵈ at all temperatures

*Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing*, 2020

**[CGW14]**

Andrew M. Childs, David Gosset, and Zak Webb

The Bose–Hubbard Model is QMA–complete

*International Colloquium on Automata, Languages, and Programming*, 2014

**[CFG+23]**

Chris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae, Jordi Weggemans

Improved Hardness Results for the Guided Local Hamiltonian Problem

*International Colloquium on Automata, Languages, and Programming*, 2023

**[CHK21]**

Van Hao Can, Remco van der Hofstad, and Takashi Kumagai

Glauber dynamics for Ising models on random regular graphs: cut-off and metastability

*arXiv*, 2021

**[CM16]**

Toby Cubitt and Ashley Montanaro

Complexity classification of local Hamiltonian problems

*SIAM Journal on Computing*, 2016

**[CMP18]**

Toby Cubitt, Ashley Montanaro and Stephen Piddock

Universal quantum Hamiltonians

*Proceedings of the National Academy of Sciences*, 2018

**[DP11]**

Jian Ding and Yuval Peres

Mixing time for the Ising model: a uniform lower bound for all graphs

*Ann. Inst. H. Poincaré Probab. Statist.*, 2011

**[FP07]**

Roberto Fernández and Aldo Procacci

Cluster expansion for abstract polymer models. New bounds from an old approach

*Communications in Mathematical Physics*, 2007

**[FV17]**

Sacha Friedli and Yvan Velenik

Statistical mechanics of lattice systems: a concrete mathematical introduction

*Cambridge University Press*, 2017

**[GG17]**

Leslie Ann Goldberg and Heng Guo

The Complexity of Approximating complex-valued Ising and Tutte partition functions

*Computational Complexity*, 2017

**[Gla63]**

Roy J. Glauber

Time Dependent Statistics of the Ising Model

*Journal of Mathematical Physics*, 1963

**[GSV16]**

Andreas Galanis, Daniel Štefankovič, and Eric Vigoda

Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region

*Journal of the ACM*, 2015

**[GW95]**

Michel Goesmans and David Williamson

Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

*Journal of the ACM*, 1995

**[HM23]**

Tyler Helmuth and Ryan L. Mann

Efficient Algorithms for Approximating Quantum Partition Functions at Low Temperature

*Quantum*, 2023

**[HNN13]**

Sean Hallgren, Daniel Nagaj and Sandeep Narayanaswami

The Local Hamiltonian problem on a line with eight states is QMA–complete

*Quantum Information and Computation*, 2013

**[HS07]**

Thomas P. Hayes and Alistair Sinclair

A general lower bound for mixing of single-site dynamics on graphs

*The Annals of Applied Probability*, 2007

**[IJ23]**

Sandy Irani and Jiaqing Jiang

Commuting Local Hamiltonian Problem on 2D beyond qubits

*arXiv*, 2023

**[JS93]**

Mark Jerrum and Alistair Sinclair

Polynomial-time approximation algorithms for the Ising model

*SIAM Journal on Computing*, 1993

**[Kin23]**

Robbie King

An Improved Approximation Algorithm for Quantum Max–Cut on Triangle–Free Graphs

*Quantum*, 2023

**[KKR05]**

Julia Kempe, Alexei Kitaev and Oded Regev

The Complexity of the Local Hamiltonian Problem

*SIAM Journal on Computing*, 2005

**[KP86]**

Roman Kotecký and David Preiss

Cluster expansion for abstract polymer models

*Communications in Mathematical Physics*, 1986

**[KPT+24]**

John Kallaugher and Ojas Parekh and Kevin Thompson and Yipu Wang and Justin Yirka

Complexity Classification of Product State Problems for Local Hamiltonians

*arXiv*, 2024

**[KR03]**

Julia Kempe and Oded Regev

3-Local Hamiltonian is QMA-complete

*Quantum Information and Computation*, 2003

**[KSV02]**

Alexei Yu. Kitaev, Alexander Shen and Mikhail N. Vyalyi

Classical and Quantum Computation

*American Mathematical Society*, 2002

**[MH21]**

Ryan L. Mann and Tyler Helmuth

Efficient Algorithms for Approximating Quantum Partition Functions

*Journal of Mathematical Physics*, 2021

**[MM24]**

Ryan L. Mann and Romy M. Minko

Algorithmic Cluster Expansions for Quantum Problems

*PRX Quantum*, 2024

**[MS13]**

Elchanan Mossel and Allan Sly

Exact thresholds for Ising–Gibbs samplers on general graphs

*The Annals of Probability*, 2013

**[OIWF21]**

Bryan O'Gorman and Sandy Irani and James Whitfield and Bill Fefferman

Intractability of Electronic Structure in a Fixed Basis

*PRX Quantum*, 2022

**[OT08]**

Roberto Oliveira and Barbara M. Terhal

The complexity of quantum spin systems on a two-dimensional square lattice

*Quantum Information and Computation*, 2008

**[Pid19]**

Stephen Piddock

Complexity and Simulation of Many-Body Quantum Systems

*University of Bristol*, 2019

**[PM15]**

Stephen Piddock and Ashley Montanaro

The complexity of antiferromagnetic interactions and 2D lattices

*Quantum Information and Computation*, 2015

**[Sal58]**

Edwin E. Salpeter

On Mayer's theory of cluster expansions

*Annals of Physics*, 1958

**[SS14]**

Allan Sly and Nike Sun

The computational hardness of counting in two-spin models on d-regular graphs

*2012 IEEE 53rd Annual Symposium on Foundations of Computer Science*, 2012

**[SST14]**

Alistair Sinclair, Piyush Srivastava, and Marc Thurley

Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs

*Journal of Statistical Physics*, 2014

**[SV09]**

Norbert Schuch and Frank Verstraete

Computational complexity of interacting electrons and fundamental limitations of density functional theory

*Nature Physics*, 2009

**[Sch11]**

Norbert Schuch

Complexity of commuting Hamiltonians on a square lattice of qubits

*arXiv*, 2011

**[Wai23]**

Gabriel Waite

*Private communication*, 2023