# Difficult instances of the counting problem for 2-quantum-SAT are very
atypical

Niel de Beaudrap
<EMAIL_ADDRESS>
CWI, Science Park 123, 1098 XG Amsterdam, Netherlands Supported by a Vidi
grant from the Netherlands Organisation for Scientific Research (NWO) and the
European Commission project QALGO.

(1 July 2014)

###### Abstract

The problem _2-quantum-satisfiability_ ($2$-QSAT) is the generalisation of the
2-cnf-sat problem to quantum bits, and is equivalent to determining whether or
not a spin-1 /2 Hamiltonian with two-body terms is frustration-free.
Similarly to the classical problem #$2$-SAT, the counting problem #$2$-QSAT of
determining the size (_i.e._ the dimension) of the set of satisfying states is
#$\mathsf{P}$-complete. However, if we consider random instances of #$2$-QSAT
in which constraints are sampled from the Haar measure, intractible instances
have measure zero. An apparent reason for this is that almost all two-qubit
constraints are entangled, which more readily give rise to long-range
constraints.

We investigate under which conditions product constraints also give rise to
efficiently solvable families of #$2$-QSAT instances. We consider #$2$-QSAT
involving only discrete distributions over tensor product operators, which
interpolates between classical #$2$-SAT and #$2$-QSAT involving arbitrary
product constraints. We find that such instances of #$2$-QSAT, defined on
Erdős–Rényi graphs or bond-percolated lattices, are asymptotically almost
surely efficiently solvable except to the extent that they are biased to
resemble monotone instances of #$2$-SAT.

##  1 Introduction

Local spin Hamiltonians are simplified models for physical systems, in which
the system is approximated by finite-range interactions between particle sites
in a fixed network. We consider problems which involve the minimum eigenvalue
of two-body Hamiltonians, $H=\sum_{\langle u,v\rangle}h_{u,v}\;,$ for
projectors $h_{u,v}$ acting on pairs of qubits (_i.e._ spin-1 /2 particles)
$u$ and $v$ drawn from some set $V$. When each $h_{u,v}$ is a projector onto
standard basis states, finding the minimum energy of $H$ is in effect
MAX-$2$-SAT, or the problem of finding an assignment to boolean variables
which satisfies as many constraints as possible, from a given list of
constraints on pairs of bits. Minimum eigenspace problems are therefore at
least $\mathsf{NP}$-hard in general, and are even $\mathsf{NP}$-hard to
approximate to within a small percentage error [15]. Even if the minimum
energy is known, determining the degeneracy (the dimension of the lowest-
energy eigenspace) is #$\mathsf{P}$-hard in general, or as difficult as
determining the number of satisfying solutions to an instance of $3$-SAT [17].
Thus, such problems should be considered to be intractable, barring major and
unexpected advances in technique.

This article concerns the conditions under which computing the degeneracy of
local Hamiltonians on spin-1 /2 particles is possible in polynomial time, as
opposed to its worst-case complexity of being #$\mathsf{P}$-hard. We make this
question more precise below.

###  1.1 Counting problems for frustration-free spin-1 /2 Hamiltonians

A special case of interest are _frustration-free_ Hamiltonians, for which
there are states $\left\lvert\psi\right\rangle$ which minimize all of the
terms $\left\langle\psi\right\rvert h_{u,v}\left\lvert\psi\right\rangle$
simultaneously. Finding ground states of such systems may still be hard, but
one may at least certify succinct descriptions of ground states, _e.g._ by
direct calculation of energy contributions from each term $h_{u,v}$. These
models are therefore a potentially useful proving ground for analytical
techniques in many-body theory. Indeed, there is a wide class of such
Hamiltonians on qubits, for which one may efficiently characterise the ground-
state manifold [5].

Bravyi [2] defines the _quantum satisfiability problem_ , or $k$-QSAT (for any
fixed $k\geqslant 1$), to be essentially the problem of determining whether a
Hamiltonian consisting of a sum of projectors, each acting non-trivially on at
most $k$ spin-1 /2 particles, is frustration-free. Bravyi shows that
$2$-QSAT is efficiently solvable; by contrast, $3$-QSAT may not have any
efficient solutions, even if it were somehow shown that
$\mathsf{P}=\mathsf{NP}$ [9].

A natural problem for frustration-free systems is to determine the
“degeneracy” of their ground-state energy levels. Given a two-body spin-1 /2
Hamiltonian $H$ as input, let #$2$-QSAT denote the problem of computing the
dimension of the subspace of states which minimizes the energy contributions
of each interaction term of $H$ independently. We refer to this dimension as
the _value_ of the instance of #$2$-QSAT. This value is positive if and only
if $H$ is frustration-free, and greater than one if $H$ is also degenerate.
The name #$2$-QSAT is chosen (see also Ref. [13]) in analogy to the problem
#$2$-SAT of counting the satisfying assignments to an instance of $2$-SAT .
The dimension of the ground-state manifold of a frustration-free spin-1 /2
Hamiltonian is simply the size of a basis for the solution space: if the
projectors $h_{u,v}$ are all diagonal operators, this problem is #$2$-SAT.
Thus #$2$-QSAT may be construed as a counting problem in the traditional
sense.

While $2$-SAT is efficiently solvable, the counting problem #$2$-SAT is
#$\mathsf{P}$-complete [17], _i.e._ polynomial-time equivalent to counting
satisfying assignments for instances of $3$-CNF-SAT. As #$2$-QSAT generalizes
#$2$-SAT, the former problem is at least as hard in the worst case. (Ji, Wei,
and Zeng [13] show that in fact
$\mbox{{{\\#}}}2\mbox{{{-QSAT}}}\in\mbox{{{\\#}}}\mathsf{P}$.) One may ask if
there are broad subfamilies of #$2$-QSAT which are considerably easier than
#$\mathsf{P}$ to compute, and if so, whether such conditions can themselves be
easily decided.

###  1.2 Entanglement and worst case vs. typical counting complexity

Though #$2$-QSAT is #$\mathsf{P}$-complete, there is a sense in which
“generic” instances of #$2$-QSAT are easily solved. Fix any graph $G$ on $n$
vertices. If we assign a qubit to each vertex, and a term
$h_{u,v}=\left\lvert\eta_{u,v}\right\rangle\mspace{-5.0mu}\left\langle\eta_{u,v}\right\rvert$
for each edge $uv\in G$, where $\left\lvert\eta_{u,v}\right\rangle$ is
distributed according to the Haar measure, the resulting #$2$-QSAT instance
can be easily solved (except with probability 0) from the structure of $G$
[14, 3]. Specifically, if the graph is a tree, the #$2$-QSAT instance has
value $n+1$; if the graph has a single cycle, it has value $2$; and if it has
two or more cycles, it has value zero (_i.e._ it is unsatisfiable, or
frustrated as a Hamiltonian).

The apparent reason for this is because a Haar-random state
$\left\lvert\eta_{u,v}\right\rangle$ is almost certainly entangled. Following
Refs. [2, 14, 5], if $h_{u,v}$ and $h_{v,w}$ project onto entangled states
$\left\lvert\eta_{u,v}\right\rangle$ and $\left\lvert\eta_{v,w}\right\rangle$,
a single-spin state on $u$ determines the feasible single-spin states at both
$v$ and $w$ similarly to an instance of classical $2$-XOR-SAT, in which the
states of each interacting pair of bits strongly restrict each other. Typical
instances of $2$-QSAT thus have effective long-range constraints between
qubits within any connected component. As a result, any graph which is dense
enough to contain multiple cycles almost certainly gives rise to an
overconstrained instance of $2$-QSAT, corresponding to a frustrated
Hamiltonian. This is in contrast to $2$-CNF-SAT formulae, which as instances
of $2$-QSAT have constraints given by standard-basis vectors
$\left\lvert\eta_{u,v}\right\rangle=\left\lvert
e_{u}\right\rangle\otimes\left\lvert e_{v}\right\rangle$ for
$e_{u},e_{v}\in\\{0,1\\}$. Such constraints on qubit-pairs $\\{u,v\\}$ and
$\\{v,w\\}$ may fail to impose any constraints between the next-nearest
neighbour qubits $u$ and $w$. This is particularly important in the monotone
special case of #$2$-SAT, which corresponds to #$2$-QSAT instances in which
$\left\lvert\eta_{u,v}\right\rangle=\left\lvert 00\right\rangle_{u,v}$ for all
edges $uv$ (corresponding to the constraint $x_{u}\vee x_{v}$ on boolean
strings $x\in\\{0,1\\}^{n}$), which is itself #$\mathsf{P}$-complete [17].

###  1.3 The typical difficulty of #$2$-QSAT with product constraints

To obtain instances of #$2$-QSAT which resist solution by polynomial-time
algorithms, there must be a substantial chance of obtaining tensor product
constraints on each edge. That this does not happen for Haar random
constraints (a natural analogue to uniformly random constraints on pairs of
bits) is a feature of quantum information theory, but does not shed much light
on the range of difficulty of #$2$-QSAT. We ask: which random graph families,
and which distributions of constraints, yield difficult instances of
#$2$-QSAT? Specifically, if only product constraints are involved, when is
#$2$-QSAT likely to be polynomial-time solvable?

We show, both for Erdős–Rényi graphs and for bond-percolated rectangular
lattices in two and three dimensions, that difficult instances of #$2$-QSAT
are rare if we select _i.i.d_. product constraints from a distribution which
differs substantially from monotone constraints. In particular, on bond-
percolated lattices, we expect the value of any #$2$-QSAT instance to be
efficiently solvable almost surely; and for Erdős–Rényi graphs, the difficult-
to-compute regime vanishes as the “monotonicity” of the constraint
distribution decreases.

We may state our results more precisely, as follows. We say that a property
which holds _asymptotically almost certainly (or surely)_ is one which holds
with probability $1-O(1/{\operatorname{poly}(n)})$. Following the usual
terminology associated with the study of random graphs, we often omit the word
“asymptotically” in connection with properties which hold almost
surely/certainly: statements about discrete distributions which are “almost”
certain or sure, are intended to be interpreted in the limit $n\to\infty$.
Considering (families of) Hamiltonians on $n$ qubits, we say that a system is
_highly disconnected_ if its connected subsystems almost surely all have size
$O(\log n)$; similarly, if it can almost surely be decomposed into subsystems
of size $O(\log n)$ which are independent of one another (despite chains of
intermediate interactions), we say that the system is _highly decoupled_. The
following Lemma follows easily from the definitions of these terms: we discuss
this in Section 2.4.

######  Lemma 1.

Instances of #$2$-QSAT which are highly disconnected, frustrated, or highly
decoupled are _easy_ (solvable in time $O(\operatorname{poly}n)$ on _e.g._ a
deterministic Turing machine).

We consider constraint models interpolating between monotone #$2$-SAT on one
hand, and continuous probability density functions of product constraints on
the other. For ${f\geqslant 1}$, let $\mathbf{q}=(q_{1},q_{2},\ldots,q_{f})$
be a distribution on $f$ distinct single-qubit states
$\left\lvert\alpha_{1}\right\rangle$, $\left\lvert\alpha_{2}\right\rangle$, …,
$\left\lvert\alpha_{f}\right\rangle$, used to generate constraints
$\left\lvert\eta_{u,v}\right\rangle=\left\lvert\alpha_{u}\right\rangle\otimes\left\lvert\alpha_{v}\right\rangle$,
where the factors are independently sampled from $\mathbf{q}$. For example,
$\mathbf{q}=(1,0,0,\ldots)$ for monotone $2$-SAT, and
$\mathbf{q}=(\tfrac{1}{2},\tfrac{1}{2},0,\ldots)$ for uniformly-random
$2$-SAT. If
$\mathbf{q}=({1\\!\\!\;/\\!\\!\>f}\>\\!,{1\\!\\!\;/\\!\\!\>f}\>\\!,\ldots,{1\\!\\!\;/\\!\\!\>f}\>\\!,0,\ldots)$,
we have $\|\mathbf{q}\|_{2}=\|\mathbf{q}\|_{\infty}={1\\!\\!\;/\\!\\!\>f}$,
which approaches $0$ as $f\to\infty$; this limiting distribution is precisely
that of single-qubit constraints chosen from the Haar measure.111As
$\mathbf{q}$ contains no information about the states
$\left\lvert\alpha_{j}\right\rangle$, we are glossing over how well-defined
the limit $\mathbf{q}\to\mathbf{0}$ is. We do not consider this here, but
propose that
$\left|\left\langle\alpha_{j}\mspace{-3.0mu}\left|\alpha_{k}\right\rangle\right.\right|\leqslant
1-\Omega(1/f)$ for all $j\neq k$ should be sufficient to maintain a promise
gap between the ground-state energy level and excited energy levels. Vector
norms of $\mathbf{q}$ thus measure how monotone the random constraints
typically are. Let $Q_{2}=1-\|\mathbf{q}\|_{2}^{2}$, and let
$Q_{\infty}=1-\|\mathbf{q}\|_{\infty}$.

######  Theorem 2 (Erdős–Rényi models).

For an Erdős–Rényi graph on $n$ vertices with $m=\gamma n$ edges, instances of
#$2$-QSAT with $\gamma<\frac{1}{2}$ are almost certainly highly disconnected,
and instances with $\gamma>\frac{1}{2Q_{2}}$ are almost certainly frustrated;
while if $2\gamma Q_{\infty}-\ln(2\gamma)>1$, frustration-free instances are
almost certainly highly decoupled.

— thus, in the $\mathbf{q}\to\mathbf{0}$ limit, a phase of typically
“difficult” problems exists only for $m/n\sim\frac{1}{2}$.

######  Theorem 3 (Bond-percolated lattice models).

Let $d\in\\{2,3\\}$, and consider a $d$-dimensional square or cubic lattice on
$n$ vertices: a segment of the rectangular grid $\mathbb{Z}\times\mathbb{Z}$
of dimensions $O(\sqrt{n})\times O(\sqrt{n})$, or of the cubic grid
$\mathbb{Z}\times\mathbb{Z}\times\mathbb{Z}$ with dimensions
$O(\sqrt[3]{n})\times O(\sqrt[3]{n})\times O(\sqrt[3]{n})$, in which edges are
present between nearest neighbours independently with some probability $p$.
Let $p_{c}$ denote the critical percolation probability, at which there
asymptotically almost surely exists a component of size $\Omega(n)$. For bond-
percolated vertices with $m$ edges, if $Q_{\infty}$ is bounded away from $0$,
there is a transition at $\frac{m}{dn}\in\Theta(n^{-1/7})$ from being almost
certainly highly disconnected and frustration-free to being almost certainly
frustrated. If we condition on frustration-free instances, we find instead
that instances for which the percolation probability is subcritical (that is
when $\frac{m}{dn}\leqslant p_{c}$) are almost certainly highly disconnected,
while instances for which $Q_{\infty}$ is greater than some constant
$p_{\text{fin}}<1$ (which depends on $d$) are almost certainly highly
decoupled.

— thus, a typical instance is almost surely solvable in polynomial-time even
for $\mathbf{q}$ which deviates from monotonicity by only a finite amount.

The above results suggest that the only difficult instances of #$2$-QSAT must
be specially constructed to resemble monotone instances of #$2$-SAT.
Specifically: (a) hard instances of #$2$-QSAT are atypical, and (b) the reason
for this does not have to do with entangled constraints, but rather that an
instance of #$2$-QSAT is only likely to be difficult if its constraints are
not very diverse and it is relatively sparsely constrained.

Structure of this article. Section 2 contains preliminary definitions and
discussion, including techniques to infer long-range constraints, to count
solutions to instances of #$2$-QSAT, and types of easily solved instances of
#$2$-QSAT. Section 3 presents the conditions under which #$2$-QSAT is easily
solvable for instances whose interaction graphs are generated according to
either the Erdős–Rényi distribution or percolated rectangular/cubic lattice
models. In Section 4 we suggest some ways in which this work might be
extended.

##  2 Preliminaries

We consider _simple graphs_ , containing no parallel edges or single-vertex
loops. We denote the state-space of a generic qubit by
$\mathcal{H}_{2}\cong\mathbb{C}^{2}$, and space of a particular qubit $u$ by
$\mathcal{H}_{u}$. For the sake of brevity we occasionally neglect error terms
which are decreasing in $n$: for instance, we write $f(n)\sim g(n)$ when
$f(n)=g(n)\bigl{[}1\pm o(1)\bigr{]}$ (which is an equivalence relation) and
$f(n)\gtrsim g(n)$ when $f(n)>g(n)\bigl{[}1\pm o(1)\bigr{]}$ (which is a
quasi-order).

While $2$-QSAT allows for a broader range of constraints, in this article we
consider only Hamiltonians $H=\sum h_{u,v}$, where $h_{u,v}$ is a rank-1
projector on $\mathbb{C}^{2}\otimes\mathbb{C}^{2}$ and the sum ranges over
pairs of vertices $\\{u,v\\}$ which are adjacent in some graph (usually a
typical graph from a given probability distribution on graphs). It should be
easy to see by extending the results below that instances of $2$-QSAT whose
constraints correspond to projectors of rank $2$ or more will only increase
the probability that the instance is efficiently solvable, by reason of the
emergence of long-range constraints on the marginals of satisfying states.

For each rank-1 projector $h_{u,v}$, we consider the state
$\left\lvert\eta_{u,v}\right\rangle\in\mathcal{H}_{u}\otimes\mathcal{H}_{v}$
such that

$h_{u,v}=\left\lvert\eta_{u,v}\right\rangle\mspace{-5.0mu}\left\langle\eta_{u,v}\right\rvert\otimes\mathbbm{1}_{V\smallsetminus\left\\{u,v\right\\}}\,.$
(1)

For $H$ frustration-free, the operator $\left\langle\eta_{u,v}\right\rvert$ is
a constraint on any ground-state $\left\lvert\psi\right\rangle$ of $H$: for
$\rho_{u,v}$ the density operator of $\left\lvert\psi\right\rangle$ on
$\left\\{u,v\right\\}$, we have
$\left\langle\eta_{u,v}\right\rvert\rho_{u,v}=0$ by hypothesis. Thus, as with
the classical decision problem $2$-SAT, we describe instances of $2$-QSAT by a
list of local “forbidden” configurations
$\left\langle\eta_{u,v}\right\rvert:\mathbb{C}^{2}\to\mathbb{C}$ on pairs of
qubits $u,v\in V$ (implicitly taking the tensor product with the identity on
all other qubits) for a global state to avoid.

###  2.1 Constraint induction

Let $\left\lvert\Psi^{-}\right\rangle\propto\left\lvert
01\right\rangle-\left\lvert 10\right\rangle$ be the singlet state. Following
Ref. [2], given constraints
$\left\langle\eta_{u,v}\right\rvert,\left\langle\eta_{v,w}\right\rvert$ for
$u\neq w$ which both act on a qubit $v\in V$, we may infer a further implicit
constraint $\left\langle\tilde{\eta}_{u,w}\right\rvert$, such that
$\left\langle\tilde{\eta}_{u,w}\right\rvert\rho_{u,w}=0$ whenever both
$\left\langle\eta_{u,v}\right\rvert\rho_{u,v}=0$ and
$\left\langle\eta_{v,w}\right\rvert\rho_{v,w}=0$ hold:

$\left\langle\tilde{\eta}_{u,w}\right\rvert\;\propto\,\Bigl{[}\left\langle\eta_{u,v}\right\rvert\otimes\left\langle\eta_{v,w}\right\rvert\Bigr{]}\Bigl{[}\mathbbm{1}_{u}\otimes\left\lvert\Psi^{-}\right\rangle\otimes\mathbbm{1}_{w}\Bigr{]}.$
(2)

We may renormalise $\left\langle\tilde{\eta}_{u,w}\right\rvert$ so that
$\left\langle\tilde{\eta}_{u,w}\mspace{-3.0mu}\left|\tilde{\eta}_{u,w}\right\rangle\right.=1$,
provided that the operator is non-zero. We may induce further implicit
constraints recursively. For two operators
$\left\langle\eta_{u,v}\right\rvert$ and $\left\langle\eta_{v,w}\right\rvert$,
we may write the operator obtained via Eqn. (2) by
$\left\langle\eta_{u,v}\right\rvert\ast\left\langle\eta_{v,w}\right\rvert$. It
is easy to show that the binary operator “$\ast$” is associative, so that

$\left\langle\eta_{u,v}\right\rvert\ast\left\langle\eta_{v,w}\right\rvert\ast\left\langle\eta_{w,x}\right\rvert\;\propto\,\Bigl{[}\left\langle\eta_{u,v}\right\rvert\otimes\left\langle\eta_{v,w}\right\rvert\otimes\left\langle\eta_{w,x}\right\rvert\Bigr{]}\Bigl{[}\mathbbm{1}_{u}\otimes\left\lvert\Psi^{-}\right\rangle\otimes\left\lvert\Psi^{-}\right\rangle\otimes\mathbbm{1}_{x}\Bigr{]},$
(3)

and so forth for longer chains, so that we may write
$\left\langle\tilde{\eta}_{u,z}\right\rvert=\left\langle\eta_{u,v}\right\rvert\ast\left\langle\eta_{v,w}\right\rvert\ast\cdots\ast\left\langle\eta_{y,z}\right\rvert$
for an operator acting on $\left\\{u,z\right\\}$ induced by a chain of
constraints from the input instance of $2$-QSAT. This is similar, in the
classical setting, to computing the transitive closure of the implication
graph defined by Aspvall, Plass, and Tarjan [1], in which case we may find
multiple constraints between a pair of variables which tightly constrain their
values. Similarly, in the more general quantum setting, we may obtain multiple
constraints
$\left\langle\smash{\eta^{(1)}_{u,v}}\right\rvert,\left\langle\smash{\eta^{(2)}_{u,v}}\right\rvert,\ldots$
which may allow us to represent their joint state-space as a two-dimensional
subspace $S\leqslant\mathcal{H}_{u}\otimes\mathcal{H}_{v}$, allowing us to
reduce the number of qubits involved in the problem by a renormalisation step
[5] without affecting the dimension of the space of satisfying states
$\left\lvert\psi\right\rangle$.

With respect to the operation “$\ast$” of induction of constraints, there are
two significantly different constraint types: product constraints
$\left\langle\eta_{u,v}\right\rvert=\left\langle\alpha_{u}\right\rvert\otimes\left\langle\beta_{v}\right\rvert$,
and entangled constraints which do not factor in this manner. It is immediate
that for
$\left\langle\tilde{\eta}_{u,w}\right\rvert=\left\langle\eta_{u,v}\right\rvert\ast\left\langle\eta_{v,w}\right\rvert$,
the constraint $\left\langle\tilde{\eta}_{u,w}\right\rvert$ is a product
constraint if either $\left\langle\eta_{u,v}\right\rvert$ or
$\left\langle\eta_{v,w}\right\rvert$ is; and that
$\left\langle\tilde{\eta}_{u,w}\right\rvert=0$ only if both
$\left\langle\eta_{u,v}\right\rvert=\left\langle\alpha_{i}\right\rvert\otimes\left\langle\alpha_{j}\right\rvert$
and
$\left\langle\eta_{v,w}\right\rvert=\left\langle\alpha_{k}\right\rvert\otimes\left\langle\alpha_{\ell}\right\rvert$
satisfy
$\left\lvert\alpha_{j}\right\rangle\propto\left\lvert\alpha_{k}\right\rangle$.
When this occurs, the marginal state of $u$ cannot indirectly constrain the
marginal on $w$, or vice-versa, through the interaction with $v$: by setting
$v$ to the state $\left\lvert\bar{\alpha}_{j}\right\rangle$ in the kernel of
$\left\langle\alpha_{j}\right\rvert$, we extend any marginal on $\\{u,w\\}$ to
one on $\\{u,v,w\\}$ which satisfies the constraints
$\left\langle\eta_{u,v}\right\rvert$ and $\left\langle\eta_{v,w}\right\rvert$.

###  2.2 Randomly generated instances of #$2$-QSAT

A “random instance” of #$2$-QSAT is a sample from a probability distribution
over instances of #$2$-QSAT, generally with a fixed number $n$ of qubits and
$m$ of constraints. We consider a generation process in which one first
generates a random graph, either by selecting a fixed number $m$ of edges from
the set of all possible pairs of edges (the _Erdős–Rényi graph model_), or by
considering a subgraph of some lattice in which each lattice-edge is included
with a probability $p$ such that the expected number of edges is $m$,
associating a qubit to each vertex of the graph. At each edge $uv$ in the
random graph, we assign an operator
$\left\langle\eta_{u,v}\right\rvert:\mathbb{C}^{4}\to\mathbb{C}$ according to
some probability distribution, representing two-body constraints on the
qubits.

We would like to also consider instances of #$2$-QSAT which are guaranteed to
have a non-zero value, corresponding to a distribution on two-body
frustration-free Hamiltonians. This requires a subtler random generation
procedure. For a model of random graphs (_e.g._ either an Erdős–Rényi model or
a percolated lattice model), we select a random order for the edge-set of the
graph. Adding these edges sequentially to graph, we assign a constraint to
each, restricting the choice of constraint so that the resulting instance of
$2$-QSAT is satisfiable. In any continuous distribution (such as the Haar
measure), any non-trivial restriction of the constraint model typically will
be to a set of measure zero; the notion of restriction we intend is limit as
$\varepsilon\to 0$, of the Haar measure conditioned on being within an
$\varepsilon$-neighbourhood (in the Euclidean norm on $\mathbb{C}^{4}$) of the
valid choices of constraint. (For instance, if only a finite set of
constraints avoid making the instance unsatisfiable, such a restriction yields
the uniform distribution over those constraints.) For the Haar measure, as
well as for the product-constraint model of our article, there is always a
choice of constraint for which the instance is satisfiable at each step: this
is easy to show in the Haar random case by a minor extension of Ref. [14], and
can be established for the constraint model of this article without difficulty
(see _e.g._ the beginning of Section 3).

###  2.3 Remarks on the counting complexity of instances of #$2$-QSAT

Given a randomly generated instance of #$2$-QSAT, we ask: with what
probability is it a “difficult” instance? Our notion of “difficulty” is
defined relative to some fixed algorithm $A$: a family of instances for which
$A$ can successfully compute the answer in polynomial time are “easy”, and
families for which $A$ has no such upper bound are “difficult”. Such
statements depend on the state of the art in combinatorics: an improved
analysis of random graphs may show that some family of formerly “difficult”
instances happen to be solvable by $A$ in polynomial time. If one accepts
standard complexity-theoretic assumptions such as $\mathsf{P}\neq\mathsf{NP}$,
there are families of instances of $2$-QSAT which are inherently “easy” or
“difficult” for any algorithm implemented _e.g._ on Turing machines. The aim
of this article is to establish bounds on the extent of any such “difficult”
regime for certain distributions on #$2$-QSAT.

An instance of $2$-QSAT is _monotone_ if there is a state
$\left\lvert\alpha_{0}\right\rangle\in\mathbb{C}^{2}$ such that
$\left\langle\eta_{u,v}\right\rvert=\left\langle\alpha_{0}\right\rvert\otimes\left\langle\alpha_{0}\right\rvert$
for each $uv\in E(G)$. This is equivalent to there being a local unitary
operator $U$ such that $\left\langle\eta_{u,v}\right\rvert(U\otimes
U)=\left\langle 00\right\rvert$ for all $uv\in E(G)$: the classical monotone
instances of #$2$-SAT are a special case in which we may take $U$ to be the
identity. As monotone #$2$-SAT is #$\mathsf{P}$-complete [17], it follows that
#$2$-QSAT is at least #$\mathsf{P}$-hard. Ji, Wei, and Zeng [13] show that
#$2$-QSAT is also contained in #$\mathsf{P}$, by a simple transformation of
instances of #$2$-QSAT which preserves the solution space and puts the
interaction graph into a standard form.

Even monotone instances of #$2$-QSAT may have structural properties which may
render it “easy”. For instance, instances whose interaction graphs $G$ have
bounded _tree-width_ [16] (see Ref. [6] for an introductory reference) may be
solved in $\operatorname{poly}(n)$ time,222The approach here, for instances
having tree-width at most $w>0$, is essentially to use dynamic programming to
count the partially-satisfying solutions for each of $2^{w}$ possible
assignments (in some local basis) for each qubit indexed by a vertex in a
tree-decomposition. A more complete description can be found in [8]. albeit
with a constant factor which grows exponentially with the tree-width [8]. This
algorithm is useful in particular for tree graphs or connected graphs which
have a single cycle, which respectively have tree-width $1$ and $2$.
Conversely, instances of #$2$-SAT which are not monotone may still be
“difficult”: for a fixed graph $G$, if we assign a uniformly random clause to
each $uv\in E(G)$, represented in the format of constraint operators for an
instance of #$2$-QSAT as one of the operators
$\left\langle\eta_{u,v}\right\rvert\in\bigl{\\{}\left\langle
00\right\rvert,\left\langle 01\right\rvert,\left\langle
10\right\rvert,\left\langle 11\right\rvert\bigr{\\}}$ then the non-trivial
constraints arising between pairs of bits by the induction procedure of Eqn.
(2) only extend over paths of expected length $O(1)$ in $G$. Then only for
sets of nodes where the constraints are relatively dense can there be a chance
of giving rise to long-range constraints of order the size of a given
connected component: this is necessary to impose enough structure to obtain an
instance of #$2$-SAT substantially different in complexity from a monotone
instance on $n^{O(1)}$ variables.

###  2.4 Three types of easily solved cases of #$2$-QSAT

We now remark on the simple observations presented in Lemma 1: this will allow
us to reduce the task of proving that instances of #$2$-QSAT are easy, to
showing that they fall into one of three structural classes of Hamiltonian —
_frustrated_ , _highly disconnected_ , or _highly decoupled_ , in the senses
described preceding Lemma 1.

Following Chvatal and Reed [4] concerning phase transitions in the
satisfiability of random instances of $2$-CNF-SAT, one may obtain results
concerning random classical #$2$-SAT on Erdős–Rényi graphs with $n$ vertices
and $m$ clauses. Specifically, an instance of $2$-SAT with density
$\frac{m}{n}>1$ is almost certainly unsatisfiable, and so by definition has
value zero as an instance of #$2$-SAT; and this can be determined in
polynomial time by detecting certain unsatisfiable substructures. Similar
remarks apply for _frustrated_ instances of #$2$-QSAT: if one can efficiently
determine that it is frustrated, this suffices to show that it has value zero.

As for easily solvable instances of #$2$-SAT with positive values, if
$\frac{m}{n}<\tfrac{1}{2}$, the underlying graph is almost certainly composed
of components of size $O(\log n)$ having at most one cycle. One can solve each
such component in polynomial time using brute-force techniques (testing all
possible assignments for each component); using dynamic programming and taking
advantage of the existence of a tree decomposition for the component, one can
even solve them in time linear in the component size (up to a logarithmic
factor due to handling vertex labels for a graph of size $n$). These represent
a _disconnected_ regime in random #$2$-SAT; and again, similar techniques
apply for #$2$-QSAT if we can establish that the components scale as $O(\log
n)$, and/or have treewidth bounded by a constant as we have described above.
It then suffices to multiply the #$2$-QSAT values for each component together:
for random graph models (such as the ones we consider) where small components
dominate, this may be done efficiently, _e.g._ using an algorithm which we
describe in Appendix A.

Finally, we may consider _highly decoupled_ instances, in which a subsystem
which is contiguous nevertheless decomposes into independent subsystems of
size $O(\log n)$. These may arise in instances which have been constructed to
be frustration-free, due to the proliferation of qubits whose states are
“fixed” by their constraints. When a qubit $x$ can only occupy a unique state
in a satisfying state, we refer to this as the _fixed state_ of the qubit $x$
(which we denote $\left\lvert\bar{\psi}_{x}\right\rangle$). As we add
constraints to a satisfiable instance of $2$-QSAT, there are at least two ways
in which an added constraint can increase the number of qubits with fixed
states:

  1. (i)

either by adding a constraint $\left\langle\eta_{x,y}\right\rvert$ between
some qubit $x$, and a qubit $y$ which already has a fixed state such that
$\left\langle\eta_{x,y}\right\rvert{\bigl{(}\mathbbm{1}_{x}\otimes\left\lvert\smash{\bar{\psi}_{y}}\right\rangle\bigr{)}}\neq\mathbf{0}^{\dagger}$,

  2. (ii)

or by adding a constraint which closes a chain of constraints starting and
ending at $x$, which is only satisfiable by a single state
$\left\lvert\bar{\psi}_{x}\right\rangle$.

Any constraint $\left\langle\eta_{x,y}\right\rvert$ acting on a qubit $x$ with
a fixed state will either be satisfied by
$\left\lvert\bar{\psi}_{x}\right\rangle$ regardless of the state of $y$, or
will serve to fix the state of $y$. Thus, interactions between qubits with
fixed states with _non_ -fixed qubits will, by construction, fail to give rise
to any long-range constraints between qubits without fixed states. If there
are enough qubits with fixed states, these may then effectively partition the
set of _non_ -fixed qubits into independent subsystems; if these subsystems
are of size $O(\log n)$, the system is then _highly decoupled_. Thus, to solve
an instance of #$2$-QSAT, it also suffices to identify enough fixed qubits to
partition the remainder into systems whose degeneracy may be efficiently
computed.

Our result is to show how in two different random graph models, for random
instances of $2$-QSAT with enough diversity in the constraints to differ
substantially from monotone instances, there is (at most) a narrow range in
which the density of constraints may give rise to instances which are neither
highly disconnected, nor frustrated, nor highly decoupled almost surely.

##  3 Discrete probabilistic models

We consider a constraint model of _independent factor distributions_ , in
which constraints are product operators
$\left\langle\alpha\right\rvert\otimes\left\langle\beta\right\rvert$ for some
_i.i.d_. single-qubit operators
$\left\langle\alpha\right\rvert,\left\langle\beta\right\rvert:{\mathbb{C}^{2}\to\mathbb{C}}$
distributed over some set of operators
$\left\\{\left\langle\alpha_{1}\right\rvert,\left\langle\alpha_{2}\right\rvert,\ldots,\left\langle\alpha_{f}\right\rvert\right\\}$
for some $f\geqslant 1$, where
$\left\langle\alpha_{j}\right\rvert\not\propto\left\langle\alpha_{k}\right\rvert$
for $j\neq k$. Given an edge which represents a product constraint, the
probability of obtaining
$\left\langle\eta_{u,v}\right\rvert=\left\langle\alpha_{h}\right\rvert_{u}\otimes\left\langle\alpha_{j}\right\rvert_{v}$
is given by $q_{h}q_{j}$, where
$\mathbf{q}\;=\;(q_{1},\,q_{2},\,\ldots,\,q_{f})$ is a fixed probability
distribution. Throughout the following, we suppose that $1>q_{1}\geqslant
q_{2}\geqslant\cdots\geqslant q_{f}>0$, so that there is some probability of
obtaining non-monotone instances of $2$-QSAT.

Independent factor distributions have convenient features for analysis.
Following Ref. [13], the ground-state manifold for an instance of $2$-QSAT
having only product constraints has a basis consisting of product states.
Furthermore, non-zero induced constraints
${\left\langle\eta_{u,v}\right\rvert\ast\left\langle\eta_{v,w}\right\rvert}$
range over the same two-qubit operators as the individual edge-constraints
themselves (albeit with a different probability distribution than
$\mathbf{q}\otimes\mathbf{q}$). As with Haar-random models, when we wish to
consider only random _frustration-free_ Hamiltonians, we must specially select
the constraints to meet that restriction. We construct the random graph in the
same manner as described in Section 2.2, this time restricting the choice of
constraints according to the condition of not giving rise to a frustrated
(_i.e._ an unsatisfiable) instance of $2$-QSAT. Frustration can only arise if
both qubits on which the constraint are each restricted to some “fixed” state
to satisfy the earlier constraints placed on it: a “non-frustrating” choice of
constraint can then be made simply by having it be satisfied by one of the two
fixed states.

We may consider how likely long-range constraints (as described in Section
2.1) are for such a constraint model. Let $x_{0},x_{\ell}\in V(G)$ be two
vertices connected by a path $P=x_{0}x_{1}\cdots x_{\ell}$ in the interaction
graph of a random instance of #$2$-QSAT. We may consider what constraints may
exist on the joint state of $x_{0}$ and $x_{\ell}$ by virtue of the inducted
constraint
$\mathcal{C}_{P}=\left\langle\eta_{x_{0},x_{1}}\right\rvert\ast\left\langle\eta_{x_{1},x_{2}}\right\rvert\ast\cdots\ast\left\langle\eta_{x_{\ell\text{--}1},x_{\ell}}\right\rvert$.
One may show by induction that $\mathcal{C}_{P}$ is non-zero if and only if
$\left\langle\eta_{x_{h\text{--}1},x_{h}}\right\rvert\ast\left\langle\eta_{x_{h},x_{h+1}}\right\rvert\neq
0$ for each index $0<h<\ell$ of internal vertices of the path. For each such
$h$, we have
$\left\langle\eta_{x_{h\text{--}1},x_{h}}\right\rvert\ast\left\langle\eta_{x_{h},x_{h+1}}\right\rvert=0$
if and only if
$\left\langle\eta_{x_{h\text{--}1},x_{h}}\right\rvert=\left\langle\alpha_{i}\right\rvert\otimes\left\langle\alpha_{j}\right\rvert$
and
$\left\langle\eta_{x_{h\text{--}1},x_{h}}\right\rvert=\left\langle\alpha_{k}\right\rvert\otimes\left\langle\alpha_{\ell}\right\rvert$
for some $j\neq k$. Because the right-factor of
$\left\langle\eta_{x_{h\text{--}1},x_{h}}\right\rvert$ and the left-factor of
$\left\langle\eta_{x_{h},x_{h+1}}\right\rvert$ are independently distributed,
this occurs with probability

$Q_{2}\;:=\;1-\|\mathbf{q}\|_{2}^{2}\;=\;\sum_{j=1}^{f}q_{j}(1-q_{j})\;\leqslant\;1-\frac{1}{f}\,,$
(4)

with equality if and only if $\mathbf{q}$ is uniform. Note that $Q_{2}>0$,
where the lower bound is the infimum as $\mathbf{q}\to(1,0,0,\ldots)$. As the
probabilities of having identical factors at each vertex are independent, we
then have

$\Pr\Bigl{[}\mathcal{C}_{P}\neq
0\Bigr{]}\;=\;\prod_{h=1}^{\ell-1}\left(1-\|\mathbf{q}\|_{2}^{2}\right)\;=\;Q_{2}^{\ell-1}\,.$
(5)

Thus, $\mathcal{C}_{P}$ is non-zero and proportional to
$\left\langle\alpha_{h}\right\rvert\otimes\left\langle\alpha_{j}\right\rvert$
with probability $q_{h}q_{j}Q_{2}^{\ell-1}$ for each ${1\leqslant h,j\leqslant
f}$, and equal to zero with probability $1-Q_{2}^{\ell-1}$. Because the long-
range constraints which involve a particular vertex as a _mid-point_ are not
independent of one another, it may be useful in some cases to bound this
probability from below by $Q_{\infty}^{\ell-1}$, where
$Q_{\infty}=1-\|\mathbf{q}\|_{\infty}$, where $\|\mathbf{q}\|_{\infty}=q_{1}$
is an upper bound on the probability that the single-qubit operators
$\left\langle\alpha_{j}\right\rvert,\left\langle\alpha_{k}\right\rvert$ with
which two different constraints act on $x$ are the same.

###  3.1 Erdős–Rényi interaction graphs

The attenuation of the probability of long-range constraints described in Eqn.
(5) is similar to what occurs in uniformly random $2$-SAT. For Erdős–Rényi
interaction graphs on $n$ vertices and $m$ edges — a distribution on labelled
graphs which may be sampled by listing each of the $\binom{n}{2}$ potential
edges in a random order, and selecting the first $m$ edges for inclusion —
this motivates an analysis which follows closely to that of Chvatal and Reed
[4], adapting it for counting problems and to involve more general constraint
distributions. We show that, except for a “difficult phase” in the regime
$\frac{1}{2}\leqslant\frac{m}{n}\leqslant\frac{1}{2Q_{2}}$, a random instance
of #$2$-QSAT is almost certainly either highly disconnected or frustrated,
according to whether $\frac{m}{n}$ is below or above the boundaries of the
difficult phase. In particular, the difficult phase shrinks to a band of zero
width at $\frac{m}{n}\sim\frac{1}{2}$ as $Q_{2}\to 1$. In the special case of
frustration-free instances, this band expands to
$\frac{1}{2}\leqslant\frac{m}{n}\leqslant\frac{1}{2Q_{\infty}}(1+\delta)$ for
some small $\delta$ which vanishes as $Q_{\infty}\to 1$; this band also
converges to $\frac{m}{n}\sim\frac{1}{2}$ as $Q_{\infty}\to 1$. Thus in the
“completely non-monotonic” limit $\mathbf{q}\to\mathbf{0}$, #$2$-QSAT is
always easy; and there is a substantial band of instances which may be
difficult to solve only if the constraint distribution shows a corresponding
bias towards a small, finite number of constraints.

####  3.1.1 The highly disconnected phase in Erdős–Rényi models

Whether or not we restrict to frustration-free instances of $2$-QSAT, the
existence of a highly disconnected regime in instances of $2$-QSAT on
Erdős–Rényi graphs $G$ follows directly from the random graph model itself.
For $\frac{m}{n}<\frac{1}{2}$, almost certainly $G$ contains only components
of size $O(\log n)$, and almost certainly contains no components having more
than one cycle [7]. Any instance of $2$-QSAT on such a graph will thus be
highly disconnected, regardless of the constraint distribution. For our
results on Erdős–Rényi models, it thus suffices to establish upper bounds on
the extent of any difficult phase.

####  3.1.2 The frustrated phase in unconditional Erdős–Rényi models

For a random graph with $m\in\Omega(n)$ edges, we adapt the analysis of
Chvatal and Reed [4, Theorem 4] to consider the probability that the giant
component $\Gamma$ contains a “frustrated figure eight” (corresponding to a
“snake” in Ref. [4]): a subsystem $X$ such that

  1. (i)

Its interaction graph contains a _figure eight graph_ , which we define as a
pair of cycles $X_{1}=x_{0}x_{1}\cdots x_{\ell-1}x_{\ell}$ and
$X_{2}=x_{\ell}x_{\ell+1}\cdots x_{2\ell-1}x_{2\ell}$ of the same length,
where $x_{0}=x_{\ell}=x_{2\ell}$, and where $X_{1}$ and $X_{2}$ intersect only
at the vertex $x_{0}=x_{\ell}$. (See Fig. 1 for an example.) There may be
additional edges connecting vertex-pairs $x_{j}x_{k}$ (though these will
typically be unlikely), and $X=X_{1}\cup X_{2}$ may be connected to other
vertices.

  2. (ii)

For each ${0\leqslant j<2\ell}$, the constraints
$\left\langle\eta_{x_{j}\\!\\!\>,\>\\!x_{j+1}}\right\rvert=\left\langle\beta_{j}\right\rvert\otimes\left\langle\gamma_{j}\right\rvert$
satisfy
$\left\langle\gamma_{j}\right\rvert\neq\left\langle\beta_{j+1}\right\rvert$.

  3. (iii)

We have
$\bigl{\\{}\left\langle\beta_{0}\right\rvert,\left\langle\gamma_{\ell-1}\right\rvert\bigr{\\}}\cap\bigl{\\{}\left\langle\beta_{\ell}\right\rvert,\left\langle\gamma_{2\ell-1}\right\rvert\bigr{\\}}=\varnothing$,
so that the constraints imposed by $X_{1}$ and $X_{2}$ on their common spin
$x_{0}$ are not simultaneously satisfiable.

Figure 1: Example of a “figure eight” graph on ${2\ell-1}$ vertices, for
$\ell=8$. By Eqn. (7), the probability of such a graph describing a frustrated
figure-eight subsystem scales as $O\bigl{(}Q_{2}^{2\ell}\bigr{)}$.

${x_{0}=x_{\ell}\,}$${\,=x_{2\ell}}$$x_{1}$$\cdots$$\ldots$$x_{\ell-1}$$x_{\ell+1}$$\cdots$$\ldots$$x_{2\ell-1}$$X_{1}$$X_{2}$

The cycles $X_{1}$ and $X_{2}$ are either “alternating loops” or “quasi-
alternating loops” in the terminology of Ref. [13], and impose constraints on
$x_{0}$ is which cannot be simultaneously satisfied. Thus a frustrated figure
eight is unsatisfiable by construction. We consider the probability of a
_large_ frustrated figure-eight arising in a random instance of $2$-QSAT with
constraints given by an independent factor distribution, which in particular
implies that it is part of the largest contiguous subsystem of the
Hamiltonian.

In a system with a figure-eight subgraph, the probability of
$\left\langle\gamma_{j-1}\right\rvert\neq\left\langle\beta_{j}\right\rvert$ is
simply $Q_{2}$ for each of the $2\ell-2$ sites $x_{j}$ of the two cycles,
excluding the shared vertex $x_{0}=x_{\ell}=x_{2\ell}$ . The conditions at the
node $x_{\ell}$, where we require
$\left\langle\beta_{0}\right\rvert=\left\langle\gamma_{\ell-1}\right\rvert\neq\left\langle\beta_{\ell}\right\rvert=\left\langle\gamma_{2\ell-1}\right\rvert$,
occur with a probability $Q_{\text{crux}}$ which also depends only on
$\mathbf{q}$. (By a routine calculation, one may show that

$\displaystyle Q_{\text{crux}}$
$\displaystyle=\;\sum_{h}q_{h}\biggl{(}\biggl{[}q_{h}\\!\sum_{j,k\neq
h}\\!\\!q_{j}q_{k}\biggr{]}+\biggl{[}\,\sum_{i\neq
h}\,q_{i}\\!\\!\\!\\!\sum_{j,k\notin\\{h,i\\}}\\!\\!\\!q_{j}q_{k}\biggr{]}\biggr{)}$
(6)
$\displaystyle=1-4\|\mathbf{q}\|_{2}^{2}+2\|\mathbf{q}\|_{2}^{4}+4\|\mathbf{q}\|_{3}^{3}-3\|\mathbf{q}\|_{4}^{4}\;.$

Then $Q_{\text{crux}}\to 1$ as $\mathbf{q}\to\mathbf{0}$, and
$Q_{\text{crux}}\in\Theta(1)$ for $\|\mathbf{q}\|_{\infty}$ bounded away from
$1$.) Given a fixed figure-eight graph $X$ on $2\ell-1$ vertices, the
probability that it gives rise to a _frustrated_ figure-eight system is then

$\displaystyle\Pr\Bigl{[}X\text{ a frustrated subsystem}\Bigr{]}\;=$
$\displaystyle\;Q_{2}^{2\ell-2}Q_{\text{crux}}.$ (7)

Let $m=\gamma n$ for some constant $\gamma>0$. Using a second moment
probabilistic argument, adapting the proof of Ref. [4, Theorem 4], we show
that the largest contiguous subsystem almost certainly contains a frustrated
figure eight so long as $\gamma>\frac{1}{2Q_{2}}$.

Let $\varphi_{\ell}$ denote the number of frustrated figure eight subsystems
in $G$ on $2\ell-1$ vertices. The mean
$\operatorname*{\mathbb{E}}(\varphi_{\ell})$ over all random graphs on $n$
vertices and $m$ edges can be evaluated by considering all sets $S$ of
$2\ell-1$ vertices, and summing the probability of $S$ being such figure eight
subsystem for all such subsets. We will make use of the equality

$\frac{n!}{(n-t)!}\;\sim\;n^{t}\exp\bigl{(}-\alpha(n,t)\bigr{)},\qquad\text{where
}~{}\alpha(n,t):=t+(n-t+\tfrac{1}{2})\ln\\!\left(\\!1-\frac{t}{n}\right)$ (8)

which holds for $t\in o(n)$,333This may be easily recovered using Stirling’s
approximation.  ignoring a relative error term of $O(\tfrac{1}{n})$ using the
notation defined at the beginning of Section 2. By considering (i) the number
of ways that we may choose the common vertex, (ii) the number of
distinguishable ways that we may construct two cycles on $\ell$ vertices
(built in either order) which incorporate the common node, (iii) the number of
ways of allocating the remaining edges after having built $X$, and (iv) the
probability that $X$ is a frustrated figure eight given that it is present in
the random graph, we may obtain

$\begin{aligned}
\operatorname*{\mathbb{E}}(\varphi_{\ell})\,&=\,Q_{2}^{2\ell-2}Q_{\text{crux}}\,\cdot\frac{n}{2}\left[\tfrac{1}{2}\binom{n-1}{\ell-1}(\ell-1)!\right]\left[\tfrac{1}{2}\binom{n-\ell}{\ell-1}(\ell-1)!\right]\left[\frac{\displaystyle\binom{\binom{n}{2}-2\ell+1}{m-2\ell+1}}{\displaystyle\binom{\binom{n}{2}}{m}}\right]\\\
&\sim\,\frac{Q_{\text{crux}}}{8Q_{2}}\left(\frac{2Q_{2}m}{n}\right)^{\\!2\ell-1}\frac{\exp\Bigl{(}-\alpha\bigl{(}n,2\ell-1\bigr{)}+\alpha\bigl{(}\tbinom{n}{2},2\ell-1\bigr{)}\Bigr{)}}{\exp\Bigl{(}\alpha\bigl{(}m,2\ell-1\bigr{)}\Bigr{)}}\;.\end{aligned}$
(9)

For $\ell\in o(n^{1/2})$, we have $\alpha(n,2\ell-1)\in o(1)$; then we can
easily show that $\varphi_{\ell}>0$ with non-zero probability, provided that
$m={\tfrac{1}{2Q_{2}}\bigl{(}1+\Omega(\tfrac{1}{\ell})\bigr{)}n}$.

Next, we show that $\varphi_{\ell}$ almost surely doesn’t differ substantially
from its mean. Define a random variable $\varphi_{X}\in\left\\{0,1\right\\}$
such that $\varphi_{X}=1$ for instances of $2$-QSAT whose constraint subgraph
contains a frustrated figure-eight on a given subgraph $X$. We compare
$\operatorname*{\mathbb{E}}(\varphi_{X})^{2}$ against
$\operatorname*{\mathbb{E}}(\varphi_{X}\varphi_{Y})$, where
$X=x_{0}x_{1}\cdots x_{2\ell-1}x_{0}$ and $Y=y_{0}y_{1}\cdots
y_{2\ell-1}y_{0}$ are both figure-eight graphs on $2\ell-1$ vertices, but
which may have vertices and edges in common. By definition, we have
$\operatorname*{Var}(\varphi_{\ell})=\operatorname*{\mathbb{E}}(\varphi_{\ell}^{2})-\operatorname*{\mathbb{E}}(\varphi_{\ell})^{2}$.
We have

$\displaystyle\operatorname*{\mathbb{E}}(\varphi_{\ell})\;$
$\displaystyle=\;\sum_{X}\Pr\bigl{[}\varphi_{X}=1\bigr{]},$
$\displaystyle\operatorname*{\mathbb{E}}(\varphi_{\ell}^{2})\;$
$\displaystyle=\;\sum_{X,Y}\Pr\bigl{[}\varphi_{X}\varphi_{Y}=1\bigr{]},$ (10)

where we sum over all possible figure-eight subgraphs $X,Y$ on $2\ell-1$
vertices selected from $n$ vertices. We show that
$\operatorname*{\mathbb{E}}(\varphi_{\ell}^{2})\sim\operatorname*{\mathbb{E}}(\varphi_{\ell})^{2}$,
which implies that $\operatorname*{Var}(\varphi_{\ell})\in
o\bigl{(}\operatorname*{\mathbb{E}}(\varphi_{\ell})^{2}\bigr{)}$.

Consider the probability that a given subgraph $g$ on $t$ edges occurs as a
subgraph of $G$. Accounting for how we can distribute $t$ edges among the
first $m$ elements of a random sequence of edges, we have

$\displaystyle f(t)\;:=\;\Pr\bigl{[}g\subseteq G\bigr{]}$
$\displaystyle=\;\binom{m}{t}\;\\!t!\left[\frac{\bigl{(}\binom{n}{2}-t\bigr{)}!}{\binom{n}{2}!}\right]$
(11)
$\displaystyle\sim\;\left(\frac{2\gamma}{n}\right)^{\\!t}\exp\Bigl{(}\alpha\bigl{(}\tbinom{n}{2},t\bigr{)}-\alpha(\gamma
n,t)\Bigr{)}\;.$

We suppose that $\ell\in o(n^{1/2})$, so that
$f(2\ell+\delta(\ell))\;\sim\;(2\gamma/n)^{\\!2\ell+\delta(\ell)}$ for
$\delta(\ell)\in\pm O(\ell)$, again using ${\mathrm{e}}^{\alpha(N,t)}\sim 1$
for $t\in o(N^{1/2})$. For figure-eight subgraphs $X,Y$ on $2\ell-1$ vertices
each, write $\Phi(X,Y):={\Pr\bigl{[}\varphi_{X}\varphi_{Y}=1\,\big{|}\,X\cup
Y\subseteq G\bigr{]}}$ for the probability of the frustration conditions on
$X\cup Y$. Then if $\bigl{\lvert}E(X)\cap E(Y)\bigr{\rvert}=i$,

$\Pr\Bigl{[}\varphi_{X}\varphi_{Y}=1\Bigr{]}\;=\;\Pr\Bigl{[}X\cup Y\subseteq
G\Bigr{]}\Phi(X,Y)\;=\;f(4\ell-i)\Phi(X,Y).$ (12)

For $X$ fixed, define $\Phi_{i}(X)$ to be the sum of
${\Pr\bigl{[}\varphi_{X}\varphi_{Y}=1\bigr{]}}$ over all figure-eight
subgraphs $Y$ of the same size, for which $\left\lvert E(X)\cap
E(Y)\right\rvert=i$ as above (_i.e._ the probability of obtaining two
frustrated figure-eight subsystems which intersect in this way, one of which
is $X$). The probability of having any pair of isomorphic frustrated figure
eight subgraphs, of which one is $X$, is then given by
$\Phi(X):=\sum_{i}\Phi_{i}(X)$.

We may show that for a fixed $X$, the contribution of $\Phi_{0}(X)$ is the
only significant contribution to $\Phi(X)$. Note that if none of the edges of
$X$ and $Y$ overlap, the frustration conditions for $X$ and for $Y$ are
completely independent, even if $X$ and $Y$ share vertices: that is,
$\Phi(X,Y)=\bigl{[}Q_{2}^{2\ell-2}Q_{\text{crux}}\bigr{]}^{2}$ in this case.
We can then upper bound $\Phi_{0}(X)$ roughly by removing the restriction on
$Y$ that $X\wedge Y$ have no edges.

Let $F_{2\ell-1}$ denote the number of possible frustrated figure eight graphs
on $2\ell-1$ vertices selected from $n$ vertices: then
$\displaystyle\Phi_{0}(X)$
$\displaystyle<\;\sum_{Y}f(4\ell)\Phi(X,Y)\;\sim\;F_{2\ell-1}\left(2\gamma\>\\!\big{/}\;\\!\\!n\right)^{\\!4\ell}Q_{2}^{4\ell-4}Q_{\text{crux}}^{2}.$
(13a) For all other $0<i\leqslant 2\ell$, we consider the number $N(i,j)$ of
figure-eight subgraphs $Y$ on $2\ell-1$ vertices, for which ${X\wedge Y}$ has
$i$ edges and $j$ vertices, and consider an upper bound $\Phi(i,j)$ for the
frustration probabilities $\Phi(X,Y)$ for all such subgraphs $Y$. Then we have
$\Phi_{i}(X)\;\leqslant\;\sum_{j}N(i,j)f(4\ell-i)\Phi(i,j)$ (13b) for $i>0$.
We bound the parameters $\Phi(i,j)$ and $N(i,j)$ by considering bounds on the
frustration conditions holding at each site in ${X\cup Y}$, and by considering
how the number of components in ${X\wedge Y}$ affects both $N(i,j)$ and the
probability of all the local frustration conditions holding.

Local frustration conditions. If $X$ and $Y$ intersect at all, the
probabilities of the frustration conditions holding for any shared vertex only
differs from what it would be independently for $X$ and for $Y$ if they also
share edges. For instance, if $x_{j}=y_{k}$ for
$j,k\notin\left\\{0,\ell,2\ell\right\\}$, and $e_{x,j},e_{x,j+1}\notin E(Y)$,
then the frustration conditions for $X$ and for $Y$ at $x_{j}$ are independent
of one another and obtain with probability $Q_{2}^{2}$, as if $x_{j}$ and
$y_{k}$ were actually distinct vertices. Similarly, if $x_{j}=y_{k}$ for
$j,k\notin\left\\{0,\ell,2\ell\right\\}$, and $e_{x,j},e_{x,j+1}\in E(Y)$,
then the frustration conditions are identical and they obtain with probability
$Q_{2}$. The most interesting cases are for the “crux” vertices $x_{\ell}$ and
$y_{\ell}$, and for the “junction” vertices of degree $3$ in $X\cup Y$ arising
from $x_{j}=y_{k}$ for $j,k\notin\left\\{0,\ell,2\ell\right\\}$.

  * •

Vertices in $X\cup Y$ of degree $3$ correspond to vertices $x_{j}=y_{k}$ for
$j,k\notin\left\\{0,\ell,2\ell\right\\}$, where one of the edges $e_{x,j}$ or
$e_{x,j+1}$ is equal to one of the edges $e_{y,k}$ or $e_{y,k+1}$. To satisfy
the frustration conditions, the common edge of $X$ and $Y$ which is adjacent
to $x_{j}$ must act on $x_{j}$ differently from the remaining two edges, but
the other two edges may act on $x_{j}$ in either distinct or identical ways to
each other. Routine calculation shows that the probability of this occurring
is $Q_{\text{junct}}:=\|\mathbf{q}\|_{2}^{2}-\|\mathbf{q}\|_{3}^{3}$.

  * •

The probability that the frustration conditions for $X$ holds at $x_{\ell}$,
when $x_{\ell}=y_{k}$ for some $0<k<2\ell$, may be somewhat complicated if
some of the edges of $Y$ incident to $y_{k}$ overlap some of the edges
$\left\\{e_{x,1},e_{x,\ell},e_{x,\ell+1},e_{x,2\ell}\right\\}$ incident to
$x_{\ell}$. Similar remarks apply to the other crux vertex $y_{\ell}$. As
there are at most two crux vertices in $X\cup Y$, we may ultimately subsume
the probability that these conditions hold at $x_{\ell}$ or at $y_{\ell}$ as a
constant factor, and simply bound the probability from above by $1$.

Vertex types and simultaneous frustration. The probability of $X$ and $Y$ both
being frustrated depends on the number of junction vertices, crux vertices,
and other vertices in $X\cup Y$, which are closely related to the number of
components. Extending the observation made with respect to the probability of
frustration conditions holding at the crux vertices, we adopt an approach of
avoiding case analysis, by sweeping various scalar factors under the rug when
they depend only on a constant number of vertices. To do so, we define a
scalar factor $c$ (which we do not explicitly calculate) to bound from above
any contributions by constant factors in the various cases.

In most cases, the components of $X\wedge Y$ (if it is non-empty) will consist
of paths, and possibly one non-path tree component in the case that
$x_{\ell}=y_{\ell}$ (with at least three of the edges of $X$ and $Y$
overlapping at that vertex). In rare cases, $X\wedge Y$ may have a component
which contains an entire cycle, or indeed two cycles if $X=Y$. In the typical
case where $X\wedge Y$ is cycle-free, the number of components will be the
difference $j-i$; Otherwise, $X\wedge Y$ has one or two cycles, so that it has
$j-i+1$ or $j-i+2$ components. In any case, the number of components is
$j-i+O(1)$. We may then make the following remarks concerning vertices of
different types:

  * •

As we note above, $X\cup Y$ has at most $O(1)$ distinct crux vertices, for
which frustration conditions occur with constant probability regardless of the
number of edges of $X$ and $Y$ which overlap at those vertices.

  * •

The number of junction vertices is minimized when each component of $X\wedge
Y$ is a path segment, with each component having two junction vertices at its
endpoints; the largest number of junction vertices a component may have is
four, in the case that the the two crux vertices coincide so that one
component of $X\wedge Y$ has four leaf nodes. (Three junction nodes are
possible as well if the two crux nodes coincide, but where only three of the
edges of $X$ and of $Y$ coincide.) Thus the number of junction vertices is
$2(j-i)+O(1)$ in all cases.

  * •

The frustration conditions elsewhere are governed by edge-pairs meeting at
some vertex, where either both edges are common to $X$ and $Y$ or both belong
to one figure-eight graph $X$ and $Y$ (the same one), but not to both.
Considering the edges $x_{0}x_{1}$, $x_{1}x_{2}$, _etc._ in sequence and
pairing each with the one that follows it, we may count these edge-pairs by
considering those edges $x_{j}x_{j+1}$ for which $x_{j+1}$ is not a junction
or crux vertex. The number of edges in $X$ which meet at non-junction, non-
crux vertices is $2\ell-2(j-i)-O(1)$, and similarly for $Y$; and the number of
such edges in $X\wedge Y$ is $i-2(j-i)-O(1)$, yielding a total of
$4\ell-2(j-i)-i\pm O(1)$.

Thus for $0<i<2\ell$ we have
$\Phi(X,Y)\;\leqslant\;c\;\\!Q_{2}^{4\ell-i}\left(\frac{Q_{\text{junct}}}{Q_{2}}\right)^{\\!2(j-i)}$
(14a) for some constant $c$ depending only on the probability distribution
$\mathbf{q}$ of constraint probabilities. For $i=2\ell$, we have $X=Y$ and
$j=2\ell-1$: then following Eqn. (7) we may explicitly evaluate
$\mspace{-10.0mu}\begin{aligned}
\Phi(X,X)\,&=\,\Pr\bigl{[}\varphi_{\\!\\!\>X}=1\,\big{|}\,X\subseteq
G\bigr{]}\,=\,Q_{\text{crux}}Q_{2}^{2\ell-2}.\end{aligned}\mspace{-10.0mu}$
(14b)

Ways to overlap at $i$ edges. Following the analysis of Ref. [4], we may bound
$N(i,j)$ by considering upper bounds on (i) the number of ways a fixed shape
for the graph $X\wedge Y$ could be mapped injectively into $X$ and into $Y$,
(ii) the number of ways that the components of $X\wedge Y$ could be arranged
into the vertex-order of $Y$, and (iii) the number vertices which may belong
to $Y\smallsetminus(X\wedge Y)$.

The number of subgraphs $Y$ such that $X\wedge Y$ has $i$ edges and $j$
vertices can then be bounded by $\displaystyle N_{\ell}(i,j)$
$\displaystyle<\;4\binom{2\ell+2}{2j-2i+2}^{\\!2}\ell\;\\!(j-i)!\;\\!2^{j-i}\;\\!n^{2\ell-j-1}$
(15a)
$\displaystyle\leqslant\;4\ell(2\ell+2)^{4(j-i)+4}\;\\!2^{j-i}\;\\!n^{2\ell-j-1}$
in the case $0<i<\ell$, and $\displaystyle N_{\ell}(i,j)$
$\displaystyle<\;4\binom{2\ell+2}{2j-2i+2}^{\\!2}\ell\;\\!(j-i)!\;\\!2^{j-i+1}\;\\!n^{2\ell-j-1}$
(15b)
$\displaystyle\leqslant\;8\ell(2\ell+2)^{4(j-i)+4}\;\\!2^{j-i}\;\\!n^{2\ell-j-1}$
for $0<i<2\ell$ more generally. If for the sake of brevity we define
$\Lambda={2(2\ell+2)^{4}/n}$, we then have
$N_{\ell}(i,j)\leqslant\begin{cases}2\ell\Lambda^{j-i+1}n^{2\ell-i}&\text{if
$0<i<\ell$},\\\ 4\ell\Lambda^{j-i+1}n^{2\ell-i}&\text{if $\ell\leqslant
i<2\ell$}.\end{cases}$ (15c)

Again, we have $X=Y$ if $i=2\ell$, so that $N_{\ell}(2\ell,j)=1$.

Suppose that $\ell\in o(n^{1/4})$, so that $\Lambda\in o(1)$. We may then use
the above remarks to bound $\Phi_{i}(X)$ for $i>0$. For ${0<i<\ell}$, the
graph $X\wedge Y$ has no cycles, so that ${i+1\leqslant j\leqslant 2\ell-1}$;

we may then bound $\displaystyle\mspace{-6.0mu}\Phi_{i}(X)\;$
$\displaystyle\leqslant\sum_{j=i+1}^{2\ell-1}\\!N(i,j)\Phi(i,j)f(4\ell-i)$
$\displaystyle<\sum_{j=i+1}^{2\ell-1}\Biggl{[}2\ell\Lambda^{j-i+1}n^{2\ell-i}\Biggr{]}\left[cQ_{2}^{4\ell-i}\left(\frac{Q_{\text{junct}}}{Q_{2}}\right)^{\\!\\!2(j-i)}\right]\left(2\gamma\>\\!\big{/}\;\\!\\!n\right)^{\\!4\ell-i}$
$\displaystyle=\,2c\ell\Lambda
n^{2\ell-i}Q_{2}^{4\ell-i}\left(2\gamma\>\\!\big{/}\;\\!\\!n\right)^{\\!4\ell-i}\sum_{j=i+1}^{2\ell-1}\left(\frac{\Lambda
Q_{\text{junct}}^{2}}{Q_{2}^{2}}\right)^{\\!\\!j-i}$
$\displaystyle<\,2c\ell\Lambda n^{-2\ell}\left(2\gamma
Q_{2}\right)^{\\!4\ell-i}\left(\frac{\Lambda
Q_{\text{junct}}^{2}}{Q_{2}^{2}}\right)\left(\frac{1}{1-{\Lambda
Q_{\text{junct}}^{2}Q_{2}^{-2}}}\right)$
$\displaystyle\sim\,\left(\frac{2cQ_{\text{junct}}^{2}}{Q_{2}^{2}}\right)\ell\Lambda^{2}n^{-2\ell}\left(2\gamma
Q_{2}\right)^{\\!4\ell-i}.$ (16a) For ${\ell<i<2\ell}$, we may only bound
${i\leqslant j\leqslant 2\ell-1}$, and for $i=2\ell$ we have
${j=2\ell-1}={i-1}$; we may then obtain similar bounds
$\displaystyle\mspace{-12.0mu}\Phi_{i}(X)\;$
$\displaystyle\lesssim\;4c\ell\Lambda n^{-2\ell}\left(2\gamma
Q_{2}\right)^{\\!4\ell-i}$ for $\ell\leqslant i<2\ell$, (16b)
$\displaystyle\mspace{-12.0mu}\Phi_{2\ell}(X)\;$
$\displaystyle\sim\;Q_{\text{crux}}Q_{2}^{-2}n^{-2\ell}\left(2\gamma
Q_{2}\right)^{\\!2\ell}\\!\\!\\!$ for $i=2\ell$. (16c)

Expanding the formulas for $\Phi_{i}(X)$ for $i>0$ and eliding the constant
factors, we may obtain

$\mspace{-19.0mu}\begin{aligned} \Phi(X)=\Phi_{0}(X)+\ell n^{-2\ell}(2\gamma
Q_{2})^{4\ell}\\!\>O\\!\\!\;\Biggl{(}\\!\Lambda^{2}\\!\\!\;\sum_{i=1}^{\ell-1}(2\gamma
Q_{2})^{-i}&+\Lambda\\!\sum_{i=\ell}^{2\ell-1}(2\gamma Q_{2})^{-i}\\!\\\
&+\ell^{-1}(2\gamma Q_{2})^{-2\ell}\Biggr{)}.\end{aligned}\\!\\!\\!$ (17)

For $\ell\in\omega(1)$, the asymptotic expression of the previous equation is
bounded from above by $O(\Lambda^{2})$, provided that
$\operatorname{poly}(\ell)(2\gamma Q_{2})^{-\Theta(\ell)}\subseteq o(1)$. For
the latter to hold, it suffices that ${2\gamma
Q_{2}-1\in\omega\bigl{(}\ell^{-1}\log(\ell)\bigr{)}}$. We then obtain the
upper bound

$\displaystyle\Phi(X)\;=\;\Phi_{0}(X)\,$
$\displaystyle+\,O\Bigl{(}\ell\Lambda^{2}n^{-2\ell}(2\gamma
Q_{2})^{4\ell}\Bigr{)}.$ (18)

We may show that $\Phi(X)=\Phi_{0}(X)\bigl{[}1+o(1)\bigr{]}$: using Eqn. (8),
we may estimate

$\mspace{-20.0mu}\begin{aligned}
F_{2\ell-1}\;&=\;n\cdot\frac{1}{2}\left[\tfrac{1}{2}\binom{n-1}{\ell-1}(\ell-1)!\right]\left[\tfrac{1}{2}\binom{n-\ell}{\ell-1}(\ell-1)!\right]\\\\[4.30554pt]
&=\;\frac{n!}{8(n-2\ell+1)!}\;\sim\;\tfrac{1}{8}n^{2\ell-1},\;\end{aligned}\mspace{-40.0mu}$
(19)

so that we have

$\displaystyle\Phi_{0}(X)$
$\displaystyle\lesssim\;F_{2\ell-1}\left(2\gamma\>\\!\big{/}\;\\!\\!n\right)^{\\!4\ell}Q_{2}^{4\ell-4}Q_{\text{crux}}^{2}\;=\;\left(\frac{Q_{\text{crux}}^{2}}{8Q_{2}^{4}}\right)n^{-2\ell-1}\left(2\gamma
Q_{2}\right)^{\\!4\ell},$ (20)

whereas by $\ell\in o(n^{1/9})$ and $\Lambda\in\Theta(\ell^{4}/n)\subseteq
o(n^{-5/9})$ we have

$O\Bigl{(}\ell\Lambda^{2}n^{-2\ell}(2\gamma
Q_{2})^{4\ell}\Bigr{)}\;\subseteq\;o\Bigl{(}n^{-2\ell-1}(2\gamma
Q_{2})^{4\ell}\Bigr{)}.$ (21)

We then have $\Phi(X)\sim\Phi_{0}(X)$ as promised. Thus we have
$\operatorname*{\mathbb{E}}(\varphi_{\ell}^{2})\sim\operatorname*{\mathbb{E}}(\varphi_{\ell})^{2}$,
so that $\operatorname*{Var}(\varphi_{\ell})\in
o(\operatorname*{\mathbb{E}}(\varphi_{\ell})^{2})$. By Chebyshev’s inequality,
the probability that $\varphi_{\ell}^{2}$ varies from its mean by
$\omega(\operatorname*{Var}(\varphi_{\ell}))$ is zero; then in particular
$\varphi_{\ell}$ is almost surely greater than $1$ provided that
$\operatorname*{\mathbb{E}}(\varphi_{\ell})>1$.

Frustrated subsystems may be efficiently detected when they are present, as
follows. For each vertex $x\in V(G)$, constraint-pair
$(\left\langle\alpha_{h}\right\rvert,\left\langle\alpha_{j}\right\rvert)$, and
$\ell>1$, we may enumerate the number of alternating paths (in the terminology
of Ref. [13]) of length $\ell$ which begin an end at $x$ whose first
constraint is of the form
$\left\langle\alpha_{h}\right\rvert\otimes\left\langle\gamma\right\rvert$ and
whose final constraint is of the form
$\left\langle\beta\right\rvert\otimes\left\langle\alpha_{j}\right\rvert$. We
may do so by traversing all alternating paths starting at $x$ by a breadth-
first search, and noting at each step whether in one step we may reach a
visited vertex which could be used to close an alternating path back to $x$.
Any one such path represents an alternating or quasi-alternating loop at $x$.
If for any $\ell>1$ there are two such loops with inconsistent constraints,
then the constraints at $x$ are unsatisfiable. Exploring all of the
alternating paths from $x$ for any one constraint pair
$(\left\langle\alpha_{h}\right\rvert,\left\langle\alpha_{j}\right\rvert)$ can
be done in time $O(m)$; doing so for all constraint-pairs and all $x\in V(G)$
can be done in time $O(nmf^{2})$. The frustrated pair of constraints may not
represent a frustrated figure eight (_e.g._ if the alternating paths starting
and ending at $x$ are of different lengths), but nevertheless serve to certify
that the instance of #$2$-QSAT is frustrated, and are present for all
frustrated instances.

Thus for $m\geqslant\frac{1+\varepsilon}{2Q_{2}}n$ for positive
$\varepsilon\in\omega(n^{-1/9}\log(n))$, an instance of $2$-QSAT constructed
on $G$ selected according to the Erdős–Rényi distribution will be frustrated
almost surely, due to the presence of multiple frustrated figure-eight
subsystems of size $O(\operatorname{poly}(n))$. Furthermore, one may determine
that such frustrations exist in polynomial time, when they are present.

####  3.1.3 The highly decoupled phase in frustration-free Erdős–Rényi models

In constructing frustration-free instances of $2$-QSAT from a discrete
distribution, we may suppose that constraints are repeatedly sampled for each
new constraint until we obtain one which does not render the instance
unsatisfiable.Any constraint which on the first “try” would have resulted in a
frustrated instance, we call a _would-be_ frustration. We may then consider
the structures in the Hamiltonian which _would have_ arisen, had we taken the
constraint which was first selected for any interaction, and thus speak
counterfactually of such features as “would-be” frustrated figure-eight
subsystems.

In frustrated figure-eight subsystems $X=X_{1}\cup X_{2}$, the common qubit
$x_{\ell}$ has conflicting constraints imposed on it by the two cycles $X_{1}$
and $X_{2}$. If we condition on frustration-free instances, this becomes a
_would-be_ frustrated figure-eight. As $X$ is being constructed, one of the
cycles (without loss of generality, $X_{1}$) must be completed before the
other: this is either a loop or quasi-alternating loop at $x$ (in the
terminology of Ref. [13]). A quasi-alternating loop at $x$ fixes the state of
$x$, which by construction do not by themselves satisfy the constraints
imposed on $x$ by $X_{2}$. Similar remarks apply when $X_{1}$ is an
alternating loop, which allows two possible single-qubit states for $x$ which
on their own satisfy the constraints imposed by $X_{1}$. In the case that
$X_{1}$ is an alternating loop, $x$ may be in one of two states
$|\psi_{x}^{0}\rangle$ or $|\psi_{x}^{1}\rangle$ in a product with the rest of
$X_{1}$, in which case all of the other spins of $X_{1}$ are in a product
state $|\Phi^{0}\rangle$ or $|\Phi^{1}\rangle$ (respectively) determined by
that state, or it may be entangled with the rest of the loop in some
superposition
$u_{0}|\psi_{x}^{0}\rangle|\Phi^{0}\rangle+u_{1}|\psi_{x}^{1}\rangle|\Phi^{1}\rangle$.
In either case, the marginal of any satisfying state on $x$ is a mixture of
$|\psi_{x}^{0}\rangle$ or $|\psi_{x}^{1}\rangle$, neither of which on their
own satisfy the constraints imposed by $X_{2}$ on $x$. Then in any case, upon
the completion of the cycle $X_{1}$, the states of all qubits in $X_{2}$ which
are accessible from $x$ at that time are uniquely fixed. Each subsequent edge
of $X_{2}$ which connects more qubits to $x_{\ell}$ also fixes the state of
those qubits. This means in particular that every one of the $\ell$ qubits
$v\in V(X_{2})$ have fixed states $\left\lvert\bar{\psi}_{v}\right\rangle$. We
call such a subsystem of fixed qubits a _frozen_ subsystem. Thus, a would-be
frustrated figure-eight on $2\ell-1$ qubits contains an (actually) frozen
cycle of $\ell$ qubits.

The analysis of the preceding section concerning frustrated figure-eight
subsystems $X={X_{1}\cup X_{2}}$ can be used to demonstrate the the existence
of a “frozen core”, or a subgraph of the giant component which itself contains
$\Omega(n)$ vertices. The growth of this frozen core will gradually start to
obstruct long-range constraints within the giant component, until eventually
it renders the #$2$-QSAT problem highly decoupled.

To describe the growth of large frozen subsystems in frustration-free
Erdős–Rényi models, we consider a random graph model for qubits with fixed
states. Define a directed graph $F$ defined by the $2$-QSAT instance
consisting of frozen subsystems, including only vertices representing qubits
with fixed states, and with arcs $x\rightarrow y$ for qubits connected by
constraints $\left\langle\eta_{x,y}\right\rvert$ such that
$\left\langle\eta_{x,y}\right\rvert\bigl{(}\left\lvert\smash{\bar{\psi}_{x}}\right\rangle\otimes\mathbbm{1}\bigr{)}\neq\mathbf{0}^{\dagger}$.
We call this digraph the _frozen subgraph_ of $G$.

We may establish lower bounds on the growth of $F$ in terms of an Erdős–Rényi
graph $U$, where edges of $G$ belong to $E(U)$ independently with some
probability $\tilde{Q}\leqslant Q$, and where all edges of $U$ are covered by
arcs of $F$. We consider $Q_{\infty}=1-\|\mathbf{q}\|_{\infty}$, and let
$p_{\infty}=mQ_{\infty}/\binom{n}{2}$. We then let $U$ be an Erdős–Rényi graph
having $m_{\infty}\approx\binom{n}{2}p_{\infty}$ edges: we treat this as a
subgraph of the Erdős–Rényi interaction graph $G$,444We may simulate randomly
sampling over graphs with $m$ edges, by considering graphs in which edges are
present _i.i.d_. with probability $p=m/\binom{n}{2}$ — the $\sqrt{n}$ variance
in the number of edges is smaller than the scales at which phase transitions
such as the emergence of the giant component occur.  including each edge of
$G$ with probability $Q_{\infty}$. Consider a random colouring
$c:V\to\\{1,2,\ldots,f\\}$, in which $\Pr[c(x)=j]=q_{j}$. For a given qubit
$x$ which has a fixed state
$\left\lvert\smash{\bar{\alpha}_{c(x)}}\right\rangle$, and a newly added edge
$xy\in E(G)$, the probability that $x\rightarrow y$ is an arc of the frozen
subgraph $F$ is $1-q_{c(x)}\geqslant Q_{\infty}$. From an initial set $S$ of
fixed qubits, we then simulate the construction of $F$ as follows:

  1. 1.

For each newly included vertex $x\in V(F)$ or $x\in S$, assign its colour
$c(x)$;

  2. 2.

For each neighbour $y$ of $x$ in $G$: If $xy\in U$, include $x\rightarrow y$
in $F$; otherwise include $x\rightarrow y$ in $F$ with probability
$(q_{1}-q_{c(x)})/q_{1}$; otherwise exclude it.

  3. 3.

Repeat the above until all $x\in S$ have been traversed, and no new vertices
have been included in $F$.

This construction reproduces the probability distribution of arcs in $F$, with
the random colouring of the vertex $c(y)$ taking the place of the action of
constraints
$\left\langle\eta_{x,y}\right\rvert=\left\langle\beta\right\rvert_{x}\otimes\left\langle\alpha_{c(y)}\right\rvert$
which fixes the state of the qubit $y$.

From the above, we may show that the largest (weakly connected) component of
$F$ grows at least as quickly as that of the Erdős–Rényi graph $U$ having
$m_{\infty}\sim mQ_{\infty}$ edges. In particular, if
$\frac{m}{n}>\gamma_{\infty}$ for $\gamma_{\infty}:=\frac{1}{2Q_{\infty}}$,
then $U$ has a giant connected component $\Gamma^{(U)}$; if any vertices of
$\Gamma^{(U)}$ are in $F$, then the entire component $\gamma^{(U)}$ is a
subgraph of $F$. As we have noted, there are frozen cycles (arising from
would-be frustrated figure eights) of size $\ell\in\operatorname{poly}(n)$ for
$(1+\varepsilon)/2Q_{2}\leqslant\frac{m}{n}\leqslant\gamma_{\infty}$: and
almost surely a constant fraction of these vertices are subsumed into
$\Gamma^{(U)}$, which has size $O(n)$. Then for $\frac{m}{n}>\gamma_{\infty}$,
the giant component of $U$ is almost surely contained in some weakly-connected
component of $F$. Thus $F$ almost surely contains a frozen core $\Gamma^{(F)}$
for $\gamma>\gamma_{\infty}$, which is at least as large as $\Gamma^{(U)}$.

Because the qubits in the frozen core cannot mediate non-trivial long-range
constraints between non-fixed qubits, and do not contribute to the value of
the #$2$-QSAT instance, they in effect play no role in the solution and may be
removed. Let $\gamma=\frac{m}{n}$. By Ref. [7, Theorem 9b], the subgraph
$\Gamma^{(U)}$ contains $(1-\tfrac{1}{2\gamma Q_{\\!\\!\>\infty}\\!}\xi(\gamma
Q_{\infty}))n+o(n)$ vertices, where

$\xi(\rho)=\sum_{k\geqslant
1}\frac{k^{k-1}}{k!}(2\rho{\mathrm{e}}^{-2\rho})^{k}$ (22)

and where $\tfrac{1}{2\rho}\xi(\rho)$ expresses (almost surely and up to
$o(1)$ error) the fraction of vertices which are contained in tree components
in an Erdős–Rényi graph with $\rho n$ edges. Following Ref. [7, Theorem 4b],
the function $\xi:[0,\infty)\to[0,1]$ has the property that
$\xi(\rho){\mathrm{e}}^{-\xi(\rho)}=2\rho{\mathrm{e}}^{-2\rho}$. We may show
that for any super-critical edge-density $\rho>\tfrac{1}{2}$, there is a sub-
critical edge-density $\tilde{\rho}:=\tfrac{1}{2}\xi(\rho)<\tfrac{1}{2}$ such
that the distribution of the sizes of tree-components for the edge-densities
$\rho$ and $\tilde{\rho}$ are the same up to a normalization
factor.555Consider a randomly selected tree component $T$, and let
$\tau_{\rho}(t)=\tfrac{1}{2\rho t!}t^{t-2}(2\rho{\mathrm{e}}^{-2\rho})^{t}$.
The probability $P_{\rho}(t)$ that $T$ has size $t$, when selecting tree-
components from the Erdős–Rényi graph with $\rho n$ edges, is then
$P_{\rho}(t)\,\sim\,\tau_{\rho}(t)\big{/}{\scriptstyle\sum_{k}}\tau_{\rho}(k)$
by Ref. [7, Eqn. 2.22]. From $\tilde{\rho}:=\tfrac{1}{2}\xi(\rho)$ and Ref.
[7, Eqn. 4.4] we may immediately see that $P_{\rho}(t)=P_{\tilde{\rho}}(t)$
for all $t$. As all but an insignificant number of vertices are contained in
either the giant component or in trees, the two distributions on graphs are
indistinguishable. Thus deleting the giant component from the Erdős–Rényi
graph with density $\rho$ gives rise to a graph indistinguishable from an
Erdős–Rényi graph with density $\tilde{\rho}$, albeit on
$\tfrac{1}{2\rho}\xi(\rho)n$ vertices. More generally, deleting the subgraph
$\Gamma^{(U)}$ from the graph $G$ yields a graph indistinguishable from an
Erdős–Rényi graph on $\tfrac{1}{2\gamma Q_{\\!\\!\;\infty}\\!}\xi(\gamma
Q_{\infty})n$ vertices, with edge-density given by

$\displaystyle\\!\tilde{\gamma}$ $\displaystyle:=\tfrac{1}{2}\xi(\gamma
Q_{\infty})+\gamma(1-Q_{\infty})\biggl{[}\frac{\xi(\gamma Q_{\infty})}{2\gamma
Q_{\infty}}\biggr{]}^{2}\\!=\tfrac{1}{2}\xi(\gamma
Q_{\infty})+\tfrac{1-Q_{\infty}}{4\gamma Q_{\infty}^{2}}\xi(\gamma
Q_{\infty})^{2},$ (23)

where the first term accounts for the density of
$U\smallsetminus\Gamma^{(U)}$, and the second term accounts for the
contribution of edges $e\in E(G)\smallsetminus E(U)$ which are also not
incident to $\Gamma^{(U)}$.

As the frozen core $\Gamma^{(F)}\supseteq\Gamma^{(U)}$ grows, the subgraph of
$G$ that remains after removing $\Gamma^{(F)}$ becomes more sparse, and
eventually becomes highly disconnected. That is to say, the instance with the
frozen subsystems included is highly decoupled. Note that $\xi(\rho)=2\rho$
for $\rho\in[0,\tfrac{1}{2}]$, achieving a maximum of $1$ and then decreasing
for $\rho\geqslant\tfrac{1}{2}$. It follows that $\tilde{\gamma}=\gamma$ for
$\gamma Q_{\infty}\leqslant\tfrac{1}{2}$, achieving a maximum of
$1/2Q_{\infty}$ and then subsequently bounded by

$\displaystyle\tilde{\gamma}\;\leqslant\;\left[\tfrac{1}{2}+\tfrac{1-Q_{\infty}}{2Q_{\infty}}\right]\xi(\gamma
Q_{\infty})$ $\displaystyle\leqslant\;\tfrac{1}{2Q_{\infty}}\xi(\gamma
Q_{\infty})$ (24) $\displaystyle\leqslant\;\gamma{\mathrm{e}}^{\xi(\gamma
Q_{\infty})}{\mathrm{e}}^{-2\gamma
Q_{\infty}}\;\leqslant\;\gamma{\mathrm{e}}^{1-2\gamma Q_{\infty}}.$

If $2\gamma Q_{\infty}-\ln(2\gamma)>1$, we then have
$\tilde{\gamma}<\tfrac{1}{2}$. In this case ${G\smallsetminus\Gamma^{(U)}}$
becomes subcritical and thus highly disconnected; the same is then true of
${G\smallsetminus\Gamma^{(F)}}$.

Thus for $\gamma$ sufficiently large, frustration-free instances of #$2$-QSAT
almost surely contain a frozen core pervasive enough to cause the problem to
be highly decoupled. It is easy to show that such a frozen core can be easily
detected, as well, using the same techniques as described in the preceding
section for frustrated figure-eights. We may detect the existence of
alternating and quasi-alternating loops at each vertex $x$ in the graph, and
then consider the constraints on $x$ and its neighbours to discover an initial
set of frozen spins. Following this, using a single breadth-first traversal,
we may discover the entire frozen subgraph and its largest component in
particular. Discovering the frozen core is therefore possible in polynomial
time using standard techniques.

###  3.2 Bond-percolated lattice graphs

The analysis for random $2$-QSAT is much simpler for bond-percolated square or
cubic lattices. In this graph model, we take vertices labelled either
$(a,b)\in\\{0,1,\ldots,L-1\\}^{2}$ or $(a,b,c)\in\\{0,1,\ldots,L-1\\}^{3}$,
and connect each pair of vertices which differ by $1$ in a single co-ordinate,
independently with some probability $p$. We let $d$ denote the dimension of
the lattice, let $n=L^{d}$ be the number of vertices and $m\sim dpn$ be the
expected number of edges.

The analysis of phase transitions in the difficulty of #$2$-QSAT for
independent factor constraints is simpler for percolated lattices than for
Erdős–Rényi graphs, as cycles arise in the percolated lattice much more easily
and as the degree of each vertex is necessarily bounded. Furthermore, we only
expect the largest components to grow with $n$ if $p$ is greater than a
“percolation threshold” $p_{c}$ [10],666For $d_{2}$, we have
$p_{c}=\tfrac{1}{2}$; for $d=3$, we have $p_{c}\approx 0.24881$; _c.f._ Ref
[10]. N.B. For $d=3$ it is not yet known whether there exists an infinite
component when $p=p_{c}$; this is known not to occur for $d=2$ or $d\geqslant
19$, and the same is conjectured for $d=3$ [10, Section 9.4].  in which case
the largest component is unique and scales as $O(n)$. For #$2$-QSAT with
independent factor constraints, this allows one to show:

  * •

#$2$-QSAT is almost certainly efficiently solvable for any value of $p$, as
there are overlapping phases of frustrated and highly disconnected instances,
occurring respectively for $p\in\omega(n^{-1/7})$ and $p\leqslant p_{c}\in
O(1)$;

  * •

For frustration-free instances of #$2$-QSAT, provided that
$Q_{\infty}:=1-\|\mathbf{q}\|_{\infty}>p_{c}$, there is a transition directly
from highly disconnected instances for $p<p_{c}$ to highly decoupled instances
for $p\geqslant p_{c}$, due to the emergence of frozen subgraph whose
components decouple the system into small non-interacting components (in a way
which is similar to, but more straightforward than, the analogous phenomenon
in models on Erdős–Rényi graphs.)

In this Section we outline these results in enough detail to indicate how the
results may be shown more completely. Furthermore, results which are similar
in quality could also be shown for any lattice model, depending in practise
only on the size of the smallest cycles and the percolation threshold $p_{c}$
of the lattice.

####  3.2.1 Critical thresholds for unconditional percolated lattice models

If each edge in a $d$-dimensional rectangular lattice (for $d\in\\{2,3\\}$) is
present independently with probability $p\in o(1)$, then the first components
with cycles to emerge as $p$ increases are the ones with the fewest edges.
That is, if the probability of there being a component in $G$ which is
isomorphic to a graph $g$ is $\Omega(1)$, then $G$ will contain infinitely
many isomorphic copies of any component $g^{\prime}$ for which
$|E(g^{\prime})|<|E(g)|$. The first components with cycles to emerge are
therefore individual square facets of the lattice, which are almost surely
absent for $p\in o(n^{-1/4})$, and present in infinite abundance for
$p\in\omega(n^{-1/4})$.

The smallest subgraph of a rectangular lattice which contains two cycles is a
_domino graph_ , as pictured in Fig. 2, which has seven edges. These are
therefore almost certainly absent for $p\in o(n^{-1/7})$, and almost certainly
abundantly present for $p\in\omega(n^{-1/7})$. It is not difficult to show
that each of these has a constant probability of being a _frustrated domino_ :
a system similar to a frustrated-figure eight in which the constraints give
rise to unsatisfiable restrictions on the state of the two central qubits.
Consider the three independent paths between the central vertices of a domino
subgraph (also depicted in Fig. 2). Given that each edge represents a non-zero
constraint (which happens with constant probability), the two outer paths in
the domino each give rise to a non-zero path constraint with probability
$Q_{2}^{2}=(1-\|\mathbf{q}\|_{2}^{2})^{2}$. With some probability, the three
path constraints will act on each of their endpoints in a different way from
the others. This remains true even for classical instances of #$2$-SAT, if the
constraint-operators are chosen from a probability distribution over a
distribution on $\\{\left\langle 00\right\rvert,\left\langle
01\right\rvert,\left\langle 10\right\rvert,\left\langle 11\right\rvert\\}$ in
which each element occurs with probability $\Omega(1)$, each such domino is
unsatisfiable with constant probability, in which case the entire instance of
#$2$-SAT which contains it has value zero. (This would occur, for instance,
for an independent factor distribution $\mathbf{q}=(q_{1},q_{2})$ in which
$\left\langle\alpha_{1}\right\rvert=\left\langle 0\right\rvert$ and
$\left\langle\alpha_{2}\right\rvert=\left\langle 1\right\rvert$, where $q_{1}$
and $q_{2}$ are both bounded away from zero.) Thus, there is a phase
transition at $p\in\Theta(n^{-1/7})$ from almost certain satisfiability to
almost certain unsatisfiability, due to the probable emergence of frustrated
dominoes, of which there are almost surely infinitely many once
$p\in\omega(n^{-1/7})$.

The components in a bond-percolated lattice for $p\in O(n^{-1/7})$ almost
certainly have size $O(1)$: specifically, they will almost surely have seven
vertices or fewer. Thus the complexity of computing #$2$-QSAT is almost surely
governed by that of multiplying $O(n)$ “small” integers. A simple algorithm to
do so is described in Appendix A. Thus, #$2$-QSAT is almost surely easy for
$p$ increasing up to, and even through, the phase transition at
$p\in\Theta(n^{-1/7})$; afterwards, of course, the value is almost surely
zero. Difficult instances of #$2$-QSAT on percolated lattices are thus either
ones which are asymptotically monotone — that is, for which $Q_{2}$ decreases
with $n$ — or ones which almost surely never occur. Similar phenomena will
occur for any lattice model, with a phase transition at
$p\in\Theta(n^{-1/\beta})$, where $\beta$ is the number of edges in the
smallest subgraph having more than one cycle.

Figure 2: (_Top:_) An isolated “domino” subgraph of a square lattice. Dashed
lines indicate missing edges incident to the subgraph. A domino subgraph in a
3D lattice may also occur with the two cycles meeting at a right angle.
(_Bottom:_) Illustration of the three independent paths between the central
qubits of a domino subgraph. If the constraints acting on $b$ do so with
different tensor factors
$\left\langle\alpha\right\rvert,\left\langle\alpha^{\prime}\right\rvert,\left\langle\alpha^{\prime\prime}\right\rvert:\mathbb{C}^{2}\to\mathbb{C}$
and similarly for the constraints
$\left\langle\beta\right\rvert,\left\langle\beta^{\prime}\right\rvert,\left\langle\beta^{\prime\prime}\right\rvert:\mathbb{C}^{2}\to\mathbb{C}$
acting on $e$, and the path-constraints are all non-zero, then these form an
infeasible system of constraints on the states of $b$ and $e$. Similar remarks
apply for any pair of qubits connected by more than two independent paths.

$a$$b$$c$$d$$e$$f$$b$$b$$b$$a$$c$$d$$e$$e$$e$$f$

####  3.2.2 Critical thresholds for frustration-free percolated lattice models

To obtain interesting instances of #$2$-SAT or #$2$-QSAT on a percolated
rectangular lattice, we must condition on models which are frustration-free.
However, for $p$ less than the percolation probability $p_{c}$, almost surely
the resulting graph $G$ contains only components of size $o(f(n))$ for any
$f\in\omega(1)$.777For $d=2$ (for which $p_{c}=\tfrac{1}{2}$) or $d=3$ (for
which $p_{c}\approx 0.24881$), the distribution of component sizes decreases
geometrically (for $p<p_{c}$) [10, Section 6.3], and almost surely no infinite
component exists. This implies that for $p<p_{c}$, it again suffices to
compute the values of #$2$-QSAT for each component individually,888As the
components all have essentially constant size, this may be done for each
component in $O(\log n)$ time, dominated merely by the time required to
process the labels of vertices. so that #$2$-QSAT is almost surely efficiently
solvable so long as $p\leqslant p_{c}$. It thus suffices for us to consider
the regime $p>p_{c}$.

We may proceed similarly to the analysis of the giant component in
frustration-free Erdős–Rényi models in Section 3.1.3. Would-be frustrated
subsystems — such as frustrated figure-eights on seven vertices (consisting of
two square cells intersecting at one qubit) or would-be frustrated dominoes —
will arise in abundance for $p\in\Theta(1)$. Each one gives rise to several
qubits with fixed states, which contribute to the presence of a non-empty
frozen subgraph $F$. If there is a giant component $\Gamma^{(G)}$, then there
are almost certainly would-be frustrated subsystems inside it: we ask to what
extent these give rise to frozen subsystems which decouple $\Gamma^{(G)}$.

As with the Erdős–Rényi case, we may let
$Q_{\infty}=1-\|\mathbf{q}\|_{\infty}$ be a lower bound on the probability
that any two constraints coinciding at a qubit give rise to a non-zero
constraint on a path of length two, such that we may treat this as as
independent events even for various pairs of constraints meeting acting on the
same qubit. For instance, the probability that any domino subgraph is a would-
be-frustrated domino is at least $Q_{\infty}^{7}$. For any qubit $x\in V(F)$,
the probability that some neighbour $y$ in $G$ is also subsumed into $V(F)$ is
also at least $Q_{\infty}$. We may then consider a percolated lattice model
$U$ in which edges are present with probability $Q_{\infty}$, and any such
component which contains a frozen seed gives rise to a component in the frozen
subgraph $F$.

When does the frozen core $\Gamma^{(F)}$ decouple an instance of #$2$-QSAT?
That is: when does ${G\smallsetminus V(\Gamma^{(F)})}$ decompose as a
collection of small components? This relates to the problem, when $U$ has a
giant component $\Gamma^{(U)}$, of whether the complement of $\Gamma^{(U)}$ in
the complete (square or cubic) lattice has any infinite components (in the
limit $n\to\infty$). For both $d\in\\{2,3\\}$, there exists a threshold
$p_{\text{fin}}<1$ [11] such that the complement of $\Gamma^{(U)}$ in the
lattice decomposes into components of finite size when
$Q_{\infty}>p_{\text{fin}}$.999A simple duality argument shows that
$p_{\text{fin}}=p_{c}=\tfrac{1}{2}$ for $d=2$ [11]. For $d=3$, only know the
more general result $p_{c}\leqslant p_{\text{fin}}<1$ is currently known.
While no numerical results are known about $p_{\text{fin}}$ for $d=3$, the
growth of infinite clusters in each planar cross-section of the cubic lattice
suggests that $p_{\text{fin}}$ is closer to $1-p_{c}$ than to $1$.  Consider
the case $Q_{\infty}>p_{c}$:

  * •

If $p=1$ (that is, $G$ is simply the entire $O(n)$-vertex square or cubic
lattice segment), then by construction $G\smallsetminus U$ is a collection of
small components. As $\Gamma^{(U)}$ is almost surely subsumed by a frozen core
$\Gamma^{(F)}$ of qubits with fixed states, which do not contribute to the
value of the #$2$-QSAT instance. As the complete lattice with $\Gamma^{(F)}$
removed consists of components of finite size, the resulting instance of
#$2$-QSAT is highly decoupled.

  * •

If $p<1$, then we may model the resulting $2$-QSAT instance on the percolated
lattice by reducing from the previous case (in which the instance is highly
decoupled), and removing each constraint in the complete lattice with
probability $1-p$: doing so does not make the instance any less decoupled.

Thus, for $Q_{\infty}>p_{\text{fin}}$ (which occurs for
$\|\mathbf{q}\|_{\infty}$ below some constant), there is a phase transition
for random frustration-free instances of #$2$-QSAT from highly disconnected
instances to highly decoupled instances. This means that for $d=2$, difficult
instances of #$2$-QSAT are only likely if the constraint model is “at least as
monotone” as some distribution of classical #$2$-SAT constraints; for $d=3$, a
bias towards monotonicity which would be substantial even for #$2$-SAT is
necessary to obtain difficult instances.101010This implies, for instance, that
uniformly random #$2$-SAT on bond-percolated cubic lattices is almost surely
efficiently solvable whether or not we condition on satisfiability.

As a final remark, note that even in the case that $Q_{\infty}\leqslant
p_{\text{fin}}$, there is a chance that frozen subsystems will decouple the
largest component $\Gamma^{(G)}$ into small subsystems. Any domino-shaped
subsystem of $\Gamma^{(G)}$ has a finite probability of containing a frozen
cycle, which can be treated in the giant component as nodes which are removed
from $\Gamma^{(G)}$ with some finite probability $1-P_{\text{site}}>0$. Using
results on mixed site- and bond-percolation [12], if
${P_{\text{site}}\,p<p_{c}}$, the giant component $\Gamma^{(G)}$ still
decouples into small subsystems whose degeneracy may be efficiently computed.
We do not present any quantitative results for $Q_{\infty}\leqslant p_{c}$,
but mention this to indicate that it likely that #$2$-QSAT may remain easy
even for some values $Q_{\infty}<p_{c}$, for reasons similar to what we have
shown for $Q_{\infty}>p_{c}$.

##  4 Open questions

The results of this article may allow for some improvements, which would
further bound any “difficult” regime in random distributions of #$2$-QSAT on
random graphs.

  * •

For frustration-free instances, $Q_{\infty}=\min_{j}(1-q_{j})$ is used as a
percolation probability on an existing random graph, to obtain lower bounds on
the transition to a highly decoupled phase; whereas
$Q_{2}=\operatorname*{\mathbb{E}}_{j}\bigl{[}1-q_{j}\bigr{]}$ is used for
potentially frustrated models (where we take $\Pr[j]=q_{j}$). Can we replace
bounds involving $Q_{\infty}$ with tighter bounds involving $Q_{2}$?

  * •

If we remove the condition of frustration-freeness from #$2$-QSAT altogether,
we are left with the problem of computing the degeneracy of the ground-state
manifold of a potentially frustrated Hamiltonian. Physical intuition suggests
that this is typically “1”, but as with #$2$-QSAT, the classical problem of
determining how many boolean strings satisfy a maximum number of constraints
is a hard problem in general. Under what conditions is it provably easy to
compute the ground-state degeneracy of random local Hamiltonians?

#### Acknowledgements.

This work was partly performed at the University of Cambridge, with support
from the EC project QCS. I would like to thank Ronald de Wolf, as well as an
anonymous referee, for helpful comments on the preliminary drafts.

## References

  * [1] B. Aspvall, M. F. Plass, and R. E. Tarjan.  A linear-time algorithm for testing the truth of certain quantified boolean formulas.  Information Processing Letters, 8(3):121–123, 1979.
  * [2] S. Bravyi.  Efficient algorithm for a quantum analogue of 2-SAT.  arXiv:quant-ph/0602108, 2006.
  * [3] S. Bravyi, C. Moore, and A. Russell.  Bounds on the Quantum Satisfiability threshold.  In Andrew Chi-Chih Yao, editor, ICS, pages 482–489. Tsinghua University Press, 2010.  arXiv:0907.1297.
  * [4] V. Chvatal and B. Reed.  Mick gets some (the odds are on his side).  In Proc. 33rd Annual FOCS, pages 620–627, 1992.
  * [5] N. de Beaudrap, T. J. Osborne, and J. Eisert.  Ground states of unfrustrated spin hamiltonians satisfy an area law.  New J. Phys., 12:095007, 2010.  arXiv:1009.3051.
  * [6] R. Diestel.  Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics.  Springer, 2012.
  * [7] P. Erdős and A. Rényi.  On the evolution of random graphs.  Publ. Math. Inst. Hungary. Acad. Sci., 5:17–61, 1960.
  * [8] E. Fischer, J. A. Makowsky, and E. V. Ravve.  Counting truth assignments of formulas of bounded tree-width or clique-width.  Discrete Applied Mathematics, 156:511–529, 2008.
  * [9] D. Gosset and D. Nagaj.  Quantum 3-SAT is QMA1-complete.  arXiv:1302.0290, 2013.
  * [10] G. Grimmett.  Percolation.  Springer, Berlin, 2nd edition, 1999.
  * [11] G. R. Grimmett, A. E. Holroyd, and G. Kozma.  Percolation of finite clusters and infinite surfaces.  Mathematical Proceedings of the Cambridge Philosophical Society, 156:263–279, 2014.  arXiv:1303.1657.
  * [12] J. M. Hammersley.  A generalization of McDiarmid’s theorem for mixed Bernoulli percolation.  Math. Proc. Camb. Phil. Soc., 1980.
  * [13] Z. Ji, Z. Wei, and B. Zeng.  Complete characterization of the ground space structure of two-body frustration-free hamiltonians for qubits.  Phys. Rev. A, 84:042338, 2011.
  * [14] C. R. Laumann, R. Moessner, A. Scardicchio, and S. L. Sondhi.  Phase transitions and random quantum satisfiability.  Quant. Inf. and Comp., 10:1–15, 2010.  arXiv:0903.1904.
  * [15] C. Papadimitriou and M. Yannakakis.  Optimization, approximation, and complexity classes.  J. Comp. Sys. Sci., 43:425–440, 1991.
  * [16] N. Robertson and P. D. Seymour.  Graph minors. III. Planar tree-width.  Journal of Combinatorial Theory, Series B, 36(1):49–64, 1984.
  * [17] L. Valiant.  The complexity of enumeration and reliability problems.  SIAM J. Computing, 8:410–421, 1979.

##  Appendix A An effective technique for multiplying together long lists of
mostly small numbers

The value of an instance of #$2$-QSAT is at most $2^{n}$. We may decompose the
value of an instance of #$2$-QSAT as a product of the values of each connected
component. In the easily solved instances which arise either when the
interaction graph is highly disconnected, or when a large frozen subsystem
decouples the Hamiltonian into small independent subsystems, the value of
#$2$-QSAT for these instances is $O(\log n)$. One might then show that simply
multiplying together these values can be performed in polynomial time, by
accounting for the increase in size of the integers involved in the
multiplication as more and more factors are included in the product. Rather
than analyse the growth of the product in an iterative multiplication
algorithm, we will show a different algorithm, by which the complexity of
evaluating this product is asymptotically no greater than multiplying two
$n$-digit numbers.

By sorting the non-giant components of $G$ in order of size (we assume only
non-giant components henceforth), we may construct a binary tree such that

  * •

The leaves represent sets, each of which contains an individual component and
having a stored #$2$-QSAT value of one more than the component size;

  * •

Each node which is not a leaf represents the union of the sets of components
represented by its child nodes, and stores the product of the #$2$-QSAT values
of its children;

  * •

The #$2$-QSAT values of the children of any node are either similar in size
(_e.g._ differing by a factor of at most $3$), or the degeneracy of one of
them is constant (_e.g._ at most $3$).

We start by pairing the largest component with the second largest component;
in the case that the second-largest component is less than half the size of
the largest, we first pair it together with a small component (_e.g._ isolated
vertices), and pair the largest component with the parent to these two nodes.
We continue similarly for the next two largest components, using the smallest
components to compensate for differences in the size of the degeneracies of
subtrees. (Because there are $O(n)$ components in the Erdős–Rényi graph for
any number of edges $m$, the components of constant size must dominate, and
the smallest ones will occur most frequently as a result of the reduced
probability of being merged with other components. For bond-percolated
lattices, the distribution of component sizes is monotone decreasing for any
bond-percolation probability $p$, so again small components dominate.) The
degeneracy of the root node of the tree then is the degeneracy of the
Hamiltonian.

The number of bits required to represent the degeneracy at each level in the
tree either remains about constant, or decreases by a factor of $2$, with each
level down from the parent node. Due to the domination by components of
constant size, there will be $\Theta(n)$ leaves on either side of the tree, so
that it will have depth $O(\log n)$; most subtrees will be balanced. Thus
there will be approximately $O(\log n)$ rounds of (in principle
parallelisable) multiplications, where the $t\textsuperscript{th}$ round from
the final one is between numbers of size $n/2^{t}$, and each round involves
about $2^{t}$ multiplications in total. For any given multiplication algorithm
running in some time $O(n^{d})$ (_e.g._ where $d=2$ for the usual
straightforward algorithm taught in schools), we can recursively evaluate the
value of the entire #$2$-QSAT instance, corresponding to the root node of the
tree, in time

$\begin{aligned} \sum_{t=1}^{\mathclap{O(\log
n)}}\,2^{t}\left(\frac{n}{2^{t}}\right)^{\\!d}&=\;\sum_{t=1}^{\mathclap{O(\log
n)}}2^{t(1-d)}n^{d}\,=\;\left[\frac{2^{(1-d)}-2^{O((1-d)\log
n)}}{1-2^{(1-d)}}\right]\\!n^{d}\;\in\;O(n^{d}).\end{aligned}\\!\\!\\!$ (25)