# On efficiently solvable cases of Quantum $k$-SAT

Marco Aldi111Department of Mathematics and Applied Mathematics, Virginia
Commonwealth University, U.S.A. Niel de Beaudrap222Department of Computer
Science, University of Oxford, U.K. Sevag Gharibian333Department of Computer
Science, University of Paderborn, Germany, and Virginia Commonwealth
University, U.S.A. Seyran Saeedi444Department of Computer Science, Virginia
Commonwealth University, U.S.A.

###### Abstract

The constraint satisfaction problems $k$-SAT and Quantum $k$-SAT ($k$-QSAT)
are canonical NP-complete and QMA1-complete problems (for $k\geq 3$),
respectively, where QMA1 is a quantum generalization of NP with one-sided
error. Whereas $k$-SAT has been well-studied for special tractable cases, as
well as from a parameterized complexity perspective, much less is known in
similar settings for $k$-QSAT. Here, we study the open problem of computing
satisfying assignments to $k$-QSAT instances which have a “matching” or “dimer
covering”; this is an NP problem whose decision variant is trivial, but whose
search complexity remains open.

Our results fall into three directions, all of which relate to the “matching”
setting: (1) We give a polynomial-time classical algorithm for $k$-QSAT when
all qubits occur in at most two clauses. (2) We give a parameterized algorithm
for $k$-QSAT instances from a certain non-trivial class, which allows us to
obtain exponential speedups over brute force methods in some cases. This is
achieved by reducing the problem to solving for a single root of a single
univariate polynomial. (3) We conduct a structural graph theoretic study of
$3$-QSAT interaction graphs which have a “matching”. We remark that the
results of (2), in particular, introduce a number of new tools to the study of
Quantum SAT, including graph theoretic concepts such as transfer filtrations
and blow-ups from algebraic geometry.

##  1 Introduction

Constraint satisfaction problems (CSPs) are cornerstones of both classical and
quantum complexity theory. Indeed, CSPs such as $3$-SAT and MAX-$2$-SAT are
complete for NP [Kar72], and their analogues Quantum $3$-SAT (3-QSAT) and the
$2$-local Hamiltonian problem are QMA1\- and QMA-complete, respectively
[Bra06, GN13, KSV02, KKR06]. (QMA is Quantum Merlin-Arthur, a quantum
generalization of Merlin-Arthur, and QMA1 is QMA with perfect completeness.)
As such CSPs are intractable in the worst case, approaches such as
approximation algorithms, heuristics, and exact algorithms are typically
employed. In this paper, we focus on the latter technique, and ask: Which
special cases of $k$-QSAT can be solved efficiently on a classical computer?

Unfortunately, this problem appears to be markedly more difficult than in the
classical setting. For example, classically, if each clause $c$ of a $k$-SAT
instance can be matched with a unique variable $v_{c}$, then clearly the
$k$-SAT instance is satisfiable, and finding a solution is trivial: Set
variable $v_{c}$ to satisfy clause $c$. (Note that the matching can be found
efficiently via, e.g., the Ford-Fulkerson algorithm [JF56].) In the quantum
setting, it has been known [LLM+10] since 2010 that $k$-QSAT instances with
such “matchings” (also called a “dimer covering” in physics [LLM+10]) are also
satisfiable, and moreover the satisfying assignment can be represented
succinctly as a tensor product state. Yet, _finding_ the satisfying assignment
efficiently has proven elusive (indeed, the proof of [LLM+10] is _non-
constructive_). In other words, we have a trivial NP _decision_ problem whose
analogous _search_ version is not known to be efficiently solvable (see, e.g.,
[BG94] regarding the longstanding open question of decision versus search
complexity for NP problems). This is the starting point of the present work.

##### Results and techniques.

Our results fall under three directions, all of which are related to $k$-QSAT
with matchings. For this, we first define Quantum $k$-SAT ($k$-QSAT) [Bra06]
and the notion of a system of distinct representatives (SDR). For $k$-QSAT,
the input is a two-tuple
$\Pi=({\left\\{\Pi_{i}=|\psi_{i}\rangle\\!{\langle\psi_{i}|}\right\\}}_{i},\alpha)$
of rank $1$ projectors or _clauses_ 555The original definition [Bra06] of
$k$-QSAT did not require each $\Pi_{i}$ to be rank $1$. As in [LLM+10], we
require the rank-$1$ condition to make our definitions and results well-
defined and valid, respectively. Nevertheless, we do allow one to “stack”
multiple clauses on a fixed set of $k$ qubits to simulate higher rank clauses.
$\Pi_{i}\in\mathcal{L}{({\mathbb{C}}^{2})^{\otimes k}}$, each acting non-
trivially on a set of $k$ (out of $n$) qubits, and non-negative real number
$\alpha>1/p(n)$ for some fixed polynomial $p$. The output is to decide whether
there exists a satisfying assignment on $n$ qubits
$|\psi\rangle\in({\mathbb{C}}^{2})^{\otimes n}$, i.e. to distinguish between
the cases $\Pi_{i}|\psi\rangle=0$ for all $i$ (YES case), or whether
${\langle\psi|}\sum_{i}\Pi_{i}|\psi\rangle\geq\alpha$ (NO case). Note that
$k$-QSAT generalizes $k$-SAT. As for a _system of distinct representatives
(SDR)_ (which is formal terminology for the notion of “matching” for $k$-QSAT
instances, as adopted from the combinatorics literature [Juk11]), given a set
system such as a hypergraph $G=(V,E)$, an SDR is a set of vertices
$V^{\prime}\subseteq V$ such that each edge in $e\in E$ is paired with a
distinct vertex $v_{e}\in V^{\prime}$ such that $v_{e}\in e$. In previous work
on QSAT, an SDR has been referred to as a “dimer covering” [LLM+10].

_1\. Quantum $k$-SAT with bounded occurrence of variables._ Our first result
concerns the natural restriction of limiting the number of times a variable
can appear in a clause. For example, $3$-SAT with at most $3$ occurrences per
variable is known to be NP-hard. We complement this as follows.

######  Theorem 1.

There exists a polynomial time classical algorithm which, given an instance
$\Pi$ of $k$-QSAT in which each variable occurs in at most two clauses,
outputs a satisfying product state if $\Pi$ is satisfiable, and otherwise
rejects. Moreover, the algorithm works for clauses ranging from $1$-local to
$k$-local in size.

To show this, our idea is to “partially reduce” the $k$-QSAT instance to a
$2$-QSAT instance. We then use the transfer matrix techniques of [Bra06,
LMSS10, dBG16] (particularly the notion of _chain reactions_ from [dBG16]),
along with a new notion of “fusing” chain reactions, to deal with the
remaining clauses of locality at least $3$ in the instance.

Whereas _a priori_ this setting may seem unrelated to the open question of
computing solutions to $k$-QSAT instances with SDRs, we connect the two
settings as follows. Denote the _interaction hypergraph_ $G=(V,E)$ of a
$k$-QSAT instance as a $k$-uniform hypergraph (i.e. all edges have size
precisely $k$), in which the vertices correspond to qubits, and each clause
$c$ acting on a set of $k$ qubits $S_{c}$, is represented by a hyperedge of
size $k$ containing the vertices corresponding to $S_{c}$.

######  Theorem 2.

Let $G=(V,E)$ be a hypergraph with all hyperedges of size at least $2$, and
such that each vertex has degree at most $2$. Then, $G$ has an SDR.

Thus, Theorem 1 resolves the open question of [LLM+10] for $k$-QSAT instances
with SDRs in which additionally (1) each variable occurs in at most two
clauses and (2) there are no $1$-local clauses. (The latter of these
restrictions is necessary, as allowing edges of size $1$ easily makes Theorem
2 false in general; see Section 3.1.)

_2\. On parameterized complexity for Quantum $k$-SAT._ Our next result, and
the main contribution of this paper, gives a parameterized
algorithm666Roughly, parameterized complexity characterizes the complexity of
computational problems with respect to specific _parameters_ of interest other
than just the input size (e.g. the treewidth of the input graph). for
explicitly computing (product state) solutions for a non-trivial class of
$k$-QSAT instances. As discussed in Section 4.4, this algorithm in some cases
provides an _exponential_ speedup over brute force diagonalization.

At the core of the algorithm is a new graph theoretic notion of _transfer
filtration of type $b$_ for a $k$-uniform hypergraph $G=(V,E)$, for fixed
$b>0$. Intuitively, one should think of $b$ as denoting the size of a set of
$b$ qubits which form the hard “foundation”’ of any $k$-QSAT instance on $G$.
With the notion of transfer filtration in hand, our framework for attacking
$k$-QSAT can be sketched at a high level as follows.

  1. 1.

First, given a $k$-QSAT instance $\Pi$ on $G$ with transfer filtration of type
$b$, we “blow-up” $\Pi$ to a larger, _decoupled_ instance $\Pi^{+}$
(Decoupling Lemma, Lemma 18). The decoupled nature of $\Pi^{+}$ makes it
“easier” to solve (Transfer Lemma, Lemma 28), in that any assignment to the
$b$ “foundation” qubits can be _extended_ to a solution to all of $\Pi^{+}$.
This raises the question — how does one map the solution of $\Pi^{+}$ back to
a solution of $\Pi$?

  2. 2.

We next give a set of “qualifier” constraints ${\left\\{h_{s}\right\\}}$
(Qualifier Lemma, Lemma 30) acting on _only the $b$ foundation qubits_, with
the following strong property: If a (product state) assignment $\mathbf{v}$ to
the $b$ foundation qubits satisfies the constraints
${\left\\{h_{s}\right\\}}$, then not only can we extend $\mathbf{v}$ via the
Transfer Lemma to a full solution for $\Pi^{+}$ as in Step 1 above, but we can
also map this extended solution back to one for the _original_ $k$-QSAT
instance $\Pi$. (For clarity, there is an additional required technical
condition on the _transfer functions_ $g_{i}$ in the Transfer Lemma, which we
circumvent in our main Theorem 38.)

Once the framework above is developed, we show that it applies to the non-
trivial family of $k$-QSAT instances whose $k$-uniform hypergraph $G=(V,E)$
has a transfer filtration of type $b=\left\lvert V\right\rvert-\left\lvert
E\right\rvert+1$. This family includes, e.g., the semi-cycle of Figure 1, (a
slight modification of) the tiling of the torus (Figure 14), and “fir tree”
(Figure 5). Our main result (Theorem 38) says the following: For any $k$-QSAT
instance $\Pi$ on such a $G$ and whose constraints are generic (see Section
4), computing a (product state) solution to $\Pi$ reduces to solving for a
root of a _single univariate_ (see Remark 41) polynomial $P$ — _any_ such root
(which always exists if the field ${\mathbb{K}}$ is algebraically closed) can
then be extended back to a full solution for $\Pi$.

The key advantage of this approach, and what makes it a parameterized
algorithm, is the following — the _degree_ of $P$, and hence the runtime of
the algorithm, scale exponentially only in $b$ and a “radius” parameter $r$ of
the transfer filtration (assuming $k\in O(1)$, see Equation (10) for an
explicit bound on runtime). Thus, given a transfer filtration where $b$ and
$r$ are at most logarithmic, finding a (product state) solution to $k$-QSAT
reduces to solving for a single root over ${\mathbb{C}}$ for a single
univariate polynomial $h_{1}$ of polynomial degree, which can be done in
polynomial time [Sch85, Sch86]. Indeed, in Section 4 we give a non-trivial
family of $k$-uniform hypergraphs, denoted Crash (Figure 7), for which our
algorithm runs in polynomial time, whereas brute force diagonalization would
require exponential time.

Conveniently, even when the foundation $b$ and radius $r$ are
superlogarithmic, our algorithm still gives a _constructive_ proof that all
$k$-QSAT instances satisfying the preconditions of Theorem 38 have a (product
state) solution. In particular, in Corollary 43 and Theorem 50, we observe
that such hypergraphs must have SDRs, and so we constructively reproduce the
result of [LLM+10] that any $3$-QSAT instance with an SDR is satisfiable (by a
product state) (again, assuming the additional conditions of Theorem 38 are
met).

Finally, although this result stems primarily from tools of projective
algebraic geometry (AG), the presentation herein avoids any explicit mention
of AG terminology (with the exception of defining the term “generic” in
Section 4.3) to be accessible to readers without an AG background. For
completeness, a brief overview of the ideas in AG terms is given at the end of
Section 4.

_3\. A study of $3$-uniform hypergraphs with SDRs._ Our final contribution,
which we hope will help guide future studies on the topic, is to take steps
towards understanding the structure of all 3-QSAT instances with SDRs,
particularly in the boundary case when $\left\lvert E\right\rvert=\left\lvert
V\right\rvert$. Unfortunately, this appears to be a difficult task (if not
potentially impossible, see comments about a “finite characterization” below).
We first give various characterizations involving intersecting families (i.e.
when each pair of edges has non-empty intersection). We then study the setting
of _linear_ hypergraphs (i.e. each pair of edges intersects in at most one
vertex), which are generally more complex. (For example, the set of edge-
intersection graphs of $3$-uniform linear hypergraphs is known not to have a
“finite” characterization in terms of a finite list of forbidden induced
subgraphs [NRSS82].) We study “extreme cases” of linear hypergraphs with SDRs,
such as the Fano plane and “tiling of the torus”, and in contrast to these two
examples, demonstrate a (somewhat involved) linear hypergraph we call the
iCycle which also satisfies the _Helly property_ (which generalizes the notion
of “triangle-free”). A main conclusion of this study is that even with
multiple additional restrictions in place (e.g. linear, Helly), the set of
$3$-uniform hypergraphs with SDRs remains non-trivial. To complement these
results, we show how to fairly systematically construct large linear
hypergraphs with $\left\lvert E\right\rvert=\left\lvert V\right\rvert$ without
SDRs. We hope this work highlights the potential complexity involved in
dealing with even the “simple” case of 3-QSAT with SDRs.

##### Discussion, previous work and open questions.

Regarding our parameterized algorithm, our notions of transfer filtrations and
blow-ups apply to _any_ instance of $k$-QSAT (and thus also777For the special
case of $k$-SAT, note that it is not _a priori_ clear that having a transfer
filtration with a small foundation suffices to solve the system trivially.
This is because the genericity assumption on constraints, which $k$-SAT
constraints do not satisfy, is required to ensure that any assignment to the
foundation propagates to all bits in the instance. Thus, the brute force
approach of iterating through all $2^{b}$ assignments to the foundation does
not obviously succeed. $k$-SAT), including $\textup{QMA}_{1}$-complete
instances. (For example, every $k$-uniform hypergraph has a trivial foundation
obtained by iteratively removing vertices until the resulting set contains no
edges. A key question is how _small_ the foundation and radius of the
filtration can be chosen for a given hypergraph, as our algorithm’s runtime
scales exponentially in these parameters; see Equation (10).) More precisely,
our techniques in Section 4, up to and including the Qualifier Lemma, apply to
arbitrary $k$-QSAT instances. If one also imposes generic constraints for an
arbitrary hypergraph, then the Surjectivity Lemma (Lemma 36) also holds. The
main question is when _local_ solutions to the qualifier constraints (which
act only on $b$ out of $n$ qubits) can be extended to _global_ solutions to
the entire $k$-QSAT instance. We answer this question affirmatively for the
non-trivial class of $k$-QSAT instances which satisfy the preconditions of
Theorem 38 (e.g. the semi-cycle, fir tree, crash, and any $k$-uniform
hypergraph with $b=\left\lvert V\right\rvert-\left\lvert E\right\rvert+1$),
obtaining exponential speedups in some cases in Section 4.4.

Moving to previous work, Quantum $k$-SAT was introduced by Bravyi [Bra06], who
gave an efficient (quartic time) algorithm for $2$-QSAT, and showed that
$4$-QSAT is QMA1-complete. Subsequently, Gosset and Nagaj [GN13] showed that
Quantum $3$-SAT is also QMA1-complete, and independently and concurrently,
Arad, Santha, Sundaram, Zhang [ASSZ16] and de Beaudrap, Gharibian [dBG16] gave
linear time algorithms for $2$-QSAT. The original inspiration for this paper
was the work of Laumann, Läuchli, Moessner, Scardicchio and Sondhi [LLM+10],
which showed _existence_ of a product state solution for any $k$-QSAT instance
with an SDR. Thus, the decision version of $k$-QSAT with SDRs is in NP and
trivially efficiently solvable. However, whether the search version (i.e.
compute an explicit satisfying assignment) is also in P remains open. Note the
question of whether the decision and search complexities of NP problems are
the same is a longstanding open problem in complexity theory; conditional
results separating the two are known (see e.g. Bellare and Goldwasser [BG94]).

In terms of classical $k$-SAT, as mentioned above, in stark contrast to
$k$-QSAT, solutions to $k$-SAT instances with an SDR can be trivially
computed. As for parameterized complexity, classically it is a well-
established field of study (see, e.g., [DF12] for an overview). The
parameterized complexity of SAT and $\\#$SAT, in particular, has been studied
by a number of works, such as [Sze04, FMR08, SS10, GHO13, STV15, PSS16,
GPST16], which consider a variety of parameterizations including based on
tree-width, modular tree-width, branch-width, clique-width, rank-width, and
incidence graphs which are interval bipartite graphs. Regarding parameterized
complexity of _Quantum_ SAT, as far as we are aware, our work is the first to
initiate a “formal” study of the subject; however, we should be clear that
existing works in Quantum Hamiltonian Complexity [Osb12, GHLS14] have long
implicitly used “parameterized” ideas (e.g. in tensor network contraction, the
bond dimension can be viewed as a parameter constraining the complexity of the
contraction).

We close with a number of open questions. Can ideas from classical
parameterized complexity be generalized to the quantum setting? We have
developed a number of tools herein for studying Quantum SAT — can these be
applied in more general settings, for example beyond the families of $k$-QSAT
instances considered in Theorem 38? The “parameters” in our results of Section
4 include the radius of a transfer filtration — whether a transfer filtration
(of a fixed type $b$) of _minimum_ radius can be computed efficiently,
however, is left open for future work. Similarly, it is not clear that given
$b\in{\mathbb{N}}$, the problem of deciding whether a given hypergraph $G$ has
a transfer filtration of type at most $b$ is in P. We conjecture, in fact,
that this latter problem is NP-complete. Finally, the question of whether
solutions to arbitrary instances of $k$-QSAT with SDRs can be computed
efficiently (recall they are guaranteed to exist [LLM+10]) remains open.

##### Organization.

Section 2 gives basic notation and definitions. Section 3 gives an efficient
algorithm for 3-QSAT with bounded occurrence of variables, which also
introduces the notions of transfer matrices (which are generalized via
transfer functions in Section 4). Our main result is given in Section 4, and
concerns a new parameterized complexity approach for solving $k$-QSAT. The
algorithm and its runtime, along with the study of asymptotic speedups, are
given in Section 4.4. Finally, Section 5 conducts a structural graph theoretic
study of hypergraphs with SDRs.

##  2 Preliminaries

##### Notation.

For complex Euclidean space $\mathcal{X}$, $\mathcal{L}(\mathcal{X})$ denotes
the set of linear operators mapping $\mathcal{X}$ to itself. For unit vector
$|\psi\rangle\in{\mathbb{C}}^{2}$, the unique orthogonal unit vector (up to
phase) is denoted $|\psi^{\perp}\rangle$, i.e.
$\mbox{$\langle\psi|\psi^{\perp}\rangle$}=0$.

We now give some definitions from graph theory, some of which are used
primarily in Section 5.

######  Definition 3 (Hypergraph).

A hypergraph is a pair $G=(V,E)$ of a set $V$ (vertices), and a family $E$
(edges) of subsets of $V$. If each vertex has degree $d$, we say $G$ is
$d$-regular. Alternatively, when convenient we use $V(G)$ and $E(G)$ to denote
the vertex and edge sets of $G$, respectively. A _simple_ hypergraph has no
repeated edges, i.e. if $e_{i}\subseteq e_{j}$, then $i=j$. We say $G$ is
$k$-uniform if all edges have size $k$.

######  Definition 4 (Chain [KS16], Figure 1).

A $k$-uniform hypergraph $G=(V,E)$ is a _chain_ if there exists a sequence
$(v_{1},v_{2},...,v_{l})\in V^{l}$ for $l\geq n$ such that (1) the sequence
contains all elements of $V$ at least once, (2) $v_{1}\neq v_{l}$, and (3)
$E=\bigcup_{1\leq i\leq l-k+1}e_{i}$ for distinct edges
$e_{i}={\left\\{v_{i},v_{i+1},...,v_{i+k-1}\right\\}}$. The length of the
chain $G$ is $m=l-k+1$.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$

Figure 1: (Top left) A chain. (Top right) A cycle. (Bottom middle) A
semicycle.

######  Definition 5 (Cycle [KS16], Figure 1).

A $k$-uniform hypergraph $G=(V,E)$ is a _cycle_ if there exists a sequence
$(v_{1},v_{2},...,v_{l})\in V^{l}$ for $l\geq n$ such that (1) the sequence
contains all elements of $V$ at least once, (2) for all $1\leq i\leq l$,
$e_{i}={\left\\{v_{i},v_{i+1},...,v_{i+k-1}\right\\}}$ are distinct edges in
$E$, where indices are understood modularly. The length of the cycle $G$ is
$m=l$.

######  Definition 6 (Semicycle [KS16], Figure 1).

A $k$-uniform hypergraph $G=(V,E)$ is a _semicycle_ if there exists a sequence
$(v_{1},v_{2},...,v_{l})\in V^{l}$ for $l\geq n$ such that (1) the sequence
contains all elements of $V$ at least once, (2) $v_{1}=v_{l}$, and (3) for all
$1\leq i\leq l-k+1$, $e_{i}={\left\\{v_{i},v_{i+1},...,v_{i+k-1}\right\\}}$
are distinct edges of $G$. The length of the semicycle is $m=l-k+1$.

######  Definition 7 (Tight star [KS16], Figure 9).

A $k$-uniform hypergraph $G=(V,E)$ is a _tight star_ if there exists a set of
$k-1$ vertices $S$, such that the intersection of any pair of edges is
precisely $S$.

######  Definition 8 ($t$-stacked set).

Let $G=(V,E)$ be a $k$-uniform hypergraph. A subset $S\subseteq E$ of $t$
edges is called a _$t$ -stacked set_ if every edge in $S$ is incident to the
same $k$ vertices in $V$, i.e. $\left\lvert\bigcup_{e\in S}e\right\rvert=k$.

##  3 Quantum SAT with bounded occurrence of variables

In this section, we study $k$-QSAT when each qubit occurs in at most two
constraints. For this, we first recall tools from the study of Quantum $2$-SAT
[Bra06, LMSS10, dBG16]. Recall that throughout this paper, each clause is
assumed to be rank $1$ (in general, however, one can “stack” multiple rank $1$
clauses on a set of vertices to simulate a higher rank clause).

##### Transfer matrices, chain reactions, and cycle matrices.

For any rank-$1$ constraint
$\Pi_{i}=|\psi\rangle\\!{\langle\psi|}\in\mathcal{L}(({\mathbb{C}}^{2})^{\otimes
k})$, consider Schmidt decomposition
$|\psi\rangle=\alpha|a_{0}\rangle|b_{0}\rangle+\beta|a_{1}\rangle|b_{1}\rangle$,
where $|a_{i}\rangle\in({\mathbb{C}}^{2})^{\otimes(k-1)}$ lives in the Hilbert
space of the first $k-1$ qubits and $|b_{i}\rangle\in{\mathbb{C}}^{2}$ the
last qubit. Then, the _transfer_ matrix $T_{\psi}:({\mathbb{C}}^{2})^{\otimes
k-1}\mapsto{\mathbb{C}}^{2}$ is given by $T_{\psi}=\beta|b_{0}\rangle{\langle
a_{1}|}-\alpha|b_{1}\rangle{\langle a_{0}|}$. In words, given any assignment
$|\phi\rangle$ to the first $k-1$ qubits, if
$T_{\psi}|\phi\rangle\in{\mathbb{C}}^{2}$ is non-zero, then it is the _unique_
assignment to qubit $k$ (given $|\phi\rangle$ on qubits $1$ to $k-1$) which
satisfies $\Pi_{i}$.

In the special case of $k=2$, transfer matrices are particularly useful.
Consider first a $2$-QSAT interaction graph (which is a $2$-uniform
hypergraph, or just a graph) $G=(V,E)$ which is a path, i.e. a sequence of
edges $e_{1}=(v_{1},v_{2}),e_{2}=(v_{2},v_{3}),\ldots,e_{m}=(v_{m-1},v_{m})$
for distinct $v_{i}\in V$, and where edge $e_{i}$ corresponds to constraint
$|\psi_{i}\rangle$. Then, any assignment $|\phi\rangle\in{\mathbb{C}}^{2}$ to
qubit $1$ _induces a chain reaction (CR)_ in $G$, meaning qubit $2$ is
assigned $T_{\psi_{1}}|\phi\rangle$, qubit $3$ is assigned
$T_{\psi_{2}}T_{\psi_{1}}|\phi\rangle$, and so forth. If this CR terminates
before all qubits labelled by $V$ receive an assignment, which occurs if
$T_{\psi_{i}}|\phi^{\prime}\rangle=0$ for some $i$, this means that constraint
$i$ (acting on qubits $i$ and $i+1$) is satisfied by the assignment
$|\phi^{\prime}\rangle$ to qubit $i$ alone, and no residual constraint is
imposed on qubit $i+1$. Thus, the graph $G$ is reduced to a path
$e_{i+1},\ldots,e_{m}$. In this case, we say the CR is _broken_. Note that if
$G$ is a path, then it is a satisfiable $2$-QSAT instance with a product state
solution.

Finally, consider a $2$-QSAT instance whose interaction graph $G$ is a cycle
$C=(v_{1},\ldots,v_{m+1})$ with $m$. Then, a CR induced on vertex $v_{1}$ with
any assignment $|\psi\rangle\in{\mathbb{C}}^{2}$ will in general propagate
around the cycle and impose a consistency constraint on $v_{1}$. Formally,
denote the product $T_{C}=T_{\psi_{m}}\cdots
T_{\psi_{1}}\in\mathcal{L}({\mathbb{C}}^{2})$ as the _cycle matrix_ of $C$.
Then, if the cycle matrix is not the zero matrix, it be shown that the
satisfying assignments for the cycle are precisely the eigenvectors of
$T_{C}$. (If $T_{C}=0$, any assignment on $v_{1}$ will only propagate
partially around the cycle, thus decoupling the cycle into two paths.) Thus,
if $G$ is a cycle, then it also has a product state solution.

In this section, when we refer to “solving the path or cycle”, we mean
applying the transfer matrix techniques above to efficiently compute a product
state solution to the path or cycle.

#####  $k$-QSAT with bounded occurence of variables.

We now restate and prove Theorem 1. Subsequently, we demonstrate the algorithm
on an example (Figure 3) and discuss its applicability more generally. Section
3.1 shows the connection between Theorem 1 and $k$-QSAT with SDRs.

######  Theorem 1.

There exists a polynomial time classical algorithm which, given an instance
$\Pi$ of $k$-QSAT in which each variable occurs in at most two clauses,
outputs a satisfying product state if $\Pi$ is satisfiable, and otherwise
rejects. Moreover, the algorithm works for clauses ranging from $1$-local to
$k$-local in size.

###### Proof.

We begin by setting terminology. Let $\Pi$ be an instance of $k$-QSAT with
$k$-uniform interaction graph $G=(V,E)$. For any clause $c$, let $Q_{c}$
denote the set of qubits acted on $c$, i.e. $Q_{c}$ is the edge in $G$
representing $c$. We say $c$ is _stacked_ if $Q_{c}$ is contained within
another edge/clause $Q_{c^{\prime}}$, i.e. if there exists $c^{\prime}\neq c$
such that $Q_{c}\subseteq Q_{c^{\prime}}$. For a qubit $v$, we use shorthand
$|v\rangle$ to denote the current assignment from ${\mathbb{C}}^{2}$ to $v$.
For a clause $c$, $|c\rangle$ denotes the bad subspace of $c$, i.e. clause $c$
is given by rank-$1$ projector $I-|c\rangle\\!{\langle c|}$. The set of
clauses vertex $v$ appears in is denoted $C_{v}$. For any assignment
$|v\rangle$, we introduce shorthand $S_{|v\rangle}={\left\\{\mbox{$\langle
v|c\rangle$}\mid c\in
C_{v}\right\\}}\subseteq\bigcup_{i=0}^{k-1}{\mathbb{C}}^{2^{i}}$, where recall
$c$ can be a clause on $1,\ldots,k$ qubits, and we implicitly assume ${\langle
v|}$ acts as the identity on the qubits of $c$ which are not $v$. For example,
if $c$ acts on qubits $v,w,x$, then $\mbox{$\langle v|c\rangle$}=({\langle
v|}\otimes I_{w,x})|c\rangle\in{\mathbb{C}}^{4}$ is the residual constraint on
qubits $w,x$, given assignment $|v\rangle$ to $v$. Thus, $S_{|v\rangle}$ is
the set of constraints we obtain by taking the clauses in $C_{v}$, and
projecting down qubit $v$ in each clause onto assignment $|v\rangle$. As a
result, the clauses in $S_{|v\rangle}$ no longer act on $v$. The algorithm we
design will satisfy that the only possible element of ${\mathbb{C}}$ in
$S_{|v\rangle}$ is $0$, which can only be obtained by projecting a constraint
$|c\rangle\in{\mathbb{C}}^{2}$ onto its orthogonal complement to satisfy it;
thus, we can assume without loss of generality that
$S_{|v\rangle}\subseteq{\left\\{\mbox{$\langle v|c\rangle$}\mid c\in
C_{v}\right\\}}\subseteq\bigcup_{i=1}^{k-1}{\mathbb{C}}^{2^{i}}$. Finally, we
say two $1$-local clauses $|c\rangle,|c^{\prime}\rangle\in{\mathbb{C}}^{2}$
_conflict_ if $|c\rangle$ and $|c^{\prime}\rangle$ are linearly independent
(i.e. $|c\rangle\\!{\langle c|}+|c^{\prime}\rangle\\!{\langle c^{\prime}|}$
has an empty null space, meaning there is no satisfying assignment).

The algorithm proceeds as follows. Let $\Pi$ satisfy the conditions of our
claim. For clarity, any time a CR on a path is broken by a transfer matrix
$T_{\psi}$ on edge $(u,v)$, i.e. $T_{\psi}|u\rangle=0$, we shall implicitly
assume we continue by choosing assignment $|0\rangle$ on $v$ to induce a new
CR and continue solving the path. (This is important for the correctness
analysis later in which Step 3 must not create a $1$-local constraint.)

##### Statement of algorithm.

The intuitive idea behind the algorithm is to “partially reduce” $\Pi$ to a
$2$-QSAT instance, and use the transfer matrix techniques outlined above to
solve this segment. Combining this with a new notion of fusing CRs, the
technique can be applied iteratively to reduce $k$-local constraints to
$2$-local ones until the entire instance is solved.

_Algorithm A._

  1. 1.

While there exists a $1$-local constraint $c$ acting on some qubit $v$:

    1. (a)

If $c$ conflicts with another $1$-local clause on $v$, reject. Else, set
$|v\rangle=|c^{\perp}\rangle\in{\mathbb{C}}^{2}$. Set888Setting
$C_{v}=S_{|v\rangle}$ means we update all clauses $c$ acting on $v$ by
projecting qubit $v$ of $c$ onto $|v\rangle$. Note that each $v$ does not keep
a local copy of $C_{v}$, i.e. all clauses are referenced in a global fashion.
$C_{v}=S_{|v\rangle}$, and remove $v$ from $\Pi$.

  2. 2.

While there exists a qubit $v$ appearing only in clauses of size at least
$k^{\prime}\geq 3$:

    1. (a)

Set $|v\rangle=|0\rangle$ and $C_{v}=S_{|v\rangle}$. Remove $v$ from $\Pi$.

  3. 3.

While there exists a $2$-local clause:

    1. (a)

If there exists a stacked $2$-local clause $c$, i.e. $c^{\prime}\neq c$ such
that $Q_{c}\subseteq Q_{c^{\prime}}$:

      1. i.

If $Q_{c}=Q_{c^{\prime}}$, remove the qubits $c$ acts on, and set their values
to satisfy $c$ and $c^{\prime}$.

      2. ii.

Else, $Q_{c}\subset Q_{c^{\prime}}$. Thus, $c^{\prime}$ is $k^{\prime}$-local
for $3\leq k^{\prime}\leq k$. Set the values of the qubits in $Q_{c}$ so as to
satisfy $c$. This collapses $c^{\prime}$ to a $(k^{\prime}-2)$-local
constraint on qubits $Q_{c^{\prime}}\setminus Q_{c}$.

        1. A.

If $k^{\prime}-2=1$, then $c^{\prime}$ has been collapsed to a $1$-local
constraint on some vertex $v\in Q_{c^{\prime}}\setminus Q_{c}$, creating a
path rooted at $v$. Set $v$ so as to satisfy $c^{\prime}$, and use a CR to
solve the resulting path until either the path ends, or a
$k^{\prime\prime}$-local constraint is hit for $3\leq k^{\prime\prime}\leq
k^{\prime}$. In the latter case (Figure 2, Left), the $k^{\prime\prime}$-local
constraint is reduced to a $(k^{\prime\prime}-1)$-local constraint and we
return to the beginning of Step 3.

    2. (b)

Else, pick an arbitrary $2$-local clause $c$ acting on variables $v_{1}$ and
$v_{2}$. Then, $v_{1}$ ($v_{2}$) is the start of a path $h_{1}$ ($h_{2}$)
(e.g., Figure 2, Middle).

      1. i.

If the path forms a cycle from $v_{1}$ to $v_{2}$, use the cycle matrix to
solve the cycle. Remove the corresponding qubits and clauses from $\Pi$.

      2. ii.

Else, set $v_{1}$ and $v_{2}$ so as to satisfy $c$. Solve the resulting paths
$h_{1}$ ($h_{2}$) until a $k^{\prime}$-local ($k^{\prime\prime}$-local)
constraint $l_{1}$ ($l_{2}$) is hit for $3\leq k^{\prime}\leq k$ ($3\leq
k^{\prime\prime}\leq k$). If both $l_{1}$ and $l_{2}$ are found:

        1. A.

If $l_{1}=l_{2}$ (i.e. $k^{\prime}=k^{\prime\prime}$) and $k^{\prime}-2=1$,
then fuse the paths $h_{1}$ and $h_{2}$ into a new path beginning at the qubit
in $l_{1}$ which is not in $h_{1}$ or $h_{2}$ (e.g., Figure 2, Right).
Iteratively solve the resulting path until a $k^{\prime}$-local constraint is
hit for $3\leq k^{\prime}\leq k$.

  4. 4.

If any qubits are unassigned, set their values to $|0\rangle$.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$

Figure 2: (Left) Solving the path rooted at $v_{1}$ via CR allows us to
satisfy clauses $(v_{1},v_{2})$ and $(v_{2},v_{3})$, and since $v_{3}$
receives an assignment in this process, the clause $(v_{3},v_{4},v_{5})$ is
projected onto a $2$-local residual clause on $(v_{4},v_{5})$. The CR then
stops. (Middle) Letting $c$ denote the clause on $(v_{2},v_{3})$, $v_{2}$ is
the start of a path $(v_{2},v_{1},\ldots)$ to the left, and $v_{3}$ is the
start of a path $(v_{3},v_{4},\ldots)$ to the right. (Right) Inducing CRs on
$v_{1}$ and $v_{7}$, we eventually assign values to $v_{3}$ and $v_{5}$. This
collapses the $3$-local clause on $(v_{3},v_{4},v_{5})$ into a $1$-local
clause on $v_{4}$ with a unique satisfying assignment, which in turn induces a
new CR starting at $v_{4}$. Thus, the two CR’s are “fused” into one CR through
the $3$-local clause.

An illustration of algorithm A on an example input is given after this proof
(see also Figure 3). It is clear that the algorithm runs in polynomial time.
We now prove correctness.

Correctness. In Step $1$, any qubit $v$ acted on by a $1$-local constraint $c$
has only one possible satisfying assignment $|c^{\perp}\rangle$ (up to phase).
Thus, if there are conflicting $1$-local clauses acting on $v$, we must
reject; else, we must set $v$ to $|c^{\perp}\rangle$, and subsequently
simplify all remaining clauses acting on $v$ (i.e. map $C_{v}$ to
$S_{|v\rangle}$). Note that since $v$ is removed at this point, we can never
have a conflict on it in a future iteration of the algorithm.

If we reach Step 2, we claim that $\Pi$ is satisfiable. To show this, note
first that each time Step $3$ is run, if there exists a $2$-local clause, then
at least one new clause is satisfied and subsequently removed from $\Pi$.
Thus, in order to prove that $\Pi$ is satisfiable, it suffices to show that
the following loop invariant holds.

_Loop Invariant:_ Before each execution of Step $3$, either $\Pi$ contains
some $2$-local clause and no $1$-local clauses, or $\Pi$ contains no clauses.

Two notes are in order here. First, the invariant’s constraint on the absence
of $1$-local clauses is necessary, as otherwise we are not guaranteed that
paths can be iteratively solved as in Step 3(a)(ii)(A). Second, the invariant
implies that once the algorithm reaches Step $4$, all clauses must have been
satisfied. Thus, all unused qubits at that point can be set arbitrarily.

We now show that the loop invariant holds throughout the execution of the
algorithm. First, since after Step $1$, $\Pi$ contained no $1$-local
contraints, and since in Step $2$ we only reduce $k^{\prime}$-local clauses to
$k^{\prime\prime}$-local ones for $k^{\prime\prime}\geq 2$, it follows that
the invariant holds the first time Step $3$ is run.

We next show that if the invariant holds just before Step $3$ is run, then it
also holds after Step $3$ is run. We divide the analysis into cases depending
on which line of Step 3 is run.

  * •

(Step 3(a)(i)) Since each qubit appears in at most $2$ clauses by assumption,
it holds that $c$ and $c^{\prime}$ must be disjoint from all other clauses in
$\Pi$. Thus, the removal of $c$ and $c^{\prime}$ does not create any $1$-local
constraints. Moreover, if subsequently $\Pi$ is non-empty, then it is not the
case that all remaining clauses are $k^{\prime}$-local for $3\leq
k^{\prime}\leq k$. This is because otherwise the set of clauses disjoint from
$c$ and $c^{\prime}$ must contain a variable involved only in clauses of size
at least $k^{\prime}\geq 3$, contradicting Step 2. Thus, the loop invariant
holds. (Aside: If $c$ and $c^{\prime}$ act on vertices $u$ and $v$, a
satisfying assignment to $c$ and $c^{\prime}$ can be computed by thinking of
$(u,v)$ and $(v,u)$ as a cycle, and subsequently solving the cycle using the
cycle matrix technique.)

  * •

(Step 3(a)(ii)) Once $c$ and the variables it acts on are removed, we have a
$(k^{\prime}-2)$-local constraint on $c^{\prime}$. Thus, if $k^{\prime}-2=1$,
this induces a CR on the incident path of $2$-local constraints on
$c^{\prime}$ (this path may have length $0$). Note that this path can never
loop back to $c^{\prime}$, nor can it contain a cycle, as otherwise a variable
would appear in more than $2$ clauses. Thus, either the path consists solely
of $2$-local constraints, which are all satisfied via the CR (recall we assume
that any broken CR’s are continued automatically by assignment $|0\rangle$ to
the next vertex in the path to induce a new CR), or eventually we hit a
$k^{\prime\prime}$-local constraint for $k^{\prime\prime}\geq 3$, which we now
collapse to a $(k^{\prime\prime}-2)$-local constraint; call the latter $\phi$.
Thus, since the CR removes any possible $1$-local constraint on $c^{\prime}$
and creates no further $1$-local constraints, no $1$-local constraints exist
after Step 3.

Also, on the existence of a $2$-local clause after Step $3$ (assuming clauses
remain): If the path above consisted solely of $2$-local constraints, then the
CR removed a connected component of the interaction graph, in which case the
remaining connected components must contain a $2$-local clause (otherwise, we
again contradict Step 2). If the path encountered a $k^{\prime\prime}$-local
clause for $k^{\prime\prime}=3$, on the other hand, the CR itself created a
$2$-local clause. Similarly, if $k^{\prime\prime}\geq 4$, then $\phi$ is at
least $3$-local, and we claim that at least one of the vertices of $\phi$ must
be incident on a $2$-local edge. Indeed, otherwise we again contradict Step 2.
Thus, the loop invariant holds.

  * •

(Step 3(b)(i)) Since any variable occurs in at most $2$ clauses, the cycle
must be disjoint from all other clauses in $\Pi$. Thus, its removal does not
create a $1$-local constraint. That there must exist a $2$-local constraint if
$\Pi$ is non-empty now follows by similar arguments as in Steps 3(a)(i) and
3(a)(ii).

  * •

(Step 3(b)(ii)) There are $2$ possible scenarios: Both $h_{1}$ and $h_{2}$ are
disjoint paths, or they intersect on a $k^{\prime}$-local clause. The first
case is analogous to Step 3(a)(ii)’s analysis. In the second case, suppose
$h_{1}$ and $h_{2}$ intersect on clause $c$. Then, since the paths do not form
a cycle (otherwise, we would be in Step 3(b)(i)), $c$ must be
$k^{\prime}$-local for $k^{\prime}\geq 3$. If $k^{\prime}-2=1$, let $v$ denote
the qubit in $c$ not acted on by $h_{1}$ or $h_{2}$. Then, solving the paths
$h_{1}$ and $h_{2}$ collapses $c$ into a $1$-local constraint on $v$. But
this, in turn, creates a new path rooted at $v$, whose analysis follows from
Step 3(a)(ii) above. If $k^{\prime}-2>1$, the CR stops once $c$ is collapsed
to a new clause of size at least $2$. That a $2$-local clause still exists at
this point (assuming the remaining instance is non-empty) follows by the
argument of Step 3(a)(ii).

This concludes the proof. ∎

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$$v_{9}$$v_{10}$$v_{11}$$v_{7}$$v_{8}$$v_{9}$$v_{10}$$v_{11}$$v_{8}$$v_{9}$$v_{10}$$v_{11}$

$v_{10}$$v_{11}$

Figure 3: (Top left) The initial $3$-QSAT instance, denoted $H(G)$ for the
purposes of this example, and where each hyperedge is an arbitrary (rank $1$)
constraint. (Top middle) The hypergraph obtained after applying Step 2 to
vertices $v_{1},v_{2},v_{3},v_{4},v_{5},v_{6}$. (Top right) The hypergraph
obtained by applying Step 2 to vertex $v_{7}$. (Bottom left) The hypergraph
obtained by applying Step 3bii to edge $(v_{8},v_{9})$. Applying Step 3bii to
edge $(v_{10},v_{11})$ would thus reduce us to a $2$-QSAT cycle, which is then
solved via Step 3bi. Note the order of vertices/edges processed in this
example is arbitrary, and was chosen here simply for symmetry. (Bottom right)
A pseudo-line graph corresponding to the hypergraph in the top left image.

##### An example and applicability.

Having shown Theorem 1, we make two remarks.

  1. 1.

(Demonstration) We illustrate in Figure 3 how algorithm A repeatedly partially
reduces parts of a $3$-QSAT instance to $2$-QSAT instances (this particular
example does not require fusing of chain reactions).

  2. 2.

(Applicability) Whereas the class of hypergraphs considered in Theorem 1 may
seem _a priori_ rather restricted, as a “proof of concept” we observe that the
example of Figure 3 can be generalized to an entire family of non-trivial
examples to which Theorem 1 applies. (We focus on $3$-uniform hypergraphs for
simplicity.) Specifically, encode the hypergraph $H(G)$ in the top left of
Figure 3 by a graph $G=(V_{d},V_{c},E)$ reminiscent of a line graph, which we
call a _pseudo-line graph_ , as depicted in the bottom right of Figure 3. $G$
is defined as follows. Each disc vertex $s_{i}\in V_{d}$ corresponds to a red
hyperedge (color online; e.g. hyperedge ${\left\\{v_{7},v_{8},v_{9}\right\\}}$
is red). Each cross vertex $t_{i}\in V_{c}$ corresponds to a pair of green
hyperedges (e.g. the hyperedges containing $v_{6}$) which intersect on a set
of size $2$. An edge in $G$ means the two hyperstructures corresponding to
each end point of the edge intersect in precisely one element (since each
vertex has degree $2$, this is well-defined). That each disc and cross vertex
have degree $3$ and $2$, respectively, ensures the corresponding hypergraph,
$H(G)$, is $2$-regular (we assume $G$ has no self-loops or parallel edges). It
is not difficult to see that any such pseudo-line graph $G$ gives rise to a
$2$-regular $3$-uniform hypergraph $H(G)$, thus yielding an entire family of
$3$-QSAT instances to which Theorem 1 applies. Finally, we connect this
example with the notion of _transfer filtrations_ in Section 4. Namely, the
hypergraph $H(G)$ in Figure 3 is of transfer type at most $12$ — for all pairs
of distinct hyperedges $e_{i},e_{j}$ with $e_{i}\cap e_{j}=2$, simply add
$e_{i}\cap e_{j}$ to the foundation.

###  3.1 Connection to $k$-QSAT instances with a SDR

Recall that the initial motivation for this study was the open question
[LLM+10] of constructing satisfying assignments to $k$-QSAT instances which
have a system of distinct representatives (SDR). We now show that the class of
$k$-QSAT instances solved by Theorem 1 is closely related to this motivation.

Specifically, note that the only line of algorithm A which can reject is 1a,
and this is due to the presence of $1$-local clauses. Since any $k$-QSAT
instance with an SDR is satisfiable (by a product state) [LLM+10], it follows
that hypergraphs with hyperedges of size $1$ in general cannot have SDRs.
Indeed, consider the hypergraph with edge set
$E={\left\\{{\left\\{1,2,3\right\\}},{\left\\{1\right\\}},{\left\\{2\right\\}},{\left\\{3\right\\}}\right\\}}$
— clearly, this has no SDR, and if we set the clauses to (respectively)
project onto $|000\rangle$, $|1\rangle$, $|1\rangle$, and $|1\rangle$, then
the corresponding $3$-QSAT instance is unsatisfiable.

However, if our $k$-QSAT instance has no $1$-local clauses in Theorem 1, then
algorithm A always produces a (product-state) solution. We now show that this
is no coincidence — such hypergraphs must have an SDR. Thus, Theorem 1 answers
the open question of [LLM+10] for all $k$-QSAT instances in which (1) there
are no $1$-local clauses and (2) each qubit occurs in at most $2$ clauses.

######  Theorem 2.

Let $G=(V,E)$ be a hypergraph with all hyperedges of size at least $2$, and
such that each vertex has degree at most $2$. Then, $G$ has an SDR.

###### Proof.

The claim is vacuously true if $G$ is empty; thus, assume $G$ is non-empty. We
claim the following (poly-time) algorithm constructs an SDR.

  1. 1.

While there exists a pair of distinct edges $e_{i},e_{j}\in E$ such that
$\left\lvert e_{i}\cap e_{j}\right\rvert\geq 2$:

    1. (a)

Pick an arbitrary pair of distinct vertices $v_{i},v_{j}\in e_{i}\cap e_{j}$.
Match $v_{i}$ to $e_{i}$ and $v_{j}$ to $e_{j}$, and remove
$v_{i},v_{j},e_{i},e_{j}$ from $G$.

  2. 2.

While there exist vertices $v$ of degree $1$ in some hyperedge $c_{v}$, match
$v$ to $c_{v}$ and remove $v$ and $c_{v}$.

  3. 3.

Remove any vertices of degree $0$.

  4. 4.

Let $G^{\prime}$ denote the remaining hypergraph. (We assume $G^{\prime}$ is
connected; if not, simply repeat the following steps on each connected
component.) Construct its line graph $L$ (defined in proof of correctness
below). Find a cycle $C$ in $L$, and let $v$ be an arbitrary vertex on $C$.

  5. 5.

(Build a “reverse SDR” on $L$) Run a depth-first search (DFS) rooted at $v$ on
$L$, with the following two modifications: (1) Each time an edge $x=(u,w)$ is
used to get to a previously unseen vertex $w$, add $2$-tuple $(w,x)$ to set
$M\subseteq V(L)\times E(L)$. (2) When the DFS begins, do not mark the root
$v$ as having been “seen”. (In other words, $v$ should only be marked as
“seen” once some edge $(w,v)$ is used in the DFS.)

  6. 6.

(Convert the “reverse” SDR on $L$ to an SDR on $G^{\prime}$) For each
$(w,x)\in M$:

    1. (a)

Suppose $x=(u,w)$ for some $u\in V(L)$. Then, let $e_{u}$ and $e_{w}$ denote
the hyperedges in $G^{\prime}$ corresponding to $u$ and $w$, respectively.
Match $e_{w}$ to the unique element of $e_{u}\cap e_{w}$.

##### Correctness.

We analyze each step in sequence.

  1. 1.

(Step 1) Since by assumption $v_{i}$ and $v_{j}$ have degree at most $2$, they
only appear in edges $e_{i}$ and $e_{j}$. Thus, we can safely match them to
$e_{i}$ and $e_{j}$, respectively, and remove $v_{i},v_{j},e_{i},e_{j}$.

  2. 2.

(Steps 2 and 3) Since $v$ occurs only in $c_{v}$, we can safely match it to
$c_{v}$ and remove $v$ and $c_{v}$.

  3. 3.

(Step 4) After Steps 1, 2, and 3, $G^{\prime}$ has two properties: (a) each
pair of edges intersects in at most one vertex, and (b) each vertex has degree
precisely $2$. By property (a), the “usual” (i.e. we do not need to
distinguish between different intersection sizes between edges) definition of
line graph can be applied to $G^{\prime}$ to construct $L$: Each hyperedge of
$G^{\prime}$ is a vertex in $L$, and two distinct vertices $u$ and $v$ in $L$
are neighbors if and only if their corresponding hyperedges in $G^{\prime}$
intersect.

Moreover, by properties (a) and (b) of $G^{\prime}$, each vertex of $L$ has
degree at least $2$. It follows that $L$ contains a cycle $C$ (e.g. since
summing degrees on each vertex yields there are at least as many edges in $L$
as vertices, and $L$ is connected by the assumption that $G^{\prime}$ is
connected).

  4. 4.

(Step 5) Since a DFS sees each vertex (at least) once, and since the first
time a vertex $w$ is seen it must be that the edge $x=(u,w)$ just used to get
to $w$ must have been used for the first time, it follows that no other
$2$-tuple in $M$ contains $x$ or $w$. Moreover, as stated in Step 5, note that
the root $v$ of the DFS is not marked until some edge $(w,v)$ is used; the
latter is guaranteed to happen since (1) we chose $v$ to lie on a cycle $C$,
and (2) if the two edges on the cycle $C$ which $v$ is incident on are
${\left\\{w,v\right\\}}$ and ${\left\\{v,w^{\prime}\right\\}}$, then by
definition of a DFS at least one of them will be traversed in direction
$(w,v)$ or $(w^{\prime},v)$ (as opposed to both being traversed in directions
$(v,w)$ and $(v,w^{\prime})$; note this property holds since we use a DFS
instead of a breadth-first search). It follows that each vertex $w$ of $L$
appears in precisely one $2$-tuple of $(w,x)\in M$. We conclude that $M$ is a
“reverse SDR” for $L$, by which we mean each _vertex_ of $L$ is matched with a
unique _edge_ of $L$ (whereas our desired SDR for hypergraph $G$ is supposed
to match each _hyperedge_ to a unique _vertex_ 999For further clarity, the
distinction is that in a reverse SDR, there may be more edges in the graph
than vertices, whereas in an SDR, there may be more vertices than edges.).

  5. 5.

(Step 6) This step converts each two-tuple in $M$ to a matched hyperedge
$e_{w}$ and vertex in $v\in e_{u}\cap e_{w}$. Note that $\left\lvert e_{u}\cap
e_{w}\right\rvert=1$ by property (a) of $G^{\prime}$. Since $M$ is a “reverse”
SDR, it follows that the matching produced by Step 6 completes the desired
SDR.

∎

##  4 Quantum SAT and parameterized algorithms

We next develop a parameterized algorithm for computing an explicit (product
state) solution to a non-trivial class of $k$-QSAT instances (Theorem 38).
Although the inspiration stems from algebraic geometry (AG), we generally
avoid AG terminology to increase accessibility. For those versed in the topic,
however, we include a brief overview of the ideas of this section in AG terms
at the end of Section 4.3. The final algorithm and its runtime, along with the
study of asymptotic speedups, are given in Section 4.4.

###  4.1 The transfer type of a hypergraph

We begin by defining the notion of _transfer type_ of a hypergraph.

######  Definition 9.

A hypergraph $G=(V,E)$ is of transfer type $b$ if there exists a chain of
subhypergraphs (denoted a transfer filtration of type $b$) $G_{0}\subseteq
G_{1}\subseteq\cdots\subseteq G_{m}=G$ and an ordering of the edges
$E(G)=\\{E_{1},\dots,E_{m}\\}$ such that

  1. 1.

$E(G_{i})=\\{E_{1},\ldots,E_{i}\\}$ for each $i\in\\{0,\ldots,m\\}$,

  2. 2.

$|V(G_{i})|\leq|V(G_{i-1})|+1$ for each $i\in\\{1,\ldots,m\\}$,

  3. 3.

if $|V(G_{i})|=|V(G_{i-1})|+1$, then $V(G_{i})\setminus V(G_{i-1})\subseteq
E_{i}$,

  4. 4.

$|V(G_{0})|=b$, where we call $V(G_{0})$ the _foundation_ ,

  5. 5.

and each edge of $G$ has at least one vertex not in $V(G_{0})$.

In other words, a transfer filtration of type $b$ builds up $G$ iteratively by
choosing $b$ vertices as a “foundation”, and in each iteration adding
precisely one new edge $E_{i}$ and _at most_ one new vertex. If a new vertex
is added in iteration $i$, condition (3) says it must be in edge $E_{i}$ added
in iteration $i$.

######  Example 10 (Running example).

We now introduce a hypergraph $G$ which will serve as a running example to
concretely illustrate the ideas of this section. Let $V(G)=\\{1,2,3,4\\}$ with
edges $E_{1}=\\{1,2,3\\}$, $E_{2}=\\{1,2,4\\}$, $E_{3}=\\{1,3,4\\}$ and
$E_{4}=\\{2,3,4\\}$. By Definition 5, $G$ is a $3$-uniform cycle. Consider
hypergraphs $G_{0},G_{1},G_{2},G_{3}$ such that $V(G_{0})=\\{1,2\\}$,
$V(G_{1})=\\{1,2,3\\}$, $V(G_{2})=V(G_{3})=V(G_{4})=V(G)$,
$E(G_{0})=\emptyset$ and $E(G_{j})=\\{E_{1},\ldots,E_{j}\\}$ for $j=1,2,3$.
Then $G_{0}\subseteq G_{1}\subseteq G_{2}\subseteq G_{3}\subseteq G_{4}=G$ is
a transfer filtration of type $2$. In particular $G_{2}$ is a chain and
$G_{3}$ is a semicycle in the sense of Definition 4 and Definition 6,
respectively.

######  Remark 11.

Let $G$ be a $k$-uniform hypergraph of transfer type $b$. Since $G_{1}$ has
exactly one edge, then $b\geq k-1$.

######  Example 12.

The tight line graph [KS16] of a $k$-uniform hypergraph $G$ is the
(undirected) graph $L(G)$ with vertices labelled by $E(G)$ and edges
$\\{(E_{i},E_{j})\mid E_{i},E_{j}\in E(G)\text{ and }\left\lvert E_{i}\cap
E_{j}\right\rvert=k-1\\}$. (This generalizes the notion of a line graph; a yet
more general definition, called an _edge intersection graph_ , is mentioned in
Section 5, which adds an edge $(E_{i},E_{j})$ so long as $E_{i}\cap
E_{j}\neq\emptyset$.) A $k$-uniform hypergraph $G$ is line graph connected if
its tight line graph is connected. Arguing as in the proof of Lemma 1 of
[KS16], it is easy to show that every $k$-uniform line graph connected
hypergraph with no isolated vertices has transfer type $k-1$. (An _isolated_
vertex is not contained in any hyperedge.) To see this, pick an edge
$E_{i_{1}}$, set $G_{1}$ to be the hypergraph induced by $E_{i_{1}}$, and
choose $G_{0}$ to be any subset of $G_{1}$ of cardinality $k-1$. Since the
vertex of $L(G)$ corresponding to $E_{i_{1}}$ is not isolated, there exists
another edge $E_{i_{2}}$ such that $|E_{i_{1}}\cap E_{i_{2}}|=k-1$. Let
$G_{2}$ be the hypergraph with vertices $E_{i_{1}}\cup E_{i_{2}}$ and edges
$E_{i_{1}}$, $E_{i_{2}}$. Since the induced subgraph with vertices $E_{i_{1}}$
and $E_{i_{2}}$ is not a connected component of $L(G)$ this procedure can be
iterated until the required transfer filtration is constructed.

######  Example 13 (Running example).

Let $G$ be the $3$-uniform cycle of Example 10. Then $L(G)$ is a cycle of
length $4$, in the usual graph-theoretical sense. In particular $G$ is line
graph connected.

######  Example 14.

Let $G$ be a $k$-uniform hypergraph with no isolated vertex. Suppose that
$L(G)$ has $c$ connected components and apply the construction of Example 12
to each connected component. Taking the union of the corresponding $G_{0}$
sets (one for each connected component) and adding the edges one at the time,
we obtain a transfer filtration of type at most $c(k-1)$ on $G$. More
generally, isolated vertices can be taken into account by adding them to the
$0$-th term of the filtration. Hence every $k$-uniform hypergraph has transfer
type at most $c(k-1)+i$ where $c$ is the number of connected components of
$L(G)$ and $i$ is the number of isolated vertices of $G$.

######  Example 15.

Let $a_{1},\ldots,a_{k-1}\geq 2$ be integers. Consider the hypergraph $G$ with
vertices
$(\mathbb{Z}/a_{1}\mathbb{Z})\times\cdots\times(\mathbb{Z}/a_{k-1}\mathbb{Z})$
and edges of the form

$\\{(i_{1},\ldots,i_{k-1}),(i_{1}+1,\ldots,i_{k-1}),(i_{1},i_{2}+1,\ldots,i_{k-1}),\ldots,(i_{1},\ldots,i_{k-1}+1)\\}$

for each $(i_{1},\ldots,i_{k-1})\in V(G)$. Let $G_{0}$ be the subhypergraph of
$G$ with vertices
$(\mathbb{Z}/a_{1}\mathbb{Z})\times\cdots\times(\mathbb{Z}/a_{k-2}\mathbb{Z})\times\\{0\\}$
and no edges. Let $G_{1}$ be the subhypergraph with vertices
$V(G_{0})\cup\\{(0,\ldots,0,1)\\}$ and a single edge
$\\{(0,\ldots,0),(1,0,\ldots,0),\ldots,(0,\ldots,0,1)\\}$. Let $G_{2}$ be the
subhypergraph obtained from $G_{1}$ by adding the vertex $(0,\ldots,0,1,1)$
and the edge

$\\{(0,\ldots,0,1,0),(1,0,\ldots,0,1,0),\ldots,(0,\ldots,0,2,0),(0,\ldots,0,1,1)\\}\,.$

Proceeding in this way, say by reverse lexicographic order, one constructs all
the vertices with last coordinate equal to $1$ and all the edges containing
$k-1$ vertices with last coordinate equal to $0$ and exactly one vertex with
last coordinate equal to $1$. The corresponding chain of subhypergraphs can be
labeled as $G_{0}\subseteq G_{1}\subseteq\cdots\subseteq G_{a_{1}\cdots
a_{k-2}}$. Iterating this construction on can extend this chain to
$G_{0}\subseteq G_{1},\ldots,\subseteq G_{2a_{1}\cdots a_{k-2}}$ in such a way
that all the vertices whose last coordinate is $0$, $1$, or $2$ are accounted.
Further iterations lead to a transfer filtration of type $|G_{0}|=a_{1}\cdots
a_{k-2}$. Clearly there is nothing special about the particular choice of
$G_{0}$ for instance we could have picked
$V(G_{0})=\\{0\\}\times(\mathbb{Z}/a_{2}\mathbb{Z})\times\cdots\times(\mathbb{Z}/a_{k-1}\mathbb{Z})$
in which case an obvious adaptation of the construction above leads to a
transfer filtration of type $a_{2}\cdots a_{k-2}$. In particular, this shows
that in general a hypergraph $G$ can be of transfer type $b$ for different
choices of $b$.

######  Remark 16.

Let $G$ be a hypergraph admitting a transfer filtration $G_{0}\subseteq
G_{1}\subseteq\cdots\subseteq G_{m}=G$ of type $b$. Assume the edges of $G$
are ordered in such a way that $E(G_{i})=\\{E_{1},\ldots,E_{i}\\}$ for each
$i\in\\{1,\ldots,m\\}$. Since by construction each edge contains at least one
vertex not in $V(G_{0})$, there exists a function
$r:\\{1,\ldots,m\\}\to\\{0,\ldots,m-1\\}$ such that $r(i)<i$ and
$|E_{i}\setminus V(G_{r(i)})|=1$ for all $i\in\\{1,\ldots,m\\}$.

######  Example 17 (Running example).

Let $G$ be the $3$-uniform cycle of Example 10. Then
$r:\\{1,2,3,4\\}\to\\{0,1,2,3\\}$ can be chosen to be such that $r(1)=r(2)=0$,
$r(3)=1$ and $r(4)=1$.

As the first step in our construction, we show how to map any $k$-uniform
hypergraph $G$ of transfer type $b$ to a new $k$-uniform hypergraph
$G^{\prime}$ of transfer type $b$ whose transfer filtration _must_ add a
vertex in each step (this follows directly from the relationship between
$\left\lvert V(G)\right\rvert$ and $\left\lvert E(G)\right\rvert$ below). This
has two effects worth noting: First, ${G^{\prime}}$ is guaranteed to have an
SDR. Second, it _decouples_ certain intersections in the hypergraph, as
illustrated in Figure 4. For clarity, in the lemma below, for a function $p$
acting on vertices, we implicitly extend its action to edges in the natural
way, i.e. if $e=(v_{1},v_{2},v_{3})$ then $p(e)=(p(v_{1}),p(v_{2}),p(v_{3}))$.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$

Figure 4: For the hypergraph on the left, consider the transfer filtration in
which $G_{0}$ contains vertices $v_{1},v_{2}$, and we iteratively add edges
${\left\\{v_{1},v_{2},v_{3}\right\\}}$,
${\left\\{v_{1},v_{2},v_{4}\right\\}}$, and
${\left\\{v_{1},v_{3},v_{4}\right\\}}$ to the filtration. Then, the Decoupling
Lemma (Lemma 18) maps the hypergraph on the left to the hypergraph on the
right, in the process decoupling the intersection on vertex $v_{4}$. The
surjective function $p$ “undoes” the decoupling by mapping $v_{1},v_{2},v_{3}$
to themselves, and $v_{4},v_{5}$ to $v_{4}$.

######  Lemma 18 (Decoupling lemma).

Given a $k$-uniform hypergraph $G$ of transfer type $b$, there exists a
$k$-uniform hypergraph $\widetilde{G}$ of transfer type $b$ with $|E(G)|+b$
vertices and a surjective function $p:V(\tilde{G})\to V(G)$ such
$p(\widetilde{E})\in E(G)$ for every $\widetilde{E}\in E(\widetilde{G})$.

###### Proof.

Let $G_{0}\subseteq G_{1}\subseteq\cdots\subseteq G_{m}=G$ be a transfer
filtration such that $|V(G_{0})|=b$ and let
$r:\\{1,\ldots,m\\}\to\\{0,\ldots,m-1\\}$ as in Remark 16. Suppose the
vertices of $G$ are labeled as $\\{1,\ldots,n\\}$ in such a way that
$V(G_{0})=\\{1,\ldots,b\\}$. Furthermore, we may assume that the edges
$\\{E_{1},\ldots,E_{m}\\}$ of $G$ are labeled in such a way that
$E(G_{i})=\\{E_{1},\ldots,E_{i}\\}$ for each $i\in\\{1,\ldots,m\\}$. Let
$V(\widetilde{G})=\\{1,\ldots,m+b\\}$ and define
$p:\\{1,\ldots,m+b\\}\to\\{1,\ldots,n\\}$ so that $p(i)=i$ for all
$i\in\\{1,\ldots,b\\}$ and $\\{p(i)\\}=E_{i-b}\setminus V(G_{r(i-b)})$ for all
$i\in\\{b+1,\ldots,b+m\\}$ (where recall $r$ is from Remark 16). By Remark 16,
$p$ is surjective. For each $j\in\\{1,\ldots,m+b\\}$, let
$\underline{j}=\min(p^{-1}(p(j)))$. If we define
$E(\widetilde{G})=\\{\widetilde{E}_{1},\ldots,\widetilde{E}_{m}\\}$ by setting
$\widetilde{E}_{i}={\left\\{i+b\right\\}}\cup\\{\underline{j}\mid j\in
p^{-1}(E_{i}\setminus p(i+b))\\}$ for each $i\in\\{1,\ldots,m\\}$, then
$\widetilde{G}$ is clearly $k$-uniform. Let $\widetilde{G}_{0}$ be the
hypergraph with vertices $\\{1,\ldots,b\\}$ and no edges. For each
$i\in\\{1,\ldots,m\\}$, let $\widetilde{G}_{i}$ be the subgraph of
$\widetilde{G}$ with vertices $\\{1,\ldots,i+b\\}$ and edges
$\\{\widetilde{E}_{1},\ldots,\widetilde{E}_{i}\\}$. Then
$\widetilde{G}_{0}\subseteq\widetilde{G}_{1}\subseteq\cdots\subseteq\widetilde{G}_{m}=\widetilde{G}$
is a transfer filtration and $\widetilde{G}$ is a hypergraph of transfer type
$b$. ∎

######  Example 19 (Running example).

Let $G$ be the $3$-uniform cycle of Example 10. The proof of Lemma 18
(appendix) produces a $3$-uniform hypergraph $\widetilde{G}$ with vertices
$\\{1,2,3,4,5,6\\}$ and edges $\widetilde{E}_{1}=\\{1,2,3\\}$,
$\widetilde{E}_{2}=\\{1,2,4\\}$, $\widetilde{E}_{3}=\\{1,3,5\\}$,
$\widetilde{E}_{4}=\\{2,3,6\\}$, and surjective function
$p:\\{1,2,3,4,5,6\\}\to\\{1,2,3,4\\}$ defined by $p(1)=1$, $p(2)=2$, $p(3)=3$,
$p(4)=p(5)=p(6)=4$. This choice is not unique: setting
$\widetilde{E}_{4}=\\{2,4,6\\}$ and $p(6)=3$ also satisfies Lemma 18.

######  Remark 20.

If $k=2$, then $G$ (as defined in Lemma 18) is an ordinary graph and the
construction of $p$ can be understood topologically in terms of the geometric
realization $|G|$ of the standard simplicial set defined by $G$. Assume for
simplicity that $G$ is connected. Then the universal cover $\widetilde{|G|}$
is the geometric realization of a (possibly infinite) tree. Moreover, the
geometric realization of $p$ is the restriction of the canonical covering map
$\widetilde{|G|}\to|G|$ to the closure of a fundamental domain for the
canonical action of $\pi_{1}(|G|)$ on $\widetilde{|G|}$.

One of the “parameters” in our parameterized approach will be the _radius_ of
a transfer filtration, defined next. The concept is reminiscent of radii of
graphs, and roughly measures “how far” an edge is from the foundation of $b$
vertices with respect to the filtration.

######  Definition 21 (Radius of transfer filtration).

Let $G$ be a hypergraph admitting a transfer filtration
$G_{0}\subseteq\cdots\subseteq G_{m}=G$ of type $b$. Consider the function
(whose existence is guaranteed by Remark 16)
$r:\\{0,\ldots,m\\}\to\\{0,\ldots,m-1\\}$ such that $r(0)=0$ and $r(i)$ is the
smallest integer such that $|E_{i}\setminus V(G_{r(i)})|=1$ for all
$i\in\\{1,\ldots,m\\}$. The radius of the transfer filtration
$G_{0}\subseteq\cdots\subseteq G_{m}=G$ of type $b$ is the smallest integer
$\beta$ such that $r^{\beta}(i)=0$ $\forall i\in\\{1,\ldots,m\\}$ ($r^{\beta}$
denotes the composition of $r$ with itself $\beta$ times). The type $b$ radius
of $G$ is the minimum value $\rho(G,b)$ of $\beta$ over the set of all
possible transfer filtrations of type $b$ on $G$.

######  Example 22 (Running example).

For $G$ the $4$-cycle from Example 10, since function $r$ described in Example
17 is non-constant and $r(r(i))=0$ for all $i\in\\{1,2,3,4\\}$, then the
transfer filtration of Example 10 has radius $\beta=2$.

###  4.2 The main construction

Let $W$ be a two dimensional vector space over a field ${\mathbb{K}}$. To
discuss $k$-local constraints and product state solutions to $k$-QSAT
instances, we now set up somewhat more general terminology than is standard in
the literature to allow the results to be stated more generally.

######  Definition 23.

A function $H_{i}:W^{n}\to{\mathbb{K}}$ is $k$-local if there exists a subset
$E_{i}=\\{i_{1},\ldots,i_{k}\\}\subseteq\\{1,\ldots,n\\}$ and a non-zero
functional $H_{i}^{*}:W^{\otimes k}\to{\mathbb{K}}$ such that

$H_{i}(v_{1},\ldots,v_{n})=H_{i}^{*}(v_{i_{1}}\otimes\cdots\otimes v_{i_{k}})$

for all $v_{1},\ldots,v_{n}\in W$, i.e. $H_{i}$ acts non-trivially only on a
subset of $k$ indices. A collection $H=(H_{1},\ldots,H_{m})$ of $k$-local
functions $H_{1},\ldots,H_{n}:W^{n}\to{\mathbb{K}}$ is $k$-local. The
corresponding subsets $\\{E_{1},\ldots,E_{m}\\}$ (i.e. on which $H_{1}$
through $H_{m}$ act non-trivially, respectively) are the edges of a hypergraph
$G_{H}$ with vertices $\\{1,\ldots,n\\}$ known as the interaction graph of
$H$. The product satisfiability set of the $k$-local collection $H$ is the set
${\mathcal{S}}_{H}$ of all $(v_{1},\ldots,v_{n})\in W^{n}$ such that
$v_{i}\neq 0$ for all $i\in\\{1,\ldots,n\\}$ and $H_{j}(v_{1},\ldots,v_{n})=0$
for all $j\in\\{1,\ldots,m\\}$.

######  Remark 24.

Consider an isomorphism $\sharp$ between $W$ and its dual $W^{\vee}$ that to
each $v\in W$ assigns a functional $v^{\sharp}\in W^{\vee}$ such that
$v^{\sharp}(v)=0$. For instance, if a basis $\\{w_{1},w_{2}\\}$ for $W$ is
chosen then we may define $\sharp$ by setting
$((a_{1}w_{1}+a_{2}w_{2})^{\sharp})(b_{1}w_{1}+b_{2}w_{2})=a_{1}b_{2}-a_{2}b_{1}$
for all $a_{1},a_{2},b_{1},b_{2}\in{\mathbb{K}}$. Moreover, given any
$v_{1},v_{2}\in W$, then $v_{1}^{\sharp}(v_{2})=0$ if and only if there exists
$\lambda\in{\mathbb{K}}$ such that $\lambda v_{2}=v_{1}$.

######  Definition 25.

Let $N$ be a non-negative integer. The Fibonacci numbers of order $N$ are the
entries of the sequence $(F^{(N)}_{r})$ such that
$F_{r}^{(N)}=F_{r-1}^{(N)}+\ldots+F_{r-N}^{(N)}$ for all $r\geq N$,
$F_{N-1}^{(N)}=1$ and $F_{r}^{(N)}=0$ for all $r\leq N-2$.

######  Remark 26.

It is shown in [Wol] that there exists a monotonically increasing sequence
$(\psi_{N})$ with values in the real interval $[1,2)$ such that, for each
$N\geq 1$, $F_{r}^{(N)}\sim\psi_{N}^{r}$ as $r\to+\infty$.

######  Definition 27.

A function $f$ on $W^{l}$ with values in a ${\mathbb{K}}$-vector space has
degree $(d_{1},\ldots,d_{l})$ if
$f(\lambda_{1}v_{1},\ldots,\lambda_{l}v_{l})=\lambda_{1}^{d_{1}}\cdots\lambda_{l}^{d_{l}}f(v_{1},\ldots,v_{l})$
for every $\lambda_{1},\ldots,\lambda_{l}\in{\mathbb{K}}$ and every
$v_{1},\ldots,v_{l}\in W$.

Applying the Decoupling Lemma to an input $k$-uniform hypergraph $G$ with
transfer type $b$, we obtain a $k$-uniform hypergraph $\widetilde{G}$ of type
$b$ with $m=n-b$, for $m$ and $n$ the number of edges and vertices,
respectively. The next lemma shows that $\widetilde{G}$ is “nice”, in that any
global (product) solution to the $k$-QSAT system can be derived from a set of
assignments to the $b$ foundation vertices, and conversely, any (product)
assignment to the latter can be extended to a global (product) solution. For
the reader familiar with transfer matrices and CRs (see Section 3), with a
little thought it can be seen that the latter of these claims is similar to
picking an arbitrary assignment to the $b$ foundation vertices, and then
iteratively applying transfer matrices to satisfy all clauses (i.e. in step
$i$ of the filtration in which edge $E_{i}$ and vertex $v_{i}$ are added, the
$4\times 2$ transfer matrix of edge $E_{i}$ is applied to the two pre-existing
vertices of $E_{i}$ in the filtration, yielding an assignment to $v_{i}$ which
satisfies clause $E_{i}$).

######  Lemma 28 (Transfer Lemma).

Let $H=(H_{1},\ldots,H_{n-b})$ be a $k$-local collection of functions
$H_{i}:W^{n}\to{\mathbb{K}}$ whose interaction graph is a $k$-uniform
hypergraph of transfer type $b$. There exist non-zero (non-constant)
functions, which we call “transfer functions”, $g_{1},\ldots,g_{n}:W^{b}\to W$
with the following properties.

  1. 1.

(Global to local assignments) If $(v_{1},\ldots,v_{n})\in{\mathcal{S}}_{H}$
(recall the $v_{i}$ are non-zero by definition of ${\mathcal{S}}_{H}$) there
exist non-zero $\lambda_{1},\ldots,\lambda_{n}\in{\mathbb{K}}$ such that, for
every $i\in\\{1,\ldots,n\\}$,

$\lambda_{i}v_{i}=g_{i}(v_{1},\ldots,v_{b}).$ (1)

  2. 2.

(Local to global assignments) For any non-zero $v_{1},\ldots,v_{b}\in W$ there
exist $v_{b+1},\ldots,v_{n}\in W$ such that
$(v_{1},\ldots,v_{n})\in{\mathcal{S}}_{H}$ and
$v_{i}=g_{i}(v_{1},\ldots,v_{b})$ for every $i$ such that
$g_{i}(v_{1},\ldots,v_{b})\neq 0$.

  3. 3.

(Degree bounds) $g_{i}$ has degree $(d_{i1},\ldots,d_{ib})$ such that
$d_{ij}\leq F_{i}^{(b)}$ for all $j\in\\{1,\ldots,b\\}$.

###### Proof.

For $i=1,\ldots,b$, define $g_{i}(v_{1},\ldots,v_{b})=v_{i}$. Up to relabeling
the $n$ vertices, since the number of edges is $n-b$, we may assume that
$G_{H}$ admits a filtration $G_{0}\subseteq G_{1}\subseteq\cdots\subseteq
G_{n-b}=G_{H}$ such that each $G_{i}$ is of transfer of type $b$ and
$V(G_{i})\setminus V(G_{i-1})=\\{i+b\\}$ for all $i\in\\{1,\ldots,n-b\\}$.
Therefore, we may work by induction on $n$ (for each fixed $b$) and assume
that $g_{b+1},\ldots,g_{n-1}$ have been constructed. Suppose that
$E_{n-b}=\\{n,i_{1},\ldots,i_{k-1}\\}$ (where we shall assume vertex $n$ is
added in step $n-b$ of the filtration) and consider the function
$g_{n}^{\sharp}:W^{b}\to W^{\vee}$ such that

$(g_{n}^{\sharp}(v_{1},\ldots,v_{b}))(v)=H^{*}_{n-b}(g_{i_{1}}(v_{1},\ldots,v_{b})\otimes\cdots\otimes
g_{i_{k-1}}(v_{1},\ldots,v_{b})\otimes v)$ (2)

for all $v_{1},\ldots,v_{b},v\in W$. In words, $g_{n}^{\sharp}$ evaluates the
local Hamiltonian term corresponding to $H^{*}_{n-b}$ on the assignment
prescribed by the already defined functions $g_{i}$ on the first $k-1$ indices
and argument $v$ on the $k$-th index. For (1) of the claim, by induction, we
have that $(v_{1},\ldots,v_{n})\in{\mathcal{S}}_{H}$ implies that
$g_{1},\ldots,g_{n-1}$ as (1) exist and
$g_{n}^{\sharp}(v_{1},\ldots,v_{b})(v_{n})=0$. Given an isomorphism $\sharp$
between $W$ and $W^{\vee}$ as in Remark 24, we define a function
$g_{n}:W^{b}\to W$ by setting
$(g_{n}(v_{1},\ldots,v_{b}))^{\sharp}=g_{n}^{\sharp}(v_{1},\ldots,v_{b})$ for
all $v_{1},\ldots,v_{b}\in W$. Then $(v_{1},\ldots,v_{n})$ is in
${\mathcal{S}}_{H}$ implies (1) holds for every $i\in\\{1,\ldots,n\\}$. This
proves (1). To prove (2), suppose $v_{b+1},\ldots,v_{n-1}$ have been
constructed. Let $v$ be such that $H^{*}_{n-b}(v_{i_{1}}\otimes\cdots\otimes
v_{i_{k-1}}\otimes v)=0$ (such a $v$ exists, for example, since recall each
QSAT constraint is rank $1$ in our definition). Then
$(v_{1},\ldots,v_{n-1},\lambda v)\in{\mathcal{S}}_{H}$ for any
$\lambda\in{\mathbb{K}}$. Moreover, if $g_{n}(v_{1},\ldots,v_{b})\neq 0$ then
by Remark 24 it has to equal $\mu v$ for some non-zero $\mu\in{\mathbb{K}}$.
Setting $v_{n}=\mu v$, proves (2). To prove (3), we observe that the degree of
$g_{n}$ equals the degree of $g_{n}^{\sharp}$. Using induction and (2) it is
easy to see that the latter satisfies the claimed bounds. ∎

######  Example 29 (Running example).

Let $H=(H_{1},H_{2},H_{3},H_{4})$ be a $3$-local collection of functions
$H_{i}:W^{6}\to\mathbb{K}$ whose interaction graph is the $3$-uniform chain
$\widetilde{G}$ described in Example 19 (obtained by plugging the $4$-cycle
$G$ of Example 10 into the Decoupling Lemma). For clarity, $H_{i}$ is defined
on hyperedge $\widetilde{E}_{i}$, where the order of vertices in each edge is
fixed by the transfer filtration chosen; in particular, we use the natural
ordering $\widetilde{E}_{1}=(1,2,3)$, $\widetilde{E}_{2}=(1,2,4)$,
$\widetilde{E}_{3}=(1,3,5)$, $\widetilde{E}_{4}=(2,4,6)$, so that the
foundation is ${\left\\{1,2\right\\}}$. Then the proof of Lemma 28 constructs
transfer functions $g_{1},\ldots,g_{6}:W^{2}\to W$ which give assignments to
qubits $1$ through $6$, respectively, as follows. Fixing a basis
$\\{w_{1},w_{2}\\}$ of $W$ and unraveling (2) we obtain

$\displaystyle g_{1}(v_{1},v_{2})$ $\displaystyle=v_{1}\,;$ $\displaystyle
g_{2}(v_{1},v_{2})$ $\displaystyle=v_{2}\,;$ $\displaystyle
g_{3}(v_{1},v_{2})$ $\displaystyle=H_{1}^{*}(v_{1}\otimes v_{2}\otimes
w_{2})w_{1}-H_{1}^{*}(v_{1}\otimes v_{2}\otimes w_{1})w_{2}\,;$ $\displaystyle
g_{4}(v_{1},v_{2})$ $\displaystyle=H_{2}^{*}(v_{1}\otimes v_{2}\otimes
w_{2})w_{1}-H_{2}^{*}(v_{1}\otimes v_{2}\otimes w_{1})w_{2}\,;$ $\displaystyle
g_{5}(v_{1},v_{2})$ $\displaystyle=H_{3}^{*}(v_{1}\otimes
g_{3}(v_{1},v_{2})\otimes w_{2})w_{1}-H_{3}^{*}(v_{1}\otimes
g_{3}(v_{1},v_{2})\otimes w_{1})w_{2}\,;$ $\displaystyle g_{6}(v_{1},v_{2})$
$\displaystyle=H_{4}^{*}(v_{2}\otimes g_{4}(v_{1},v_{2})\otimes
w_{2})w_{1}-H_{4}^{*}(v_{2}\otimes g_{4}(v_{1},v_{2})\otimes w_{1})w_{2}\,.$

In particular the matrix of degrees $d_{ij}$ is

$\left(\begin{array}[]{cccccc}1&0&1&1&2&1\\\
0&1&1&1&1&2\end{array}\right)^{T}$

so that, in accordance to the bound given in Lemma 28, the $i$-th entry of
each column is less or equal than the $i$-th (ordinary) Fibonacci number
$F_{i}^{(2)}$.

Thus far, we have seen how combining the Decoupling and Transfer Lemmas “blows
up” an input $k$-QSAT system $\Pi$ to a larger “decoupled” system $\Pi^{+}$
which is easier to solve due to its decoupled property. Now we wish to relate
the solutions of $\Pi^{+}$ _back_ to $\Pi$. This is accomplished by the next
lemma, which introduces a set of “qualifier” constraints
${\left\\{h_{s}\right\\}}$ with the key property: Any solution to
${\left\\{h_{s}\right\\}}$ can be extended to one for $\Pi^{+}$, and then
_mapped back_ to a solution for $\Pi$. Importantly, the qualifier constraints
_act only_ on the $b$ foundation vertices, as opposed to all $n$ vertices!

######  Lemma 30 (Qualifier Lemma).

Let $H=(H_{1},\ldots,H_{m})$ be a $k$-local collection of functions
$H_{i}:W^{n}\to{\mathbb{K}}$ whose interaction graph is a $k$-uniform
hypergraph of transfer type $b$ such that $m>n-b$. Then there exist non-zero
(non-constant) functions, called _qualifiers_ ,
$h_{1},\ldots,h_{m-n+b}:W^{b}\to{\mathbb{K}}$ and $\pi:W^{n}\to W^{b}$ such
that

  1. 1.

$h_{s}(\pi({\mathcal{S}}_{H}))=0$ for all $s\in\\{1,\ldots,m-n+b\\}$;

  2. 2.

$h_{s}$ has degree $(d_{s1},\ldots,d_{sb})$ with $d_{sr}\leq
2F^{(b)}_{\rho(G,b)+b+1}$ for all $s\in\\{1,\ldots,m+b\\}$ and all
$r\in\\{1,\ldots,b\\}$.

###### Proof.

We begin by applying the Decoupling Lemma (Lemma 18) to $G_{H}$. This yields
the larger hypergraph $\widetilde{G_{H}}$ and surjection
$p:V(\widetilde{G_{H}})\to V(G_{H})$, constructed via a transfer filtration
$G_{0}\subseteq\cdots\subseteq G_{m}=G$ of type $b$. Note that
$\widetilde{G_{H}}$ is the interaction graph of a $k$-local collection
$\widetilde{H}=(\widetilde{H}_{1},\ldots,\widetilde{H}_{m})$ of functions
$\widetilde{H}_{i}:W^{m+b}\to{\mathbb{K}}$ such that
$\widetilde{H}^{*}_{i}=H^{*}_{i}$ for each $i\in\\{1,\ldots,m\\}$. Let
$\Delta:W^{n}\to W^{m+b}$ be such that
$\Delta(v_{1},\ldots,v_{n})=(\widetilde{v}_{1},\ldots,\widetilde{v}_{m+b})$,
where $\widetilde{v}_{i}=v_{p(i)}$ for all $i\in\\{1,\ldots,m+b\\}$. In other
words, $\Delta$ “blows up” any assignment on the original $n$ vertices to one
on $m+b$ vertices (where by assumption $m+b>n$), such that any vertex $j$ of
$\widetilde{G_{H}}$ obtained by “decoupling” a vertex $i$ of $G_{H}$
(formally, $p(j)=i$) is assigned the same vector as $i$. It follows that
$(v_{1},\ldots,v_{n})\in{\mathcal{S}}_{H}$ if and only if
$\Delta(v_{1},\ldots,v_{n})\in{\mathcal{S}}_{\widetilde{H}}$.

Having applied the Decoupling Lemma and obtained a hypergraph
$\widetilde{G_{H}}$ satisfying $m=n-b$, we now apply the Transfer Lemma (Lemma
28) to $\widetilde{G_{H}}$. This yields that there exist
$g_{1},\dots,g_{m+b}:W^{b}\to W$ with the property that
$\Delta(v_{1},\ldots,v_{n})\in{\mathcal{S}}_{\widetilde{H}}$ implies that
$g_{i}(v_{1},\ldots,v_{b})$ is a multiple of $v_{p(i)}$ for all
$i\in\\{1,\ldots,m+b\\}$. Borrowing notation from the proof of Lemma 18, let
$\\{i_{1},\ldots,i_{m-n+b}\\}$ be the subset of all $i\in\\{1,\ldots,m+b\\}$
such that $\underline{i}<i$ (intuitively, these indices correspond to vertices
of $\widetilde{G_{H}}$ obtained by decoupling a vertex of $G_{H}$). For each
$s\in\\{1,\ldots,m-n+b\\}$, define qualifier $h_{s}:W^{b}\to{\mathbb{K}}$ be
such that

$h_{s}(v_{1},\ldots,v_{b})=(g_{i_{s}}^{\sharp}(v_{1},\ldots,v_{b}))(g_{\underline{i_{s}}}(v_{1},\ldots,v_{b}))$
(3)

for all $v_{1},\ldots,v_{b}\in W$. If
$(v_{1},\ldots,v_{n})\in{\mathcal{S}}_{H}$, then for every
$s\in\\{1,\ldots,m-n+b\\}$ there exists
$\lambda_{i_{s}},\lambda_{\underline{i_{s}}}\in{\mathbb{K}}$ such that
$\lambda_{i_{s}}v_{p(i_{s})}=g_{i_{s}}(v_{1},\ldots,v_{b})$ and
$\lambda_{\underline{i_{s}}}v_{p(i_{s})}=g_{\underline{i_{s}}}(v_{1},\ldots,v_{b})$.
Therefore,

$h_{s}(v_{1},\ldots,v_{b})=\lambda_{i_{s}}\lambda_{\underline{i}_{s}}v_{p(i_{s})}^{\sharp}(v_{p(i_{s})})=0$

for every $s\in\\{1,\ldots,m-n+b\\}$. Therefore, (1) holds if we define $\pi$
to be the composition of $\Delta$ with the projection onto the first $b$
entries. It follows from Lemma 28 and (3) that $h_{s}$ has degree
$(d_{s1},\ldots,d_{sb})$ with $d_{sr}\leq 2F_{i_{s}}^{(b)}$ for every
$s\in\\{1,\ldots,m-n+b\\}$ and $r\in\\{1,\ldots,b\\}$. Finally (2) follows
from Lemma 28, by choosing the transfer filtration
$G_{0}\subseteq\cdots\subseteq G_{m}=G$ of type $b$ to have radius
$\rho(G,b)$. ∎

######  Remark 31.

In the notation of the proof of Lemma 30, suppose $v_{1},\ldots,v_{b}$ is an
assignment to the foundation which satisfies the qualifiers, i.e.
$h_{s}(v_{1},\ldots,v_{b})=0$ for all $s\in\\{1,\ldots,m-n+b\\}$, and that
$g_{i_{s}}(v_{1},\ldots,v_{b})\neq 0$ for all $s\in\\{1,\ldots,m-n+b\\}$. Then
by Remark 24 we have that for each $s\in\\{1,\ldots,m-n+b\\}$ there exist
$\mu_{s}\in\mathbb{K}$ such that

$\mu_{s}g_{\underline{i_{s}}}(v_{1},\ldots,v_{b})=g_{i_{s}}(v_{1},\ldots,v_{b})\,.$

In other words, in a solution to the decoupled instance on
$\widetilde{G_{H}}$, it must be the case that all decoupled copies of a vertex
$v$ receive the _same_ assignment (up to scalars). Indeed,
$g_{\underline{i_{s}}}(v_{1},\ldots,v_{b})\neq 0$, and hence by Lemma 28 there
exist $v_{b+1},\ldots,v_{n}$ such that
$(v_{1},\ldots,v_{n})\in{\mathcal{S}}_{H}$, i.e. a satisfying assignment for
$H$ must exist. Thus, to solve the original $k$-QSAT instance $\Pi$, it
suffices to: (1) apply the Decoupling Lemma to blow up the instance to a
decoupled instance $\Pi^{+}$, (2) apply the transfer functions from the
Transfer Lemma to $v_{1},\ldots,v_{b}$ to obtain a solution on all $m+b$
vertices for $\Pi^{+}$, and (3) (easily) map this solution back to one on $n$
vertices for $\Pi$.

######  Example 32 (Running example).

Let $H=(H_{1},H_{2},H_{3},H_{4})$ be a $3$-local collection of functions
$H_{i}:W^{4}\to\mathbb{K}$ whose interaction graph is the $3$-uniform cycle of
transfer type $2$ introduced in Example 10. If $p$ is chosen as in Example 19,
then the two qualifier functions are

$h_{1}(v_{1},v_{2})=(g_{5}^{\sharp}(v_{1},v_{2}))(g_{4}(v_{1},v_{2}))$

of degree $(3,2)$ and

$h_{2}(v_{1},v_{2})=(g_{6}^{\sharp}(v_{1},v_{2}))(g_{3}(v_{1},v_{2}))$

of degree $(2,3)$, where $g_{3},g_{4},g_{5},g_{6}$ so that $d_{sr}\leq 3\leq
10=2F_{5}^{(2)}$ for each $s,r\in\\{1,2\\}$, in accordance to Lemma 30.
Choosing a basis $\\{w_{1},w_{2}\\}$ of $W$ as in Example 32, we obtain via
Condition 1 of Lemma 30 that $(v_{1},v_{2},v_{3},v_{4})\in\mathcal{S}_{H}$
implies

$\displaystyle 0=H_{1}^{*}(v_{1}\otimes v_{2}\otimes
w_{1})H_{2}^{*}(v_{1}\otimes v_{2}\otimes w_{1})H_{3}^{*}(v_{1}\otimes
w_{2}\otimes w_{2})$ $\displaystyle+H_{1}^{*}(v_{1}\otimes v_{2}\otimes
w_{2})H_{2}^{*}(v_{1}\otimes v_{2}\otimes w_{2})H_{3}^{*}(v_{1}\otimes
w_{1}\otimes w_{1})$ $\displaystyle-H_{1}^{*}(v_{1}\otimes v_{2}\otimes
w_{1})H_{2}^{*}(v_{1}\otimes v_{2}\otimes w_{2})H_{3}^{*}(v_{1}\otimes
w_{2}\otimes w_{1})$ $\displaystyle-H_{1}^{*}(v_{1}\otimes v_{2}\otimes
w_{2})H_{2}^{*}(v_{1}\otimes v_{2}\otimes w_{1})H_{3}^{*}(v_{1}\otimes
w_{1}\otimes w_{2})$

and

$\displaystyle 0=H_{1}^{*}(v_{1}\otimes v_{2}\otimes
w_{1})H_{2}^{*}(v_{1}\otimes v_{2}\otimes w_{1})H_{4}^{*}(v_{2}\otimes
w_{2}\otimes w_{2})$ $\displaystyle+H_{1}^{*}(v_{1}\otimes v_{2}\otimes
w_{2})H_{2}^{*}(v_{1}\otimes v_{2}\otimes w_{2})H_{4}^{*}(v_{2}\otimes
w_{1}\otimes w_{1})$ $\displaystyle-H_{1}^{*}(v_{1}\otimes v_{2}\otimes
w_{1})H_{2}^{*}(v_{1}\otimes v_{2}\otimes w_{2})H_{4}^{*}(v_{2}\otimes
w_{2}\otimes w_{1})$ $\displaystyle-H_{1}^{*}(v_{1}\otimes v_{2}\otimes
w_{2})H_{2}^{*}(v_{1}\otimes v_{2}\otimes w_{1})H_{4}^{*}(v_{2}\otimes
w_{1}\otimes w_{2})\,.$

###  4.3 Generic constraints

Remark 31 outlined the high-level strategy for computing a (product-state)
solution to an input $k$-QSAT system $\Pi$. For this strategy to work,
however, we require an assignment to the foundation of the transfer filtration
which (1) satisfies the qualifier functions from the Qualifier Lemma, and (2)
causes the transfer functions $g_{i}$ from the Transfer Lemma to output non-
zero vectors. When are (1) and (2) possible? We now answer this question
affirmatively for a non-trivial class of $k$-QSAT instances, assuming
constraints are chosen generically. Aside: In this section alone, the
terminology of projective algebraic geometry (AG) is used briefly to define
generic constraints; otherwise, the content is intended to be accessible
without a background in AG.

######  Remark 33 (Generic constraints).

Let $G$ be a $k$-uniform hypergraph. The set of $k$-local constraints $H$ with
interaction graph $G$ is canonically identified with the projective variety
${\mathcal{X}}_{G}({\mathbb{K}})=({\mathbb{P}}^{2^{k}-1}({\mathbb{K}}))^{m}$.
(We remark the same variety was used in [LLM+10].) We say that a property
holds for the generic constraint with interaction graph $G$ if it holds for
every $k$-local constraint on a Zariski open set of
${\mathcal{X}}_{G}({\mathbb{K}})$. Note that we allow different (generic)
constraints on each edge (i.e. the Hamiltonian is not necessarily translation-
invariant).

######  Definition 34.

Let $G_{0}\subseteq G_{1}\subseteq\cdots\subseteq G$ be a transfer filtration
on a $k$-uniform hypergraph $G$ whose vertices $\\{1,\ldots,n\\}$ are ordered
in such a way that if $i\in V(G_{j})\setminus V(G_{j-1})$, then $i-1\in
V(G_{j-1})$. Given $i,i^{\prime}\in\\{1,\ldots,n\\}$ we say that $i^{\prime}$
is a successor of $i$ (and $i$ is a predecessor of $i^{\prime}$) if there
exists sequences $i_{1},\ldots,i_{l}\in V(G)$ and $E_{1},\ldots,E_{l+1}\in
E(G)$ such that $i\leq i_{1}\leq\cdots\leq i_{l}\leq i^{\prime}$, $i\in
E_{1}$, $i^{\prime}\in E_{l+1}$ and $i_{j}\in E_{j}\cap E_{j+1}$ for all
$j\in\\{1,\ldots,l\\}$.

######  Example 35.

Let $G$ be as in Example 35. Then $3$ is a predecessor of $4$ and a successor
of both $1$ and $2$.

Before showing the main theorem of this section (Theorem 38), we first require
the following lemma, which shows that under certain conditions, the transfer
functions $g_{i}$ of the Transfer Lemma satisfy a surjectivity criterion.

######  Lemma 36 (Surjectivity Lemma).

Let $G$ be a $k$-uniform hypergraph of transfer type $b$ with $n$ vertices and
$n-b$ edges. Let $H$ be a generic $k$-local constraint in
${\mathcal{X}}_{G}({\mathbb{K}})$, let $g_{1},\ldots,g_{n}:W^{b}\to W$ be
transfer functions as in the Transfer Lemma (Lemma 28) and choose non-zero
$v_{1},\ldots,v_{b-1}\in W$. For each $i$, define $\gamma_{i}:W\to W$ such
that

$\gamma_{i}(w):=g_{i}(v_{1},\ldots,v_{b-1},w)$ (4)

for all $w\in W$. If $i$ is a successor of $b$, then $\gamma_{i}$ is
surjective.

###### Proof.

Up to a permutation of $\\{1,\ldots,b\\}$, we may assume that $n$ is a
successor of $b$. By induction we may assume the claim has been proved for
hypergraphs with $n-1$ vertices (the base case $i=b$ follows since we can take
$g_{b}$ to be the identity, see the first line of the proof of Lemma 28).
Therefore, a generic choice of $H_{1},\ldots,H_{n-1-b}$ leads to surjective
maps $\gamma_{i}$ for every successor of $b$. If the edge that contains vertex
$n$ is $\\{i_{1},\ldots,i_{k-1},n\\}$, then at least one other vertex, say
$i_{1}$, is also a successor of $b$. Since $\gamma_{i_{1}}$ is surjective by
the induction hypothesis, we can choose $w^{\prime},w^{\prime\prime}\in W$
such that $\gamma_{i_{1}}(w^{\prime})$ and $\gamma_{i_{1}}(w^{\prime\prime})$
are linearly independent. Suppose that $\gamma_{n}$ is not surjective. Since
it has definite (i.e. well-defined) degree, this implies
$\gamma_{n}(w^{\prime})$ and $\gamma_{n}(w^{\prime\prime})$ are not linearly
independent. By (1) this means that $H_{n-b}^{*}$ vanishes at two prescribed,
linearly independent vectors. Since this condition is not generic, we have a
contradiction. Thus, generically $\gamma_{n}$ is surjective. ∎

######  Remark 37.

For each $i,j$, consider the function $\Gamma_{ij}:W\to{\mathbb{K}}$ defined
by setting

$\Gamma_{ij}(w):=(\gamma_{i}(w))^{\sharp}(\gamma_{j}(w))$

for all $x\in\mathbb{K}$. It is easy to see by induction that if
$w^{\prime},w^{\prime\prime}\in W$ are linearly independent, then
$P_{ij}(x)=\Gamma_{ij}(w^{\prime}+xw^{\prime\prime})$ is a univariate
polynomial in $x$ with coefficients in $\mathbb{K}$. Furthermore, if the
constraint $H$ is chosen generically and either $i$ or $j$ is a successor of
$b$ then $P_{ij}$ is not a non-zero constant.

$v_{13}$$v_{14}$$v_{15}$$v_{16}$$v_{17}$$v_{18}$$v_{19}$$v_{20}$$v_{21}$$v_{22}$$v_{23}$$v_{24}$$v_{25}$$v_{26}$$v_{27}$$v_{28}$$v_{29}$$v_{30}$$v_{31}$$v_{32}$$v_{33}$$v_{34}$$v_{35}$$v_{36}$$v_{37}$$v_{38}$$v_{39}$$v_{40}$$v_{41}$$v_{42}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$$v_{9}$$v_{10}$$v_{11}$$v_{12}$

Figure 5: (Fir tree) A $3$-uniform hypergraph $G$ of transfer type $b$ to
which Theorem 38 applies. $G$ has $m=31$ edges, $n=42$ vertices, and
foundation size $b=12$ (the vertices marked with a star are foundation
vertices). The hypergraph’s name was chosen due to its (vague) resemblance to
a fir tree.

We now show the main theorem of this section, which applies to $k$-uniform
hypergraphs of transfer type $b=n-m+1$. The latter includes non-trivial
instances which we discuss in Section 4.4 (along with an example of
exponential speedup of our parameterized algorithm over brute
diagonalization). In words, the theorem says that for any $k$-uniform
hypergraph of transfer type $b=n-m+1$ (i.e. there is precisely one qualifier
function $h_{1}$), if the constraints are chosen generically, then any zero of
$h_{1}$ is the image under the map $\pi$ (defined in Qualifier Lemma) of a
satisfying assignment to the corresponding $k$-QSAT instance. The key
advantage to this approach is simple: To solve the $k$-QSAT instance, instead
of solving a system of equations, we are reduced to solving for the roots of
just one polynomial — $h_{1}$. Moreover, if both the foundation size $b$ and
the radius of the transfer filtration of $G$ scale as $O(\log m+\log n)$, then
$h_{1}$ has polynomial degree in $m$ and $n$.

######  Theorem 38.

Let ${\mathbb{K}}$ be algebraically closed, and let $\mathcal{F}$ denote the
set of $k$-uniform hypergraphs with $n$ vertices, $m$ edges, and transfer type
$b=n-m+1$. If $H$ is a generic $k$-local constraint with interaction graph
$G\in\mathcal{F}$ and $h_{1}$ and $\pi$ are as in the Qualifier Lemma (Lemma
30), then $(h_{1}\circ\pi)^{-1}(0)\cap{\mathcal{S}}_{H}$ is nonempty.

###### Proof.

Let $\widetilde{G}$ and $g_{1},\ldots,g_{n+1}$ as in the proof of the
Qualifier Lemma (Lemma 30). Since ${\mathbb{K}}$ is algebraically closed, by
the discussion in Remark 41, there exist $\hat{v}_{1},\ldots,\hat{v}_{b}\in W$
such that $h_{1}(\hat{v}_{1},\ldots,\hat{v}_{b})=0$. As shown in the previous
section, if additionally $g_{i_{1}}(\hat{v}_{1},\ldots,\hat{v}_{b})\neq 0$,
then
$\pi^{-1}(\hat{v}_{1},\ldots,\hat{v}_{b})\cap{\mathcal{S}}_{H}\neq\emptyset$,
as desired. Thus, we are left to show that the same conclusion holds even if
$g_{i_{1}}(\hat{v}_{1},\ldots,\hat{v}_{b})=0$ (which immediately implies
$h_{1}(\hat{v}_{1},\ldots,\hat{v}_{b})=0$).

Let $j\in\\{b+1,\ldots,n+1\\}$ be minimal among those predecessors of $i_{1}$
such that $g_{j}(\hat{v}_{1},\ldots,\hat{v}_{b})=0$. For a sufficiently
generic choice of constraint we may assume that
$g_{l}(\hat{v}_{1},\ldots,\hat{v}_{b})\neq 0$ for any $l$ that is not a
successor of $j$. Our strategy is now to _remove_ the edge in $\widetilde{G}$
which was added in the same step of the filtration in which vertex $j$ was
added, namely edge $\widetilde{E_{j-b}}$. We then instead add vertex $j$
directly to the foundation. Formally, consider hypergraph $F$ obtained from
$\widetilde{G}$ by removing edge $\widetilde{E_{j-b}}$, and consider transfer
filtration $F_{0}\subseteq F_{1}\subseteq\cdots\subseteq F_{m-1}=F$ where:

  * •

(Add $j$ to the foundation) $V(F_{i})=V(\widetilde{G_{i}})\cup\\{j\\}$ for all
$i\in{\left\\{0,\ldots,j-b-1\right\\}}$ and $V(F_{i})=V(\widetilde{G_{i+1}})$
for all $i\in{\left\\{j-b,\ldots,m-1\right\\}}$,

  * •

(Remove edge $\widetilde{E_{j-b}}$) $E(F_{i})=E(\widetilde{G_{i}})$ for all
$i\in{\left\\{0,\ldots,j-b-1\right\\}}$ and
$E(F_{i})=E(\widetilde{G_{i+1}})\setminus\\{\widetilde{E_{j-b}}\\}$ for all
$i\in{\left\\{j-b,\ldots,m-1\right\\}}$.

The hypergraph $F$ thus has $n_{F}:=n$ vertices, $m_{F}:=m-1=n-b$ edges, and
foundation of size $b_{F}:=b+1=n-m+2$. Thus, $m_{F}>n_{F}-b_{F}$, implying we
can apply the Qualifier Lemma (Lemma 30) and the Surjectivity Lemma (Lemma 36)
to obtain transfer functions $f_{1},\ldots,f_{n_{F}}:W^{b_{F}}\mapsto W$ and
$\gamma_{1,F},\ldots,\gamma_{n_{F},F}:W\mapsto W$ (based on $f_{i}$ instead of
$g_{i}$). Two comments are in order here: First, each $\gamma_{i,F}$ depends
on $\hat{v}_{1},\ldots,\hat{v}_{b}$ (which are fixed) and parameter $w$, which
corresponds to the vertex $j$ added to the foundation in the construction of
$F$. Second, for $i\in{\left\\{0,\ldots,j-b-1\right\\}}$, we have by
construction that for all $w\in W$,
$f_{i}(\hat{v}_{1},\ldots,\hat{v}_{b},w)=g_{i}(\hat{v}_{1},\ldots,\hat{v}_{b})$
— this is because each corresponding $\widetilde{G_{i}}$ (i.e. the first $j-b$
“steps” of the original transfer filtration) does not depend on vertex $j$.

Now recall from Remark 37 the polynomial

$P_{i_{1}\underline{i_{1}}}(x):=\Gamma_{i_{1},\underline{i_{1}}}(w^{\prime}+xw^{\prime\prime})=(\gamma_{i_{1},F}(w^{\prime}+xw^{\prime\prime}))^{\sharp}(\gamma_{\underline{i_{1}},F}(w^{\prime}+xw^{\prime\prime}))\in{\mathbb{K}}[x].$

Since ${\mathbb{K}}$ is algebraically closed, $P_{i_{1}\underline{i_{1}}}(x)$
has a root $\hat{x}$ in ${\mathbb{K}}$. Thus, by Remark 24, there exists
$\lambda\in{\mathbb{K}}$ such that
$\gamma_{i_{1},F}(w^{\prime}+\hat{x}w^{\prime\prime})=\lambda\gamma_{\underline{i_{1}},F}(w^{\prime}+\hat{x}w^{\prime\prime})$
(i.e. both decoupled vertices $i_{1}$ and $\underline{i_{1}}$ can be given the
same assignment). Therefore, if we set
${v}_{i}=\gamma_{{i},F}(w^{\prime}+\hat{x}w^{\prime\prime})$ for all
$i\in\\{1,\ldots,n\\}$ (note we may assume by Remark 39 that each $v_{i}\neq
0$), then (1) vertices $i_{1}$ and $\underline{i_{1}}$ receive consistent
assignments, (2) edge $\widetilde{E_{j-b}}$ is satisfied by the second remark
above that
$f_{i}(\hat{v}_{1},\ldots,\hat{v}_{b},w)=g_{i}(\hat{v}_{1},\ldots,\hat{v}_{b})$
for $i\in{\left\\{0,\ldots,j-b-1\right\\}}$ (here we also use the fact that by
Equation (2), edge $\widetilde{E_{j-b}}$ was satisfied by foundation
assignment $(\hat{v}_{1},\ldots,\hat{v}_{b})$ regardless of the assignment to
vertex $i_{1}$), and (3) $({v}_{1},\ldots,{v}_{n})$ satisfies all constraints
in hypergraph $F$. It follows that
$({v}_{1},\ldots,{v}_{n})\in\pi^{-1}(\hat{v_{1}},\ldots,\hat{v_{b}})\cap{\mathcal{S}}_{H}$,
as required. ∎

######  Remark 39 (The maps $\gamma_{i}(w)$ have no zeroes).

The maps $\gamma_{i}(w)$ from the Surjectivity Lemma (Lemma 36) can without
loss of generality be taken to have no zeroes, i.e. $\nexists w\in W$ such
that $\gamma_{i}(w)=0$. To see this, consider
$\gamma_{i}(w^{\prime}+xw^{\prime\prime}):W\mapsto W$ for $x\in{\mathbb{K}}$
as in Remark 37. Since $w^{\prime}$ and $w^{\prime\prime}$ are linearly
independent, we can write
$\gamma_{i}(w^{\prime}+xw^{\prime\prime})=p(x)w^{\prime}+q(x)w^{\prime\prime}$
for polynomials $p,q\in{\mathbb{K}}[x]$. In order for the right hand size to
vanish on $x_{0}$, since ${\mathbb{K}}$ is algebraically closed, $p$ and $q$
must share a common factor $(x-x_{0})$. Factoring out $(x-x_{0})$, we obtain
new polynomials $p^{\prime}$ and $q^{\prime}$, and redefine
$\gamma^{\prime}_{i}(w^{\prime}+xw^{\prime\prime})=p^{\prime}(x)w^{\prime}+q^{\prime}(x)w^{\prime\prime}$.
(Note we are implicitly working in projective space, since solutions to the
Quantum SAT instance remain solutions under (non-zero) scaling.)

######  Example 40 (Running example).

We illustrate the proof of Theorem 38 by specializing the construction to the
$3$-uniform semicycle $G_{3}$ from Example 10. Then $\widetilde{G}_{3}$ is the
hypergraph with vertices $\\{1,2,3,4,5\\}$ and edges
$\widetilde{E}_{1}=\\{1,2,3\\}$, $\widetilde{E}_{2}=\\{1,2,4\\}$,
$\widetilde{E}_{3}=\\{1,3,5\\}$. Moreover, the transfer functions
$g_{1},\ldots,g_{5}:W^{2}\to W$ can be chosen as in Example 29. Let $h_{1}$ be
as in Example 32 and suppose $v_{1},v_{2}\in W$ are such that
$h_{1}(v_{1},v_{2})=0$. If none of the $g_{i}(v_{1},v_{2})$ are zero, then a
solution of the form $(v_{1},v_{2},v_{3},v_{4})$ can be found by Remark 31.
Else, suppose (say) $g_{3}(v_{1},v_{2})=0$ (generically, only one
$g_{i}(v_{1},v_{2})$ will be zero in this case). Then the hypergraph $F$ has
vertices $\\{1,2,3,4,5\\}$ and edges $\widetilde{E}_{2}$, $\widetilde{E}_{3}$.
Furthermore, $F$ has a transfer filtration $F_{0}\subseteq F_{1}\subseteq
F_{2}=F$, where $F_{0}$ has vertices $\\{1,2,3\\}$ and no edges, while $F_{1}$
has vertices $\\{1,2,3,4\\}$ and a single edge $\widetilde{E}_{2}$. Unraveling
(2) we obtain

$\displaystyle\gamma_{1,F}(w)$ $\displaystyle=v_{1}\,;$
$\displaystyle\gamma_{2,F}(w)$ $\displaystyle=v_{2}\,;$
$\displaystyle\gamma_{3,F}(w)$ $\displaystyle=w\,;$
$\displaystyle\gamma_{4,F}(w)$ $\displaystyle=H_{2}^{*}(v_{1}\otimes
v_{2}\otimes w^{\prime\prime})w^{\prime}-H_{2}^{*}(v_{1}\otimes v_{2}\otimes
w^{\prime})w^{\prime\prime}\,;$ $\displaystyle\gamma_{5,F}(w)$
$\displaystyle=H_{3}^{*}(v_{1}\otimes w\otimes
w^{\prime\prime})w^{\prime}-H_{3}^{*}(v_{1}\otimes w\otimes
w^{\prime})w^{\prime\prime}$

and thus

$\Gamma_{54}(w)=H_{3}^{*}(v_{1}\otimes w\otimes
w^{\prime})H_{2}^{*}(v_{1}\otimes v_{2}\otimes
w^{\prime\prime})-H_{3}^{*}(v_{1}\otimes w\otimes
w^{\prime\prime})H_{2}^{*}(v_{1}\otimes v_{2}\otimes w^{\prime})$

for all $w\in W$. Hence $P_{54}(x)=P_{54}^{0}+P_{54}^{1}x$ where

$P_{54}^{0}=H_{3}^{*}(v_{1}\otimes w^{\prime}\otimes
w^{\prime})H_{2}^{*}(v_{1}\otimes v_{2}\otimes
w^{\prime\prime})-H_{3}^{*}(v_{1}\otimes w^{\prime}\otimes
w^{\prime\prime})H_{2}^{*}(v_{1}\otimes v_{2}\otimes w^{\prime})$

and

$P_{54}^{1}=H_{3}^{*}(v_{1}\otimes w^{\prime\prime}\otimes
w^{\prime})H_{2}^{*}(v_{1}\otimes v_{2}\otimes
w^{\prime\prime})-H_{3}^{*}(v_{1}\otimes w^{\prime\prime}\otimes
w^{\prime\prime})H_{2}^{*}(v_{1}\otimes v_{2}\otimes w^{\prime})\,.$

In this case it is immediately clear that generically $P_{54}(x)$ is non-
constant and, being linear, has a root over any (non-necessarily algebraically
closed) field. However, in general, $P_{i\underline{i}}(x)$ may have
arbitrarily high degree and assuming that $\mathbb{K}$ is algebraically closed
becomes necessary.

######  Remark 41 (Reduction to univariate polynomials).

Theorem 38 reduces us to solving a single polynomial equation,

$h_{1}(v_{1},\ldots,v_{b})=0,$

which is multi-variate. In this case, we reduce it further to a univariate
polynomial by fixing arbitrary vectors $w_{1},\ldots,w_{b}\in W$ and
$w^{\prime}_{b}\in W$ linearly independent from $w_{b}$. Then

$P(x)=h_{1}(w_{1},\ldots,w_{b}+xw^{\prime}_{b})$

is a _univariate_ polynomial in $\mathbb{K}[x]$, which has a root
$x\in{\mathbb{K}}$ since ${\mathbb{K}}$ is algebraically closed. Thus, we can
reduce the problem of computing a root of the multivariate polynomial $h_{1}$
to computing a root of the univariate polynomial $P$.

Before explicitly stating our algorithm and formally analyzing runtimes in
Section 4.4, we finally tie Theorem 38 back to SDRs, and give an AG overview
of our approach.

######  Remark 42 (Connection to SDRs).

Theorem 38 gives a _constructive_ proof that all hypergraphs in $\mathcal{F}$
have a satisfying (product state) assignment if the constraints are chosen
generically. This implies each hypergraph in $\mathcal{F}$ has an SDR, as we
now observe.

######  Corollary 43.

If $G$ is a $k$-uniform hypergraph of transfer type $b$ and such that
$|E(G)|=|V(G)|-b+1$, then $G$ has an SDR.

###### Proof.

By Theorem 38, ${\mathcal{S}}_{H}$ is nonempty for generic
$H\in{\mathcal{X}}_{G}(\mathbb{C})$. Theorem 2 of [LLM+10] then implies that
$G$ has an SDR. ∎

Thus, Theorem 38 constructively recovers the result of [LLM+10] (that any
$k$-QSAT instance with an SDR has a (product-state) solution) in the case when
the additional conditions of Theorem 38 are met (recall [LLM+10] works on all
graphs with an SDR, but is not constructive). Finally, in Theorem 50, we show
a generalization of Corollary 43 above with a self-contained proof based on
Hall’s marriage theorem.

######  Remark 44 (AG view).

As stated at the outset of Section 4, we now give a brief sketch of the ideas
discussed here in AG terms. It is natural to represent product states using
the Segre map $(v_{1},\ldots,v_{n})\to v_{1}\otimes\cdots\otimes v_{n}$ which
describes an embedding of the $n$-fold product of projective lines into a
projective space of dimension $2^{n}-1$. Using this representation, the
product satisfiability ${\mathcal{S}}_{H}$ can be naturally thought of as an
algebraic set in $({\mathbb{P}}^{1}(\mathbb{K}))^{n}$. In the language of
algebraic geometry, the Transfer Lemma (Lemma 28) says that if the interaction
graph is $k$-uniform of transfer type $b=|V(G)|-|E(G)|$, then
${\mathcal{S}}_{H}$ can be realized as an iterated blow-up of
$({\mathbb{P}}^{1}(\mathbb{K}))^{b}$, so in particular it is a rational
variety. Moreover, the blow-ups are taken along the loci where the transfer
functions $g_{i}$ vanish or equivalently where their projectivizations (which
are by construction rational functions in suitable coordinates) are
indeterminate. On the other hand, the Qualifier Lemma (Lemma 30) says that the
projection of ${\mathcal{S}}_{H}$ along the coordinates corresponding to
$G_{0}$ is contained in the algebraic set $X_{H}$ cut out by the regular
functions $h_{s}$. In general, we cannot guarantee that the projection of
${\mathcal{S}}_{H}$ coincides with $X_{H}$. However, Theorem 38 says that in
the non-trivial case when $X_{H}$ is a hypersurface, then the projection of
${\mathcal{S}}_{H}$ does indeed coincide with $X_{H}$.

###  4.4 Explicit algorithm statement, runtime, and speedups

Figure 6 states our algorithm explicitly. We now give a runtime analysis, as
well as families of inputs for which a speedup (polynomial to exponential) is
obtained over brute force methods.

1:input: A $k$-uniform hypergraph $G=(V,E)$ (along with a constraint $H_{e}$
for each hyperedge $e$), transfer filtration $F$ of $G$ of type $b$ and radius
$r$.

2:output: An $n$-qubit tensor product assignment satisfying all constraints,
if one exists. Else, the algorithm rejects.

3:

4:procedure BLOWUP($G,F$)

5: Apply Decoupling Lemma (Lemma 18) to $G$ to compute $\widetilde{G}$ and
$p:V(\widetilde{G})\mapsto V(G)$.

6: Apply Transfer Lemma (Lemma 28) to $\widetilde{G}$ to compute
$g_{1},\ldots,g_{n}:W^{b}\mapsto W$.

7: Apply Qualifier Lemma (Lemma 30) to $g_{1},\ldots,g_{n}$ to compute
$h_{1},\ldots,h_{m-n+b}:W^{b}\mapsto\mathbb{K}$.

8: Compute foundation assignment $v_{1},\ldots,v_{b}\subseteq W$ such that for
all $s\in[m-n+b]$, $h_{s}(v_{1},\ldots,v_{b})=0$ and
$g_{i_{s}}(v_{1},\ldots,v_{b})\neq 0$ . If no such assignment found, reject.

9: For each qubit $i$ of $G$, return assignment $g_{i}(v_{1},\ldots,v_{b})$.

10:end procedure

Figure 6: Parameterized algorithm for Quantum $k$-SAT.

##### Runtime analysis.

We bound the complexity of each step of Figure 6. Note these bounds are rather
naive; improved polynomial factors can likely be attained by an appropriate
use of data structures and a more careful analysis. Below, we assume
$\mathbb{K}={\mathbb{C}}$, use of the Random Access Machine model (e.g.
looking up entries in arrays costs constant time), and we count the number of
field operations over ${\mathbb{C}}$ (as opposed to bit operations).

  * •

(Decoupling Lemma, Line $5$) Let $(E_{1},\ldots,E_{m})$ denote the order in
which edges of $G$ are added in the filtration $F$. In order to compute
$\widetilde{G}$ and $p$, the first step is to compute
$r:{\left\\{1,\ldots,m\right\\}}\mapsto{\left\\{0,\ldots,m-1\right\\}}$ from
Remark 16. Recall this was defined such that $r(i)$ is the smallest integer
satisfying $\left\lvert E_{i}\setminus V(G_{r(i)})\right\rvert=1$, i.e. the
first point in the filtration at which $E_{i}$ could be added next via the
introduction of precisely one vertex. Since $k\in O(1)$, one can compute all
vertex sets $V(G_{i})$ in $O(m)$ time. With all $V(G_{i})$ precomputed,
computing $r(i)$ now takes $O(i)$ time, and so precomputing all values of $r$
takes $O(m+m^{2})\in O(m^{2})$ total time.

Moving on to $p$, since $p(i)=i$ when $i\in[b]$ and $p(i)=E_{i-b}\setminus
V(G_{r}(i-b))$ when $i\in{\left\\{b+1,\ldots,b+m\right\\}}$, each entry $p(i)$
can now be computed in $O(1)$ time, implying all values of $p$ can be computed
in time $O(m+b)$.

Since the preimage $p^{-1}(j)$ can be of size up to $m$, computing it takes
$O(m)$ time, implying computing $\underline{j}$ and $\widetilde{E_{i}}$ take
$O(m)$ time. Therefore, computing all edges $\widetilde{E_{i}}$ takes
$O(m(m+b))$ time.

The total runtime for this step is hence $O(m^{2})+O(m+b)+O(m(m+b))\in
O(m(m+b))$.

  * •

(Transfer Lemma, Line $6$) To analyze the cost of computing a transfer
function (where by “computing”, we mean explicitly writing out all
coefficients of the corresponding multi-variate polynomial) , $g:W^{b}\mapsto
W$, it is helpful to use the construction of Example 29 as a guide. Namely,
since $W$ is two-dimensional, it suffices to analyze the maximum cost of
outputting a component of $g$’s two-dimensional output vector. This requires
bounding the cost of expanding an expression of the form

$H^{*}(g_{i_{1}}(v_{1},\ldots,v_{b})\otimes\cdots\otimes
g_{i_{k-1}}(v_{1},\ldots,v_{b})\otimes w_{l})=:H^{*}(\mathbf{u})$

(for $w_{l}$ some fixed basis vector for $W$) as a multivariate polynomial in
the $2b$ components of $v_{1},\ldots,v_{b}$. For convenience, let
$\mathbf{u}=g_{i_{1}}(v_{1},\ldots,v_{b})\otimes\cdots\otimes
g_{i_{k-1}}(v_{1},\ldots,v_{b})\otimes w_{l}$ above, and set
$S={\left\\{i_{1},\ldots,i_{k-1}\right\\}}$. Observe now that if $g_{i_{t}}$
has degree $(d_{i_{t},1},\ldots,d_{i_{t},b})$, then since $g_{i_{t}}$ is a
multivariate polynomial, it has at most $O(d_{i_{t},1}d_{i_{t},2}\cdots
d_{i_{t},b})$ distinct monomials. It follows that computing an arbitrary entry
of $\mathbf{u}$ costs $O(\Pi_{i\in S}\Pi_{j=1}^{b}d_{i,j})$ time (for this
simple analysis, we naively multiply out all monomials and add like terms).
Note next that if $H$ denotes the $k$-local Hamiltonian term corresponding to
$H^{*}$, then $H^{*}(\mathbf{u})=\mathbf{u}^{\dagger}H\mathbf{u}$. Thus,
assuming $k\in O(1)$, computing $H^{*}(\mathbf{u})$ costs

$O\left(\Pi_{i\in S}\;\Pi_{j=1}^{b}\;d^{2}_{i,j}\right)$ (5)

time in the worst case. By the degree bounds of Lemma 28 and Remark 26, we
have $d_{i,j}\leq F^{(b)}_{i}\in o(2^{i})$. Equation (5) can hence be bounded
by

$O\left(\Pi_{i\in S}\;d^{2b}_{i,j}\right)\in O\left(2^{2b\sum_{i\in
S}i}\right)\in O\left(2^{2bk\max_{i\in S}i}\right),$ (6)

where the last statement follows since $\left\lvert S\right\rvert\leq k$. A
naive analysis would now suggest $\max_{i\in S}\leq n$, as there are $n$
transfer functions $g$. However, this analysis is too loose — it assumes the
worst case that each tensor factor $g_{i_{1}}(v_{1},\ldots,v_{b})$ depends
recursively on all previous transfer functions $g_{1}\ldots,g_{i_{1}-1}$
(hence the degree of $g_{i_{1}-1}\leq F^{b}_{i}$ for $i\in[n]$). By taking the
_radius_ of the filtration into account, $\rho(G,b)$, we can obtain a much
smaller bound when the radius is small. Specifically, similar to the analysis
of Lemma 30, one can instead show $d_{i,j}\leq F^{(b)}_{\rho(G,b)+b+1}\in
O(2^{\rho(G,b)+b})$. Thus, we can improve Equation (6) to

$O\left(2^{2kb(\rho(G,b)+b)}\right).$

Since there are $n$ transfer functions in total, the cost of Line 6 is hence
$O\left(n2^{2kb(\rho(G,b)+b)}\right)$, where recall we assume $k\in O(1)$.

  * •

(Qualifier Lemma, Line $7$) We consider the cost of computing an arbitrary
qualifier $h_{s}$. Since in Line 5 we already computed $\underline{i}$ for all
$i\in{\left\\{1,\ldots,m+b\right\\}}$, we may compile set
${\left\\{i_{1},\ldots,i_{m-n+b}\right\\}}$ in time $O(m-n+b)$. Since $W$ is a
two-dimensional space, computing $g_{i_{s}}^{\\#}$ takes time linear in the
number of monomials in each amplitude/component of $g_{i_{s}}$, i.e.
$O(d_{i_{s},1}\cdots d_{i_{s},b})\in O\left(2^{b(\rho(G,b)+b)}\right)$ time.
It follows that computing $h_{s}$ requires $O\left(2^{2b(\rho(G,b)+b)}\right)$
time. Since there are $m-n+b$ qualifier functions, the total cost of this step
is

$O\left((m-n+b)2^{2b(\rho(G,b)+b)}\right).$

We may bound the cost of Lines $5$ \- $7$ (which apply to any instance of
$k$-QSAT) by

$O\left((m-n+b)2^{2kb(\rho(G,b)+b)}\right).$ (7)

For arbitrary $k$-QSAT instances, the runtime of Lines $8$ \- $9$ is less
clear (e.g. how to find a common root to all $h_{s}$ while also ensuring
$g_{i_{s}}$ to be non-zero?); however, these steps can indeed be solved for
the family of instances with generic constraints and transfer type $b=n-m+1$,
as demonstrated in Section 4.3. As noted in Remark 41, in this case we may
reduce Lines $8$ \- $9$ to solving for the roots of a single univariate
polynomial (moreover, the Surjectivity Lemma 36 ensures $g_{i_{s}}$ outputs a
non-zero value). We now analyze this reduction’s runtime.

  * •

(Lines $8$ \- $9$, generic constraints, $b=n-m+1$) When $b=n-m+1$, there is
precisely one qualifier function $h_{s}(v_{1},\ldots,v_{b})$, which is a
multivariate polynomial in $2b$ complex variables, and has degree
$(d_{s1},\ldots,d_{sb})$ for $d_{sr}\leq 2^{\rho(G,b)+b+2}$ (by Lemma 30) for
all $r\in[b]$. Following Remark 41, fix
$w_{1}=\cdots=w_{b}=|0\rangle\in{\mathbb{C}}^{2}$ and
$w^{\prime}_{b}=|1\rangle\in{\mathbb{C}}^{2}$ and consider variable
$x\in{\mathbb{C}}$. Then,
$q(x):=h_{s}(w_{1},\ldots,w_{b-1},w_{b}+xw^{\prime}_{b})$ is a univariate non-
constant101010Note that, in principle, $q(x)$ could be constant. However,
since $h_{s}$ is non-constant by the Qualifier Lemma, there must be at least
one coordinate $j\in{\left\\{1,\ldots,b\right\\}}$ such that redefining $q(x)$
to have its $j$th argument to equal $w_{j}+xw_{j}^{\prime}$, and all other
arguments $j^{\prime}\neq j$ equal to $|\psi\rangle$ for some appropriate
constant vector $|\psi\rangle$, yields a non-constant polynomial over $x$.
(For example, set the entries of $|\psi\rangle$ to be sufficiently large in
magnitude to ensure the monomials of different degrees in the expansion of
$h_{s}$ cannot cancel out. Recall here that since we are essentially working
in projective space, $|\psi\rangle$ need not be normalized.) polynomial over
$x$ with degree at most

$d\leq 2^{\rho(G,b)+b+2}.$ (8)

Observe that $h_{s}$ has at most $M=\Pi_{s}d_{sr}\leq 2^{b(\rho(G,b)+b+2)}$
monomials. Thus, computing $q(x)$ takes $O(M)$ time since each of the $2b$
complex variables plugged into $h_{s}$ is given a value from set
${\left\\{0,1,x\right\\}}$ (i.e. simplifying monomials with large exponents is
trivial). To find a root of $q$, which exists since ${\mathbb{C}}$ is
algebraically closed, we can now apply an algorithm of Schönhage [Sch86] as
follows.

Schönhage’s univariate polynomial factorization algorithm. Let us write
$q(x)=\sum_{i=1}^{d}c_{i}x^{i}\in{\mathbb{C}}[x]$, and define one-norm
$\left\|\,q\,\right\|_{1}:=\sum_{i=1}\left\lvert c_{i}\right\rvert$. Then,
Equation (3.2) of [Sch86] says “approximate factorization” of $q$ is possible
within error111111For clarity, Equation (3.2) of [Sch86] assumes
$\left\|\,q\,\right\|_{1}\leq 1$, and hence the error is stated therein as
$\epsilon=2^{-N}$. In our setting, however, we first need to rescale our $q$
to ensure $\left\|\,q\,\right\|_{1}\leq 1$. This does not affect the number of
field operations required for Schönhage’s algorithm, but results in the
multiplicative $\left\|\,q\,\right\|_{1}$ term (which is absent in [Sch86]) in
the resulting bound on accuracy, Equation (9) . We hence define the error as
$\epsilon=2^{-N}\left\|\,q\,\right\|_{1}$ here for convenience.
$\epsilon=2^{-N}\left\|\,q\,\right\|_{1}$ in $O(d^{3}\log d+d^{2}N)$ field
operations. Here, “approximate factorization” within error $\epsilon$ means
computing linear factors $L_{j}(x)=u_{j}x+v_{j}$ for $1\leq j\leq d$ such that

$\left\|\,q(x)-L_{1}(x)\cdots
L_{d}(x)\,\right\|_{1}<2^{-N}\left\|\,q\,\right\|_{1}.$ (9)

Let $w_{j}=-v_{j}/u_{j}\leq 1$ denote the root of linear factor $L_{j}(x)$.
Given Equation (9), the next question is: How closely do the $w_{j}$
approximate the roots $z_{j}$ of $q(x)$? As done in Section 3.4 of [Sch86],
one can apply the perturbation bound of Theorem 2.7 of [Sch85] to obtain the
following. If $\left\|\,q(x)-L_{1}(x)\cdots
L_{d}(x)\,\right\|_{1}\leq\eta\left\|\,q(x)\,\right\|_{1}$ for $\eta\leq
2^{-7d}$, then there exists an ordering of the $w_{j}$ such that for all $j$,

$\left\lvert w_{j}-z_{j}\right\rvert<9\eta^{1/d}.$

It follows that in order to compute the roots $z_{j}$ within additive error
$2^{-p(n)}$ for some polynomial $p$, it suffices to approximately factorize
$q$ within error $\epsilon=\left\|\,q\,\right\|_{1}/(9^{d}2^{p(n)d})$, which
can be accomplished in time

$O\left(d^{3}\log d+d^{2}\log\left(9^{d}2^{p(n)d}\right)\right).$

  * •

(Line 9) We now have a root
$(v_{1}:=|0\rangle,\ldots,v_{b-1}:=|0\rangle,v_{b}:=|0\rangle+x|1\rangle)$ of
$h_{s}$. To compute $g_{i}(v_{1},\ldots,v_{b})$ for any $i\in[n]$ involves
evaluating a multivariate polynomial of degree $(d_{s1},\ldots,d_{sb})$ for
$d_{sr}\leq 2^{\rho(G,b)+b+2}$ for all $r\in[b]$. Naively substituting in our
root and using square-and-multiply to compute monomials with large powers,
evaluating each $g_{i}$ hence requires at most time

$O((\rho(G,b)+b)2^{b(\rho(G,b)+b+2)}).$

Combining the cost of all steps, we find $k$-QSAT instances with generic
constraints and $b=n-m+1$ require total time at most (for $d\leq
2^{\rho(G,b)+b+2}$)

$O(mn)+O\left(2^{2kb(\rho(G,b)+b)}\right)+O\left(d^{3}\log
d+d^{2}\log\left(9^{d}2^{p(n)d}\right)\right)+O((\rho(G,b)+b)2^{b(\rho(G,b)+b+2)}),$
(10)

where recall from Equation (8) that $d\leq{\rho(G,b)+b+2}$. Thus, the
algorithm is polynomial in $m$ and $n$, and exponential in $k$ (the locality
of the constraints), $\rho(G,b)$ (the radius), and $b$ (foundation size).

_Aside: Error propagation._ Note that in Line 8, we compute a root $z$ of $q$
within additive error $2^{-p(n)}$. In Line 9, we then substitute this root
into our transfer functions $g_{i}$ to obtain our final assignment on qubit
$i$. This substitution can propagate the additive error from Line 8. However,
since the degrees of the transfer functions are bounded by $\exp(n)$
(specifically, $d_{sr}\leq 2^{\rho(G,b)+b+2}$), it follows that by choosing
$p$ to be a sufficiently large fixed polynomial, one can make the additive
error for the output of $g_{i}$ exponentially small in $n$.

##### On exponential speedups via Theorem 38.

Recall Theorem 38 applies to $k$-uniform hypergraphs of transfer type
$b=n-m+1$, such as the semicycle. From a parameterized complexity perspective,
however, most interesting are hypergraphs for which the foundation size $b$
and filtration radius $r$ satisfy $b,r\in o(n+m)$, for which we might obtain
an asymptotic speedup over brute force diagonalization of the Quantum SAT
system. We now discuss various hypergraph families and analyze their
parameters $m$ and $n$ versus $b$ and $r$. In particular, we obtain quadratic
(tiling of torus, fir tree) to _exponential_ (crash) separations between these
parameters. Note that for the runtime of Equation (10), a quadratic separation
is unfortunately not enough for an asymptotic speedup. However, an
_exponential_ separation in parameters, as for the crash family of
hypergraphs, implies our parameterized algorithm runs in polynomial time,
whereas brute force diagonalization would require time exponential in $m$ and
$n$.

######  Example 45 (Semicycles).

We begin with the study of semicycles, for which there is no separation in
parameters. Namely, let $S_{t,k}$ denote the $k$-uniform hypergraph with
vertices $V(S_{t,k})=\mathbb{Z}/t\mathbb{Z}$ and edges
$E(S_{t,k})=\\{E_{0},\ldots,E_{t-k+1}\\}$ such that
$E_{i}=\\{i,i+1,\ldots,i+k-1\\}$ for every $i\in\\{0,\ldots,t-k+1\\}$. By
construction, $|V(S_{t,k})|-|E(S_{t,k})|+1=k-1$ for every $t$. On the other
hand, $S_{t,k}$ is line graph connected for every $t$ and thus has transfer
type $k-1$ by Example 12. Depending on how the transfer filtration is chosen,
the transfer radius is at least $|E(S_{t,k})|/2$ and at most $|E(S_{t,k})|$.
Thus, the radius $r$ satisfies $r\in\Theta(|E(S_{t,k})|)$, i.e. no separation
in parameters exists.

######  Example 46 (Modified tiling of the torus).

We next discuss a slight modification of the tiling of torus which yields a
quadratic separation in parameters. Let $k\geq 3$ and let $t$ be a positive
integer. Let $V_{t,k}$ be the set of pairs $(p,q)$ of integers such that
$0\leq(k-2)q\leq p\leq(k-2)t$. Let $G_{t,k}$ be the $k$-uniform hypergraph
with vertices $V(G_{t,k})=V_{t,k}$ and edges
$E_{r,s}=\\{(r,s),(r+1,s),\ldots,(r+k-2,s),(r+k-2,s+1)\\}$ for each pair
$(r,s)\in V_{t-1,k}$. Then $G_{t,k}$ has $\frac{(t+1)(2+t(k-2))}{2}$ vertices
and $\frac{t(2+(t-1)(k-2))}{2}$ edges. All vertices except for $(0,0)$,
$(t(k-2),0)$ and $(t(k-2),t)$ have degree at least $2$. There exists a
transfer filtration with foundation $\\{(0,0),\ldots,(t(k-2),0)\\}$ obtained
by adding the edges in the following order

$E_{0,0},E_{1,0},\ldots,E_{(t-1)(k-2),0},E_{k-2,1},E_{k-1,1},\ldots,E_{(t-1)(k-2),1},E_{2(k-2),2},\ldots,E_{(t-1)(k-2),t-1}\,.$

In particular, this filtration has radius $t$.

Now, consider the $k$-uniform hypergraph $T_{t,k}$ obtained by identifying the
degree $1$ vertices of $G_{t,k}$. (This can be visualized similar to the
tiling of the torus as in Figure 14, except one keeps only the “lower
triangular” portion of Figure 14, i.e. vertices
$v_{2},v_{3},v_{4},v_{5},v_{7}$ from Figure 14 are discarded. Unlike the
tiling of the torus, however, the example here has a transfer filtration type
which satisfies the preconditions of Theorem 38, as stated below.) Then
$T_{t,k}$ has a transfer filtration of type

$\displaystyle t(k-2)$
$\displaystyle=\frac{(t+1)(2+t(k-2))}{2}-2+\frac{t(2+(t-1)(k-2))}{2}+1$
$\displaystyle=|V(T_{t,k})|-|E(T_{t,k})|+1,$

satisfying the preconditions for Theorem 38. Since $T_{t,k}$ has radius $t$,
it follows that the radius and foundation size are $\Theta(t)$ (for $k\in
O(1)$, which is the typical assumption), whereas $\left\lvert
V(T_{t,k})\right\rvert,\left\lvert E(T_{t,k})\right\rvert\in\Theta(t^{2})$,
i.e. there is a quadratic gap between these parameters.

######  Example 47 (Fir Tree).

We next give another example of a hypergraph family (Figure 5) with a
quadratic separation in parameters. For each $k\geq 3$, $t\geq 1$ and
$i\in\mathbb{Z}/k\mathbb{Z}$ let $G_{t,k,i}$ be a copy of the $k$-uniform
hypergraph $G_{t,k}$ introduced in Example 46. Let $H_{t,k}^{\prime}$ be
obtained by identifying the vertex $(t(k-2),0)$ of $G_{t,k,i}$ with the vertex
$(0,0)$ of $G_{t,k,i+1}$ for each $i\in\mathbb{Z}/k\mathbb{Z}$ and let
$H_{t,k}$ be the graph obtained from $H^{\prime}_{t,k}$ by adding the edge
whose elements are the vertices $(t(k-2),t)$ for each of the $G_{t,k,i}$. For
example, $H_{4,3}$ is illustrated in Figure 5. Then $H_{t,k}$ has a filtration
of type

$\displaystyle tk(k-2)$
$\displaystyle=k\left(\frac{(t+1)(2+t(k-2))}{2}-1\right)-k\frac{t(2+(t-1)(k-2))}{2}-1+1$
$\displaystyle=|V(H_{t,k})|-|E(H_{t,k})|+1$

and radius $t+1$. Thus, we have another family of hypergraphs which satisfy
the preconditions of Theorem 38, and have a quadratic gap between the radius
and foundation size (both $\Theta(t)$) versus the number of vertices and edges
(both $\Theta(t^{2})$).

$222$$221$$212$$211$$122$$121$$112$$111$$22$$21$$12$$11$$2$$1$${(0,2)}$${(0,1)}$

Figure 7: Depiction of $3$-uniform crash hypergraph $C_{3,3}$. Generally,
$C_{t,k}$ has an exponential separation between the filtration radius and
foundation size versus number of vertices and edges.

######  Example 48 (Crash).

Finally, we give a $k$-uniform hypergraph family with an exponential
separation in parameters (Figure 7). For $k\geq 2$ an integer, let
$\Sigma=\\{1,2,\ldots,k-1\\}$ be an alphabet of size $k-1$. For $t\geq 1$ an
integer, consider the hypergraph $C_{t,k}$ with vertices
$V(C_{t,k})=\bigcup_{j=0}^{t}V_{j}$ where $V_{j}=\Sigma^{t-j+1}$ for all
$1\leq j\leq t$, and $V_{0}=\\{(0,x)\,|\,x\in\Sigma\\}$. The edge set of
$C_{t,k}$ is the union of all edges of the following three forms:

  1. 1.

For every $x\in V_{1}$, $E_{x}=\\{x\\}\cup V_{0}$;

  2. 2.

for every $2\leq j\leq t$ and every $x\in V_{j}$,
$E_{x}=\\{x\\}\cup\\{xa\,|,a\in\Sigma\\}$;

  3. 3.

$E_{0}=\\{(0,1)\\}\cup V_{t}$.

Then $C_{t,k}$ has a transfer filtration with foundation $V_{0}$ obtained by
first adding all the edges $E_{x}$ with $x\in V_{1}$, then adding all the
edges $E_{x}$ with $x\in V_{2}$ etc. with $E_{0}$ added last. Clearly this
transfer filtration has radius $t$ and type

$\displaystyle k-1$
$\displaystyle=(k-1)\left(1+\frac{(k-1)^{t}-1}{k-2}\right)-\frac{(k-1)((k-1)^{t}-1)}{k-2}-1+1$
$\displaystyle=|V(C_{t,k})|-|E(C_{t,k})|+1\,.$

In particular, this family satisfies the preconditions for Theorem 38 and
yields an exponential separation between radius and foundation size
($\Theta(t)$ and $O(k)$, respectively) versus the number of vertices and edges
($\Theta[(k-1)^{t}]$ for constant $k\geq 3$). Thus, via the runtime of
Equation (10), our algorithm runs in polynomial time on crash (i.e. time
$\operatorname{poly}(|V(C_{t,k})|,|E(C_{t,k})|)$), whereas brute force
diagonalization would require exponential time in $|V(C_{t,k})|$.

##  5 On the structure of 3-uniform hypergraphs

In this section, we take a structural graph theory perspective, and make steps
towards understanding the set of $3$-uniform hypergraphs $G=(V,E)$ in which
each edge is matched to a unique vertex. In the combinatorics literature, such
a matching for a set system is called a _System of Distinct Representatives
(SDR)_ [Juk11]. Formally, an SDR for a sequence of sets $S_{1},\ldots,S_{m}$
is a sequence of distinct elements $x_{1},\ldots,x_{m}$ such that $x_{i}\in
S_{i}$ for all $i\in[m]$. Hall’s well-known Marriage Theorem says that a set
system ${\left\\{S_{i}\right\\}}_{i=1}^{m}$ has an SDR if and only if for any
$I\subseteq[m]$, $\left\lvert\bigcup_{i\in I}S_{i}\right\rvert\geq\left\lvert
I\right\rvert$.

To begin, let us state a known corollary of the Marriage Theorem, which will
help foreshadow the complexity involved in attempting to characterize the set
of $3$-uniform hypergraphs with SDRs. Let $m=\left\lvert E\right\rvert$ and
$n=\left\lvert V\right\rvert$ for brevity.

######  Corollary 49.

[see, e.g., Corollary 5.2 of [Juk11]] Let $G=(V,E)$ be a $d$-regular
$r$-hypergraph. If $m\leq n$, then the hypergraph has an SDR.

Thus, the class of hypergraphs with SDRs is, in the sense above, not
necessarily small. In this section, we focus our attention on the edge case
$m=n$. In this case, any $2$-uniform hypergraph (i.e. a _graph_) must be a
cycle (up to attaching disjoint paths to each vertex of the cycle). In
contrast, we will see that the set of $3$-uniform hypergraphs with $m=n$ and
with SDRs is more complex.

Aside. In Corollary 49, note via doublecounting that we must have $nd=mr$
(i.e. add up all degrees on the left, and take the union of all edges on the
right); thus, if $r=3$ and $m=n$, we must have regularity $d=3$. This yields
that any $3$-regular $3$-uniform hypergraph with $m=n$ has an SDR.

Finally, using the Marriage Theorem we obtain an elementary proof of a
generalization of Corollary 43.

######  Theorem 50.

Let $G$ be a $k$-uniform hypergraph of transfer type $b\leq|V(G)|-|E(G)|+k-1$.
Then $G$ has an SDR. Moreover, this bound is tight.

###### Proof.

Consider a transfer filtration $G_{0}\subseteq G_{1}\subseteq\cdots\subseteq
G_{m}=G$ so that $G$ has $m$ edges and transfer type $b=|V(G_{0})|$. Suppose
the edges $E(G)=\\{E_{1},\ldots E_{m}\\}$ are ordered in such a way that
$E(G_{i})\setminus E(G_{i-1})=\\{E_{i}\\}$ for all $i\in\\{1,\ldots,m\\}$. By
the Marriage Theorem, it suffices to prove that $|E_{i_{1}}\cup\cdots\cup
E_{i_{l}}|\geq l$ for any increasing sequence $1\leq
i_{1}<i_{2}<\cdots<i_{l}\leq m$. For each $i\in\\{1,\ldots,m\\}$, let
$\mu_{i}=|V(G_{i-1})|-|V(G_{i})|+1$. By definition of transfer filtration,
$\mu_{i}\in\\{0,1\\}$ for each $i\in\\{1,\ldots,m\\}$. More precisely,
$\mu_{i}=0$ if and only if $E_{i}$ contains a vertex that does not belong to
any $E_{j}$ with $j<i$. Hence, given any increasing sequence $1\leq
i_{1}<i_{2}<\cdots<i_{l}\leq m$, we have $|E_{i_{1}}|=k$, $|E_{i_{1}}\cup
E_{i_{2}}|\geq k+1-\mu_{i_{2}}$ and, iteratively adding one edge at the time,

$|E_{i_{1}}\cup E_{i_{2}}\cup\cdots\cup E_{i_{l}}|\geq
k+l-1-(\mu_{i_{2}}+\cdots+\mu_{i_{l}}).$ (11)

Since by assumption we have

$\mu_{i_{2}}+\cdots+\mu_{i_{l}}\leq\mu_{1}+\mu_{2}+\cdots+\mu_{m}=b-|V(G)|+|E(G)|\leq
k-1\,.$ (12)

Substituting (12) into (11) we obtain

$|E_{i_{1}}\cup E_{i_{2}}\cup\cdots\cup E_{i_{l}}|\geq k+l-1-(k-1)\geq l$

which, by the Marriage Theorem, proves the bound. to prove that the bound is
tight, consider a $k$-uniform hypergraph $G$ with $|V(G)|=k$ and $|E(G)|=k+1$
so that the same edge is repeated $k+1$ times. Clearly there exist a transfer
filtration of type $k-1>k-2=|V(G)|-|E(G)|+k-1$ and (since $|V(G)|<|E(G)|)$,
$G$ has no SDR. Hence the bound is tight.

∎

###  5.1 Intersecting families

We begin with the study of $3$-uniform hypergraphs which are _intersecting
families_. Here, a set system $S$ is an _intersecting family_ if any pair of
sets has non-empty intersection. We say the system is _$k$ -intersecting_ if
any distinct pair of sets $A,B\in S$ satisfies $\left\lvert A\cap
B\right\rvert=k$.

####  5.1.1 $2$-intersecting families

For $2$-intersecting families, we actually characterize a _larger_ class: The
set of $3$-uniform hypergraphs with the weaker condition that _if_ a pair of
distinct edges $e_{i}$ and $e_{j}$ intersect, then either $\left\lvert
e_{i}\cap e_{j}\right\rvert=2$ (Lemma 51) or $\left\lvert e_{i}\cap
e_{j}\right\rvert\geq 2$ (Lemma 53). The characterization for $2$-intersecting
families follows as an immediate corollary, and is given in Corollary 52.

######  Lemma 51.

Let $G=(V,E)$ be a $3$-uniform hypergraph such that:

  1. 1.

$m=n$ and $G$ has an SDR, and

  2. 2.

If a pair of distinct edges $e_{i}$ and $e_{j}$ intersects, then $\left\lvert
e_{i}\cap e_{j}\right\rvert=2$.

Then $G$ is a cycle of length $4$.

###### Proof.

We proceed by case analysis. We begin with a pair of intersecting edges (WLOG
we may assume one such pair exists) as in Figure 8:

$v_{1}$$v_{2}$$v_{3}$$v_{4}$

Figure 8: A pair of edges with intersection size $2$.

We now analyze how one can “grow” the graph by adding hyperedges. Consider
first the formation of a tight star as in Figure 9.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$

Figure 9: A $3$-uniform hypergraph which is a tight star of size $3$.

We argue that this structure is impossible, given conditions 1 and 2. To see
why, denote vertices $\\{v_{1},v_{4},v_{5}\\}$ as “outer” vertices and
$\\{v_{2},v_{3}\\}$ as “inner” vertices. By symmetry, there are seven options
for adding a new edge to the tight star:

  1. (i)

Add an edge containing a new vertex $v_{6}$, an outer vertex, and an inner
vertex, e.g. $\\{v_{1},v_{2},v_{6}\\}$. This violates property 2 since
$\left\lvert\\{v_{1},v_{2},v_{6}\\}\cap\\{v_{2},v_{3},v_{4}\\}\right\rvert=1$.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$

  2. (ii)

Add an edge containing one new vertex $v_{6}$, and two outer vertices, e.g.
$\\{v_{1},v_{5},v_{6}\\}$. This violates property 2, since
$\left\lvert\\{v_{1},v_{5},v_{6}\\}\cap\\{v_{2},v_{3},v_{5}\\}\right\rvert=1$.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$

  3. (iii)

Add an edge containing one new vertex $v_{6}$, two inner vertices, e.g.
${\left\\{v_{2},v_{3},v_{6}\right\\}}$, which is the only case not violating
property 2.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$

  4. (iv)

Add an edge containing two outer vertices, and one inner vertex, e.g.
${\left\\{v_{1},v_{2},v_{5}\right\\}}$, which violates property 2, since
$\left\lvert\\{v_{1},v_{2},v_{5}\\}\cap\\{v_{2},v_{3},v_{4}\\}\right\rvert=1$.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$

  5. (v)

Add an edge containing two inner vertices and one outer vertex, e.g.
${\left\\{v_{2},v_{3},v_{4}\right\\}}$, which clearly violates property 2.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$

  6. (vi)

Add an edge containing three outer vertices, e.g.
${\left\\{v_{1},v_{5},v_{4}\right\\}}$, which violates property 2 since
$\left\lvert\\{v_{1},v_{5},v_{4}\\}\cap\\{v_{2},v_{3},v_{4}\\}\right\rvert=1$.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$

  7. (vii)

Add two new vertices, and one inner or outer vertex. This violates property 2.

We conclude that the only possibility is case (iii), which grows the tight
star. In other words, once we have a tight star, our only option is to
continue to build a larger tight star (with distinct edges). But a tight star
cannot satisfy property 1, since it has $n=m+2$. Thus, $G$ cannot contain a
tight star (consisting of more than $2$ edges).

Let us continue our case analysis of how Figure 8 can be extended:

  1. (a)

Add a new vertex and two outer vertices, which violates property 2.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$

  2. (b)

Add a new vertex, one inner vertex, and one outer vertex, which violates
property 2, e.g. in:

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$

  3. (c)

The only remaining option is to add an edge such as the blue one below. This
temporarily violates property 1, since $m\neq n$.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$

An analogous case analysis shows that the only way to proceed is to add the
yellow edge below, which yields a cycle of length $4$, and which satisfies
properties 1 and 2. No further edges can be added, completing the proof.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$

∎

Lemma 51 yields the following immediate corollary, obtained by observing that
the cycle of length $4$ is in fact a $2$-intersecting family.

######  Corollary 52.

The unique $3$-uniform hypergraph which (1) is a $2$-intersecting family, (2)
has $m=n$, and (3) has an SDR is the cycle of length $4$.

More generally, we can relax the statement of Lemma 51 to enforce only
$\left\lvert e_{i}\cap e_{j}\right\rvert\geq 2$ (as opposed to $\left\lvert
e_{i}\cap e_{j}\right\rvert=2$) and still obtain a characterization. Note that
although the statement of Lemma 53 below does not require $G$ to _a priori_ be
an intersecting family, the graphs obtained in the characterization are indeed
intersecting families (but not necessarily $k$-intersecting for some fixed
$k$).

######  Lemma 53.

Let $G=(V,E)$ be a $3$-uniform hypergraph with property 1 in Lemma 51, and
assume each pair of edges $e_{i}$ and $e_{j}$ which intersects satisfies
$\left\lvert e_{i}\cap e_{j}\right\rvert\geq 2$. Then $G$ is one of the
following:

  1. (i)

A 3-stacked set, or

  2. (ii)

a tight star with two 2-stacked sets, or

  3. (iii)

a tight star with one 3-stacked set, or

  4. (iv)

a cycle of length $4$.

###### Proof.

Case (i) trivially holds, and case (iv) is given by Lemma 53. For cases (ii)
and (iii), we return to the case analysis in the proof of Lemma 51 involving
Figure 9, i.e. the tight star. Following the proof of Lemma 51, once we have a
tight star, we only have two choices each time we add an edge: (1) Grow the
tight star (case (iii) in Lemma 51), or (2) create a parallel edge (case (v)
in Lemma 51); note this latter case is now possible since we can have
$\left\lvert e_{i}\cap e_{j}\right\rvert=3$. The former choice adds a new
vertex and new edge, preserving the invariant $n-m$. The latter choice keeps
$n$ fixed but increments $m$ by $1$, implying $n-m$ decreases by $1$. It
follows that one must add precisely two parallel edges, yielding cases (ii)
and (iii). Finally, analyzing cases (a), (b), and (c) in Lemma 51 yields that
no other choices of $G$ are possible. ∎

####  5.1.2 $1$-intersecting families

We next consider the set of $3$-uniform hypergraphs in which each pair of
edges intersects in precisely one vertex. In this case, it turns out there is