Quantum SAT Problems with Finite Sets of Projectors Are Complete for a Plethora of Classes

Our main result establishes that the QSAT problem SLCT-QSAT is ${\mathrm{𝖡𝖰𝖯}}_1^{{𝒢}_8}$-complete. However, as the construction and analysis of this problem is contrived, we first show that the simpler and less optimized version of this problem, LCT-QSAT, is also complete for this class.

An interesting feature of this problem, and one that may be of independent interest, is that this problem makes clever use of the principle of monogamy of entanglement to strongly constrain the structure of input instances, facilitating the task of deciding whether they are frustration-free.⁵⁵5This construction is the most faithful to those considered by Meiburg in Ref. [32]. Unfortunately, this trick comes at a price of high qudit dimensionality. Our main result shows that by relaxing the constraint on the instance’s structure and instead study the instances more closely, we can obtain a similar problem with the same complexity but with reduced qudit dimensionality.

We refer to these problems by the same name as before, except that we now add a subindex to represent that the problem refers to the qubit version, e.g. SLCT-QSAT₂ is the QSAT problem that results from the reduction of SLCT-QSAT.

Finally, there is a notion of direct product “$\otimes$” and direct sum “$\oplus$” (Definitions 17 and 18) for both CSPs and QCSPs, which we use to show that there are six new QSAT problems that are complete for classes $\mathrm{𝖯𝖨}(A,B)$ and $\mathrm{𝖲𝗈𝖯𝖴}(A,B)$, where $A$ and $B$ are themselves complexity classes. $\mathrm{𝖯𝖨}(A,B)$ stands for the pairwise intersection of classes (Definition 11), and $\mathrm{𝖲𝗈𝖯𝖴}(A,B)$ for the star of pairwise union of classes (Definition 12). Roughly, these two classes correspond to the sets of problems that can be expressed as the intersection and union (respectively) of a problem in $A$ and a problem in $B$.⁶⁶6These classes are not to be confused with $A\cap B$ and $A\cup B$. $A\cap B$ corresponds to the set of problems that are in both $A$ and $B$, while $A\cup B$ corresponds to those that are in either $A$ or $B$. We show:

Finally, given that the QSAT problems in Corollaries 7 and 8 consist of finite sets of projects with $𝒪(1)$-local qubit clauses, and similarly $2$-SAT, $3$-SAT, Stoquastic 6-SAT, and $3$-QSAT (which are respectively in $𝖯$, $\mathrm{𝖭𝖯}$-complete, $\mathrm{𝖬𝖠}$-complete and ${\mathrm{𝖰𝖬𝖠}}_1^{{𝒢}_8}$-complete), our results imply that:

The goal of the construction is to design a QSAT problem that can encode the computation of any quantum circuit in ${\mathrm{𝖡𝖰𝖯}}_1$, while keeping all its instances solvable in quantum polynomial-time with perfect completeness and bounded soundness. We define the problem using projectors ${\mathrm{\Pi }}_{init}$, ${\mathrm{\Pi }}_{prop,U}$, and ${\mathrm{\Pi }}_{out}$ similar to $P_{init}$, $P_{prop,U}$, and $P_{out}$ defined in Equation 6.⁷⁷7The projectors $P_{start}$, $P_{clock}$, and $P_{stop}$ associated with the clock encoding remain unchanged and are integrated into the definitions of ${\mathrm{\Pi }}_{init}$, ${\mathrm{\Pi }}_{prop}$, and ${\mathrm{\Pi }}_{out}$. To see why our projectors must differ from the original ones, consider the QSAT problem built with $\{P_{init},P_{prop,U},P_{out},P_{start},P_{clock},P_{end}\}$. Showing that the problem is ${\mathrm{𝖡𝖰𝖯}}_1$-hard is straightforward, as we can encode the circuit that computes the answer to a ${\mathrm{𝖡𝖰𝖯}}_1$ problem in a similar way as that shown in Section A.3. This time however, all data particles in the instance should be initialized, instead of having free particles whose role is to accommodate a witness state. The difficulty lies in demonstrating that every instance generated with a polynomial number of these projectors can also be decided in ${\mathrm{𝖡𝖰𝖯}}_1$. There is a fundamental and a practical limitation for this:

• $\mathrm{■}$

  Instances which encode the computation of a ${\mathrm{𝖰𝖬𝖠}}_1$ problem, e.g. the instance in Figure 4 and the left instance in Figure 2(b), are valid inputs. This is problematic since it is unknown how to decide these instances in ${\mathrm{𝖡𝖰𝖯}}_1$ (and doing so would show that ${\mathrm{𝖡𝖰𝖯}}_1={\mathrm{𝖰𝖬𝖠}}_1$).

• $\mathrm{■}$

  Input instances may form intricate structures complicating the task of deciding if a satisfying state exists, e.g. the right instance in Figure 2(b).

We define the projectors ${\mathrm{\Pi }}_{init}$, ${\mathrm{\Pi }}_{prop}$, and ${\mathrm{\Pi }}_{out}$ to address these two difficulties (see Figure 2(c)). Importantly, these projectors do not significantly alter the proof that the problem is ${\mathrm{𝖡𝖰𝖯}}_1$-hard and can proceed as mentioned. Now, let us briefly discuss how we overcome both difficulties.

Instances like those in Figure 4, which have a proper structure and uninitialized data particles, are prototypical examples of $\mathrm{𝖰𝖬𝖠}$ instances. These “free” particles give one the freedom to guess if there exists a state they can be in such that the instance can be satisfied (or equivalently be provided with such a state which we verify). To address this issue, we remove the need to guess a satisfying state by introducing a new undefined basis state $|\mathrm{?}⟩$ (making the data particles 3-dimensional), such that setting the free data particles to this state always results in a satisfiable instance. More specifically, we achieve this by defining ${\mathrm{\Pi }}_{prop,U}$ so that if any data particle in the clause is in state $|\mathrm{?}⟩$, the clause is satisfied without needing to apply the associated unitary.⁸⁸8Although the data particles are $3$-dimensional and the unitaries are gates from a set designed to act on qubits, these cause no conflicts as the gates will never act on undefined data particles. Then, for these instances, the satisfying state is given by a truncated version of the history state (without a witness) since the computation is no longer required to elapse past the first ${\mathrm{\Pi }}_{prop,U}$ clause acting on an undefined state. We say the instance is now “trivially satisfiable” as its structure alone suffices to determine its satisfiability.

To determine the satisfiability of intricate instances, the projectors are now also defined to leverage the principle of monogamy of entanglement. Each clock particle is equipped with two $2$-dimensional auxiliary subspaces $CA$ and $CB$ (making them $12$-dimensional) and the ${\mathrm{\Pi }}_{prop,U}$ clauses are then defined to require that the $CB$ subspace of the predecessor clock particle forms a $|{\mathrm{\Phi }}^{+}⟩$ Bell pair with the $CA$ subspace of its successor. Then, if a $CA$ or $CB$ subspace is required to form more than one Bell pair, the principle of monogamy of entanglement states that only one of these clauses can be satisfied, and so the instance is unsatisfiable. Therefore, instances that are not deemed unsatisfiable because of this reason must form one-dimensional chains with a unique “time” direction. Finally, to guarantee that ${\mathrm{\Pi }}_{init}$ and ${\mathrm{\Pi }}_{out}$ only act on the ends of the chain, these make use of a new endpoint particle consisting of a single two-dimensional space $EC$ and require that it also forms a Bell pair with either the $CA$ (for ${\mathrm{\Pi }}_{init}$) or $CB$ (for ${\mathrm{\Pi }}_{out}$) subspace of a clock particle. These modifications thus yield a $17$-dimensional local Hilbert space: a $3$-dimensional data subspace, plus a $2$-dimensional endpoint subspace, plus a $12$-dimensional clock subspace.

Although these modifications do not get rid off all difficulties, a comprehensive analysis of the resulting instances can be used to demonstrate that a hybrid algorithm can determine the satisfiability status of all input instances. Briefly, the classical part of the algorithm evaluates the structure of the clauses in the instance and concludes whether it is trivially unsatisfiable, trivially satisfiable, or is one requiring the assistance of a quantum subroutine. Trivially unsatisfiable instances are those whose clause arrangement imply one or several clauses cannot be simultaneously satisfied, like those that violate monogamy of entanglement. On the other hand, trivially satisfiable instances are those whose clauses do not create any conflicts but whose structure is simple enough that the satisfying state can be inferred, like those with a proper structure and uninitialized data particles. We show that the only type of instances that are not in either one of these cases, are those like Figure 2(a) which express the computation of a quantum circuit on initialized ancilla qubits. For these instances, the classical algorithm makes use of a quantum subroutine that executes the quantum circuit expressed by the instance, while simultaneously measuring the eigenvalues of relevant projectors. The measurement outcomes indicate whether the instance should be accepted or rejected.

This section argues that even by removing the projectors that demand successive clock (or endpoint) particles must be entangled with each other, the satisfiability of instances remains the same. Specifically, we argue that the propagation rules, the choice of clock encoding, and the requirement to maintain a consistent clock register state at all times suffice to show that any instance in which the clock particles are not arranged linearly and do not point in the same direction is unsatisfiable. Consequently, there is no longer a need for auxiliary subspaces or endpoint particles. Together, these results show that while the use of monogamy of entanglement in the construction does facilitate some proofs, it is not crucial for the construction. Removing these elements reduce the local dimension from $17$ down to $6$.

The main challenge in this construction stems from the weaker constraints that the ${\mathrm{\Pi }}_{init}$ and ${\mathrm{\Pi }}_{out}$ clauses set instead of the endpoint particles. In summary, instances with more than a single ${\mathrm{\Pi }}_{init}$/${\mathrm{\Pi }}_{out}$ pair may now be satisfiable. Part of the proof of this section requires showing that if such sub-instances are potentially satisfiable, they can be further separated into smaller linear instances, each with a single ${\mathrm{\Pi }}_{init}/{\mathrm{\Pi }}_{out}$ pair. Each of these smaller pieces is then satisfied by a history state, while the clauses connecting them together (arranged in any shape) can be satisfied trivially. For this reason, we have used the term semilinear in the name of the resulting problem.

The construction from Section 2.2 can be modified to generate a ${\mathrm{𝖰𝖢𝖬𝖠}}_1^{{𝒢}_8}$-complete problem. Moreover, since ${\mathrm{𝖰𝖢𝖬𝖠}}_1^{{𝒢}_8}=\mathrm{𝖰𝖢𝖬𝖠}$ [27], this results in a $\mathrm{𝖰𝖢𝖬𝖠}$-complete problem. Although there are already many problems known to be complete for this class [19, 42, 21, 24, 40], none of them are strong QCSPs.⁹⁹9While Ref. [40] also defines a $\mathrm{𝖰𝖢𝖬𝖠}$-complete QSAT problem, it requires additional promise conditions.

In Section 2.1, we argued that the unconstrained or “free” logical qudits of an instance allowed one to guess what state of these qudits (the witness state) might satisfy the instance. This freedom made the problem more difficult and thus not likely contained in ${\mathrm{𝖡𝖰𝖯}}_1$. For this reason, we introduced the undefined state $|\mathrm{?}⟩$, which simplified these instances and made them decidable in ${\mathrm{𝖡𝖰𝖯}}_1$. In this construction, we seek to construct a problem that sits in between these two classes so it is $\mathrm{𝖰𝖢𝖬𝖠}$-complete. To accomplish this, we desire to have “free” logical qudits to accommodate a witness state that helps verify whether the instance is satisfiable, but have some sort of constraint to demand that the state is classical.¹⁰¹⁰10We continue using the undefined state for logical qudits whose initial state is not constrained so the difficulty of the problem does not become $\mathrm{𝖰𝖬𝖠}$.

In practice, creating these constraints is challenging since any superposition of two satisfying states will also satisfy the clause. Instead, we set the constraints such that if there exists a quantum witness state that is part of a satisfying state, there is also a classical witness state. Loosely, we accomplish this by defining new witness qudits and create a new constraint ${\mathrm{\Pi }}_{\mathrm{𝑖𝑛𝑖𝑡}}^{|00,11⟩}$ that connects a witness qudit with a logical one, and require that they are both either $|00⟩$, $|11⟩$, or in a superposition of the two.¹¹¹¹11The local Hilbert space is then $8$-dimensional, as it composed of a 3-dimensional data subspace, a 3-dimensional clock subspace, and a 2-dimensional witness subspace. In this way, the two qudits are partially “free” as there is some freedom to their state, yet posses some desired structure. Importantly, we ensure that the witness qudits do not form part of the computation after this initial point.

To see why this leads to the desired effect, consider the toy instance of Figure 3 and suppose there exists a state $|{\psi }_{\text{wit}}⟩$ of the four “free” qudits that leads to a satisfying state. Observe that to satisfy the ${\mathrm{\Pi }}_{\mathrm{𝑖𝑛𝑖𝑡}}^{|00,11⟩}$ clauses, this state must be of the form $|{\psi }_{\text{wit}}⟩={({\alpha }_{00}|0000⟩+{\alpha }_{01}|0011⟩+{\alpha }_{10}|1100⟩+{\alpha }_{11}|1111⟩)}_{L_1,W_1,L_2,W_2}$ with ${\sum }_{b\in {\{0,1\}}^2}{|{\alpha }_b|}^2=1$, which we can rewrite in a more convenient form as $|{\psi }_{\text{wit}}⟩={\sum }_{b\in {\{0,1\}}^2}{\alpha }_b{|b⟩}_L\otimes {|b⟩}_W$. Then, a state that satisfies all clauses of the instance is the history state

where $|{\xi }_b^t⟩:=U_t\mathrm{\dots }{U}_0|00⟩\otimes {|b⟩}_L$. Now, let us argue that there is also a classical witness that leads to a satisfying history state. First, observe that any basis state ${|b⟩}_L\otimes {|b⟩}_W$ with $|{\alpha }_b|>0$ from the decomposition of the witness satisfies the ${\mathrm{\Pi }}_{\mathrm{𝑖𝑛𝑖𝑡}}^{|00,11⟩}$ clauses. Consequently, the history state above but with initial state $|00⟩\otimes {|b⟩}_L\otimes {|b⟩}_W$ satisfies the ${\mathrm{\Pi }}_{\mathrm{𝑖𝑛𝑖𝑡}}^{|0⟩}$, ${\mathrm{\Pi }}_{\mathrm{𝑖𝑛𝑖𝑡}}^{|00,11⟩}$, and ${\mathrm{\Pi }}_{prop}$ clauses of the instance. Finally, to show that this state also satisfies the ${\mathrm{\Pi }}_{out}$ clause, recall that this clause is satisfied if at time $t=4$, the probability that the second qubit yields outcome “1” when measured is 1. As shown in Equation 3, this probability can be written as

where ${\mathrm{\Pi }}^{(1)}:=|1⟩{⟨1|}_2\otimes I_{rest}$, and in the last equality we observed that $⟨b^{\prime }|b⟩={\delta }_{b,b^{\prime }}$. Then, by the assumption that the instance is satisfiable, it must be that $⟨{\xi }_b^4|{\mathrm{\Pi }}^{(1)}|{\xi }_b^4⟩=1$ for all basis states $|b⟩$ with $|{\alpha }_b|>0$. This can also be understood as the probability that at the end of the circuit, the second qubit yields outcome “1” when the witness is the basis state $|b⟩\otimes |b⟩$. Therefore, the history state of Equation 1 with classical witness $|{\psi }_{\text{wit}}⟩={|b⟩}_L\otimes {|b⟩}_W$ also satisfies all clauses of the instance.

The remaining parts of the proof require showing that all new possible qudit connections with new ${\mathrm{\Pi }}_{\mathrm{𝑖𝑛𝑖𝑡}}^{|00,11⟩}$ clause can still be handled, as well as demonstrate perfect completeness and bounded soundness of the hybrid algorithm. For the latter, the majority of the arguments from the ${\mathrm{𝖡𝖰𝖯}}_1$ construction also directly apply here.

In Section 2.1, we mentioned that the satisfiability of some instances is decided through a quantum circuit. In particular, this circuit was used to verify the satisfiability of the simultaneous ${\mathrm{\Pi }}_{prop}$ clauses and final ${\mathrm{\Pi }}_{out}$ clauses. For the latter, the circuit executed the quantum circuit $U_T\mathrm{\dots }{U}_1$ on input ${|0⟩}^{\otimes q}$, measured some of the qubits, and accepted or rejected depending on the measurement outcomes. Intuitively, to generate the $\mathrm{𝖼𝗈𝖱𝖯}$-complete problem, we would like to replace the universal quantum circuit by a universal classical reversible circuit $R=R_T\mathrm{\dots }{R}_1$ (reversibility is needed since the best potentially satisfying state is still a quantum history state) and introduce randomness into the instance by initializing $p$ ancilla qubits to $|+⟩$. Then, for these new sub-instances, we could analogously verify the ${\mathrm{\Pi }}_{out}$ clauses by sampling a bitstring $b\in {\{0,1\}}^p$, evaluating the circuit $R$ on input $(0^q,b)$ and deciding on its satisfiability based on the final state of the bits. While this idea is close to the actual construction, for reasons mentioned in the full version of the text, it is not sufficient to decide all instances.

For the construction to work, we also incorporate elements of the $\mathrm{𝖰𝖢𝖬𝖠}$ problem from the previous section. Namely, we modify the ${\mathrm{\Pi }}_{\mathrm{𝑖𝑛𝑖𝑡}}^{|00,11⟩}$ clause so it initializes both a witness (now referred to as auxiliary qudit as we remove the freedom) and a logical qudit to the maximally entangled state $|{\mathrm{\Phi }}^{+}⟩$. This new clause is denoted ${\mathrm{\Pi }}_{\mathrm{𝑖𝑛𝑖𝑡}}^{|{\mathrm{\Phi }}^{+}⟩}$.

Again using the toy example of Figure 3 (replacing the ${\mathrm{\Pi }}_{\mathrm{𝑖𝑛𝑖𝑡}}^{|00,11⟩}$ clauses by ${\mathrm{\Pi }}_{\mathrm{𝑖𝑛𝑖𝑡}}^{|{\mathrm{\Phi }}^{+}⟩}$ clauses and the unitaries $U_i$ by reversible classical gates $R_i$), let us illustrate how this construction allows us to verify the satisfiability of ${\mathrm{\Pi }}_{out}$ clauses. If the instance is satisfiable, the satisfying state must be the history state

where in the second line we observed that ${|{\mathrm{\Phi }}^{+}⟩}^{\otimes p}=2^{-\frac{p}{2}}{\sum }_{b\in {\{0,1\}}^p}{|b⟩}_L\otimes {|b⟩}_{Aux}$ for any $p\in \mathbb{N}$, and defined $|{\xi }_b^t⟩:=R_t\mathrm{\dots }{R}_1|00⟩\otimes {|b⟩}_L$. The ${\mathrm{\Pi }}_{out}$ clause is satisfied if at time $t=4$, the probability that the second qubit yields outcome “1” when measured is $1$. This probability is given by

from where it is evident that if the instance is satisfiable, $⟨{\xi }_b^4|{\mathrm{\Pi }}^{(1)}|{\xi }_b^4⟩=1$ for all $b\in {\{0,1\}}^2$. Hence, it is possible to verify the ${\mathrm{\Pi }}_{out}$ clause by sampling one of the strings $b$, running circuit $R$ on input $(0^2,b)$, and measuring the state of the second qubit.

Another important consideration is that the classical reversible gate set must be chosen with care. Although not covered in this version of the paper, we usually desire that $𝒢$ is a gate set such that all gates in the set change the basis states upon application, and so $V({\mathrm{\Pi }}_i)$ of Equation 2 can be implemented perfectly with gates from this set. Here, only the first property is relevant. We choose $𝒢=\{X,(X\otimes X\otimes X)\text{Toffoli}\}$, which clearly satisfies this property and is also a universal gate set for reversible classical computation. As a consequence, the QSAT problem of this section has $5$-local clauses since the ${\mathrm{\Pi }}_{prop}$ clauses may use a Toffoli. This is the best locality we can achieve as it is also well known that any universal gate set for reversible quantum computation must include a $3$-bit gate.

In previous sections, we showed that there are QSAT problems acting on qudits that are complete ${\mathrm{𝖡𝖰𝖯}}_1^{{𝒢}_8}$, $\mathrm{𝖰𝖢𝖬𝖠}$, and $\mathrm{𝖼𝗈𝖱𝖯}$. Here, we refine these statements and show that there are QSAT problems on qubits (albeit with higher locality) that are also complete for these classes. To achieve this, we show that any QCSP on qudits can be reduced to another QSAT problem on qubits using little computational power. We note that this section, apart from some changes in the exposition, stems directly from Ref. [32].

At first glance, this statement may seem trivial as operations on qubits are universal for quantum computation, i.e. we can emulate a $d$-qudit with a $\lceil {\log }_2(d)\rceil$ qubits and carry out unitaries on those qubits. For our QSAT problems, it is true that any instance retains its satisfiability status when expressed in terms of qubits. However, it is not clear if all input instances generated with these new qubit clauses are contained within this class. For a successful reduction, we must have both.

For an even more explicit example, let us first represent the basis clock states using qubits as: $|r⟩:=|00⟩$, $|a⟩:=|01⟩$, and $|d⟩:=|10⟩$. The ${\mathrm{\Pi }}_{start}=|r⟩⟨r|$ clause (defined exactly as $P_{init}$ in Equation 7) can now be written as ${\mathrm{\Pi }}_{start}=|00⟩⟨00|+|11⟩⟨11|$, where the last term is to prevent the fourth basis state $|11⟩$, which did not exist before. The clause ${(|00⟩⟨00|+|11⟩⟨11|)}_{1,2}+{(|00⟩⟨00|+|11⟩⟨11|)}_{2,3}$ acting on three qubits is now valid and is satisfied by the state $|0_1{0}_2{1}_3⟩$. This state, however, presents some ambiguity: either we have $|r⟩$ on qubits 1 and 2, or $|a⟩$ on qubits 2 and 3. In general, decomposing all clauses into qubits and considering all input instances that may occur adds a significant level of complexity to the problem, making it difficult to determine if it remains in the same class. Moreover, we remark that this is not only particular to our QSAT problems, but in fact applies to all CSPs and QCSPs defined on qudits or non-Boolean variables! In general, the issue is that we cannot ensure that the new qubit clauses are applied to qubits in a consistent fashion based on its parent qudit problem. For example, a qubit clause might treat a particular qubit as “qubit 1” of a previous $d$-qudit, while another clause might refer to the same qubit as “qubit 2”. Moreover, the qubit clauses could also “mix and match”, combining “qubit 1” from one previous $d$-qudit with “qubit 2” from another $d$-qudit (as in the example with ${\mathrm{\Pi }}_{start}$). Overall, these lead to constraints that were unrealizable in the parent qudit problem.

Our main result of this section shows that with a more clever reduction than directly decomposing a $d$-qudit into $\lceil {\log }_2(d)\rceil$ qubits, we can guarantee that a satisfiable/unsatisfiable instance on qubits maps to one on qudits with the same satisfiability status. This is something that is not known to be possible classically! More formally, we show that

The main idea behind the proof is that in the quantum world, we can fix the issues mentioned above by again using monogamy of entanglement to bind together our constituent qubits into ordered, entangled larger systems. Ultimately, each clause in the resulting qubit problem incorporates new projectors that force a particular ordering of qubits, and any two clauses that try to “mix and match”, or use the same set of qubits but with different ordering, are necessarily frustrated.

If in Theorem 10 we do not require the reductions to be in ${\mathrm{𝖠𝖢}}^0$, and instead allow $𝖯$-reductions, a locality of $4\lceil {\log }_2(d)\rceil k$ suffices. This is used in Corollary 7.

There is a notion of direct sum (denoted by “$\oplus$”) and direct product (denoted by “$\otimes$”) on CSPs and QCSPs that allow us to define the remaining six complete problems. To be clear, these are operations on languages themselves, not on instances. For example, we can talk about the languages $\text{3-Colorable}\oplus \text{4-SAT}$ and $\text{3-Colorable}\otimes \text{4-SAT}$. Although this notion appears to be quite natural, we were unable to find many sources discussing such ideas – possibly because the classical theory is not as exciting, for reasons we also discuss. The relevant task here is to demonstrate that sum and product QCSPs inherit completeness properties from their constituents. In this way, we are able to construct QCSPs that are complete for $\mathrm{𝖯𝖨}$ and $\mathrm{𝖲𝗈𝖯𝖴}$ classes, defined as follows.

Definition 12 merits a brief explanation. For a pair of languages $L_1$ and $L_2$, what do the strings in the language $L:={(d{L}_1|d{L}_2)}^{\ast }$ look like? Given an input string like $d010011d101101d101001$, it will belong to $L$ if and only if each of the three bitstrings $\{010011,101101,101001\}$ belongs to either $L_1$ or $L_2$. If $C$ is a complexity class powerful enough to break apart the individual bitstrings from the $d$-delimited string, as well decide both $L_1$ and $L_2$, then $\mathrm{𝖲𝗈𝖯𝖴}({𝒞}_1,{𝒞}_2)\in C$.

We begin discussing that there are CSPs that are complete for these classes, and then extend this to the quantum setting since the latter follows almost identically.

As mentioned previously, while the notion of product and sum of constraint problems seems natural, classical constraint problems do not seem to offer such a rich theory. This is due to the fact that most classes with complete CSPs are contained within each other. Indeed, Allender et al.’s refinement of Schaefer’s dichotomy theorem states that all Boolean CSPs are either in $\mathrm{𝖼𝗈}$-$\mathrm{𝖭𝖫𝖮𝖦𝖳𝖨𝖬𝖤}$; or are complete for $𝖫$, $\mathrm{𝖭𝖫}$, $\oplus 𝖫$, $𝖯$ or $\mathrm{𝖭𝖯}$ under $A{C}^0$ reductions [3]. With the exception of $\mathrm{𝖭𝖫}$ and $\oplus 𝖫$, all possible pairs from this list have an obvious containment relation, so the only nontrivial consequence would be that there exists a CSP, on a domain of size four, that is $\mathrm{𝖯𝖨}(\oplus 𝖫,\mathrm{𝖭𝖫})$-complete under $A{C}^0$ reductions. However, under the more common $P$-reductions, the complexity of these problems becomes either in $𝖯$ or $\mathrm{𝖭𝖯}$-complete.¹³¹³13The same is true for CSPs defined on qudits [43]. Then, since $𝖯\subseteq \mathrm{𝖭𝖯}$ and these classes meet all properties discussed in Lemma 22, it follows that products or sums of these problems result in complexity classes that are trivially equal to $\mathrm{𝖭𝖯}$. For example, 2-SAT $\oplus$ 3-SAT and 2-SAT $\otimes$ 3-SAT are complete problems for $\mathrm{𝖯𝖨}(𝖯,\mathrm{𝖭𝖯})$ and $\mathrm{𝖲𝗈𝖯𝖴}(𝖯,\mathrm{𝖭𝖯})$, but these classes are trivially equal to $\mathrm{𝖭𝖯}$.

This is no longer the case in this work. The seven classes we have discussed so far which have complete CSPs are $𝖯$, $\mathrm{𝖼𝗈𝖱𝖯}$, ${\mathrm{𝖡𝖰𝖯}}_1$, $\mathrm{𝖭𝖯}$, $\mathrm{𝖰𝖢𝖬𝖠}$, and ${\mathrm{𝖰𝖬𝖠}}_1$. Importantly, these all have the closure properties discussed in this section so far: union, intersection, logspace reductions, and delimited concatenation; and they all include the trivial problems ALL and NONE. Among these classes, most pairs $\{A,B\}$ have $A\subseteq B$, in which case $\mathrm{𝖯𝖨}(A,B)=\mathrm{𝖲𝗈𝖯𝖴}(A,B)=B$. However, there are three pairs that are not known to contain each other, these are: $\mathrm{𝖼𝗈𝖱𝖯}\stackrel{?}{\subseteq }\mathrm{𝖭𝖯}$, ${\mathrm{𝖡𝖰𝖯}}_1\stackrel{?}{\subseteq }\mathrm{𝖭𝖯}$, and ${\mathrm{𝖡𝖰𝖯}}_1\stackrel{?}{\subseteq }\mathrm{𝖬𝖠}$. Each of these pairs leads to two new classes $\mathrm{𝖯𝖨}(A,B)$ and $\mathrm{𝖲𝗈𝖯𝖴}(A,B)$, that are not obviously equal to some other known class. Together, we obtain six more complexity classes with complete QCSPs.