On efficiently solvable cases of Quantum k-SAT
Marco Aldi Niel de Beaudrap Sevag Gharibian Seyran Saeedi
quant-ph cs.CC math.AG math.CO


Tensor network complexity of multilinear maps
    Kaie Kubjas
    December 30, 2023
=============================================




Estimating ground state energies of local Hamiltonian models is a central problem in quantum physics. The question of whether a given local Hamiltonian is frustration-free, meaning the ground state is the simultaneous ground state of all local interaction terms, is known as the Quantum k-SAT (k-QSAT) problem. In analogy to its classical Boolean constraint satisfaction counterpart, the NP-complete problem k-SAT, Quantum k-SAT is QMA_1-complete (for k≥ 3, and where QMA_1 is a quantum generalization of NP with one-sided error), and thus likely intractable. But 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  “dimer covering” or “matching”; such systems are known to be frustration-free, but it remains open whether one can efficiently compute a ground state.

Our results fall into three directions, all of which relate to the “dimer covering” setting: (1) We give a polynomial-time classical algorithm for k-QSAT when all qubits occur in at most two interaction terms or 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. An explicit family of hypergraphs, denoted Crash, for which such a speedup is obtained is introduced. (3) We conduct a structural graph theoretic study of 3-QSAT interaction graphs which have a “dimer covering”. 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.
 



§ INTRODUCTION

Estimating ground state energies is a central problem in quantum physics. Specifically, given a k-local Hamiltonian H=∑_i H_i acting on n qubits, and where each local interaction term or clause H_i acts non-trivially on a subset of at most k qubits[For clarity, in the general formulation of k-LH, there is no geometric restriction on where the interaction terms act (e.g. on a 1D chain or a 2D lattice).], the aim is to estimate the smallest eigenvalue of H. In 1999, Kitaev showed that this problem, dubbed the k-local Hamiltonian problem (k-LH), is complete for a quantum generalization of NP known as Quantum Merlin Arthur (QMA) <cit.>. This not only demonstrated that k-LH is likely intractable in the worst case, but also spawned an entire area of research at the intersection of mathematics, condensed matter physics, and computational complexity theory known as Quantum Hamiltonian Complexity (see e.g. <cit.> for surveys).

Let us explore this connection to classical complexity theory further. In the canonical NP-complete Boolean constraint satisfaction problem MAX-k-SAT, one is given a set of k-local Boolean functions or constraints/clauses ϕ:=ϕ_i_i=1^m, such that each clause acts on k out of all n bits in the system. (Moreover, for MAX-k-SAT, each ϕ_i is a logical OR of k literals, such as ϕ_i =x_2∨x_3∨⋯∨ x_1, for x the negation of x.) Given such a set of clauses ϕ, the aim is to compute the maximum number of clauses which can be simultaneously satisfied over all assignments to the bits x_1,…, x_n. Note the maximization flavor of this problem; the correct generalization of this to the quantum setting is k-LH, since in k-LH the ground space may also be frustrated, meaning it may be impossible to satisfy all constraints simultaneously. If we instead demand that the ground space be frustration-free, i.e. the ground state |ψ⟩∈(^2)^n lives in the simultaneous ground spaces of each constraint H_i, then we are more accurately considering a quantum analogue of the NP-complete problem k-SAT, in which the question is given ϕ, can we simultaneously satisfy all constraints? This quantum analogue, denoted Quantum k-SAT (k-QSAT), was introduced by Bravyi in 2006 <cit.>, and is QMA_1-complete for k≥ 3 <cit.>. (See “previous work” below for further known results.) (Here, QMA_1 is QMA with perfect completeness, meaning in a YES instance of a given problem, the quantum proof must be accepted with certainty by the quantum verifier.)

Given the importance of such constraint satisfaction problems (classical or quantum) and their intractability (up to standard complexity theoretic conjectures such as P≠NP and BQP≠QMA_1), much effort has been devoted by the classical community to approaches for MAX-k-SAT and k-SAT, including approximation algorithms, heuristic algorithms, and exact algorithms[The distinction between these three approaches is as follows. Approximation algorithms run in polynomial time, and provably provide a solution which is within some fixed prescribed relative error of optimal. A heuristic typically is also polynomial time, but does not provide any guarantee as to the accuracy of the solution found. An exact algorithm produces the optimal solution, but either takes superpolynomial time (as expected) but better than brute force time, or exactly solves a restricted case of the problem in polynomial time.].  A particular direction of research involving exact algorithms is what restrictions to the input are sufficient to allow polynomial-time solvability. In this paper, we focus on this theme, and ask:

Which special cases of k-QSAT can be solved efficiently on a classical computer?


Unfortunately (but also intriguingly), this problem appears to be markedly more difficult quantumly than classically. Consider the motivating example for this work: Classically, if each clause c of a k-SAT instance can be matched with a unique variable v_c (such that v_c appears in clause c), then clearly the k-SAT instance is satisfiable. For example, in the instance ϕ=ϕ_1=x_1∨x_2,ϕ_2=x_1∨ x_2, we can match x_1 with clause ϕ_1 and x_2 with clause ϕ_2. For any such “matched” k-SAT instance, finding a solution is trivial: Set variable v_c to satisfy clause c. In our example, this means setting x_1=1 and x_2=1. (Note that the matching can be found efficiently via a reduction to network flow, which can then be solved in polynomial time via, e.g., the Ford-Fulkerson algorithm <cit.>.) Let us compare and contrast with the quantum setting. Quantumly, it has been known <cit.> since 2010 that k-QSAT instances with “matchings” (also called a “dimer covering” in <cit.>) are also satisfiable/frustration-free. Moreover, a ground state exists which is of a particularly nice form — it can be assumed to be a tensor product state. Despite this, finding said ground state efficiently has proven elusive (indeed, the proof of <cit.> is non-constructive). In complexity theoretic terms, we have a trivial NP decision problem (since the answer is always YES, the system is frustration-free, and the proof is a tensor product state which can be described via polynomially many bits) whose analogous search version is not known to be efficiently solvable. It should be pointed out here that classically, the question of whether decision versus search complexity coincide for NP problems is a long-standing open problem (see, e.g., <cit.>), and so it is perhaps surprising that this phenomenon seems to potentially also play a role in “matched” QSAT. 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, and which can very broadly be summarized as follows: (1) We show how to efficiently solve k-QSAT with sufficiently bounded occurrence of variables, (2) we give a general framework for parameterized algorithms for Quantum k-SAT, which in principle applies to any Quantum k-SAT instance, (3) we attempt to characterize the set of all 3-uniform hypergraphs (which encode interaction graphs for 3-QSAT, formal definitions given shortly) with a “dimer covering”, or formally, a “system of distinct representatives”. Results (1) and (2) partially resolve the open problem of <cit.> by giving efficient classical algorithms for special cases of “matched QSAT”, and result (2) in particular gives (as far as we are aware) the first known parameterized algorithm for QSAT, obtaining exponential speedups over brute force in some cases (Section <ref>). However, we are not yet able to fully resolve whether the decision and search complexity of “matched QSAT” coincide; indeed, as the structural graph theoretic study of (3) suggests, the geometry of all 3-QSAT instances with matchings/dimer coverings appears quite complex.


Definitions and precise statements of results. To more precisely state our results, we now require formal definitions. For this, we first define Quantum k-SAT (k-QSAT) <cit.> and the notion of a system of distinct representatives (SDR). For k-QSAT, the input is a two-tuple Π=(Π_i=|ψ_i⟩⟨ψ_i|_i, α) of rank 1 projectors or clauses[The original definition <cit.> of k-QSAT did not require each Π_i to be rank 1. As in <cit.>, 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.] Π_i∈(^2)^⊗ k, each acting non-trivially on a set of k (out of n) qubits, and non-negative real number α>1/p(n) for some fixed polynomial p. The output is to decide whether there exists a satisfying assignment on n qubits |ψ⟩∈ (^2)^⊗ n, i.e. to distinguish between the cases Π_i|ψ⟩=0 for all i (YES case), or whether ⟨ψ|∑_iΠ_i|ψ⟩≥α (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 <cit.>), given a set system such as a hypergraph G=(V,E), an SDR is a set of vertices V'⊆ V such that each edge in e∈ E is paired with a distinct vertex v_e∈ V' such that v_e∈ e. In previous work on QSAT, an SDR has been referred to as a “dimer covering” <cit.>.


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 now show this threshold is tight[In addition to being NP-hard, whether k-QSAT with at most 3 occurrences of variables is also QMA_1-hard is not clear. For example, the QMA_1-completeness constructions of <cit.> utilize more than 3 occurrences per variable.], in the following sense.

        There exists a polynomial time classical algorithm which, given an instance Π of k-QSAT in which each variable occurs in at most 2 clauses, outputs a satisfying product state if Π 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 <cit.> (particularly the notion of chain reactions from <cit.>), 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.

    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 <ref> resolves the open question of <cit.> 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 <ref> false in general; see Section <ref>.)



 2. Parameterized algorithms for Quantum k-SAT. Our next result, and the main contribution of this paper, gives a parameterized algorithm[Roughly, parameterized complexity characterizes the complexity of computational problems with respect to specific parameters of interest other than just the input size. For example, for an NP-complete graph theoretic problem Π on n vertices, a parameterized algorithm might run in time polynomial in n, but potentially exponentially with respect to some other graph parameter, such as the treewidth of the input graph. In this example, Π would be tractable on input graphs of logarithmic treewidth. Parameterized complexity is the focus of an entire research community classically; see “previous work” for further details.] for explicitly computing (product state) solutions for a non-trivial class of k-QSAT instances. As discussed in Section <ref>, this algorithm in some cases provides an exponential speedup over brute force diagonalization.



 Transfer filtrations. To sketch the idea of the algorithm at a high level, we first introduce a new graph theoretic notion of a transfer filtration for a k-uniform hypergraph G=(V,E) (see Definition <ref> for a formal definition). Intuitively, a “transfer filtration of type b>0” should be thought of as a set of b of qubits (out of all n qubits the k-QSAT instance acts on) which form the “hard core” or foundation of the instance. Roughly, this is in the sense that if one could determine what states to assign to the qubits in the foundation, then resolving the remainder of the instance would be “easy” (this is not entirely accurate, hence the quotes on “easy”).



 Algorithm sketch. With the notion of transfer filtration in hand, our framework for attacking k-QSAT can be sketched at a high level as follows.
 
    
  * (Decoupling step) First, given a k-QSAT instance Π on G with transfer filtration of type b, we “blow-up” Π to a larger, decoupled instance Π^+ (Decoupling Lemma, Lemma <ref>).

    
  * (Solve decoupled instance) The decoupled nature of Π^+ makes it “easier” to solve (Transfer Lemma, Lemma <ref>), in that any assignment to the b “foundation” qubits can be extended to a solution to all of Π^+. This raises the question — how does one map the solution of Π^+ back to a solution of Π?

    
  * (Map solutions back to original instance) We next give a set of “qualifier” constraints h_s (Qualifier Lemma, Lemma <ref>) acting on only the b foundation qubits, with the following strong property: If a (product state) assignment v to the b foundation qubits satisfies the constraints h_s, then not only can we extend v via the Transfer Lemma to a full solution for Π^+ as in Step 1 above, but we can also map this extended solution back to one for the original k-QSAT instance Π. (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 <ref>.)
 
 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=V-E+1. This family includes, e.g., the semi-cycle of Figure <ref>, (a slight modification of) the tiling of the torus (Figure <ref>), and “fir tree” (Figure <ref>). Our main result (Theorem <ref>) says the following: For any k-QSAT instance Π on such a G and whose constraints are generic (see Section <ref>), computing a (product state) solution to Π reduces to solving for a root of a single univariate (see Remark <ref>) polynomial P — any root thereof (which always exists if the field  is algebraically closed) can then be extended back to a full solution for Π.



Advantages of framework. The key advantage of this approach, and what makes it a parameterized algorithm, is the following — the degree of polynomial P, and hence the runtime of the algorithm, scale exponentially only in the foundation size b and a “radius” parameter r of the transfer filtration (assuming k∈ O(1), see Equation (<ref>) 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  for a single univariate polynomial P of polynomial degree, which can be done in polynomial time <cit.>. Indeed, in Section <ref> we give a non-trivial family of k-uniform hypergraphs, denoted Crash (Figure <ref>), for which our algorithm runs in polynomial time, whereas brute force diagonalization would require exponential time.

If, on the other hand, the foundation size b and radius r of the input k-QSAT instance are superlogarithmic, then our algorithm requires superpolynomial time. Even here, however, the framework yields a new result: it gives a constructive proof that all k-QSAT instances satisfying the preconditions of Theorem <ref> have a (product state) solution. In particular, in Corollary <ref> and Theorem <ref>, we observe that such hypergraphs must have SDRs, and so we constructively reproduce the result of <cit.> that any 3-QSAT instance with an SDR is satisfiable by a product state (again, assuming the additional conditions of Theorem <ref> 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 <ref>) 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 <ref>.


 3. A study of 3-uniform hypergraphs with SDRs. Given that computing ground states for k-QSAT instances with SDRs appears challenging, in the hope of helping guide future studies on the topic, our final contribution aims to better understand the set of all k-QSAT instances with SDRs, particularly in the boundary case when E=V. Unfortunately, this in itself appears to be a difficult task (if not potentially impossible, see comments about a “finite characterization” below). Our results here are as follows. 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 <cit.>.) 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 E=V without SDRs. We hope this work highlights the potential complexity involved in dealing with even the “simple” case of  with SDRs.

 

  
*Discussion.
Regarding our parameterized algorithm, we stated earlier that our framework applies to the non-trivial family of k-QSAT instances whose k-uniform hypergraph G=(V,E) has a transfer filtration of “type b=V-E+1”. Let us elaborate on this further, and in particular stress which parts of our framework require this additional assumption on b, and which parts of the framework apply to arbitrary instances of k-QSAT.

First, our notions of transfer filtrations and blow-ups apply to any instance of k-QSAT (and thus also[For 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 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[Whereas our algorithm's runtime benefits greatly from small foundation size, a natural question is whether a “small” versus “large” foundation generally should make k-QSAT easier or harder. Intuitively, indeed one expects a smaller foundation to yield “easier” instances of k-QSAT, as recall the foundation captures the hard “core” of the k-QSAT instance (in that, roughly speaking, assignments to the foundation qubits generically force assignments onto the remaining, non-foundation, qubits). In the “Open Questions” paragraph of Section <ref>, we conjecture that computing the minimum foundation size is NP-hard of a given input hypergraph is actually NP-hard (similar to how computing common parameterized algorithmic parameters such as treewidth is NP-hard <cit.>).] is how small the foundation size b and radius r of the filtration can be chosen for a given hypergraph, as our algorithm's runtime scales exponentially in these parameters; see Equation (<ref>).) More precisely, our techniques in Section <ref>, up to and including the Qualifier Lemma, apply to arbitrary k-QSAT instances. If one also assumes that constraints are generic (but still on an arbitrary hypergraph), then the Surjectivity Lemma (Lemma <ref>) also holds.

The remaining question is Phase 3 of the framework (“Map solutions back to original instance” above) — when can local solutions to the qualifier constraints be extended to global solutions for the entire k-QSAT instance? Answering this requires solving for a common root of a set of high-degree multi-variate polynomials (hence the connection to algebraic geometry). This is where we consider the restriction to input k-uniform hypergraphs of transfer type b=V-E+1, which allows us to reduce the entire framework to the solution of a single univariate (high-degree) polynomial (to which one can now apply the root-finding algorithm of Schönhage <cit.>; see Section <ref>). We stress that the family of k-QSAT instances with b=V-E+1 is non-trivial, and includes the semi-cycle (Figure <ref>), tiling of the torus (Figure <ref>), fir tree (Figure <ref>, and crash (Figure <ref>) families of hypergraphs. In particular, for the latter family we obtain exponential speedups over brute force diagonalization in Section <ref>. For clarity, all runtimes in this paper are rigorous worst-case runtimes.



  
*Previous work. Quantum k-SAT was introduced by Bravyi <cit.>, who gave an efficient (quartic time) algorithm for 2-QSAT, and showed that 4-QSAT is QMA_1-complete. Subsequently, Gosset and Nagaj <cit.> showed that Quantum 3-SAT is also QMA_1-complete, and independently and concurrently, Arad, Santha, Sundaram, Zhang <cit.> and de Beaudrap, Gharibian <cit.> gave linear time algorithms for 2-QSAT. The original inspiration for this paper was the work of Laumann, Läuchli, Moessner, Scardicchio and Sondhi <cit.>, 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 polynomial-time solvable remains open. 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 <cit.>).

In terms of approaches to k-QSAT, a complementary and well-studied tool which should also be mentioned is the Quantum Lovász Local Lemma (QLLL), introduced by Ambainis, Kempe, and Sattath <cit.>. The QLLL non-constructively guarantees frustration-freeness of the input Hamiltonian under certain conditions. Subsequently, Schwarz, Cubitt and Verstraete <cit.> and Sattath and Arad <cit.> provided constructive (i.e. algorithmic) versions of QLLL under the assumption of commuting local terms <cit.>, and more recently Gilyén and Sattath <cit.> gave an algorithm QLLL for non-commuting terms by introducing a uniformly gapped assumption. The QLLL has since been extended to Shearer's bound by Sattath, Morampudi, Laumann and Moessner <cit.>, in that a quantum analogue of Shearer's bound is a sufficient criterion for frustration-freeness. Most recently, He, Li, Sun, and Zhangit showed <cit.> that in fact Shearer's bound is tight in the quantum setting. We remark that the approaches in these works appear distinct from those taken here; for example, the QLLL allows certain cases of k-QSAT to be resolved even when it is not clear the ground space contains a tensor product state, whereas our algorithms search for product state solutions (guaranteed to exist for any k-QSAT instance with an SDR, which recall was the motivation for this work). This also means algorithmic QLLL results such as <cit.> use quantum algorithms to prepare a ground state, whereas our framework here is classical. As a result, our work should be viewed as a complementary approach for tackling k-QSAT instances, which introduces genuinely distinct tools such as parameterized algorithms and blowups from algebraic geometry.

 Finally, in terms of classical k-SAT, in stark contrast to k-QSAT, solutions to k-SAT instances with an SDR can be efficiently computed. As for parameterized complexity,  classically it is a well-established field of study (see, e.g., <cit.> for an overview). The parameterized complexity of SAT and #SAT, in particular, has been studied by a number of works, such as <cit.>, 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 <cit.> have long implicitly used “parameterized” ideas. For example, Markov and Shi <cit.> give a classical simulation algorithm for quantum circuits whose runtime scales polynomially in the size of the circuit, but exponentially in its treewidth. Their algorithm is based on tensor networks (e.g. <cit.>), whose bond dimension can be viewed as a parameter constraining the complexity of the contraction. In particular, 1d tensor networks whose bond dimension is at most polynomial in the length of the chain can be contracted efficiently (a fact used, for example, in the polynomial time algorithm of Landau, Vidick and Vazirani <cit.> for solving the 1D gapped Local Hamiltonian <cit.> problem). This is in stark contrast to 2D tensor networks (often denoted PEPS, for Projected Entangled Pair States), which are #P-hard to contract even for constant bond dimension <cit.>.

 

  
Open questions. We close with a number of open questions. We showed that k-QSAT with at most 2 occurences per variable is efficiently solvable (Theorem <ref>), but 3 occurrences per variable is well-known to be at least NP-hard (for 3-SAT, which is a special case of 3-QSAT). Is 3-QSAT with at most 3 occurrences per variable similarly QMA_1-complete? 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 <ref>? The “parameters” in our results of Section <ref> 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∈, 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 <cit.>) remains open.

 

  
*Organization. Section <ref> gives basic notation and definitions. Section <ref> gives an efficient algorithm for  with bounded occurrence of variables, which also introduces the notions of transfer matrices (which are generalized via transfer functions in Section <ref>). Our main result is given in Section <ref>, 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 <ref>. Finally, Section <ref> conducts a structural graph theoretic study of hypergraphs with SDRs.





§ PRELIMINARIES




  
*Notation. For complex Euclidean space X, (X) denotes the set of linear operators mapping X to itself. For unit vector |ψ⟩∈^2, the unique orthogonal unit vector (up to phase) is denoted |ψ^⊥⟩, i.e. ⟨ψ|ψ^⊥⟩=0.

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


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 ⊆ e_j, then i=j. We say G is k-uniform if all edges have size k.



A k-uniform hypergraph G=(V,E) is a chain if there exists a sequence (v_1,v_2,...,v_l)∈ V^l for l≥ n such that (1) the sequence contains all elements of V at least once, (2) v_1≠ v_l, and (3) E=⋃_1≤ i ≤ l-k+1e_i for distinct edges e_i=v_i,v_i+1,...,v_i+k-1. The length of the chain G is m=l-k+1.




A k-uniform hypergraph G=(V,E) is a cycle if there exists a sequence (v_1,v_2,...,v_l)∈ V^l for l≥ n such that (1) the sequence contains all elements of V at least once, (2) for all 1≤ i ≤ l, e_i=v_i,v_i+1,...,v_i+k-1 are distinct edges in E, where indices are understood modularly. The length of the cycle G is m=l.	


A k-uniform hypergraph G=(V,E) is a semicycle if there exists a sequence (v_1,v_2,...,v_l)∈ V^l for l≥ n such that (1) the sequence contains all elements of V at least once, (2) v_1=v_l, and (3) for all 1≤ i ≤ l-k+1, e_i=v_i,v_i+1,...,v_i+k-1 are distinct edges of G. The length of the semicycle is m=l-k+1.	


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.



Let G=(V,E) be a k-uniform hypergraph. A subset S⊆ 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. ⋃_e∈ Se=k.







§ 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 <cit.>. 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 Π_i=|ψ⟩⟨ψ|∈((^2)^⊗ k), consider Schmidt decomposition |ψ⟩=α|a_0⟩|b_0⟩+β|a_1⟩|b_1⟩, where |a_i⟩∈(^2)^⊗ (k-1) lives in the Hilbert space of the first k-1 qubits and |b_i⟩∈^2 the last qubit. Then, the transfer matrix T_ψ:(^2)^⊗ k-1↦^2 is given by T_ψ = β|b_0⟩⟨a_1| - α|b_1⟩⟨a_0|. In words, given any assignment |ϕ⟩ to the first k-1 qubits, if T_ψ|ϕ⟩∈^2 is non-zero, then it is the unique assignment to qubit k (given |ϕ⟩ on qubits 1 to k-1) which satisfies Π_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),…,e_m=(v_m-1,v_m) for distinct v_i∈ V, and where edge e_i corresponds to constraint |ψ_i⟩. Then, any assignment |ϕ⟩∈^2 to qubit 1 induces a chain reaction (CR) in G, meaning qubit 2 is assigned T_ψ_1|ϕ⟩, qubit 3 is assigned T_ψ_2T_ψ_1|ϕ⟩, and so forth. If this CR terminates before all qubits labelled by V receive an assignment, which occurs if T_ψ_i|ϕ'⟩=0 for some i, this means that constraint i (acting on qubits i and i+1) is satisfied by the assignment |ϕ'⟩ 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,…, 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,…, v_m+1) with m. Then, a CR induced on vertex v_1 with any assignment |ψ⟩∈^2 will in general propagate around the cycle and impose a consistency constraint on v_1. Formally, denote the product T_C=T_ψ_m⋯ T_ψ_1∈(^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 <ref>. Subsequently, we demonstrate the algorithm on an example (Figure <ref>) and discuss its applicability more generally. Section <ref> shows the connection between Theorem <ref> and k-QSAT with SDRs.

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


We begin by setting terminology. Let Π 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', i.e. if there exists c'≠ c such that Q_c⊆ Q_c'. For a qubit v, we use shorthand |v⟩ to denote the current assignment from ^2 to v. For a clause c, |c⟩ denotes the bad subspace of c, i.e. clause c is given by rank-1 projector I-|c⟩⟨c|. The set of clauses vertex v appears in is denoted C_v. For any assignment |v⟩, we introduce shorthand S_|v⟩=⟨v|c⟩| c∈ C_v⊆⋃_i=0^k-1^2^i, where recall c can be a clause on 1,…,k qubits, and we implicitly assume ⟨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 ⟨v|c⟩=(⟨v|⊗ I_w,x)|c⟩∈^4 is the residual constraint on qubits w,x, given assignment |v⟩ to v. Thus, S_|v⟩ 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⟩. As a result, the clauses in S_|v⟩ no longer act on v. The algorithm we design will satisfy that the only possible element of  in S_|v⟩ is 0, which can only be obtained by projecting a constraint |c⟩∈^2 onto its orthogonal complement to satisfy it; thus, we can assume without loss of generality that S_|v⟩⊆⟨v|c⟩| c∈ C_v⊆⋃_i=1^k-1^2^i. Finally, we say two 1-local clauses |c⟩,|c'⟩∈^2 conflict if |c⟩ and |c'⟩ are linearly independent (i.e. |c⟩⟨c|+|c'⟩⟨c'| has an empty null space, meaning there is no satisfying assignment).

The algorithm proceeds as follows. Let Π satisfy the conditions of our claim. For clarity, any time a CR on a path is broken by a transfer matrix T_ψ on edge (u,v), i.e. T_ψ|u⟩=0, we shall implicitly assume we continue by choosing assignment |0⟩ 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” Π 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.  More informally, the algorithm exploits the extra degrees of freedom which arise when each qubit appears in at most two clauses. In particular, by considering clauses in the “right” order below, we are able to (iteratively) greedily satisfy a given clause locally, and propagate the implications of such an assignment via transfer matrix techniques. 


Algorithm A.

    
  * While there exists a 1-local constraint c acting on some qubit v:
        
            
  * If c conflicts with another 1-local clause on v, reject. Else, set |v⟩=|c^⊥⟩∈^2. Set[Setting C_v=S_|v⟩ means we update all clauses c acting on v by projecting qubit v of c onto |v⟩. 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⟩, and remove v from Π.
        
    
  * While there exists a qubit v appearing only in clauses of size at least k'≥ 3:
        
            
  * Set |v⟩=|0⟩ and C_v=S_|v⟩. Remove v from Π.
        
    
  * While there exists a 2-local clause:

    
        
  * If there exists a stacked 2-local clause c, i.e. c'≠ c such that Q_c⊆ Q_c':
    
        
  * If Q_c= Q_c', remove the qubits c acts on, and set their values to satisfy c and c'.
        
  * Else, Q_c⊂ Q_c'. Thus, c' is k'-local for 3≤ k'≤ k. Set the values of the qubits in Q_c so as to satisfy c. This collapses c' to a (k'-2)-local constraint on qubits Q_c'∖ Q_c.
            
                
  * If k'-2=1, then c' has been collapsed to a 1-local constraint on some vertex v∈ Q_c'∖ Q_c, creating a path rooted at v. Set v so as to satisfy c', and use a CR to solve the resulting path until either the path ends, or a k”-local constraint is hit for 3≤ k”≤ k'. In the latter case (Figure <ref>, Left), the k”-local constraint is reduced to a (k”-1)-local constraint and we return to the beginning of Step 3.
            
        
        
  * 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 <ref>, Middle).
            
                
  * 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 Π.
                
  * Else, set v_1 and v_2 so as to satisfy c. Solve the resulting paths h_1 (h_2) until a k'-local (k”-local) constraint l_1 (l_2) is hit for 3≤ k'≤ k (3≤ k”≤ k). If both l_1 and l_2 are found:
                
                    
  * If l_1=l_2 (i.e. k'=k”) and k'-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 <ref>, Right). Iteratively solve the resulting path until a k'-local constraint is hit for 3≤ k'≤ k.
                
            
    
    
  * If any qubits are unassigned, set their values to |0⟩.



An illustration of algorithm A on an example input is given after this proof (see also Figure <ref>). 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^⊥⟩ (up to phase). Thus, if there are conflicting 1-local clauses acting on v, we must reject; else, we must set v to |c^⊥⟩, and subsequently simplify all remaining clauses acting on v (i.e. map C_v to S_|v⟩). 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 Π 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 Π. Thus, in order to prove that Π is satisfiable, it suffices to show that the following loop invariant holds.


Loop Invariant: Before each execution of Step 3, either Π contains some 2-local clause and no 1-local clauses, or Π 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, Π contained no 1-local contraints, and since in Step 2 we only reduce k'-local clauses to k”-local ones for k”≥ 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' must be disjoint from all other clauses in Π. Informally, the joint satisfiability of c and c' is hence independent of the satisfiability of the rest of the instance. In the language of our loop invariant, the removal of c and c' does not create any 1-local constraints. Moreover, if subsequently Π is non-empty, then it is not the case that all remaining clauses are k'-local for 3≤ k'≤ k. This is because otherwise the set of clauses disjoint from c and c' must contain a variable involved only in clauses of size at least k'≥ 3, contradicting Step 2. Thus, the loop invariant holds. (Aside: If c and c' act on vertices u and v, a satisfying assignment to c and c' 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'-2)-local constraint on c'. Thus, if k'-2=1, this induces a CR on the incident path of 2-local constraints on c' (this path may have length 0). Note that this path can never loop back to c', 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⟩ to the next vertex in the path to induce a new CR), or eventually we hit a k”-local constraint for k”≥ 3, which we now collapse to a (k”-2)-local constraint; call the latter ϕ. Thus, since the CR removes any possible 1-local constraint on c' 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”-local clause for k”=3, on the other hand, the CR itself created a 2-local clause. Similarly, if k”≥ 4, then ϕ is at least 3-local, and we claim that at least one of the vertices of ϕ 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 Π. Thus, its removal does not create a 1-local constraint. That there must exist a 2-local constraint if Π 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'-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'-local for k'≥ 3. If k'-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'-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.





  
*An example and applicability. Having shown Theorem <ref>, we make two remarks.

    
  * (Demonstration) We illustrate in Figure <ref> 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).
    
  * (Applicability) Whereas the class of hypergraphs considered in Theorem <ref> may seem a priori rather restricted, as a “proof of concept” we observe that the example of Figure <ref> can be generalized to an entire family of non-trivial examples to which Theorem <ref> applies. (We focus on 3-uniform hypergraphs for simplicity.) Specifically, encode the hypergraph H(G) in the top left of Figure <ref> 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 <ref>. G is defined as follows. Each disc vertex s_i∈ V_d corresponds to a red hyperedge (color online; e.g. hyperedge v_7,v_8,v_9 is red). Each cross vertex t_i∈ 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 <ref> applies. Finally, we connect this example with the notion of transfer filtrations in Section <ref>. Namely, the hypergraph H(G) in Figure <ref> is of transfer type at most 12 — for all pairs of distinct hyperedges e_i,e_j with e_i∩ e_j=2, simply add e_i∩ e_j to the foundation.




 §.§ Connection to k-QSAT instances with a SDR


Recall that the initial motivation for this study was the open question <cit.> 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 <ref> 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) <cit.>, it follows that hypergraphs with hyperedges of size 1 in general cannot have SDRs. Indeed, consider the hypergraph with edge set E=1,2,3,1,2,3 — clearly, this has no SDR, and if we set the clauses to (respectively) project onto |000⟩, |1⟩, |1⟩, and |1⟩, then the corresponding 3-QSAT instance is unsatisfiable.

However, if our k-QSAT instance has no 1-local clauses in Theorem <ref>, 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 <ref> answers the open question of <cit.> for all k-QSAT instances in which (1) there are no 1-local clauses and (2) each qubit occurs in at most 2 clauses.

thm:matchgraph
    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.


    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.
    
        
  * While there exists a pair of distinct edges e_i,e_j∈ E such that e_i∩ e_j≥ 2:
            
                
  * Pick an arbitrary pair of distinct vertices v_i,v_j∈ e_i∩ 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.
            
        
  * While there exist vertices v of degree 1 in some hyperedge c_v, match v to c_v and remove v and c_v.

        
  * Remove any vertices of degree 0.

        
  * Let G' denote the remaining hypergraph. (We assume G' 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.
        
  * (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⊆ V(L)× 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.)
        
  * (Convert the “reverse” SDR on L to an SDR on G') For each (w,x)∈ M:
        
            
  * Suppose x=(u,w) for some u∈ V(L). Then, let e_u and e_w denote the hyperedges in G' corresponding to u and w, respectively. Match e_w to the unique element of e_u∩ e_w.
        
    

    

  
*Correctness. We analyze each step in sequence.
    
        
  * (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.
        
  * (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.

        
  * (Step 4) After Steps 1, 2, and 3, G' 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' to construct L: Each hyperedge of G' 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' intersect.

            Moreover, by properties (a) and (b) of G', 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' is connected).

        
  * (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 w,v and v,w', then by definition of a DFS at least one of them will be traversed in direction (w,v) or (w',v) (as opposed to both being traversed in directions (v,w) and (v,w'); 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)∈ 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[For 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.]).

        
  * (Step 6) This step converts each two-tuple in M to a matched hyperedge e_w and vertex in v∈ e_u∩ e_w. Note that e_u∩ e_w=1 by property (a) of G'. Since M is a “reverse” SDR, it follows that the matching produced by Step 6 completes the desired SDR.
    







§ 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 <ref>). 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 <ref>. The final algorithm and its runtime, along with the study of asymptotic speedups, are given in Section <ref>. For readers who wish to see the outline of the algorithm before reading the details, see Figure <ref> on Page 29.



 §.§ The transfer type of a hypergraph




  
Transfer filtrations. The core graph theoretic idea on which our framework will be built is the new notion of transfer type of a hypergraph, which we now introduce.


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⊆ G_1⊆⋯⊆ G_m=G and an ordering of the edges E(G)={E_1,…,E_m} such that


  * E(G_i)={E_1,…,E_i} for each i∈{0,…,m},

  * |V(G_i)|≤ |V(G_i-1)|+1 for each i∈{1,…,m},

  * if |V(G_i)|= |V(G_i-1)|+1, then V(G_i)∖ V(G_i-1) ⊆ E_i,

  * |V(G_0)|=b, where we call V(G_0) the foundation,

  * 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. Note that under certain conditions (i.e. when the foundation size is bounded by b≤ |V(G)|-|E(G)|+k-1), we later show (Theorem <ref>) that this iterative construction can be exploited to prove the hypergraph G must have an SDR. Also, recall that as stated in Section <ref>, we conjecture that given G as input, finding a foundation of minimum size is NP-hard. (In the context of our parameterized algorithms, this is reminiscent of common parameters such as treewidth being NP-hard to compute <cit.>.) Finally, condition 5 in Definition <ref> is a “minimality” condition. For example, the entire vertex set is also a valid foundation, but contains more vertices than required to satisfy conditions 1 through 4. To prevent such cases, for convenience in our discussions we have added Condition 5 to Definition <ref>, which holds without loss of generality. In particular, given a filtration satisfying 1-4 but not 5, it is easy to compute a modified filtration with a smaller foundation satisfying 1-5 (if edge e fails 5, simply remove a single arbitrary vertex v∈ e from G_0, and add an additional intermediate graph G_i to the filtration to first “pick up” vertex v). 


[Running example (Figure <ref>)]
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 <ref>, 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)=∅ and E(G_j)={E_1,…,E_j} for j=1,2,3. Then G_0⊆ G_1⊆ G_2⊆ G_3⊆ 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 <ref> and Definition <ref>, respectively.






Let G be a k-uniform hypergraph of transfer type b. Since G_1 has exactly one edge, then b≥ k-1.



The tight line graph <cit.> of a k-uniform hypergraph G is the (undirected) graph L(G) with vertices labelled by E(G) and edges {(E_i,E_j)| E_i,E_j∈ E(G) and E_i∩ E_j=k-1}. (This generalizes the notion of a line graph; a yet more general definition, called an edge intersection graph, is mentioned in Section <ref>, which adds an edge (E_i,E_j) so long as E_i∩ E_j≠∅.) 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 <cit.>, 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∩ E_i_2|=k-1. Let G_2 be the hypergraph with vertices E_i_1∪ 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.


[Running example]
Let G be the 3-uniform cycle of Example <ref>. Then L(G) is a cycle of length 4, in the usual graph-theoretical sense. In particular G is line graph connected.



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 <ref> 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.




Let a_1,…,a_k-1≥ 2 be integers. Consider the hypergraph G with vertices (ℤ/a_1ℤ)×⋯× (ℤ/a_k-1ℤ) and edges of the form

    {(i_1,…,i_k-1),(i_1+1,…, i_k-1),(i_1,i_2+1,…,i_k-1),…,(i_1,…,i_k-1+1)}

for each (i_1,…,i_k-1)∈ V(G). Let G_0 be the subhypergraph of G with vertices (ℤ/a_1ℤ)×⋯× (ℤ/a_k-2ℤ)×{0} and no edges. Let G_1 be the subhypergraph with vertices V(G_0)∪{(0,…,0,1)} and a single edge {(0,…,0),(1,0,…,0),…,(0,…,0,1)}. Let G_2 be the subhypergraph obtained from  G_1 by adding the vertex (0,…,0,1,1) and the edge

    {(0,…,0,1,0),(1,0,…,0,1,0),…,(0,…,0,2,0),(0,…,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⊆ G_1⊆⋯⊆ G_a_1⋯ a_k-2. Iterating this construction on can extend this chain to G_0⊆ G_1,…,⊆ G_2a_1⋯ 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⋯ 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}×(ℤ/a_2ℤ)×⋯× (ℤ/a_k-1ℤ) in which case an obvious adaptation of the construction above leads to a transfer filtration of type a_2⋯ a_k-2. In particular, this shows that in general a hypergraph G can be of transfer type b for different choices of b.



Let G be a hypergraph admitting a transfer filtration G_0⊆ G_1⊆⋯⊆ G_m=G of type b. Assume the edges of G are ordered in such a way that E(G_i)={E_1,…,E_i} for each i∈{1,…,m}. Since by construction each edge contains at least one vertex not in V(G_0), there exists a function r:{1,…,m}→{0,…,m-1} such that r(i)<i and |E_i∖ V(G_r(i))|=1 for all i∈{1,…,m}.


[Running example]
Let G be the 3-uniform cycle of Example <ref>. Then r:{1,2,3,4}→{0,1,2,3} can be chosen to be such that r(1)=r(2)=0, r(3)=1 and r(4)=1.




  
The Decoupling Lemma. 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' of transfer type b whose transfer filtration must add a vertex in each step (this follows directly from the relationship between V(G) and E(G) below). This has two effects worth noting: First, G' is guaranteed to have an SDR. Second, it decouples certain intersections in the hypergraph, as illustrated in Figure <ref>. 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)).




Given a k-uniform hypergraph G of transfer type b, there exists a k-uniform hypergraph G of transfer type b with |E(G)|+b vertices and a surjective function p:V(G̃)→ V(G) such p(E)∈ E(G) for every E∈ E(G).

 Let G_0⊆ G_1⊆⋯⊆ G_m=G be a transfer filtration such that |V(G_0)|=b and let r:{1,…,m}→{0,…,m-1} as in Remark <ref>. Suppose the vertices of G are labeled as {1,…,n} in such a way that V(G_0)={1,…,b}. Furthermore, we may assume that the edges {E_1,…,E_m} of G are labeled in such a way that E(G_i)={E_1,…,E_i} for each i∈{1,…,m}. Let V(G)={1,…,m+b} and define p:{1,…,m+b}→{1,…, n} so that p(i)=i for all i∈{1,…,b} and {p(i)}=E_i-b∖ V(G_r(i-b)) for all i∈{b+1,…,b+m} (where recall r is from Remark <ref>). By Remark <ref>, p is surjective. For each j∈{1,…,m+b}, let j=min(p^-1(p(j))). If we define E(G)={E_1,…,E_m} by setting E_i=i+b∪{j| j∈ p^-1(E_i∖ p(i+b))} for each i∈{1,…,m}, then G is clearly k-uniform. Let G_0 be the hypergraph with vertices {1,…,b} and no edges. For each i∈{1,…,m}, let G_i be the subgraph of G with vertices {1,…,i+b} and edges {E_1,…,E_i}. Then G_0⊆G_1⊆⋯⊆G_m=G is a transfer filtration and G is a hypergraph of transfer type b.




[Running example (Figure <ref>)]
Let G be the 3-uniform cycle of Example <ref>. The proof of Lemma <ref> (appendix) produces a 3-uniform hypergraph G with vertices {1,2,3,4,5,6} and edges E_1={1,2,3}, E_2={1,2,4}, E_3={1,3,5}, E_4={2,3,6}, and surjective function p:{1,2,3,4,5,6}→{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 E_4={2,4,6} and p(6)=3 also satisfies Lemma <ref>.



If k=2, then G (as defined in Lemma <ref>) 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 |G| is the geometric realization of a (possibly infinite) tree. Moreover, the geometric realization of p is the restriction of the canonical covering map |G|→ |G| to the closure of a fundamental domain for the canonical action of π_1(|G|) on |G|.




  
Radius of transfer filtration. 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.


Let G be a hypergraph admitting a transfer filtration G_0⊆⋯⊆ G_m=G of type b. Consider the function (whose existence is guaranteed by Remark <ref>) r:{0,…,m}→{0,…,m-1} such that r(0)=0 and r(i) is the smallest integer such that |E_i∖ V(G_r(i))|= 1 for all i∈{1,…,m}. The radius of the transfer filtration G_0⊆⋯⊆ G_m=G of type b is the smallest integer β such that r^β(i)=0 ∀ i∈{1,…,m} (r^β denotes the composition of r with itself β times). The type b radius of G is the minimum value ρ(G,b) of β over the set of all possible transfer filtrations of type b on G.


[Running example]
For G the 4-cycle from Example <ref>, since function r described in Example <ref> is non-constant and r(r(i))=0 for all i∈{1,2,3,4}, then the transfer filtration of Example <ref> has radius β=2.





 §.§ The main construction


To describe the main construction, we shall use rather general terminology to describe the most general setting in which the framework applies. For those versed in quantum information, we will attempt to note what special cases for the general definitions we give are most relevant to said community; these notes will be marked with terminology  (color online).



  
Definitions. To begin, let W be a two dimensional vector space over a field .  We may set =ℂ and identify W with ℂ^2 if desired. We now define k-local functions;  these capture the notion of a k-local Hamiltonian constraint evaluated against a tensor product of k input qubit states |v_i_1⟩⊗⋯⊗|v_i_k⟩.


A function H_i:W^n→ is k-local if there exists a subset E_i={i_1,…,i_k}⊆{1,…,n} and a non-zero functional H_i^*:W^⊗ k→ such that

    H_i(v_1,…,v_n)=H_i^*(v_i_1⊗⋯⊗ v_i_k)

for all v_1,…,v_n∈ W, i.e. H_i acts non-trivially only on a subset of k indices. A collection H=(H_1,…,H_m) of k-local functions H_1,…,H_n:W^n→ is k-local. The corresponding subsets {E_1,…,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,…,n} known as the interaction graph of H. The product satisfiability set of the k-local collection H is the set _H of all (v_1,…,v_n)∈ W^n such that v_i≠ 0 for all i∈{1,…,n} and H_j(v_1,…,v_n)=0 for all j∈{1,…,m}.



Consider an isomorphism  ♯ between W and its dual W^∨ that to each v∈ W assigns a functional v^♯∈ W^∨ such that v^♯(v)=0. For instance, if a basis {w_1,w_2} for W is chosen then we may define ♯ by setting ((a_1w_1+a_2w_2)^♯)(b_1w_1+b_2w_2)=a_1b_2-a_2b_1 for all a_1,a_2,b_1,b_2∈. Moreover, given any v_1,v_2∈ W, then v_1^♯ (v_2)=0 if and only if there exists λ∈ such that λ v_2 = v_1.  The ♯ isomorphism essentially maps a vector |ψ⟩∈^2 to its unique (up to scaling) orthogonal state |ψ^⊥⟩∈^2.



 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)+…+F_r-N^(N) for all r≥ N, F_N-1^(N)=1 and F_r^(N)=0 for all r≤ N-2.



It is shown in <cit.> that there exists a monotonically increasing sequence (ψ_N) with values in the real interval [1,2) such that, for each N≥ 1, F_r^(N)∼ψ_N^r as r→ +∞.



A function f on W^l with values in a -vector space has degree (d_1,…,d_l) if f(λ_1v_1,…,λ_l v_l)=λ_1^d_1⋯λ_l^d_lf(v_1,…,v_l) for every λ_1,…,λ_l∈ and every v_1,…,v_l∈ W.




  
The Transfer Lemma. Applying the Decoupling Lemma to an input k-uniform hypergraph G with transfer type b, we obtain a k-uniform hypergraph G of type b with m=n-b, for m and n the number of edges and vertices, respectively. The next lemma shows that 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 <ref>), 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× 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).


Let H=(H_1,…,H_n-b) be a k-local collection of functions H_i:W^n → 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,…,g_n: W^b→ W with the following properties.


  * (Global to local assignments) If (v_1,…,v_n)∈_H (recall the v_i are non-zero by definition of _H) there exist non-zero λ_1,…,λ_n∈ such that, for every i∈{1,…,n},

    λ_iv_i=g_i(v_1,…, v_b).


  * (Local to global assignments) For any non-zero v_1,…,v_b∈ W there exist v_b+1,…,v_n∈ W such that (v_1,…,v_n)∈_H and v_i=g_i(v_1,…,v_b) for every i such that g_i(v_1,…,v_b)≠ 0.

  * (Degree bounds) g_i has degree (d_i1,…,d_ib) such that d_ij≤ F_i^(b) for all j∈{1,…,b}.

 Intuitively, a transfer function g_i takes in a tensor product assignment to the b foundation qubits, and gives a closed formula for an assignment to qubit i.


For i=1,…,b, define g_i(v_1, …, 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⊆ G_1⊆⋯⊆ G_n-b=G_H such that each G_i is of transfer of type b and V(G_i)∖ V(G_i-1)={i+b} for all i∈{1,…,n-b}. Therefore, we may work by induction on n (for each fixed b) and assume that g_b+1,…, g_n-1 have been constructed. Suppose that E_n-b={n,i_1,…,i_k-1} (where we shall assume vertex n is added in step n-b of the filtration) and consider the function g_n^♯:W^b→ W^∨ such that

    (g_n^♯(v_1,…, v_b))(v) = H^*_n-b(g_i_1(v_1,…,v_b)⊗⋯⊗ g_i_k-1(v_1, …, v_b)⊗ v)

for all v_1,…,v_b,v∈ W.  Intuitively, g_n^♯ evaluates the local Hamiltonian term (i.e. estimates its energy penalty) corresponding to H^*_n-b on the tensor product assignment prescribed by transfer 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,…,v_n)∈_H implies that g_1,…,g_n-1 as (<ref>) exist and g_n^♯(v_1,…,v_b)(v_n)=0. Given an isomorphism ♯ between W and W^∨ as in Remark <ref>, we define a function g_n:W^b→ W by setting (g_n(v_1,…,v_b))^♯=g_n^♯(v_1,…,v_b) for all v_1,…,v_b∈ W. Then (v_1,…,v_n) is in _H implies (<ref>) holds for every i∈{1,…,n}. This proves (1).

To prove (2), suppose v_b+1,…,v_n-1 have been constructed. Let v be such that H^*_n-b(v_i_1⊗⋯⊗ v_i_k-1⊗ v)=0 (such a v exists, for example, since recall each QSAT constraint is rank 1 in our definition). Then (v_1,…,v_n-1, λ v)∈_H for any λ∈. Moreover, if g_n(v_1,…,v_b)≠ 0 then by Remark <ref> it has to equal μ v for some non-zero μ∈. Setting v_n =μ v, proves (2).

To prove (3), we observe that the degree of g_n equals the degree of g_n^♯. Using induction and (<ref>) it is easy to see that the latter satisfies the claimed bounds.


[Running example]
Let H=(H_1,H_2,H_3,H_4) be a 3-local collection of functions H_i:W^6→𝕂 whose interaction graph is the 3-uniform chain G described in Example <ref> (obtained by plugging the 4-cycle G of Example <ref> into the Decoupling Lemma). For clarity, H_i is defined on hyperedge E_i, where the order of vertices in each edge is fixed by the transfer filtration chosen; in particular, we use the natural ordering E_1=(1,2,3), E_2=(1,2,4), E_3=(1,3,5), E_4=(2,4,6), so that the foundation is 1,2. Then the proof of Lemma <ref> constructs transfer functions g_1,…,g_6:W^2→ W which give assignments to qubits 1 through 6, respectively, as follows. Fixing a basis {w_1,w_2} of W and unraveling (<ref>) we obtain

    g_1(v_1,v_2)   =v_1 ;
    
    g_2(v_1,v_2)   =v_2 ;
    
    g_3(v_1,v_2)   = H_1^*(v_1⊗ v_2⊗ w_2)w_1-H_1^*(v_1⊗ v_2⊗ w_1)w_2 ;
    
    g_4(v_1,v_2)   = H_2^*(v_1⊗ v_2⊗ w_2)w_1-H_2^*(v_1⊗ v_2⊗ w_1)w_2 ;
    
    g_5(v_1,v_2)   = H_3^*(v_1⊗ g_3(v_1,v_2)⊗ w_2)w_1-H_3^*(v_1⊗ g_3(v_1,v_2)⊗ w_1)w_2 ;
    
    g_6(v_1,v_2)   = H_4^*(v_2⊗ g_4(v_1,v_2)⊗ w_2)w_1-H_4^*(v_2⊗ g_4(v_1,v_2)⊗ w_1)w_2 .

In particular the matrix of degrees d_ij is

    (
      [ 1 0 1 1 2 1; 0 1 1 1 1 2 ])^T

so that, in accordance to the bound given in Lemma <ref>, the i-th entry of each column is less or equal than the i-th (ordinary) Fibonacci number F_i^(2).




  
The Qualifier Lemma. Thus far, we have seen how combining the Decoupling and Transfer Lemmas “blows up” an input k-QSAT system Π to a larger “decoupled” system Π^+ which is easier to solve due to its decoupled property. Now we wish to relate the solutions of Π^+ back to Π. This is accomplished by the next lemma, which introduces a set of “qualifier” constraints h_s with the key property (follows from Lemma <ref> and Remark <ref>): Any solution to h_s can be extended to one for Π^+, and then mapped back to a solution for Π. Importantly, the qualifier constraints act only on the b foundation vertices, as opposed to all n vertices!





Let H=(H_1,…,H_m) be a k-local collection of functions H_i:W^n→ 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,…, h_m-n+b:W^b→ and π:W^n→ W^b such that


  * h_s(π(_H))=0 for all s∈{1,…,m-n+b};

  * h_s has degree (d_s1,…,d_sb) with d_sr≤ 2 F^(b)_ρ(G,b)+b+1 for all s∈{1,…,m+b} and all r∈{1,…,b}.

 Condition (1) essentially says that any satisfying product state to the k-QSAT instance H will, after application of an appropriate map π from n qubits down to the b foundation qubits, yield a common root to all qualifier functions h_s.



We begin by applying the Decoupling Lemma (Lemma <ref>) to G_H. This yields the larger hypergraph G_H and surjection p:V(G_H)→ V(G_H), constructed via a transfer filtration G_0⊆⋯⊆ G_m=G of type b. Note that G_H is the interaction graph of a k-local collection H=(H_1,…,H_m) of functions H_i:W^m+b→ such that H^*_i=H^*_i for each i∈{1,…,m}. Let Δ:W^n→ W^m+b be such that Δ(v_1,…,v_n)=(v_1,…,v_m+b), where v_i = v_p(i) for all i∈{1,…,m+b}. In other words, Δ “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 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, … ,v_n)∈_H if and only if Δ(v_1,…,v_n)∈_H.

Having applied the Decoupling Lemma and obtained a hypergraph G_H satisfying m=n-b, we now apply the Transfer Lemma (Lemma <ref>) to G_H. This yields that there exist g_1,…,g_m+b:W^b→ W with the property that Δ(v_1,…,v_n)∈_H implies that g_i(v_1,…,v_b) is a multiple of v_p(i) for all i∈{1,…,m+b}. Borrowing notation from the proof of Lemma <ref>, let {i_1,…,i_m-n+b} be the subset of all  i∈{1,…,m+b}  such that i < i (intuitively, these indices correspond to vertices of G_H obtained by decoupling a vertex of G_H). For each s∈{1,…, m-n+b}, define qualifier h_s:W^b→ be such that

    h_s(v_1,…,v_b)=(g_i_s^♯(v_1,…,v_b))(g_i_s(v_1,…,v_b))

for all v_1,…,v_b∈ W. If (v_1,…,v_n)∈_H, then for every s∈{1,…,m-n+b} there exists λ_i_s, λ_i_s∈ such that λ_i_s v_p(i_s) = g_i_s(v_1,…,v_b) and λ_i_s v_p(i_s)=g_i_s(v_1,…,v_b). Therefore, 
    h_s(v_1,…,v_b)=λ_i_sλ_i_sv_p(i_s)^♯(v_p(i_s))=0

for every s∈{1,…,m-n+b}. Therefore, (1) holds if we define π to be the composition of Δ with the projection onto the first b entries. It follows from Lemma <ref> and (<ref>) that h_s has degree (d_s1,…,d_sb) with d_sr≤ 2F_i_s^(b) for every s∈{1,…,m-n+b} and r∈{1,…,b}. Finally (2) follows from Lemma <ref>, by choosing the transfer filtration G_0⊆⋯⊆ G_m=G of type b to have radius ρ(G,b).


In the notation of the proof of Lemma <ref>, suppose v_1,…,v_b is an assignment to the foundation which satisfies the qualifiers, i.e.  h_s(v_1,…,v_b)=0 for all s∈{1,…,m-n+b}, and that g_i_s(v_1,…,v_b)≠ 0 for all s∈{1,…,m-n+b}. Then by Remark <ref> we have that for each s∈{1,…,m-n+b} there exist μ_s∈𝕂 such that

    μ_s g_i_s(v_1,…,v_b)=g_i_s(v_1,…,v_b) .

In other words, in a solution to the decoupled instance on G_H, it must be the case that all decoupled copies of a vertex v receive the same assignment (up to scalars). Indeed, g_i_s(v_1,…,v_b)≠ 0, and hence by Lemma <ref> there exist v_b+1,…,v_n such that (v_1,…,v_n)∈_H, i.e. a satisfying assignment for H must exist. Thus, to solve the original k-QSAT instance Π, it suffices to: (1) apply the Decoupling Lemma to blow up the instance to a decoupled instance Π^+, (2) apply the transfer functions from the Transfer Lemma to v_1,…,v_b to obtain a solution on all m+b vertices for Π^+, and (3) (easily) map this solution back to one on n vertices for Π.


[Running example]
Let H=(H_1,H_2,H_3,H_4) be a 3-local collection of functions H_i:W^4→𝕂 whose interaction graph is the 3-uniform cycle of transfer type 2 introduced in Example <ref>. If p is chosen as in Example <ref>, then the two qualifier functions are

    h_1(v_1,v_2)=(g_5^♯(v_1,v_2))(g_4(v_1,v_2))

of degree (3,2) and

    h_2(v_1,v_2)=(g_6^♯(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≤ 3≤ 10 =2 F_5^(2) for each s,r∈{1,2}, in accordance to Lemma <ref>. Choosing a basis {w_1,w_2} of W as in Example <ref>, we obtain via Condition 1 of Lemma <ref> that (v_1,v_2,v_3,v_4)∈𝒮_H implies

    0=H_1^*(v_1⊗ v_2⊗ w_1)H_2^*(v_1⊗ v_2⊗ w_1) H_3^*(v_1⊗ w_2⊗ w_2)
    
    + H_1^*(v_1⊗ v_2⊗ w_2)H_2^*(v_1⊗ v_2⊗ w_2) H_3^*(v_1⊗ w_1⊗ w_1)
    
    -H_1^*(v_1⊗ v_2⊗ w_1)H_2^*(v_1⊗ v_2⊗ w_2) H_3^*(v_1⊗ w_2⊗ w_1)
    
    -H_1^*(v_1⊗ v_2⊗ w_2)H_2^*(v_1⊗ v_2⊗ w_1) H_3^*(v_1⊗ w_1⊗ w_2)

and

    0=H_1^*(v_1⊗ v_2⊗ w_1)H_2^*(v_1⊗ v_2⊗ w_1) H_4^*(v_2⊗ w_2⊗ w_2)
    
    + H_1^*(v_1⊗ v_2⊗ w_2)H_2^*(v_1⊗ v_2⊗ w_2) H_4^*(v_2⊗ w_1⊗ w_1)
    
    -H_1^*(v_1⊗ v_2⊗ w_1)H_2^*(v_1⊗ v_2⊗ w_2) H_4^*(v_2⊗ w_2⊗ w_1)
    
    -H_1^*(v_1⊗ v_2⊗ w_2)H_2^*(v_1⊗ v_2⊗ w_1) H_4^*(v_2⊗ w_1⊗ w_2) .





 §.§ Generic constraints


Remark <ref> outlined the high-level strategy for computing a (product-state) solution to an input k-QSAT system Π. 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.


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 _G()=(ℙ^2^k-1())^m. (We remark the same variety was used in <cit.>.) 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 _G(). In the important case 𝕂=ℂ, this implies in particular that such a property holds for almost all choices of constraints (with respect to the natural measure on _G() induced by the Fubini-Study metric). Note that we allow different (generic) constraints on each edge (i.e. the Hamiltonian is not necessarily translation-invariant).  To give some intuition, a generic 2-qubit constraint |ψ⟩∈^2⊗^2 would be any entangled |ψ⟩ (since the set of two-qubit states with a Schmidt coefficient of zero forms a zero measure set). In the case of 2-QSAT, the upshot of this is that if |ψ⟩ is a constraint on qubits i and j, then given any assignment |ϕ_1⟩ to qubit i, the transfer matrix T_ij corresponding to |ψ⟩ is full-rank, meaning T_ij|ϕ_1⟩≠ 0 (and additionally, by definition of a transfer matrix, ⟨ψ|(I⊗ T_ij)|ϕ⟩_i⊗|ϕ⟩_j=0). In other words, an assignment on qubit i is guaranteed to propagate to a valid assignment on qubit j. Note that classical k-SAT constraints are not generic, as they represent a finite set in the variety of all constraints (and in particular, correspond to rank-1 projections onto product states). Nevertheless, as we prove in Theorem <ref>, the hypergraphs to which our main theorem applies (Theorem <ref>) have an SDR; and a satisfying assignment to any classical k-SAT instance with an SDR is easy to compute (as mentioned in Section <ref>).



Let G_0⊆ G_1⊆⋯⊆ G be a transfer filtration on a k-uniform hypergraph G whose vertices {1,…,n} are ordered in such a way that if i∈ V(G_j)∖ V(G_j-1), then i-1∈ V(G_j-1). Given i,i'∈{1,…,n} we say that i' is a successor of i (and i is a predecessor of i') if there exists sequences i_1,…,i_l∈ V(G) and E_1,…,E_l+1∈ E(G) such that i≤ i_1≤⋯≤ i_l≤ i', i∈ E_1, i'∈ E_l+1 and  i_j∈ E_j∩ E_j+1 for all j∈{1,…,l}.



Let G be as in Example <ref>. Then 3 is a predecessor of 4 and a successor of both 1 and 2.


Before showing the main theorem of this section (Theorem <ref>), 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.  This is roughly a generalization of the idea from 2-QSAT that when all constraints all entangled, then all transfer matrices are full rank (and hence are surjective maps).


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 _G(), let g_1,…,g_n:W^b→ W be transfer functions as in the Transfer Lemma (Lemma <ref>) and choose non-zero v_1,…,v_b-1∈ W. For each i, define γ_i:W→ W such that

    γ_i(w):=g_i(v_1,…,v_b-1,w)

for all w∈ W. If i is a successor of b, then γ_i is surjective.

 Up to a permutation of {1,…,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 <ref>). Therefore, a generic choice of H_1,…,H_n-1-b leads to surjective maps γ_i for every successor of b. If the edge that contains vertex n is {i_1,…,i_k-1,n}, then at least one other vertex, say i_1, is also a successor of b. Since γ_i_1 is surjective by the induction hypothesis, we can choose w',w”∈ W such that γ_i_1(w') and γ_i_1(w”) are linearly independent. Suppose that γ_n is not surjective. Since it has definite (i.e. well-defined) degree, this implies γ_n(w') and γ_n(w”) are not linearly independent. By (<ref>) 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 γ_n is surjective.


For each i,j, consider the function Γ_ij:W→ defined by setting

    Γ_ij(w):=(γ_i(w))^♯(γ_j(w))

for all x∈𝕂. It is easy to see by induction that if w',w”∈ W are linearly independent, then P_ij(x)=Γ_ij(w'+xw”) is a univariate polynomial in x with coefficients in 𝕂. 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.




  
The main theorem. 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 <ref> (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 π (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.


Let  be algebraically closed, and let 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∈F and h_1 and π are as in the Qualifier Lemma (Lemma <ref>), then (h_1∘π)^-1(0)∩_H is nonempty.


Let G and g_1,…,g_n+1 as in the proof of the Qualifier Lemma (Lemma <ref>). Since  is algebraically closed, by the discussion in Remark <ref>, there exist v̂_1,…, v̂_b∈ W such that h_1(v̂_1,…,v̂_b)=0. As shown in the previous section, if additionally g_i_1(v̂_1,…,v̂_b)≠ 0, then π^-1(v̂_1,…,v̂_b)∩_H≠∅, as desired. Thus, we are left to show that the same conclusion holds even if g_i_1(v̂_1,…,v̂_b)=0 (which immediately implies h_1(v̂_1,…,v̂_b)=0).

Let j∈{b+1,…,n+1} be minimal among those predecessors of i_1 such that g_j(v̂_1,…,v̂_b)=0. For a sufficiently generic choice of constraint we may assume that g_l(v̂_1,…,v̂_b)≠ 0 for any l that is not a successor of j. Our strategy is now to remove the edge in G which was added in the same step of the filtration in which vertex j was added, namely edge E_j-b. We then instead add vertex j directly to the foundation. Formally, consider hypergraph F obtained from G by removing edge E_j-b, and consider transfer filtration F_0⊆ F_1⊆⋯⊆ F_m-1=F where: 
    
  * (Add j to the foundation) V(F_i)=V(G_i)∪{j} for all i∈0,…, j-b-1 and V(F_i)=V(G_i+1) for all i∈j-b,…, m-1,
    
  * (Remove edge E_j-b) E(F_i)=E(G_i) for all i∈0,…,j-b-1 and E(F_i)=E(G_i+1)∖{E_j-b} for all i∈j-b,…, m-1.

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 <ref>) and the Surjectivity Lemma (Lemma <ref>) to obtain transfer functions f_1,…,f_n_F:W^b_F↦ W and γ_1,F,…,γ_n_F,F:W↦ W (based on f_i instead of g_i). Two comments are in order here: First, each γ_i,F depends on v̂_1,…, 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∈0,…,j-b-1, we have by construction that for all w∈ W, f_i(v̂_1,…, v̂_b, w)=g_i(v̂_1,…,v̂_b) — this is because each corresponding G_i (i.e. the first j-b “steps” of the original transfer filtration) does not depend on vertex j.

Now recall from Remark <ref> the polynomial

    P_i_1i_1(x):=Γ_i_1,i_1(w'+xw”)=(γ_i_1,F(w'+xw”))^♯(γ_i_1,F(w'+xw”))∈[x].

Since  is algebraically closed, P_i_1i_1(x) has a root x̂ in . Thus, by Remark <ref>, there exists λ∈ such that γ_i_1,F(w'+x̂w”)=λγ_i_1,F(w'+x̂w”) (i.e. both decoupled vertices i_1 and i_1 can be given the same assignment). Therefore, if we set v_i=γ_i,F(w'+x̂w”) for all i∈{1,…,n} (note we may assume by Remark <ref> that each v_i≠ 0), then (1) vertices i_1 and i_1 receive consistent assignments, (2) edge E_j-b is satisfied by the second remark above that f_i(v̂_1,…, v̂_b, w)=g_i(v̂_1,…,v̂_b) for i∈0,…,j-b-1 (here we also use the fact that by Equation (<ref>), edge E_j-b was satisfied by foundation assignment (v̂_1,…, v̂_b) regardless of the assignment to vertex i_1), and (3) (v_1,…,v_n) satisfies all constraints in hypergraph F. It follows that (v_1,…,v_n)∈π^-1(v̂_̂1̂,…,v̂_̂b̂)∩_H, as required.



The maps γ_i(w) from the Surjectivity Lemma (Lemma <ref>) can without loss of generality be taken to have no zeroes, i.e. ∄ w∈ W such that γ_i(w)=0. To see this, consider γ_i(w'+xw”):W↦ W for x∈ as in Remark <ref>. Since w' and w” are linearly independent, we can write γ_i(w'+xw”)=p(x)w'+q(x)w” for polynomials p,q∈[x]. In order for the right hand size to vanish on x_0, since  is algebraically closed, p and q must share a common factor (x-x_0). Factoring out (x-x_0), we obtain new polynomials p' and q', and redefine γ'_i(w'+xw”)=p'(x)w'+q'(x)w”. (Note we are implicitly working in projective space, since solutions to the Quantum SAT instance remain solutions under (non-zero) scaling.)



[Running example] We illustrate the proof of Theorem <ref> by specializing the construction to the 3-uniform semicycle G_3 from Example <ref>. Then G_3 is the hypergraph with vertices {1,2,3,4,5} and edges E_1={1,2,3}, E_2={1,2,4}, E_3={1,3,5}. Moreover, the transfer functions g_1,…,g_5:W^2→ W can be chosen as in Example <ref>. Let h_1 be as in Example <ref> and suppose v_1,v_2∈ 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 <ref>. 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 E_2, E_3. Furthermore, F has a transfer filtration F_0⊆ F_1⊆ 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 E_2. Unraveling (<ref>) we obtain

    γ_1,F(w)   =v_1 ;
    γ_2,F(w)   =v_2 ;
    γ_3,F(w)   =w ;
    γ_4,F(w)   =H_2^*(v_1⊗ v_2⊗ w”)w'-H_2^*(v_1⊗ v_2⊗ w')w” ;
    γ_5,F(w)   =H_3^*(v_1⊗ w⊗ w”)w'-H_3^*(v_1⊗ w⊗ w')w”

and thus

    Γ_54(w)=H_3^*(v_1⊗ w ⊗ w')H_2^*(v_1⊗ v_2⊗ w”)-H_3^*(v_1⊗ w⊗ w”)H_2^*(v_1⊗ v_2⊗ w')

for all w∈ W. Hence P_54(x)=P_54^0+P_54^1x where

    P_54^0=H_3^*(v_1⊗ w' ⊗ w')H_2^*(v_1⊗ v_2⊗ w”)-H_3^*(v_1⊗ w'⊗ w”)H_2^*(v_1⊗ v_2⊗ w')

and

    P_54^1=H_3^*(v_1⊗ w”⊗ w')H_2^*(v_1⊗ v_2⊗ w”)-H_3^*(v_1⊗ w”⊗ w”)H_2^*(v_1⊗ v_2⊗ w') .

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_ii(x) may have arbitrarily high degree and assuming that 𝕂 is algebraically closed becomes necessary.





Theorem <ref> reduces us to solving a single polynomial equation,

    h_1(v_1,…,v_b)=0,

which is multi-variate. In this case, we reduce it further to a univariate polynomial by fixing arbitrary vectors w_1,…,w_b∈ W and w'_b∈ W linearly independent from w_b. Then

    P(x)=h_1(w_1,…,w_b+xw'_b)

is a univariate polynomial in 𝕂[x], which has a root x∈ since  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 <ref>, we finally tie Theorem <ref> back to SDRs, and give an AG overview of our approach.

 Theorem <ref> gives a constructive proof that all hypergraphs in F have a satisfying (product state) assignment if the constraints are chosen generically. This implies each hypergraph in F has an SDR, as we now observe.
     
        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.
    
    
        By Theorem <ref>, _H is nonempty for generic H∈_G(ℂ). Theorem 2 of <cit.> then implies that G has an SDR.
    
     Thus, Theorem <ref> constructively recovers the result of <cit.> (that any k-QSAT instance with an SDR has a (product-state) solution) in the case when the additional conditions of Theorem <ref> are met (recall <cit.> works on all graphs with an SDR, but is not constructive). Finally, in Theorem <ref>, we show a generalization of Corollary <ref> above with a self-contained proof based on Hall's marriage theorem.



 As stated at the outset of Section <ref>, 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,…,v_n)→ v_1⊗⋯⊗ 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 _H can be naturally thought of as an algebraic set in (ℙ^1(𝕂))^n. In the language of algebraic geometry, the Transfer Lemma (Lemma <ref>) says that if the interaction graph is k-uniform of transfer type b=|V(G)|-|E(G)|, then _H can be realized as an iterated blow-up of (ℙ^1(𝕂))^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 <ref>) says that the projection of _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 _H coincides with X_H. However, Theorem <ref> says that in the non-trivial case when X_H is a hypersurface, then the projection of _H does indeed coincide with X_H.






 §.§ Explicit algorithm statement, runtime, and speedups

Figure <ref> 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.





  
Runtime analysis. We bound the complexity of each step of Figure <ref>. 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 𝕂=, 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  (as opposed to bit operations).


    
  * (Decoupling Lemma, Line 5) Let (E_1,…, E_m) denote the order in which edges of G are added in the filtration F. In order to compute G and p, the first step is to compute r:1,…, m↦0,…,m-1 from Remark <ref>. Recall this was defined such that r(i) is the smallest integer satisfying E_i∖ V(G_r(i))=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∈ 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)∈ O(m^2) total time.

        Moving on to p, since p(i)=i when i∈[b] and p(i)=E_i-b∖ V(G_r(i-b)) when i∈b+1,…, b+m, 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 j and  E_i take O(m) time. Therefore, computing all edges 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))∈ 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↦ W, it is helpful to use the construction of Example <ref> 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,…,v_b)⊗⋯⊗ g_i_k-1(v_1,…,v_b)⊗ w_l)=: H^*(u)

        (for w_l some fixed basis vector for W) as a multivariate polynomial in the 2b components of v_1,…, v_b. For convenience, let u=g_i_1(v_1,…,v_b)⊗⋯⊗ g_i_k-1(v_1,…,v_b)⊗ w_l above, and set S=i_1,…, i_k-1.  Observe now that if g_i_t has degree (d_i_t,1,…, d_i_t,b), then since g_i_t is a multivariate polynomial, it has at most O(d_i_t,1d_i_t,2⋯ d_i_t,b) distinct monomials. It follows that computing an arbitrary entry of u costs O(Π_i∈ SΠ_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^*(u)=u^† Hu. Thus, assuming k∈ O(1), computing H^*(u) costs
        
    O(Π_i∈ S Π_j=1^b  d^2_i,j)

        time in the worst case. By the degree bounds of Lemma <ref> and Remark <ref>, we have d_i,j≤ F^(b)_i∈ o(2^i). Equation (<ref>) can hence be bounded by
        
    O(Π_i∈ S  d^2b_i,j)∈ O(2^2b∑_i∈ Si)∈ O(2^2bkmax_i∈ Si),

        where the last statement follows since S≤ k. A naive analysis would now suggest max_i∈ S≤ 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,…, v_b) depends recursively on all previous transfer functions g_1…, g_i_1-1 (hence the degree of g_i_1-1≤ F^b_i for i∈[n]). By taking the radius of the filtration into account, ρ(G,b), we can obtain a much smaller bound when the radius is small. Specifically, similar to the analysis of Lemma <ref>, one can instead show d_i,j≤ F^(b)_ρ(G,b)+b+1∈ O(2^ρ(G,b)+b). Thus, we can improve Equation (<ref>) to
        
    O(2^2kb(ρ(G,b)+b)).

        Since there are n transfer functions in total, the cost of Line 6 is hence O(n2^2kb(ρ(G,b)+b)), where recall we assume k∈ O(1).

        
  * (Qualifier Lemma, Line 7) We consider the cost of computing an arbitrary qualifier h_s. Since in Line 5 we already computed i for all i∈1,…, m+b, we may compile set i_1,…, i_m-n+b 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⋯ d_i_s,b)∈ O(2^b(ρ(G,b)+b)) time. It follows that computing h_s requires O(2^2b(ρ(G,b)+b)) time. Since there are m-n+b qualifier functions, the total cost of this step is
            
    O((m-n+b)2^2b(ρ(G,b)+b)).


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

    O((m-n+b)2^2kb(ρ(G,b)+b)).

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 <ref>. As noted in Remark <ref>, in this case we may reduce Lines 8 - 9 to solving for the roots of a single univariate polynomial (moreover, the Surjectivity Lemma <ref> 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,…, v_b), which is a multivariate polynomial in 2b complex variables, and has degree (d_s1,…,d_sb) for d_sr≤ 2^ρ(G,b)+b+2 (by Lemma <ref>) for all r∈[b]. Following Remark <ref>, fix w_1=⋯ =w_b=|0⟩∈^2 and w'_b=|1⟩∈^2 and consider variable x∈. Then, q(x):=h_s(w_1,…, w_b-1,w_b+x w'_b) is a univariate non-constant[Note 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∈1,…, b such that redefining q(x) to have its jth argument to equal w_j+xw_j', and all other arguments j'≠ j equal to |ψ⟩ for some appropriate constant vector |ψ⟩, yields a non-constant polynomial over x. (For example, set the entries of |ψ⟩ 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, |ψ⟩ need not be normalized.)] polynomial over x with degree at most
        
    d≤ 2^ρ(G,b)+b+2.

        Observe that h_s has at most M=Π_sd_sr≤ 2^b(ρ(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 0,1,x (i.e. simplifying monomials with large exponents is trivial). To find a root of q, which exists since  is algebraically closed, we can now apply an algorithm of Schönhage <cit.> as follows.

        Schönhage's univariate polynomial factorization algorithm. Let us write q(x)=∑_i=1^d c_i x^i∈[x], and define one-norm q_1:=∑_i=1c_i. Then, Equation (3.2) of <cit.> says “approximate factorization” of q is possible within error[For clarity, Equation (3.2) of <cit.> assumes q_1≤ 1, and hence the error is stated therein as ϵ=2^-N. In our setting, however, we first need to rescale our q to ensure q_1≤ 1. This does not affect the number of field operations required for Schönhage's algorithm, but results in the multiplicative q_1 term (which is absent in <cit.>) in the resulting bound on accuracy, Equation (<ref>) . We hence define the error as ϵ=2^-Nq_1 here for convenience.] ϵ=2^-Nq_1 in O(d^3log d + d^2N) field operations. Here, “approximate factorization” within error ϵ means computing linear factors L_j(x)=u_jx+v_j for 1≤ j ≤ d such that
        
    q(x)-L_1(x)⋯ L_d(x)_1< 2^-Nq_1.

        Let w_j=-v_j/u_j≤ 1 denote the root of linear factor L_j(x). Given Equation (<ref>), 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 <cit.>, one can apply the perturbation bound of Theorem 2.7 of <cit.> to obtain the following. If q(x)-L_1(x)⋯ L_d(x)_1≤ηq(x)_1 for η≤ 2^-7d, then there exists an ordering of the w_j such that for all j,
        
    w_j-z_j< 9η^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 ϵ=q_1/(9^d2^p(n)d), which can be accomplished in time
        
    O(d^3log d + d^2 log(9^d2^p(n)d)).

         

         
  * (Line 9) We now have a root (v_1:=|0⟩,…, v_b-1:=|0⟩,v_b:=|0⟩+x|1⟩) of h_s. To compute g_i(v_1,…, v_b) for any i∈[n] involves evaluating a multivariate polynomial of degree (d_s1,…,d_sb) for d_sr≤ 2^ρ(G,b)+b+2 for all r∈[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((ρ(G,b)+b)2^b(ρ(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≤ 2^ρ(G,b)+b+2)

    O(mn)+ O(2^2kb(ρ(G,b)+b))+O(d^3log d + d^2 log(9^d2^p(n)d))+O((ρ(G,b)+b)2^b(ρ(G,b)+b+2)).

Thus, the algorithm is polynomial in m and n, and exponential in k (the locality of the constraints), ρ(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≤ 2^ρ(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 <ref>.
Recall Theorem <ref> 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∈ 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 (<ref>), 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.

[Semicycles (Figure <ref>, page 9)]
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)=ℤ/tℤ and edges E(S_t,k)={E_0,…,E_t-k+1} such that E_i={i,i+1,…,i+k-1} for every i∈{0,…,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 <ref>. 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∈Θ (|E(S_t,k)|), i.e. no separation in parameters exists.




[Modified tiling of the torus (Figure <ref>, page 34)] 
We next discuss a slight modification of the tiling of torus which yields a quadratic separation in parameters. Let k≥ 3 and let t be a positive integer. Let V_t,k be the set of pairs (p,q) of integers such that 0≤ (k-2) q ≤ p ≤ (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),…,(r+k-2,s),(r+k-2,s+1)} for each pair (r,s)∈ V_t-1,k. Then G_t,k has (t+1)(2+t(k-2))/2 vertices and 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),…,(t(k-2),0)} obtained by adding the edges in the following order

    E_0,0, E_1,0,…,E_(t-1)(k-2),0,E_k-2,1,E_k-1,1,…,E_(t-1)(k-2),1,E_2(k-2),2,…,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 <ref>, except one keeps only the “lower triangular” portion of Figure <ref>, i.e. vertices v_2,v_3,v_4,v_5,v_7 from Figure <ref> are discarded. Unlike the tiling of the torus, however, the example here has a transfer filtration type which satisfies the preconditions of Theorem <ref>, as stated below.) Then T_t,k has a transfer filtration of type

    t(k-2)    = (t+1)(2+t(k-2))/2 -2 + t(2+(t-1)(k-2))/2 +1  
        = |V(T_t,k)|-|E(T_t,k)|+1,

satisfying the preconditions for Theorem <ref>. Since T_t,k has radius t, it follows that the radius and foundation size are Θ(t) (for k∈ O(1), which is the typical assumption), whereas V(T_t,k),E(T_t,k)∈Θ(t^2), i.e. there is a quadratic gap between these parameters.


[Fir Tree (Figure <ref>, page 27)]
We next give another example of a hypergraph family (Figure <ref>) with a quadratic separation in parameters. For each k≥ 3, t≥ 1 and i∈ℤ/kℤ let G_t,k,i be a copy of the k-uniform hypergraph G_t,k introduced in Example <ref>. Let H_t,k' 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∈ℤ/kℤ and let H_t,k be the graph obtained from H'_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 <ref>. Then H_t,k has a filtration of type

    tk(k-2)    = k((t+1)(2+t(k-2))/2-1) - kt(2+(t-1)(k-2))/2 - 1 + 1
       =|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 <ref>, and have a quadratic gap between the radius and foundation size (both Θ(t)) versus the number of vertices and edges (both Θ(t^2)).


 



[Crash (Figure <ref>, page 36)]
 Finally, we give a k-uniform hypergraph family with an exponential separation in parameters (Figure <ref>). For k ≥ 2 an integer, let Σ = {1,2,…,k-1} be an alphabet of size k-1.
  For t ≥ 1 an integer, consider the hypergraph C_t,k with vertices V(C_t,k)=⋃_j=0^t V_j where V_j = Σ^t-j+1 for all 1 ≤ j ≤ t, and V_0 = {(0,x) |  x ∈Σ}. The edge set of C_t,k is the union of all edges of the following three forms:

  
  * For every x∈ V_1, E_x = {x}∪ V_0;
  
  * for every 2≤ j ≤ t and every x∈ V_j, E_x={x}∪{xa |,a∈Σ};
    
  * E_0={(0,1)}∪ 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∈ V_1, then adding all the edges E_x with x∈ V_2 etc. with E_0 added last. Clearly this transfer filtration has radius t and type

    k-1     = (k-1)(1+(k-1)^t-1/k-2) - (k-1)((k-1)^t-1)/k-2 -1+1
        = |V(C_t,k)|-|E(C_t,k)|+1 .

In particular, this family satisfies the preconditions for Theorem <ref> and yields an exponential separation between radius and foundation size (Θ(t) and O(k), respectively) versus the number of vertices and edges (Θ[(k-1)^t] for constant k≥ 3). Thus, via the runtime of Equation (<ref>), our algorithm runs in polynomial time on crash (i.e. time poly(|V(C_t,k)|,|E(C_t,k)|)), whereas brute force diagonalization would require exponential time in |V(C_t,k)|. Intuitively, one may think of crash hypergraphs as a hypergraph-version of trees; a crash hypergraph “starts small” (has a small foundation, corresponding to a tree root), and then rapidly expands “horizontally”, resulting a hypergraph whose “depth” is short relative to the number of vertices (just as the depth of a complete binary tree is logarithmic in the size of the tree). Whether such hypergraphs are physically relevant is not clear; here, this family is presented primarily as a proof of concept demonstrating that exponential separations (versus brute force) are indeed possible for our algorithm.









§ 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) <cit.>. Formally, an SDR for a sequence of sets S_1,…, S_m is a sequence of distinct elements x_1,…,x_m such that x_i∈ S_i for all i∈[m]. Hall's well-known Marriage Theorem says that a set system S_i_i=1^m has an SDR if and only if for any I⊆ [m], ⋃_i∈ IS_i≥I.

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=E and n=V for brevity.

[see, e.g., Corollary 5.2 of <cit.>]
    Let G=(V,E) be a d-regular r-hypergraph. If m≤ 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 <ref>, 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 <ref>.


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



  Consider a transfer filtration G_0⊆ G_1⊆⋯⊆ G_m=G so that G has m edges and transfer type b=|V(G_0)|. Suppose the edges E(G)={E_1,… E_m} are ordered in such a way that E(G_i)∖ E(G_i-1)={E_i} for all i∈{1,…,m}. By the Marriage Theorem, it suffices to prove that |E_i_1∪⋯∪ E_i_l|≥ l for any increasing sequence 1≤ i_1<i_2<⋯<i_l≤ m. For each i∈{1,…,m}, let μ_i=|V(G_i-1)|-|V(G_i)|+1. By definition of transfer filtration, μ_i∈{0,1} for each i∈{1,…,m}. More precisely, μ_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≤ i_1<i_2<⋯<i_l≤ m, we have |E_i_1|=k, |E_i_1∪ E_i_2|≥ k+1-μ_i_2 and, iteratively adding one edge at the time,

    |E_i_1∪ E_i_2∪⋯∪ E_i_l|≥ k+l-1-(μ_i_2+⋯+μ_i_l).

Since by assumption we have

    μ_i_2+⋯+μ_i_l≤μ_1+μ_2+⋯+μ_m=b-|V(G)|+|E(G)|≤ k-1 .

Substituting (<ref>) into (<ref>) we obtain

    |E_i_1∪ E_i_2∪⋯∪ E_i_l|≥ k+l-1-(k-1)≥ 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.









 §.§ 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∈ S satisfies A∩ B=k.







  §.§.§ 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 e_i∩ e_j=2 (Lemma <ref>) or e_i∩ e_j≥ 2 (Lemma <ref>). The characterization for 2-intersecting families follows as an immediate corollary, and is given in Corollary <ref>.

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

	
  *  m=n and G has an SDR, and
	
  *  If a pair of distinct edges e_i and e_j intersects, then e_i ∩ e_j=2. 	

Then G is a cycle of length 4.


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


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

We argue that this structure is impossible, given conditions <ref> and <ref>. 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:

	
  * 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 <ref> since {v_1,v_2,v_6}∩{v_2,v_3,v_4}=1.
	
		


150pt!

    (v1) at (0,0) ;
    (v2) at (2,0) ;
    (v3) at (4,0) ;
    (v4) at (6,0) ;
    (v5) at (3,-2);
	(v6) at (1,-2);
    ǐn v1,v2,v3,v4,v5,v6
      [circle, minimum size=0.4cm, line width=0pt] ('̌) at ()̌ ;
    
    [draw=black, fill=red, opacity=0.2]
		(v1'.270) – (v3'.270) arc (-90:90:0.2)
		– (v2'.90) arc (90:90:0.2)
		– (v1'.90) arc (90:270:0.2) – cycle;
		
    [draw=black, fill=blue, opacity=0.2]
		(v2'.90) – (v4'.90) arc (90:-90:0.2)
		– (v3'.-90) arc (-90:-90:0.2)
		– (v2'.-90) arc (-90:-270:0.2) – cycle;
		
    [draw=black, fill=green, opacity=0.2]
		(v3'.-30) – (v5'.-30) arc (-30:-150:0.2)
		– (v2'.210) arc (210:90:0.2)
		– (v3'.90) arc (90:-30:0.2) – cycle;
	
	[draw=black, fill=yellow, opacity=0.2]
		(v2'.-30) – (v6'.-30) arc (-30:-150:0.2)
		– (v1'.210) arc (210:90:0.2)
		– (v2'.90) arc (90:-30:0.2) – cycle;
		
    łin 1,...,6
      [black] (vł) circle (2pt) node [label=below:v_ł] ;
    




	

	
  * Add an edge containing one new vertex v_6, and two outer vertices, e.g. {v_1,v_5,v_6}. This violates property <ref>, since {v_1,v_5,v_6}∩{v_2,v_3,v_5}=1.
	

150pt!
	
    (v1) at (0,0) ;
    (v2) at (2,0) ;
    (v3) at (4,0) ;
    (v4) at (6,0) ;
    (v5) at (3,-2) ;
	(v6) at (1,-2) ;
    ıin 1,...,6
      [circle, minimum size=0.4cm, line width=0pt] (vı') at (vı) ;
    
    [draw=black, fill=red, opacity=0.2]
		(v1'.270) – (v3'.270) arc (-90:90:0.2)
		– (v1'.90) arc (90:270:0.2) – cycle;
		
    [draw=black, fill=blue, opacity=0.2]
		(v2'.90) – (v4'.90) arc (90:-90:0.2)
		– (v2'.-90) arc (-90:-270:0.2) – cycle;
		
    [draw=black, fill=green, opacity=0.2]
		(v3'.-30) – (v5'.-30) arc (-30:-150:0.2)
		– (v2'.210) arc (210:90:0.2)
		– (v3'.90) arc (90:-30:0.2) – cycle;
	
	[draw=black, fill=yellow, opacity=0.2]
		(v1'.60) – (v5'.60) arc (60:-90:0.2)
		– (v6'.-90) arc (270:210:0.2)
		– (v1'.210) arc (210:60:0.2);
		
    łin 1,...,6
      [black] (vł) circle (2pt) node [label=below:v_ł] ;
    




	
  *  Add an edge containing one new vertex v_6, two inner vertices, e.g. v_2,v_3,v_6, which is the only case not violating property <ref>.


150pt!

    (v1) at (0,0) ;
    (v2) at (2,0) ;
    (v3) at (4,0) ;
    (v4) at (6,0) ;
    (v5) at (3,-2);
	(v6) at (3,2) ;
    ǐn v1,v2,v3,v4,v5,v6
      [circle, minimum size=0.4cm, line width=0pt] ('̌) at ()̌ ;
    
    [draw=black, fill=red, opacity=0.2]
		(v1'.270) – (v3'.270) arc (-90:90:0.2)
		– (v2'.90) arc (90:90:0.2)
		– (v1'.90) arc (90:270:0.2) – cycle;
		
    [draw=black, fill=blue, opacity=0.2]
		(v2'.90) – (v4'.90) arc (90:-90:0.2)
		– (v3'.-90) arc (-90:-90:0.2)
		– (v2'.-90) arc (-90:-270:0.2) – cycle;
		
    [draw=black, fill=green, opacity=0.2]
		(v3'.-30) – (v5'.-30) arc (-30:-150:0.2)
		– (v2'.210) arc (210:90:0.2)
		– (v3'.90) arc (90:-30:0.2) – cycle;
	
	[draw=black, fill=yellow, opacity=0.2]
		(v3'.30) – (v6'.30) arc (30:150:0.2)
		– (v2'.150) arc (150:270:0.2)
		– (v3'.270) arc (-90:30:0.2) – cycle;
		
    łin 1,...,6
      [black] (vł) circle (2pt) node [label=below:v_ł] ;
    







		
  * Add an edge containing two outer vertices, and one inner vertex, e.g. v_1,v_2,v_5, which violates property <ref>, since {v_1,v_2,v_5}∩{v_2,v_3,v_4}=1.
		

150pt!
		
	    (v1) at (0,0) ;
	    (v2) at (2,0) ;
	    (v3) at (4,0) ;
	    (v4) at (6,0) ;
	    (v5) at (3,-2) ;
	    ıin 1,...,5
	      [circle, minimum size=0.4cm, line width=0pt] (vı') at (vı) ;
	    
	    [draw=black, fill=red, opacity=0.2]
			(v1'.270) – (v3'.270) arc (-90:90:0.2)
			– (v1'.90) arc (90:270:0.2) – cycle;
			
	    [draw=black, fill=blue, opacity=0.2]
			(v2'.90) – (v4'.90) arc (90:-90:0.2)
			– (v2'.-90) arc (-90:-270:0.2) – cycle;
			
	    [draw=black, fill=green, opacity=0.2]
			(v3'.-30) – (v5'.-30) arc (-30:-150:0.2)
			– (v2'.210) arc (210:90:0.2)
			– (v3'.90) arc (90:-30:0.2) – cycle;
		
		[draw=black, fill=yellow, opacity=0.2]
			(v1'.90) – (v2'.90) arc (90:30:0.2)
			– (v5'.30) arc (30:-120:0.2)
			– (v1'.-120) arc (240:90:0.2);
			
	    łin 1,...,5
	      [black] (vł) circle (2pt) node [label=below:v_ł] ;
	    
	

	

	
	
  *  Add an edge containing two inner vertices and one outer vertex, e.g. v_2,v_3,v_4, which clearly violates property <ref>.
	

150pt!
	
    (v1) at (0,0) ;
    (v2) at (2,0) ;
    (v3) at (4,0) ;
    (v4) at (6,0) ;
    (v5) at (3,-2);
    ǐn v1,v2,v3,v4,v5
      [circle, minimum size=0.4cm, line width=0pt] ('̌) at ()̌ ;
    
	ǐn v1,v2,v3,v4,v5
      [circle, minimum width=1cm] (”̌) at ()̌ ;
    
	
	ǐn v1,v2,v3,v4,v5
      [circle, minimum width=.74cm] (”̌') at ()̌ ;
    
	
	[draw=black, fill=yellow, opacity=0.2]
		(v1”'.270) – (v3”'.270) arc (-90:90:0.37)
		– (v1”'.90) arc (90:270:0.37) – cycle;
		
    [draw=black, fill=blue, opacity=0.5]
		(v2'.90) – (v4'.90) arc (90:-90:0.2)
		– (v2'.-90) arc (-90:-270:0.2) – cycle;
	
	[draw=black, fill=pink, opacity=0.5]
		(v2”.90) – (v4”.90) arc (90:-90:0.5)
		– (v2”.270) arc (270:90:0.5) – cycle;	
		
    [draw=black, fill=green, opacity=0.2]
		(v3'.-30) – (v5'.-30) arc (-30:-150:0.2)
		– (v2'.210) arc (210:90:0.2)
		– (v3'.90) arc (90:-30:0.2) – cycle;
		
    łin 1,...,5
      [black] (vł) circle (2pt) node [label=below:v_ł] ;
    
	

	

	
  * Add an edge containing three outer vertices, e.g. v_1,v_5,v_4, which violates property <ref> since  {v_1,v_5,v_4}∩{v_2,v_3,v_4}=1.


150pt!

    (v1) at (0,0) ;
    (v2) at (2,0) ;
    (v3) at (4,0) ;
    (v4) at (6,0) ;
    (v5) at (3,-2);
    ǐn v1,v2,v3,v4,v5
      [circle, minimum size=0.4cm, line width=0pt] ('̌) at ()̌ ;
    
    [draw=black, fill=red, opacity=0.2]
		(v1'.270) – (v3'.270) arc (-90:90:0.2)
		– (v2'.90) arc (90:90:0.2)
		– (v1'.90) arc (90:270:0.2) – cycle;
		
    [draw=black, fill=blue, opacity=0.2]
		(v2'.90) – (v4'.90) arc (90:-90:0.2)
		– (v3'.-90) arc (-90:-90:0.2)
		– (v2'.-90) arc (-90:-270:0.2) – cycle;
		
    [draw=black, fill=green, opacity=0.2]
		(v3'.-30) – (v5'.-30) arc (-30:-150:0.2)
		– (v2'.210) arc (210:90:0.2)
		– (v3'.90) arc (90:-30:0.2) – cycle;
	
	[draw=black, fill=yellow, opacity=0.2]
		(v1'.45) – (v5'.120) arc(-120:-60:0.2)
		– (v4'.120) arc(120:-60:0.2)
		– (v5'.300) arc(300:250:0.2)
		– (v1'.250) arc(250:45:0.2);

    łin 1,...,5
      [black] (vł) circle (2pt) node [label=below:v_ł] ;
    




    
  * Add two new vertices, and one inner or outer vertex. This violates property <ref>.

We conclude that the only possibility is case <ref>, 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 <ref>, 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 <ref> can be extended:

	
  * Add a new vertex and two outer vertices, which violates property <ref>.


150pt!

    (v1) at (0,0);
    (v2) at (2,0) ;
    (v3) at (4,0);
    (v4) at (6,0) ;
    (v5) at (3,-2) ;
    ǐn v1,v2,v3,v4,v5
      [circle, minimum size=0.4cm, line width=0pt] ('̌) at ()̌ ;
    
    [draw=black, fill=red, opacity=0.2]
		(v1'.270) – (v3'.270) arc (-90:90:0.2)
		– (v2'.90) arc (90:90:0.2)
		– (v1'.90) arc (90:270:0.2) – cycle;
		
    [draw=black, fill=blue, opacity=0.2]
		(v2'.90) – (v4'.90) arc (90:-90:0.2)
		– (v3'.-90) arc (-90:-90:0.2)
		– (v2'.-90) arc (-90:-270:0.2) – cycle;
	
	[draw=black, fill=yellow, opacity=0.2]
		(v1'.45) – (v5'.120) arc(-120:-60:0.2)
		– (v4'.120) arc(120:-60:0.2)
		– (v5'.300) arc(300:250:0.2)
		– (v1'.250) arc(250:45:0.2);
    łin 1,...,5
      [black] (vł) circle (2pt) node [label=below:v_ł] ;
    





	
  * Add a new vertex, one inner vertex, and one outer vertex, which violates property <ref>, e.g. in:
	

150pt!

    (v1) at (0,0) ;
    (v2) at (2,0) ;
    (v3) at (4,0) ;
    (v4) at (6,0) ;
    (v5) at (8,0) ;
    ǐn v1,v2,v3,v4,v5
      [circle, minimum size=0.4cm, line width=0pt] ('̌) at ()̌ ;
    
    [draw=black, fill=red, opacity=0.2]
		(v1'.270) – (v3'.270) arc (-90:90:0.2)
		– (v2'.90) arc (90:90:0.2)
		– (v1'.90) arc (90:270:0.2) – cycle;
		
    [draw=black, fill=blue, opacity=0.2]
		(v2'.90) – (v4'.90) arc (90:-90:0.2)
		– (v3'.-90) arc (-90:-90:0.2)
		– (v2'.-90) arc (-90:-270:0.2) – cycle;
	[draw=black, fill=green, opacity=0.2]
		(v3'.90) – (v5'.90) arc (90:-90:0.2)
		– (v4'.-90) arc (-90:-90:0.2)
		– (v3'.-90) arc (-90:-270:0.2) – cycle;
		
    łin 1,...,5
      [black] (vł) circle (2pt) node [label=below:v_ł] ;
    





	
  * The only remaining option is to add an edge such as the blue one below. This temporarily violates property <ref>, since m≠ n.


150pt!

    (v1) at (0,0) ;
    (v2) at (2,0) ;
    (v3) at (4,0) ;
    (v4) at (6,0) ;    ǐn v1,v2,v3,v4
      [circle, minimum size=0.4cm, line width=0pt] ('̌) at ()̌ ;
    
    [draw=black, fill=red, opacity=0.2]
		(v1'.270) – (v3'.270) arc (-90:90:0.2)
		– (v2'.90) arc (90:90:0.2)
		– (v1'.90) arc (90:270:0.2) – cycle;
		
    [draw=black, fill=blue, opacity=0.2]
		(v2'.90) – (v4'.90) arc (90:-90:0.2)
		– (v3'.-90) arc (-90:-90:0.2)
		– (v2'.-90) arc (-90:-270:0.2) – cycle;
	
	[draw=black, fill=cyan, opacity=0.2, xshift=0cm]
	plot [smooth, tension=2] coordinates (v1'.180) (3,1.2) (v4'.0)
	arc(0: -90:0.2) – (v3'.270) arc(270:180:0.2)
	plot [smooth, tension=2] coordinates (v3'.180) (2,0.8) (v1'.0) arc(0:-180:0.2);
    łin 1,...,4
      [black] (vł) circle (2pt) node [label=below:v_ł] ;
    




	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 <ref> and <ref>. No further edges can be added, completing the proof.


150pt!

    (v1) at (0,0) ;
    (v2) at (2,0) ;
    (v3) at (4,0) ;
    (v4) at (6,0) ;    ǐn v1,v2,v3,v4
      [circle, minimum size=0.4cm, line width=0pt] ('̌) at ()̌ ;
    
    [draw=black, fill=red, opacity=0.2]
		(v1'.270) – (v3'.270) arc (-90:90:0.2)
		– (v2'.90) arc (90:90:0.2)
		– (v1'.90) arc (90:270:0.2) – cycle;
		
    [draw=black, fill=blue, opacity=0.2]
		(v2'.90) – (v4'.90) arc (90:-90:0.2)
		– (v3'.-90) arc (-90:-90:0.2)
		– (v2'.-90) arc (-90:-270:0.2) – cycle;
	
	[draw=black, fill=cyan, opacity=0.2]
	plot [smooth, tension=2] coordinates (v1'.180) (3,1.2) (v4'.0)
	arc(0: -90:0.2) – (v3'.270) arc(270:180:0.2)
	plot [smooth, tension=2] coordinates (v3'.180) (2,0.8) (v1'.0) arc(0:-180:0.2);
	
	[draw=black, fill=yellow, opacity=0.2]
	plot [smooth, tension=2] coordinates (v1'.180) (3,-1.2) (v4'.0)
	arc(0:180:0.2)
	plot [smooth, tension=2] coordinates (v4'.180) (4,-0.8) (v2'.0)
	arc(0:90:0.2) – (v1'.90) arc(90:180:0.2)
	;
    łin 1,...,4
      [black] (vł) circle (2pt) node [label=below:v_ł] ;
    









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

 
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 <ref> to enforce only e_i∩ e_j≥ 2 (as opposed to e_i∩ e_j= 2) and still obtain a characterization. Note that although the statement of Lemma <ref> 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).


Let G=(V,E) be a 3-uniform hypergraph with property <ref> in Lemma <ref>, and assume each pair of edges e_i and e_j which intersects satisfies e_i ∩ e_j≥ 2. Then G is one of the following:

	
  * A 3-stacked set, or
	
  * a tight star with two 2-stacked sets, or
	
  * a tight star with one 3-stacked set, or
	
  * a cycle of length 4.




Case (i) trivially holds, and case (iv) is given by Lemma <ref>. For cases (ii) and (iii), we return to the case analysis in the proof of Lemma <ref> involving Figure <ref>, i.e. the tight star. Following the proof of Lemma <ref>, 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 <ref>), or (2) create a parallel edge (case (v) in Lemma <ref>); note this latter case is now possible since we can have e_i∩ e_j=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 <ref> yields that no other choices of G are possible.







  §.§.§ 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 a unique 3-uniform hypergraph with m=n and an SDR — the well-known Fano plane.


The Fano plane is the unique projective plane of order 2, and can be represented by the Fano hypergraph G=(V,E) (see Figure <ref>) with V=v_1,v_2,v_3,v_4,v_5,v_6,v_7 and

    E={v_1,v_2,v_3},{v_1,v_4,v_5},{v_1,v_6,v_7},{v_2,v_4,v_6},{v_2,v_5,v_7},{v_3,v_4,v_7}, {v_3,v_5,v_6}.





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


	Let G=(V,E) satisfy the properties of the claim. WLOG, we begin with an arbitrary pair of intersecting edges, e_1=v_1,v_2,v_3 and e_2=v_1,v_4,v_5, pictured below:


90pt!
	
        [inner sep=0pt]
        (v1) at (210:2cm);
        (v2) at (270:1cm);
        (v3) at (330:2cm);
        (v4) at (150:1cm);
        (v5) at (90:2cm);
        ıin 1,...,5
            [circle, font=, minimum size=0.4cm, line width=0mm] (vı') at (vı) ;
        

        [draw=black, fill=yellow, minimum size=0pt, opacity=0.2]
            (v5'.150) – (v1'.150) arc (-210:-30:0.2cm) – (v5'.330) arc (-30:150:0.2cm);

        [draw=black, fill=blue, minimum size=0pt, opacity=0.2]
            (v1'.270) – (v3'.270) arc(-90:90:0.2cm) – (v1'.90) arc (90:270:0.2cm);
       łin 1,...,5
      [black] (vł) circle (2pt) node [inner sep=5pt, label=below:v_ł] ;
    
    
    


We proceed by adding edges one at a time while maintaining property (1). To add the third edge e_3, since the graph is 1-intersecting, there are two cases:

    
  (a)e_3=v_1,v_6,v_7 intersects both e_1 and e_2 at vertex v_1.
    	

    90pt!
	
        [inner sep=0pt]
        (v1) at (210:2cm);
        (v2) at (270:1cm);
        (v3) at (330:2cm);
        (v4) at (150:1cm);
        (v5) at (90:2cm);
        (v6) at (30:1cm);
        (v7) at (0,0);
        ıin 1,...,7
            [circle, font=, minimum size=0.4cm, line width=0mm] (vı') at (vı) ;
        

        [draw=black, fill=yellow, minimum size=0pt, opacity=0.2]
            (v5'.150) – (v1'.150) arc (-210:-30:0.2cm) – (v5'.330) arc (-30:150:0.2cm);

        [draw=black, fill=blue, minimum size=0pt, opacity=0.2]
            (v1'.270) – (v3'.270) arc(-90:90:0.2cm) – (v1'.90) arc (90:270:0.2cm);

        [draw=black, fill=orange, minimum size=0pt, opacity=0.2]
            (v6'.120) – (v1'.120) arc(120:300:0.2cm) – (v6'.300) arc(-60:120:0.2cm) ;
       łin 1,...,7
      [black] (vł) circle (2pt) node [inner sep=5pt, label=below:v_ł] ;
    

    
    



		
  (b) e_3=v_3,v_5,v_6 does not intersect e_1 and e_2 at v_1. By symmetry, we may represent this as below.


Let us now add the fourth edge, which can be done in one of two ways: Either we add a new vertex, or we do not add a new vertex.
	

	
  * If we add a new vertex: For case (a), we obtain a graph isomorphic to


90pt!

        [inner sep=0pt]
        (v1) at (210:2cm);
        (v2) at (270:1cm);
        (v3) at (330:2cm);
        (v4) at (150:1cm);
        (v5) at (90:2cm);
        (v6) at (30:1cm);
        (v7) at (0,0);
        (v1) ++(90:1.73cm) node (v8) ;
        (v1) ++(90:3.46cm) node (v9) ;
        ıin 1,...,9
            [circle, font=, minimum size=0.4cm, line width=0mm] (vı') at (vı) ;
        

        [draw=black, fill=yellow, minimum size=0pt, opacity=0.2]
            (v5'.150) – (v1'.150) arc (-210:-30:0.2cm) – (v5'.330) arc (-30:150:0.2cm);

        [draw=black, fill=blue, minimum size=0pt, opacity=0.2]
            (v1'.270) – (v3'.270) arc(-90:90:0.2cm) – (v1'.90) arc (90:270:0.2cm);

        [draw=black, fill=orange, minimum size=0pt, opacity=0.2]
            (v6'.120) – (v1'.120) arc(120:300:0.2cm) – (v6'.300) arc(-60:120:0.2cm) ;

		[draw=black, fill=red, minimum size=0pt, opacity=0.2]
            (v1'.0) – (v9'.0) arc(0:180:0.2cm) – (v1'.180) arc (-180:0:0.2cm);
       łin 1,...,9
      [black] (vł) circle (2pt) node [inner sep=5pt, label=below:v_ł] ;
    
    
    


    This does not have m=n and cannot be extended into a 1-intersecting family since any further edge (of size 3) would have to intersect 4 existing edges. For (b), a case analysis reveals that the only way to extend by adding a new vertex while maintaining the 1-intersection property is via a graph isomorphic to:
    

  * If we do not add a new vertex:
		
            
  * Case (a) can only be extended while maintaining the 1-intersecting property via a graph isomorphic to that in Figure <ref>.
			
  * For case (b), either we obtain a graph isomorphic to Figure <ref>, or we add e_4={v_2,v_4,v_6} to obtain Figure <ref>.


		
	
From the fifth edge onward, an analogous case analysis yields at each step that only two types of edges can be added at this point which preserve the 1-intersecting property: A “crossing edge” (as in Figure <ref>) v_1,v_6,v_7, v_3,v_4,v_7, or v_2,v_5,v_7, or a “circular edge” (as in Figure <ref>) v_2,v_4,v_6. When all such edges are added, we arrive at 7 edges total and obtain the Fano hypergraph. No fewer edges satisfies the m=n property, and clearly one cannot add another edge at this point while satisfying the 1-intersecting property. Finally, that G has an SDR can either be verified directly or by applying Corollary <ref>.




 §.§ Linear hypergraphs

In Section <ref>, we studied the set of 3-uniform hypergraphs in which if a pair of distinct edges intersect, then the intersection size is at least 2. We now take the complementary approach by asking that any pair of distinct edges intersect on at most one vertex. Such hypergraphs are called linear; note that linear hypergraphs are not necessarily 1-intersecting.

To set the context, linear hypergraphs in general (i.e. not necessarily with an SDR) are a complicated, but well-studied, class. Let L_3^l denote the set of edge intersection graphs of linear 3-uniform hypergraphs. (An edge intersection graph (EIG) is the generalization of a line graph to the setting of hypergraphs G; namely, the vertices of the EIG are the hyperedges of G, and two vertices of the EIG are neighbors if and only if their hyperedges in G intersect. Note that an EIG is a graph, i.e. a 2-uniform hypergraph.) It is known that L_3^l has no “finite characterization” in terms of a finite list of forbidden induced subgraphs <cit.>. However, the same paper does give the following characterization: A graph G is in L_k^l if and only if G has so-called Krausz dimension k. Unfortunately, it was later shown <cit.> that deciding if Krausz dimension is at most 3 is NP-complete (even on planar graphs of degree at most 5); thus, determining if a graph is an EIG of a linear 3-uniform hypergraph is NP-complete, suggesting the class of linear 3-uniform hypergraphs is quite complex.

In our setting, we study linear 3-uniform hypergraphs G with the additional guarantees that m=n and that G has an SDR. Nevertheless, we are not able to complete a structural characterization. Instead, we find various interesting “canonical-looking” examples. For brevity, we henceforth denote a linear 3-uniform hypergraph with m=n and an SDR as an LGraph.



  
*Minimum size and the Fano plane. What is the minimum size an LGraph can have?


    The minimum size of an LGraph is m=n=7, and the Fano hypergraph (Figure <ref>) is the unique LGraph of this size.


    The lower bound on minimum size follows from an old lemma of Corrádi.

 Let A_1,...,A_N be r-element sets and X be their union. If |A_i∩ A_j|≤ k for all i≠ j, then
X≥ (r^2N)/(r+(N-1)k).

Plugging in our LGraph parameters k=1, r=3, E={A_1,...,A_m}, V=X={1,...,n}, yields that E=V≥ 7. Note that the Fano hypergraph is an LGraph with m=n=7, which also happens to be 1-intersecting. To show uniqueness, we hence show that any LGraph with m=n=7 must be 1-intersecting; the claim then follows from Lemma <ref>.

      To show that any LGraph with m=n=7 must be 1-intersecting, suppose, for sake of contradiction, that G=(V,E) is an LGraph with m=n=7 and edges e_1,e_2 with e_1∩ e_2=∅. Then, the subgraph of G induced by e_1,e_2 is isomorphic to

    	

300pt!

    (v1) at (0,0);
    (v2) at (2,0) ;
    (v3) at (4,0);
    (v4) at (6,0) ;
    (v5) at (8,0) ;
    (v6) at (10,0) ;
    (v7) at (12,0) ;
    ǐn v1,v2,v3,v4,v5,v6,v7
      [circle, minimum width=0.2cm] ('̌) at ()̌ ;
    
    [draw=black, fill=red, opacity=0.2]
		(v1'.270) – (v3'.270) arc (-90:90:0.2)
		– (v2'.90) arc (90:90:0.2)
		– (v1'.90) arc (90:270:0.2) – cycle;
		
	[draw=black, fill=green, opacity=0.2]
		(v5'.90) – (v7'.90) arc (90:-90:0.2)
		– (v6'.-90) arc (-90:-90:0.2)
		– (v5'.-90) arc (-90:-270:0.2) – cycle;
		
    łin 1,...,7
      [black] (vł) circle (2pt) node [label=below:v_ł] ;
    




Since G is linear, any edge we add must contain v_4, and in turn, must also contain a unique vertex from each of v_1,v_2,v_3 and v_5,v_6,v_7. Thus, the maximum number of edges we may add is 3, giving a total of 5 edges, which is a contradiction.




  
*The tiling of the torus. There is a sense in which the Fano hypergraph is the “most compact” LGraph. On the opposite extreme, an example of what seems the “least compact” LGraph is the “tiling of the torus”, given in Figure <ref>. More precisely, this is the specialization of Example <ref> to the case k=3 and a_1=a_2=3.




  
*The Helly property. Another well-studied hypergraph property is the Helly property, which requires that any intersecting family F of hyperedges of the hypergraph G have non-empty intersection. An equivalent, perhaps more geometrically intuitive, characterization is the following:

    A hypergraph H has the Helly property if and only if for any three vertices a_1,a_2,a_3, the family of hyperedges which contains at least two of these vertices has non-empty intersection.

In the special case of linear hypergraphs, the Helly property forbids a “linear 3-cycle”, as illustrated in Figure <ref>. In this sense, linear Helly hypergraphs roughly generalize triangle-free graphs.

Observe now that the two “canonical-looking” LGraphs we have discussed thus far, the Fano plane and the tiling of the torus, do not satisfy the Helly property. This raises the question: Do all LGraphs violate the Helly property? In Lemma <ref>, we answer this question negatively by giving an LGraph with the Helly property. Thus, even with numerous restrictions (i.e. m=n, linear, Helly), the set of 3-uniform hypergraphs with SDRs seems non-trivial.

    There exists a linear 3-uniform hypergraph G=(V,E) with E=V=28 such that G satisfies the Helly property, and G has an SDR.


    Since the Helly property forbids a linear 3-cycle, the idea of the construction is to build a longer linear cycle, with added “links” between vertices to ensure m=n. We call this the “interlinked cycle” (iCycle) for short; a formal specification is given in Figure <ref>, and a graphical depiction in Figure <ref>. The claimed properties are tedious, but straightforward, to verify.
    
    




  
*Do all linear 3-uniform hypergraphs with m=n have an SDR?
The examples we have studied in this section are all LGraphs, even with constraints such as the Helly property. This raises the question: Could all linear 3-uniform hypergraphs with m=n have SDR's? Intuitively, this is plausible, as the linear property forces a 3-uniform hypergraph to be “spread out” in a rough sense. We now answer this question in the negative, and the construction of the counterexample will teach us something about the structure of LGraphs.

For this, we first require a definition of a block and useful lemma.


    For hypergraph G=(V,E), let G_E' denote the edge-induced subgraph of G by E'⊆ E. Then, we call G_E' a block if it has an equal number of vertices and edges.


    Let G=(V,E) be a hypergraph with an SDR. Let A denote a block in G. Then, the SDR matches the vertices in A to the edges in A. Moreover, for any other block B in G, A and B are vertex-disjoint.


    Let A=(V_A,E_A) be a block in G. Since A is edge-induced, the only vertices which can match to the edges in E_A are those in V_A. Since V_A=E_A by definition of a block, our first claim follows. The second claim now follows as a corollary, since if A and B intersect on vertex v∈ V, then both A and B require v as part of their respective SDR's by our first claim, which is impossible since each vertex can only be matched to a single edge.



    There exists a linear hypergraph with m=n which does not have an SDR.


    The intuitive idea is to “stitch together” three copies of (say) the Fano hypergraph with an extra edge, so that there is no way to match the new edge to a vertex. This loses the m=n property; we then add further edges and vertices to recover the property. The resulting hypergraph is depicted in Figure <ref>. That the graph lacks an SDR follows from Lemma <ref>; specifically, let e denote the unique edge incident on all three Fano hypergraphs. Since the latter are blocks, none of their vertices can be matched to e, implying e cannot be matched.


As an aside, note that the construction of Theorem <ref> can be modified to also satisfy the Helly property — namely, replace each copy of the Fano hypergraph with a copy of the iCycle, discard the inner two circular edges v_2,v_8,v_5 and v_3,v_4,v_7 and the two “straight-line” edges v_9,v_8,v_7 and v_4,v_5,v_6, and discard vertices v_4,v_5,v_7,v_8. The resulting hypergraph is linear, Helly, and satisfies m=n, but does not have a matching. Thus, the construction of Theorem <ref> appears to yield a fairly systematic approach for constructing hypergraphs without SDR's, but still satisfying other desirable properties such as being linear or Helly.




§ ACKNOWLEDGEMENTS

The first result of this project was partially completed while NdB was affiliated with the Centrum Wiskunde & Informatica; SG thanks Ronald de Wolf and Centrum Wiskunde & Informatica for their hospitality. SG thanks Howard Barnum and David Reeb regarding discussions on algebraic geometry, and David Gosset for discussions on Quantum SAT. NdB acknowledges support from the EPSRC National Quantum Technology
Hub in Networked Quantum Information Processing. SG acknowledges support from NSF grants CCF-1526189 and CCF-1617710.





