An Unholy Trinity: TFNP, Polynomial Systems, and the Quantum Satisfiability Problem

We begin by introducing the new framework of Weighted SDRs (WSDR), which underlies much of this work. Roughly, a WSDR (Definition 20) generalizes an SDR by introducing a weight function $w:V\to {\mathbb{Z}}_{\ge 0}$, such that for any vertex $v\in V$ corresponding to a qudit, $v$ can be matched to $w(v)$ clauses. Which weight function should one choose? In this work, when we say a given QSAT instance $G=(V,E)$ on $n$ qudits of local dimensions $d_1,\mathrm{\dots },d_n$ has a WSDR, we mean with respect to weight function $w(v_i)=d_i-1$ for each $i\in \{1,\mathrm{\dots },n\}$. Thus, on $n$-qubit systems, a WSDR is just an SDR. Checking whether $G$ has an WSDR can be done efficiently (Remark 28 in full version [3]).

Our first main result is that WSDRs are tightly connected to when a QSAT instance on qudits has a product state solution.

With this said, while interesting in its own right, the primary appeal of Theorem 1 for us here is the techniques behind its proof, which will be crucial for our study of MHS. Specifically, we give two independent proofs of Theorem 1. The first (Section 4.1) is completely different than [35], and introduces the use of the Chow ring (Section 4.1) to obtain a simple proof of just a few lines. The second (Section 4.2) gives a poly-time mapping reduction from QSAT on qudits with WSDR to QSAT on qubits with SDR, and then plugs in [35]. This reduction, in particular, will play a key role in our MHS-hardness result of Theorem 3.

WSDRs beyond QSAT. As an aside, we demonstrate the power of WSDRs beyond the study of QSAT by using Theorem 1 to give a simple proof of a result of Parthasarathy [45], which says that any completely entangled subspace⁵⁵5A subspace is completely entangled if it does not contain any product states [3, Definition 48]. has dimension at most ${\prod }_{i=1}^k{d}_i-{\sum }_{i=1}^k{d}_i+k-1$ (Corollary 49 in full version [3]).

We now discuss our first main result, for which we define our first subclass of TFNP, which involves systems of low-degree, multi-variate polynomial equations:

Comments regarding the constant bounds on the variable set size $s$ and degree $d$: (1) This ensures $\text{MHS}\subseteq \text{TFNP}$ even for inverse exponential $ϵ$, since poly-time Turing machines can efficiently perform basic arithmetic with polynomial bits of precision. (2) For Theorem 3 below, $d\in O(1)$ is what yields constant locality $k$, whereas $s\in O(1)$ yields constant local dimensional qudits. (3) Formally, MHS is a union of complexity classes ${\text{MHS}}_{s,d}$ over all positive natural numbers $s$ and $d$. (4) MHS does not obviously include general homogeneous systems as a special case due to $s\in O(1)$, i.e. one cannot trivially place all variables into one variable group. Finally, for precision $ϵ$, we shall utilize ${\text{MHS}}_{ϵ}$ when we wish to specify a particular precision $ϵ$. We now show that QSAT with SDR is “MHS-complete”⁶⁶6We use the term “MHS-complete” in the introduction for simplicity, but the formal statement is more subtle (Theorem 39). In the case of MHS-hardness, for example, it says any problem in ${\text{MHS}}_{s,d}(ϵ)$ can be reduced to solving $k$-QSAT on qubits with locality $k\ge {(s+1)}^d$ within precision $\mathrm{\Theta }(ϵ)$, for $s,d,k\in O(1)$. In particular, to contain this $k$-QSAT instance in ${\text{MHS}}_{s^{\prime },d^{\prime }}$, we now need a larger value $d^{\prime }\ge {(s+1)}^d$. In other words, our reduction does not produce a fixed $k$ which simultaneously yields hardness for all $s$ and $d$. This is similar to how for each level ${\mathrm{\Sigma }}_k^p$ of the Polynomial-Time Hierarchy (PH), Quantified Boolean Satisfiability with $k-1$ alternations (QBF_k) is ${\mathrm{\Sigma }}_k^p$-complete, while problems simultaneously complete for all levels of PH are not known.:

As even finding common roots of homogeneous polynomial systems in $n+1$ variables and $n$ equations remains an open problem [28], we interpret Theorem 3 as implying QSAT with SDR is intractable. Thus, we have the surprising juxtaposition that while classical SAT with SDR is easy, its quantum analogue is not.

To help understand the complexity of MHS, we give our second main result, which defines a second TFNP subclass, involving a single, high-degree, univariate polynomial equation. Below, a sparse polynomial (Definition 40), is one whose number of non-zero coefficients is logarithmic in its degree.

As implied by its name, SFTA is inspired by the Fundamental Theorem of Algebra (Theorem 41), which recall states that any non-constant complex polynomial has a complex root $r$. Two comments regarding restrictions in the definition: First, the sparsity ensures⁷⁷7Another possible definition generalizing ours is to encode a non-sparse polynomial succinctly via a poly-size circuit which, given index $i$, outputs the $i$th coefficient of $p$. For us, however, the sparsity is necessary for our proof technique behind Theorem 5. by definition that the degree $d$ is exponential in the encoding size of polynomial $p$. This is important, as root approximations can be computed in $\mathrm{poly}(d)$ time (see e.g. [48], as used in Section 4.4 of [2]), and thus the roots of a non-sparse polynomial can in general be efficiently approximated. Second, requiring $\left|r\right|\in [0,1+2\log (d)/d]$ is without loss of generality (Lemma 43), and is in fact necessary in order to prove $\text{SFTA}\subseteq \text{TFNP}$ (Theorem 44)⁸⁸8For example, if $d$ is exponential, then $p(2)$ can be doubly exponentially large, and thus not representable with polynomially many bits..

We now ask: What is the relationship between MHS and SFTA? We first conjecture $\text{SFTA}\subseteq \text{MHS}$, and are able to prove the following:

In words, SFTA can be reduced to QSAT with SDR if we require $|v⟩$ to perfectly satisfy all clauses, i.e. SFTA is contained in the version of MHS with error $ϵ=0$. (Recall, however, that we do not allow $ϵ=0$ in Definition 2, as the resulting class does not obviously allow poly-time verification of solutions.) We believe a more careful analysis of our construction behind Theorem 5 should yield the desired containment in MHS.

In the reverse direction, we believe $\text{MHS}⊈\text{SFTA}$. This belief notwithstanding, by leveraging an old result of Canny [11], we show that generic (Definition 18) instances of QSAT with WSDR can be embedded into the roots of a single, high-degree polynomial $p$ (see Theorem 83 of the full version [3]). (In fact, one obtains something stronger, known as a geometric resolution, i.e. a set of rational functions $\left\{r_i\right\}$, so that when $r_i$ is fed the $j$th root of $p$, it produces the $i$th amplitude of the $j$th solution to QSAT.) The polynomials $p$ and $r_i$, however, are only poly-space computable, which is why this cannot yield $\text{MHS}\subseteq \text{SFTA}$.

NP-hardness results. Via the construction of Theorem 5, we can also show that even slight variants of QSAT with SDR are no longer in TFNP (assuming $\text{P}\ne \text{NP}$), but rather NP-hard.

Finally, to complete the picture, we show that in contrast to Theorem 7, classical SAT with SDR with $O(1)$ additional clauses again becomes easy! This mirrors precisely the behavior Theorem 3 exhibits for MHS-hardness of QSAT with SDR versus the fact that classical SAT with SDR is efficiently solvable; see Table 1.

Since the MHS-completeness of Theorem 3 suggests QSAT with WSDR cannot be efficiently solved, the last part of this work rounds out our study by showing how to extend the parameterized algorithm of [2] in three different directions to solve new special cases efficiently.

Our first two results here concern the qubit case, and are complementary. In this setting, [2] efficiently solves QSAT with SDR for generic (Definition 18) instances of transfer type $b=n-m+1$ [3, Definition 85], where $m$ denotes the number of constraints and $n$ the number of qubits. Transfer type $b$ means that we can find a vertex set of size $b$, and an ordering of the hyperedges (called transfer filtration), such that each edge adds at most one vertex. Recall non-generic instances allow constraints that are not entangled across some bipartite cuts.

We first show that the generic assumption can be dropped if one assumes an “almost extending edge order” [3, Definition 87], which in turn implies the existence of an SDR [2]. We say an ordering of the hyperedges is $k$-almost extending if all but $k$ edges add a new vertex (for $k=1$, we just say almost extending). Kremer [33] gives an algorithm to efficiently compute these.

We then show that, instead of dropping the generic assumption, one can instead relax the transfer type assumption and still obtain a parameterized algorithm:

Finally, we sketch how to extend the algorithm of [2] to QSAT on qudits with WSDR. This allows us to obtain an exponential speedup over brute force for solving a new high-dimensional, non-trivial (but artificial) infinite family of instances on Pinwheel Hypergraphs (Section 7.5.1 and Figure 5 in full version [3]).

For the MHS-completeness in Theorem 3, containment in MHS holds since PRODSAT can be written as a special case of solving multi-homogeneous systems as follows. In the case of $2$-QSAT, for example, a tensor product state $|{\alpha }_1,{\beta }_2⟩:=|\alpha ⟩\otimes |\beta ⟩$ on two qubits satisfies a $2$-local constraint $|\varphi ⟩$ if and only if $0=⟨\varphi |{\alpha }_1,{\beta }_2⟩={\sum }_{i,j\in [2]}{\varphi }_{i,j}^{\ast }{\alpha }_i{\beta }_j.$ The right hand side above is a multilinear polynomial in the amplitudes $\{{\alpha }_1,{\alpha }_2\}$ (respectively, $\{{\beta }_1,{\beta }_2\}$) of $|\alpha ⟩$ (respectively, $|\beta ⟩$). So, we will treat these amplitudes as variables in a system of multi-linear polynomials. The catch is that there is an independent normalization condition implicit on each qudit’s amplitudes; in our example here, both ${\left|{\alpha }_1\right|}^2+{\left|{\alpha }_2\right|}^2=1$ and ${\left|{\beta }_1\right|}^2+{\left|{\beta }_2\right|}^2=1$ must be independently satisfied. Since we will later work in projective space, however, this normalization is not explicitly enforced (other than the implicit constraint $|\alpha ⟩,|\beta ⟩\ne 0$). Instead, we must allow the amplitudes of $|\alpha ⟩$ and $|\beta ⟩$ to adhere to different “length scales”, since the assignments our system gives to them may lead to different norms for each vector. And now we come to why we require multi-homogeneous systems instead of homogeneous systems in this paper – recall that by definition, a multi-homogeneous system allows us to partition variables into sets $S_i$, so that each polynomial is homogeneous with respect to each $S_i$. Thus, by setting $S_i$ to represent the amplitudes of qudit $i$, we obtain that each quantum constraint is independently homogeneous with respect to each qudit $i$. (Each monomial will have degree $0$ or $1$, depending on whether the constraint acts on qudit $i$.) In other words, each qudit’s amplitudes implicitly has its own independent normalization.

As for hardness, to reduce multi-homogeneous systems to PRODSAT, the ideal aim is to represent each variable group by a single qudit. In other words, if variable group $S_i$ contains $n_i$ variables, we embed each variable as an amplitude of an $n_i$-dimensional qudit $q_i$. The first problem this presents is that monomials in a multi-homogeneous system need not be linear in each variable set $S_i$. To thus simulate non-linearity, we create multiple copies of each $q_i$; by placing constraints on these simultaneously, we can create products of amplitudes from $q_i$. However, this raises a second challenge – this logic only holds when each copy of $q_i$ has an identical assignment! The natural way to resolve this is to enforce equality between all copies of $q_i$ by adding projectors onto the antisymmetric subspace. This, however, does not work for us, as the rank of the antisymmetric subspace for qu$d$its with $d>2$ is too large, requiring the addition of too many rank-$1$ constraints for an SDR to exist. To overcome this, we instead utilize the qudit-to-qubit reduction from our second proof of Theorem 1, which is a mapping iteratively replacing each $d$-dimensional qudit with a pair of $2$- and $(d-1)$-dimensional qudits. Thus, each qu$d$it is replaced with $d-1$ qu$b$its, and we show that the mapping preserves PRODSAT solutions. We are finally now in business, because on pairs of qubits, the projector onto the antisymmetric subspace is of rank $1$, and thus we can show that there exists an SDR for the instance output by our reduction.

We discuss the proof of Theorem 5, which recall shows how to embed the roots of an arbitrary sparse polynomial $p$ of exponential degree $d$ into the solution set of a QSAT with SDR instance. The tool we start with is a transfer function (used also, e.g., in [9, 35]; see Lemma 14), which roughly is the quantum generalization of the following standard classical approach for propagating assignments: Given (e.g.) clause $(x\vee y\vee z)$, if $x=y=0$, then $z=1$ necessarily. Via this tool, we show how to design $2$-local (respectively, $3$-local) rank-$1$ QSAT constraints which force a target qubit to encode any desired linear (respectively, quadratic) operations on an input state ${(x,y)}^T$. For example, via a $2$-local constraint $|{\varphi }_{12}⟩$ on qubits $1$ and $2$, we can enforce that if qubit $1$ has assignment ${(x,y)}^T$, then in order to satisfy ${\varphi }_{12}$, qubit $2$ must be set (proportional to) ${(a_{1}x+a_{2}y,b_{1}x+b_{2}y)}^T$, for any desired ${\left|a_1\right|}^2+{\left|a_2\right|}^2={\left|b_1\right|}^2+{\left|b_2\right|}^2=1$.

With these gadgets in hand, we then move to encoding input polynomial $p$ into QSAT by designing three sets of clauses. To begin, we homogenize $p(x)$ to a bivariate polynomial $q(x,y)$, and let $|v_0⟩={(x,y)}^T$ denote an assignment to the first qubit. Ultimately, this $x$ and $y$ will end up encoding our roots to $p$. Our first set of contraints uses transfer functions and square-and-multiply to create new qubits of various powers of $x$ and $y$, i.e. “power qubits” whose assignments must be proportional to ${(x^i,y^i)}^T$. Our second set of constraints then combines these power qubits with our transfer function gadgets to recursively construct $q(x,y)$ in a final target qubit, whose assignment must be proportional to ${(q(x,y),y^d)}^T$. The third set is a single constraint, which forces the target qubit’s state ${(q(x,y),y^d)}^T$ to be proportional to $(0,1)$, which enforcing $q(x,y)=0$. By “undoing” the homogenization, we can then show that $p(x/y)$ must be a root of $p$.

As this work bridges rather disjoint areas of study (TFNP, polynomial systems, and quantum satisfiability), we address possible comments/questions to set further context.

1. 1.

   Are product state solutions to quantum satisfiability problems interesting? Generally speaking, yes. Although solutions to quantum satisfiability problems are typically entangled, product state solutions have a long history of being used as an ansatz to study properties of local Hamiltonians (i.e. “quantum constraint satisfiability problems”) in the mean-field theory physics literature [22]. For example, mean-field ansatzes suffice to efficiently approximate ground state energies of planar [6, 8] and dense [23, 8] local Hamiltonians to within any desired relative error $(1\pm ϵ)$ for $ϵ>0$. In the case of $2$-local frustration free Hamiltonians (as in $2$-QSAT), exact product-state solutions always exist and can be found [10, 12], which has implications such as the fact that such Hamiltonians cannot be used to prepare resource states for one-way quantum computing [12].

2. 2.

   Why is adding SDRs to the picture interesting? PRODSAT with SDR is interesting as it falls under the “dimer model” of physics [32], which is useful as it is (1) exactly solvable and (2) aids in understanding phase transitions, which are typically difficult to study. For example, the original motivation of [35] was to understand the SAT-UNSAT phase transition in random QSAT instances. Therein, dimer coverings/SDRs were used to show that for clause densities below a certain $k$-dependent threshold, random $k$-QSAT instances are satisfiable with probability $1$ by a product state solution. While this did not perfectly resolve the exact SAT-UNSAT threshold, it significantly improved previously known lower bounds.

3. 3.

   Typically TFNP classes (e.g. PPAD) are defined via a complete problem whose input is a circuit succinctly encoding an exponentially large object (e.g. a circuit succinctly encoding an exponentially large graph for END-OF-LINE). On the other hand, MHS and SFTA, have their input explicitly written out? This is a good discussion point. Traditional “syntactic” circuit-based definitions have the advantage that the existence principle for the class is captured by a simple combinatorial complete problem, which can make reasoning about the class easier. This, however, has a downside – proving hardness results for new problems not specified by input circuits, which are arguably more natural, can be more challenging (see, e.g. Göös, Kamath, Sotiraki and Zampetakis’ [26] non-circuit based PPA_p-complete problem ($p\ge 3$ a prime) for the Chevalley-Warning theorem). In contrast, MHS and SFTA may be thought of as “white-box” TFNP subclasses, in that the object to be studied (i.e. polynomial equations) is specified explicitly, rather than succinctly via circuit. On the negative side, this has the downside of potentially obscuring the relationship between the class and the existence principle. On the positive side, it can bring establishing hardness results for further natural problems within reach, since the artificial circuit input encoding is bypassed. In our case, this motivation is further strengthed by the fact that MHS and SFTA are based on polynomials, which themselves are ubiquitous in the sciences, yielding a potentially promising route for characterizing the complexity of new TFNP problems.

4. 4.

   Is there also combinatorial principle underlying MHS? Yes and no. No, in that the existence principle for MHS is Bézout’s theorem, which is algebraic geometric. Yes, in that checking if the Bézout number $d_{\text{Béz}}>0$ boils down to checking if a certain bipartite graph has a perfect matching (see Observation 55 in the full version [3]). More generally, computing $d_{\text{Béz}}$ itself counts the number of perfect matchings in said graph (which is intractable, but also not necessary for our purposes).

5. 5.

   Can MHS or SFTA be related to existing TFNP subclasses? This would be indeed ideal, but our attempts thus far have not succeeded. The most obvious candidate is PPAD, due to its connection [44] to Brouwer’s fixed point theorem. This is because there is a natural algorithm⁹⁹9Due to David Gosset via private communication. using transfer functions to attempt to solve QSAT with SDR; roughly, this algorithm aims to converge to a product state assignment which is a fixed point under all local transfer functions. Unfortunately, Brouwer’s theorem requires convex sets, and the set of product state solutions is not convex. Moreover, the standard approach of moving to the convex hull of product states (i.e. mixed separable states) seems to break the transfer function formalism. We thus leave this as what we feel is an important and interesting open question.

We have defined and studied two TFNP subclasses connected to complex polynomial systems. The first, Multi-Homogeneous Systems (MHS), leads to the first formal proof of a quantum problem which, on the one hand, is guaranteed to have a “simple” (i.e. tensor product) solution, and on the other hand, is potentially intractable. As even the “simpler” setting of finding common roots of homogeneous polynomial systems in $n+1$ variables and $n$ equations is believed difficult [28], we thus view MHS-hardness as a viable indicator for computational hardness. Our second class, Sparse Fundamental Theorem of Algebra (SFTA), was used to show that the problem of computing roots of sparse high-degree univariate polynomials can be embedded into computing exact solutions to QSAT with SDR, thus showing SFTA is contained in the zero-error version of MHS. We conjecture in fact that $\text{SFTA}\subseteq \text{MHS}$ – can this be shown?

As each member of the trinity studied here (TFNP, polynomial systems, and quantum satisfiability problems) is unto itself a research field, many questions in their intersection remain open. For example, which natural classical problems might be complete for MHS or SFTA? Are there other TFNP subclasses related to polynomial systems over complex numbers? As discussed in “question and answer” above, can MHS or SFTA be related to standard TFNP subclasses such as PPAD? Similarly, how is the setting of “syntactic” (i.e. circuit-based) TFNP subclasses to be understood versus our “white-box” setting for MHS and SFTA? Finally, a more subtle question is whether our definition of MHS as a union of complexity classes ${\text{MHS}}_{s,d}$ is necessary, or whether there is a fixed choice of $(s,d)$ which suffices to capture the family of the union? Recall the roadblock here was that our reduction from ${\text{MHS}}_{s,d}$ to $k$-QSAT with SDR introduced a dependency in the locality $k$ on $(s,d)$.

Due to space constraints, we can only give the technical statements including preliminaries for our main results in the remainder of this paper. We give proof sketches for Theorems 1 and 3. All other proofs are deferred to the full version [3], which also contains additional exposition, examples, and figures to aid understanding.

Section 2 states basic definitions, including formally defining QSAT, PRODSAT, and the connection between PRODSAT and polynomial systems. Section 3 introduces Weighted SDRs (WSDR), which are then used in Section 4 to give our two proofs of Theorem 1, i.e. that QSAT with WSDR always has a solution. Section 5 defines our class MHS and proves MHS-completeness of QSAT with SDR (Theorem 3). Section 6 defines class SFTA, studies its relationship to MHS, and gives the NP-hardness results of Theorem 6 and Theorem 7. Section 7 of the full version [3] gives efficient algorithms for special cases of QSAT with WSDR.

At a high level, the Chow ring approach uses intersection theory [21, 18, 49]. One reason for the effectiveness of this approach in the study of PRODSAT (i.e. product state solutions to QSAT) is that intersection theory is designed to work with generic constraints. This is in essence why important intersection-theoretic quantities, such as the Bézout number, are encoded into the interaction hypergraph. More concretely, the key property of the Chow ring we leverage is as follows (Fact 28): Given a set of rank-$1$ QSAT constraints with solution sets $\{V_1,\mathrm{\dots },V_r\}$ (formally, hypersurfaces), the Chow ring has a canonical mapping from each $V_i$ to a “representative” of the Chow ring itself, denoted $[V_i]$. Then, if the product of these representatives is non-zero, i.e. $[V_1]\mathrm{\cdots }[V_r]\ne 0$, one immediately has that $V_1\cap \mathrm{\cdots }\cap V_r\ne \mathrm{\varnothing }$, i.e. the solution sets to each constraint share a common solution. Conversely, if $[V_1]\mathrm{\cdots }[V_r]=0$, generically, no joint solution exists.

We refer to [18, 21] for an in-depth discussion of the Chow ring of a variety. Here we limit ourselves to the multi-projective case which is relevant to PRODSAT. Recall we define ${𝒳}_{d_1,\mathrm{\dots },d_n}:={\mathbb{P}}^{d_1-1}(ℂ)\times \mathrm{\cdots }\times {\mathbb{P}}^{d_n-1}(ℂ)$.

This first proof of Theorem 1 will crucially use the notion of “representatives” $[V]$ of subvarieties $V$ relative to the Chow ring. For this, let $Z({𝒳}_{d_1,\mathrm{\dots },d_n})$ be the free abelian group of cycles, generated by subvarieties of ${𝒳}_{d_1,\mathrm{\dots },d_n}$. Linear combinations $n_1{V}_1+\mathrm{\cdots }+n_k{V}_k$ with positive coefficients can be thought of as the union of $n_1$ copies of the subvariety $V_1$, $n_2$ copies of the subvariety $V_2$, etc.

Here is the key fact we will need about subvariety representatives.

Theorem 1 now follows almost directly. Let $\mathrm{\Pi }=\{{\mathrm{\Pi }}_i\}$ be an instance of QSAT on qudits $|{\phi }_1⟩,\mathrm{\dots },|{\phi }_n⟩$ of dimensions $d_1,\mathrm{\dots },d_n$, respectively. Recall the weighted hypergraph $(G,w)$ with $V(G)=\{v_1,\mathrm{\dots },v_n\}$, $E(G)=\{e_1,\mathrm{\dots },e_m\}$ such that $v_i\in e_j$ if and only if the clause ${\mathrm{\Pi }}_j$ acts non-trivially on the qu-$d_i$-it $|{\phi }_i⟩$. The weight function $w$ encodes the information regarding the dimension of the qudits, namely $w(v_i)=d_i-1$ for each $i\in \{1,\mathrm{\dots },n\}$.

Let $V_i$ be the hypersurfaces corresponding to the clauses ${\mathrm{\Pi }}_i$, $i=1,\mathrm{\dots },m$. Since $V_i$ is of degree $1$ in the variables corresponding to the qubits on which ${\mathrm{\Pi }}_i$ acts non-trivially and of degree $0$ in the remaining ones (see Equation 2), its image in the Chow ring is

Hence,

which is non-zero if and only if there is a summand in which each $H_j$ appears at most $d_j-1$ times i.e. if and only if $(G,w)$ has a WSDR. The claim now follows from Fact 28. $◀$ Actually, the proof shows an additional fact, which we will utilize in Section 4.2: