# Improved Product-state Approximation Algorithms for Quantum Local
Hamiltonians

Thiago Bergamaschi UC Berkeley. Email<EMAIL_ADDRESS>
###### Abstract

The ground state energy and the free energy of Quantum Local Hamiltonians are
fundamental quantities in quantum many-body physics, however, it is QMA-Hard
to estimate them in general. In this paper, we develop new techniques to find
classical, additive error product-state approximations for these quantities on
certain families of Quantum $k$-Local Hamiltonians. Namely, those which are
either dense, have low threshold rank, or are defined on a sparse graph that
excludes a fixed minor, building on the methods and the systems studied by
Brandão and Harrow, Gharibian and Kempe, and Bansal, Bravyi and Terhal.

We present two main technical contributions. First, we discuss a connection
between product-state approximations of local Hamiltonians and combinatorial
graph property testing. We develop a series of weak Szemerédi regularity
lemmas for $k$-local Hamiltonians, built on those of Frieze and Kannan and
others. We use them to develop constant time sampling algorithms, and to
characterize the ‘vertex sample complexity’ of the Local Hamiltonian problem,
in an analog to a classical result by Alon, de la Vega, Kannan and Karpinski.
Second, we build on the information-theoretic product-state approximation
techniques by Brandão and Harrow, extending their results to the free energy
and to an asymmetric graph setting. We leverage this structure to define
families of algorithms for the free energy at low temperatures, and new
algorithms for certain sparse graph families.

##  1 Introduction

The mean-field approximation is a popular heuristic in quantum many-body
physics, in which product-states are used as an ansatz for generic quantum
states. The low-energy states of quantum systems may be highly entangled
objects, and possibly exponentially more complex than simple (unentangled)
product states. This often makes computing properties of these low-energy
states classically intractable. From a complexity-theoretic point of view, the
mean-field approach casts these quantum problems that are in the complexity
class QMA [KSV02], into problems in NP, since product-states have a
polynomial-size description and can act as classical, efficiently verifiable
certificates. However, in the absence of a hardness-of-approximation result
for QMA [Aar06, Ara11, AALV09, Has13] and assuming QMA$\neq$NP, it is
generally unknown if the ground states of quantum systems can even have ‘good’
approximations with succinct classical descriptions, let alone if we can
compute or approximate them efficiently.

In this work, we develop a series of classical algorithms to efficiently find
mean-field approximations for quantum systems described by local Hamiltonians,
and we develop new techniques to show that good mean-field approximations
exist for fairly general classes of these systems. A local Hamiltonian
corresponds to a sparse matrix $H\in\mathbb{C}^{d^{n}\times d^{n}}$ which is
exponentially large in the number $n$ of quantum particles (or qudits), and
can be described as a sum over ‘local’ terms $H=\sum_{e\in E}h_{e}$ defined by
some hypergraph $G=([n],E)$. $H$ is said to be $k$-local if each hyperedge
$e\in E$ is a $k$-tuple of vertices in $[n]$, see section 2.1 for more
details.

It is well known that the existence of product-state approximations to $H$ is
very sensitive to the structure of the underlying interaction graph $G$. In a
seminal result, [BH13] proved that so long as $H$ has bounded interaction
strengths, and is defined on a graph $G$ of high degree or small expansion,
then there exists a product state which approximates the ground state energy
of $H$ up to an additive error $\epsilon\cdot m$ (scaling with the number of
edges or ‘interactions’ $m$ of $H$). Their results can be interpreted as
rigorous proofs of accuracy of the mean-field approximation to the ground
state energy of certain systems, and they opened the door to classical
approximation schemes to find these ‘good’ mean-field solutions efficiently.
One of the main focuses of this work is to relax certain assumptions on the
structure of the interaction graphs $G$, to extend the scope of their
algorithms and existence statements.

The second main focus of this work is to study the structure and classical
computation of properties of quantum systems in thermal equilibrium. The
Helmholtz Free Energy $F(\beta)$ of a Quantum Local Hamiltonian $H$ at a given
temperature $\beta^{-1}$ arises as an approximate counting analog to the
ground state energy, as it reveals the degeneracy of the ground state (the
number of QMA witnesses), the density of states of the Hamiltonian, as well as
the existence of phase transitions. Quantitatively, $F(\beta)$ can be
described as the optimum of a maximum entropy program:

$F(\beta)\equiv\min_{\rho\geq 0,\|\rho\|_{1}=1}f(\rho)=\min_{\rho\geq
0,\|\rho\|_{1}=1}\text{Tr}[H\rho]-S(\rho)/\beta$ (1)

Where the optimizer $\rho\propto e^{-\beta H}$ of the program above is called
the Gibbs state of $H$. The computational complexity, and in particular the
hardness of approximation of $F(\beta)$ is similarly not comprehensively
understood. While QMA-Hard to estimate in general due to a reduction to the
‘low temperature’ limit, and exactly computable in polynomial time using a #P
oracle [BFS11], it would seem there is much to uncover regarding the
computational tradeoffs between error and temperature [BCGW21].

###  1.1 Our Main Contributions

In this section we overview our main contributions, which we present formally
and in more detail in section 2.2.

Rigorous Mean-Field Approximations and Guarantees in NP

Our first contributions concern improvements and extensions to the existence
statements by [BH13]. Their methods had roots in the information-theoretic
techniques by [RT12] and [BRS11], developed in the context of approximating
CSPs using the Lasserre Heirarchy. Informally, we show how to use their self-
decoupling arguments to construct mixed states which are tensor products of
single-particle mixed states, which approximate the Free Energy up to an
additive error. We view these results as rigorous proofs of accuracy for the
mean-field approximation to the Free Energy of Quantum Local Hamiltonians, and
they imply that approximating the Free Energy of dense Hamiltonians up to an
extensive error (scaling with the number of edges) is in NP.

######  Theorem 1.1.

Fix $d=O(1),\epsilon>0$, and an inverse temperature $\beta$. Let $H=\sum_{e\in
E}h_{e}$ be a $2$-Local Hamiltonian on $n$ qudits of local dimension $d$, and
$m=\Omega(n/\epsilon^{3})$ interactions each of strength
$\|h_{e}\|_{\infty}\leq 1$. Then, there exists a product state
$\sigma_{\beta}=\otimes_{u\in[n]}\sigma_{u},\sigma_{u}\in\mathbb{C}^{d\times
d}$ such that

$F(\beta)\leq
f(\sigma_{\beta})=\text{Tr}[H\sigma_{\beta}]-S(\sigma_{\beta})/\beta\leq
F(\beta)+\epsilon\cdot m$ (2)

We emphasize two important points about the result above. First and foremost,
the existence of approximations to $F(\beta)$ in NP implies that we can now
use classical approximation schemes to search for optimal mean-field
approximations to the free energy, and they will also be good approximations
to the ‘entangled value’ of $F(\beta)$. As we discuss later, this enables us
to import practically all the previous machinery of approximation schemes for
the ground state energy, to the Free Energy, developing novel algorithms for
many quantum systems and improving on recent results.

The second point of emphasis is that the result above holds at all
temperatures $\beta^{-1}$. In this fashion, we are able to bypass the ‘low
temperature bottleneck’ of many approximation schemes for the Free Energy
which constrain approaches in previous work, such as the polynomial
interpolation method [Bar16] or Markov Chain Monte Carlo methods. We present a
comprehensive comparison with previous work and the scope of our techniques
for thermal systems in section 2.3.

Hamiltonian Regularity Lemmas, Approximation Algorithms and Property Testing

From an algorithmic point of view, our main contribution is a connection
between product state approximations and graph property testing. We discuss
quantum analogs of the weak Szemerédi regularity lemmas for dense graphs,
hyper-graphs and low-threshold rank graphs [FK99, AdlVKK02, GT13], developed
in the context of additive approximation schemes for Max-Cut and Max-kCSPs. At
their heart lies a powerful combinatorial characterization of these systems,
Szemerédi’s celebrated regularity lemma [Sze75], which states that dense
graphs can be approximately decomposed into unions of complete bipartite
graphs. We develop natural, constructive generalizations of these results for
Quantum Local Hamiltonians, by combining our new product state approximations
with multi-coloured versions of known weak regularity results, leading to
improved approximation algorithms and novel structural characterizations of
local Hamiltonians. Our central result in this vein is an additive error
approximation scheme for dense $k$-Local Hamiltonians, which runs in constant
time:

######  Theorem 1.2.

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

We report our sampling algorithms, including that in theorem 1.2, in the probe
model of computation introduced by [GGR98]. In a nutshell, the time complexity
measured above corresponds to the number of queries to a description of $H$,
see section 2.1 for more details. In the body, we show how these ideas can be
used to develop improvements in runtime from $n^{\text{poly}(1/\epsilon)}$ to
$\text{poly}(n,1/\epsilon)+2^{\text{poly}(1/\epsilon)}$ or
$2^{\text{poly}(1/\epsilon)}$ for a wide range of problems on Quantum Local
Hamiltonians, such as approximation schemes for the ground state energy, the
Free Energy, and for Hamiltonians defined on low threshold rank graphs.

##  2 Technical Overview

###  2.1 Background and Notation

Linear Algebra and Matrix Norms Given an $w\times w$ matrix $A$ we refer to
$\|A\|_{p}$ as the Schatten $p$-norm of $A$, the $L_{p}$ norm of the singular
values of $A$, and we refer to $|A|_{p}$ as the $L_{p}$ norm of the
$w^{2}$-dimensional vectorization of $A$. The graph decompositions are phrased
in terms of the cut norm $\|A\|_{C}$ introduced by [FK99], defined by

$A^{+}=\max_{S_{1},S_{2}\subseteq[w]}\sum_{i\in S_{1},j\in S_{2}}A_{ij}\text{
and }\|A\|_{C}=\max(A^{+},(-A)^{+})$ (3)

where we have $\|A\|_{C}\leq\|A\|_{\infty\rightarrow 1}=\sup_{x\neq
0}\frac{|Ax|_{1}}{|x|_{\infty}}\leq 4\cdot\|A\|_{C}$.

Asymptotic Notation For any function $f(n)$ we refer to the asymptotic
notation $\tilde{O}(f(n))=O(f(n)\text{polylog}(f(n)))\leq c_{1}\cdot
f(n)\log^{c_{2}}f(n)$ for a choice of real positive constants $c_{1},c_{2}$.

Local Hamiltonians We denote a $k$-Local Hamiltonian on $n$ qudits of local
dimension $d$ via a $d^{n}\times d^{n}$ Hermitian matrix, which can be
expressed as a sum of local interactions $H=\sum_{e\in E}h_{e}$. By ‘local’,
we simply mean that each summand $h_{e}=H_{e}\otimes\mathbb{I}_{V\setminus e}$
acts non-trivially only on $k$ particles at a time, as indicated by each
$k$-tuple $e=(u_{1}\cdots u_{k})$ in a set of hyper-edges $E$. In this manner,
we can specify any Local Hamiltonian ‘instance’ simply by specifying the
$d^{k}\times d^{k}$ submatrices of each local term. If $d,k=O(1)$, then the
input has a polynomial-sized description in $n$. For notational convenience,
we often omit the trivial support $\mathbb{I}_{V\setminus e}$. The ground
state energy and the ground state of $H$ are its minimum eigenvalue and
corresponding eigenvector, and the variational minimum energy of $H$ is the
minimum energy of $H$ among all product states
$\min_{\rho=\otimes\rho_{u}}\text{Tr}[H\otimes_{u}\rho_{u}]$ with
$\rho_{u}\in\mathbb{C}^{d\times d}$ and $\rho_{u}\geq
0,\text{Tr}_{u}[\rho_{u}]=1$.

Interaction Graphs We refer to the ‘Interaction Graph’ $G=([n],E)$ of a
2-Local Hamiltonian $H$ as the graph with undirected edges $e=(u,v)\in E$
whenever the particles $u,v$ interact non-trivially in $H$. That is, whenever
the spectral norm is non-zero $\|H_{e}\|_{\infty}\neq 0$. By expressing each
$d^{2}\times d^{2}$ Hermitian matrix
$H_{u,v}=\sum_{i,j\in[d^{2}]}H^{i,j}_{u,v}\cdot\sigma^{i}_{u}\otimes\sigma^{j}_{v}$
in an orthogonal basis decomposition, and grouping all the interactions with
the same basis $i,j$, we refer to the $i,j$ ‘Pauli Graph’ as the subgraph of
$G$ induced on all the directed edges $e=(u,v)$ with non-zero
$H^{i,j}_{u,v}=d^{-2}\text{Tr}[H_{u,v}\sigma^{i}_{u}\otimes\sigma^{j}_{v}]$,
with weighted adjacency matrix $J^{ij}=\\{H^{i,j}_{u,v}\\}_{u,v\in[n]}$. We
note that the matrices $J^{ij}$ are degenerate, since $J^{ij}=(J^{ji})^{T}$,
but we often brush over this issue via a handshaking argument. If we are given
a density matrix $\rho=\otimes\rho_{u}$ which is a product of single qudit
density matrices with a basis decomposition
$\rho_{u}=d^{-1}\sum_{i}\alpha^{i}_{u}\cdot\sigma^{i}$, then the energy of
$\rho$, $\text{Tr}[H\rho]$ is a polynomial over the real variables $\alpha$:

$\sum_{(u,v)\in
E}\text{Tr}[H_{u,v}\rho_{u}\otimes\rho_{v}]=d^{-2}\sum_{(u,v)\in
E}\sum_{i,j\in[d^{2}]}H^{i,j}_{u,v}\alpha^{i}_{u}\cdot\alpha^{j}_{v}=(2d^{2})^{-1}\sum_{i,j\in[d^{2}]}\sum_{u\neq
v\in[n]}J^{ij}_{uv}\alpha^{i}_{u}\cdot\alpha^{j}_{v}$ (4)

Model of Computation We report our sampling algorithms in the probe model of
computation introduced by [GGR98] in the context of graph property testing.
That is, we assume we can sample a uniformly random vertex or hyper-edge in
$O(1)$ time (or ‘probes’). Formally, fixed a $k$-Local Hamiltonian ‘instance’
$H=\sum_{e\in E}H_{e}\otimes\mathbb{I}_{V\setminus e}$, for any $k$-tuple of
vertices/hyper-edge $e=(u_{1}\cdots u_{k}),u_{i}\in[n]$, we assume we can
query the (constant-sized) $d^{k}\times d^{k}$ sub-matrix $H_{e}$ in $O(1)$
time. We emphasize that since our goal is often a sublinear time algorithm, we
always enforce that our algorithms output estimates for the energy (or free
energy), and implicit descriptions of product states. If requested, these
implicit descriptions can always be expanded into $n$-qudit product states in
an additional polynomial time.

Extensive Errors We refer to an additive approximation scheme, or an additive
error, for a problem on a Hamiltonian $H$ (or graph $G$), as extensive if the
notion of error scales with the number of interactions of $H$ (resp., edges of
$G$). For instance, an $\epsilon\cdot m$ additive approximation scheme for
Max-Cut on graphs of $m$ edges is an ‘extensive’ error approximation scheme
for constant $\epsilon$. We pay particular attention to this limit of additive
errors since the PCP theorem [ALM+92] ensures it is NP-Hard to approximate
Max-Cut up to said error in general.

###  2.2 Our Results

Approximation Guarantees in NP

The first of our results are rigorous proofs of accuracy of the mean-field
approximation on Quantum $k$-Local Hamiltonians. We argue the existence of
product states, or products of single-particle mixed states, which provide
additive error approximations to the ground state energy and the free energy
of these systems. We build on the information-theoretic techniques by [BH13],
presenting an extension to the free energy and modestly refining their
techniques on generic (hyper-) graphs.

######  Theorem 2.1.

Fix $k,d=O(1)$. Let $H=\sum_{e\in E}h_{e}$ be a $k$-Local Hamiltonian on $n$
qudits of local dimension $d$, and $m$ interactions each of strength
$\|h_{e}\|_{\infty}\leq 1$. Then, there exists a product state
$\psi\rangle=\otimes_{u\in[n]}|\psi_{u}\rangle,|\psi_{u}\rangle\in\mathbb{C}^{d}$
such that

$\langle\psi|H|\psi\rangle\leq\min_{\phi}\langle\phi|H|\phi\rangle+O(n^{\frac{k-1}{3}}m^{2/3})$
(5)

In the body, we prove more general versions of the theorem above sensitive to
the matrix of interaction strengths of $H$. Theorem 2.1 matches the previous
results in [BH13] whenever the Hamiltonian is defined on $D$-regular or dense
graphs $m=\Omega(n^{k})$, and generalizes these statements to an asymmetric
setting on Hamiltonians which are dense on average. In the setting of Theorem
2.1, whenever $m=\Omega(n^{k-1}/\epsilon^{3})$, approximating the ground state
energy of $H$ up to additive error $\epsilon\cdot m$ is in the complexity
class NP, as the product state has a polynomial size description and acts as a
classical witness. While these optimal product states may be NP-Hard to find
in the worst case, there are many examples where one can approximate these
solutions efficiently.

To extend both these information-theoretic ideas and algorithmic applications
to the free energy, we need further insights on the structure of these product
state approximations. We discuss in section 4 how the ‘entanglement-breaking’
procedure of [BH13], not only approximately preserves the energy, but in fact
also increases the entropy as well. When applied to the Gibbs state, we show
one can carefully extract a tensor product of single particle mixed-states
which is a good approximation to the free energy. We formalize this statement
in Theorem 2.2,

######  Theorem 2.2.

Fix $k,d=O(1)$, and an inverse temperature $\beta$. Let $H=\sum_{e\in E}h_{e}$
be a $k$-Local Hamiltonian on $n$ qudits of local dimension $d$, and $m$
interactions each of strength $\|h_{e}\|_{\infty}\leq 1$. Then, there exists a
product state
$\sigma_{\beta}=\otimes_{u\in[n]}\sigma_{u},\sigma_{u}\in\mathbb{C}^{d\times
d}$ such that

$f(\sigma_{\beta})=\text{Tr}[H\sigma_{\beta}]-S(\sigma_{\beta})/\beta\leq
F+O(n^{\frac{k-1}{3}}m^{2/3})$ (6)

We emphasize that the statement above implies a product state approximation
exists at all temperatures $\beta^{-1}$ (and recovers the ground state
approximation at $T=0$), and moreover uses very little of the underlying graph
structure apart from the average dense condition.

Hamiltonian Weak Regularity Lemmas

We develop an approach to designing approximations algorithms for Local
Hamiltonians based on weak Szemerédi regularity lemmas, which are approximate
decompositions to graphs, matrices, and tensors [Sze75, FK99, AdlVKK02, GT13].

The idea behind this construction lies in a powerful tool in extremal
combinatorics. In his celebrated regularity lemma, [Sze75] proved that any
dense graph can be approximated by a union of a constant number of complete
bipartite graphs. However, the number of partitions grew very fast with the
intended quality of approximation. [FK99] developed a constructive
decomposition under a weaker notion of approximation, what they refered to as
a “weak” regularity lemma. Concretely, they prove that any real $n\times n$
matrix with bounded entries can be decomposed into a sum of
$O(1/\epsilon^{2})$ cut matrices (complete bipartite graphs), up to an error
$\epsilon\cdot n^{2}$ in the cut norm. Moreover, [FK99] prove that one can in
fact construct such a “cut decomposition” implicitly in time polynomial in
$1/\epsilon$, which enables them to devise constant time sampling-based
approximation schemes for many problems on dense graphs.

We define a natural adaptation of their results to a quantum setting, by
constructing an approximate decomposition $H_{D}$ of a Local Hamiltonian $H$
which is a sum over complete, bipartite, sub-Hamiltonians. The structure of
$H_{D}$ can be understood as a ‘multi-colored’ matrix cut decomposition, as
essentially we apply the cut decomposition by [FK99] to each term in a basis
decomposition of $H$. For concreteness, let $H=\sum_{u,v}h_{u,v}$ be a
$2$-Local Hamiltonian on qubits, and let us consider re-writing its Pauli
basis decomposition below. We suppress the identity terms
$\otimes\mathbb{I}_{V\setminus\\{u,v\\}}$ on the qubits that each interaction
acts trivially on.

$H=\sum_{(u,v)\in E}h_{u,v}=\sum_{(u,v)\in
E}\sum_{i,j\in\\{I,X,Y,Z\\}}h^{i,j}_{u,v}\sigma_{u}^{i}\otimes\sigma_{v}^{j}=\sum_{i,j\in\\{I,X,Y,Z\\}}\sum_{u<v}h^{i,j}_{u,v}\sigma_{u}^{i}\otimes\sigma_{v}^{j}$
(7)

We associate each pair of indices $i,j\in\\{I,X,Y,Z\\}$ to a color, and
consider the $n\times n$ real valued weighted adjacency matrix
$J^{ij}=\\{h^{i,j}_{u,v}\\}_{u,v\in[n]}$ of the $i,j$ ‘Pauli Graph’. By
applying the cut decomposition by [FK99] to each of these $16$ matrices
$J^{ij}$, we construct an approximate decomposition of $H$ into roughly
$16\cdot O(1/\epsilon^{2})$ complete bipartite sub-Hamiltonians. In this
context, a ‘complete bipartite sub-Hamiltonian’ is defined by two Pauli
matrices, (say, $X,Y$), two subsets $S,T\subset[n]$ (which, for now, we assume
to be disjoint), and an interaction strength $\alpha\in\mathbb{R}$, and can be
expressed as $\alpha\sum_{u\in S,v\in T}X_{u}\otimes Y_{v}$.

In the body we argue that the approximation guarantees in the cut norm are
precisely what we need to ensure that for any product state
$\sigma=\otimes_{u}\sigma_{u}$, the energy of $\sigma$ under $H$ or $H_{D}$
are close: $\text{Tr}[H\sigma]\approx\text{Tr}[H_{D}\sigma]$. By further
combining this product state regularity with our asymmetric product state
approximations, we prove a stronger property on the spectra of $H_{D}$:

######  Lemma 2.1 (Informal).

Fix $d,k=O(1)$ and a constant $\epsilon>0$, and let $H=\sum_{e}h_{e}$ be a
$k$-Local Hamiltonian on $n$ qudits of local dimension $d$ and $m$
interactions of strength bounded by $\|h_{e}\|_{\infty}\leq 1$. Then, there
exists a decomposition $H_{D}=\sum_{i}^{s}D^{(i)}$ of $H$ into
$s=O(1/\epsilon^{2})$ complete bipartite sub-Hamiltonians such that

$\|H-H_{D}\|_{\infty}\leq\epsilon\cdot n^{k/2}m^{1/2}$ (8)

Additive Error Approximation Schemes

Leveraging the structure of the Hamiltonian regularity Lemma 2.1 in
combination with the product state approximation toolkit enables us to devise
a series of approximation schemes for Quantum Local Hamiltonians. We follow
the ideas of [FK99, AdlVKK02, GT13] in establishing LP relaxations to Max Cut
and other Max CSPs, and we develop an SDP relaxation scheme for finding the
minimal energy product state of a Local Hamiltonian. These ideas enable us to
devise an efficient additive error approximation scheme for dense
Hamiltonians,

######  Theorem 2.3 (Theorem 1.2, restatement).

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$ interactions of
bounded strength $\|h_{e}\|_{\infty}\leq 1$. There exists a randomized
algorithm which runs in time $2^{\tilde{O}(1/\epsilon^{2k-2})}$ in the probe
model of computation, and with probability $.99$ computes an estimate for the
ground state energy of $H$ accurate up to an additive error of $\epsilon\cdot
n^{k/2}\sqrt{m}$.

We note that $n^{k/2}\sqrt{m}\geq m$, and thus in polynomial or sublinear time
this approximation scheme only provides a non-trivial guarantee when the
hyper-graph is dense, $m=\Omega(n^{k}/\log^{c}n)$ for some small positive
constant $c$. However, it provides an improvement over the
$n^{O(1/\epsilon^{2})}$ time algorithms by [GK11] and [BH13] in this additive
error regime. On the other hand, a simple explicit variant of this result
provides a sub-exponential time approximation algorithm whenever
$m=\omega(n^{k-1}\log n)$:

######  Theorem 2.4.

In the context of Theorem 1.2, 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$.

Concretely, the key idea behind these relaxations is that for any product
state $\sigma=\otimes_{u}\sigma_{u}$, the energy of $\sigma$ on the cut
decomposition $H_{D}$ is a simple function of the average magnetization of a
small number of subsets of the $n$ qudits. To illustrate how this enables a
relaxation scheme, consider a single complete bipartite sub-Hamiltonian, such
as $H_{S,T}=\sum_{u\in S,v\in T}X_{u}\otimes Y_{v}$. The energy of $\sigma$ on
$H_{S,T}$ is

$\text{Tr}[H_{S,T}\sigma]=\sum_{u\in S,v\in
T}\text{Tr}_{u,v}[X_{u}\sigma_{u}\otimes
Y_{v}\sigma_{v}\big{]}=\bigg{(}\sum_{u\in
S}\text{Tr}[X_{u}\sigma_{u}]\bigg{)}\cdot\bigg{(}\sum_{v\in
T}\text{Tr}[Y_{v}\sigma_{v}]\bigg{)},$ (9)

simply the product of the average $X$ direction magnetization of $S\subset[n]$
with the average $Y$ magnetization of $T$. If we fix a ‘guess’ $r,c\in[-n,n]$,
one can introduce affine constraints on the single particle density matrices
$\sigma_{u}$, constraining their average magnetizations to lie within a
$\pm\gamma\cdot n$ range of the guess $r,c$:

$\displaystyle r-\gamma\cdot n\leq\sum_{u\in S}\text{Tr}[X_{u}\sigma_{u}]\leq
r+\gamma\cdot n$ (10) $\displaystyle c-\gamma\cdot n\leq\sum_{v\in
T}\text{Tr}[Y_{v}\sigma_{v}]\leq c+\gamma\cdot n$ (11)

Then we are guaranteed that any product state $\sigma$ which is feasible for
the constraints above must have energy in a range around the guess:
$|\text{Tr}[H_{S,T}\sigma]-r\cdot c|\leq(2\cdot\gamma+\gamma^{2})\cdot n^{2}$.
In this manner, one can discretize over the space of ‘guesses’ $(r,c)$ and
define an overlapping set of convex constraints on the description of the
product states $\sigma$, such that every product state is feasible for at
least one set of constraints. Approximating the ground state energy among
product states ultimately reduces to checking the feasibility of a constant
number of SDPs, one for each guess of $r,c$, and outputting whichever gives us
the smallest energy estimate.

Using the techniques by [GT13], we can extend these insights to the setting of
symmetric $2$-Local Hamiltonians defined on graphs of low threshold rank. They
proved that the weak regularity results of [FK99] could be extended to low-
threshold rank graphs, by constructing a cut decomposition of a low rank
approximation to the normalized adjacency matrix of these graphs. While in the
appendix we formalize approximation algorithms for generic symmetric
Hamiltonians (on low threshold rank graphs), perhaps the most faithful
extension of this result to the quantum setting would be its application to
approximating the Quantum Max Cut [GP19, PT21b, PT21a, PT22]. Given an
undirected graph $G=(V,E)$, the “Quantum Max-Cut” corresponds to the maximum
eigenvalue of the Hamiltonian

$H=\frac{1}{2}\sum_{e\in
E}\bigg{(}\mathbb{I}_{u}\otimes\mathbb{I}_{v}-X_{u}\otimes X_{v}-Y_{u}\otimes
Y_{v}-Z_{u}\otimes Z_{v}\bigg{)}\otimes\mathbb{I}_{V\setminus\\{u,v\\}}$ (12)

If $A$ is the adjacency matrix of $G$ and $D$ the diagonal matrix of degrees,
the $\delta$-SOS threshold rank $t_{\delta}(A)$ of $A$ is the number of
eigenvalues of the normalized adjacency matrix $D^{-1/2}AD^{-1/2}$ which are
outside of the range $[-\delta,\delta]$. We prove

######  Theorem 2.5.

Fix $\epsilon,\delta>0$. Let $G=(V,E)$ be a graph on $n$ vertices and $m$
edges with adjacency matrix $A$ and threshold rank $t\equiv
t_{\epsilon/2}(A)$. Then, there exists an algorithm which finds an
$\epsilon\cdot m+O(n^{1/3}m^{2/3})$ additive error approximation to the
Quantum Max Cut of $G$ in time
$\text{poly}(n,1/\epsilon,t)+2^{\tilde{O}(t/\epsilon^{2})}$.

For instance, sparse $D$-regular random graphs have $\Theta(D^{-1/2})$-SOS
threshold rank $1$. In this manner, for any constant $\epsilon$ and if
$D=\Omega(1/\epsilon^{3})$, then one can compute an $\epsilon\cdot m$
approximation to the Quantum Max Cut of a $D$-regular random graph in
polynomial time.

A series of works [JKM18a, JKM18b, JKR19] showed that the matrix weak
regularity lemma [FK99] could be used to approximate the free energy of Ising
Models, and to give interesting structural results on the quality of the mean-
field approximation and the ‘vertex sample complexity’ of these systems. They
observed that the maximum entropy program subject to the linear relaxation
constraints described above, reveals properties of the Gibbs distribution and
enables an additive error approximation to the free energy at all
temperatures. By combining these ideas with the Hamiltonian regularity Lemma
2.1 and Theorem 2.2 on product state approximations to the free energy, we
develop a series of additive error approximation schemes for the free energy
of Quantum Local Hamiltonians. The first of which is a constant time
approximation scheme, which provides an additive error guarantee in a low
temperature regime.

######  Theorem 2.6.

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})$ in the probe model of computation, 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$.

We emphasize that the free energy is a convex program regularized by
temperature, and thereby our approximation schemes often incur a tradeoff
between combinatorial errors and thermal (temperature dependent) errors. In
the low temperature regime, whenever $\beta=\Omega(n^{1-k/2}m^{-1/2})$, the
algorithm above recovers the behavior of the ground state energy approximation
scheme, and is largely temperature independent. However, as the temperature
increases and surpasses the threshold, the leading source of error becomes the
thermal error $\delta n/\beta$. In our second algorithm, we show that an
explicit approach significantly improves this thermal error dependence, at the
cost of a polynomial runtime.

######  Theorem 2.7.

Fix $k,d=O(1)$, and $\epsilon,\delta>0$ 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 high
probability.

The Vertex Sample Complexity

The Regularity Lemma 5.1 enables us to derive an insightful structural
statement for Local Hamiltonians. Namely, the definition of a ‘vertex sample
complexity’ for Local Hamiltonians of bounded interaction strengths, in an
analogy to the vertex sample complexity of Max-kCSPs of [AdlVKK02] and [AE02].
They showed that the restriction of any Max-kCSP to a uniformly random sample
of $\text{poly}(1/\epsilon)$ variables, sufficed to estimate the maximum
number of satisfiable clauses up to an additive error of $\epsilon\cdot
n^{k}$. We develop a generalization of this result to Quantum Local
Hamiltonians, by combining the Hamiltonian regularity lemma with some
extensions to the proof techniques by [AdlVKK02] to SDPs.

######  Theorem 2.8.

Fix $d,k=O(1)$ and $\epsilon>0$, and let $H$ be a $k$-local Hamiltonian on $n$
qudits of local dimension $d$ and $m$ bounded interaction strengths. Let
$Q\subset[n]$ be a uniformly random sample of $q=\Omega(\epsilon^{-6}\log
1/\epsilon)$ of those qudits, and let $H_{Q}$ be the sum of interactions with
support contained entirely in $Q$. Then, with probability $0.99$,

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

We rely crucially on the guarantee of product state approximations to Quantum
Local Hamiltonians in this regime of additive error. Indeed, one of the
directions of the statement above is quite intuitive for both classical and
quantum systems: If the ground state energy of $H$ is low, then the ground
state energy of the restriction $H_{Q}$ can’t be much higher than the
estimate. This is since the reduced density matrix
$\rho_{Q}=\text{Tr}_{V\setminus Q}[\psi]$ of the ground state $\psi$ of $H$,
probably also has low energy
$\text{Tr}[H_{Q}\rho_{Q}]\approx\frac{q^{2}}{n^{2}}\cdot\text{Tr}[H\psi]$, and
the true ground state energy of $H_{Q}$ can only be lower than that.

In the converse, however, lies an interesting ‘semi-classical’
characterization of this additive error regime. Note that if the ground state
energy of $H$ is ‘high’, then in particular there doesn’t exist any product
states with low energy on $H$. Using the proof techniques in [AdlVKK02], we
show this implies the existence of a certain succinctly describable classical
certificate to this product-state ‘infeasibility’, which we sample from to
prove the absence of product states with low energy on $H_{Q}$. Here is where
we require the asymmetric product state approximations of Theorem 2.1: for
sufficiently large $Q$, the absence of low energy product states for $H_{Q}$
must imply a high ground state energy for $H_{Q}$. In this sense, the ground
state energy of $H_{Q}$ can’t be much lower than its estimate either.

As a straightforward corollary to this structural result, now we can easily
devise an algorithm which provides an additive error guarantee by exactly
diagonalizing the Hamiltonian $H_{Q}$ on $q=\tilde{O}(\epsilon^{-6})$ vertices
in time $2^{\tilde{O}(1/\epsilon^{6})}$. However, we can in fact do slightly
better, simply by applying the additive error, product state approximation
algorithm by [GK11] to the subsample:

######  Corollary 2.1.

Fix $d,k=O(1)$ and $\epsilon>0$, and let $H$ be a $k$-Local Hamiltonian on $n$
qudits of local dimension $d$ and $m$ bounded interaction strengths. There
exists a randomized algorithm which runs in time
$2^{\tilde{O}(\epsilon^{-2})}$, and with probability $.99$ outputs an estimate
to the ground state energy accurate up to an additive error of $\epsilon\cdot
n^{k}$.

Aside from the improved dependence on $k$ in the exponent, this result may
seem to only subtly differ from that in Theorem 1.2. However, we emphasize
that Theorem 1.2 requires an exponential number in $1/\epsilon$ of samples of
vertices, whereas Theorem 2.8 guarantees a polynomial number suffices.

Approximation Schemes on Graphs that exclude a Fixed Minor

Finally, for our last main contribution, we develop novel singly-exponential
time algorithms for sparse, $2$-Local Hamiltonians defined on graphs that
exclude a fixed minor. Formally, the family of $h$-minor free graphs are all
the graphs $G$ that can not produce another (smaller) graph $h$, by deleting
edges and vertices and by contracting edges [RS86a]. Planar graphs, and
bounded genus graphs (such as toriods) are among the interesting special cases
of these classes. Our approach builds on previous work by [BBT09] and [BH13]
on planar graphs, using more general combinatorial decompositions [DHiK05] and
improving on their ‘quantum-to-classical’ mappings. We show how such $2$-Local
Hamiltonians can be approximately understood as classical Max $k$-CSPs defined
on the high degree vertices in the graph, and develop a dynamic programming
algorithm to solve it using a simple hyper-dimensional version of a tree
decomposition. Our first result for these systems is a classical algorithm to
approximate the ground state energy in time singly exponential in
$\text{poly}(1/\epsilon)$,

######  Theorem 2.9.

Fix $\epsilon>0$. Let $H$ be a 2-Local Hamiltonian defined on $n$ qubits and
$m=\Theta(n)$ bounded strength interactions of norm $<1$, configured on an
$h$-minor free graph $G=(V,E)$ where the minor is constant size $|h|=O(1)$.
Then, we can approximate the ground state energy of $H$ up to additive error
$\epsilon\cdot n$, in time $\text{poly}(n)+n\cdot
2^{\text{poly}(1/\epsilon)}$.

We build on these ideas by combining them with our information-theoretic
techniques for the free energy of quantum systems, to construct novel
algorithms for the free energy of these classes of sparse graphs at low
temperatures as well.

######  Theorem 2.10.

Fix $\epsilon>0$ and an inverse temperature $\beta$. Let $H$ be a 2-Local
Hamiltonian on $n$ qubits and $m=\Theta(n)$ bounded strength interactions of
norm $<1$, configured on an $h$-minor free graph $G=(V,E)$ where the minor is
constant size $|h|=O(1)$. Then, we can approximate the the free energy
$F(\beta)$ of $H$ up to additive error $\epsilon\cdot n$, in time
$\text{poly}(n)+n\cdot\max(2,\beta^{-1})^{\text{poly}(1/\epsilon)}$,
respectively.

###  2.3 Related Work

Classical Approximation Schemes for QMA Complete Problems

While the systematic study of approximation algorithms to QMA-Complete
problems is still emerging, there are a number of works we would like to
highlight on the topic. [BBT09] developed classical approximation schemes for
ground state energies of classical and Quantum 2-Local Hamiltonians configured
on planar graphs (of bounded degree, in the quantum case). They leveraged
Baker’s technique [Bak94] and structural properties of planar graphs to
approximately decompose the Hamiltonian into non-interacting partitions, which
then could be analyzed by exact diagonalization, or dynamic programming.
[GK11] were among the first to construct an approximation algorithm for the
$k$-Local Hamiltonian Problem. They argued that product states can provide a
$d^{-k+1}$-relative factor approximations to the ground state energy of
$k$-Local Hamiltonians defined on qudits, similarly to how Max Cut admits a
$1/2$ multiplicative approximation. They then developed an approximation
algorithm for the variational problem of finding the minimal energy product
state of a given Local Hamiltonian $H$. It constructs a product state that
provides an (extensive) $\epsilon\cdot n^{k}$ additive approximation to the
ground state energy, in runtime $n^{O(\epsilon^{-2}\log 1/\epsilon)}$. Their
approach was based on an adaptation of a classical technique, the “exhaustive
sampling method” by [AKK99] to the quantum setting, developed in the context
of approximating Max Cut on dense graphs.

Later, [BH13] developed information-theoretic techniques to argue the
existence of product state approximations to the the ground state energy. More
precisely, they show that so long as $H$ is everywhere dense
($\Omega(n^{k-1})$ minimum degree), has bounded expansion, or is clustered
into regions of sub-volume law entanglement entropy, there exist product
states that provide additive error approximations to the minimum energy.
Leveraging their information-theoretic statements, they turned the algorithm
of [GK11] into a PTAS for the ground state energy, albeit only meaningful when
the number of interactions $m=\Omega(n^{k})$. Additionally, they devise
approximation schemes for Quantum Hamiltonians defined on generic planar
graphs (not just those of bounded degree), solving an open problem posed by
[BBT09]. Their key insight was what we refer to as a ‘high-low degree’
technique, in which one could consider a product state over all vertices of
degree larger than some tunable cutoff $\Delta$, and a generic (entangled)
quantum state over the hilbert space of the low-degree particles, while
incurring only a small error to the ground state energy. It is worthwhile to
raise however, that the runtime of the resulting algorithm is triply-
exponential in $1/\epsilon$, where the algorithm returns an $\epsilon\cdot n$
additive approximation.

More recently, in the context of relative error approximation schemes, [HM15]
showed that one can find a product state within a relative error of $\sqrt{l}$
of the ground state of a traceless $k$-Local Hamiltonian of bounded norm,
where $l$ is the maximum degree of the underlying hyper-graph. [BGKT19]
devised a $O(\log n)$ multiplicative approximation scheme to the ground state
energy of 2-Local traceless Hamiltonians by rounding the solutions of SDPs to
product states.

Classical Approximation Schemes for the Free Energy of Quantum Systems

Our results also contribute to a rich literature of classical techniques for
thermal quantum systems. Perhaps the most well known of these techniques are
the Quantum Monte Carlo methods, which approximate the quantum partition
function of a quantum system to that of a classical spin system, which in turn
is approximated via Markov chain Monte Carlo methods. Despite the enormous
practical success of these techniques, rigorous proofs of convergence have
only been presented in certain restricted systems [BG17, Ber20, CH21], and
they generically are efficient only in the high temperature limit. Another
high-temperature technique is the polynomial interpolation method [Bar16,
HMS20], based on a Taylor expansion of the partition function in the high
temperature limit. Although both of these approaches are only provably
efficient either on restricted classes of systems (such as substochastic
Hamiltonians) and/or in the high temperature limit (typically $\beta$ is a
constant, or at most $O(\log n)$), they provide quite strong notions of
approximation. In fact, they generally provide $(1+\epsilon)$ multiplicative
approximations to the partition function (which translates to an $\epsilon$
additive approximation to the free energy), while in this paper we only
attempt extensive, additive, $\epsilon\cdot m$ error approximations to the
free energy.

By approaching the problem via this weaker notion of error, it is possible to
devise approximation schemes in a much wider range of temperatures. A recent
result by [BCGW21] presented an algorithm that estimates the free energy of
dense Local Hamiltonians, also building on the information-theoretic
techniques by [BH13]. Their approach is based on a quantum generalization to a
classical correlation rounding approach by [Ris16], and their algorithm finds
a $\epsilon\cdot n^{2}$ additive approximation to the free energy of 2-Local
Hamiltonians, in runtime $n^{O(\epsilon^{-2})}$.

Comparison to Previous Work

To conclude our introduction we summarize our algorithmic improvements in
constrast to previous known constructions for the quantum systems studied. In
table 1 below we label the Hamiltonians, and runtime and accuracy guarantees
of the additive error approximation schemes in previous work for the systems
we consider. In table 2, we present our results for these same systems.

For simplicity, unless otherwise stated we concern ourselves with Quantum
Local Hamiltonians of bounded interaction strengths $\|H_{e}\|_{\infty}\leq 1$
on $n$ qubits and $m$ interactions. In both tables, we refer to a ‘low
threshold rank’ Hamiltonian as having constant $\epsilon$-SOS threshold rank
of its interaction graph. With the exception of the recent work by [BCGW21],
all the results in table 1 concern ground state energy approximation schemes.

Result | Context | Accuracy | Runtime
---|---|---|---
[GK11] |  $k$-local Hamiltonians | $\epsilon\cdot n^{k}$ | $n^{\tilde{O}(\epsilon^{-2})}$
[BH13] | Low Threshold Rank | $\epsilon\cdot\sum_{e\in E}\|H_{e}\|_{\infty}$ | $n^{O(\epsilon^{-1})}$
Hamiltonians
[BCGW21] | Free Energy of | $\epsilon\cdot n^{2}+\delta\cdot n/\beta$ | $n^{\tilde{O}(\epsilon^{-2})}\cdot O(\log 1/\delta)$
2-local Hamiltonians
[BBT09] | Planar Graphs | $\epsilon\cdot\sum_{e\in E}\|H_{e}\|_{\infty}$ | $n^{O(1)}\cdot 2^{2^{\text{poly}(\Delta,\epsilon^{-1})}}$
of bounded degree $\Delta$ |  |
[BH13] | Planar Graphs | $\epsilon\cdot\sum_{e\in E}\|H_{e}\|_{\infty}$ | $n^{O(1)}\cdot 2^{2^{2^{\text{poly}(\epsilon^{-1})}}}$
Table 1: A summary of previous algorithms for related Quantum Systems System | Context | Accuracy | Runtime
---|---|---|---
$k$-local Hamiltonians | G.S. Energy | $\epsilon\cdot n^{k}$ | $2^{\text{poly}(\epsilon^{-1})}$
Free Energy | $\epsilon\cdot n^{k}+\delta\cdot n/\beta$ | $2^{\text{poly}(\epsilon^{-1})}\cdot O(\delta^{-2})$
Low Threshold Rank | Maximum | $\epsilon\cdot m+O(n^{1/3}m^{2/3})$ | $(n/\epsilon)^{O(1)}+2^{\tilde{O}(1/\epsilon^{2})}$
Quantum Max Cut | Eigenvalue
$h$-Minor Free Graphs | G.S. Energy | $\epsilon\cdot n$ | $n^{O(1)}+n\cdot 2^{\text{poly}(\Delta,\epsilon^{-1})}$
of bounded degree $\Delta$ | Free Energy
$h$-Minor Free Graphs | G.S. Energy | $\epsilon\cdot n$ | $n^{O(1)}+n\cdot 2^{\text{poly}(\epsilon^{-1})}$
Free Energy | $n^{O(1)}+n\cdot\max(2,\beta^{-1})^{\text{poly}(\epsilon^{-1})}$
Table 2: The main algorithms in this work

###  2.4 Organization

We organize the rest of the paper as follows. Before diving into the proofs,
in section 3 we present a discussion on open problems raised in this work and
future problems we hope our techniques could be useful to.

To keep our information-theoretic arguments self-contained, we begin in
section 4 by presenting our existence statements, and our extensions to the
techniques by [BH13]. We proceed in section 5 by presenting a simple
discussion on our Hamiltonian regularity lemma, key to our additive error
approximation schemes. In section 6.2, we apply our regularity lemma to define
additive error approximation schemes for the 2-Local Hamiltonian problem. We
defer the generalizations to $k$-local systems to appendix C, and to 2-Local
Hamiltonians on low threshold graphs to appendix D. Finally, in section 7, we
present our sample complexity bounds.

For conciseness, we’ve deferred to the appendix all our algorithms for sparse
graphs, and our algorithms for the free energy. In appendix E, we extend our
additive approximation schemes for the ground state energy, to approximating
the free energy of $k$-Local Hamiltonians. In appendix F, we present our
algorithms for the ground state energy of Hamiltonians on graphs that exclude
a fixed minor. Finally, in appendix G, we lift those techniques to the free
energy of graphs that exclude a fixed minor as well.

##  3 Discussion

We conclude this work by raising some open problems. The first of which is a
curious gap between the quality of the mean field approximation to classical
and Quantum Local Hamiltonians. To contrast our results to those in the
classical setting, [BCL+12, BM15, JKM18a, JKR19] studied the quality of the
mean-field approximation to classical spin glass models with generic
interaction matrices. The work of [JKR19] culminated in the result that the
mean-field approximation is within an additive error of $O(n^{2/3}m^{1/3})$ of
the free energy, a strictly better dependence on the number of interactions
than our upper bound, $O(n^{1/3}m^{2/3})$. As both these results have roots in
the information-theoretic techniques by [RT12], it seems intriguing to ask
whether there is some deeper structure. A possible direction would be to
combine the regularity insights with the correlation rounding techniques, as
in [JKR19]. However, there remain certain technical obstacles to approaching
the free energy of quantum systems with the regularity lemma, namely analyzing
the matrix exponential of the cut decomposition $H_{D}$.

Another interesting problem is to improve the weak regularity results for ‘low
threshold rank’ Hamiltonians, discussed in section D. While we are able to
devise approximation schemes based on graph regularity for a range of
Hamiltonians whose interaction graphs have low threshold rank, we are unable
to provide an actual construction of an approximate Hamiltonian $H^{\prime}$.
It would also be interesting to see whether the coarsest partition technique
could be lifted to be applied to more general low threshold rank Hamiltonians,
as opposed to relying on the high degree of symmetry of the Quantum Max Cut.

Finally, while the focus of this paper is on product-state approximations, the
author considers it to be an outstanding open problem whether one can devise
entangled ansatz’s for classical approximations schemes to quantum problems.
For examples, see [Kin22, AGM20], who devised low-depth quantum circuits which
perform slightly better than the best product state on certain Hamiltonians.

##  4 On The Existence of Product State Approximations

In this section, we discuss the existence of separable and product states that
approximate the energy and the free energy of Local Hamiltonians that are
somewhat ‘dense’. The approach follows that of [BH13], in analysing the
structure of $n$ qudit quantum states once you condition on, or measure, a
small random subset of the qudits. They showed that for any given starting
state $\rho$, a certain ‘entanglement-breaking’ mapping could be used to
construct a separable state $\sigma$, defined over single-qudit marginals of
$\rho$ conditioned on measurement outcomes. They prove that under this
mapping, on average $\sigma$ approximates the few-body marginals of $\rho$,
which is then used to ensure that $\sigma$ approximately preserves the energy
of $\rho$ on sufficiently dense Hamiltonians.

We note that a similar mapping was used by [BGKT19] to prove a stronger
version of a theorem by Lieb [Lie73], and a recent paper by [BCGW21] uses this
idea to ensure that certain pseudo-distributions resulting from convex
programming solvers can be accurately rounded to product states which
approximate the free energy of dense ($m=\Omega(n^{2})$) 2-Local Hamiltonians.
Here, we reason that there exist extensive error, product state approximations
to the free energy up to a much smaller $m=\omega(n)$ number of edges, and
extend the results by [BH13] to this sparse graph regime without assuming that
the graph is everywhere-dense (i.e has a minimum degree). To prove these
results, we reason about the entropy of the separable states produced by their
‘entanglement-breaking’ mapping, and its product state components.

We organize the rest of this section as follows: In subsection 4.1, we
introduce notation, discuss the entanglement breaking procedure, and the
structure of the separable state $\sigma$. In subsection 4.2, we prove an
extension to the results of [BH13] on general graphs, by showing how the
separable state $\sigma$ approximately preserve the energy of $\rho$. In
subsection 4.3, we discuss how the state $\sigma$ is a mixture of states
$\eta^{C,b}$, which have higher entropy than $\rho$. Finally, we conclude in
subsection 4.4 by showing how to carefully extract a product state from these
ensembles which approximates the free energy.

###  4.1 The Entanglement-Breaking Mapping

Before beginning, let us discuss the mapping and setup some notation. Let
$\Lambda$ be a single-qubit measurement channel of low distortion, meaning
that we have an upper bound on $\|\gamma\|_{1}/\|\Lambda(\gamma)\|_{1}$ for
all traceless operators $\gamma$. While tighter results in terms of the local
dimension $d$ and the Hamiltonian locality $k$ are possible by carefully
choosing $\Lambda$, for our purposes we follow the choice by [BGKT19, BCGW21]
and let $\Lambda$ be a measurement in a random Pauli basis:

$\displaystyle\Lambda(\rho)=\frac{1}{3}\sum_{b\in[3],r\in[-1,1]}|b,r\rangle\langle
b,r|\cdot\langle\psi_{b,r}|\rho|\psi_{b,r}\rangle,\text{ and }$ (14)
$\displaystyle\mathcal{N}(\rho)=\frac{1}{3}\sum_{b\in[3],r\in[-1,1]}|\psi_{b,r}\rangle\langle\psi_{b,r}|\cdot\langle\psi_{b,r}|\rho|\psi_{b,r}\rangle,$
(15)

where $\mathcal{N}$ corresponds to a measurement and averaging over the
measurement outcome. In the above, we denote as
$|\psi_{b,1}\rangle,|\psi_{b,-1}\rangle$ the eigenstates of the Pauli matrix
$\sigma_{b}$, $b\in\\{1,2,3\\}$, with eigenvalues $1,-1$. When applied to
qudits of local dimension $d=2^{d^{\prime}}$, we simply apply the channel
$\Lambda^{\otimes\log d}$.

If $\rho$ is a generic density matrix on a set $V$ of $n$ qubits, [BH13]
define its separable state approximation $\sigma$ as follows. Fixed an integer
parameter $l$, they first sample a small integer $m\in[l]$, and then randomly
sample a subset $C\subset V$ of $m$ particles to measure. Then, the channel
$\mathcal{N}^{\otimes m}_{C}\otimes\mathbb{I}_{V\setminus C}$ is applied on
the qubits in $C$. To shorten notation, we denote the expectation over the
size $m$ of $C$ and the choice of $C$ as $\mathbb{E}_{0\leq m\leq
l}\mathbb{E}_{C\subset[n],|C|=m}\equiv\mathbb{E}_{C}$; and, for $x=(b,r)$ with
$b\in\\{1,2,3\\}^{m}$ and $r\in\\{-1,1\\}^{m}$ denoting a $m$ different bases
and $m$ measurement outcomes, we write
$|\psi_{x}\rangle=\otimes_{i=1}^{m}|\psi_{b_{i},r_{i}}\rangle\text{ and
}\psi_{x}\equiv|\psi_{x}\rangle\langle\psi_{x}|$. Let $\tau$ denote the
density matrix corresponding to the ensemble over measurement outcomes of this
process, which can be written as

$(\mathcal{N}^{\otimes m}_{C}\otimes\mathbb{I}_{V\setminus
C})(\rho)=\tau=\mathbb{E}_{C,x=(b,r)}\psi_{x}^{C}\otimes\tau^{(C,x)},$ (16)

with $\tau^{(C,x)}=\langle\psi_{b,r}^{C}|\rho|\psi_{b,r}^{C}\rangle$ the
density matrix on the unmeasured qubits $V\setminus C$, consistent with
outcomes $x$ on the particles $C$. Finally, to define $\sigma$, each
$\tau^{(C,x)}$ is ‘broken’ into the tensor product of its marginals
$\tau^{(C,b,r)}_{u}=\text{Tr}_{(V\setminus
C)\setminus\\{u\\}}[\tau^{(C,b,r)}]$. The resulting separable state $\sigma$
can be expressed as an ensemble over choices of $C$ and the measurement basis
and outcomes $x=(b,r)$:

$\sigma\equiv\mathbb{E}_{C,x=(b,r)}\psi_{x}^{C}\bigotimes_{u\notin
C}\tau^{(C,b,r)}_{u}\equiv\mathbb{E}_{C,x=(b,r)}\eta^{(C,b,r)}\equiv\mathbb{E}_{C,b}\eta_{C,b}$
(17)

where in the RHS above we introduce
$\eta^{(C,b,r)}=\psi_{(b,r)}^{C}\bigotimes_{u\notin C}\tau^{(C,b,r)}_{u}$ and
$\eta_{C,b}=\mathbb{E}_{r}\eta^{(C,b,r)}$. We emphasize that this last step
isn’t a physical operation - it is just a mathematical mapping to define an
un-entangled state.

We raise two interesting properties about the marginals of these states: since
$\tau^{(C,x)}$ is supported on the unmeasured particles, its expectation over
measurement outcomes $r$ recovers the original reduced density matrix:
$\rho^{V\setminus C}=\mathbb{E}_{r}\tau^{(C,b,r)}$ for all $C,b$. Next,
consider the separable states $\eta_{C,b}$, resulting from fixing the set of
measured particles $C$ and the basis $b$, and averaging over the measurement
outcomes $r$. If a given particle $u\notin C$ is not measured, then its
(marginal) single particle reduced density matrix remains the same as that of
the original $\rho$:

$\eta^{C,b}_{u}=\text{Tr}_{V\setminus
u}[\eta_{C,b}]=\mathbb{E}_{r}\tau^{(C,b,r)}_{u}=\text{Tr}_{V\setminus(C\cup\\{u\\})}[\mathbb{E}_{r}\tau^{(C,b,r)}]=\text{Tr}_{V\setminus
u}[\rho]=\rho_{u}$ (18)

###  4.2 Product State Approximations on General Graphs

In this subsection, we present a simple extension to the results on product
states by [BH13] to more general interaction hyper-graphs.

######  Theorem 4.1.

Fix $d,k=O(1)$ and let $H=\sum_{e\in E}H_{e}$ be a $k$-Local Hamiltonian on
qudits, where we define $J$ to be the $k$ dimensional array of interaction
strengths $J_{u_{1}\cdots u_{k}}=\|H_{u_{1}\cdots u_{k}}\|_{\infty}$, for all
$u_{1}\cdots u_{k}\in V$. Let $\rho$ be a generic density matrix on
$n$-qubits, and pick a positive integer $l<n$. Then there exists a globally
separable state $\sigma$ such that

$\big{|}\text{Tr}[H(\rho-\sigma)]\big{|}\leq\delta_{l}\equiv
O\bigg{(}\frac{l}{n}\cdot|J|_{1}+\frac{n^{k/2}}{\sqrt{l}}\cdot\|J\|_{F}\bigg{)}$
(19)

with $\|J\|_{F}^{2}=|J|_{2}^{2}=\sum_{e}J_{e}^{2}$ and
$|J|_{1}=\sum_{e}|J_{e}|$.

We refer to the error factor $\delta_{l}$ above frequently in the analysis in
this section. It corresponds to the error to the energy of the entanglement-
breaking state $\sigma$, when the set of particles measured $C$ is of maximum
size $l$. For constant $d,k$, and if $H$ has $m$ interactions of strength
bounded by 1, then $\min_{l}\delta_{l}=O(n^{\frac{k-1}{3}}m^{\frac{2}{3}})$.
In particular, this is $O(n^{1/3}m^{2/3})$ for 2-Local Hamiltonians, or
$O(nD^{2/3})$ on $D$ regular graphs. Indeed, this shows there exists a product
state approximation to any ground state of $H$ with extensive error
$\min_{l}\delta_{l}\leq\epsilon\cdot m$ so long as
$m=\Omega(n^{k-1}/\epsilon^{3})$, providing the notion of ‘dense’ we require
for hypergraphs.

Our proof strategy follows the techniques by [BH13]. First, we reduce this
energy difference to an expression of quantum correlations between $k$
unmeasured quantum particles. By measuring these particles with a quantum
channel of low distortion, we upper bound these quantum correlations via the
classical correlations between the random variables resulting from the
measurement. In turn, we analyze these classical correlations using extensions
to the self-decoupling lemmas by [BH13].

###### Proof.

By the triangle inequality, Holder’s inequality, and Jensen’s inequality in
sequence, we upper bound the energy difference in terms of an expectation over
the choice of measured particles $C$:

$\displaystyle\big{|}\text{Tr}[H(\rho-\sigma)]\big{|}\leq\sum_{e}\|H_{e}\|_{\infty}\cdot\|\rho^{e}-\sigma^{e}\|_{1}\leq\mathbb{E}_{C}\bigg{(}\sum_{e}\|H_{e}\|_{\infty}\cdot\|\rho^{e}-\eta^{e}_{C}\|_{1}\bigg{)}$
(20)

This enables us to divide into cases on whether the summands $e=(u_{1}\cdots
u_{k})$ were measured (i.e. $\in C$). In particular, if any $u_{i}$ is in $C$,
then simply upper bound the distance by $2$.

$\displaystyle\mathbb{E}_{C}\bigg{(}\sum_{e}\|H_{e}\|_{\infty}\cdot\|\rho^{e}-\eta^{e}_{C}\|_{1}\bigg{)}=$
(21) $\displaystyle=\mathbb{E}_{C}\bigg{(}\sum_{e:e\cap
C=\emptyset}\|H_{e}\|_{\infty}\|\rho^{e}-\eta^{e}_{C}\|_{1}+\sum_{e:e\cap
C\neq\emptyset}\|H_{e}\|_{\infty}\|\rho^{e}-\eta^{e}_{C}\|_{1}\bigg{)}\leq$
(22) $\displaystyle\leq 2\cdot k\cdot
l/n\cdot|J|_{1}+\mathbb{E}_{C}\bigg{(}\sum_{e:e\cap
C=\emptyset}\|H_{e}\|_{\infty}\|\rho^{e}-\eta^{e}_{C}\|_{1}\bigg{)}$ (23)

where in the last line we use linearity of expectation, and that the
probability either $e\cap C\neq\emptyset$ is $\leq k\cdot l/n$ (union bound),
and finally $|J|_{1}\equiv\sum_{e}\|H_{e}\|_{\infty}$.

Now, let us turn our attention to the remaining term in the RHS above. Since
$e=(u_{1}\cdots u_{k})\notin C$ are not measured, we know there is a
particular structure to their states as expectations over measurement
outcomes:
$\eta_{C}^{e}=\mathbb{E}_{x=(b,r)}\bigotimes_{i}^{k}\tau^{(C,b,r)}_{u_{i}}$,
and $\rho^{e}=\mathbb{E}_{x=(b,r)}\tau^{(C,b,r)}_{u_{1}\cdots u_{k}}$. In this
setting, we can use Jensen’s inequality to extract the expectation over $x$,
followed by the Cauchy-Schwartz inequality, and then once again Jensen’s
inequality:

$\displaystyle\mathbb{E}_{C}\bigg{(}\sum_{e\cap
C=\emptyset}\|H_{e}\|_{\infty}\|\rho^{e}-\eta^{e}_{C}\|_{1}\bigg{)}\leq\mathbb{E}_{C,x}\bigg{(}\sum_{e\cap
C=\emptyset}\|H_{e}\|_{\infty}\|\tau^{(C,x)}_{e}-\bigotimes_{i}^{k}\tau^{(C,b,r)}_{u_{i}}\|_{1}\bigg{)}$
(24)
$\displaystyle\leq\bigg{(}\sum_{e}\|H_{e}\|_{\infty}^{2}\bigg{)}^{1/2}\cdot\mathbb{E}_{C,x}\bigg{(}\sum_{e\cap
C=\emptyset}\|\tau^{(C,x)}_{e}-\bigotimes_{i}^{k}\tau^{(C,b,r)}_{u_{i}}\|_{1}^{2}\bigg{)}^{1/2}$
(25) $\displaystyle\leq\|J\|_{F}\cdot\bigg{(}\mathbb{E}_{C,x}\sum_{e\cap
C=\emptyset}\|\tau^{(C,x)}_{e}-\bigotimes_{i}^{k}\tau^{(C,b,r)}_{u_{i}}\|_{1}^{2}\bigg{)}^{1/2}$
(26)

In this manner, we have reduced the problem to a question about the k-particle
quantum correlations of un-measured particles. Following the proof techniques
of [BH13], to analyze them we first consider measuring these states using the
Pauli channel $\Lambda$ described previously. In particular, we measure each
qudit with the quantum-classical channel
$\Lambda^{\prime}=\Lambda^{\otimes\log d}$. Let us denote as $p_{X_{1}\cdots
X_{n}}=(\Lambda^{\prime})^{\otimes n}(\rho)$ the classical output
distribution, where each $X_{i}$ corresponds to a basis $b\in\\{X,Y,Z\\}^{\log
d}$ and the outcomes $r\in\\{0,1\\}^{\log d}$. We observe that for any subset
$S\subset V\setminus C$ and partial information about $C$,
$x_{C}=(b_{C},r_{C})$, the distribution of measurement outcomes $x_{S}$
conditioned on $x_{C}$ is given by the measurement outcomes of
$\tau^{(C,x_{C})}_{S}$, indeed:

$p_{X_{S}}\big{|}_{X_{C}=x_{C}}=\Lambda^{\otimes S}(\tau^{(C,x_{C})}_{S})$
(27)

Now, we can use a claim by [BCGW21] on the distortion of the Pauli channel
$\Lambda$ to relate the corresponding quantum and classical correlations

######  Claim 4.1 (Claim 2, [BCGW21]).

For any integer $z\geq 1$ and any $z$ qubit Hermitian operator $Q$, we have
$\|\Lambda^{\otimes z}(Q)\|_{1}\geq 6^{-z}\|Q\|_{1}$.

We make the observation that $(\Lambda^{\prime})^{\otimes k}$ acts on $z=k\log
d$ qubits to apply the claim above and obtain

$\displaystyle\bigg{\|}\tau^{(C,x)}_{e}-\bigotimes_{i}^{k}\tau^{(C,b,r)}_{u_{i}}\bigg{\|}_{1}\leq
d^{3k}\cdot\bigg{\|}p_{X_{e}}\big{|}_{X_{C}=x}-\prod_{i\in[k]}p_{X_{u_{i}}}\big{|}_{X_{C}=x}\bigg{\|}_{1}.$
(28)

We proceed by applying Pinsker’s Inequality for multi-partite classical
distributions on the distribution $p_{x_{S}}$ to express

$\displaystyle\mathbb{E}_{C,x}\sum_{e\cap
C=\emptyset}\|\tau^{(C,x)}_{e}-\bigotimes_{i}^{k}\tau^{(C,b,r)}_{u_{i}}\|_{1}^{2}\leq
2\cdot d^{6k}\cdot\mathbb{E}_{C,x}\sum_{e\notin
C}I(X_{u_{1}}:X_{u_{2}}\cdots:X_{u_{k}}|X_{C}=x)\leq$ (29) $\displaystyle\leq
2\cdot d^{6k}\cdot n^{k}\cdot\mathbb{E}_{C}\mathbb{E}_{u_{1}\cdots u_{k}\notin
C}I(X_{u_{1}}:X_{u_{2}}\cdots:X_{u_{k}}|X_{C})$ (30)

To conclude the proof, we apply a self-decoupling lemma, which is a
generalization of Lemma 19 in [BH13] to the multi-partite case. For
conciseness, we present the proof of which in the appendix.

######  Lemma 4.1 (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\\}})$
(31)

Since each random variable $X_{u}=(b_{u},r_{u})$ is supported on a set of size
$6^{\log d}$, $I(X_{u}:X_{V\setminus\\{u\\}})\leq\log d\cdot\log 6$, and we
conclude

$\big{|}\text{Tr}[H(\rho-\sigma)]\big{|}\leq\frac{2kl}{n}\cdot|J|_{1}+\frac{6kd^{3k}\log
d}{\sqrt{l}}\cdot n^{k/2}\|J\|_{F}$ (32)

∎

###  4.3 On the Entropy of the Entanglement-Breaking Mapping

While originally applied to the context of approximating ground state
energies, the results of the previous subsection above work for any state
$\rho$ on $n$ particles, not necessarily the ground state. In particular, we
can apply Theorem 4.1 to the Gibbs state, guaranteeing that there exists a
separable state $\sigma$ that is close to the Gibbs state in energy. To
guarantee that the separable state $\sigma$ is indeed also close in free
energy, we use the variational characterization of the free energy, and a
characterization of the entropy of the entanglement breaking procedure.

######  Theorem 4.2.

Let $\rho$ be a generic density matrix on $n$ qudits. Define
$\sigma=\mathbb{E}_{C,b}\eta_{C,b}$ to be the separable state approximation to
$\rho$, as defined in Theorem 4.1. Then,

$S(\rho)\leq S(\eta_{C,b}),\text{ for all }C,b$ (33)

We approach the proof of this theorem in three parts. First, we use the chain
rule of the entropy, and the fact that conditioning never increases
information, to upper bound the entropy of $\rho$ in terms of the entropy of
the measured set $C$ and the entropy of the other vertices conditioned on $C$.
That is:

$S(\rho)=S(C)_{\rho}+\sum_{u\notin C}S(u|C,\text{ all previous }v<u)\leq
S(C)_{\rho}+\sum_{u\notin C}S(u|C)_{\rho}$ (34)

This effectively decouples the non-measured particles. Next, we argue that in
fact both of the terms that arise above are upper bounded by their counter-
parts in $\eta_{C,b}$. We do so in two lemmas:

######  Lemma 4.2.

The entropy of the measured set of particles $C$ can only increase in
$\eta_{C,b}$,

$S(C)_{\rho}\leq S(C)_{\eta_{C,b}}$ (35)

###### Proof.

Let us consider the result of the Brandao-Harrow mapping, if the original
state $\rho$ were the maximally mixed state on $C$, $\mathbb{I}/2^{|C|}$. The
result of the measurement in a fixed basis $b$, is naturally again maximally
mixed. Let the CPTP channel representing this measurement be
$\mathcal{N}_{b}$. By the data-processing inequality,

$S(\rho^{C}||\mathbb{I}/2^{|C|})\geq
S(\mathcal{N}_{b}(\rho^{C})||\mathcal{N}_{b}(\mathbb{I}/2^{|C|}))=S(\eta_{C,b}^{C}||\mathbb{I}/2^{|C|})$
(36)

Since $S(\gamma||\mathbb{I}/2^{|C|})=|C|-S(\gamma)\forall\gamma$, then we
obtain the inequality $S(C)_{\rho}\leq S(C)_{\eta_{C,b}}$. ∎

Let us now consider the conditional entropy of a particle $u$ that wasn’t
measured. This proof is based on a discussion in [BCGW21] on pseudo-density
matrix rounding, and follows from another application of a data-processing
inequality.

######  Lemma 4.3.

The conditional entropy of an un-measured particle $u\notin C$ does not
decrease in $\eta_{C,b}$, that is

$S(u|C)_{\rho}\leq S(u|C)_{\eta_{C,b}}$ (37)

###### Proof.

We have that the reduced density matrix on $C\cup\\{u\\}$ of $\eta_{C,b}$ is
the output of the CPTP map $(\mathbb{I}_{u}\otimes\mathcal{N}^{C}_{b})$ on
$\rho$, and since CPTP maps do not increase the mutual information,

$\displaystyle I(u:C)_{\rho}\geq I(u:C)_{\eta_{C,b}}\iff
S(u)_{\rho}-S(u|C)_{\rho}\geq S(u)_{\eta_{C,b}}-S(u|C)_{\eta_{C,b}}$ (38)
$\displaystyle\Rightarrow S(u|C)_{\eta_{C,b}}\geq S(u|C)_{\rho}$ (39)

where we used the fact that the reduced density matrices of the unmeasured
particles is the same $\rho^{u}=\eta_{C,b}^{u}$, and thereby have the same
entropy. ∎

With these two lemmas, we conclude as well the proof of Theorem 4.2.

###  4.4 The Existence of Free-Energy Approximations

We can now finally argue the existence of product states which approximate the
free energy. We combine the previous statements that the separable state
$\sigma$ produced by the entanglement breaking channel [BH13] approximates the
energy of the actual Gibbs state (Theorem 4.1), and has a higher entropy
(Theorem 4.2), to argue that it serves as a good approximation to the free
energy as well. We then leverage this separable state and a series of
averaging arguments to prove our main result of this section, that there
exists product states that approximate the free energy at all temperatures.

To begin, it is useful to recall the variational presentation of the free
energy:

######  Definition 4.1.

The free energy $F$ is the minimum of the following objective:

$F\equiv\min_{\rho\geq 0:\|\rho\|=1}f(\rho)\equiv\min_{\rho\geq
0:\|\rho\|=1}\text{Tr}[H\rho]-S(\rho)/\beta$ (40)

and the minimum is attained when $\rho$ is the Gibbs State, $\rho\propto
e^{-\beta H}$.

For simplicity, for now let us represent the objective above by including the
temperature term within the Hamiltonian and the free energy, that is,

$F\leftarrow\beta F\text{ and }H\leftarrow\beta H.$ (41)

What the variational characterization immediately tells us is that any state
$\sigma$ gives us an upper bound to the free energy: $F\leq
f(\sigma)\forall\sigma$. Let us now turn to the discussion on the lower bound.

######  Theorem 4.3.

Let $H$ be a $2$-Local Hamiltonian on $n$ particles. Define an integer
parameter $1\leq l\leq n$. Correspondingly, define the error parameter
$\delta_{l}$ as in Theorem 4.1. Then there exists a separable quantum-
classical state $\sigma$ whose free-energy $f(\sigma)$ satisfies

$f(\sigma)\geq F\geq f(\sigma)-\delta_{l}$ (42)

###### Proof.

If
$\rho=\operatorname*{argmin}_{\gamma}f(\gamma)=\operatorname*{argmin}_{\gamma}\text{Tr}[H\gamma]-S(\gamma)$
is the Gibbs state, then let $\sigma=\mathbb{E}_{C,b}\eta_{C,b}$ be the state
produced by applying the entanglement breaking map to the state $\rho$.
Theorem 4.1 guarantees that their energies are close, and therefore one can
lower bound the free energy via the energy of $\sigma$:

$F=\text{Tr}[H\rho]-S(\rho)=\text{Tr}[H(\rho-\sigma)]+\text{Tr}[H\sigma]-S(\rho)\geq-\delta_{l}+\text{Tr}[H\sigma]-S(\rho)$
(43)

and Theorem 4.2 ensures their entropy doesn’t decrease:
$S(\rho)\leq\mathbb{E}_{C,b}S(\eta_{C,b})$, thus

$F\geq-\delta_{l}+\text{Tr}[H\sigma]-\mathbb{E}_{C,b}[S(\eta_{C,b})]=-\delta_{l}+\mathbb{E}_{C,b}f(\eta_{C,b})$
(44)

This is, up to some additive error, on average the free energy of the states
$\eta_{C,b}$ in the ensemble $\sigma$ lower bounds the actual free energy. By
an averaging argument, there exists $C^{*}$, $b^{*}$ which is better than the
expectation, and we conclude that there exists a quantum-classical, separable
state $\eta_{C^{*},b^{*}}$ that approximates the free energy. ∎

In fact, we can actually find a single product of mixed states that
approximates the free energy. Let us consider the structure of the separable
state $\eta_{C^{*},b^{*}}$ that minimizes the expectation above.

$\eta_{C,b}=\sum_{r}p_{C,b}(r)\psi_{(b,r)}^{C}\otimes\eta^{(C,b,r)}=\sum_{r}p_{C,b}(r)\psi_{(b,r)}^{C}\bigotimes_{u\notin
C}\eta^{(C,b,r)}_{u}$ (45)

Indeed, $\eta_{C^{*},b^{*}}$ is a quantum-classical state, and an ensemble of
product states, one for each measurement outcome $r\in\\{0,1\\}^{|C|}$ of the
(now fixed) measurements in the Pauli basis $b\in\\{1,2,3\\}^{|C|}$.

We claim that the free energy of these states can be expressed through an
average over the free energy of the product states that compose it:

######  Claim 4.2.

The free energy of the states $\eta_{C,b}$ can be expressed as an average over
the free energy of product states, minus the entropy of the measured
particles:

$f(\eta_{C,b})=-S(C)_{\eta_{C,b}}+\mathbb{E}_{r}f(\psi_{(b,r)}^{C}\otimes\eta^{(C,b,r)}).$
(46)

Where the expectation $\mathbb{E}_{r}$ denotes the average over the
distribution $p_{C,b}(r)$ of measurement outcomes.

###### Proof.

The entropy of a quantum-classical state is well known, and given by

$\displaystyle
S(\eta_{C,b})=S(C)_{\eta_{C,b}}+\mathbb{E}_{r}[S(\otimes_{u\notin
C}\eta^{(C,b,r)}_{u})]$ (47)

That is, it can be directly expressed as the entropy of the measured particles
$C$, plus an average over the entropy of the quantum components, which in this
case are a product state. Since the entropy of the pure state
$\psi_{(b,r)}^{C}$ is 0, one can expand the free energy as above. ∎

We can now use this expression to prove the following theorem on the existence
of product state approximations to the free energy

######  Theorem 4.4.

Let $H$ be a $2$-Local Hamiltonian on $n$ particles. Define an integer
parameter $1\leq l\leq n$. Correspondingly, define the error parameter
$\delta_{l}$ as in Theorem 4.1. Then there exists a product state
$\sigma=\otimes_{u\in V}\sigma_{u}$ whose free-energy $f(\sigma)$ satisfies

$f(\sigma)\geq F\geq f(\sigma)-2\delta_{l}$ (48)

###### Proof.

In Theorem 4.3 we proved that the entanglement-breaking state
$\sigma=\mathbb{E}_{C,b}\eta_{C,b}$ of the Gibbs state of $H$ provides a good
approximations to the free energy on average
$\mathbb{E}_{C,b}f(\eta_{C,b})\leq F+\delta_{l}$. Let us fix our attention to
a pair $C,b$. From Claim 4.2, we know the free energy $f(\eta_{C,b})$ of
$\eta_{C,b}$ has a particular form:

$f(\eta_{C,b})=-S(C)_{\eta_{C,b}}+\mathbb{E}_{r}f(\psi_{(b,r)}^{C}\otimes\eta^{(C,b,r)}).$
(49)

Let us now apply an averaging argument, to pick a measurement outcome
$r^{*}_{C,b}$ for each pair $(C,b)$ s.t.

$\displaystyle
f(\psi_{(b,r^{*})}^{C}\otimes\eta^{(C,b,r^{*})})\leq\mathbb{E}_{r}f(\psi_{(b,r)}^{C}\otimes\eta^{(C,b,r)})\text{
and thereby }$ (50) $\displaystyle
f(\eta_{C,b})\geq-S(C)_{\eta_{C,b}}-\sum_{u\notin
C}S(\eta^{(C,b,r^{*})}_{u})+\text{Tr}[H\psi_{(b,r^{*})}^{C}\otimes\eta^{(C,b,r^{*})}]$
(51)

Let us now consider defining product states
$\gamma_{C,b}=\mathbb{I}_{C}/d^{|C|}\otimes\eta^{(C,b,r^{*})}$, that is,
replacing the states of the measured particles $C$ by a maximally mixed state,
and maintaining the states $\eta^{(C,b,r^{*})}$ picked through the averaging
argument. Our intention is to argue that the states $\gamma^{C,b}$ only
increase the energy of $\psi_{(b,r^{*})}^{C}\otimes\eta^{(C,b,r^{*})}$ by a
small amount, and don’t decrease the entropy, thereby defining an approximate
lower bound to $f(\eta_{C,b})$. We do so in two steps. First, since
$\gamma^{C,b}_{C}$ is maximally mixed, the entropy of the particles in $C$
doesn’t decrease, and the entropy of particles outside of $C$ doesn’t change

$S(C)_{\eta_{C,b}}\leq S(C)_{\gamma^{C,b}}\text{ and
}S(\gamma^{(C,b)}_{u})=S(\eta^{(C,b,r^{*})}_{u})\text{ for }u\notin C$ (52)

Finally, the energy difference between the states $\gamma_{C,b}$ and
$\psi_{(b,r^{*})}^{C}\otimes\eta^{(C,b,r^{*})}$ can be upper bounded by the
interactions with $C$. Let $J_{C}=\sum_{e\in E:e\cap C}\|H_{e}\|_{\infty}$ be
the sum of interaction strengths of edges that hit the set of measured
particles $C$. We thereby have

$\bigg{|}\text{Tr}[H\psi_{(b,r^{*})}^{C}\otimes\eta^{(C,b,r^{*})}]-\text{Tr}[H(\mathbb{I}_{C}/d^{|C|})\otimes\eta^{(C,b,r^{*})}]\bigg{|}\leq
J_{C}$ (53)

and thus $f(\eta_{C,b})\geq f(\gamma_{C,b})-J_{C}$. Note that over a uniformly
random choice of $C$ of size at most $l$,
$\mathbb{E}_{C}J_{C}=2\frac{l}{n}|J|_{1}$, as previously discussed in the
proof of Theorem 4.1. Here $J$ corresponds to the matrix of interaction
strengths, and $|J|_{1}$ is simply the sum of all interaction strengths. If we
return to the setting of Theorem 4.3, we have proved the existence of product
states $\gamma_{C,b}$ such that

$\mathbb{E}_{C,b}f(\gamma_{C,b})\leq\mathbb{E}_{C,b}f(\eta_{C,b})+2\frac{l}{n}|J|_{1}\Rightarrow\mathbb{E}_{C,b}f(\gamma_{C,b})\leq
F+\delta_{l}+2\frac{l}{n}|J|_{1}\leq F+2\delta_{l}$ (54)

by an averaging argument, we prove the theorem.

∎

##  5 The Hamiltonian Regularity Lemma

Let us begin by reviewing the cut decomposition of [FK99]. The key intuition
behind their result is the notion that dense graphs can be roughly viewed as a
sum of complete bipartite sub-graphs between subsets of vertices in the graph.
Each of these bipartite sub-graphs is essentially a ‘cut’ in the graph, hence
the name.

######  Definition 5.1.

Given two sets $S,T\subset[n]$ and a number $d\in\mathbb{R}$, the $n\times n$
cut matrix $D=$CUT$(S,T,d)$ is defined by $D_{u,v}=d\cdot\delta_{u\in
S}\delta_{v\in T}$.

######  Definition 5.2.

A ‘cut decomposition’ expresses a real matrix $J$ as the sum

$J=\sum_{k=0}^{s}D^{(k)}+W$ (55)

where each $D^{(k)}$ is a cut matrix defined on sets $R_{k},L_{k}\subset[n]$,
and of weight $d_{k}$. Such a decomposition is said to have width $s$,
coefficient length $(\sum d_{k}^{2})^{1/2}$, and error
$\|W\|_{\infty\rightarrow 1}$.

The main result of [FK99] is precisely an algorithm to efficiently find such a
decomposition:

######  Theorem 5.1 ([FK99]).

Let $J$ be an arbitrary real matrix and fix a constant $\epsilon>0$. Then
there exists a cut decomposition of width $O(\epsilon^{-2})$, coefficient
length $O(\|J\|_{F}/n)$, error at most $\epsilon n\|J\|_{F}$, and such that
$\|W\|_{F}\leq\|J\|_{F}$. Moreover, with probability $1-\delta$ said
decomposition can be found implicitly in time
$2^{\tilde{O}(\epsilon^{-2})}/\delta^{2}$, and explicitly in time
$\tilde{O}(n^{2}/\epsilon^{4})+2^{\tilde{O}(\epsilon^{-2})}/\delta^{2}$.

######  Remark 5.1.

The key point of the cut decomposition is that the number of cuts only depends
on the quality of the approximation, not the size of the graph.

Perhaps the main tool we introduce in this work is a generalization of this
result to the quantum setting. We exploit the fact that quantum density
matrices and quantum Hamiltonians can be expressed in a Pauli basis, to reduce
the problem of decomposing Hamiltonians into that of a ‘multi-colored’ cut
decomposition. For simplicity, here we discuss the case of 2-Local
Hamiltonians, on qudits of local dimension $d=2^{d^{\prime}}$ which is a power
of 2, and defer further generalizations to the appendix.

Let $H=\sum H_{e}$ be 2-local Hamiltonian defined on $n$ qudits, and define
$\mathbb{P}_{\log d}=\\{\mathbb{I},X,Y,Z\\}^{\otimes\log d}$ be the set of
Pauli operators acting on a single qudit. Any operator $h_{u,v}$ acting on the
Hilbert space of 2 qudits can be decomposed into basis of $\mathbb{P}_{\log
d}\otimes\mathbb{P}_{\log d}$:

$H_{uv}=\sum_{i,j\in[d^{2}]}h_{uv}^{ij}\sigma^{u}_{i}\otimes\sigma^{v}_{j}$
(56)

Where the $h_{uv}^{ij}$ are all real coefficients. Group the coefficients of
the interactions defined on the same Pauli matrices $i,j$ into an interaction
matrix $J^{ij}=\\{h_{uv}^{ij}\\}_{u,v}$, i.e., a matrix for each of $d^{4}$
‘colors’. We note that this essentially defines $O(d^{4})$ different weighted
adjacency matrices. Now, let us apply the regularity lemma of [FK99] on each
of the colored interaction/adjacency matrices $J^{ij}$ above. By construction,
for each pair $(i,j)$ one can express

$J^{ij}=\sum_{k=1}^{s}D^{ijk}+W^{ij}\equiv D^{ij}+W^{ij}$ (57)

Where $D^{ijk}$ are the $s$ cut matrices of the interaction $i,j\in[d^{2}]$,
defined on partitions $\\{R^{ijk},L^{ijk}\\}$ of the vertex set of the graph
for $k\in[s]$. We can thereby define the cut decomposition $H_{D}$ of the
Hamiltonian $H$ to be the edges of the $D^{ijk}$ crossing any such cut:

$\text{The Hamiltonian Cut Decomposition:
}H_{D}=\frac{1}{2}\sum_{i,j\in[d^{2}]\atop k\in[s]}\sum_{u\in R^{ijk}\atop
v\neq u,v\in
L^{ijk}}D^{ijk}_{uv}\sigma^{u}_{i}\otimes\sigma^{v}_{j}\otimes\mathbb{I}_{V\setminus\\{u,v\\}}$
(58)

where we appropriately order the tensor product such that $u<v$ and add a
factor of $1/2$ via a handshaking argument. More importantly, we filter out
the diagonal entries $D^{ijk}_{uu}$, since the cuts $S,T$ returned by the cut
decomposition in Theorem 5.1 need not be disjoint, and Local Hamiltonians
can’t have ‘self-edges’ in a basis decomposition. While unfortunately we no
longer can interpret the interaction graph of $H_{D}$ as an exact sum of
complete bipartite sub-Hamiltonians, fortunately, we will later recover this
interpretation in an approximate sense.

We dedicate the rest of this section to proving two interesting properties of
$H_{D}$. First, we argue that the energy of any product state
$\rho=\otimes_{u\in V}\rho_{u}$ is close, whether in $H$ or $H_{D}$, arising
from the combinatorial structure of the decomposition. Then, we leverage our
product state approximation toolkit from section 4, to argue that $H_{D}$ is
in fact close to $H$ in the spectral norm $\|H-H_{D}\|_{\infty}$.

######  Theorem 5.2.

Let $H=\sum_{u,v}H_{u,v}$ be a 2-Local Hamiltonian defined on qudits of local
dimension $d=2^{d^{\prime}}=O(1)$, let $J_{uv}=\|H_{uv}\|_{\infty}$ be the
matrix of interaction strengths, and let $H_{D}$ be the Hamiltonian cut
decomposition of $H$ of width $s=O(\epsilon^{-2})$. Then, for all product
states $\rho=\otimes_{u\in V}\rho_{u}$,

$|\text{Tr}[(H-H_{D})\rho]|\leq\epsilon n\|J\|_{F}$ (59)

Moreover, with probability $1-\delta$ said decomposition can be found
implicitly in time $2^{\tilde{O}(\epsilon^{-2})}/\delta^{2}$, and explicitly
in time
$\tilde{O}(n^{2}/\epsilon^{4})+2^{\tilde{O}(\epsilon^{-2})}/\delta^{2}$

###### Proof.

By restricting our attention to product states, we are able to essentially
decouple the ‘colors’ (different Pauli terms) in the Cut Decomposition.

$\displaystyle\big{|}\text{Tr}[(H-H_{D})\rho]\big{|}=\bigg{|}\sum_{u<v}\sum_{i,j}(h_{uv}^{ij}-D^{ij}_{uv})\text{Tr}[\sigma^{i}_{u}\otimes\sigma^{j}_{v}\rho]\bigg{|}=$
(60) $\displaystyle=\bigg{|}\frac{1}{2}\sum_{i,j}\sum_{u\neq
v}W^{ij}_{uv}\text{Tr}[\sigma^{i}_{u}\rho_{u}]\text{Tr}[\sigma^{j}_{v}\rho_{v}]\bigg{|}\leq\sum_{i,j}\bigg{|}\sum_{u\neq
v}W^{ij}_{uv}\text{Tr}[\sigma^{i}_{u}\rho_{u}]\text{Tr}[\sigma^{j}_{v}\rho_{v}]\bigg{|}=$
(61) $\displaystyle=\sum_{i,j}\bigg{|}\sum_{v}\bigg{(}\sum_{u:u\neq
v}W^{ij}_{uv}\text{Tr}[\sigma^{i}_{u}\rho_{u}]\bigg{)}\text{Tr}[\sigma^{j}_{v}\rho_{v}]\bigg{|}\leq\sum_{i,j}\sum_{v}\bigg{|}\sum_{u}W^{ij}_{uv}\text{Tr}[\sigma^{i}_{u}\rho_{u}]\bigg{|}+\sum_{i,j}\sum_{v}|W^{ij}_{vv}|\leq$
(62) $\displaystyle\leq\sum_{ij}\bigg{(}\|W^{ij}\|_{\infty\rightarrow
1}+n\cdot\max_{v}|W^{ij}_{vv}|\bigg{)}$ (63)

where we re-introduced the diagonal terms to obtain the $\infty\rightarrow 1$
norm. From Theorem 5.1 we can pick a width
$s=O(d^{8}\epsilon^{-2})=O(\epsilon^{-2})$ s.t. $\|W^{ij}\|_{\infty\rightarrow
1}\leq\epsilon n\|J^{ij}\|_{F}/d^{4}$. Finally, the Cauchy-Schwartz inequality
tells us the diagonal entries are bounded:
$|W^{ij}_{vv}|=|J^{ij}_{vv}-D^{ij}_{vv}|\leq\sum_{k}|d^{ijk}|\leq
s^{1/2}\cdot(\sum d_{k}^{ij})^{1/2}\leq s^{1/2}\cdot\|J^{ij}\|_{F}/n$. The
observation $\|J^{ij}\|_{F}\leq\|J\|_{F}$ and assuming $\epsilon^{-2}=o(n)$
concludes the proof. ∎

By combining the product state cut decomposition above with our results on
product state approximations in section 4, we can extend our results to
entangled states as well.

######  Lemma 5.1 (The Hamiltonian Weak Regularity Lemma).

In the context of Theorem 5.2, $\|H-H_{D}\|\leq\epsilon\cdot n\|J\|_{F}$.

###### Proof.

By Schatten norm duality, there exists a normalized state $\psi^{*}$ s.t.

$\|H-H_{D}\|_{\infty}=\max_{\psi}|\text{Tr}[(H-H_{D})\psi]|=|\text{Tr}[(H-H_{D})\psi^{*}]|$
(64)

We now apply the product state approximation Theorem 4.1 on the state
$\psi^{*}$ and Hamiltonian $H^{\prime}=H-H_{D}$, to argue there exists a
separable state $\sigma$ s.t.

$|\text{Tr}[(H-H_{D})(\psi^{*}-\sigma)]|\leq\epsilon n\|J\|_{F}/2$ (65)

where we observe that if $J^{\prime}$ is the matrix of interaction strengths
of $H^{\prime}=H-H_{D}$, then $\|J^{\prime}\|_{1}\leq n\|J^{\prime}\|_{F}$
(Cauchy-Schwartz) and
$\|J^{\prime}\|_{F}\leq\sum_{i,j\in[d^{2}]}\|W^{ij}\|_{F}\leq
O(d^{4}\|J\|_{F})$ by means of a triangle inequality and the guarantees on $W$
in Theorem 5.1. Since $\sigma$ is separable, we can appropriately pick the
width $s=O(\epsilon^{-2})$ in Theorem 5.2 to guarantee

$|\text{Tr}[(H-H_{D})\sigma]|\leq\epsilon n\|J\|_{F}/2$ (66)

and thereby via the triangle inequality:

$\|H-H_{D}\|_{\infty}\leq|\text{Tr}[(H-H_{D})(\psi^{*}-\sigma)]|+|\text{Tr}[(H-H_{D})\sigma]|\leq\epsilon
n\|J\|_{F}$ (67)

∎

Using the existing technology of matrix regularity lemmas, in the appendix we
present extensions to the result above for Local Hamiltonians defined on
hyper-graphs and for graphs of low threshold rank.

##  6 A Ground State Energy PTAS

In this section, we discuss how to use the Hamiltonian cut decomposition
(Theorem 5.2) to construct additive error approximation schemes for the ground
state energy. Our strategy will be to devise an algorithm to find the minimum
energy among product states of the cut decomposition $H_{D}$ of $H$, which by
our weak regularity result and the product state approximations in Theorems
5.2, 4.1, guarantee an additive error to the true ground state energy.
Naturally, the resulting optimization program over product states is no longer
convex, however, the low rank structure to the cut decomposition will enable
us to construct a suitable convex relaxation. Our algorithms follow the ideas
of [FK99], in establishing linear programming relaxations that give additive
approximation schemes for Max Cut.

Let $H$ be a be a $2$-Local Hamiltonian on $n$ qudits, where we assume the
local dimension $d=O(1)$ to be a power of 2 for simplicity. Let
$J_{uv}=\|H_{uv}\|_{\infty}$ be its matrix of interaction strengths. The main
result of this section is in Theorem 6.1.

######  Theorem 6.1.

Fix $\epsilon>0$. There exists an algorithm that runs in time
$2^{\tilde{O}(1/\epsilon^{2})}$ in the probe model of computation and
estimates the ground state energy of $H$ up to additive error $\epsilon
n\|J\|_{F}$ and is correct with probability $.99$. Alternatively, the estimate
can be returned in time $\text{poly}(n,1/\epsilon,\log
1/\delta)+2^{\tilde{O}(1/\epsilon^{2})}\cdot O(\log 1/\delta)$, together with
a product state $|\psi\rangle=\otimes_{u}|\psi_{u}\rangle$ s.t

$\langle\psi|H|\psi\rangle\leq\min_{\rho\geq
0,\|\rho\|_{1}=1}\text{Tr}[H\rho]+\epsilon n\|J\|_{F},$ (68)

and the energy estimate is correct with probability $1-\delta$.

The key idea in our approximation algorithm for the variational minimum energy
is to leverage the regularity lemma to relax the non-convex optimization
program over product states, to checking the feasibility of a set of
semidefinite programs. At a high level, the cut decomposition allows us to
approximately interpret (dense) local Hamiltonians as a sum of a constant
number of Hamiltonians, defined on complete bipartite graphs with uniform edge
strengths. As we restrict our attention to product states, the uniformity in
$H_{D}$ ensures that its energy becomes a function of the average
magnetization (the expectations of single qudit pauli operators) on each half
of these bipartite graphs. By constraining the average magnetizations of these
subsets of vertices to lie within a range, via linear inequality constraints,
we consequently have that any product state which is feasible for those
constraints must have energy in a fixed range. In this manner, relaxing the
non-convex optimization problem to checking the feasibility of a set of SDP’s.
Given the behavior of these constraints on single qubit observables, we coin
them the ‘subset magnetization constraints’, and dedicate section 6.1 for an
intuitive discussion on their formulation and guarantees.

Crucially, to actually make these algorithms run in constant time in the probe
model of computation, we use a common refinement technique well known in the
matrix regularity literature and presented in subsection 6.1.1. This enables
us to compress the number of variables in our sets of convex constraints,
resulting in convex programs whose size only depends on the intended accuracy.
In section 6.2 we discuss how to actually solve the resulting feasibility
problems, and combine their approximation guarantees with our existence
statements to prove Theorem 6.1.

###  6.1 The Subset Magnetization Constraints

Here, we apply the regularity lemma to construct a collection of convex sets
over the description of product states over $n$ qudits. Each such convex set
will correspond to the set of product states within a given energy range, or
in more detail, partitions of the graph will have magnetizations within a
specified range. Naturally, there will be no guarantee that each convex set is
feasible, however, by construction at least one such set will be feasible and
contain a ball of finite radius. This will later enable a linear relaxation to
the the problems of finding the best product state for the ground state
energy, or the free energy, that one can solve using Convex Programming
algorithms.

Given a density matrix $\rho=\otimes_{u\in V}\rho_{u}$ which is a tensor
product of $n$ single qudit mixed states, we express each
$\rho_{u}\in(\mathbb{C})^{d\times d}$ in a generalized Pauli basis
decomposition. That is, we describe each such $\rho$ via $(d^{2}-1)\cdot n$
real coeficients $\alpha_{i}^{v}\in\mathbb{R},i\in[d^{2}-1],v\in V$, where
$d=O(1)$ is the local dimension and

$\rho_{v}=\frac{1}{d}\mathbb{I}_{d\times
d}+\frac{1}{d}\sum_{i\in[d^{2}]-1}\alpha_{i}^{v}\sigma_{i},\alpha_{i}^{v}\equiv\text{Tr}[\sigma_{i}\rho_{v}],\rho_{v}\geq
0$ (69)

The constraint that these matrices are psd is equivalent to that of checking
if the lowest eigenvalue of $\rho_{v}$ is non-negative. Indeed, following
standard techniques in semidefinite programming we note that its lowest
eigenvector $|\psi\rangle$ provides a separating hyperplane on the variables
$\alpha$, and we can compute it in time $O(d^{3})$.

$\rho_{v}\ngeq 0\iff\exists\psi\text{ s.t.
}\langle\psi|\rho_{v}|\psi\rangle=1/d+\sum_{i\in[d^{2}-1]}\alpha_{i}^{v}\cdot\langle\psi|\sigma_{i}|\psi\rangle/d<0$
(70)

The energy of the product state $\rho$ under the Hamiltonian cut decomposition
$H_{D}$ of Theorem 5.2 can be expressed as

$\text{Tr}[H_{D}\rho]=\frac{1}{2d^{2}}\sum_{i,j\in[d^{2}]}\sum_{k\in[s]}\sum_{u\neq
v}D^{ijk}_{uv}\alpha^{u}_{i}\alpha^{v}_{j}\cdot\text{Tr}_{u,v}[(\sigma_{i}^{u}\otimes\sigma_{j}^{v})^{2}]=\frac{1}{2}\sum_{i,j\in[d^{2}]}\sum_{k\in[s]}\sum_{u\neq
v}D^{ijk}_{uv}\alpha^{u}_{i}\alpha^{v}_{j}$ (71)

In the above we abuse notation and let $\alpha_{0}^{u}=1$. Recall that the
$D^{ijk}$, $i,j\in[d^{2}],k\in[s]$ are cut matrices, where
$s=O(\epsilon^{-2})$ is the width of the decomposition. That is, $D^{ijk}$ has
a constant interaction strength of $d^{ijk}$ on the edges that cross from
$R^{ijk}$ to $L^{ijk}$. In this setting, if each side of the cut was disjoint,
$R^{ijk}\cap L^{ijk}=\emptyset$ we could re-express the energy due to the
$k$-th cut of the $i,j$ Pauli interaction as:

$\sum_{u,v}D^{ijk}_{uv}\alpha^{u}_{i}\alpha^{v}_{j}=d^{ijk}\bigg{(}\sum_{u\in
R^{ijk}}\alpha^{u}_{i}\bigg{)}\bigg{(}\sum_{v\in
L^{ijk}}\alpha^{v}_{j}\bigg{)}\equiv d^{ijk}r^{ijk}c^{ijk}$ (72)

where $r^{ijk}$ becomes the total magnetization in the $i$th ‘direction’ of
the particles in the partition $R^{ijk}\subset V$, and analogously for
$c^{ijk}$. Instead, we have to make due with the approximation (as in the
proof of Theorem 5.2)

$\bigg{|}\text{Tr}[H_{D}\rho]-\sum_{i,j,k}d^{ijk}r^{ijk}c^{ijk}\bigg{|}\leq\sum_{i,j,k}\sum_{u\in[n]}|d^{ijk}|\leq
d^{4}\cdot s^{1/2}\|J\|_{F}$ (73)

Naturally, if we knew the coefficients $\alpha^{*}$ of the best product state
$\rho^{*}$, constructing said coefficients $r^{*},c^{*}$ and the corresponding
energy would be trivial. The beauty in this method is that one can enumerate
(or guess) over the range of $r,c$, with the guarantee that there is at least
one assignment that is close to $r^{*},c^{*}$. In particular, let us note that
since each coeficient $|\alpha^{v}_{i}|\leq 1$, then
$|r^{ijk}|\leq|R^{ijk}|\leq n$. Construct the ordered set

$I_{\gamma}=\\{-\gamma ln,-\gamma(l-1)n,\cdots,0,\cdots\gamma ln\\}$ (74)

where $\gamma$ is some accuracy parameter, and $l=\lfloor\gamma^{-1}\rfloor$.
We note $|I_{\gamma}|\leq 2/\gamma+1$. Let us define the shorthand
$r=\\{r^{ijk}\\}_{ijk},c=\\{c^{ijk}\\}_{ijk}$ for the corresponding vectors of
length $d^{4}s$. For each of $|I_{\gamma}|^{2\cdot
d^{4}s}=2^{O(1/\epsilon^{2})}$ possible assignment to these vectors
$r,c\in(I_{\gamma})^{d^{4}s}$, we define the following set of constraints
$C_{r,c,\gamma}$:

$\displaystyle\rho_{\alpha_{u}}\geq 0\text{ for all particles }u\in V$ (75)
$\displaystyle r^{ijk}-\gamma n\leq\sum_{u\in R^{ijk}}\alpha^{u}_{i}\leq
r^{ijk}+\gamma n\text{ and }$ (76) $\displaystyle c^{ijk}-\gamma
n\leq\sum_{u\in L^{ijk}}\alpha^{u}_{j}\leq c^{ijk}+\gamma n\text{ for all
}i,j\in[d^{2}],k\in[s]$ (77)

Let us add a few remarks on the structure of $C_{r,c,\gamma}$. The first
constraint ensures that any feasible point must be a density matrix of a
product state. The second and third constraints enforce the magnetizations of
given subsets of vertices, to be around the ’guess’. In particular, the
application of a simple lemma by [FK99] guarantees that if $\alpha$ is a
feasible point of $C_{r,c,\gamma}$, then its energy is close to its ’guess’:

######  Lemma 6.1.

Let $\alpha=\\{\alpha^{u}_{i}\\}_{u\in V,i\in[d^{2}-1]}$ be a feasible point
to the constraints $C_{r,c,\gamma}$, where $r=\\{r^{ijk}\\}$,
$c=\\{c^{ijk}\\},i,j\in[d^{2}],k\in[s]$. Correspondingly, let
$\rho=\otimes\rho_{u},\rho_{u}=\mathbb{I}/d+\alpha^{u}\cdot\sigma^{u}/d$ be
the product state defined by $\alpha$. Then

$\bigg{|}\text{Tr}[H_{D}\rho]-\sum_{ijk}d^{ijk}r^{ijk}c^{ijk}\bigg{|}\leq
O(\gamma/\epsilon\cdot n\|J\|_{F})$ (78)

where $s=O(\epsilon^{-2})$ is the width of each cut-decomposition, and
$\gamma$ is the accuracy parameter of the constraints.

###### Proof.

We use the following lemma by [FK99]

######  Lemma 6.2 ([FK99]).

Let $J$ be a real matrix, and $D^{1}\cdots D^{s},W$ be its cut decomposition
of width $s$. Then given real numbers
$r_{i},c_{i},r^{\prime}_{i},c^{\prime}_{i}$ with
$|r_{i}|,|r_{i}^{\prime}|,|c_{i}|,|c^{\prime}_{i}|\leq n$ and
$|r_{i}-r^{\prime}_{i}|,|c_{i}-c^{\prime}_{i}|\leq\gamma n$ for each
$i\in[s]$, then $\sum_{i}d_{i}|r_{i}c_{i}-r^{\prime}_{i}c^{\prime}_{i}|\leq
8(\sum_{i}d_{i}^{2})^{1/2}\cdot n^{2}\gamma s^{1/2}$

which follows from the Cauchy-Schwartz inequality. Recall the bound of
$(\sum_{i}d_{i}^{2})^{1/2}\leq\|J\|_{F}/n$ on the coefficient length, and the
width $s=O(\epsilon^{-2})$, from Theorem 5.1. If $r^{\prime},c^{\prime}$ are
the true average magnetizations of the subsets in the cut decomposition, then

$\displaystyle\bigg{|}\text{Tr}[H_{D}\rho]-\sum_{ijk}d^{ijk}r^{ijk}c^{ijk}\bigg{|}\leq\bigg{|}\text{Tr}[H_{D}\rho]-\sum_{ijk}d^{ijk}r^{\prime
ijk}c^{\prime
ijk}\bigg{|}+\sum_{ijk}|d^{ijk}|\cdot\big{|}r^{ijk}c^{ijk}-r^{\prime
ijk}c^{\prime ijk}\bigg{|}$ (79) $\displaystyle\leq O\bigg{(}\frac{\gamma
d^{4}}{\epsilon}\cdot n\|J\|_{F}\bigg{)}$ (80)

so long as $\gamma n/\epsilon=\omega(1)$ ∎

We pick, in particular, $\gamma=O(\epsilon/s^{1/2})=O(\epsilon^{2})$, s.t. the
error in the above becomes $\epsilon n\|J\|_{F}$.

####  6.1.1 Common Refinements

The high degree of symmetry in the cut decomposed Hamiltonian $H_{D}$ presents
some key advantages. In this section, we discuss a known common refinement
technique used throughout the literature on matrix regularity lemmas [FK99,
AdlVKK02, JKM18b, GT13] that enables us to compress the set of constraints
$C_{r,c,\gamma}$ on $n$ variables into a set of constraints
$\tilde{C}_{r,c,\gamma}$ on $2^{O(s)}=2^{O(\epsilon^{-2})}$ variables.

Let us consider the partitions $\\{R^{ijk},L^{ijk}\\}_{ijk}$ defined in the
cut decomposition, and let $\mathcal{A}=\\{\mathcal{A}_{a}\\}_{a\in[A]}$ be
their common refinement (or, coarsest partition). That is, the subsets
$\mathcal{A}_{a}\subset V$ are a disjoint partition of the vertices $V$, such
that each set $R^{ijk},L^{ijk}$ is the exact union of subsets
$\mathcal{A}_{a}$. Thereby, each $v\in\mathcal{A}_{a}$ is on the same side of
every cut. We note that there are $2$ choices of a side on each of $d^{4}\cdot
s$ partitions, and thereby the number of subsets is $A=2^{d^{4}\cdot s}$. The
key observation is that each $u\in\mathcal{A}_{a}$ is indistinguishable from
the other $v\in\mathcal{A}_{a}$ within the constraints. Since the constraints
are convex, one can thereby use the same density matrix
$\rho_{a}=\frac{1}{d}\mathbb{I}+\frac{1}{d}\alpha_{a}\cdot\sigma^{a}$ for
every qudit in $\mathcal{A}_{a}$. In this manner, we define a set of
$(d^{2}-1)\cdot 2^{d^{4}\cdot s}=2^{O(\epsilon^{-2})}$ variables, and
correspondingly define the compressed set of constraints
$\tilde{C}_{r,c,\gamma}$:

$\displaystyle\rho_{\alpha_{a}}\geq 0\text{ for all }a\in[A]$ (81)
$\displaystyle r^{ijk}-\gamma n\leq\sum_{a:\mathcal{A}_{a}\subset
R^{ijk}}|\mathcal{A}_{a}|\cdot\alpha^{a}_{i}\leq r^{ijk}+\gamma n\text{ and }$
(82) $\displaystyle c^{ijk}-\gamma n\leq\sum_{a:\mathcal{A}_{a}\subset
L^{ijk}}|\mathcal{A}_{a}|\cdot\alpha^{a}_{j}\leq c^{ijk}+\gamma n\text{ for
all }i,j\in[d^{2}],k\in[s]$ (83)

To ensure that this compression is actually useful, we use a simple claim to
argue that it preserves feasibility.

######  Claim 6.1.

Fix ‘guess’ vectors $r,c$. Then $C_{r,c,\gamma}$ is feasible $\iff$
$\tilde{C}_{r,c,\gamma}$ is feasible.

###### Proof.

If $\tilde{C}_{r,c,\gamma}$ is feasible, then $C_{r,c,\gamma}$ is by
definition. The converse is slightly trickier. Let $\alpha^{u}_{i}$ be a
feasible point to $C_{r,c,\gamma}$. Let us consider grouping the vertices by
their common refinements, and average their spins. That is, we define a point
$\\{\alpha^{a}_{i}\\}_{i\in[d^{2}-1],a\in[A]}$ in the variable space of
$\tilde{C}_{r,c}$, via

$\alpha^{a}_{i}=\frac{1}{|\mathcal{A}_{a}|}\sum_{u\in\mathcal{A}_{a}}\alpha^{u}_{i}.$
(84)

This point $\\{\alpha^{a}_{i}\\}_{i\in[d^{2}-1],a\in[A]}$ clearly still
satisfies the magnetization constraints, due to symmetry. Moreover, the
resulting matrix $\rho_{\alpha_{a}}$ is psd since it is a convex combination
of psd matrices. In this manner we conclude the claim. ∎

Finally, we remark that for the purposes of devising sublinear time
algorithms, we won’t actually have access to the full description of each
partition $\mathcal{A}_{a}$. Instead, we will have to make do with knowledge
of their connectivity to other partitions, and estimates
$|\hat{\mathcal{A}}_{a}|$ of their sizes. We denote as $\hat{C}_{r,c,\gamma}$
the convex set of constraints corresponding to modifying
$\tilde{C}_{r,c,\gamma}$ above with $|\hat{\mathcal{A}}_{a}|$ instead of
$|\mathcal{A}_{a}|$. Fortunately, a simple claim argues these constraints are
robust to this sampling noise.

######  Claim 6.2.

Fix $\delta<\gamma A^{-1}/4$, and assume
$\big{|}|\hat{\mathcal{A}}_{a}|-|\mathcal{A}_{a}|\big{|}\leq\delta\cdot n$ for
all $a\in[A]$. Then,

  1. 1.

For every $n$ qudit product state $\rho=\otimes_{u}\rho_{u}$, there exists a
choice of $r,c\in(I_{\gamma})^{d^{4}\cdot s}$ such that $\rho$ is feasible for
$C_{r,c,\gamma}$, and $\hat{C}_{r,c,\gamma}$ is also feasible.

  2. 2.

$\tilde{C}_{r,c,\gamma}$ feasible $\Rightarrow\hat{C}_{r,c,2\gamma}$ feasible,
and $\hat{C}_{r,c,2\gamma}$ feasible $\Rightarrow\tilde{C}_{r,c,2\gamma}$
feasible, for all $r,c$.

###### Proof.

The proof of (1) follows from the guarantee that for every product state
$\rho$, there always exists a choice $r,c\in$ such that $\rho$ is bounded
$\gamma/2\cdot n$ away from saturating the magnetization constraints. Then,
(1) and (2) follows since the magnetization constraints are affine and
$|\alpha|_{\infty}\leq 1$, such that each magnetization is perturbed by at
most $A\cdot\delta\cdot n\leq\gamma\cdot n/4$. We note that this remains
bounded away from saturating the magnetization constraints. ∎

In this manner, given a cut decomposition, it really simply suffices to
estimate the sizes of the partitions in the decomposition to instantiate the
optimization program. In appendix B, we present a discussion on the volume of
the convex set of feasible solutions to these constraints, which later ensure
our algorithms converge efficiently. To conclude this section, let us briefly
describe the data-structure used by [FK99] to implicitly store this common
refinement. Given a single cut decomposition, they explicitly construct a
decision tree where the refinements $a\in[A]$ are the leaves, and one can
query in $\text{poly}(1/\epsilon)$ time which refinement $\mathcal{A}_{a}$
contains any vertex $v\in[n]$. For any cut $R^{ijk},L^{ijk}$, one can use this
data-structure to list all the partitions $a$ contained in each of
$R^{ijk},L^{ijk}$ in $2^{O(1/\epsilon^{2})}$ time.

###  6.2 The Algorithm

The description of our algorithm is as follows. Given a $2$-Local Hamiltonian,
we first implicitly construct the Hamiltonian cut decomposition $H_{D}$ of
Theorem 5.2. Next, using the implicit data-structure described in section 5,
we use standard sampling guarantees to ensure we estimate the sizes of the
coarsest partitions $|\hat{\mathcal{A}}_{a}|$ up to an additive error of
$\gamma/4A\cdot n$. Finally, we construct the convex programs
$\hat{C}_{r,c,\gamma}$, for each $r,c\in(I_{\gamma})^{d^{4}\cdot s}$ as
defined above, and use the convex program solver of Theorem 6.2 below to check
if each of the $2^{O(1/\epsilon^{2}\log 1/\epsilon)}$ constraints is feasible.
If $\hat{F}_{\gamma}$ are the set of pairs $(r,c)\in(I_{\gamma})^{d^{4}\cdot
s}$ such that $\hat{C}_{r,c,\gamma}$ is feasible, then we output

$\hat{V}_{\gamma}\equiv\min_{r,c\in\hat{F}_{\gamma}}\hat{V}_{r,c}\equiv\min_{r,c\in\hat{F}_{\gamma}}\sum_{i,j,k}d^{ijk}r^{ijk}c^{ijk},$
(85)

where the coefficients $d^{ijk}$ arise from the cut decomposition $H_{D}$. To
prove Theorem 6.1, we need to argue the correctness and runtime of our scheme.
We begin by arguing correctness.

It will later be relevant to prove properties on the un-perturbed constraint
set $\tilde{C}_{r,c,\gamma}$, and so in Lemma 6.3 we warm up our proof
techniques as if we had perfect knowledge of the cut decomposition and the
sizes of the coarsest partitions $\mathcal{A}_{a}$. Correspondingly, let
$F_{\gamma}$ be the set of pairs $r,c\in(I_{\gamma})^{d^{4}\cdot s}$ such that
$\tilde{C}_{r,c,\gamma}$ is feasible and analogously define the energy
estimate:

$V_{\gamma}\equiv\min_{r,c\in F_{\gamma}}V_{r,c}\equiv\min_{r,c\in
F_{\gamma}}\sum_{ijk}d^{ijk}r^{ijk}c^{ijk}.$ (86)

First, in Lemma 6.3 and Corollary 6.1 below we prove that $V_{\gamma}$ is a
close approximation to the minimum energy of the cut decomposition
$\text{Tr}[H_{D}\rho]$ among product states $\rho$. The key intuition behind
this claim stems from Lemma 6.1: If a product state $\rho$ is feasible for a
set of constraints $\tilde{C}_{r,c,\gamma}$, its actual energy must be close
to the ’guess’, which must imply $V_{\gamma}$ can’t be much smaller than the
variational minimum energy. Conversely, the minimum energy product state must
be feasible for some $C_{r,c,\gamma}$, implying $V_{\gamma}$ can’t be much
larger than the variational energy either.

######  Lemma 6.3.

$V_{\gamma}$ is an $O(\gamma/\epsilon\cdot n\|J\|_{F})$ additive approximation
to $\min_{\rho=\otimes\rho_{u}}\text{Tr}[H_{D}\rho]$

###### Proof.

We argue the two directions of the approximation inequality separately. To
begin, let the product state minimizer of the energy of $H_{D}$ be $\rho^{*}$,
that is

$\min_{\rho=\otimes\rho_{u}}\text{Tr}[H_{D}\rho]=\text{Tr}[H_{D}\rho^{*}],\big{|}\text{Tr}[H_{D}\rho^{*}]-\sum_{ijk}d^{ijk}r^{ijk}_{*}c^{ijk}_{*}\big{|}\leq
O(\|J\|_{F}/\epsilon)$ (87)

where we let $r^{ijk}_{*},c^{ijk}_{*}$ be the subset magnetizations
corresponding of $\rho^{*}$ . By construction, there is a pair
$r,c\in(I_{\gamma})^{d^{4}\cdot s}$ such that $|r^{ijk}_{*}-r^{ijk}|\leq
n\gamma/2$, and therefore $\rho^{*}$ is feasible for some $C_{r,c,\gamma}$.
Therefore, $V_{\gamma}$ must be upper bounded by the energy of
$C_{r,c,\gamma}$, which by Lemma 6.1, is close to the energy of $\rho^{*}$:

$V_{\gamma}\leq\text{Tr}[H_{D}\rho^{*}]+O(\gamma/\epsilon\cdot n\|J\|_{F})$
(88)

Conversely, let $r,c$ be the pair that defines the minimum of $V_{\gamma}$,
and via Claim 6.1 we know there exists a product state $\rho^{\prime}$
feasible for $C_{r,c,\gamma}$. Then $V_{\gamma}$ is close to the energy of
$\rho^{\prime}$ via Lemma 6.1, and the energy of $\rho^{\prime}$ must be lower
bounded by that of $\rho^{*}$

$V_{\gamma}\geq\text{Tr}[H_{D}\rho^{\prime}]-O(\gamma/\epsilon\cdot
n\|J\|_{F})\geq\text{Tr}[H_{D}\rho^{*}]-O(\gamma/\epsilon\cdot
n\cdot\|J\|_{F}).$ (89)

∎

######  Corollary 6.1.

$V_{O(\epsilon^{2})}$ is an $\epsilon n\|J\|_{F}$ additive approximation to
$\min_{\rho=\otimes\rho_{u}}\text{Tr}[H\rho]$

###### Proof.

This follows from Lemma 6.3 above with $\gamma=O(\epsilon^{2})$, and the
product state regularity in Theorem 5.2. ∎

To extend these claims to the case in which we perturb the constraints with
noisy samples of the sizes of the partitions, we use the discussion in Claim
6.2.

######  Lemma 6.4.

Fix $\delta<\gamma A^{-1}/4$, and assume
$\big{|}|\hat{\mathcal{A}}_{a}|-|\mathcal{A}_{a}|\big{|}\leq\delta\cdot n$ for
all $a\in[A]$. Then, $\hat{V}_{O(\epsilon^{2})}$ is an $\epsilon n\|J\|_{F}$
additive approximation to $\min_{\rho=\otimes\rho_{u}}\text{Tr}[H\rho]$.

###### Proof.

Once again let us address the two directions. By Claim 6.2 (1), the upper
bound on $\hat{V}_{\gamma}$ is straightforward: If $\rho^{*}$ is the minimum
energy product state of $H_{D}$, then there exists $r,c$ s.t. both
$C_{r,c,\gamma}$ and $\hat{C}_{r,c,\gamma}$ are feasible. Then,
$\hat{V}_{\gamma}\leq\text{Tr}[H_{D}\rho^{*}]+O(\gamma/\epsilon\cdot
n\|J\|_{F})$.

Conversely, if $r,c$ minimize $\hat{V}_{\gamma}$, then let $\rho_{A}$ be a
product state on $A$ qudits, feasible for $\hat{C}_{r,c,\gamma}$. We note that
by copying the product state assignment of a given partition $a\in[A]$ to all
the qudits in $\mathcal{A}_{a}$, one can naturally define a product state
$\rho$. Let $r^{\prime},c^{\prime}$ be the true average magnetizations of
$\rho$ on the subsets $\\{R^{ijk},L^{ijk}\\}$. As in the proof of Claim 6.2,

$|r^{ijk}-r^{\prime ijk}|\leq\gamma\cdot
n+\bigg{|}\sum_{a:\mathcal{A}_{a}\subset
R^{ijk}}\bigg{(}|\hat{\mathcal{A}}_{a}|-|\mathcal{A}_{a}|\bigg{)}\cdot\alpha_{i}^{a}\bigg{|}\leq(\gamma+A\cdot\delta)\cdot
n\leq 2\gamma\cdot n,$ (90)

for all $i,j\in[d^{2}],k\in[s]$. By Lemma 6.2, we conclude
$\hat{V}_{\gamma}\geq\text{Tr}[H_{D}\rho^{*}]-O(\gamma/\epsilon n\|J\|_{F})$.
∎

######  Claim 6.3.

Given an implicit description of the cut decomposition $H_{D}$ of $H$, one can
find estimates $|\hat{\mathcal{A}}_{a}|$, $a\in[A]$ for the sizes of all the
partitions in the coarsest partition of the cut decomposition in time
$2^{O(1/\epsilon^{2})}\cdot O(\gamma^{-2}\log 1/\delta)$, such that with
probability $1-\delta$

$\big{|}|\hat{\mathcal{A}}_{a}|-|\mathcal{A}_{a}|\big{|}\leq\frac{\gamma}{4A}\cdot
n\text{ for all }a\in[A]$

###### Proof.

Let us recall that the number of partitions $A=2^{O(1/\epsilon^{2})}$, and
that we can check which partition a given vertex $v$ is in, in time
$\text{poly}(1/\epsilon)$. In this setting, sample $k$ vertices uniformly at
random, and let $X^{a}_{i}$ be the indicator random variable set to 1 if
$v\in\mathcal{A}_{a}$. The estimator $\frac{n}{k}\sum_{i}^{k}X^{a}_{i}$ is
unbiased and via Hoeffding’s inequality,

$\mathbb{P}\bigg{[}\big{|}\frac{n}{k}\sum_{i}^{k}X^{a}_{i}-|\mathcal{A}_{a}|\big{|}\geq\frac{\gamma}{4A}\cdot
n\bigg{]}\leq\exp\bigg{[}-\frac{\gamma^{2}}{16A^{2}}k\bigg{]}\leq\frac{\delta}{A}$
(91)

If we pick
$k=O(\frac{A^{2}}{\gamma^{2}}\log\frac{A}{\delta})=2^{O(1/\epsilon^{2})}\cdot
O(\gamma^{-2}\log 1/\delta)$. ∎

Now that we have expressed the minimization over product states of the energy
of $H$ as checking the feasibility of $|I_{\gamma}|^{d^{4}\cdot
s}=2^{O(\epsilon^{-2}\log 1/\epsilon)}$ convex programs
$\hat{C}_{r,c,\gamma}$, we discuss how to solve them. We use a theorem by
[BV02], in the formulation of [BCGW21]:

######  Theorem 6.2 ([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$. Then, with probability $1-2^{-\Omega(m)}$ we can
compute a feasible point $x\in K$ using $\text{poly}(m,T)\cdot O(\log R/r)$
calls to the separation oracle.

In our case, we are dealing with $m=2^{O(\epsilon^{-2})}$ real variables and
$2^{O(\epsilon^{-2})}$ constraints. We can thereby compute whether a given
product state parametrized by a vector $\alpha$ is feasible for
$\hat{C}_{r,c,O(\epsilon^{-2})}$ in time $T=2^{O(\epsilon^{-2})}$. If $\alpha$
is not feasible for $\hat{C}_{r,c,O(\epsilon^{-2})}$, then it violates either
a PSD constraint or a magnetization constraint, both of which have associated
hyperplane witnesses which serve as the separation oracle. In appendix B we
prove we can choose $R=2^{O(\epsilon^{-2})}$ and $r=O(\gamma)$. Applying
Theorem 6.2, we can find the feasible set of pairs $F_{\gamma}$ in time
$2^{O(\epsilon^{-2})}$ for each pair, for a total time of
$2^{O(\epsilon^{-2}\log 1/\epsilon)}$. Once we include the runtime of
constructing the decomposition $H_{D}$ as per Theorem 5.2, and of defining the
constraints $\hat{C}_{r,c,O(\epsilon^{-2})}$ as in Claim 6.3, we arrive at our
main result in Theorem 6.1. Finally, to actually output a pure product state,
we expand our implicit solution $\rho=\otimes\rho_{u}$ into an explicit
product of $n$ qudit density matrices and use the method of conditional
expectations [Vaz03] to extract a pure state from each qudit.

##  7 The Vertex Sample Complexity of the Ground State Energy

In this section, we study the vertex sample complexity of the ground state
energy of local Hamiltonians of bounded interaction strengths. We prove that
sample of all the interactions between a constant number of particles suffices
to estimate the ground state energy up to a constant factor times $n^{2}$.
Formally, the main result of this section is

######  Theorem 7.1.

Let $H=\sum_{e}H_{e}$ be a 2-Local Hamiltonian on $n$ qudits, of local
dimension $d=O(1)$ and of bounded interaction strengths $\|H_{e}\|\leq 1$.
Pick $Q\subset[n]$ to be a uniformly random sample of
$q=\Omega(\epsilon^{-6}\log 1/\epsilon)$ of those qudits. Let $H_{Q}$ be the
sum of interactions with support contained entirely in $Q$. Then, 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\cdot
n^{2}$ (92)

Let us overview the proof of this theorem, which we detail in subsection 7.1.
In order to prove that the sampled estimate for the ground state energy is
accurate, we follow a sequence of reductions. We begin by arguing that the
ground state energy is close, up to an additive error $\epsilon\cdot n^{2}$ to
the un-entangled, minimum product state energy of the Hamiltonian using the
product state approximations of Theorem 4.1. This holds on both the original
Hamiltonian, and for the ground state and variational energies of the sampled
Hamiltonian, so long as the sample size is sufficiently large. Next, we reduce
these variational (product state) problems to their corresponding versions on
cut decomposed Hamiltonians. To do so, we rely crutially on a lemma by
[AdlVKK02] on the cut norm of random sub-matrices of a matrix of bounded cut,
to argue that the error of the restriction of the cut decomposition to the
sample $Q$ is still an accurate cut decomposition. That is, with constant
probability the energy of any product state on $q$ qubits is close, whether on
the restriction of $H$, $H_{Q}$ or the restriction of $H_{D}$, $H_{D_{Q}}$.

At this point, we have reduced the problem to that of the vertex sample
complexity of the variational minimum energy of the Hamiltonian cut
decomposition $H_{D}$. Here, we extensively leverage the machinery of the
subset magnetization constraints $C_{r,c,\gamma}$ developed in the previous
section 6.1. To proceed, we follow the proof techniques of [AdlVKK02] and
[JKR19], in studying the properties of randomized restrictions of convex
programs. We begin by arguing the easy direction: that if the set of
constraints $C_{r,c,\gamma}$ is feasible, then with constant probability, a
sample of a feasible point of $C_{r,c,\gamma}$ is approximately feasible for
the sampled constraints. Therefore, the variational minimum energy of the
sampled constraints is less than that of the original cut decomposed
Hamiltonian, with constant probability. The converse is more tricky: we use
convex programming duality to argue that if $C_{r,c,\gamma}$ is in-feasible,
then a set of lagrange multipliers acts as a witness to its in-feasibility,
and we sample from this witness to argue the in-feasibility of the sampled
constraints. This infeasibility relation implies that the variational energy
of the sample is, with constant probability, not much less than the true
variational energy of $H_{D}$.

###  7.1 Proof of Theorem 7.1

Let us begin by relating the ground state energy with variational (product
state) minimum energy of the Hamiltonian, on both the original system and the
sample. To do so, we use the asymetric extension to the product state
approximations of [BH13], presented in Theorem 4.1 and simplified here:

######  Corollary 7.1.

Given a 2-Local Hamiltonian $H=\sum_{e}H_{e}$ on $n$ qudit particles 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^{1/3}m^{2/3})$ (93)

Given a uniformly random sample of vertices $Q\subset[n]$ of size $q$, let
$H_{Q}$ be the sub-Hamiltonian of the interactions of the induced sub-graph
$G[Q]$. From the corollary and $m\leq n^{2}$ we see

$\displaystyle\min_{\text{product states
}\sigma}\text{Tr}[H\sigma]-\min_{\sigma}\text{Tr}[H\sigma]\leq n^{5/3}\text{
and }$ (94) $\displaystyle\frac{n^{2}}{q^{2}}\cdot\bigg{(}\min_{\text{product
states
}\sigma_{Q}}\text{Tr}_{Q}[H_{Q}\sigma_{Q}]-\min_{\sigma}\text{Tr}[H_{Q}\sigma_{Q}]\bigg{)}\leq
n^{2}/q^{1/3}$ (95)

Now that we have turned our attention to product states, we can use the
Hamiltonian cut decomposition of Theorem 5.2 to further simplify the
variational problem. However, we require a guarantee on how accurate the cut
decomposition is when we sample a random $Q\times Q$ sub-matrix of it.
[AdlVKK02] proved the following theorem on the cut norm of random sub matrices
of the cut decomposition

######  Theorem 7.2 ([AdlVKK02]).

Let $W$ be an $n\times n$ matrix, with bounded vector norms
$\|W\|_{\infty}=O(\epsilon^{-1}),\|W\|_{\infty\rightarrow 1}\leq\epsilon
n^{2}$, and $\|W\|_{F}\leq O(n^{2})$. 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^{2})$, $\|W_{Q}\|_{F}\leq
O(q^{2}/\sqrt{\delta})$.

We use the theorem above to prove a bound on the accuracy of the cut
decomposition on the sampled sub-graph. If $H_{D}$ is the cut decomposition of
Theorem 5.2, let $H_{D_{Q}}$ be the interactions of $H_{D}$ of support
contained entirely in $Q\subset V$.

######  Lemma 7.1.

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^{2}),$ (96)

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

###### Proof.

Consider the $O(d^{4})=O(1)$ ‘error’ matrices $W^{ij}$, for each (generalized)
Pauli matrix pair $i,j\in[d^{2}]$ resulting from the cut decomposition of the
interactions of $H_{D}$. Applying the result of Theorem 7.2 [AdlVKK02] above,
and a union bound over all $d^{4}=O(1)$ matrices, we are guaranteed that with
probability $1-\delta$, $\sum_{ij}\|W^{ij}_{Q}\|_{\infty\rightarrow 1}\leq
O(\epsilon/\sqrt{\delta}\cdot q^{2})$, so long as
$q=\Omega(\delta^{-5}\epsilon^{-4}\log 1/\epsilon)$. Moreover, we still have
$W^{ij}_{u,u}\leq O(1/\epsilon)$ as in Theorem 5.2 and the lemma follows. ∎

We emphasize that these first two steps allowed us to reduce the problem to an
analysis of sub-sampling Classical CSPs: by the triangle inequality,

$\displaystyle\bigg{|}\min_{\rho}\text{Tr}[H\rho]-\frac{n^{2}}{q^{2}}\cdot\min_{\rho_{Q}}\text{Tr}[H_{Q}\rho_{Q}]\bigg{|}\leq$
(97) $\displaystyle\leq\bigg{|}\min_{\text{product state
}\rho}\text{Tr}[H_{D}\rho]-\frac{n^{2}}{q^{2}}\cdot\min_{\text{product state
}\rho_{Q}}\text{Tr}[H_{D_{Q}}\rho_{Q}]\bigg{|}+O\big{(}\epsilon/\sqrt{\delta}\cdot
n^{2}\big{)}$ (98)

That is, now we can reason directly on the cut-decomposed Hamiltonian $H_{D}$
and its sub sample $H_{D_{Q}}$. Here we can draw from the machinery of the
subset magnetization constraints, that we developed in sections 6.1 and 6.2.
Recall the definition of the convex set of constraints $C_{r,c,\gamma}$, which
corresponded to the set of density matrices of product states with ‘subset
magnetizations’ (a linear function) within a $\gamma n$ additive range around
the constraint coefficients $r,c$. We proved that the minimum over the choices
of $r,c$ that are feasible $C_{r,c,\gamma}$ provides a good estimate to the
variational minimum energy:

$V_{\gamma}=\min_{\begin{subarray}{c}r,c\in(I_{n,\gamma})^{d^{4}\cdot s}\\\
C_{r,c,\gamma}\text{
feasible}\end{subarray}}\sum_{ijk}d^{ijk}r^{ijk}c^{ijk}\text{ and
}|V_{\gamma}-\min_{\text{product state }\rho}\text{Tr}[H_{D}\rho]|\leq
O(\gamma/\epsilon\cdot n^{2})\text{ (Lemma \ref{lemma-Vadditive1} })$ (99)

To provide an analogous bound for the sample, let us formally define its sub-
program. We let $C_{r,c,\gamma}(Q)$ be the subset magnetization constraints of
the sample $Q$, given guesses $r,c\in(I_{q,\gamma})^{d^{4}\cdot
s}\equiv(\\{-q,-q+\gamma q,-q+2\gamma q,\cdots,0,\cdots,q\\})^{d^{4}\cdot s}$
and accuracy $\gamma$:

$\displaystyle
C_{r,c,\gamma}(Q):\rho_{\alpha_{u}}=\frac{\mathbb{I}}{d}+\frac{\alpha_{u}\cdot\sigma}{d}\geq
0\text{ for all particles }u\in Q$ (100) $\displaystyle r^{ijk}-\gamma
q\leq\sum_{u\in R^{ijk}}\alpha^{u}_{i}\leq r^{ijk}+\gamma q\text{ and }$ (101)
$\displaystyle c^{ijk}-\gamma q\leq\sum_{u\in L^{ijk}}\alpha^{u}_{j}\leq
c^{ijk}+\gamma q\text{ for all }i,j\in[d^{2}],k\in[s]$ (102)

We emphasize that this is simply the corresponding set of constraints to
$H_{D_{Q}}$, the sub-Hamiltonian of the cut-decomposition. More importantly,
$C_{r,c,\gamma}(Q)$ should be viewed as the restriction of
$C_{rn/q,cn/q,\gamma}$ to $Q$, with scaled coefficients $rn/q,cn/q$. We can
similarly define an estimate for the variational minimum energy of the sample:

$V_{\gamma}(Q)=\min_{\begin{subarray}{c}r,c\in(I_{q,\gamma})^{16s}\\\
C_{r,c,\gamma}(Q)\text{
feasible}\end{subarray}}\sum_{ijk}d^{ijk}r^{ijk}c^{ijk}$ (103)

The following claim guaranteess that $V_{\gamma}(Q)$ is an accurate estimate
to the variational minimum energy of the sample.

######  Claim 7.1.

$V_{\gamma}(Q)$ is an $O(\gamma/\epsilon\cdot q^{2})$ additive approximation
to $\min_{\text{product state }\rho}\text{Tr}[H_{D_{Q}}\rho_{Q}]$.

###### Proof.

The proof follows analogously to that of Lemmas 6.1 and 6.3, where we note
that the ‘coefficient length’ of $D_{Q}$ is still the same as $D$. We
emphasize that this is independent of the sample $Q$, it just relies on the
properties of the original cut decomposition. ∎

In order to relate $V_{\gamma}(Q)$ and $V_{\gamma}$, we need to argue about
the structure of the convex constraints $C_{r,c,\gamma}$ and how they relate
to their sub-samples, $C_{r^{\prime},c^{\prime},\gamma^{\prime}}(Q)$. We note
that proving one of the directions is much easier: if the global constraints
$C_{r,c,\gamma}$ are feasible, then a sample from the coordinates of a
feasible point is likely feasible for the constraints of the sample. To
approach the converse, we follow the techniques of [AdlVKK02] and [JKM18b] for
affine constraints. We essentially need to argue that the absence of a good
solution to the original problem, implies the absence of a good solution to
the sampled problem. The approach exploits the existence of certain witnesses
to the dual convex program of the constraint set $C_{r,c,\gamma}$, whenever it
is infeasible. Let us begin by proving the easier direction:

######  Claim 7.2.

Assume $q=\Omega(\gamma^{-2}\log 1/(\delta\epsilon))$. Then with probability
$1-\delta$, if $C_{r,c,\gamma}$ is feasible, then $C_{rq/n,cq/n,2\gamma}(Q)$
is feasible as well.

###### Proof.

Consider the $r,c$ that maximizes $V_{\gamma}$, and let
$\alpha=(\alpha^{u}_{i})_{u\in V,i\in[d^{2}-1]}$ be a feasible point of
$C_{r,c,\gamma}$. For a fixed sample $Q$, consider the point
$\alpha_{Q}=(\alpha^{u}_{i})_{u\in Q,i\in[d^{2}-1]}$ defined by the
restriction of $\alpha$ to the sampled particles. We can define the
magnetizations $r_{Q}^{ijk},c_{Q}^{ijk}$ of the sample by
$r_{Q}^{ijk}=\sum_{u\in R^{ijk}\cap Q}\alpha_{u}^{i},c_{Q}^{ijk}=\sum_{u\in
L^{ijk}\cap Q}\alpha_{u}^{j}$, where in expectation
$\mathbb{E}_{Q}[r_{Q}^{ijk}]=\frac{q}{n}r^{ijk}$. By the psd constraint we
have $|\alpha_{u}^{i}|\leq 1$, so a Chernoff bound tells us that the sampled
magnetizations aren’t far from their expectation:

$\mathbb{P}[|r_{Q}^{ijk}-\frac{q}{n}\cdot r^{ijk}|\geq\gamma q]\leq\cdot
e^{-\Omega(\gamma^{2}q)}$ (104)

and by a union bound over the $d^{4}\cdot s=O(\epsilon^{-2})$ subsets
$(i,j,k)$, we have with probability $1-\delta$ that all the magnetization
estimates are accurate up to error $\gamma\cdot q$ , so long as
$q=\Omega(\gamma^{-2}\log 1/(\epsilon\delta))$. We adequate for this sampling
error by increasing the slack in the constraints: It follows that if
$C_{r,c,\gamma}$ is feasible, then with probability $1-\delta$,
$C_{rq/n,cq/n,2\gamma}(Q)$ is feasible as well.

∎

To argue the converse of the Claim 7.2 is very tricky. To do so, let us begin
by expressing the constraints $C_{r,c,\gamma}$ in a more standard SDP
formulation, which will be more convenient to write out the dual. First, WLOG
reintroduce the constraints over the trace $\text{Tr}[\rho_{u}]=1$ of the
density matrices, and generically define matrix variables $\rho_{u}\geq
0,\rho_{u}\in\mathbb{C}^{d\times d}$ parameterized by their real-valued Pauli
basis description. Next, consider each of the $2\cdot d^{4}\cdot s$
‘regularity’ constraints in $C_{r,c,\gamma}$, and observe that $p$th
constraint (indexed by the pauli matrices $i,j$ and the cut $k$) can be cast
into the matrix form $\sum\text{Tr}[A_{p,u}\rho_{\alpha_{u}}]-b_{p}\leq 0$. In
this context, $A_{p,u}\in\\{0,\pm\sigma^{u}_{i},\pm\sigma^{u}_{j}\\}$ are
Pauli matrices (including identity) or 0, and $b_{p}\in\\{\pm r^{p}+\gamma
n,\pm c^{p}+\gamma n\\}$. We express the program:

$\displaystyle\text{ minimize }0,\text{ subject to }C_{r,c,\gamma}:$ (105)
$\displaystyle\text{Tr}[\rho_{{}_{u}}]=1,\rho_{u}\geq 0\text{ for
}u\in[n]\text{ and }$ (106)
$\displaystyle\sum_{p,u}\text{Tr}[A_{p,u}\rho_{u}]-b_{p}\leq 0\text{ for each
constraint }p\in[2d^{4}s]$ (107)

We denote the optima of this program as $O_{r,c,\gamma}$, which is set to
$+\infty$ whenever $C_{r,c,\gamma}$ is infeasible. Given this set of
constraints, we can define the Lagrangian
$\mathcal{L}_{r,c,\gamma}(\rho,\lambda,\mu,Y)$, where we define the
multipliers as follows: $Y\geq 0$ are a collection of $n$ psd matrices in
$\mathbb{C}^{d\times d}$ associated to the PSD constraint on each $\rho_{u}$,
$\lambda\in\mathbb{R}_{+}^{2d^{4}s}$ are the positive valued multipliers on
the regularity constraints, and $\mu\in\mathbb{R}^{n}$ are unconstrained
variables associated to the trace constraints. We have:

$\displaystyle\mathcal{L}_{r,c,\gamma}(\rho,\lambda,\mu,Y)=-\sum_{u\in[n]}\text{Tr}[Y_{u}\rho_{u}]+\sum_{u\in[n]}\mu_{u}\bigg{(}\text{Tr}[\rho_{u}]-1\bigg{)}+\sum_{p}\lambda_{p}\bigg{(}\sum_{u}\text{Tr}[A_{p,u}\rho_{u}]-b_{p}\bigg{)}$
(108)
$\displaystyle=-\sum_{j}\lambda_{j}b_{j}-\sum_{u}\mu_{u}+\sum_{u\in[n]}\text{Tr}\bigg{[}\rho_{u}\bigg{(}\sum_{p}\lambda_{p}A_{p,u}-Y_{u}+\mu_{u}\mathbb{I}\bigg{)}\bigg{]}$
(109)

Indeed, note that
$\max_{Y,\lambda>0,\mu}\mathcal{L}_{r,c,\gamma}(\rho,\lambda,\mu,Y)=0$ if
$\rho$ is feasible for $C_{r,c,\gamma}$ by picking $Y,\lambda=0$, and can be
made $+\infty$ otherwise. One can thereby construct the Lagrangian dual
objective
$\mathcal{D}_{r,c,\gamma}(\lambda,\mu,Y)=\min_{\rho}\mathcal{L}_{r,c,\gamma}(\rho,\lambda,\mu,Y)$,
and its corresponding dual program, which we note to be equivalent to

$\displaystyle\max_{\lambda\geq
0,\mu}\mathcal{D}^{\prime}_{r,c,\gamma}(\lambda,\mu)=\max_{\lambda\geq
0,\mu}-\sum_{j}\lambda_{j}b_{j}-\sum_{u}\mu_{u}\text{ subject to }$ (110)
$\displaystyle\mu_{u}\mathbb{I}+\sum_{p}\lambda_{p}A_{p,u}\geq 0\forall
u\in[n]$ (111)

We note in that this dual is trivially feasible, with $\mu,\lambda=0$ and
objective value 0. Moreover, it is actually strictly feasible, as in
particular one can pick small $\lambda>0$ and sufficiently large $\mu>0$ such
that every PSD constraint above is strictly satisfied $>0$. In this manner,
duality of SDPs tells us that if, by assumption, the primal $C_{r,c,\gamma}$
is infeasible, then the dual must be unbounded. In particular, there must
exist a choice of $\mu,\lambda$ better than the trivial solution $(0,0)$, i.e.
bounded away from 0,

$\exists\mu,\lambda\text{ such that
}-\sum_{j}\lambda_{j}b_{j}-\sum_{u}\mu_{u}>0$ (112)

In this manner, the tuple $(\mu,\lambda)$ acts as a witness to the
infeasibility of $C_{r,c,\gamma}$. We sample from said witness to argue the
infeasibility of the randomly restricted SDP:

######  Claim 7.3.

Assume $q=\Omega(\gamma^{-2}\log 1/\delta)$. Then with probability $1-\delta$
over the choice of $Q\subset[n]$, if $C_{r,c,\gamma}$ is infeasible, then
$C_{rq/n,cq/n,\gamma/2}(Q)$ is infeasible as well

###### Proof.

To begin, we note that the PSD constraints in the dual enable a bound on the
multipliers $\mu_{u}$. For fixed $\lambda$, the feasible choice of $\mu$ which
maximizes the dual, is the minimum $\mu$ satisfying the PSD constraints (the
dual objective is negative in $\mu$). Since the minimum $\mu_{u}$ satisfying
the PSD constraints is the maximum eigenvalue of
$-\sum_{p}\lambda_{p}A_{p,u}$, $\mu_{u}$ can always be chosen to be

$\displaystyle\mu_{u}\leq\|\sum_{p}\lambda_{p}A_{p,u}\|_{\infty}\leq\sum_{p}\lambda_{p}\|A_{p,u}\|_{\infty}\leq\|\lambda\|_{1}\text{
and }$ (113)
$\displaystyle\mu_{u}\mathbb{I}\geq-\sum_{p}\lambda_{p}A_{p,u}\Rightarrow\mu_{u}\geq-\|\lambda\|_{1}$
(114)

Let us consider using $\lambda$, and the restriction of $\mu$ to $Q$ as a
witness to the dual of the sampled program $C_{rq/n,cq/n,\gamma^{\prime}}(Q)$.
We note that the constraints of the dual of $C_{rq/n,cq/n,\gamma^{\prime}}(Q)$
are the restriction to $Q\subset[n]$ of the dual constraints
$\mathcal{D}^{\prime}_{r,c,\gamma}(\lambda,\mu)$, and thereby
$(\lambda,\mu_{Q})$ is always feasible for the sampled dual. Moreover,
Hoeffding’s inequality tells us that

$\mathbb{P}\bigg{[}\bigg{|}\sum_{u\in Q}\mu_{u}-\frac{q}{n}\sum_{u\in
V}\mu_{u}\bigg{|}\geq\frac{\gamma q}{2}\cdot\|\lambda\|_{1}\bigg{]}\leq
e^{-\Omega(\gamma^{2}q)}$ (115)

and therefore, with probability $1-e^{-\Omega(\gamma^{2}q)}$,

$\displaystyle 0<-\frac{q}{n}\cdot\sum_{u\in
V}\mu_{u}(\lambda)-\frac{q}{n}\sum_{j}\lambda_{j}b_{j}\leq$ (116)
$\displaystyle\leq-\sum_{u\in
Q}\mu_{u}(\lambda)-\sum_{j}\lambda_{j}q\cdot\bigg{(}\frac{1}{n}\cdot
b_{j}-\frac{\gamma}{2}\bigg{)}\leq\cdot O_{rq/n,cq/n,\gamma/2}(Q)$ (117)

where here we use the fact that the constraint coefficients $b_{j}$ are all
additive in the error, e.g. $b_{j}=+\gamma n\pm r_{ijk}$, and therefore
subtracting from $b_{j}$ can be viewed lowering the slack in the constraint.
The last inequality is simply weak duality of the sampled program
$C_{rq/n,cq/n,\gamma/2}(Q)$. Precisely, this implies that if $C_{r,c,\gamma}$
is infeasible, with probability $1-e^{-\Omega(\gamma^{2}q)}$,
$C_{rq/n,cq/n,\gamma/2}(Q)$ is infeasible as well. We pick
$q=\Omega(\gamma^{-2}\log 1/\delta)$ to conclude the claim.

∎

We are now in position to relate the two objectives.

######  Claim 7.4.

The variational minimum energy of the cut decomposition is close to that of
its sample:

$\bigg{|}\min_{\text{product state
}\rho}\text{Tr}[H_{D}\rho]-\frac{n^{2}}{q^{2}}\cdot\min_{\text{product state
}\rho_{Q}}\text{Tr}[H_{D_{Q}}\rho_{Q}]\bigg{|}\leq O(\epsilon\cdot n^{2})$
(118)

with probability $1-\delta$ over the choice of $Q$, so long as
$q=\Omega(\epsilon^{-6}\log 1/\epsilon\delta)$

###### Proof.

By a union bound over all $2^{O(\epsilon^{-2}\log 1/\gamma)}$ possible choices
of the guesses $r,c\in(I_{\gamma})^{16s}$ (with width $s=O(\epsilon^{-2})$),
we have that the events of Claims 7.3, 7.2 hold with probability $1-\delta$,
so long as $q=\Omega(\epsilon^{-2}\gamma^{-2}\log 1/(\gamma\delta))$. In this
setting, let us first combine Claim 7.2 with Claim 7.1, to argue that the
optima of the sample provides a lower bound to the energy:

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

where the second line follows from the observation that if $\rho_{Q}$ is a
density matrix feasible for $C_{r,c,2\gamma}(Q)$, then its energy must be at
most $O(\gamma/\epsilon\cdot q^{2})$ away by Claim 7.1. Conversely,

$\displaystyle
V_{\gamma}(Q)=\min_{\begin{subarray}{c}r,c\in(I_{q,\gamma})^{16s}\\\
C_{r,c,\gamma}(Q)\text{