Quantum 2-SAT on Low Dimensional Systems Is QMA₁-Complete: Direct Embeddings and Black-Box Simulation

We show two main results, along with a third preliminary one.

1. ${\mathrm{QMA}}_1$-hardness for qubit systems. The complexity of $(d_A\times d_B)-\mathrm{QSAT}$ including our new results is summarized in Table 1. The first main result is as follows.

Here, $N$ denotes the number of gates⁹⁹9As an aside, we assume in this paper that the ${\mathrm{QMA}}_1$ verifier utilizes the standard “Clifford + T” gate set. See also [39] for an in-depth discussion of the “gate set issue” of ${\mathrm{QMA}}_1$. used by the ${\mathrm{QMA}}_1$-verifier. Thus, qubit systems can encode ${\mathrm{QMA}}_1$-hardness. Let us be clear that the surprising part of this is not that this setting is intractable – indeed, even classical $(2\times 3)$-SAT is known to be NP-hard (e.g. [34]). What is surprising is that one can encode quantum verifications in such low dimension, for two reasons. First, a priori a $2$-dimensional space for $2$-local constraints appears too limited to exactly¹⁰¹⁰10An exact encoding appears needed by definition of $\mathrm{QSAT}$. This is in strong contrast to $2$-LH, where approximate encodings are allowed (since all constraints need not be simultaneously satisfiable) via perturbation theory [29, 10]. encode a computation – a two-dimensional space only appears to suffice to encode a “data qubit”, so where does one encode the “clock” tracking the computation? Second, the entanglement of $(2\times d)$ systems is generally easier to characterize than that of $(d\times d)$ systems. For example, whether a $(2\times 2)$ or $(2\times 3)$ system is entangled is detectable via Peres’ Positive Partial Transpose (PPT) criterion [37], whereas detecting entanglement for $(d\times d)$ systems (for polynomial $d$) becomes strongly NP-hard [25, 27, 21]. And recall that a “sufficiently entangled” ground space is necessary to encode ${\mathrm{QMA}}_1$-hardness.

As a complementary result, we show that one can “trade” dimensions in the construction above if one is careful, i.e. the $5$ in $(2\times 5)$ can be reduced to $4$ at the expense of increasing $2$ to $3$.

One can also consider general Quantum $2$-SAT on qu-$d$-its of identical dimension $d$, which is ${\mathrm{QMA}}_1$-complete for $d=5$ [17]. Theorem 1.2 improves this to $d=4$.

We remark that obtaining Theorems 1.1 and 1.2 is significantly more involved than the previous best ${\mathrm{QMA}}_1$-hardness for $(3\times 5)-\mathrm{QSAT}$ [17] (details in “Techniques” below), and in particular requires (among other ideas) a simplified analysis of the advanced 2D-Hamiltonian framework of Gosset and Nagaj for $(2\times 2\times 2)$-QSAT (i.e. $3$-QSAT on qubits) [24]¹¹¹¹11At a first glance, it seems like $(2\times 2\times 2)$-QSAT can be reinterpreted as $(2\times 4)-\mathrm{QSAT}$-QSAT by combining two qubits into a qu-$4$-dit. Indeed, a single $(2\times 2\times 2)$-constraint can be embedded straightforwardly into a $(2\times 4)$-constraint. However, the interactions between a set of $(2\times 2\times 2)$-constraints seems difficult to directly reproduce via a set of $(2\times 4)$-constraints., a new clock construction, and the Unitary Labelled Graphs of Bausch, Cubitt and Ozols [6]. One of the payoffs is that we obtain a “tight”¹²¹²12By “tight”, we mean that it is not currently known for either QSAT or LH how to get a promise gap larger than $\mathrm{\Omega }(1/N^2)$ [42]. soundness gap of $\mathrm{\Omega }(1/N^2)$ for Theorem 1.1, compared to the $\mathrm{\Omega }(1/N^6)$ gap of [24]. This allows us to recover the $3$-QSAT hardness results of [24], but with improved soundness¹³¹³13For clarity, this improved soundness is not necessary for our results, but an added bonus of our new analysis.:

2. Low dimensional systems on the line. Our next main result is the following.

This improves significantly on the previous best 1D $(11\times 11)-\mathrm{QSAT}$ ${\mathrm{QMA}}_1$-hardness construction of Nagaj [34], showing that frustration free Hamiltonians on qutrits can encode not just entangled ground states (cf. [9]), but also ${\mathrm{QMA}}_1$-hard computations.

For clarity, there is a trade-off in the parameter, $d$, which we now elaborate. A key novelty of Theorem 1.4 is its proof via black-box reduction (see “Techniques” below), as opposed to a direct embedding of a ${\mathrm{QMA}}_1$ computation. Specifically, given an arbitrary 1D Hamiltonian $H$ on $d^{\prime }$-dimensional qudits, we embed it into an effective 1D $(3\times d)-\mathrm{QSAT}$ instance with $d\in O({(d^{\prime })}^4)$ (i.e. $d\in O(1)$ for constant $d^{\prime }$). On the not-so-positive side, the generality of this approach means that an input 1D Hamiltonian $H$ on $d^{\prime }$-dimensional qudits is mapped to a 1D Hamiltonian on constraints of dimension $(3\times O({(d^{\prime })}^4))$, i.e. the first dimension drops to $3$ at the expense of the second dimension increasing. Thus, for example, if we plug in the 1D $(11\times 11)$ ${\mathrm{QMA}}_1$-hardness construction [34], Theorem 1.4 gives ${\mathrm{QMA}}_1$-hardness for $(2\times 76176)-\mathrm{QSAT}$.

On the positive side, however, our technique is the first use of (a weaker notion) of the influential idea of local simulation (Bravyi and Hastings [7], Cubitt, Montanaro, and Piddock [13]; see Definition 4.1 of [22] for a simpler statement) in the study of QSAT. Roughly, in such simulations, given a local Hamiltonian $H$ on $n$ qubits, one typically applies a local isometry $V$ to each qubit, i.e. maps $H\mapsto V^{\otimes n}H{(V^{†})}^{\otimes n}$, blowing up the input space $A$ into a larger, “logical” space $B$. By cleverly choosing an appropriate Hamiltonian $H^{\prime }$ on $B$, one forces the low-energy space of $H^{\prime }$ to approximate $H$. Traditionally, the drawback of this approach is its reliance on perturbation theory, which necessarily gives rise to¹⁴¹⁴14In words, perturbation theory is only known to be able to show $\mathrm{QMA}$-hardness for $k$-LH, as opposed to ${\mathrm{QMA}}_1$-hardness for $k$-QSAT. frustrated Hamiltonians $H^{\prime }$. Here, however, we show for the first time that a weaker¹⁵¹⁵15For clarity, the simulations of [7, 13] reproduce the whole target Hamiltonian $H$, whereas our approach is weaker in that we prove simulation of only $H$’s nullspace. A similar notion of simulation is discussed by Aharonov and Zhou [3], called gap simulation, where only the ground space is approximately simulated. version of such local embeddings can be designed even for the frustration-free setting, ultimately yielding Theorem 1.4.
3. Towards qubits on the line. Finally, we initiate the study $(2\times d)$ on a line by proving that even a frustration-free Hamiltonian on a line of alternating particles with dimensions $2$ and $4$ can have a unique entangled ground state.

We focus on our main results, Theorem 1.1 and Theorem 1.4.

${\mathrm{QMA}}_1$-hardness for $(2\times 5)-\mathrm{QSAT}$. The basic idea behind most (if not all) ${\mathrm{QMA}}_1$-hardness constructions for QSAT is to embed a so-called history state $|{\psi }_{\text{hist}}⟩$ encoding the ${\mathrm{QMA}}_1$ verifier’s circuit $U$ into the nullspace of a local Hamiltonian $H$. Specifically, let $U=U_T\mathrm{\cdots }{U}_1$ be a sequence of $1$- and $2$-qubit gates. Then, the Feynman-Kitaev history state [19, 30] is given by

for register $A$ the proof register, $B$ the ancilla register, and $C$ the clock register. This should be thought of as the quantum analogue of a Cook-Levin tableau, where the steps of the computation are now encoded in superposition over time $t$. While this basic idea is simple, the challenge lies in implementing it when restricted to certain local dimensions, clause/interaction localities, or interaction geometries. Progress for QSAT in particular has largely been difficult, since in contrast to the setting of LH, one does not have access to the tools of perturbation theory, which necessarily create Hamiltonians with frustrated ground spaces (i.e. empty nullspaces). Instead, QSAT hardness constructions must carefully stitch together rather involved gadgets to logically effect the history state idea above.

To this end, we begin by discussing our approach for Theorem 1.1. We wish to encode local Hamiltonian constraints which force any potential null state to repeatedly update the current time in the clock register from $t$ to $t+1$, along with applying the $t$th gate of $U$, as sketched above. However, even embedding a clock (never mind the full computation of $U$!) into the nullspace of a $(2\times d)$-Hamiltonian is non-trivial, as we only have qubit-systems at our disposal to act as “auxiliary particles” (as opposed to qutrits in [17]). Thus, our first challenge is to break this “qutrit barrier”. We illustrate our techniques in a toy example.

Our starting point is to embed a simple clock into the null-space of a $(3\times 3)$-Hamiltonian, and subsequently logically simulate this clock by pairing “indicator qubits” (i.e. qubit auxiliary particles) with $6$-dimensional qudits as follows. It is straightforward to write down a $(3\times 3)$-Hamiltonian encoding the simple sequence of clock states (e.g. on $3$ qutrits) $(|100⟩,|200⟩,|210⟩,|220⟩,|221⟩,|222⟩)$ in its nullspace, where note that only a single qutrit changes in each step. To break the “qutrit barrier”, we thus now implement each qutrit in this clock logically in a larger space consisting of a $6$-dimensional qudit and a triple of “indicator qubits”. Formally, qutrit $|x⟩\in \{|0⟩,|1⟩,|2⟩\}$ is encoded via

where $\alpha$ is $6$-dimensional, and $\beta$ consists of three qubits labelled ${\beta }_0,{\beta }_1,{\beta }_2$. To illustrate the idea behind this encoding, consider a projector that enforces equality (i.e. applies an identity gate) between the first two clock states (we also call this a $|100⟩\leftrightarrow |200⟩$ transition). In $(3\times 3)$, we can use the projector onto $|10⟩-|20⟩$ (i.e. $\frac{1}{2}(|1⟩-|2⟩)(⟨1|-⟨2|)\otimes |0⟩⟨0|$) acting on the first two qutrits, where $|0⟩⟨0|$ on the second qutrit ensures that the projector only acts on the first two timesteps. Using our encoding, we can realize this transition with a $(2\times 6)$-projector onto ${|11⟩}_{\alpha ,{\beta }_0}-{|21⟩}_{\alpha ,{\beta }_0}$. This uses two features of the encoding: (1) a transition on a logical qutrit can be implemented with a $1$-local projector on qudit $\alpha$ (here $\frac{1}{2}(|1⟩-|2⟩){(⟨1|-⟨2|)}_{\alpha }$), and (2) a projection onto a standard basis state $|i⟩\in \{|0⟩,|1⟩,|2⟩\}$ of a logical qudit can be implemented with a $1$-local projector onto an indicator qubit ${\beta }_i$ (here $|1⟩{⟨1|}_{{\beta }_i}$).

This qutrit encoding (Equation 2) generalizes to qudits of any dimension, and combined with the $(3\times 5)$-Hamiltonian of [17], gives ${\mathrm{QMA}}_1$-hardness of $(2\times 10)-\mathrm{QSAT}$. We can remove some unused indicator qubits to improve this to $(2\times 7)-\mathrm{QSAT}$ (see [40]) as the indicator requires an extra qudit dimension ($|x⟩$ and $|x^{\prime }⟩$).¹⁷¹⁷17We need both and ${|x⟩}_{\alpha }$ and ${|x^{\prime }⟩}_{\alpha }$ so that logical $|x⟩$ and $|y⟩$ differ only in a single qudit (on a subspace), which allows for a $1$-local transition. Since the indicator qubits are “off” on ${|x⟩}_{\alpha }$, we need a unique ${|x^{\prime }⟩}_{\alpha }$ to “turn on” the correct indicator via a transition.

Further improvement to $(2\times 5)-\mathrm{QSAT}$ requires much more work. In order to directly enforce the application of a gate $U_t\ne 𝕀$ in a history state (Equation 1) with a $2$-local projector, we can only use a single qudit from the proof register and a single qudit from the clock register. Hence, we need to be able to project onto clock states with a $1$-local qudit projector. For that, Eldar and Regev [17] introduce the notion of “$u$nborn”, “$d$ead”, and “$a$live” states, where non-trivial transitions only happen on the “alive” states, which uniquely identify a single timestep. Having separate “unborn” and “dead” states allows the clock states to have the general structure $d\mathrm{\cdots }dau\mathrm{\cdots }u$, which is easy to enforce with $2$-local constraints.¹⁸¹⁸18A natural question is if we can reduce the alphabet $\{a,u,d\}$ to a simpler binary alphabet $\{0,1\}$, so that clock states look like $\{|100⟩,|010⟩,|001⟩\}$. Unfortunately, there is no set of $2$-local projectors whose joint nullspace is the span of $\{|100⟩,|010⟩,|001⟩\}$. The common unary encoding $|100⟩,|110⟩,|111⟩$ cannot be used here because such states cannot be identified $1$-locally. In fact, [17] uses three “alive states” $a_1,a_2,a_3$ to implement a CNOT gate via a “triangle gadget”, which routes states with $|0⟩$ and $|1⟩$ in the control register along two different paths, only applying the $X$ gate on the path of $|1⟩$ (see Figure 1(a)).

Gosset and Nagaj [24] (see Figure 1(b)) introduce the idea of a 2D-clock with two separate clock registers for the $X$- and $Y$-directions. Hence, clock states are vertices in a 2D-grid and therefore can realize separate paths while only requiring transitions between “adjacent” (in one dimension) clock states. The next idea of our construction is to implement this 2D-Hamiltonian of [24] using just two “alive” states in $2$-QSAT (compared with three “alive” states in [17] for $2$-QSAT; note [24] uses their 2D-clock for $3$-QSAT). Figure 1(b) depicts the “effective Hamiltonian” leveraging this idea in order to implement a CNOT gate. Note Figure 1(b) is simplified; the actual implementation with $2$-local projectors is significantly more involved (see full version [40]). This is due to complications which arise from geometric limitations: For example, we are not able to restrict the $U_0$ transition (Figure 1(b)) in the $Y$-direction (i.e. $U_0$ would be applied from $x=2$ to $x=3$ for all coordinates $y$).

To implement the ideas of the previous paragraph, we extract the 2D-Hamiltonian of [24] as a generic construction into which we can plug any clock satisfying certain requirements (see Theorem 3.1). Thereby we obtain ${\mathrm{QMA}}_1$-hardness for $(3\times 4)-\mathrm{QSAT}$. Then we simulate this $(3\times 4)$-clock on a $(2\times 5)$-system via the indicator qubit principle (similar to Equation 2). Note that when implementing a logical $4$-dit on a $(2\times 5)$-system, we can only use a single indicator qubit. Thus, we need a very carefully crafted $(3\times 4)$-clock, and further “technical tricks”, which we omit in this introduction.

Finally, to analyze the 2D-Hamiltonian, we prove a novel technical lemma, which we dub the “Nullspace Connection Lemma” (Lemma 3.2). This enables us to split the 2D-Hamiltonian into smaller gadgets (see Figure 1(b) and [40] for the individual gadgets), each of which implements a small part of the history state and is relatively straightforward to analyze. The gadgets are then connected with additional transitions to form the complete Hamiltonian (see [40]), whose nullspace is spanned by superpositions of the gadget’s history states. Footnote 20 gives a visualization and informal statement of the lemma. The Connection Lemma is quite generic and can also be applied to, e.g., the original circuit Hamiltonian of Kitaev [30] (see Remark 3.3), matching the $\mathrm{\Omega }(1/N^2)$ soundness (smallest non-zero eigenvalue) therein. Furthermore, the Connection Lemma is proven directly via the Geometric Lemma [30] and does not require transformation to the Laplacian matrix of a random walk, unlike [30]. Our main application of the Connection Lemma is to give a simplified proof for the 2D-Hamiltonian with improved soundness. Since the Connection Lemma requires modifications to the Hamiltonian of [24], we actually use our own variant of [24]’s gadget, which is slightly more compact (using $6M+1$ clock states as opposed to $9M+3$ for $M$ gates). Finally, we do not rely on numerical methods to derive the nullspaces of the individual gadgets (cf. the gadget analysis of [24], which required numerics), and instead give a formal proof based on the theory of unitary labeled graphs [6]. The upshot is that our overall approach is very flexible – by combining unitary labelled graphs with the Connection Lemma, one can in principle analyze combinations of Hamiltonian gadgets beyond just our 2D setting with relative ease. Therefore, we believe the Connection Lemma will find uses in future works.

${\mathrm{QMA}}_1$-hardness for $(3\times d)-\mathrm{QSAT}$ on the line. As mentioned earlier, in contrast to the direct embedding for Theorem 1.1, for Theorem 1.4 we instead use a black-box simulation. In other words, we do not give a new circuit-to-Hamiltonian mapping, but instead bootstrap the prior ${\mathrm{QMA}}_1$-completeness result of QSAT on a line of qu-$d$-its with $d=11$ due to Nagaj [34]. Specifically, we construct a general embedding of any 1D-Hamiltonian $H$ on a line of qudits into a Hamiltonian $H^{\prime }$ on an alternating line of qu-$d^{\prime }$-its and qutrits. We then plug the [34] construction into this embedding. To design our embedding, each qu-$d^{\prime }$-it is treated as two logical qu-$d^{\prime \prime }$-its with $d^{\prime \prime }=\sqrt{d^{\prime }}$ (see Figure 1.3; Figure 4.2 for technical details). We construct a Hamiltonian $H_{\mathrm{logical}}^{\prime }$ that restricts the $(d^{\prime \prime }\times 3\times d^{\prime \prime })$ systems to a $d$-dimensional subspace, which acts as a logical qu-$d$-it. This logical subspace has the key feature that, in a sense, the logical qu-$d$-it can be “accessed” from either its left or right qu-$d^{\prime \prime }$-it. This allows us to encode the $2$-local terms of $H$ as $1$-local terms acting on the qu-$d^{\prime }$-its of $H^{\prime }$. The rough idea behind the logical subspace is to treat the $(d^{\prime \prime }\times 3\times d^{\prime \prime })$ system as three bins capable of holding two types of balls (red and black) that are exchanged between the bins to move the information between the left and right qu-$d^{\prime \prime }$-it in each triple $(d^{\prime \prime }\times 3\times d^{\prime \prime })$. When one $d^{\prime \prime }$-bin is full, the other $d^{\prime \prime }$-bin must be empty and the total number $i$ of red balls encodes the basis state $|i/2⟩$ of the corresponding logical qudit (Figure 4.1 depicts the balls and bins). To encode a $d$-dimensional system, this requires $O(d)$ red balls and $O(d)$ black balls, so that $d^{\prime \prime }=\mathrm{\Theta }(d^2)$, and thus $d^{\prime }=\mathrm{\Theta }(d^4)$.

As previously described, our embedding can be seen as a weaker notion of simulation in the sense of [7, 13], in that formally our embedding is achieved via application of local isometries (i.e. local observables are mapped to local observables), followed by additional constraints on the logical space (Equations 19a and 19b). However, in contrast to [7, 13], we do not analyze the structure of higher energy spaces of $H^{\prime }$, and only show that $H^{\prime }$ preserves the nullspace of $H$ as well as its smallest non-zero eigenvalue, up to a linear factor (see Lemma 4.3), as this suffices for our purposes.

Although we have shown that qubit systems can support ${\mathrm{QMA}}_1$-hard problems, the frontier for characterizing the complexity transition of local Hamiltonian problems from low to high local dimension remains challenging. In our setting, in particular, the main open question is whether one can obtain ${\mathrm{QMA}}_1$-hardness even for $(2\times 3)-\mathrm{QSAT}$? This would complete the complexity characterization for $(d_A\times d_B)-\mathrm{QSAT}$, as recall $(2\times 2)-\mathrm{QSAT}$ (i.e. $2$-QSAT) is in P [8]. Getting this down to $(2\times 3)-\mathrm{QSAT}$ (even $(3\times 3)-\mathrm{QSAT}$ or $(2\times 4)-\mathrm{QSAT}$), however, appears difficult, requiring ideas beyond those introduced here.

As for the 1D line, the best hardness results for $2$-LH and $2$-QSAT are on $8$-dimensional [26] and $11$-dimensional [34] systems, respectively. Is 1D $2$-QSAT on qudits with ${\mathrm{QMA}}_1$-hard? We showed that 1D $(3\times d)-\mathrm{QSAT}$ is ${\mathrm{QMA}}_1$-hard, but due to our black-box approach we only get $d=76176$. So it seems likely that this $d$ can be improved significantly. Perhaps more interesting is the question whether 1D $(2\times d)-\mathrm{QSAT}$ is still ${\mathrm{QMA}}_1$-hard. We showed that even 1D $(2\times 4)$-dimensional constraints can support a unique globally entangled ground state (Theorem 1.5), but this construction alone does not embed a computation, and thus does not yield ${\mathrm{QMA}}_1$-hardness. Can this be bootstrapped to obtain ${\mathrm{QMA}}_1$-hardness for 1D $(2\times d)-\mathrm{QSAT}$? For 1D $2$-LH, the situation is even worse – on qubits, these systems can only be efficiently solved in the presence of a constant spectral gap [32]. In contrast, for inverse polynomial gap, and even with the promise of an NP witness (i.e. via Matrix Product State), the problem is NP-complete [41]. What is the complexity of 1D $2$-LH on qudits with ?

Section 2 gives formal definitions for ${\mathrm{QMA}}_1$, $(d_A\times d_B)-\mathrm{QSAT}$, and states the Geometric Lemma with various corollaries. Section 3 proves our main result, the ${\mathrm{QMA}}_1$-completeness of $(2\times 5)-\mathrm{QSAT}$. Section 4 proves the ${\mathrm{QMA}}_1$-completeness of $(3\times d)-\mathrm{QSAT}$ on a line. Section 5 gives the construction of the $(2\times 4)$-Hamiltonian on a line with entangled ground space.