feasible}\end{subarray}}\sum_{ijk}d^{ijk}r^{ijk}c^{ijk}\geq\frac{q^{2}}{n^{2}}\cdot\min_{\begin{subarray}{c}r,c\in(I_{n,\gamma})^{16s}\\\
C_{r,c,2\gamma}\text{
feasible}\end{subarray}}\sum_{ijk}d^{ijk}r^{ijk}c^{ijk}\text{ with prob.
}1-\delta/2$ (121) $\displaystyle\text{ and
}\min_{\begin{subarray}{c}r,c\in(I_{n,\gamma})^{16s}\\\ C_{r,c,2\gamma}\text{
feasible}\end{subarray}}\sum_{ijk}d^{ijk}r^{ijk}c^{ijk}\geq\min_{\text{product
state }\rho}\text{Tr}[H_{D}\rho]-O(\gamma/\epsilon\cdot n^{2})$ (122)

Using the expressions for $V_{\gamma}$ and $V_{\gamma}(Q)$ in Lemma 6.3 and
Claim 7.1, with $\gamma=O(\epsilon^{2})$, we conclude the proof of the claim.
∎

We can now finally conclude the proof of the theorem:

###### Proof.

[of Theorem 7.1] Via the triangle inequality, Claim 7.4, Lemma 7.1, and
corollary 7.1 tell us that with probability 0.99,

$\bigg{|}\min_{\rho}\text{Tr}[H\rho]-\frac{n^{2}}{q^{2}}\min_{\rho_{Q}}\text{Tr}[H_{Q}\rho_{Q}]\bigg{|}\leq\epsilon
n^{2}$ (123)

by the union bound and the appropriate choice of $\delta=O(1)$ and $\epsilon$,
so long as $q$ is larger than the largest size constraint,
$\Omega(\epsilon^{-6}\log 1/\epsilon)$. ∎

##  8 Acknowledgements

The author would like to thank Anurag Anshu, Yunchao Liu, Umesh Vazirani and
Sevag Gharibian for many fruitful discussions on product state approximations,
Aram Harrow and Daniel Ranard for a discussion leading to the Hamiltonian
Regularity Lemma, and Anirban Chowdhury for questions and conversations on the
Free Energy of dense Local Hamiltonians.

## References

  * [AALV09] Dorit Aharonov, Itai Arad, Zeph Landau, and Umesh V. Vazirani.  The detectability lemma and quantum gap amplification.  In STOC ’09, 2009.
  * [Aar06] Scott Aaronson.  The quantum pcp manifesto, Oct 2006.  URL: http://www.scottaaronson.com/blog/?p=139.
  * [AdlVKK02] Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, and Marek Karpinski.  Random sampling and approximation of max-csp problems.  Electron. Colloquium Comput. Complex., 2002.
  * [AE02] Gunnar Andersson and Lars Engebretsen.  Property testers for dense constraint satisfaction programs on finite domains.  Random Struct. Algorithms, 21:14–32, 2002.
  * [AGM20] Anurag Anshu, David Gosset, and Karen J. Morenz.  Beyond product state approximations for a quantum analogue of max cut.  In TQC, 2020.
  * [AKK99] Sanjeev Arora, David R. Karger, and Marek Karpinski.  Polynomial time approximation schemes for dense instances of np-hard problems.  Journal of Computer and System Sciences, 58:193–210, 1999.
  * [ALM+92] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy.  Proof verification and hardness of approximation problems.  Proceedings., 33rd Annual Symposium on Foundations of Computer Science, pages 14–23, 1992.
  * [Ara11] Itai Arad.  A note about a partial no-go theorem for quantum pcp.  Quantum Inf. Comput., 11:1019–1027, 2011.
  * [AST90] Noga Alon, Paul D. Seymour, and Robin Thomas.  A separator theorem for graphs with an excluded minor and its applications.  In STOC ’90, 1990.
  * [Bak94] S. Baker.  Approximation algorithms for np-complete problems on planar graphs.  Journal of the ACM, 1994.
  * [Bar16] Alexander I. Barvinok.  Combinatorics and complexity of partition functions.  In Algorithms and combinatorics, 2016.
  * [BBT09] Nikhil Bansal, Sergey Bravyi, and Barbara M. Terhal.  Classical approximation schemes for the ground-state energy of quantum and classical ising spin hamiltonians on planar graphs.  Quantum Inf. Comput., 9:701–720, 2009.
  * [BCGW21] Sergey Bravyi, Anirban Narayan Chowdhury, David Gosset, and Pawel Wocjan.  On the complexity of quantum partition functions.  2021\.
  * [BCL+12] Christian Borgs, Jennifer T. Chayes, László Miklós Lovász, Vera T. Sós, and Katalin Vesztergombi.  Convergent sequences of dense graphs ii. multiway cuts and statistical physics.  Annals of Mathematics, 176:151–219, 2012.
  * [BDD+16] Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, F. Fomin, Daniel Lokshtanov, and Michał Pilipczuk.  A ck n 5-approximation algorithm for treewidth.  SIAM J. Comput., 45:317–378, 2016.
  * [Ber20] Thiago Bergamaschi.  Simulated quantum annealing is efficient on the spike hamiltonian.  arXiv: Quantum Physics, 2020.
  * [BFS11] Brielin Brown, Steven T. Flammia, and Norbert Schuch.  Computational difficulty of computing the density of states.  Physical review letters, 107 4:040501, 2011.
  * [BG17] Sergey Bravyi and David Gosset.  Polynomial-time classical simulation of quantum ferromagnets.  Physical review letters, 119 10:100503, 2017.
  * [BGKT19] Sergey Bravyi, David Gosset, Robert Koenig, and Kristan Temme.  Approximation algorithms for quantum many-body problems.  Journal of Mathematical Physics, 2019.
  * [BH13] Fernando G. S. L. Brandão and Aram Wettroth Harrow.  Product-state approximations to quantum ground states.  In STOC ’13, 2013.
  * [BM15] Anirban Basak and Sumit Mukherjee.  Universality of the mean-field for the potts model.  Probability Theory and Related Fields, 168:557–600, 2015.
  * [Bod93] Hans L. Bodlaender.  A tourist guide through treewidth.  Acta Cybern., 11:1–21, 1993.
  * [BRS11] Boaz Barak, Prasad Raghavendra, and David Steurer.  Rounding semidefinite programming hierarchies via global correlation.  2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 472–481, 2011.
  * [BV02] Dimitris Bertsimas and Santosh S. Vempala.  Solving convex programs by random walks.  In STOC ’02, 2002.
  * [CH21] Elizabeth Crosson and Aram Wettroth Harrow.  Rapid mixing of path integral monte carlo for 1d stoquastic hamiltonians.  Quantum, 5:395, 2021.
  * [DH04a] Erik D. Demaine and Mohammad Taghi Hajiaghayi.  Diameter and treewidth in minor-closed graph families, revisited.  Algorithmica, 40:211–215, 2004.
  * [DH04b] Erik D. Demaine and Mohammad Taghi Hajiaghayi.  Equivalence of local treewidth and linear local treewidth and its algorithmic applications.  In SODA ’04, 2004.
  * [DH05] Erik D. Demaine and Mohammad Taghi Hajiaghayi.  Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality.  In SODA ’05, 2005.
  * [DHiK05] Erik D. Demaine, Mohammad Taghi Hajiaghayi, and Ken ichi Kawarabayashi.  Algorithmic graph minor theory: Decomposition, approximation, and coloring.  46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05), pages 637–646, 2005.
  * [DHiK09] Erik D. Demaine, Mohammad Taghi Hajiaghayi, and Ken ichi Kawarabayashi.  Approximation algorithms via structural results for apex-minor-free graphs.  In ICALP, 2009.
  * [DHiK11] Erik D. Demaine, Mohammad Taghi Hajiaghayi, and Ken ichi Kawarabayashi.  Contraction decomposition in h-minor-free graphs and algorithmic applications.  In STOC ’11, 2011.
  * [DN16] Zdeněk Dvořák and Sergey Norin.  Strongly sublinear separators and polynomial expansion.  SIAM J. Discret. Math., 30:1095–1101, 2016.
  * [Epp00] David Eppstein.  Diameter and treewidth in minor-closed graph families.  Algorithmica, 27:275–291, 2000.
  * [FK99] Alan M. Frieze and Ravi Kannan.  Quick approximation to matrices and applications.  Combinatorica, 19:175–220, 1999.
  * [GGR98] Oded Goldreich, Shafi Goldwasser, and Dana Ron.  Property testing and its connection to learning and approximation.  Electron. Colloquium Comput. Complex., 3, 1998.
  * [GHT84] John R. Gilbert, Joan P. Hutchinson, and Robert E. Tarjan.  A separator theorem for graphs of bounded genus.  J. Algorithms, 5:391–407, 1984.
  * [GK11] Sevag Gharibian and Julia Kempe.  Approximation algorithms for qma-complete problems.  2011 IEEE 26th Annual Conference on Computational Complexity, pages 178–188, 2011.
  * [GP19] Sevag Gharibian and Ojas Parekh.  Almost optimal classical approximation algorithms for a quantum generalization of max-cut.  ArXiv, abs/1909.08846, 2019.
  * [GT13] Shayan Oveis Gharan and Luca Trevisan.  A new regularity lemma and faster approximation algorithms for low threshold rank graphs.  In APPROX-RANDOM, 2013.
  * [Has13] Matthew B. Hastings.  Trivial low energy states for commuting hamiltonians, and the quantum pcp conjecture.  Quantum Inf. Comput., 13:393–429, 2013.
  * [HM15] Aram Wettroth Harrow and Ashley Montanaro.  Extremal eigenvalues of local hamiltonians.  ArXiv, abs/1507.00739, 2015.
  * [HMS20] Aram Wettroth Harrow, Saeed Adel Mehraban, and Mehdi Soleimanifar.  Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems.  Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020.
  * [iKR10] Ken ichi Kawarabayashi and Bruce A. Reed.  A separator theorem in minor-closed classes.  2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 153–162, 2010.
  * [JKM18a] Vishesh Jain, Frederic Koehler, and Elchanan Mossel.  The mean-field approximation: Information inequalities, algorithms, and complexity.  In COLT, 2018.
  * [JKM18b] Vishesh Jain, Frederic Koehler, and Elchanan Mossel.  The vertex sample complexity of free energy is polynomial.  In COLT, 2018.
  * [JKR19] Vishesh Jain, Frederic Koehler, and Andrej Risteski.  Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective.  Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019.
  * [Kin22] Robbie King.  An improved approximation algorithm for quantum max-cut.  2022\.
  * [KPR93] Philip N. Klein, Serge A. Plotkin, and Satish Rao.  Excluded minors, network decomposition, and multicommodity flow.  In STOC ’93, 1993.
  * [KSV02] Alexei Y. Kitaev, Alexander Shen, and Mikhail N. Vyalyi.  Classical and quantum computation.  In Graduate studies in mathematics, 2002.
  * [Lie73] Elliott H. Lieb.  The classical limit of quantum spin systems.  Communications in Mathematical Physics, 31:327–340, 1973.
  * [LT77] Richard J. Lipton and Robert E. Tarjan.  A separator theorem for planar graphs.  Siam Journal on Applied Mathematics, 36:177–189, 1977.
  * [NdMW12] Jaroslav Nesetril, Patrice Ossona de Mendez, and David R. Wood.  Characterisations and examples of graph classes with bounded expansion.  Eur. J. Comb., 33:350–373, 2012.
  * [PT21a] Ojas Parekh and Kevin Thompson.  Application of the level-$2$ quantum lasserre hierarchy in quantum approximation algorithms.  In ICALP, 2021.
  * [PT21b] Ojas Parekh and Kevin Thompson.  Beating random assignment for approximating quantum 2-local hamiltonian problems.  ArXiv, abs/2012.12347, 2021.
  * [PT22] Ojas Parekh and Kevin Thompson.  An optimal product-state approximation for 2-local quantum hamiltonians with positive terms.  ArXiv, abs/2206.08342, 2022.
  * [Ris16] Andrej Risteski.  How to calculate partition functions using convex programming hierarchies: provable bounds for variational methods.  ArXiv, abs/1607.03183, 2016.
  * [RS86a] Neil Robertson and Paul D. Seymour.  Graph minors. ii. algorithmic aspects of tree-width.  J. Algorithms, 7:309–322, 1986.
  * [RS86b] Neil Robertson and Paul D. Seymour.  Graph minors. v. excluding a planar graph.  J. Comb. Theory, Ser. B, 41:92–114, 1986.
  * [RT12] Prasad Raghavendra and Ning Tan.  Approximating csps with global cardinality constraints using sdp hierarchies.  In SODA, 2012.
  * [Sze75] Endre Szemerédi.  Regular partitions of graphs.  1975\.
  * [Vaz03] Vijay V. Vazirani.  Approximation algorithms.  Approximation Algorithms, 2003.

##  Appendix A The Multi-Partite Self Decoupling Lemma

######  Lemma A.1.

Let $X_{1}\cdots X_{n}$ be classical random variables with some arbitrary
joint distribution, and fix integers $k,l<n$. Then

$\mathbb{E}_{0\leq m\leq l}\mathbb{E}_{\begin{subarray}{c}C\subset[n],\\\
|C|=m\end{subarray}}\mathbb{E}_{\begin{subarray}{c}u_{1}\cdots u_{k}\in
V\setminus C\\\ u_{i}\neq
u_{j}\end{subarray}}I(X_{u_{1}}:\cdots:X_{u_{k}}|X_{C})\leq\frac{k^{2}}{l}\mathbb{E}_{u}I(X_{u}:X_{V\setminus\\{u\\}})$
(124)

###### Proof.

We begin by expressing the multi-partite mutual information as bipartite,
followed by the chain rule of the mutual information:

$\displaystyle
I(X_{u_{1}}:\cdots:X_{u_{k}}|X_{C})=\sum_{j=1}^{k-1}I(X_{u_{1}}\cdots
X_{u_{j}}:X_{u_{j+1}}|X_{C})=$ (125)
$\displaystyle=\sum_{j=1}^{k-1}\sum_{i=1}^{j}I(X_{u_{i}}:X_{u_{j+1}}|X_{C},X_{u_{1}}\cdots
X_{u_{i-1}})$ (126)

Consider a single summand above, in expectation over uniformly random (and
without replacement) choices of $c_{1}\cdots c_{m},u_{1}\cdots u_{k}\in[n]$.

$\displaystyle\mathbb{E}_{\begin{subarray}{c}C\subset[n],\\\
|C|=m\end{subarray}}\mathbb{E}_{\begin{subarray}{c}u_{1}\cdots u_{k}\in
V\setminus C\\\ u_{a}\neq
u_{b}\end{subarray}}I(X_{u_{i}}:X_{u_{j+1}}|X_{C},X_{u_{1}}\cdots
X_{u_{i-1}})=$ (127)
$\displaystyle\mathbb{E}_{\begin{subarray}{c}u,c_{1}\cdots c_{m+1},u_{1}\cdots
u_{i-1}\in[n]\\\ \text{all
distinct}\end{subarray}}I(X_{u}:X_{c_{m+1}}|X_{c_{1}},\cdots
X_{c_{m}},X_{u_{1}}\cdots X_{u_{i-1}})$ (128)

in expectation over the choice of size of $C$ as well,

$\displaystyle\mathbb{E}_{0\leq m\leq
l}\mathbb{E}_{\begin{subarray}{c}C\subset[n],\\\
|C|=m\end{subarray}}\mathbb{E}_{\begin{subarray}{c}u_{1}\cdots u_{k}\in
V\setminus C\\\ \text{all
distinct}\end{subarray}}I(X_{u_{1}}:\cdots:X_{u_{k}}|X_{C})\leq$ (129)
$\displaystyle k\cdot\sum_{i=1}^{k-1}\mathbb{E}_{0\leq m\leq
l}\mathbb{E}_{\begin{subarray}{c}u,c_{1}\cdots c_{m+1},u_{1}\cdots
u_{i-1}\in[n]\\\ \text{all
distinct}\end{subarray}}I(X_{u}:X_{c_{m+1}}|X_{c_{1}},\cdots
X_{c_{m}},X_{u_{1}}\cdots X_{u_{i-1}})=$ (130) $\displaystyle
k\cdot\sum_{i=1}^{k-1}\mathbb{E}_{\begin{subarray}{c}u,c_{1}\cdots
c_{l+1},u_{1}\cdots u_{i-1}\in[n]\\\ \text{all
distinct}\end{subarray}}\mathbb{E}_{0\leq m\leq
l}I(X_{u}:X_{c_{m+1}}|X_{c_{1}},\cdots X_{c_{m}},X_{u_{1}}\cdots
X_{u_{i-1}})=$ (131)
$\displaystyle=\frac{k}{l}\cdot\sum_{i=1}^{k-1}\mathbb{E}_{\begin{subarray}{c}u,c_{1}\cdots
c_{l+1},u_{1}\cdots u_{i-1}\in[n]\\\ \text{all
distinct}\end{subarray}}I(X_{u}:X_{C_{\leq l+1}}|X_{u_{1}}\cdots X_{u_{i}})$
(132)

where first we used linearity of expectation, then we reordered the
expectation via the permutation invariance of the sampling distribution, and
finally applied the chain rule. To conclude, we can simply apply the
monotonicity relations $I(A:B|C),I(A:B)\leq I(A:BC)$

$\displaystyle\leq\frac{k}{l}\cdot\sum_{i=1}^{k-1}\mathbb{E}_{\begin{subarray}{c}u,c_{1}\cdots
c_{l+1},u_{1}\cdots u_{i-1}\in[n]\\\ \text{all
distinct}\end{subarray}}I(X_{u}:X_{C_{\leq l+1}},X_{u_{1}}\cdots
X_{u_{i}})\leq\frac{k^{2}}{l}\cdot\mathbb{E}_{u\in[n]}I(X_{u}:X_{[n]\setminus
u})$ (133)

∎

##  Appendix B The Volume of Feasible Set $K_{r,c,\gamma}$

In this appendix, we construct upper and lower bounds on the volumes of
feasible regions $K_{r,c,\gamma}\subset\mathbb{R}^{(d^{2}-1)n}$, the convex
set of feasible points to constraints $C_{r,c,\gamma}$ described in section
6.1. In particular, we argue that any product state is contained in at least
some feasible region $K_{r,c,\gamma}$ (for some choice of $r,c$), and moreover
said $K_{r,c,\gamma}$ is contained in a ball of radius $R_{u}$ centered at the
origin, and contains a ball of radius $R_{l}$. In this manner, by running a
convex program solver, say, the Ellipsoid algorithm up to a cutoff volume
$R_{l}^{(d^{2}-1)n}$ for every set of constraints $C_{r,c,\gamma}$, we are
guaranteed that every product state is in at least one of the feasible
$K_{r,c,\gamma}$ found by the algorithm.

Before beginning, let us define the corresponding set and radii
$\tilde{K}_{r,c,\gamma},\tilde{R}_{l},\tilde{R}_{u}$ for the compressed set
$\tilde{C}_{r,c,\gamma}$ given by the common refinements, which we return to
at the end of this section. For simplicity, let us begin with the upper bound.

######  Claim B.1.

Every product state $\rho$ is contained in some $K_{r,c,\gamma}$, where
$K_{r,c,\gamma}$ is contained in a ball of radius $R_{u}\leq d\cdot\sqrt{n}$
centered at the origin.

###### Proof.

Recall that each density matrix $\rho_{v}$ is specified by the vector
$(\alpha^{v}_{i})_{i\in[d^{2}]}$, where
$|\alpha^{v}_{i}|=|\text{Tr}[\sigma_{i}\rho^{v}]|\leq 1$. Thus the variable
space $\\{\alpha_{v}:v\in V\\}$ of valid product states is therefore contained
in a ball of radius

$R^{2}=\max_{\alpha\text{ valid}}\|\alpha\|_{2}^{2}=\sum_{v\in
V}\|\alpha^{v}\|^{2}_{2}\leq n\cdot d^{2}\Rightarrow R\leq d\cdot\sqrt{n}$
(134)

∎

The lower bound on $K_{r,c,\gamma}$ is more subtle. Conceptually, the lower
bound hinges on the idea of perturbing a carefully chosen feasible point away
from saturating any constraints, such that the perturbed point is a center for
a ball within $K_{r,c,\gamma}$. To find a suitable starting point, we observe
that the ’guesses’ $r,c$ are overlapping, and thereby for every product state
$\rho$ there is a choice of $r,c$ such that $\rho$ is already bounded away
from the regularity constraints.

######  Claim B.2.

Every product state $\rho$ is contained in some $K_{r,c,\gamma}$, where
$K_{r,c,\gamma}$ contains a ball of radius $R_{l}\geq O(\gamma)$.

###### Proof.

Consider an arbitrary product state $\rho$, let $\\{\alpha^{v}_{i}\\}_{v\in
V,i\in[d^{2}-1]}$ be its pauli basis description, and let
$r^{*},c^{*}\in[-n,n]^{(d^{4}\cdot s)}$ be its average subset magnetizations,
as defined in section 6.1. By definition of $I_{\gamma}$, there is a choice of
$r,c\in(I_{\gamma})^{(d^{4}\cdot s)}$ such that for each constraint $i,j,k$,
their ‘subset magnetizations’ are close $|r^{ijk}-r^{*,ijk}|\leq\gamma n/2$.
Note this is bounded $\gamma n/2$ away from saturating any magnetization
constraint. Our intention is now to perturb the description $\alpha$ by an
arbitrary vector $\delta$ of bounded $\|\delta\|_{\infty}$, and argue that the
resulting point is still feasible, to reason that
$K_{r^{\prime},c^{\prime},\gamma}$ contains a ball of radius
$\|\delta\|_{\infty}$. Since the magnetization constraints are linear and we
are already bounded away from their saturation, their analysis is quite
straightforward and we defer it to later. The main technical issue is that
this perturbation may violate a psd constraint, which we address by ’bumping
up’ all the eigenvalues of each $\rho_{u}$ which are smaller than some cutoff.
We formalize this notion in the following claim:

######  Claim B.3.

Let $Q=\mathbb{I}/d+\alpha\cdot\sigma/d\geq 0$ be a trace 1, Hermitian, PSD
matrix, and let $Q=\sum_{i}\lambda_{i}|\psi_{i}\rangle\langle\psi_{i}|$ be its
eigenbasis decomposition. Fix $d^{-1}>\delta>0$ and define the
$\delta$-truncation

$Q_{\delta}=\sum_{i:\lambda_{i}<\delta}\delta|\psi_{i}\rangle\langle\psi_{i}|+\sum_{i:\lambda_{i}\geq\delta}\lambda_{i}|\psi_{i}\rangle\langle\psi_{i}|,\tilde{Q}_{\delta}=\frac{Q_{\delta}}{\text{Tr}[Q_{\delta}]}$
(135)

Then
$\tilde{Q}_{\delta}\geq\frac{\delta}{2}\mathbb{I},\text{Tr}[\tilde{Q}_{\delta}]=1$,
and if $\alpha_{\delta}\in\mathbb{R}^{d^{2}-1}$ is the Pauli basis description
of $Q_{\delta}$, $\|\alpha-\alpha_{\delta}\|_{\infty}\leq d^{2}\delta$.

We defer the proof of this claim, and use it to note that if we
$\delta$-truncate the description $\alpha$ of each single qudit density matrix
in the product state $\rho$ to obtain $\alpha_{\delta}$, by linearity and the
triangle inequality we have that the average subset magnetizations
$r^{ijk}_{\delta},c^{ijk}_{\delta}$ have changed by at most
$n\cdot\|\alpha_{\delta}-\alpha\|_{\infty}\leq nd^{2}\delta$. For an
appropriate choice of constant $\delta=\Theta(\gamma/d^{2})=\Theta(\gamma)$,
we have constructed a feasible point $\alpha_{\delta}$ that is
$\delta/2=\Theta(\gamma)$ bounded away from the psd constraints, and
$\Theta(\gamma n)$ bounded away from the magnetization constraints. To
conclude, let us consider any perturbation $z\in\mathbb{R}^{(d^{2}-1)n}$ to
the description $\alpha_{\delta}$ to obtain $\alpha_{z}=z+\alpha_{\delta}$,
with a sufficiently small $\|z\|_{\infty}=\Theta(\gamma)$. Via the argument
above, $\alpha_{z}$ remains $\Theta(\gamma\cdot n)$ away from saturating the
magnetization constraints. Moreover, if
$\rho_{\alpha}\equiv\mathbb{I}/d+\alpha\cdot\sigma/d\geq 0$, then

$\|\rho_{\alpha}-\rho_{\alpha_{z}}\|_{\infty}=\frac{1}{d}\|\sum_{i}z_{i}\sigma_{i}\|_{\infty}\leq\frac{1}{d}\sum_{i}^{d^{2}}|z_{i}|\|\sigma_{i}\|_{\infty}\leq
d\|z\|_{\infty}$ (136)

and thus
$\rho_{\alpha+z}\geq(\frac{\delta}{2}-d\|z\|_{\infty})\mathbb{I}\geq\frac{\delta}{4}\mathbb{I}$
if $\|z\|_{\infty}\leq\frac{\delta}{2d}=\Theta(\gamma)$. Thus, we have
reasoned that every product state $\rho$ is contained in some
$K_{r,c,\gamma}$, which contains a feasible point $\alpha_{\delta}$ and a ball
of radius $\Theta(\gamma)$ around it. ∎

###### Proof of Claim B.3.

Note via the normalization that $\text{Tr}[\tilde{Q}_{\delta}]=1$. Let $m<d$
be the number of eigenvalues of $Q$ with $\lambda_{i}<\delta$, and recall
$\delta<1/d$. Then

$\displaystyle
1\leq\text{Tr}[Q_{\delta}]=\sum_{i:\lambda_{i}<\delta}\delta+\sum_{i:\lambda_{i}\geq\delta}\lambda_{i}=\sum_{i:\lambda_{i}<\delta}(\delta-\lambda_{i})+1\leq
1+d\delta\leq 2$ (137)
$\displaystyle\Rightarrow\tilde{Q}_{\delta}\geq\sum_{i:\lambda_{i}<\delta}\frac{\delta}{1+d\delta}|\psi_{i}\rangle\langle\psi_{i}|+\sum_{i:\lambda_{i}\geq\delta}\frac{\lambda_{i}}{1+d\delta}|\psi_{i}\rangle\langle\psi_{i}|,\tilde{Q}_{\delta}=\frac{Q_{\delta}}{\text{Tr}[Q_{\delta}]}\geq\frac{\delta}{2}\mathbb{I}$
(138)

Moreover,

$\displaystyle\tilde{Q}_{\delta}-Q=\sum_{i:\lambda_{i}<\delta}\bigg{(}\frac{\delta}{Tr[Q_{\delta}]}-\lambda_{i}\bigg{)}+\sum_{i:\lambda_{i}\geq\delta}\lambda_{i}\bigg{(}\frac{1}{Tr[Q_{\delta}]}-1\bigg{)}$
(139)
$\displaystyle\Rightarrow\|\tilde{Q}_{\delta}-Q\|_{\infty}\leq\max\bigg{(}\delta,\frac{\text{Tr}[Q_{\delta}]-1}{Tr[Q_{\delta}]}\bigg{)}\leq
d\delta$ (140)

Finally,
$\|\alpha-\alpha_{\delta}\|_{\infty}=\max_{i}|\text{Tr}[\sigma_{i}(Q-\tilde{Q}_{\delta})]|\leq\|\sigma_{i}\|_{1}\cdot\|\tilde{Q}_{\delta}-Q\|_{\infty}\leq
d^{2}\delta$ as claimed.

∎

Let us now return to the compressed constraints $\tilde{C}_{r,c,\gamma}$.
Recall how $\tilde{C}_{r,c,\gamma}$ is defined on $2^{O(s)}$ variables, such
that $\tilde{K}_{r,c,\gamma}$ is contained in a ball of radius
$\tilde{R}_{u}\leq 2^{O(s)}$ via Claim B.1. To prove the lower bound, we note
that WLOG we could have picked the starting product state $\rho$ in the proof
of Claim B.2 to be one in which the density matrices of the particles in each
refinement set $\mathcal{A}_{a}$ are all the same. The argument follows
immediately and we conclude $\tilde{R}_{l}\geq\Theta(\gamma)$.

##  Appendix C Regularity and Applications on $k$-Local Hamiltonians

In this section, we discuss extensions to our Hamiltonian regularity lemma to
‘dense’ $k$-Local Hamiltonians defined on qudits. Our strategy generically
follows the proof techniques of section 5, in first restricting our attention
to product states and developing a weak regularity result for these systems,
and then lifting the techniques to general entangled states via the product
state approximation toolkit from [BH13] (section 4). The cut decompositions we
construct can be understood simply as multi-colored versions of existing
regularity statements for hypergraphs by [FK99], and [AdlVKK02].

We organize this appendix as follows. In section C.1 we present and define the
Hamiltonian weak regularity lemma for these systems. Then, in section C.2, we
show how they can be used to develop algorithms. Once again, the general idea
is to exploit the low rank structure to the cut decomposition, and relax the
optimization problem to checking a series of Complex SDPs (or Conic programs).
Finally, in section C.3, we prove a generalization of our vertex sample
complexity results for $k$-local systems. Given how these results parallel
that of the 2-local case, we emphasize this section to proofs of the
modifications.

###  C.1 A Regularity Lemma

Let us assume the local dimension of each particle is $d=2^{d^{\prime}}=O(1)$,
and observe that the set of Pauli matrices $\mathcal{P}_{\log
d}=\\{I,X,Y,Z\\}^{\otimes\log d}$ on $\log d$ qubits defines a complete basis
for any single qudit density matrix. We begin by expressing any $k$-local
Hamiltonian over Qudits $H=\sum_{e\in E}h_{e}$, where $h_{e}$ acts non-
trivially on the $k$-hyperedge $e\in E$, through a Pauli basis decomposition,

$H=d^{-k}\sum_{\sigma\in(\mathcal{P}_{\log d})^{\otimes k}}\sum_{e\in
E}\text{Tr}[h_{e}\sigma_{e}\otimes\mathbb{I}_{V\setminus
e}]\sigma_{e}\otimes\mathbb{I}_{V\setminus e}$ (141)

where each $\sigma_{e}=\bigotimes_{j}^{k}\sigma_{e_{j}}$ is a $k$-qudit Pauli.

Note that we have re-ordered the summation to explicitly group the
interactions with the same basis. Indeed, each of $d^{2k}$ terms in the outer
summation will correspond to a different colour in the cut decomposition. We
can now explicitly define the tensors $M^{c}$ for each color $c\in[d^{2k}]$,
correspondent to the hyperedge adjacency matrix for edges which support the
Pauli term $\sigma^{c}$:

$M_{(u_{1}\cdots u_{k})}^{c}\equiv\text{Tr}[h_{(u_{1}\cdots
u_{k})}\sigma^{c}_{(u_{1}\cdots
u_{k})}\otimes\mathbb{I}_{V\setminus(u_{1}\cdots u_{k})}]\text{ where
}(u_{1}\cdots u_{k})\in([n])^{\times k}$ (142)

We note we can define every entry $(u_{1}\cdots u_{k})$ of $M^{c}$ WLOG, so
long as we compute the trace above in an appropriate order
$u_{i}<u_{j},i<j\in[k]$ in the tensor product. In this setting, the notion of
a cut decomposition for an array or ‘$k-$matrix’ as referred to by [AdlVKK02],
is simply a sum over a set of ‘cut arrays’:

######  Definition C.1.

For any real value $d\in\mathbb{R}$ and $k$ sets $S=S_{1}\cdots
S_{k}\subset[n]$, we define $CUT(d,S)$ to be a $k$-cut array as follows:

$CUT(d,S)_{i_{1}\cdots i_{k}}=\begin{cases}d&i_{1}\in S_{1}\cdots i_{k}\in
S_{k}\\\ 0&\text{ otherwise}\end{cases}$ (143)

We now have a choice on which tensor cut decomposition to use. The works by
[FK99] and [AdlVKK02] developed different high-dimensional generalizations to
cut decompositions, which differ in their accuracy and rank guarantees, as
well as their runtimes. The construction by [FK99] can be constructed
implicitly via sampling (in the probe model of computation) in time roughly
$2^{\tilde{O}(1/\epsilon^{2})}$, and provides a width $O(\epsilon^{2-2k})$.
Thus, this is the construction we discuss for our additive approximation
schemes which run in constant time. Correspondingly, the result by [AdlVKK02]
provides a better width, $O(1/\epsilon^{2})$, at the cost of polynomial
runtime in $n$. That’s the construction we use for the vertex sample
complexity, and for the explicit algorithms.

######  Theorem C.1 ([FK99]).

Let $J$ be an arbitrary $k$-dimensional matrix on $X_{1}\times\cdots\times
X_{k}$ where we assume that $k\geq 2$ is a fixed constant $k=O(1)$. Let
$N=|X_{1}|\cdots|X_{k}|$ and $\epsilon,\delta>0$. Then, with probability
$1-\delta$ and in time $2^{\tilde{O}(1/\epsilon^{2})}/\delta^{2}$ we can find
a cut decomposition of width $O(\epsilon^{2-2k})$, error $\epsilon\cdot
N^{1/2}\cdot\|J\|_{F}$, and coefficient length $O(\|J\|_{F}/\sqrt{N})$.

######  Theorem C.2 ([AdlVKK02]).

In the setting of Theorem C.1, in time $2^{O(1/\epsilon^{2})}O(N\log
1/\delta)$ and with probability at least $1-\delta$, we can find a cut
decomposition of width $O(\epsilon^{-2})$, error at most
$\epsilon\sqrt{N}\|J\|_{F}$, and the following bound on the coefficient
length: $\sum_{i}|d_{i}|\leq 2\|J\|_{F}/\epsilon\sqrt{N}$, where
$(d_{i})^{s}_{i=1}$ are the coefficients of the cut arrays.

######  Remark C.1.

The error referred to in the theorems above is in the cut norm
$\|\cdot\|_{C}$. As discussed in [AdlVKK02], it is equivalent to the statement
that

$\|W\|_{\infty\rightarrow 1}=\max_{x_{1}\cdots
x_{k}\in\mathbb{R}^{n},\|x_{i}\|_{\infty}=1}\bigg{|}\sum_{i_{1}\cdots
i_{k}\in[n]}W_{i_{1}\cdots i_{k}}\prod_{j}x_{j,i_{j}}\bigg{|}\leq
2^{k}\|W\|_{C}$ (144)

In this setting, we apply either of the theorems above to each of $d^{2k}$
coloured tensors $M^{c}$ to obtain cut decompositions $M^{c}=D^{c}+W^{c}$,
with cuts $D^{c}=\sum^{s}_{i=0}D^{c,i}$ of width $s$ and error tensor $W^{c}$.
Finally, we recompose them to define our Hamiltonian cut decomposition:

$H_{D}=\frac{1}{k!d^{k}}\sum_{c\in[d^{2k}]}\sum_{i=0}^{s}\sum_{e\in[n]^{k}\atop
e_{a}\neq e_{b}}D^{c,i}_{e}\sigma^{c}_{e}\otimes\mathbb{I}_{V\setminus e}$
(145)

where $\sigma^{c}_{e}$ is the Pauli matrix on $k$ qudits acting on a hyperedge
$e$, indexed the color $c\in[d^{2k}]$, and we implicitly order the tensor
product in $\sigma^{c}_{e}$ such that $e_{a}<e_{b},a<b\in[k]$ with a factor of
$k!$ from a hand-shaking argument. For simplicity, in the claim below we
restrict our attention to local Hamiltonians $H$ of $m$ hyper-edges of bounded
strengths $\|h_{e}\|_{\infty}\leq 1$, although the proofs are readily
generalizable. Following our proof techniques we immediately readout a claim
over product states:

######  Claim C.1.

Fix $d,k=O(1)$. For any product state over $n$ qudits $\rho=\otimes_{u\in
V}\rho_{u}$, and $H_{D}$ defined as above, then
$|\text{Tr}[(H-H_{D})\rho]|\leq\epsilon n^{k/2}\sqrt{m}$. .

###### Proof.

Let us make the observation that any Pauli matrix $\sigma^{c}$ defined on $k$
qudits can be expressed as the tensor product of $k$ single-qudit Paulis
$\sigma^{c}=\bigotimes_{j}^{k}\sigma^{c,j}$, and reduce the energy difference
to an expression of the $\infty\rightarrow 1$ norm by removing the diagonal
terms:

$\displaystyle\bigg{|}\text{Tr}[(H-H_{D})\rho]\bigg{|}\leq\frac{1}{d^{k}k!}\sum_{c\in[d^{2k}]}\bigg{|}\sum_{e\in[n]^{k}\atop
e_{a}\neq
e_{b}}W^{c}_{e}\prod_{j}^{k}\text{Tr}[\sigma^{c,j}\rho_{e_{j}}]\bigg{|}\leq$
(146)
$\displaystyle\leq\frac{1}{d^{k}k!}\sum_{c\in[d^{2k}]}\bigg{(}\|W^{c}\|_{\infty\rightarrow
1}+k^{2}n^{k-2}\sum_{v}\max_{v,e^{\prime}}|W^{c}_{v,v,e^{\prime}}|\bigg{)}$
(147)

If we instantiate $H_{D}$ using Theorem C.1, the maximum diagonal term is
$\max_{v,e^{\prime}}|W^{c}_{v,v,e^{\prime}}|=s^{1/2}\|J\|_{F}n^{-k/2}=\epsilon^{1-k}\|J\|_{F}n^{-k/2}$
by the Cauchy-Schwartz inequality on the coefficient length, and thus
$k^{2}n^{k-2}\sum_{v}\max_{v,e^{\prime}}|W^{c}_{v,v,e^{\prime}}|\leq\|W^{c}\|_{\infty\rightarrow
1}$ if $n=\omega(\epsilon^{-k}).$ In Theorem C.2 the maximum diagonal term is
$\sum_{i}|d_{i}|\leq 2\|J\|_{F}n^{-k/2}/\epsilon$, and thus
$k^{2}n^{k-2}\sum_{v}\max_{v,e^{\prime}}|W^{c}_{v,v,e^{\prime}}|\leq\|W^{c}\|_{\infty\rightarrow
1}$ if $n=\omega(\epsilon^{-2}).$ In either case we prove the claim.

∎

######  Lemma C.1.

In the context of Claim C.1, $\|H-H_{D}\|\leq\epsilon n^{k/2}m^{1/2}$

###### Proof.

Follows from the proof of Lemma 5.1, Claim C.1 and the product state
approximation Theorem 4.1, and the observation that
$m^{2/3}n^{(k-1)/3}=o(n^{k/2}m^{1/2})$. ∎

###  C.2 Algorithms for $k$-local Hamiltonians

We prove a generalization to the results in section 6.2, on approximation
schemes for dense $k$ local systems. The main conclusion of this section is a
sampling algorithm which approximates the ground state energy of a given $k$
local Hamiltonian $H$ up to an additive error of $\epsilon\cdot
n^{k/2}m^{1/2}$:

######  Theorem C.3.

Fix $d,k=O(1)$, and let $H$ be a $k$ local Hamiltonian on $n$ qudits of local
dimension $d$ and $m$ bounded strength interactions. Then there exists an
algorithm to estimate the ground state energy of $H$ up to an additive error
of $\epsilon\cdot n^{k/2}m^{1/2}$ in time $2^{\tilde{O}(\epsilon^{2-2k})}$ and
is correct with probability $.99$.

This algorithm is analogous to the 2-local case in section 6.2, and is based
on implicitly generating a cut decomposition $H_{D}$ of $H$ using Lemma C.1,
instantiated with the higher-dimensional array cut decomposition by [FK99].
Thus, for conciseness we focus this section on the proofs of the necessary
modifications. At the end of this section, we discuss how an explicit approach
using the array cut decomposition by [AdlVKK02] enables us to devise sub-
exponential time algorithms whenever $m=\tilde{\Omega}(n^{k-1})$. We begin by
briefly discussing the algorithm description to introduce notation and the
modifications to the relaxation scheme, and to present the runtime of the
approximation scheme. Afterwards, we detail the modifications to the
correctness proofs.

Recall how $H_{D}$ can be understood as a multi-colored cut decomposition with
$d^{2k}$ different ‘colors’, each color incurring $s$ (the width) different
cuts, and each cut incurring a partition of the vertices into $k$ different
partitions. The common refinement/coarsest partition of this set of $k\cdot
d^{2k}\cdot s$ different subsets is a set of $A=2^{k\cdot d^{2k}\cdot s}$
subsets. We estimate the sizes $|\hat{\mathcal{A}}_{a}|$ of each of these
subsets $a\in[A]$, up to some additive accuracy $O(\gamma/A\cdot n)$, by
random sampling using Claim 6.3. Now, for each cut $i$ in the decomposition
and for each subset $j\in[k]$ in cut $i$, we define a ‘guess’ $r^{i}_{j}\in
I_{\gamma}\subset[-n,n]$ for its average magnetization in the direction
indicated by the decomposition. For each guess vector
$\vec{r}\in(I_{\gamma})^{k\cdot d^{2k}\cdot s}$, we define the convex set of
constraints $C_{\vec{r},\gamma}$ by analogously defining a linear inequality
constraint over the average magnetization of each of $k$ sides of each cut. We
correspondingly define the compressed set of constraints
$\tilde{C}_{\vec{r},\gamma}$, and the set $\hat{C}_{\vec{r},\gamma}$ defined
on the size estimates $|\hat{\mathcal{A}}_{a}|$. The algorithm enumerates over
choices of $\vec{r}$, checking the feasibility of $\hat{C}_{\vec{r},\gamma}$
and outputting

$\hat{V}_{\gamma}=\min_{\vec{r}:\hat{C}_{\vec{r},\gamma}\text{ feasible
}}\sum_{i}d_{i}\prod_{j}^{k}r^{i}_{j}$ (148)

Where $d_{i}$ is the coefficient of the $i$th cut in the entire multi-colored
decomposition, $i\in[d^{2k}\cdot s]$. We readoff that the number of choices of
$\vec{r}$, and thereby the SDP’s we need to check the feasibility of is
$(2/\gamma+1)^{k\cdot d^{2k}\cdot s}=2^{O(\epsilon^{2-2k}\log 1/\gamma)}$ if
we use the implicit cut decomposition by [FK99] in Theorem C.1, and assume
$d,k=O(1)$. The number of partitions in the common refinements/coarsest
partition of these subsets is $A=2^{k\cdot d^{2k}\cdot
s}=2^{O(\epsilon^{2-2k})}$. We conclude in this fashion that the runtime of
implicitly constructing the Hamiltonian cut decomposition, estimating the
sizes of the $A$ different coarsest partitions, and solving the
$2^{O(\epsilon^{2-2k}\log 1/\gamma)}$ different convex programs on
$2^{O(\epsilon^{2-2k})}$ variables using Theorem 6.2, is
$2^{O(\epsilon^{2-2k}\log 1/\gamma)}/\delta^{2}$ with probability $1-\delta$.

To prove correctness and in particular the accuracy guarantees, the main claim
missing is a generalization of Lemma 6.1, which we present in Claim C.2. That
is, we need to guarantee that any product state which is feasible for the
constraints, must have energy close to its guess. This key claim ensures
immediate generalizations of Lemmas 6.3 and corollary 6.1, which proves that
the energy ‘estimate’ output by the algorithm is close to the minimum energy
of $H_{D}$ among product states.

######  Claim C.2.

If a product state $\rho$ is feasible for the constraints
$C_{\vec{r},\gamma}$, then

$\bigg{|}\text{Tr}[H_{D}\rho]-\sum
d^{i}\prod_{j=1}^{k}r^{i}_{j}\bigg{|}\leq\begin{cases}O(\gamma\cdot
s^{1/2}\cdot n^{k/2}\|J\|_{F})\text{ under thm }\ref{theorem-
kmatrixregfrieze}\\\ O(\frac{\gamma}{\epsilon}\cdot n^{k/2}\|J\|_{F})\text{
under thm }\ref{theorem-kmatrixreg}\end{cases}$ (149)

where we distinguish whether we generate the Hamiltonian cut decomposition
$H_{D}$ using Theorem C.1 or C.2.

In the above, recall $J$ is the array of interaction strengths of $H$,
$J_{e}=\|H_{e}\|_{\infty}$ where $e$ is a $k$-tuple over $[n]$. The proof of
the above follows from a simple technical claim, which we defer to the end of
this section and present in Claim C.3. Beforehand, let us briefly argue that
C.2 concludes the proof of correctness. It will later prove relevant to first
present a statement for the noiseless constraints, and their objective
$V_{\gamma}$:

######  Corollary C.1 (A generalization of Lemma 6.3).

$V_{\gamma}$ is an $\epsilon\cdot n^{k/2}\cdot\|J\|_{F}$ additive error
approximation to $\min_{\rho=\otimes\rho_{u}}\text{Tr}[H_{D}\rho]$, so long as
$H_{D}$ is generated using Theorem C.2 and $\gamma=O(\epsilon^{2})$, or,
$H_{D}$ is generated using Theorem C.1 and $\gamma=O(\epsilon^{k})$.

By a brief modification to the feasibility statements in C.2, we extend the
argument in the corollary above to the constraints $\hat{C}_{\vec{r},\gamma}$.
Recall $\hat{C}_{\vec{r},\gamma}$ is defined over estimates of the actual size
of the common refinements. We argue the objective value $\hat{V}_{\gamma}$ is
robust to these noisy estimates, so long as the tolerance $\gamma$ is small
enough, and the noise to the size estimates is bounded.

######  Corollary C.2.

Let $H_{D}$ be the Hamiltonian cut decomposition of a $k$-Local Hamiltonian
$H$ using Theorem C.1, and assume we have estimates $|\hat{\mathcal{A}}_{a}|$
for the sizes of each subset $a\in[A]$ in the coarsest partition of the cuts
in $H_{D}$ which are accurate up to additive error $\gamma/(4A)\cdot n$. Then,
$\hat{V}_{O(\epsilon^{k})}$ is an $\epsilon\cdot n^{k/2}\cdot\|J\|_{F}$
additive error estimate to $\min_{\rho=\otimes\rho_{u}}\text{Tr}[H_{D}\rho]$.

The proof of the corollary above is the same as Claim 6.4. By direct
application of Claim 6.3, we can compute these estimates efficiently to within
the intended accuracy guarantees. By combining the corollary above with the
guarantees in Claim C.1 and Lemma C.1, we ensure $\hat{V}_{O(\epsilon^{k})}$
is an $\epsilon\cdot n^{k/2}m^{1/2}$ additive error approximation to the
ground state energy $\min_{\rho}\text{Tr}[H\rho]$, as intended.

To conclude the proof of correctness, we present the missing claim.

######  Claim C.3.

Let $d_{i}$, $x_{i}^{j}$, $y_{i}^{j}$ for $j\in[k]$ and $i\in[s]$ be numbers
such that $|x_{i}^{j}|,|y_{i}^{j}|\leq n,|x_{i}^{j}-y_{i}^{j}|\leq\gamma\cdot
n$ and either (1) $\sum_{i}d_{i}^{2}=O(\|J\|_{F}/n^{k/2})$ or (2)
$\sum_{i}|d_{i}|=O(\|J\|_{F}/\epsilon n^{k/2})$. Then,

$\displaystyle(1)\bigg{|}\sum d_{i}\prod_{j}x_{i}^{j}-\sum
d_{i}\prod_{j}y_{i}^{j}\bigg{|}=O(\gamma\cdot s^{1/2}\cdot
n^{k/2}\|J\|_{F})\text{ and }$ (150) $\displaystyle(2)\bigg{|}\sum
d_{i}\prod_{j}x_{i}^{j}-\sum d_{i}\prod_{j}y_{i}^{j}\bigg{|}=O(\gamma\cdot
s\cdot n^{k/2}\|J\|_{F})\leq O(\frac{\gamma}{\epsilon}\cdot n^{k/2}\|J\|_{F})$
(151)

###### Proof.

$\bigg{|}\sum d_{i}\prod_{j}x_{i}^{j}-\sum
d_{i}\prod_{j}y_{i}^{j}\bigg{|}\leq\sum|d_{i}|\cdot\bigg{|}\prod_{j}x_{i}^{j}-y_{i}^{j}\bigg{|}$
(152)

In case (1), we apply the Cauchy-Schwartz inequality as before, with the
observation $\big{|}\prod_{j}x_{i}^{j}-\prod_{j}y_{i}^{j}\big{|}\leq
k\cdot\gamma\cdot n^{k}$, obtaining the error intended. In case (2), we simply
upper bound $\big{|}\prod_{j}x_{i}^{j}-\prod_{j}y_{i}^{j}\big{|}$. ∎

###### Proof.

[of Claim C.2] Let $\rho$ be a product state with vector of true average
subset magnetizations $\vec{r}$. We know that the energy of $\rho$ is roughly
a function of $\vec{r}$, up to the ‘self-edges’ which appear in the cut
decomposition:

$\bigg{|}\text{Tr}[H_{D}\rho]-\sum_{i}d_{i}\prod_{j}^{k}r^{i}_{j}\bigg{|}\leq
k^{2}n^{k-1}\max_{v,e^{\prime}}|W^{C}_{v,v,e^{\prime}}|\leq\epsilon
n^{k/2}\|J\|_{F}\text{(see Claim \ref{claim-kdpsreg})}$ (153)

and thereby with Claim C.3 and the appropriate choice of $\gamma$ for each cut
decomposition we conclude the claim. ∎

To conclude this section, we remark that we could have performed all of the
steps above explicitly, using the explicit higher-dimensional cut
decomposition by [AdlVKK02] presented in Theorem C.2. We show this gives us
sub-exponential time algorithms in almost the entire regime where product
states give extensive additive error approximations to the ground state
energy:

######  Theorem C.4.

Fix $d,k=O(1)$ and $\epsilon>0$. Let $H=\sum_{e}h_{e}$ be a $k$-Local
Hamiltonian on $n$ qudits of local dimension $d$, and $m=\Omega(n^{k}\log n)$
interactions of bounded strength $\|h_{e}\|_{\infty}\leq 1$. There exists a
randomized algorithm which runs in time $\tilde{O}(n^{k})\cdot
2^{\tilde{O}(n^{k}/\epsilon^{2}m)}$, and with high probability computes an
estimate for the ground state energy of $H$ accurate up to an additive error
of $\epsilon\cdot m$.

###### Proof.

As discussed in corollary C.1, the estimate $V_{O(\epsilon^{\prime 2})}$ for
the variational minimum energy using the cut decomposition $H_{D}$
instantiated with Theorem C.2 is an $\epsilon^{\prime}\cdot n^{k/2}\cdot
m^{1/2}$ approximation to the variational minimum energy of $H_{D}$. If we
pick $\epsilon^{\prime}=\epsilon\cdot m^{1/2}n^{-k/2}/2$, this is a
$\epsilon\cdot m/2$ additive error. By Claim C.1 and Theorem 4.1, this ensures
a $\epsilon\cdot m+O(n^{(k-1)/3}m^{2/3})\leq 2\epsilon\cdot m$ for any
constant $\epsilon=O(1)$ and $m=\Omega(n^{k-1}\log n)$. The resulting runtime
of this scheme is dominated by that of computing the cut decomposition and
solving the $2^{\tilde{O}(\epsilon^{\prime-2})}=2^{O(n^{k}\log
n/\epsilon^{2}m)}$ convex programs. To ensure the correctness guarantees with
high probability, we repeat the algorithm $\log n$ times and output the
product state of minimum energy. ∎

###  C.3 Vertex Sample Complexity for $k$-Local Hamiltonians

In this section we prove a generalization of the vertex sample complexity
result for 2-Local Hamiltonians to $k$-Local Hamiltonians, following the
techniques in section 7. The main result of this section was presented in
Theorem 2.8. Recall we assume the locality $k$ and the local dimension of the
quantum particles $d$ to be both $O(1)$.

First of all, let us reason on the cut decomposition $H_{D}$ of $H$, using the
result in Theorem C.2 by [AdlVKK02]. We note that under this decomposition, we
have introduced $O(d^{2k}/\epsilon^{2})$ $k-$cuts in the graph, and thereby
the coarsest partition of the cuts is a family of $A=2^{O(1/\epsilon^{2})}$
subsets of $[n]$, asymptotically the same as in the 2-local case. Crucially,
the structure of the compressed constraints $\tilde{C}_{\vec{r},\gamma}$ is
the same as in section 7: there is a $d\times d$ density matrix defined for
each subset $a\in[A]$, a trace and PSD constraints, and the relaxed average
magnetization constraints. Once placed in standard form, we observe the
duality arguments are entirely unmodified. Moreover, we have already proved a
generalization to Lemma 6.1 in Claim C.2, guaranteeing the properties of
$V_{\gamma}$ and how it relates to the minimum energy over product states of
$H_{D}$. In this manner, up to irrelevant constant factors of $d,k$ the only
modifications we require to prove Theorem 2.8 are Corollary 7.1, on product
state approximations to the ground state energy and Lemma 7.1, on the cut norm
of random restrictions of arrays with small cut norm.

Fortunately, our product state approximations on $k$-local systems in Theorem
4.1 present a generalization to Corollary 7.1:

######  Corollary C.3.

Fix $d,k=O(1)$. Given a $k$-Local Hamiltonian $H=\sum_{e}H_{e}$ on $n$ qudits
and $m$ interactions of strength bounded by $\|H_{e}\|_{\infty}\leq 1$, there
exists a product state $\sigma$ such that

$\text{Tr}[H\sigma]\leq\lambda_{min}(H)+O(n^{\frac{k-1}{3}}m^{2/3})$ (154)

To conclude, we use a theorem by [AdlVKK02] on the cut norm of random
restrictions of arrays with small cut norm, which they proved as a higher
dimensional generalization to the previously discussed Theorem 7.2. In
particular,

######  Theorem C.5 ([AdlVKK02], Theorem 6).

Fix $\epsilon,\delta>0$. Let $W$ be a $k$ dimensional array, with bounded
norms $\|W\|_{\infty}=O(\epsilon^{-1}),\|W\|_{\infty\rightarrow 1}\leq\epsilon
n^{k}$, and $\|W\|_{F}\leq O(n^{k})$. Suppose $Q$ is a random subset of $[n]$
of size $q=\Omega(\delta^{-5}\epsilon^{-4}\log 1/\epsilon)$, and let $W_{Q}$
be the sub-matrix defined by the restriction of $W$ to $Q$. Then, with
probability $1-\delta$, $\|W_{Q}\|_{\infty\rightarrow 1}\leq
O(\epsilon/\sqrt{\delta}\cdot q^{k})$, $\|W_{Q}\|_{F}\leq
O(q^{k}/\sqrt{\delta})$.

[AdlVKK02] use the above to prove that a random restriction of the cut
decomposition, is still a valid and accurate cut decomposition for the induced
subgraph on the sample. We apply their statement to derive an analogous
statement to Lemma 7.1 for $k$-local systems.

######  Lemma C.2.

Let $H_{D_{Q}}$ be the sub-hamiltonian of the decomposition $H_{D}$ of support
only in the random set $Q\subset V$. Then with probability $1-\delta$ over the
choice of $Q$, for every product state $\rho_{Q}$ on $Q$,

$\bigg{|}\text{Tr}[(H_{Q}-H_{D_{Q}})\rho]\bigg{|}\leq
O(\epsilon/\sqrt{\delta}\cdot q^{k}),$ (155)

so long as $q=\Omega(\delta^{-5}\epsilon^{-4}\log 1/\epsilon)$.

###### Proof.

Consider the $d^{2k}=O(1)$ ‘error’ arrays $W^{c}$, for each ‘color’
$c\in[d^{2k}]$ in the generalized Pauli basis decomposition. We note the
arrays $W^{c}$ fit the norm guarantees of Theorem C.5 [AdlVKK02] by
construction, see Theorem C.2. By a union bound over all $d^{2k}=O(1)$ arrays,
we are guaranteed that with probability $1-\delta$,
$|\text{Tr}[(H_{Q}-H_{D_{Q}})\rho]|\leq\sum_{c}\|W^{c}_{Q}\|_{\infty\rightarrow
1}\leq O(\epsilon/\sqrt{\delta}\cdot q^{k})$ for all product states $\rho$, so
long as $q=\Omega(\delta^{-5}\epsilon^{-4}\log 1/\epsilon)$. ∎

##  Appendix D Regularity and Applications on Low-Threshold Rank Hamiltonians

Let us now turn to extending the Hamiltonian regularity lemma to 2-Local
Hamiltonians on graphs of low threshold rank. Following the proof techniques
of the previous sections, we begin by devising a cut decomposition for these
systems by considering multi-coloured versions of the cut decomposition for
low threshold rank graphs by [GT13]. Unfortunately, the structure of these
systems will prohibit us from exhibiting a clean spectral characterization of
the decomposition as in Lemma 5.1, however, combined with our assymetric
product state approximations, we will use them to devise extensive error
approximation algorithms for these 2-local quantum systems.

We present two results in this section. The first of which is an algorithm for
2-Local Hamiltonians on ‘generic’ low threshold rank interaction graphs. It
highlights the main challenges in establishing a regularity lemma for quantum
systems on these graphs, and develops the main algorithmic techniques we use.
Our second and main result of this section is a classical algorithm for
Quantum Max Cut on low threshold rank graphs, discussed in Theorem 2.5. We
show how the symmetry in the Quantum Max Cut Hamiltonian in different basis
enables us to apply the ‘common refinement’ technique discussed in section 6,
and compress the size of the resulting optimization program, which we were not
able to do on general low threshold rank Hamiltonians.

###  D.1 A Regularity Lemma

The $\delta$-SOS threshold rank of a graph $G$ is the number of eigenvalues in
the normalized adjacency matrix of $G$ outside of the range
$[-\delta,\delta]$. In the more general case of a real symmetric matrix $J$,
we define the normalized adjacency matrix $J_{D}$ of $J$ in terms of
‘effective degrees’. For each row $u$, let the effective degree
$d_{u}=\sum_{v}|J_{uv}|$, $D=\text{diag}(d_{u},u\in[n])$ be the diagonal
matrix of degrees, and $J_{D}=D^{-1/2}JD^{-1/2}$.

######  Definition D.1.

The $\delta$-SOS threshold rank of a symmetric real matrix $J$ is defined to
be $t_{\delta}(J_{D})=\sum_{i:|\lambda_{i}|\geq\delta}\lambda_{i}^{2}$, where
$\lambda_{1}\cdots\lambda_{n}$ are the eigenvalues of $J_{D}$.

The weak regularity lemma by [GT13] for low threshold rank matrices is based
on designing a cut decomposition for a low rank approximation of $J_{D}$. In
their decomposition, the notion of a ‘cut matrix’ is now a weighted complete
bipartite sub-graph, CUT$(S_{1},S_{2},\alpha)=\alpha\cdot
d_{S_{1}}d^{T}_{S_{2}}$, where here we indicate $d_{S}$ as the vector of
degrees $(d_{S})_{i}=d_{i}$ if $i\in S$, $0$ otherwise. They prove:

######  Theorem D.1.

[[GT13]] Let $J$ be a real symmetric matrix, $\epsilon>0$, and $t\equiv
t_{\epsilon/2}(J_{D})$. Then there exists a cut decomposition of $J=\sum
D^{(i)}+W$ of width $O(t\epsilon^{-2})$, error $\|W\|_{\infty\rightarrow
1}\leq\epsilon\cdot|J|_{1}$, and where each coefficient of the decomposition
satisfies $|\alpha_{i}|\leq O(\sqrt{t}/|J|_{1})$. Furthermore, this
decomposition can be found in poly$(n,\epsilon^{-1},t)$ time.

We use this theorem to define decompositions for 2-Local Hamiltonians
$H=\sum_{(u,v)\in E}H_{u,v}\otimes\mathbb{I}_{V\setminus(u,v)}$ on qudits
whose Pauli interaction graphs are undirected and each have low threshold
rank. That is, let $H=\sum_{a,b\in[d^{2}]}\sum_{(u,v)\in
E}h_{uv}^{ab}\sigma_{u}^{a}\otimes\sigma_{v}^{b}\otimes\mathbb{I}_{V\setminus(u,v)}$
be a Pauli basis decomposition of $H$, and let
$J^{ab}=\\{h^{ab}_{uv}\\}_{u,v\in[n]}$ be the $(a,b)\in[d^{2}]^{2}$
interaction matrix of $H$. By undirected, we simply mean that
$h_{uv}^{ab}=h_{vu}^{ab}$, and thus $J^{ab}$ can be considered the adjacency
matrix of a weighted undirected graph. We refer to the effective
$(a,b)$-degree of a vertex $u$ as $d_{u}^{a,b}=\sum_{v}|J^{a,b}_{uv}|$, and
note that we assume $d^{a,b}=d^{b,a}$.

Let $J^{a,b}_{D}$ be the normalized adjacency matrix for the interaction
$(a,b)$. In this setting, the ‘threshold rank’ we consider is the maximum
$\delta$-SOS threshold rank $t\equiv\max_{a,b}t_{\epsilon/2}(J^{a,b}_{D})$
among the interactions $a,b$. If this $t$ is sufficiently small, then we can
apply the framework of [GT13] to our setting efficiently. In particular, we
use Theorem D.1 on each $J^{(a,b)}$ for $(a,b)\in[d^{2}]^{2}$, obtaining cuts
$(R^{a,b,i},L^{a,b,i})$ and cut matrices $D^{(a,b,i)},i\in[s]$ in
$\text{poly}(n,t,1/\epsilon)$ time. Now, we would like to follow our ideas in
section 5 and express a Hamiltonian $H_{D}$

$H_{D}=\frac{1}{2}\sum_{a,b\in[d],i\in[s]}\sum_{u\neq
v}D^{(a,b,i)}_{u,v}\sigma_{u}^{a}\otimes\sigma_{v}^{b}.$ (156)

However, this unfortunately does not necessarily preserve the energy of
product states. If the cut decomposition generated only disjoint cuts
($R^{a,b,i}\cap L^{a,b,i}=\emptyset$) such that the diagonal entries of
$D^{(a,b,i)}$ are all 0, then indeed we would recover the product state
statement $|\text{Tr}[(H-H_{D})\rho]|\leq\|W\|_{\infty\rightarrow 1}$ and the
ensuing spectral bound. Instead, we can only prove the weaker statement with
the self-edges:

######  Claim D.1.

Let $H=\sum_{e}H_{e}$ be a 2-Local Hamiltonian defined on qudits of local
dimension $d=O(1)$, and let $J_{u,v}=\|H_{(u,v)}\|_{\infty}$ be the matrix of
interaction strengths. Let $t\equiv\max_{a,b}t_{O(\epsilon)}(J^{a,b}_{D})$ be
the maximum threshold rank among the Pauli interactions $a,b\in[d^{2}]$, and
let $D^{(a,b,i)}=$ CUT$(R^{a,b,i},$
$L^{a,b,i},\alpha^{a,b,i}),i\in[O(t\epsilon^{-2})]$ be a cut decomposition of
each $J^{a,b}$ using Theorem D.1. Then, for all product states
$\rho=\otimes_{u}\rho_{u}$

$\bigg{|}\text{Tr}[H\rho]-\frac{1}{2}\sum_{a,b\in[d^{2}]\atop
i\in[s]}\alpha^{a,b,i}\bigg{(}\sum_{u\in
R^{a,b,i}}d^{a,b}_{u}\cdot\text{Tr}[\sigma^{a}\rho_{u}]\bigg{)}\bigg{(}\sum_{v\in
L^{a,b,i}}d^{a,b}_{v}\cdot\text{Tr}[\sigma^{b}\rho_{v}]\bigg{)}\bigg{|}\leq\epsilon\cdot|J|_{1}$
(157)

###### Proof.

Let $W^{a,b}=J^{a,b}-\sum_{i}D^{a,b,i}$ be the $n\times n$ error matrices in
the cut decomposition, and note that the error above is exactly

$=\bigg{|}\sum_{a,b}\sum_{u,v}W^{a,b}_{u,v}\text{Tr}[\sigma^{a}\rho_{u}]\text{Tr}[\sigma^{b}\rho_{v}]\bigg{|}\leq\sum_{a,b}\|W^{a,b}\|_{\infty\rightarrow
1}\leq\epsilon\cdot d^{4}\cdot|J|_{1}$ (158)

by appropriately rescaling $\epsilon$ and the width of the decomposition we
prove the claim. ∎

###  D.2 Algorithms for Low-Threshold Rank Hamiltonians

In this section, we discuss two algorithms for local Hamiltonians configured
on low threshold rank graphs. The first of which is the natural generalization
of the techniques in section 6, in relaxing the optimization program to
checking the feasibility of a small number of convex programs. However, in the
general case that $H$ is composed of multiple distinct low threshold rank
interaction graphs, we will not be able to perform the common refinement
technique analogous to section 6 to compress these convex constraints into a
constant number of variables. Instead, for our second algorithm we restrict
our attention to the Quantum Max Cut on on low threshold rank graphs, and show
how for these systems with further symmetry in their interaction graph the
compression technique holds and leads to faster algorithms.

To begin, let us consider a 2-Local Hamiltonian $H$ on $n$ qubits whose Pauli
graphs are undirected and of maximum threshold rank
$t=\max_{a,b}t_{O(\epsilon)}(J^{a,b}_{D})$. In the setting of Claim D.1, the
energy of $H$ on any product state $\rho=\otimes\rho_{u}$ is

$\text{Tr}[H\rho]\approx\frac{1}{2}\sum_{a,b\in[d^{2}]}\sum_{k\in[s]}\alpha^{a,b,k}\bigg{(}\sum_{u\in
R^{a,b,k}}d_{u}^{a,b}\text{Tr}[\sigma_{u}^{a}\rho_{u}]\bigg{)}\cdot\bigg{(}\sum_{u\in
L^{a,b,k}}d_{v}^{a,b}\text{Tr}[\sigma_{v}^{b}\rho_{v}]\bigg{)}$ (159)

We establish a series of inequality constraints on the weighted magnetizations
above, to relax this non-convex optimization problem over product states to a
convex feasibility problem. In particular, since $\sum_{u\in
R^{a,b,k}}d_{u}^{a,b}\leq\|J^{a,b}\|_{1}$, we pick precision parameters
$\Delta^{a,b}$ and ranges for each color $a,b$:

$I^{a,b}=\bigg{\\{}-\Delta^{a,b}\big{(}\lfloor\frac{\|J^{a,b}\|_{1}}{\Delta^{a,b}}\rfloor+1\big{)},-\Delta^{a,b}\lfloor\frac{\|J^{a,b}\|_{1}}{\Delta^{a,b}}\rfloor,\cdots\Delta^{a,b}\big{(}\lfloor\frac{\|J^{a,b}\|_{1}}{\Delta^{a,b}}\rfloor+1\big{)}\bigg{\\}}$

That is, rounding to the nearest multiple of $\Delta^{a,b}$. For each of
$d^{4}\cdot s$ cuts in the cut decomposition, we pick guesses
$\vec{r},\vec{c}=(r^{a,b,k})_{a,b\in[d^{2}],k\in[s]},(c^{a,b,k})_{a,b\in[4],k\in[s]},r^{a,b,k},c^{a,b,k}\in
I^{a,b}$ for the weighted magnetizations of both sides of each cut. For each
$\vec{r},\vec{c}$, we define the relaxed constraints $C_{\vec{r},\vec{c}}$
over the description of a product state over $n$ qudits to check whether the
product state has these weighted magnetizations within a $\Delta$ range of the
guess:

$\displaystyle C_{\vec{r},\vec{c}}:\text{Tr}[\rho_{u}]=1,\rho_{u}\geq 0\text{
for all particles }u\in V$ (160) $\displaystyle
r^{a,b,k}-\Delta^{a,b}\leq\sum_{u\in
R^{a,b,k}}d_{u}^{a,b}\cdot\text{Tr}[\sigma_{u}^{a}\rho_{u}]\leq
r^{a,b,k}+\Delta^{a,b}\text{ and }$ (161) $\displaystyle
c^{a,b,k}-\Delta^{a,b}\leq\sum_{u\in
L^{a,b,k}}d_{u}^{a,b}\cdot\text{Tr}[\sigma_{u}^{b}\rho_{u}]\leq
c^{a,b,k}+\Delta^{a,b}\text{ for all }a,b\in[d^{2}],k\in[s]$ (162)

Our algorithm is to enumerate over all the choices of $\vec{r},\vec{c}$, and
for each one, check the feasibility of $C_{\vec{r},\vec{c}}$ via the algorithm
in Theorem 6.2 up to a cutoff radius $r^{\prime}$. Among the pairs
$\vec{r},\vec{c}$ which are feasible, we output as estimate the pair
$\vec{r}^{*},\vec{c}^{*}$ which minimizes the energy estimate
$\sum_{a,b,k}\alpha_{a,b,c}r_{a,b,k}^{*}c_{a,b,k}^{*}$, and we output any
feasible $\rho$ for the choice of $C_{\vec{r}^{*},\vec{c}^{*}}$. Let $\hat{V}$
be said energy estimate.

To prove correctness of this scheme, we need to show that for an appropriate
choice of the precision parameters $\Delta^{a,b}$, the feasible solutions to
$C_{\vec{r},\vec{c}}$ have energy close to the guess
$\sum_{a,b,k}\alpha_{a,b,c}r_{a,b,k}c_{a,b,k}$, and thereby the output energy
is close to the ground state energy.

######  Claim D.2.

Pick $\Delta^{a,b}=\delta\|J^{a,b}\|_{1}$, with
$\delta=O(\epsilon^{3}/t^{3/2})$. If a product state $\rho$ is feasible for
$C_{\vec{r},\vec{c}}$, then

$\bigg{|}\text{Tr}[H\rho]-\sum_{a,b,k}\alpha_{a,b,c}r_{a,b,k}c_{a,b,k}\bigg{|}\leq\epsilon\cdot|J|_{1}$
(163)

###### Proof.

Let $r^{\prime},c^{\prime}$ be the length $d^{4}\cdot s=O(t\epsilon^{-2})$
vectors of the true weighted average magnetizations of $\rho$, then the error
to the energy estimate above satisfies

$\displaystyle\leq\bigg{|}\text{Tr}[H\rho]-\sum_{a,b,k}\alpha_{a,b,c}r^{\prime}_{a,b,k}c^{\prime}_{a,b,k}\bigg{|}+\sum_{a,b,k}|\alpha_{a,b,c}|\cdot\bigg{|}r^{\prime}_{a,b,k}c^{\prime}_{a,b,k}-r_{a,b,k}c_{a,b,k}\bigg{|}\leq$
(164)
$\displaystyle\leq\epsilon\cdot|J|_{1}+s\cdot\sum_{a,b}\max_{k}|\alpha_{a,b,k}|\cdot(2\Delta^{a,b}\|J^{a,b}\|_{1}+(\Delta^{a,b})^{2})\leq$
(165) $\displaystyle\leq\epsilon\cdot|J|_{1}+3\sqrt{t}\cdot
s\sum_{a,b}\Delta^{a,b}=\epsilon\cdot|J|_{1}+O(t^{3/2}\epsilon^{-2}\cdot\delta|J|_{1})$
(166)

where we used Claim D.1 and the properties of the decomposition in Theorem
D.1. We conclude this claim by picking $\delta=O(\epsilon^{3}t^{-3/2})$ and
appropriately rescaling $\epsilon$. ∎

To show we can find these feasible points efficiently, if they exist, we need
to argue that the convex set of feasible points to $C_{\vec{r},\vec{c}}$
contains a small ball of radius $r^{\prime}$. This once again follows from the
fact that the ranges $I^{a,b}$ are overlapping: that is, for every product
state $\rho$, there exists a choice of $\vec{r},\vec{c}$ s.t. $\rho$ is
feasible and bounded $\min_{a,b}\Delta^{a,b}/2$ away from saturating any of
the magnetization constraints. It is an easy corollary of the proof techniques
in section B that $C_{\vec{r},\vec{c}}$ thereby contains a ball of radius
$r^{\prime}=O(\min_{a,b}\frac{\Delta^{a,b}}{|J^{a,b}|_{1}})=O(\epsilon^{3}/t^{3/2})$,
under the conditions on $\Delta^{a,b}$ in the claim above.

######  Corollary D.1.

$\hat{V}$ is an $\epsilon\cdot|J|_{1}+O(n^{1/3}|J|_{1}^{1/3}\|J\|_{F}^{2/3})$
additive error estimate to the ground state energy
$\min_{\rho}\text{Tr}[H\rho]$.

###### Proof.

Since every product state feasible for some $C_{r,c}$ has energy close to its
estimate, and since every product state is feasible for some $C_{r,c}$ for
some choice of $r,c$, we have $|\hat{V}-\min_{\text{product state
}\rho}\text{Tr}[H\rho]|\leq\epsilon|J|_{1}$. To conclude, we use the
assymetric product state approximations in Theorem 4.1 to relate
$\min_{\rho=\otimes\rho_{u}}\text{Tr}[H\rho]$ and
$\min_{\rho}\text{Tr}[H\rho]$.

∎

We summarize this result in the following theorem:

######  Theorem D.2.

Fix $d=O(1),\epsilon>0$. Let $H=\sum_{u,v}H_{u,v}$ be a 2-Local Hamiltonian
defined on $n$ qudits of local dimension $d$, with Pauli interaction graphs
$J^{a,b}$ of maximum threshold rank
$t\equiv\max_{a,b\in[d^{2}]}t_{O(\epsilon)}(J^{a,b}_{D})$, and matrix of
interaction strengths $J=\\{\|H_{uv}\|_{\infty}\\}_{u,v\in[n]}$. Then, there
exists an algorithm which finds an
$\epsilon|J|_{1}+O(n^{1/3}|J|_{1}^{1/3}\|J\|_{F}^{2/3})$ approximation to the
ground state energy of $H$ in time poly$(n)\cdot
2^{\tilde{O}(t/\epsilon^{2})}$.

###### Proof.

It remains to reason on the runtime of the algorithm. We compute the
decomposition using Theorem D.1 in time poly$(n,1/\epsilon,t)$. For fixed
$\vec{r},\vec{c}$, we can check the feasibility of $C_{\vec{r},\vec{c}}$ in
time poly$(n,1/\epsilon,t)$ using Theorem 6.2, given that the number of
variables is $O(n)$, the number of constraints is poly$(1/\epsilon,t)$, and
the guarantees on the volume of the feasible regions is $\log R/r=O(\log
n+\log 1/\epsilon+\log t)$. To conclude, the number of such programs is

$\leq\prod_{a,b\in[d^{2}],k\in[s]}\bigg{(}2\frac{\|J^{a,b}\|_{1}}{\Delta^{a,b}}+3\bigg{)}\leq
2^{O(t/\epsilon^{2}\log 1/\delta)}=2^{\tilde{O}(t/\epsilon^{2})}$ (167)

where $\tilde{O}$ hides factors of poly$\log 1/\epsilon$, poly$\log t$ and we
use the definition of $\Delta^{a,b}$ in claim D.2. ∎

For certain restrited classes of low threshold rank Hamiltonians, we are able
to reduce this runtime to
poly$(n,1/\epsilon,t)+2^{\tilde{O}(t/\epsilon^{2})}$. To do so, we would
essentially like to exploit the same common refinement technique discussed in
the dense case in section 6, where we replace the density matrices $\rho_{u}$
within each partition by a single ‘averaged’ density matrix $\rho_{P}$ for
every $u\in P\subset[n]$. That is, in the dense case, given any product state
$\rho$ which is feasible for some $C_{\vec{r},\vec{c}}$, we argued that
averaging over the partitions $\rho_{P}=\sum_{u\in P}\rho_{u}/|P|$ defines an
$n$ qubit product state which is still feasible for $C_{\vec{r},\vec{c}}$.
Unfortunately, this no longer holds in the low threshold rank case, since
different colors $a,b$ may attribute different degrees $d^{a,b}_{u}$ to $u$,
and thereby there is no guarantee that any average over the components in each
partition $P$ preserves the feasibility of the magnetization constraints.

However, when the degrees $d^{a,b}_{u}$ are color-independent, i.e. either
$d^{a,b}_{u}=d_{u}$ for all $u\in V$ or $d^{a,b}_{u}=0$ for all $u\in V$, then
a certain convex combination of the density matrices in each partition
achieves our goal. Quantitatively, an example of this condition is the Quantum
Max-Cut Hamiltonian, where each $X_{u}\otimes X_{v}$ interaction is
accompanied by a $Y_{u}\otimes Y_{v}$ of the same weight, but the generic
Quantum Heisenberg model is not. By weighting the convex combination by the
degrees,

$\rho_{P}=\sum_{u\in P}\frac{d_{u}}{\sum_{u\in
P}d_{u}}\rho_{u}\Rightarrow\sum_{u\in
P}d_{u}\text{Tr}[\sigma^{a}\rho_{P}]=\sum_{u\in
P}d_{u}\text{Tr}[\sigma^{a}\rho_{u}]$ (168)

$\rho_{P}$ has trace 1 and is PSD, and preserves the weighted magnetizations
of the subset $P$ for every choice of basis $a\in[4]$. In this setting, we can
define a ‘compressed’ set of constraints $\tilde{C}_{\vec{r},\vec{c}}$, where
the variables are $2^{O(s)}=2^{O(t/\epsilon^{2})}$ PSD matrices $\rho_{P}$,
one for each subset $P$ in the common refinement. For notional convenience, we
denote as $d^{a,b}(P)=\sum_{u\in P}d^{a,b}_{u}$.

$\displaystyle\tilde{C}_{\vec{r},\vec{c}}:\text{Tr}[\rho_{P}]=1,\rho_{P}\geq
0\text{ for all particles }u\in V$ (169) $\displaystyle
r^{a,b,k}-\Delta^{a,b}\leq\sum_{P:P\subset
R^{a,b,k}}d^{a,b}(P)\cdot\text{Tr}[\sigma^{a}\rho_{P}]\leq
r^{a,b,k}+\Delta^{a,b}\text{ and }$ (170) $\displaystyle
c^{a,b,k}-\Delta^{a,b}\leq\sum_{P:P\subset
L^{a,b,k}}d^{a,b}(P)\cdot\text{Tr}[\sigma_{u}^{b}\rho_{P}]\leq
c^{a,b,k}+\Delta^{a,b}\text{ for all }a,b\in[4],k\in[s]$ (171)

######  Theorem D.3.

Let $H=\sum_{(u,v)}H_{u,v}$ be a instance of the Quantum Max Cut Hamiltonian,
with $n\times n$ edge weight matrix $J$ of threshold rank
$t=t_{O(\epsilon)}(J_{D})$. Then there exists an algorithm which finds a
$\epsilon|J|_{1}+O(n^{1/3}|J|_{1}^{1/3}\|J\|_{F}^{2/3})$ additive error
approximation to the Quantum Max Cut $\max_{\rho}\text{Tr}[H\rho]$ in time
$\text{poly}(n,t,1/\epsilon)+2^{\tilde{O}(t/\epsilon^{2})}$.

###### Proof.

Crucially, as previously discussed $C_{\vec{r},\vec{c}}$ is feasible $\iff$
$\tilde{C}_{\vec{r},\vec{c}}$ is feasible. Moreover, every set of
$2^{O(t/\epsilon^{2})}$ single qubit density matrices on the partitions
$\rho_{P}$ is feasible for at least one choice of $\vec{r},\vec{c}$, and
bounded away from saturating the magnetization constraints, and thereby via
section B we know that the feasible region of $\tilde{C}_{\vec{r},\vec{c}}$
contains a ball of radius $r^{\prime}=O(\delta)=O(\epsilon^{3}/t^{3/2})$.
Thus, we can check the feasibility of all the $\tilde{C}_{\vec{r},\vec{c}}$ in
time $2^{\tilde{O}(t/\epsilon^{2})}$. ∎

##  Appendix E A Free Energy PTAS on Dense Graphs

To extend the regularity lemma and its applications to the context of the free
energy, we revisit the ground state energy approximation scheme devised in
section 6, with a point of view based on the results by [JKM18a]. Recall how
we estimated the minimum energy of $H$ among product states by reducing the
computation to checking the feasibility of a small number of convex
constraints. [JKM18a] showed that for Ising models, it is the maximum entropy
program subject to these regularity-based constraints that enables an estimate
for the true free energy. By combining our product state approximations for
the free energy with our Hamiltonian regularity statements, we are able to
draw quantum generalizations of their results on Local Hamiltonians.

As we later discuss, since the free energy itself is a maximum entropy program
regularized by the temperature, our algorithms often incur a tradeoff between
combinatorial, regularity-based errors, and thermal errors incurred from noise
in our sampling algorithms. In this fashion we devise two main algorithms, the
first of which is a sublinear time, additive error approximation algorithm
which provides accurate approximations in a low temperature regime:

######  Theorem E.1.

Fix $k,d=O(1)$, and $\epsilon,\delta>\omega(n^{-1/(2k-2)})$ and an inverse
temperature $\beta>0$, and let $H$ be a $k$-Local Hamiltonian on $n$ qudits of
local dimension $d$ and $m$ bounded strength interactions. Then, there exists
an algorithm that runs in time $2^{\tilde{O}(\epsilon^{2-2k})}\cdot
O(\delta^{-2})$, that returns an estimate to the free energy accurate up to an
additive error of $\epsilon n^{k/2}m^{1/2}+\delta n/\beta$ and is correct with
probability $.99$.

In effect, the thermal error above arises since we only have imperfect
knowledge of the cut decomposition, and the sizes of the partitions within
each cut. In the low temperature regime, whenever
$\beta=\Omega(n^{1-k/2}m^{-1/2})$, this first algorithm ensures a $\epsilon
n^{k/2}m^{1/2}$ approximation in $2^{\tilde{O}(\epsilon^{2-2k})}$ time, much
like the sublinear time approximation algorithm for the ground state energy.
Our second approach explicitly computes the cut decomposition, significantly
improving the thermal error dependence at higher temperatures, at the cost of
a higher runtime:

######  Theorem E.2.

Fix $k,d=O(1)$, and $\epsilon,\delta>\omega(n^{-1/2)})$ and an inverse
temperature $\beta>0$, and let $H$ be a $k$-Local Hamiltonian on $n$ qudits of
local dimension $d$ and $m$ bounded strength interactions. Then, there exists
an algorithm that runs in time
$2^{\tilde{O}(\epsilon^{-2})}\cdot\tilde{O}(n^{k}\log 1/\delta)$, that returns
an estimate to the free energy accurate up to an additive error of $\epsilon
n^{k/2}m^{1/2}+\delta n/\beta$ and is correct with probability $.99$.

###  E.1 Finding the best Product State Approximation

In the setting of the section 6 and appendix C, given a $k$-Local Hamiltonian
$H$ on $n$ qudits of local dimension $d$ and $m$ bounded strength
interactions, let $J=\\{\|H_{e}\|_{\infty}\\}_{e\in[n]^{k}}$ be its $k$
dimensional array of interaction strengths, and let $H_{D}$ be its cut
decomposition following theorems C.1 and C.1 with width
$s=O(\epsilon^{2-2k})$. While we phrase most of the discussion in this section
with the cut decomposition in Theorem C.1 by [FK99], the analysis under the
cut decomposition in Theorem C.2 by [AdlVKK02] follows analogously. To
proceed, fix a precision parameter $\gamma$ and for every ‘guess’ vector $r$
of size $k\cdot d^{2k}\cdot s$ with $r_{i}\in I_{\gamma}\subset[-n,n]$ for the
average magnetization of each of $k$ sides of the $d^{2k}\cdot s$ cuts in the
cut decomposition of $H$, we can formulate the convex program $O_{r,\gamma}$
to be the maximum entropy program over the subset magnetization constraints
$C_{r,\gamma}$

$O_{r,\gamma}=\max_{\alpha\in\mathbb{R}^{(d^{2-1})n}}\sum_{u\in
V}S(\rho^{\alpha_{u}})\text{ subject to }C_{r,\gamma}$ (172)

In this manner, we express the problem of finding the product state of
approximately minimum free energy as the minimum over the optima of
$2^{O(k\cdot d^{2k}\cdot s\log 1/\gamma)}$ convex programs.

$F_{\gamma}=\min_{r:C_{r,\gamma}\text{feasible}}F_{r,\gamma}=\min_{r:C_{r,\gamma}\text{feasible}}\bigg{(}\sum_{i\in[d^{2k}\cdot
s]}d^{i}\prod_{j}^{k}r^{i}_{j}-O_{r,\gamma}/\beta\bigg{)}$ (173)

To speedup the optimization, we replace the convex constraints by the induced
constraints $\tilde{C}_{r,\gamma}$ on the common refinement of the partitions
in the cut decomposition. If $\mathcal{A}_{a}\subset[n]$, $a\in[A]$ is the
coarsest partition of $H_{D}$, then $A\leq 2^{k\cdot d^{2k}\cdot s}$. We
appropriately re-scale the objective to define the program
$\tilde{O}_{r,\gamma}$:

$\displaystyle\tilde{O}_{r,\gamma}=\max_{\alpha\in\mathbb{R}^{(d^{2}-1)\cdot
A}}\sum_{a\in[A]}|\mathcal{A}_{a}|S(\rho^{\alpha_{a}})\text{ subject to
}\tilde{C}_{r,\gamma},$ (174) $\displaystyle\text{ and return
}\min_{r:\tilde{C}_{r,\gamma}\text{feasible}}\bigg{(}\sum_{i\in[d^{2k}\cdot
s]}d^{i}\prod_{j}^{k}r^{i}_{j}-\tilde{O}_{r,\gamma}/\beta\bigg{)}$ (175)

Recall that Claim 6.1 tells us that $C_{r,\gamma}$ is feasible
$\iff\tilde{C}_{r,\gamma}$ is feasible, and thereby the convexity of the
entropy ensures that $O_{r,\gamma}=\tilde{O}_{r,\gamma}$. Once again, since
our goal is a sublinear time algorithm, we only have imperfect knowledge of
the sizes $|\mathcal{A}_{a}|$ of the common refinements. However, we can
construct estimates $|\hat{\mathcal{A}}_{a}|$ accurate up to some additive
error efficiently, following Claim 6.3, and instantiate programs
$\hat{O}_{r,\gamma}$ with ‘noisy’ constraints $\hat{C}_{r,\gamma}$. We solve
each of the convex programs using a result of [BV02], an analog of Theorem 6.2
for optimization which we present at the end of this section.

Let us begin by reasoning on the correctness of this algorithm. First, we
argue that the noise-less, compressed programs $\tilde{O}_{r,\gamma}$ provides
a good approximation to the optimum product state assignment to the free
energy of $H_{D}$. So long as the noise on $|\hat{\mathcal{A}}_{a}|$ isn’t too
large, next we prove that the optima of the noisy programs
$\hat{O}_{r,\gamma}$ is close to the noise-less case. Finally, our product
state approximations together with the Hamiltonian regularity lemma will
ensure that the true free energy has a good product state approximation, tying
the output of our algorithm to the free energy.

######  Claim E.1.

$\tilde{F}_{O(\epsilon^{k})}$ is an $\epsilon\cdot n^{k/2}\|J\|_{F}$ additive
approximation to
$\min_{\rho=\otimes\rho_{u}}f_{D}(\rho)=\min_{\rho=\otimes\rho_{u}}\text{Tr}[H_{D}\rho]-S(\rho)/\beta$.

###### Proof.

Let $\rho^{*}$ be the product state minimizer of
$f_{D}(\rho)=\text{Tr}[H_{D}\rho]-S(\rho)/\beta$. Correspondingly, let
$r^{*}\in[-n,n]^{k\cdot d^{2k}\cdot s}$ be the subset magnetizations
corresponding to $\rho^{*}$. By construction, there is a guess vector
$r\in(I_{\gamma})^{k\cdot d^{2k}\cdot s}$ s.t. $|r_{j}^{*}-r_{j}|\leq
n\gamma/2$, and thus $\rho^{*}$ is feasible for $C_{r,\gamma}$. Picking
$\gamma=O(\epsilon^{k})$ in Claim C.2 ensures that the energy of $\rho^{*}$ on
$H_{D}$ is close to its estimate. We further observe that by definition,
$O_{r,\gamma}\geq S(\rho^{*})$, since $\rho^{*}$ is feasible for
$C_{r,\gamma}$, and thus:

$\displaystyle
f_{D}(\rho^{*})=\text{Tr}[H_{D}\rho^{*}]-S(\rho^{*})/\beta\geq-\epsilon
n^{k/2}\|J\|_{F}+\sum_{i}d^{i}\prod_{j}^{k}r^{i}_{j}-S(\rho^{*})/\beta\geq$
(176) $\displaystyle\geq-\epsilon
n^{k/2}\|J\|_{F}+\sum_{i}d^{i}\prod_{j}^{k}r^{i}_{j}-O_{r,\gamma}/\beta\geq-\epsilon
n^{k/2}\|J\|_{F}+\min_{r:C_{r,\gamma}\text{ feas
}}\sum_{i}d^{i}\prod_{j}^{k}r^{i}_{j}-O_{r,\gamma}/\beta=$ (177)
$\displaystyle=-\epsilon n^{k/2}\|J\|_{F}+\hat{F}_{\gamma}$ (178)

The lower bound, in turn, requires a definition. Let $\rho^{r,\gamma}$ be the
product state that maximizes the program $O_{r,\gamma}$ if feasible. Then,
Claim C.2 ensures we have $f_{D}(\rho^{r,\gamma})\leq F_{r,\gamma}+\epsilon
n^{k/2}\|J\|_{F}$, if $\gamma=O(\epsilon^{k})$. In turn, let
$\rho_{r^{\prime},\gamma}$ be the product state where $r^{\prime}$ minimizes
$\min_{r}\hat{F}_{r,\gamma}$. That is,
$\hat{F}_{\gamma}=\hat{F}_{r^{\prime},\gamma}$. By the variational description
of the free energy product state optima of $f_{D}$, we obtain the lower bound:

$f_{D}(\rho^{*})\leq f_{D}(\rho_{r^{\prime},\gamma})\leq\epsilon
n^{k/2}\|J\|_{F}+\hat{F}_{r^{\prime},\gamma}=\epsilon
n^{k/2}\|J\|_{F}+\hat{F}_{\gamma}$ (179)

∎

Now that we’ve ensured that the optima $\tilde{F}_{O(\epsilon^{k})}$ of the
noise-less programs is a good approximation to the variational free energy of
$H_{D}$, let us prove that approximating this quantity with the noisy
constraints is still a good approximation.

######  Claim E.2.

Assume we have estimates for the sizes $|\hat{\mathcal{A}}_{a}|,a\in[A]$ of
each partition in the common refinement of the cuts in $H_{D}$, accurate up to
an additive error $\delta/A\cdot n$ with $\delta<\gamma/4$ and
$\gamma=O(\epsilon^{k})$. Then, the estimate $\hat{F}_{O(\epsilon^{k})}$
corresponding to the optima of the noisy programs is an $\epsilon\cdot
n^{k/2}\|J\|_{F}+\frac{\delta\log d}{\beta}\cdot n$ additive error
approximation to the variational free energy of $H_{D}$,
$\min_{\rho=\otimes\rho_{u}}f_{D}(\rho)$.

###### Proof.

By Claim 6.2 (1), there is a choice of $r$ s.t. the optimum product state
$\rho^{*}$ of $f_{D}$ is feasible for $C_{r,\gamma}$, and thus there is a
choice of an $A$ qudit product state $\sigma^{*}$, one qudit for each subset
in the common refinement, which is feasible for both $\tilde{C}_{r,\gamma}$
and $\hat{C}_{r,\gamma}$. We remark we can choose in particular
$\sigma_{a}=|\mathcal{A}_{a}|^{-1}\sum_{u\in\mathcal{A}_{a}}\rho^{*}_{u}$. We
note that $S(\rho^{*})\leq\sum_{a\in A}|\mathcal{A}_{a}|\cdot
S(\sigma^{*}_{a})$ by subadditivity and convexity of the entropy, and thus
$S(\rho^{*})\leq\sum_{a\in A}|\hat{\mathcal{A}}_{a}|\cdot
S(\sigma^{*}_{a})+\delta\cdot n\cdot\log d$ by assumption. However,
$\sigma^{*}$ is feasible for $\hat{C}_{r,\gamma}$, and thus $\sum_{a\in
A}|\hat{\mathcal{A}}_{a}|\cdot S(\sigma^{*}_{a})\leq\hat{O}_{r,\gamma}$. In
this manner, once again picking $\gamma=O(\epsilon^{k})$ gives

$f_{D}(\rho^{*})+\epsilon\cdot n^{k/2}\|J\|_{F}+\delta/\beta\cdot n\cdot\log
d\geq\min_{r:\hat{C}_{r,\gamma}\text{ feas
}}\sum_{i}d^{i}\prod_{j}^{k}r^{i}_{j}-\hat{O}_{r,\gamma}/\beta=\hat{F}_{O(\epsilon^{k})}$
(180)

Conversely, if $r$ is the vector that extremizes $\hat{F}_{\gamma}$, and if
$\sigma^{r,\gamma}$ is an $A$-qudit product of density matrices which
optimizes $\hat{O}_{r,\gamma}$, let us consider $\rho$ to be the $n$ qubit
density matrix given by copying the assignment of each subset in the common
refinement to every vertex within it: $\rho_{u}=\sigma^{r,\gamma}_{a}$ for
$a\in\mathcal{A}_{a}$, $a\in[A]$. We note $\hat{O}_{r,\gamma}\leq
S(\rho)+\delta\log d\cdot n$, and by Claim C.2,

$\displaystyle f_{D}(\rho^{*})\leq f_{D}(\rho)\leq\epsilon\cdot
n^{k/2}\|J\|_{F}+\sum_{i}d^{i}\prod_{j}^{k}r^{i}_{j}-S(\rho)/\beta\leq$ (181)
$\displaystyle\leq\sum_{i}d^{i}\prod_{j}^{k}r^{i}_{j}-\hat{O}_{r,\gamma}/\beta+\epsilon\cdot
n^{k/2}\|J\|_{F}+\frac{\delta\log d}{\beta}\cdot n$ (182)

∎

We emphasize that this noisy estimate $\hat{F}_{O(\epsilon^{k})}$ incurs a
thermal error to the estimate of the free energy, since we use the noisy
estimates for the sizes of the partitions to compute the entropy of the $n$
qubit system. In the low temperature regime
$\beta=\Omega(1/n^{k/2-1}\cdot\|J\|_{F})$, we can essentially ignore this
thermal error, however in the high temperature regime this regularization
starts taking effect. We return to this discussion shortly. By combining these
results with our product state approximations for the free energy, we prove
that these estimates in fact approximate the free energy of $H$.

######  Corollary E.1.

$\tilde{F}_{O(\epsilon^{k})}$ is an $2\epsilon\cdot n^{k/2}\|J\|_{F}$ additive
error estimate to $F=\min_{\rho\geq 0}f(\rho)$, and
$\hat{F}_{O(\epsilon^{k})}$ is an $2\epsilon\cdot
n^{k/2}\|J\|_{F}+\frac{\delta\log d}{\beta}\cdot n$ additive error estimate to
$F$.

###### Proof.

We note
$\big{|}\min_{\rho:\rho=\otimes\rho_{u}}f_{D}(\rho)-\min_{\rho:\rho=\otimes\rho_{u}}f(\rho)\big{|}\leq\max_{\rho:\rho=\otimes\rho_{u}}\big{|}\text{Tr}[(H-H_{D})\rho]\big{|}\leq\epsilon
n^{k/2}\|J\|_{F}$, and thus the variational free energies of $H,H_{D}$ are
close. Moreover, by Theorem 4.4 the free energy has a product state
approximation $\big{|}\min_{\rho:\rho=\otimes\rho_{u}}f(\rho)-\min_{\rho\geq
0}f(\rho)\big{|}\leq
O(n^{\frac{k-1}{3}}|J|_{1}^{1/3}\|J\|_{F}^{2/3})=O(n^{k/2-1/3}\|J\|_{F})$. ∎

It suffices now only to argue the runtime of the algorithm to conclude the
proof of our approximation algorithm to the free energy. We use the following
result by [BV02]:

######  Theorem E.3 ([BV02]).

Suppose $K\subset\mathbb{R}^{m}$ is a convex set, and $R,r\in\mathbb{R}$ and
$y\in K$ are such that: $K$ is contained in the ball of radius $R$ centered at
the origin, and, if $K$ is non-empty, $K$ contains the ball of radius $r$
centered at $y$. Assume $K$ has a separation oracle which is efficiently
computable in time $T$. Further suppose $g:\mathbb{R}^{m}\rightarrow[-1,1]$ is
a convex function, which is efficiently computable and differentiable at any
point $\gamma\in K$ in time $T^{\prime}$. Then, with probability
$1-2^{-\Omega(m)}$ we can compute a feasible point $x^{\prime}\in K$ which is
approximately minimal,

$|g(x^{\prime})-\min_{x\in K}g(x)|\leq\epsilon$ (183)

in time $\text{poly}(m,T,T^{\prime})\cdot O(\log R/r\cdot\log 1/\epsilon)$.

We are now in a position to prove theorems E.1 and E.2:

###### Proof.

[of Theorem E.1]

We note as in sections 6 and C that the convex sets
$\tilde{C}_{r,O(\epsilon^{k})}$ and $\hat{C}_{r,O(\epsilon^{k})}$ have
$m=A=2^{O(\epsilon^{2-2k})}$,
$R=\text{poly}(d,A)=2^{O(\epsilon^{2-2k})},r=O(\epsilon^{k})$, as well as
$T,T^{\prime}=\text{poly}(d,A)=2^{O(\epsilon^{2-2k})}$.

We implicitly compute the cut decomposition $H_{D}$ of Theorem C.1, and
estimate the sizes of the coarsest partitions of the cuts using Claim 6.3, for
an appropriate choice of $\delta<\frac{\gamma}{4\log d}$. Then, we instantiate
all the $2^{\tilde{O}(\epsilon^{2-2k})}$ maximum entropy programs subject to
the noisy constraints $\hat{C}_{r,O(\epsilon^{k})}$, and solve them all up to
an additive error $\delta\cdot n$ in time $2^{\tilde{O}(\epsilon^{2-2k})}\cdot
O(\log 1/\delta)$. Overall, with probability $.99$, this achieves an estimate
for the true free energy accurate up to additive error $2\epsilon
n^{k/2}\|J\|_{F}+2\cdot\delta\cdot n/\beta$, and runs in time
$2^{\tilde{O}(\epsilon^{2-2k})}\cdot O(\delta^{-2})$ in the probe model of
computation. In the low temperature regime, whenever
$\beta=\Omega(n^{1-k/2}\|J\|_{F}^{-1})$, this provides an $\epsilon
n^{k/2}\|J\|_{F}$ approximation in time $2^{\tilde{O}(\epsilon^{2-2k})}$.

∎

###### Proof.

[of Theorem E.2]

Alternatively, in the explicit approach, we explicitly compute the cut
decomposition $H_{D}$ using Theorem C.2, and and explicitly compute the
coarsest partition of the cuts in time $O(n^{k})\cdot
2^{\tilde{O}(1/\epsilon^{2})}$. Recall that the array cut decomposition by
[AdlVKK02] has width $O(1/\epsilon^{2})$, and that we can use Claim C.2 to
ensure the analogous accuracy guarantees to the free energy if we pick
$\gamma=O(\epsilon^{2})$.

Under Theorem C.2, we note the convex set $\tilde{C}_{r,O(\epsilon^{k})}$ has
$m=A=2^{O(\epsilon^{-2})}$,
$R=\text{poly}(d,A)=2^{O(\epsilon^{-2})},r=O(\epsilon^{2})$, as well as
$T,T^{\prime}=\text{poly}(d,A)=2^{O(\epsilon^{-2})}$. We can then instantiate
all the $2^{\tilde{O}(\epsilon^{2})}$ maximum entropy programs subject to the
noise-less constraints $\tilde{C}_{r,O(\epsilon^{2})}$, and solve them up to
an additive error $\delta\cdot n$ in time $2^{\tilde{O}(\epsilon^{-2})}\cdot
O(\log 1/\delta)$. If we pick $\delta=\epsilon\min(\beta
n^{k/2-1}\|J\|_{F},1)$, then overall this achieves an estimate for the true
free energy up to additive error $\epsilon n^{k/2}\|J\|_{F}+\delta
n/\beta\leq\epsilon n^{k/2}\|J\|_{F}\leq 2\epsilon n^{k/2}\|J\|_{F}$ in time
$O(n^{k})\cdot 2^{\tilde{O}(\epsilon^{-2})}+2^{\tilde{O}(\epsilon^{-2})}\cdot
O(\log\frac{1}{\epsilon\beta n^{k/2-1}\|J\|_{F}})$. ∎

##  Appendix F A Ground State Energy PTAS on Sparse Graph Classes

In this section, let us turn to the converse limit of Local Hamiltonians
studied until now: those on sparse graphs. Our intention is to construct
approximation schemes for the ground state energy and the free energy on
certain restricted classes of sparse graphs, namely, graphs excluding a fixed
minor, where their structure enables us to construct efficient divide-and-
conquer and dynamic programming algorithms. We follow the ideas of [BBT09] and
[BH13] on planar graphs, improving their results by using ideas from the
algorithmic graph minor theory of [DHiK05] and an improved quantum-to-
classical mapping over the high degree vertices in the graph. In the next
section, we extend these techniques to approximating the free energy as well.
In particular, the main result of this section is the following theorem:

######  Theorem F.1.

Let $H=\sum_{e\in E}H_{e}$ be a 2-Local Hamiltonian defined on $n$ qubits,
configured on an $h$-minor free graph $G=(V,E)$ where $|h|=O(1)$. Let the
maximum interaction strength be $\max_{e}\|H_{e}\|_{\infty}=1$, let the number
of interactions be $m=|E|$, and let $\epsilon>0$. Then there exists a
clustered product state $\sigma$ that approximates the ground state energy of
$H$ up to error

$\text{Tr}[H\sigma]\leq\min_{\rho}\text{Tr}[H\rho]+\epsilon m.$ (184)

Moreover, $\sigma$ can be found in $\text{poly}(n)+n\cdot
2^{O(\epsilon^{-9}\log 1/\epsilon)}$ time.

We organize the rest of this section as follows. In subsection F.1, we
overview our approach and highlight our improvements to the quantum-to-
classical mappings in previous work. In subsection F.2, we summarize and prove
the combinatorial properties of $h$-minor free graphs that we need in our
algorithms. In subsection F.3, we restrict our attention to the easier bounded
degree $h$-minor free graphs, and develop an algorithm which efficiently
approximates their ground state energy based almost exclusively on our
combinatorial decomposition theorems. Finally, in subsection F.4, we combine
our bounded degree approach with the high-low degree techniques by [BH13] to
develop a novel dynamic programming algorithm culminating in Theorem F.1.

###  F.1 Overview

In this subsection, we briefly present a high level description of the
approach and our main contributions to approximation schemes on Quantum
2-Local Hamiltonians defined on graphs that exclude a fixed minor. There is a
rich literature of approximation algorithms to NP Hard problems on $h$ minor
free graphs, which we extensively draw from in our paper. This is since these
graphs quite generically have many interesting structural properties, which
can be exploited to construct algorithms. One such property is the concept of
a vertex separator. In a seminal work, [LT77] introduced the notion of a
planar separator, a small set of vertices in a planar graph that once removed,
divides the graph into roughly balanced disconnected components. This idea
essentially enabled a divide and conquer approach to optimization problems on
planar graphs, in which the (disconnected) components are optimized
independently. A number of further studies significantly generalized the
concept beyond the planar graph setting [GHT84, AST90, KPR93, iKR10, NdMW12,
DN16].

Another interesting graph-theoretic concept we draw from is that of the tree-
width and the tree decomposition. While we defer most technical details to
later in this work, the tree-width is an integer parameter that quantifies how
far a graph is from a tree. The concept was originally developed by [RS86a],
and has been widely influencial in developing parametrized algorithms (often
via dynamic programming) for problems that become simpler on graphs of low
tree-width. For a review of equivalent definitions, algorithms, and
applications, refer to [Bod93]. Most relevant to our paper is ‘Baker’s
technique’ [Bak94], an algorithmic technique to approximate many NP Hard
problems on planar graphs. The technique is essentially based on another
decomposition theorem, that partitions planar graphs into disconnected
components of small tree-width, which can be optimized independently. Later, a
beautiful line of work [DH04b, DH04a, DH05, DHiK05, DHiK09, DHiK11] developed
an algorithmic graph minor theory, which generalized Baker’s technique and
defined many other decompositions for $h$ minor free graphs.

[BBT09] were the first to bring these ideas into the context of approximating
QMA-hard problems. At a high-level, their algorithm for the minimum energy of
quantum hamiltonians on planar graphs of bounded degree was to use a edge
separator construction by [KPR93], which removed a small number of edges (or
interactions) from $H$ such that the sub-Hamiltonian $H^{\prime}$ that remains
is disconnected, and organized into connected components of small size. These
clusters could then be optimized independently by exact diagonalization. They
used Weyl’s inequality to formalize the error to the ground state energy that
incurred by computing that of $H^{\prime}$:

$\big{|}\lambda_{\min}(H)-\lambda_{\min}(H^{\prime})\big{|}\leq\|H-H^{\prime}\|_{\infty}\leq
O(\text{Edge Weight Removed})$ (185)

Naturally, neither the existence of such a choice of a small number edges, nor
algorithms to find them, are guaranteed for generic graphs. However, graphs
that exclude a fixed minor are among the most general classes of graphs that
these techniques are applicable to. Without yet entering into too many details
of the decomposition, the key intuition we need is that graphs that exclude a
fixed minor of bounded degree, have efficient edge separators. The bounded
degree constraint here is crucial, as the star graph (which is a planar graph)
would immediately arise as a worst case to the decomposition techniques.

[BH13] bypassed this bounded degree constraint, by directly arguing about the
structure of the quantum ground states of graphs that have high degree
vertices. They used information-theoretic ideas to argue that the two-particle
reduced density matrices of high degree vertices with their neighbors are, on
average, close to a product state. Quantitatively, they ‘condition’ on all the
particles of degree larger than poly$(1/\epsilon)$ in the graph being a
product state, and prove such a state exists with energy only $\epsilon\cdot
m$ above the ground state. By considering the original graph, with the high
degree vertices removed, they then applied the decomposition techniques of
[BBT09] to the bounded degree vertices in the graph. This information-
theoretic ‘high-low degree’ technique allowed them to discretize the Hilbert
spaces of high degree vertices, and clusters of $2^{\tilde{O}(\epsilon^{-1})}$
low degree vertices, into $\epsilon$-nets, and therefore treat them as
classical particles of spin dimension $2^{2^{\tilde{O}(\epsilon^{-1})}}$ on a
2-Local classical Hamiltonian.

In our work, we build on the graph decomposition techniques of [BBT09], and
the high-low degree techniques of [BH13]. In subsection F.2, we begin by
refining this ‘cluster decomposition’ using a generalized version of Baker’s
technique [DHiK05], and a recursive vertex separator theorem based on the tree
decomposition for graphs of bounded edge weights. These graph-theoretic ideas
allow us to improve on the size of the low degree clusters in the
decomposition to poly$(1/\epsilon)$ vertices, which already enables us in
subsection F.3 to present simpler and faster divide-and-conquer algorithms for
approximating ground state and free energies of $h$ minor free graphs of
bounded degree. The key idea to further compress the classical representation
is the observation that if the clusters of low degree vertices have bounded
size poly$(1/\epsilon)$, and if they all have bounded degree
poly$(1/\epsilon)$, then the neighborhood of each cluster has at most
poly$(1/\epsilon)$ high degree vertices. In this manner, the low degree
clusters act as effective, poly$(1/\epsilon)$-local interactions between the
high degree vertices. This observation hinges on the fact that once you
condition on the all product states of the high degree neighbors of a given
cluster (by choosing them from a $\epsilon$-net), the minimum energy (possibly
entangled) state of that cluster is well defined by the hamiltonian terms
acting on it. This results in the construction of an effective classical
hamiltonian defined on the $O(n)$ high degree vertices, of locality
poly$(1/\epsilon)$ and local dimension poly$(1/\epsilon)$. That is,
essentially a classical $k$-CSP with $k=$ poly$(1/\epsilon)$. To actually
solve this optimization problem, we heavily exploit properties of the tree
decomposition that the graph is defined over, and formalize a dynamic
programming algorithm in the known tree decomposition framework which we refer
to as ‘high degree dynamic programming’.

###  F.2 Preliminaries: Graph Minor theory

In this section, we discuss some ideas from Graph Minor theory, later used to
construct approximations to the ground state energy. Let us begin by
presenting the definition of the tree-width of a graph by [RS86a] and some of
its properties. For a review on the subject, refer to [Bod93].

######  Definition F.1 ([RS86a]).

A tree decomposition of $G=(V,E)$ is a family of subsets $(X_{i}:i\in I)$ of
$V$, arranged on a tree $T$ with vertices $I$, with the following properties:

  1. 1.

Every vertex is covered by a ‘bag’, i.e. $\cup_{i}X_{i}=V$.

  2. 2.

Every edge is contained in a ‘bag’, i.e. $u,v\in X_{i}$ for some $i$, for
every $e=(u,v)\in E$.

  3. 3.

Given three bags $i,j,k\in I$, if $j$ lies on the path in $T$ from $i$ to $k$,
then $X_{i}\cap X_{k}\subset X_{j}$.

By inspection of the properties above, one easily deduces

######  Lemma F.1 ([Bod93]).

The tree-width is non-increasing under vertex and edge deletions, and edge
contractions.

We additionally use the non-trivial property

######  Lemma F.2 ([Bod93]).

Given a tree decomposition $T$ of a graph $G$ of tree-width $t$, one can
construct a tree decomposition $T^{\prime}$ which is a binary tree, of same
tree-width, where the size of $T^{\prime}=O(n)$.

While finding the exact tree-width of a graph is NP-Complete, for fixed small
tree-width an algorithm by [BDD+16] finds a constant multiplicative
approximation in polynomial time:

######  Lemma F.3 ([BDD+16]).

Given a graph of tree-width $t$, one can find a tree-decomposition of width
$O(t)$ in time $n\cdot 2^{O(t)}$.

Integral in our constructions will be to use the tree decomposition to cut up
the graph into disconnected regions by deleting edges. A formalization of this
notion is the concept of a graph separator, originally proposed by [LT77] for
planar graphs. We use a result of [RS86b] to extract separators from the tree-
decomposition:

######  Lemma F.4 ([RS86b], Vertex Separators).

Any graph $G=(V,E)$ of tree-width $t$ has a vertex separator of size $O(t)$.
That is, there is a set $X$ of vertices s.t. removing them defines a partition
into at least 2 components that do not have an edge between them, and are of
size $\leq|V|/2+1$. Moreover, given a tree decomposition, one can find said
separator in time $O(n^{2})$.

To leverage this result to construct approximation algorithms, we use a simple
recursive application of the result above.

######  Lemma F.5 (Recursive Vertex Separators).

Let $G=(V,E)$ be a graph of tree-width $t$. Then it can be separated into
mutually disconnected components each of size $\leq r$, by the removal of
$O(tn/r)$ vertices. Given a tree decomposition of width $O(t)$, said separator
decomposition can be constructed in $O(n^{2})$ time.

To extend the previous work on approximation schemes for local Hamiltonians on
planar graphs ([BBT09]) to H-minor free graphs, we use the following result by
[DHiK05] on the decomposition of said graphs.

######  Theorem F.2 ([DHiK05]).

For a fixed graph $H$ of constant size, there exists a constant $c_{H}$ s.t.
for every $k\geq 1$, and for every $H$-minor free graph $G$, the edges of $G$
can be partitioned into $k+1$ sets s.t. any $k$ of the sets induce a graph of
tree-width at most $c_{H}k$. Furthermore, such a partition can be found in
polynomial time $n^{O(1)}$.

To illustrate its application, as a warm-up, it is instructive to first
discuss the approach of [Bak94] on planar graphs. Consider an arbitrary
starting vertex $s\in V$. Perform breadth-first-search, starting from $s$,
within the planar graph. This procedure defines a sequence of layers,
$L_{1},L_{2},\cdots$, where $L_{i}$ is the set of vertices at distance $i$
from $u$. Fix some integer parameter $t$. Consider the sets of interlacing
layers $S_{i}=L_{i},L_{i+t},L_{i+2t}\cdots$. By construction, removing the set
of vertices $S_{i}$ for some $i$ will partition the graph into sets of
consecutive layers, e.g., $C_{i}=L_{i+1},L_{i+2}\cdots L_{i+t-1}$. More
importantly, if we connect all the nodes in $L_{i+1}$ with a source $v$, then
$C_{i}\cup\\{v\\}$ has diameter $2t$, and since the graph is planar, this
region has tree-width $O(t)$! This relation between diameter and tree-width is
not unique to Planar Graphs. [Epp00] characterized the graphs that have this
‘linear local tree-width’ property to be the set of apex-minor free graphs. In
an incredible development, [DHiK05] showed that analogous properties held for
even more general classes, as we summarize in Theorem F.2 above.

###  F.3 Bounded Degree $h$-Minor Free Graphs

In this section, we discuss how to use the ideas from Bidimensionality theory
to construct approximations to the ground state energy. In particular, we
define a clustered product state, which is a tensor product of density
matrices of clusters of vertices. As a warm-up, it is instructive to consider
a simple divide and conquer algorithm for the bounded degree case. Let
$H=\sum_{e\in E}H_{e}$ be a 2-Local Hamiltonian defined on an $h$-minor free
graph $G=(V,E)$, where each vertex in $V$ has bounded degree $\Delta$. Let
$J=\max_{e}\|H_{e}\|$ be the maximum interaction strength on this graph,
$n=|V|,m=|E|$, and let us assume the minor has constant size $|h|=O(1)$. To
construct an approximation scheme for the ground state energy of $H$, we first
remove selected edges of $H$ in order the simplify the resulting optimization.

Let us first apply Theorem F.2 with $k=O(\epsilon^{-1})$. In this setting, we
can pick a set $RE$ of edges of size $\leq m/(k+1)=O(\epsilon m)$ such that
their removal defines components of tree-width $O(\epsilon^{-1})$ in time
$n^{O(1)}$. Lemma F.3 tells us we can find a decomposition of tree-width
$O(\epsilon^{-1})$ in the resulting graph in time $n\cdot
2^{O(\epsilon^{-1})}$. By now applying the Recursive Vertex Separator Lemma
F.5, we remove a set $RV$ of vertices of size $|RV|=O(n/(r\epsilon))$ such
that the resulting graph $G^{\prime}=(V^{\prime},E^{\prime})$ can be arranged
into at most $O(n)$ mutually disconnected components, each of maximum size
$r$. Since the graph has bounded degree, this corresponds to removing
$\Delta\cdot|RV|=O(\Delta n/r\epsilon)$ edges. Let $H^{\prime}$ be the
Hamiltonian defined simply by keeping the interactions in $G^{\prime}$. Let us
pick $r=O(\Delta/\epsilon^{2})$, such that in total we have removed
$O(\epsilon m)$ edges. Weyl’s inequality tells us that the Hamiltonian
$H^{\prime}$ satisfies

$H^{\prime}=\sum_{e\in E^{\prime}}H_{e},\text{ such that
}\|H-H^{\prime}\|=O(\epsilon mJ)$ (186)

Consider a single component $C\subset V$ of $G^{\prime}$, and recall $C$ has
at most $r$ vertices, and is disconnected from the other components in
$H^{\prime}$. We can find its ground state $\sigma_{C}$ by explicitly
diagonalizing

$\sigma_{C}=\operatorname*{argmin}_{\rho}\text{Tr}\bigg{[}\sum_{e\in
E^{\prime}:e\in C}H_{e}\rho\bigg{]}$ (187)

in time $2^{O(r)}=2^{O(\Delta/\epsilon^{2})}$, as the support of the effective
interaction above is only on $r$ qubits. Repeating for each component, we
conclude with the following theorem.

######  Theorem F.3.

Let $H$ be a 2-Local Hamiltonian defined on $n$ qubits arranged on an
$h$-minor free graph of bounded degree $\Delta$, where the minor is constant
sized $|h|=O(1)$. Fix a constant $\epsilon>n^{-1/2}$. Then there is an
algorithm that finds a clustered product state $\sigma$ in time
$n^{O(1)}+n\cdot 2^{O(\Delta/\epsilon^{2})}$ such that

$\text{Tr}[H\sigma]\leq\text{min}_{\rho}\text{Tr}[H\rho]+\epsilon mJ$ (188)

###### Proof.

As motivated in the previous discussion, one can construct a Hamiltonian
$H^{\prime}$ that approximates the spectra of $H$ via Theorem F.2 and Lemma
F.5 in runtime $n^{O(1)}+n\cdot 2^{O(\epsilon^{-1})}$. We can then optimize
each component individually in total runtime $n\cdot
2^{O(\Delta/\epsilon^{2})}$. We are guaranteed that the resulting state
$\sigma=\otimes_{C}\sigma_{C}$ satisfies

$\displaystyle\text{Tr}[H\sigma]\leq\|H-H^{\prime}\|_{\infty}+\text{Tr}[H^{\prime}\sigma]\leq\|H-H^{\prime}\|_{\infty}+\text{Tr}[H^{\prime}\rho]\leq
2\|H-H^{\prime}\|_{\infty}+\text{Tr}[H\rho]$ (189)
$\displaystyle\Rightarrow\text{Tr}[H\sigma]\leq\text{min}_{\rho}\text{Tr}[H\rho]+O(\epsilon
Jm)$ (190)

by an adequate re-scaling of $\epsilon$ we obtain the desired approximation.

∎

###  F.4 High-Degree Dynamic Programming

To extend the bounded-degree divide and conquer construction in the previous
subsection to $h$-minor free graphs of arbitrary degree, we use the high-low
degree technique of [BH13]. This technique is a slight modification to their
general self-decoupling lemmas, which we briefly present here. Consider a
generic density matrix $\rho$ on $n$ qubits. The goal is to construct a
suitable approximation to $\rho$ via an ensemble of product states over the
high-degree vertices, essentially breaking the entanglement over high-degree
vertices. Similar to as we discussed in section 5, [BH13] pick a random subset
$C$ of vertices to measure in a random Pauli basis $b$, obtaining a string
$z$. Let $\mathcal{H}$ be the set of vertices of degree $\geq\Delta$, and
$\mathcal{L}$ be the set of vertices of degree $\leq\Delta$, for some $\Delta$
to be chosen later. Once measured, the remaining un-measured qubits that have
high-degree in the underlying graph, $\mathcal{H}\setminus C$, are placed in a
tensor product, while the un-measured qubits of low degree,
$\mathcal{L}\setminus C$, are simply unmodified. The resulting state is a
classical distribution of these product states, one for each choice of $C$,
basis measurement $b$, and measurement outcome $z$:

$\sigma=\mathbb{E}_{C,b}\mathbb{E}_{z}\bigotimes_{u\in
C}\psi_{b_{u},z_{u}}\otimes\sigma_{\mathcal{L}\setminus
C}^{(C,b,z)}\bigotimes_{u\in\mathcal{H}\setminus C}\sigma_{u}^{(C,b,z)}$ (191)

######  Remark F.1.

In the interest of shortening notation, we let $\bigotimes_{u\in
C}\psi_{b_{u},z_{u}}=\psi_{C,b,z}$ and
$\eta_{C,b}=\mathbb{E}_{z}\psi_{C,b,z}\otimes\sigma_{\mathcal{L}\setminus
C}^{(C,b,z)}\bigotimes_{u\in\mathcal{H}\setminus C}\sigma_{u}^{(C,b,z)}$. More
importantly, in this section, as $C$ doesn’t play a role we shorten the
description and let
$\sigma=\mathbb{E}_{x}\sigma_{\mathcal{L}}^{(x)}\bigotimes_{u\in\mathcal{H}}\sigma_{u}^{(x)}$

######  Lemma F.6 (High-Low Degree Technique, [BH13]).

Let $H$ be a 2-Local Hamiltonian defined on a graph $G=(V,E)$ of $n$ particles
of local dimension $d=O(1)$, and $|E|=m$. Let $\mathcal{H}$ be the set of
vertices of degree $\geq\Delta$, and $\mathcal{L}$ be the set of vertices of
degree $\leq\Delta$. Let $l$ be a positive integer parameter $<n$, and $C$ be
a random set of vertices of uniformly random size at most $l$. Let $\rho$ be a
generic state defined on these particles $V$. Then there exists a separable
state
$\sigma=\sigma=\mathbb{E}_{x}\sigma_{\mathcal{L}}^{(x)}\bigotimes_{u\in\mathcal{H}}\sigma_{u}^{(x)}$,
that is an ensemble of states that are product over the high degree vertices,
that approximates the energy of $\rho$ as

$\bigg{|}\text{Tr}[H\sigma]-\text{Tr}[H\rho]\bigg{|}=O\bigg{(}\frac{l}{n}+\sqrt{\frac{n}{l\Delta}}\bigg{)}Jm\equiv\delta_{l,\Delta}$
(192)

######  Remark F.2.

If we pick some $l=O(n\Delta^{-1/3})$, we achieve an error of
$\delta_{l,\Delta}=\Delta^{-1/3}Jm$.

######  Corollary F.1.

By an averaging argument, there exists a product state
$\sigma^{(x)}=\sigma_{\mathcal{L}}^{(x)}\bigotimes_{u\in\mathcal{H}}\sigma_{u}^{(x)}$
that approximates the ground state energy of $H$:

$\text{Tr}[H\sigma^{(x)}]\leq\text{min}_{\rho}\text{Tr}[H\rho]+O(\Delta^{-1/3}Jm)$
(193)

The main takeaway of the above is that we can try to minimize the energy of
$H$ among certain structured product states that break the entanglement of
high degree vertices, up to certain error.

Let us now consider a Hamiltonian defined on an $h$-minor free graph
$G=(V,E)$, and similarly to the above partition the set of vertices into
$V=\mathcal{L}\cup\mathcal{H}$ of degree $\leq\Delta$ and $>\Delta$
respectively. Consider the subgraph
$G_{\mathcal{L}}=(\mathcal{L},E_{\mathcal{L}})$ of $G$, defined by the
vertices of $\mathcal{L}\subset V$, and the edges between them (basically
delete $\mathcal{H}$ from the graph). This graph is still $h$-minor free, and
by construction, has bounded degree $\leq\Delta$. In this manner, we can apply
the separator framework of the previous section. We partition $\mathcal{L}$
into (disjoint subsets) clusters $C_{1}\cdots C_{c}$ of $c=O(n)$ clusters of
low degree vertices, each of size $\leq r$, by deleting $O(\Delta
n/r\epsilon+\epsilon m)$ edges. We can now define a Hamiltonian
$H^{\prime\prime}$, corresponding to the interactions within the clusters,
between clusters and high-degree vertices, and between the high-degree
vertices - that is, we omit cluster-cluster interactions.

$H^{\prime\prime}=\sum_{e\in E,u,v\in\text{ some }C_{i}}H_{e}+\sum_{e\in
E,u,v\in\mathcal{H}}H_{e}+\sum_{e\in E,u\in\mathcal{H},v\in\mathcal{L}}H_{e}$
(194)

where once again Weyl’s inequality guarantees these Hamiltonians have similar
spectra

$\|H-H^{\prime\prime}\|\leq O(J\Delta n/r\epsilon+\epsilon Jm).$ (195)

Let us pick, for conciseness and later convenience, $\Delta=O(\epsilon^{-3})$,
and $r=O(\epsilon^{-5})$, such that the error above is $O(\epsilon mJ)$. Let
us consider minimizing the ground state energy of $H^{\prime\prime}$ among
clustered product states
$\bigotimes_{C_{i}\subset\mathcal{L}}\sigma_{C_{i}}\bigotimes_{u\in\mathcal{H}}\sigma_{u}$,
where each of the high degree vertices is put in a product, and each of the
clusters $C_{i}$ is also put in a product. Let $\sigma$ be said minimum. We
will discuss how to find said $\sigma$ of such structure shortly, but for now
let us discuss its guarantees. We claim

######  Claim F.1.

With $H^{\prime\prime}$ previously defined; If $\sigma$ is the minimizer of
$\text{Tr}[H^{\prime\prime}\sigma]$ among product states of certain structure
$\sigma=\bigotimes_{C_{i}\subset\mathcal{L}}\sigma_{C_{i}}\bigotimes_{u\in\mathcal{H}}\sigma_{u}$,
then $\sigma$ also provides a good estimate for the ground state energy of
$H$:

$\text{Tr}[H\sigma]\leq\min_{\rho}\text{Tr}[H\rho]+O(\epsilon Jm).$ (196)

###### Proof.

Let $D_{2}$ be the set of all density matrices over $n$ particles of the form
$\sigma_{\mathcal{L}}\bigotimes_{u\in\mathcal{H}}\sigma_{u}$, and let $D_{1}$
be the set of all density matrices over $n$ particles of the form
$\bigotimes_{C_{i}\subset\mathcal{L}}\sigma_{C_{i}}\bigotimes_{u\in\mathcal{H}}\sigma_{u}$,
i.e. with a tensor product over the clusters of low degree vertices. Lemma F.6
tells us that if $\rho^{\prime\prime}$ is the ground state of
$H^{\prime\prime}$, then there exists $\sigma_{1}\in D_{1}$ such that

$\text{Tr}[H^{\prime\prime}\sigma_{1}]\leq\text{Tr}[H^{\prime\prime}\rho^{\prime\prime}]+O(\epsilon
Jm)$ (197)

We note that since $H^{\prime\prime}$ has no interactions between clusters,
then one can construct a density matrix $\sigma_{2}\in D_{2}$ that is the
marginalization of $\sigma_{1}$ in each cluster, i.e.

$\sigma_{2}=\bigotimes_{C_{i}\subset\mathcal{L}}\sigma_{2,C_{i}}\bigotimes_{u\in\mathcal{H}}\sigma_{u}\text{
with }\sigma_{2,C_{i}}=\text{Tr}_{\mathcal{L}\setminus
C_{i}}[\sigma_{1,\mathcal{L}}]\text{ such that
}\text{Tr}[H^{\prime\prime}\sigma_{1}]=\text{Tr}[H^{\prime\prime}\sigma_{2}]$
(198)

with the guarantee that their energies over $H^{\prime\prime}$ are exactly the
same. In this manner,

$\min_{\sigma\in
D_{2}}\text{Tr}[H^{\prime\prime}\sigma]\leq\text{Tr}[H^{\prime\prime}\sigma_{2}]=\text{Tr}[H^{\prime\prime}\sigma_{1}]\leq\text{Tr}[H^{\prime\prime}\rho^{\prime\prime}]+O(\epsilon
Jm)$ (199)

Let $\sigma^{*}\in D_{2}$ be the minimizer of the LHS above, corresponding to
the minimum energy state among the clustered product states. We are thereby
guaranteed that $\sigma^{*}$ is a good estimate for the ground state energy of
the actual $H$, since

$\displaystyle\text{Tr}[H\sigma^{*}]\leq\text{Tr}[H^{\prime\prime}\sigma^{*}]+O(\epsilon
Jm)\leq\text{Tr}[H^{\prime\prime}\rho^{\prime\prime}]+O(\epsilon Jm)\leq$
(200) $\displaystyle\leq\text{Tr}[H^{\prime\prime}\rho]+O(\epsilon
Jm)\leq\text{Tr}[H\rho]+O(\epsilon Jm).$ (201)

Where, in sequence, we use the fact that $H,H^{\prime\prime}$ are close, then
the previously derived relation with the ground state $\rho^{\prime\prime}$ of
$H^{\prime\prime}$, next the fact that $\rho$ has larger energy than
$\rho^{\prime\prime}$ on $H^{\prime\prime}$ by definition, and finally the
fact that $H,H^{\prime\prime}$ are close once again. ∎

Now that we are guaranteed that the clustered product state $\sigma$ that
minimizes the energy of $H^{\prime\prime}$ is also a good estimate for the
ground state energy, let us reason how to find it.

######  Claim F.2.

Let $D_{2}$ be the set of clustered product density matrices of the form
$\bigotimes_{i\in[c]}\sigma_{C_{i}}\bigotimes_{u\in\mathcal{H}}\sigma_{u}$.
Then, there exists a deterministic algorithm that performs the minimization
$\min_{\sigma\in D_{2}}\text{Tr}[H^{\prime\prime}\sigma]$ and returns a state
$\sigma\in D_{2}$ in time $n\cdot 2^{O(\epsilon^{-9}\log 1/\epsilon)}$ such
that

$\text{Tr}[H^{\prime\prime}\sigma]\leq\min_{\sigma\in
D_{2}}\text{Tr}[H^{\prime\prime}\sigma]+\epsilon mJ$ (202)

###### Proof.

Let us consider the Hamiltonian $H^{\prime\prime}$ and the graph
$G^{\prime\prime}$ it is defined on. Recall that $G^{\prime\prime}$ can be
configured into a set of high degree vertices $\mathcal{H}$, and a set of
disjoint clusters $C_{1}\cdots C_{c}$ of low degree vertices, where there are
no interactions between clusters. For convenience, consider contracting each
of these clusters into supernodes, each of local dimension
$2^{|C_{i}|}=2^{O(r)}$, each connected only to high-degree vertices. We note
that given a tree decomposition of $G^{\prime\prime}$, we can construct
another decomposition $T$ of the supernode graph in linear time, where the
tree-width is still bounded by $O(\epsilon^{-1})$ by Lemma F.1. WLOG, by Lemma
F.2 we can assume $T$ is a binary tree of size $O(n)$.

As discussed by [BBT09] and [BH13], we could construct a $\epsilon$-net over
each of the clusters and particles defined in the decomposition. This would
reduce the problem to that of a classical Hamiltonian, where we could perform
the known dynamic programming algorithm on graphs of low tree-width to
minimize the energy. The central caveat in this approach is that the number
possible values for the spin of each cluster is doubly exponential in the size
of the cluster, $2^{O(2^{r}\log 1/\epsilon)}=2^{2^{\text{poly}(1/\epsilon)}}$,
as the dimension of the Hilbert space of each cluster is already exponential
in $r=\text{poly}(1/\epsilon)$, and the dimension of the net is exponential in
the dimension of the Hilbert space. We emphasize that this is already an
exponential improvement over the original construction of [BH13], but we can
further improve the runtime by refining the dynamic programming algorithm.

Consider augmenting the tree-decomposition $T$ as follows. For each bag $B\in
T$, if there is a cluster-node $C_{i}\in B$, then we augment the bag $B$ by
adding to it the entire neighborhood of the cluster $C_{i}$. We note that we
are only adding high degree vertices to the bag, as $C_{i}$ is only connected
to high degree vertices in $G^{\prime\prime}$. By adding these neighborhoods,
we argue that the resulting tree is still a valid tree decomposition, but now
at a higher tree-width. It follows by carefully inspecting property 3 in the
definition F.1 that the decomposition remains a valid tree-decomposition. More
importantly, we note that we can bound the new width of the tree-decomposition
by the sizes of the added neighborhoods. Since each cluster has size $\leq r$,
each of degree $\leq\Delta$, the neighborhood of high degree vertices of each
cluster must be bounded by $\leq r\cdot\Delta$. Since there are at most tree-
width $t=O(k)=O(\epsilon^{-1})$ cluster-nodes in each bag, we have added at
most $O(kr\Delta)=O(\epsilon^{-9})$ high degree vertices to each bag. This is
the new tree-width of the augmented tree decomposition.

Let us now consider constructing an $\epsilon$-net over each high degree
vertex in $\mathcal{H}$. Consider a fixed cluster $C_{i}$, and fix a
configuration $\psi_{u_{1}}\cdots\psi_{u_{N(C_{i})}}$ of its
$O(r\Delta)=O(\epsilon^{-8})$ high degree vertex neighbors $u_{1}\cdots
u_{|N(C_{i})|}$, where here $|N(C_{i})|$ denotes the size of the neighborhood.
The key point in why the augmented decomposition is useful, is the fact that
once the configuration of the neighbors $N(C_{i})$ is fixed, the density
matrix of the cluster $\sigma_{C_{i}}$ that minimizes the energy is well
defined:

$\sigma_{C_{i}}=\text{argmin}_{\rho}\sum_{(u,v)\in E:u,v\in
C_{i}}\text{Tr}_{u,v}\bigg{[}H_{uv}\rho_{uv}\bigg{]}+\sum_{(u,v)\in E:u\in
C_{i},v\in
N(C_{i})}\text{Tr}_{u,v}\bigg{[}H_{uv}\rho_{u}\otimes\psi_{v}\bigg{]}$ (203)

Simply the ground state of an effective Hamiltonian. We emphasize that in this
setting one can treat this interaction between the cluster $C_{i}$ and its
high-degree neighborhood $N(C_{i})$ as an effective $|N(C_{i})|$-local
classical interaction between the neighbors, as the minimum energy of the
interactions with and within $C_{i}$ only depends on the spins of the
neighborhood. Crucially, each of these interactions is covered in at least a
bag via the augmentation.

Now let us formulate the dynamic programming algorithm. We express the
subproblems as follows. Consider a given bag $B$ in the tree decomposition
$T$, let $u_{1}\cdots u_{|B|}$ be the high-degree vertices in the bag, and let
$V_{B}$ be all the vertices of $G$ contained in the subtree of $T$ rooted at
$B$. Our subproblem $E(B,\psi_{u_{1}}\cdots\psi_{u_{|B|}})$ corresponds to the
minimum energy of the classical hamiltonian $H_{V_{B}}$ defined by all the
interactions fully contained in $V_{B}$, among states in the clustered product
convex set $D_{2}$, conditioned on fixing the states of the high degree
vertices $u_{1}\cdots u_{|B|}$ in $B$ to be $\psi_{u_{1}}\cdots\psi_{u_{|B|}}$
(each a spin chosen from the $\epsilon$-net). We note that there are a total
of $O(n)\cdot(1/\epsilon)^{O(|B|)}=O(n)\cdot 2^{\text{poly}(1/\epsilon)}$ such
subproblems.

The base case of the dp is quite straightforward. It suffices to compute the
minimum energy of $H_{V_{B}}$ for each configuration of high degree vertices
in the bags $B$ that are leaves of the tree. Let us now recursively relate the
subproblems defined on a bag $B$ with that of the at most two children
$B_{1},B_{2}$ of $B$ in $T$. We divide into cases on the interactions within
$V_{B}$. Let $H_{U}$ be the Hamiltonian defined by interactions within $B$,
that are not fully supported in neither $V_{B_{1}}$ or $V_{B_{2}}$. Let
$H_{12}$ be the interactions fully contained within both $V_{B_{1}}$ and
$V_{B_{2}}$, which by property 3 of the definition F.1, we are guaranteed to
be fully contained in $B$. Via inclusion-exclusion, we can express the
classical Hamiltonian corresponding to the interactions within $V_{B}$ as
$H_{V_{B}}=H_{V_{B_{1}}}+H_{V_{B_{2}}}+H_{U}-H_{1,2}$.

Fix a configuration of the spins of $B$,
$\psi_{B}=\psi_{u_{1}}\cdots\psi_{u_{|B|}}$. Let $B\cap B_{i}$ be the vertices
that are both in $B$ and $B$’s $i$th child, $i\in\\{1,2\\}$. The spins of this
set must be consistent with those chosen in $B$. In this setting, one can
express the recursive optimization as

$\displaystyle E(B,\psi_{B})=\min_{\psi_{B_{1}\setminus
B},\psi_{B_{2}\setminus B}}\bigg{[}E(B_{1},\psi_{B_{1}\cap
B}\otimes\psi_{B_{1}\setminus B})+E(B_{2},\psi_{B_{2}\cap
B}\otimes\psi_{B_{2}\setminus B})\bigg{]}+$ (204)
$\displaystyle+\text{Tr}\bigg{[}\big{(}H_{U}-H_{1,2}\big{)}\psi_{B}\bigg{]}$
(205)

For fixed subproblem $(B,\psi_{B})$, computing the corresponding energy above
involves iterating over the configurations in the $\epsilon$-net of the
particles in $B_{1}\setminus B$ and $B_{2}\setminus B$, and thereby takes
$(1/\epsilon)^{O(|B|)}=2^{O(\epsilon^{-9}\log 1/\epsilon)}$ time. Since there
are $n\cdot 2^{O(\epsilon^{-9}\log 1/\epsilon)}$ subproblems, we can compute
the entire dynamic programming table in time $n\cdot 2^{O(\epsilon^{-9}\log
1/\epsilon)}$. Finally, we return the minimum of $E(r,\psi_{r})$ at the root
$r$ of the tree $T$, over the choices $\psi_{r}$ in the $\epsilon$-net of the
high degree vertices in $r$. ∎

Claim F.2 guarantees that we can find the minimum energy clustered product
state $\sigma\in D_{2}$ that minimizes the energy of $H^{\prime\prime}$ in
polynomial time, and Claim F.1 guarantes that it is a good approximation for
the ground state energy of $H$. This concludes the proof of the main theorem
of this section, Theorem F.1.

##  Appendix G A Free Energy PTAS on Sparse Graph Classes

In this section, we extend the divide-and-conquer and dynamming programming
scheme to construct approximations to the free energy of 2-Local Hamiltonians
defined on $h$-minor free graphs. We do so in 3 steps. First, we begin in
subsection G.1 by constructing a classical approximation scheme for the free
energy of 2-Local Hamiltonians defined on $h$-minor free graphs of bounded
degree. Parallel to our algorithms for the ground state energy of Hamiltonians
on sparse graphs of bounded degree of section F, we use ideas from
Bidimensionality theory to construct Hamiltonians that are clustered in a
sense, and simpler to optimize over. Our algorithms for the bounded degree
case are randomized, they achieve extensive additive errors, and work in the
full regime of temperature. We summarize:

######  Theorem G.1.

Let $H=\sum_{e\in E}H_{e}$ be a 2-Local Hamiltonian on $n$ qubits defined on
an $h$-minor free graph $G=(V,E)$, where $|h|=O(1)$, $|E|=m$. Further assume
that each particle only directly interacts with $\leq\Delta$ other particles,
that is, the graph has bounded degree $\Delta$. Let the maximum interaction
strength be $\max_{e}\|H_{e}\|_{\infty}=J$. Then there exists a classical,
randomized algorithm that produces a clustered product state $\sigma$ that
approximates the free energy of $H$ up to error

$F\leq f(\sigma)\leq F+\epsilon mJ$ (206)

The algorithm runs in time $n^{O(1)}+n\cdot 2^{O(\Delta/\epsilon^{2})}$.

We note that in the bounded degree case, both the quality of the approximation
and the runtime are temperature independent.

To lift our approximation schemes to the arbitrary degree case, we first have
to argue that separable and product states actually serve as good
approximations to the free energy. To do so, in subsection G.2 we use an
application of the entropy non-decreasing Theorem 4.2 to argue that the
Brandao-Harrow states produced by the high-low degree technique (Lemma F.6) do
also serve as good approximations to the free energy.

In the ensuing subsection G.3, we construct a dynamic programming algorithm
that approximately finds the minimum of the free energy among these clustered
product states. As our approach hinges on a discretization of the Hilbert
space of high degree vertices, we incur a small thermal error which limits our
algorithms to the low temperature regime. To summarize, we prove:

######  Theorem G.2.

Let $H=\sum_{e\in E}H_{e}$ be a 2-Local Hamiltonian on $n$ qubits defined on
an $h$-minor free graph $G=(V,E)$, where $|h|=O(1)$, $|E|=m$. Let the maximum
interaction strength be $\max_{e}\|H_{e}\|_{\infty}=J$. Then there exists a
classical, randomized algorithm that produces a clustered product state
$\sigma$ that approximates the free energy of $H$ up to error

$F\leq f(\sigma)\leq F+\epsilon mJ$ (207)

The algorithm runs in time $n^{O(1)}+n\cdot\max(2,\frac{1}{\beta
J})^{\tilde{O}(\epsilon^{-9})}$ .

######  Remark G.1.

We emphasize that the algorithm of the theorem above approximates the free
energy of $H$ up to constant error $\epsilon$ in the low temperature regime in
polynomial time $n^{\text{poly}(1/\epsilon)}$, that is, for any polynomial
temperature $T\leq O(Jn^{c})$ for any integer $c$.

###  G.1 Bounded Degree h-Minor Free Graphs

In this subsection we provide an algorithm for approximating the free energy
of Hamiltonians defined on $h$-minor free graphs of bounded degree. We
summarize in the theorem:

######  Theorem G.3 (Theorem G.1, restatement).

Let $H=\sum_{e\in E}H_{e}$ be a 2-Local Hamiltonian on $n$ qubits defined on
an $h$-minor free graph $G=(V,E)$, where $|h|=O(1)$, $|E|=m$. Further assume
that each particle only directly interacts with $\leq\Delta$ other particles,
that is, the graph has bounded degree $\Delta$. Let the maximum interaction
strength be $\max_{e}\|H_{e}\|_{\infty}=J$. Then there exists a classical,
randomized algorithm that produces a clustered product state $\sigma$ that
approximates the free energy of $H$ up to error

$F\leq f(\sigma)\leq F+\epsilon mJ$ (208)

The algorithm runs in time $n^{O(1)}+n\cdot 2^{O(\Delta/\epsilon^{2})}$.

Our approach to the bounded degree case follows that of the ground state
approximation scheme of Theorem F.3. We use ideas from Bidimensionality theory
to decompose $G$ into disconnected clusters, that can be optimized
independently. To recall the construction, we first apply Theorem F.2 from the
work of [DHiK05] to decompose $G$ into components of tree-width
$O(\epsilon^{-1})$, by the removal of $O(\epsilon m)$ edges. Next, we apply
the recursive vertex separator Lemma F.5 to further decompose the graph into
disjoint components $C_{1}\cdots C_{c}$ of size $\leq
r=O(\Delta/\epsilon^{2})$, by removing another $O(\epsilon m)$ edges. We note
that the number of components is $c=O(n)$. Let the resulting Hamiltonian
defined over the interactions that weren’t deleted be $H^{\prime}$. We observe
$\|H-H^{\prime}\|_{\infty}\leq\epsilon Jm$.

######  Remark G.2.

The Gibbs state of $H^{\prime}$ is a product state over the clusters, that is,

$e^{-\beta H^{\prime}}/Z=\bigotimes_{i\in[c]}e^{-\beta H_{C_{i}}}/Z_{C_{i}},$
(209)

since the support of the Hamiltonians $H_{C_{i}}$ within each cluster $C_{i}$
are disjoint, and thereby commute.

A simple but crucial technical lemma enables us to approximate the free energy
of $H$ by using the Gibbs state of the simpler Hamiltonian $H^{\prime}$, which
is close to $H$.

######  Lemma G.1.

Let $H$ and $H^{\prime}$ be two 2-Local Hamiltonians, and $\rho,\rho^{\prime}$
their corresponding Gibbs states, and $f(\cdot),f^{\prime}(\cdot)$ their
corresponding variational free energies. Then

$f(\rho)\leq f(\rho^{\prime})\leq f(\rho)+2\cdot\|H-H^{\prime}\|_{\infty}$
(210)

###### Proof.

The lower bound on $f(\rho^{\prime})$ follows from the variational definition
of the free energy. In turn, the upper bound satisfies:

$f(\rho^{\prime})\leq f^{\prime}(\rho^{\prime})+\|H-H^{\prime}\|_{\infty}\leq
f^{\prime}(\rho)+\|H-H^{\prime}\|_{\infty}\leq
f(\rho)+2\cdot\|H-H^{\prime}\|_{\infty}.$ (211)

∎

We now are in a position to prove our main theorem of this subsection.

###### Proof.

[of Theorem G.1]

We note that given a generic hamiltonian on $r$ qubits, one can explicitly
diagonalize the Hamiltonian and find all its eigenvectors and eigenvalues in
time $2^{O(r)}$. One can therefore explicitly construct its Gibbs state at a
certain temperature in time $2^{O(r)}$.

In this setting, we describe our algorithm as follows. We first construct the
decomposed Hamiltonian $H^{\prime}$ as detailed above in time $n^{O(1)}+n\cdot
2^{O(\epsilon^{-1})}$. Let $C_{1}\cdots C_{c}$ be the clusters in the
decomposed graph $G^{\prime}$. For each cluster, we construct its Gibbs state
explicitly by diagonalizing the Hamiltonian $H^{\prime}_{C}$, the terms of
$H^{\prime}$ supported on $C$, in total time $O(n)\cdot 2^{O(r)}=n\cdot
2^{O(\Delta/\epsilon^{2})}$. Finally, we return the product state
$\sigma=\bigotimes_{i\in[c]}\sigma_{C_{i}}$.

We note that via remark G.2, the state we return is indeed the exact Gibbs
state of $H^{\prime}$. Via Lemma G.1, we are guaranteed that the variational
free energy $f(\sigma)$ is indeed close to the actual free energy of $H$. In
fact, since $\|H-H^{\prime}\|=O(\epsilon mJ)$, by an appropriate choice of
$\epsilon$ we obtain the approximation guarantee.

∎

###  G.2 Clustered Approximations to the Free Energy

In this subsection we reason that clustered product states (as defined in
Section F), and ensembles of clustered product states, are good approximations
to the free energy on $h$-minor free graphs. To do so, we first extend the
high-low degree technique (Lemma F.6) of [BH13] with the entropy non-
decreasing theorem to argue that breaking the entanglement among high-degree
vertices also provides a good approximation to the free energy on sparse
graphs. We follow our approach in Section 4 to argue that in fact one can
consider a single a product state over high degree vertices, that approximates
the free energy up to twice the error in the high-low degree technique. Then,
we reason as we did in section G.1 by applying ideas from the Bidimensionality
theory to construct a simpler, decomposed Hamiltonian that is easier to
optimize over. Our main conclusion of this subsection is the idea that one can
compute the minimum free energy clustered product state for the simpler
Hamiltonian $H^{\prime}$, and said state will be a good approximation for the
true free energy. We formalize and summarize in Claim G.1.

To begin, let us recall the setting of the high-low degree technique of
[BH13], presented in Lemma F.6. Consider an $h$-minor free graph $G$, and let
$\mathcal{H},\mathcal{L}$ be the sets of vertices of degree $>\Delta$ and
$\leq\Delta$ respectively. For any given state $\rho$ defined on qubits
configured on a graph $G$, Lemma F.6 guarantees the existence of a separable
state which is a product over both the states of the high-degree particles
$\mathcal{H}$ and the measured particles $C$:

$\sigma=\mathbb{E}_{C,b}\eta_{C,b}=\mathbb{E}_{C,b}\mathbb{E}_{z}\psi_{C,b,z}\otimes\sigma_{\mathcal{L}\setminus
C}^{(C,b,z)}\bigotimes_{u\in\mathcal{H}\setminus C}\sigma_{u}^{(C,b,z)}$ (212)

We note that the entropy non-decreasing theorem 4.2 allows us to state that
$S(\rho)\leq S(\eta_{C,b})$, for all possible choices of $C,b$. This is since
our proof of Theorem 4.2 does not require us to take marginals of every qubit,
as is the structure of the high-low degree states. In fact, this observation
enables us to carry the proof technique of theorems 4.3 and 4.4, and to argue
that a particular product state
$\gamma_{C,b}=(\mathbb{I}_{C}/d^{|C|})\otimes\sigma_{\mathcal{L}\setminus
C}^{(C,b,z^{*})}\bigotimes_{u\in\mathcal{H}\setminus
C}\sigma_{u}^{(C,b,z^{*})}$ provides a good approximation to the free energy:

######  Lemma G.2.

Let $H$ be a $2$-Local Hamiltonian defined on an $h$-minor free graph
$G=(V,E)$. Let $\mathcal{H},\mathcal{L}$ be the subsets of vertices in $G$ of
degree $>\Delta$ and $\leq\Delta$ respectively. Let $C$ be a subset of
vertices of size $\leq l$, and $b\in\\{1,2,3\\}^{|C|}$. Then there exists a
product state
$\gamma_{C,b}=(\mathbb{I}_{C}/d^{|C|})\otimes\sigma_{\mathcal{L}\setminus
C}^{(C,b,z^{*})}\bigotimes_{u\in\mathcal{H}\setminus
C}\sigma_{u}^{(C,b,z^{*})}$ for a particular choice of $C,b,z^{*}$, such that

$f(\gamma_{C,b})\geq F\geq f(\gamma_{C,b})-2\delta_{l,\Delta}$ (213)

where $F$ is the free energy of $H$.

###### Proof.

We remark that the entropy non-decreasing Theorem 4.2 enables us follow the
same proof of Theorem 4.3 and conclude that there exists $C,b$ such that the
separable states $\eta_{C,b}$ are $\delta_{l,\Delta}$-additive approximations
to the free energy. In particular, one in fact reasons that these states are
good approximations in expectation

$\mathbb{E}_{C,b}f(\eta_{C,b})\leq F+\delta_{l,\Delta}$ (214)

To prove the existence of a single product state over high-degree vertices
that serves as a good approximation to the free energy, we follow the approach
of the proof of Theorem 4.4, in carefully constructing states
$\gamma_{C,b}=(\mathbb{I}_{C}/d^{|C|})\otimes\sigma_{\mathcal{L}\setminus
C}^{(C,b,z^{*})}\bigotimes_{u\in\mathcal{H}\setminus
C}\sigma_{u}^{(C,b,z^{*})}$ by replacing the states of set of particles in $C$
with maximally mixed states, and optimally picking measurement outcomes
$z^{*}$ for each $\eta_{C,b}$. Please refer to Theorem 4.4 for details. We
obtain that the states $\gamma_{C,b}$ are good approximations to the free
energy in expectation:

$\mathbb{E}_{C,b}f(\gamma_{C,b})\leq F+2\cdot\delta_{l,\Delta}$ (215)

∎

The next question is whether we can simplify the Hamiltonian to impose more
structure on the states of the un-measured low degree vertices,
$\sigma_{\mathcal{L}\setminus C}$. Our intention will be to write these states
of low degree vertices as a tensor product of its marginal density matrices of
clusters of low degree vertices in the graph. To do so, let us now consider
the Hamiltonian $H^{\prime\prime}$ of section F. Let us briefly recall its
construction: starting from $H$ defined on $G=(V,E)$, we first use Lemma F.2
to define a subgraph $G^{\prime}$ of $G$ such that each connected component
has tree width $O(\epsilon^{-1})$. Next, we partition the vertices of
$G^{\prime}$ into high and low degree vertices thresholded by a degree
$\Delta=O(\epsilon^{-3})$, and use the recursive vertex separator Lemma F.5 to
decompose the subgraph of low degree vertices into components $C_{1}\cdots
C_{c}$, $c=O(n)$, each of size at most $r=O(\epsilon^{-5})$. The total amount
of edges removed from $G$ to form $G^{\prime\prime}$ was $O(\epsilon m)$. The
following claim says that we can attempt to optimize the free energy by
exploiting this clustering:

######  Claim G.1.

Let $H$ be a 2-Local Hamiltonian defined on an $h$-minor free graph $G$, and
let $H^{\prime\prime}$ be its corresponding Hamiltonian defined after the
decomposition procedure of Section F. Let $C_{1}\cdots C_{c}$ be the disjoint
clusters of low degree particles in $H^{\prime\prime}$. Then, there exists
clustered product state
$\sigma=\bigotimes_{i\in[c]}\sigma_{C_{i}}\bigotimes_{u\in\mathcal{H}}\sigma_{u}$
that provides a good approximation to the free energy:

$f(\sigma_{C,b})\geq F\geq f(\sigma_{C,b})-2\cdot\delta_{l,\Delta}-O(\epsilon
mJ)$ (216)

The claim above is the key existence statement that enables us to later
optimize over clusters independently. Our strategy to proving it follows
closely to the proof of Claim F.1.

######  Remark G.3.

Let us pick $l=O(n\Delta^{-1/3})$, and as before $\Delta=O(\epsilon^{-3})$,
such that an adequate rescaling of $\epsilon$ achieves total error $\epsilon
mJ$.

###### Proof.

Let $\rho,\rho^{\prime\prime}$ be the Gibbs states of $H,H^{\prime\prime}$
respectively. Lemma G.1 tells us that $F=f(\rho)\leq
f(\rho^{\prime\prime})\leq f(\rho)+O(\epsilon mJ)$, since $H,H^{\prime\prime}$
are close. Let us now apply Lemma G.2, the free energy variant of the high-low
degree technique to $H^{\prime\prime},\rho^{\prime\prime}$. We are guaranteed
the existence of clustered product states $\gamma_{C,b}$ for each $C,b$ such
that

$\mathbb{E}_{C,b}f^{\prime\prime}(\gamma_{C,b})\leq
f^{\prime\prime}(\rho^{\prime\prime})+\delta_{l,\Delta}$ (217)

Fix $C,b$, and let us consider the state $\gamma_{C,b}$. Recall that it is of
the form