The Quantum Smooth Label Cover Problem Is Undecidable

A two-player one referee game is akin to a two-prover interactive proof system. Here, non-communicating players (or provers) interact with a referee (or verifier) through a single round of question and answer. The players are cooperating and their goal is to win the game by satisfying the rule predicate, a condition checked by the referee. In the quantum setting the players have access to the additional resource of entangled quantum states, and the ability to measure them locally between receiving their questions and returning their answers.

An instance of smooth label cover consists of a bipartite graph $G$ with partitioned vertices $U\cup V$, edges $E$, and an alphabet of size $n$. Given an instance, the goal is to assign labels to each of the vertices, maximizing the number of valid assignments; the validity of a label assignment is determined by constraints imposed by the edges of the graph. Smoothness is a certain global-to-local property on the constraints, which ensures the assignments satisfying any near-optimal number of constraints have specific local features. Each smooth label cover problem is an instance of a 2-ary constraint satisfaction problem ($2$-$\mathrm{CSP}$), with degree $n$ variables corresponding to the vertices, and constraints imposed by edges.

This smooth label cover game can be played as a constraint system nonlocal game ${𝒢}_{\mathrm{SLC}(n)}$. In the game, the referee samples a constraint $e_{uv}$ according to some distribution, and sends one variable $u$ to the first player, and the other variable $v$ to the second player. The first player responds with an assignment to variable $u$, and the second player with an assignment to variable $v$. Finally, the referee checks that the assignments to $u$ and $v$ satisfy the constraint $e_{uv}$. The completeness of the game is clear: if they have an assignment which satisfies a large number of constraints, then they are likely to win the game. The notion of soundness is similar: players with a good strategy will be able to construct a good assignment.

The optimal classical value of the smooth label cover game ${𝒢}_{\mathrm{SLC}(n)}$, denoted by ${\omega }_c({𝒢}_{\mathrm{SLC}(n)})$, will be directly related to the optimal fraction of satisfied constraints in the smooth label cover instance. The classical hardness of the smooth label cover problem is the statement that for all , there is an $n$ large enough, such that the following decision problem is $\mathrm{NP}$-hard: given ${𝒢}_{\mathrm{SLC}(n)}$ decide if ${\omega }_c({𝒢}_{\mathrm{SLC}(n)})=1$ or , promised that one holds³³3Unlike for unique label cover, smooth label cover with perfect completeness is not necessarily easy.. By allowing quantum strategies for the corresponding 2-CSP game, the quantum smooth label cover problem is the following: given ${𝒢}_{\mathrm{SLC}(n)}$ and , decide if ${\omega }_q({𝒢}_{\mathrm{SLC}(n)})=1$ or , promised that one holds. Where the quantum value ${\omega }_q({𝒢}_{\mathrm{SLC}(n)})$ is the supremum over all quantum strategies for ${𝒢}_{\mathrm{SLC}(n)}$. We establish the following result.

With this result, it seems as though quantum unique label cover problem is the most strange, effectively switching from hard to easy. See Theorem 6 for the formal statement. One can take the perspective that the ${\mathrm{MIP}}^{\ast }=\mathrm{RE}$ result is a quantum version of the classical PCP theorem⁴⁴4Although, there are some good reasons to not compare these statements directly, see [33]. for succinctly presented constraint satisfaction problems (CSPs). Unlike with the classical $\mathrm{MIP}=\mathrm{NEXP}$ result [4], computable reductions between problems in $\mathrm{RE}$ are not sensitive to whether we have a compact presentation of the CSP. In other words, if a succinctly presented CSP is undecidable, then so is the non-succinct version of the problem. In this sense, the ${\mathrm{MIP}}^{\ast }=\mathrm{RE}$ result of [20] puts significant limitations on the existence of any approximation algorithms for the quantum value of nonlocal games. Still, understanding which games admit approximation algorithms for the quantum value is a very interesting problem. Here, little is known compared to the classical case, beyond the setting of XOR games [7, 39, 5], and some other partial results [9].

Mousavi and Spirig point out that the ${\mathrm{MIP}}^{\ast }=\mathrm{RE}$ result implies that the quantum oracularized label cover problem is also $\mathrm{RE}$-hard. Oracularizable quantum strategies are a restricted class of quantum synchronous strategies which have convenient properties in the context of reductions between ${\mathrm{MIP}}^{\ast }$ protocols for CSPs. In particular, they are necessary for the answer reduction portion of the ${\mathrm{MIP}}^{\ast }=\mathrm{RE}$ proof [20, 13]. This led Mousavi and Spirig to provide an alternative quantum unique games conjecture, based on the quantum oracularized value, for which the approximation algorithm of [22] does not readily apply. Assuming their conjecture, they established a hardness of approximation result for the quantum oracularized value for families of CSPs from $\text{2-}\mathrm{LIN}$ and $\mathrm{MAXCUT}$ which resemble those established in the classical case under the unique games conjecture by Khot and others [24, 25].

Our results for quantum smooth label cover aligns with their quantum unique games conjecture. Moreover, we were able to extend our result to the oracularized setting. Accordingly, our second main result extends the hardness of quantum smooth label cover to the quantum oracularized value. In other words, we show that the problem of deciding if ${\omega }_{qo}({𝒢}_{\mathrm{SLC}(n)})=1$ or , is RE-hard, where ${\omega }_{qo}({𝒢}_{\mathrm{SLC}(n)})$ is the supremum over all quantum oracularizable strategies. For concreteness, one can consider the smooth label cover game, where one of the players must reply with an assignment to both vertices $u$ and $v$, and the other player obtains only one of $u$ or $v$ chosen at random by the verifier, and replies with an assignment to that vertex.

The formal result can be found in Corollary 13. Oracularizable quantum strategies for 2-CSPs, like smooth label cover, are more akin to quantum strategies for CSPs where each constraint contains more than two variables. In two-player protocols for CSPs where the constraints contain more than two variables, at least one of the players must be forced to respond with an assignments to multiple variables, otherwise the protocol lacks soundness. As such, that player’s measurement operators for the variables in that constraint must commute. On the other hand, in a non-oracularizable strategy for a $2$-CSP protocol, each player is sent only one variable, and yet the protocol is still sound. Unlike before, the player’s measurements for these variables need not commute, since a single player only measures one variable. Such sound noncommutative quantum protocols only exist for 2-CSPs! Making this constraint-noncommutativity a behaviour unique to entangled 2-CSP protocols.

In an oracularizable strategy for a $2$-CSP game, measurements for the variables in each constraint always commute. This is similar to the quantum strategies for CSP protocols with constraints involving more than 2 variables, such as the constraint-constraint and constraint-variable games, see for example [6, 19, 3, 34, 8]. The existence of non-oracularizable strategies for 2-CSPs is one of the reasons why the authors of [32] suggest a unique games conjecture based on the hardness of the quantum oracularized value, as it fits with the general theory of entangled CSP protocols of higher arity. In particular, the entangled strategies produced by efficient procedure of [22] are not oracularizable and therefore the RE-hardness of the quantum oracularized label cover problem is entirely plausible.

Several of the proof ideas in this work are inspired by classical reductions between decision problems. Establishing completeness of a classical reduction in the quantum case is often more straightforward, and it is establishing the quantum soundness which often presents a new challenge. To overcome this obstacle in many cases, we make use of the powerful algebraic formalism for handling soundness arguments for ${\mathrm{MIP}}^{\ast }$ protocols for CSPs that was recently introduced in [31] and expanded on in [8]. The weighted algebra formalism examines how reductions change the quantum synchronous value. One of the main observations used throughout this work (as well as, for instance [31, 8, 16]) is that we can reduce questions about the hardness of the quantum value to the hardness of the quantum synchronous value.

To prove our first main result, we give a reduction from the halting problem to the quantum smooth label cover problem. Our starting point is the $\mathrm{RE}$-hardness for $3\mathrm{S}\mathrm{A}{\mathrm{T}}^{\ast }$ established by Culf and Mastel [8], where $3\mathrm{S}\mathrm{A}{\mathrm{T}}^{\ast }$ denotes the ${\mathrm{MIP}}^{\ast }$ protocol for $3\mathrm{S}\mathrm{A}\mathrm{T}$. Next, we exhibit a reduction from this RE-hard problem to $3\mathrm{S}\mathrm{A}\mathrm{T}{5}^{\ast }$, the corresponding ${\mathrm{MIP}}^{\ast }$ protocol where every variable appears in (exactly) $5$ constraints. From here, we employ the classical construction of Guruswami, Raghavendra, Saket, and Wu [18], building on the work of Khot [23], to obtain a smooth label cover instance. One of our technical contributions is ensuring the completeness and soundness of the Guruswami, Raghavendra, Saket, and Wu construction in the quantum case. This involves considering a variant of the $(J,R)$-dummy variable game (see Definition 7) where the questions and answers are ordered, since completeness of parallel repetition in the quantum setting depends on the players knowing which round of the repeated game they are playing. However, the primary technical contribution of this work is establishing the reduction from $3\mathrm{S}\mathrm{A}{\mathrm{T}}^{\ast }$ to $3\mathrm{S}\mathrm{A}\mathrm{T}{5}^{\ast }$.

Our approach is inspired by the classical reductions from $3\mathrm{S}\mathrm{A}\mathrm{T}$ to $3\mathrm{S}\mathrm{A}\mathrm{T}B$ (where every variable appears in $B$ constraints for some constant $B$) by Papadimitriou and Yannakakis [35] and Arora et al. [1], and then from $3\mathrm{S}\mathrm{A}\mathrm{T}B$ to $3\mathrm{S}\mathrm{A}\mathrm{T}5$ by Feige [14]. This involves modifying the $3\mathrm{S}\mathrm{A}\mathrm{T}$ system by first labelling each variable by its constraint and then adding equality constraints between these labelled variables. One can think of the labelled variables and equality constraints between them as the vertices and edges of a graph. Unfortunately, this reduction does not decrease the degree of the $3\mathrm{S}\mathrm{A}\mathrm{T}$ instance. To overcome this issue, as in the classical reductions, we modify the construction by adding equality constraints only along the edges of an expander graph. Unlike in the classical setting, analysing the soundness of the expander construction is less straightforward, however we are able to prove that it remains sound in the quantum setting. The key observation is that we can employ a nice result from [21] (Lemma 22) to obtain a constant soundness drop-off in the quantum case.

The soundness proof of the expander graph construction hinges on a certain uniformity assumption for the question distribution of the initial $3\mathrm{S}\mathrm{A}{\mathrm{T}}^{\ast }$ protocol. Hence, to complete the proof of $\mathrm{RE}$-hardness for $3\mathrm{S}\mathrm{A}\mathrm{T}{5}^{\ast }$, we need to establish RE-hardness for such uniform $3\mathrm{S}\mathrm{A}{\mathrm{T}}^{\ast }$ protocols. Unfortunately, this is not clear a priori via polynomial-time reductions. Nevertheless, we modify the halting problem so that the required uniformity condition is baked in. This modified halting problem is $\mathrm{RE}$-hard by an exponential-time reduction from the halting problem. Then, the $\mathrm{RE}$-hardness of uniform $3\mathrm{S}\mathrm{A}{\mathrm{T}}^{\ast }$ follows by a polynomial-time reduction from the modified halting problem.

Our second main result, establishing undecidability in the oracularized case, follows by a modification of the $3\mathrm{S}\mathrm{A}\mathrm{T}{5}^{\ast }$ protocol described above. This modification results in a $3\mathrm{S}\mathrm{A}\mathrm{T}{10}^{\ast }$ protocol, in which the quantum assignments are what we call 2-oracularizable. That is, pairs of observables corresponding to variables, say $x$ and $y$, will commute not only if they are in the same constraint, but also whenever another variable $z$ appears in separate constraints with each of $x$ and $y$, respectively. The 2-oracularizable property of the quantum assignments to the $3\mathrm{S}\mathrm{A}\mathrm{T}{10}^{\ast }$ protocol ensures that in the construction of the smooth label cover game ${𝒢}_{\mathrm{SLC}(n)}$, the quantum strategies will be fully oracularizable. The construction is such that quantum assignments to the $3\mathrm{S}\mathrm{A}\mathrm{T}{5}^{\ast }$ protocol will give assignments to the $3\mathrm{S}\mathrm{A}\mathrm{T}{10}^{\ast }$ protocols. Lastly, the soundness of the construction follows by observing that the entire modification is an instance of a “constraint subdivision” transformation, and therefore quantum soundness follows by a result of [8], using the weighted algebra formalism.

A two-player nonlocal game $𝒢=(I,{\{O_i\}}_{i\in I},\pi ,V)$ consists of a finite set of questions $I$, a collection of finite answer sets ${\{O_i\}}_{i\in I}$, a probability distribution $\pi$ on $I\times I$, and a family of functions $V(\cdot ,\cdot |i,j):O_i\times O_j\to \{0,1\}$ for $(i,j)\in I\times I$. In the game, the players, often called Alice and Bob, receive questions $i$ and $j$, respectively, from $I$ with probability $\pi (i,j)$, and, without communicating with one another, reply with answers $a\in O_i$ and $b\in O_j$, respectively. They win if $V(a,b|i,j)=1$ and lose otherwise. We have assumed without loss of generality that the players’ question and answer sets are the same.

Although they cannot communicate during the game, the players can coordinate a strategy beforehand. The players’ strategy in a nonlocal game is described by the probability distributions $p:=p(a,b|i,j)$ of their answers conditioned on the question pair they receive. Such distributions are known as correlations for the game $𝒢$. Depending on the resources available to the players, they can only employ certain correlations. A correlation $p$ is quantum if there are:

1. (i)

   finite-dimensional Hilbert spaces ${\mathscr{H}}_A$ and ${\mathscr{H}}_B$,

2. (ii)

   a projective measurement ${\{M_a^i\}}_{a\in O_i}$ on ${\mathscr{H}}_A$ for every $i\in I$,

3. (iii)

   a projective measurement ${\{N_a^j\}}_{a\in O_j}$ on ${\mathscr{H}}_B$ for every $j\in I$, and

4. (iv)

   a state $|v⟩\in {\mathscr{H}}_A\otimes {\mathscr{H}}_B$

such that $p(a,b|i,j)=⟨v|M_a^i\otimes N_b^j|v⟩$ for all $i,j\in I$, $a\in O_i$, and $b\in O_j$. The collection $({\mathscr{H}}_A,{\mathscr{H}}_B,\{M_a^i\},\{N_a^j\},|v⟩)$ is called a quantum strategy. Quantum strategies capture the scenario where the players share some bipartite quantum state and sample their answers via measurements of that state. If the players instead only have access to classical resources such as shared randomness, their correlation and strategy are called classical.

The winning probability of a correlation $p$ in a nonlocal game $𝒢=(I,\{O_i\},\pi ,V)$ is

Sometimes we denote a strategy by $𝒮$, and write $\omega (𝒢;S)$ for the winning probability. Let $C_q$ be the set of quantum correlations, then the quantum value of $𝒢$ is ${\omega }_q(𝒢):={sup}_{p\in C_q}(𝒢;p)$.

A nonlocal game $𝒢=(I,\{O_i\},\pi ,V)$ is synchronous if $V(a,b|i,i)=0$ for all $i\in I$ and $a\ne b\in O_i$. A correlation $p$ is synchronous if $p(a,b|i,i)=0$ for all $i\in I$ and $a\ne b\in O_i$. The set of synchronous classical and quantum correlations are denoted $C_c^s$ and $C_q^s$, respectively. We define the synchronous quantum value ${\omega }_q^s$ analogously to ${\omega }_q$ by replacing $C_q$ with $C_q^s$. If $p$ is a synchronous quantum correlation, then there is a single projective measurement ${\{M_a^i\}}_{a\in O_i}$ for each $i\in I$ on a single finite dimensional Hilbert space $\mathscr{H}$, and the state $|v⟩$ is tracial, in the sense that $⟨v|\alpha \beta |v⟩=⟨v|\beta \alpha |v⟩$ for all $\alpha$ and $\beta$ in the $\ast$-algebra generated by the operators $M_a^i$, $i\in I$, $a\in O_i$. Moreover, the correlation can be written as $p(a,b|i,j)=⟨v|M_a^i{M}_b^j|v⟩$ for all $i,j\in I$, $a\in O_i$, and $b\in O_j$. The collection $(\mathscr{H},\{M_a^i\},|v⟩)$ is called a synchronous quantum strategy. A synchronous strategy is called oracularizable if $M_a^i{M}_b^j=M_b^j{M}_a^i$ for all $i,j\in I$, $a\in O_i$, and $b\in O_j$ with $\pi (i,j)>0$. Similarly, we call a correlation oracularizable if it admits an oracularizable strategy. Let $C_{qo}$ be the set of oracularizable quantum correlations, then the quantum oracularizable value of $𝒢$ is ${\omega }_{qo}(𝒢):={sup}_{p\in C_{qo}}(𝒢;p)$. In some previous work on 2-CSP games, namely [32], the quantum synchronous value of a synchronous game has been called the non-commutative value, and the oracularized synchronous quantum value has been called the quantum value. Every quantum correlation that is approximately synchronous, in the sense that $p(a,b|i,i)$ $\approx 0$ for all $i\in I$ and $a\ne b\in O_i$, is close to an exactly synchronous quantum correlation [38, 28, 30]. Because of this, we work mainly with the synchronous value.

A constraint system (CS) over an alphabet $\mathrm{\Sigma }$ consists of a set of variables $𝒳$ and a collection of constraints ${\{{𝒞}_i\}}_{i=1}^n$, where ${𝒞}_i=({𝒰}_i,{ℛ}_i)$ for $1\le i\le n$. Each ${𝒰}_i$, called a context, is an ordered subset of $𝒳$, and the relations ${ℛ}_i$ are nonempty subsets of ${\mathrm{\Sigma }}^{{𝒰}_i}$. When $|{𝒰}_i|=k$ we say that $𝒞$ is a $k$-ary constraint, and we write $k$-CS to denote a CS where each constraint has arity $k$. An assignment to ${𝒰}_i$ is an element of ${\mathrm{\Sigma }}^{{𝒰}_i}$. Given a constraint ${𝒞}_i$ the satisfying assignments are the elements of ${ℛ}_i$, and assignments not in ${ℛ}_i$ are unsatisfying assignments. In the special case where the alphabet $\mathrm{\Sigma }$ has size two, we say $S$ is a boolean constraint system (BCS). A constraint language is the family of constraint systems where each constraint comes from a restricted set of relations. An important example of a constraint language is $3\mathrm{S}\mathrm{A}\mathrm{T}$, where each context contains three variables and each constraint is a disjunction of three literals. Another example we mention here is the language of fixed degree $3\mathrm{S}\mathrm{A}\mathrm{T}$, which we denote by $3\mathrm{S}\mathrm{A}\mathrm{T}k$ for $k>0$, where each variable appears in exactly $k$ contexts.

A constraint satisfaction problem with completeness $c$ and soundness $s$, for , is a promise problem:

Similarly, a succinct constraint satisfaction problem with completeness $c$ and soundness $s$, for , is a promise problem:

For convenience later, we write $\mathrm{SuccinctCSP}{(3\mathrm{S}\mathrm{A}\mathrm{T})}_{c,s}$ and $\mathrm{CSP}{(3\mathrm{S}\mathrm{A}\mathrm{T})}_{c,s}$ for the succinct (and non-succinct) constraint satisfaction problems where each CS is a $3\mathrm{S}\mathrm{A}\mathrm{T}$ instance. Additionally, it will be convenient to make use of the following graph associated with a CS, which exhibits which variables appear in which constraints in a constraint system.

Given a distribution $\mu :[n]\to {ℝ}_{\ge 0}$ and a CS $S$, the constraint-variable CS game is the nonlocal game $𝒢(S,\mu )=([n]\cup 𝒳,{\{{𝒪}_i\}}_{i\in [n]\cup 𝒳},\pi ,V)$, where $O_i={\mathrm{\Sigma }}^{{𝒰}_i}$ when $i\in [n]$ and $O_i=\mathrm{\Sigma }$ otherwise (i.e. $i\in 𝒳)$, $\pi (i,x)=\mu (i)/|{𝒰}_i|$ for $x\in {𝒰}_i$ and is 0 on other inputs, and $V(\varphi ,a|i,x)=1$ if $\varphi \in {𝒞}_i$ and $\varphi (x)=a$ and is $0$ otherwise. Note that although the players have different question sets, the game can be symmetrized without changing the synchronous winning probability. In this game, one player receives $i\in [n]$ sampled from $\mu$ and the other receives a uniformly random variable $x\in {𝒰}_i$. To win, the first player must answer with a satisfying assignment $\varphi \in {𝒞}_i$ and the second must answer $a\in \mathrm{\Sigma }$ such that $a=\varphi (x)$. When $S$ is boolean, we call that $𝒢(S,\pi )$ a BCS game.

The constraint-variable game is not naturally synchronous. To make it synchronous, the verifier must randomly choose which player to ask the constraint question and which player to ask the variable question, and also ask consistency check questions with some constant probability. This transformation preserves constant completeness-soundness gaps and guarantees that the players can win near-optimally with synchronous strategies due to Theorem 0.1 of [30], so we do not need to worry about it in practice.

Let $S$ be a $2$-CS over an alphabet $\mathrm{\Sigma }$ and ${\pi }^{\prime }$ be a probability distribution on $[m]$, define the $\mathrm{𝟐}$-CS game $G_a(S,{\pi }^{\prime })$ as the nonlocal game $(𝒳,\mathrm{\Sigma },{\nu }_a,V_a)$, where ${\nu }_a(x,y)=\frac{{\pi }^{\prime }(i)}{2}$ if ${𝒰}_i=\{x,y\}$ and $0$ otherwise, and $V_a(a,b|x,y)=1$ iff there exists $\varphi \in {ℛ}_i$ such that $\varphi (x)=a$ and $\varphi (y)=b$. In this game, the referee samples $i$ from ${\pi }^{\prime }$, and then asks each of the players one variable from the constraint. Each player responds with an assignment to the variable she received. They win if they have answered a satisfying assignment.

If the players are classical, then their strategy for either type of CS game can be taken to be deterministic. The responses of the player who received the variable question constitute an assignment to the constraint system. Similarly, the variable player’s measurements in a synchronous strategy constitute a quantum (synchronous) assignment to the CS. If the corresponding strategy is oracularizable, then the assignment is called an oracularizable assignment. One can reason about reductions between classical strategies for CS games by working with global assignments. When the players have access to quantum resources, we can get a similar simplification when thinking about synchronous strategies using the weighted algebra formalism developed in [31] and [8].

For a set of variables $𝒰$, let $ℂ{\mathbb{Z}}_k^{\ast 𝒰}$ be the free algebra generated by order-$k$ unitaries labelled by the elements $x\in 𝒰$, and let $ℂ{\mathbb{Z}}_k^{𝒰}$ be its abelianization. For any order-$k$ unitary $x$ and $a\in {\mathbb{Z}}_k$ with eigenvalues ${\{{\omega }_k^a\}}_{a\in {\mathbb{Z}}_k}$, write ${\mathrm{\Pi }}_a^{(k)}(x)$ for the projector onto the ${\omega }_k^a$-eigenspace of $x$; where $k$ is clear, we suppress the superscript $(k)$. Given $\varphi \in {\mathbb{Z}}_k^{𝒰}$, we define the element ${\mathrm{\Phi }}_{𝒰,\varphi }^{(k)}\in ℂ{\mathbb{Z}}_k^{\ast 𝒰}$ as ${\mathrm{\Phi }}_{𝒰,\varphi }^{(k)}={\prod }_{x\in V}{\mathrm{\Pi }}_{\varphi (x)}^{(k)}(x),$ where as before the superscript $k$ is suppressed where clear. We use the same notation for the image of ${\mathrm{\Phi }}_{𝒰,\varphi }^{(k)}$ under any homomorphism when the homomorphism is clear. Given a constraint $(𝒰,ℛ)$ over the alphabet ${\mathbb{Z}}_k$, we write $𝒜(𝒰,ℛ)=ℂ{\mathbb{Z}}_k^{𝒰}/⟨{\mathrm{\Phi }}_{𝒰,\varphi }:\varphi \notin ℛ⟩.$ The algebra $𝒜(𝒰,ℛ)$ is isomorphic to the $C^{\ast }$-algebra of functions on the finite set $ℛ$. Consequently, if $\rho :𝒜(𝒰,ℛ)\to ℬ(\mathscr{H})$ is a $\ast$-representation, then ${\{\rho ({\mathrm{\Phi }}_{𝒰,\varphi })\}}_{\varphi \in ℛ}$ is a projective measurement on $\mathscr{H}$, and conversely if ${\{M_{\varphi }\}}_{\varphi \in ℛ}$ is a projective measurement on $\mathscr{H}$ then there is a $\ast$-representation $\rho :𝒜(𝒰,ℛ)\to ℬ(\mathscr{H})$ with $\rho ({\mathrm{\Phi }}_{𝒰,\varphi })=M_{\varphi }$.

Let $S=(𝒳,{({𝒰}_i,{ℛ}_i)}_{i=1}^n)$ be a CS. The constraint-variable algebra is the free product ${𝒜}_{c-v}(S)={\ast }_{i=1}^m𝒜({𝒰}_i,{ℛ}_i)\ast ℂ{\mathbb{Z}}_k^{\ast 𝒳}$. Let ${\sigma }_i:𝒜({𝒰}_i,{ℛ}_i)\to {𝒜}_{c-v}(S)$ be the inclusion on the $i^{th}$ factor, and let ${\sigma }^{\prime }:ℂ{\mathbb{Z}}_k^{\ast 𝒳}\to {𝒜}_{c-v}(S)$ be the inclusion on the final factor. To keep our formulas tidy, we’ll often omit the ${\sigma }_i$ and ${\sigma }^{\prime }$ when it’s clear what subalgebra $𝒜({𝒰}_i,{ℛ}_i)$ the element belongs to. By the GNS representation theorem, there is a correspondence between finite dimensional tracial states on the constraint variable algebra and synchronous quantum strategies for the constraint-variable game. A correlation $p\in C_q^s$ if and only if there is a finite dimensional tracial state $\tau$ on ${𝒜}_{c-v}(S)$ such that $p(\varphi ,a|i,x)=\tau ({\mathrm{\Phi }}_{{𝒰}_i,\varphi }{\mathrm{\Pi }}_a({\sigma }^{\prime }(x)))$. A tracial state $\tau$ on ${𝒜}_{c-v}(S)$ is perfect if it corresponds to a perfect correlation. This happens if and only if $\tau ({\mathrm{\Phi }}_{{𝒰}_i,\varphi }{\mathrm{\Pi }}_a({\sigma }^{\prime }(x)))=0$ whenever $\varphi (x)\ne a$. We are now ready to define the weight and defect, which gives us a way of tracking how close players’ strategies are to being perfect at the level of tracial states on algebras.

Since $\mu$ is finitely supported, the sum in the definition of the defect is finite, and hence is well-defined. The support of the weight is chosen so that if $\mathrm{def}(\tau ;\mu )=0$, then $\tau$ is perfect.

For a probability distribution ${\pi }^{\prime }$ on $[m]$, define the weighted constraint-variable algebra to be ${𝒜}_{c-v}(S,{\pi }^{\prime })=({𝒜}_{c-v}(S),{\mu }_{c-v,{\pi }^{\prime }})$ where the weight function ${\mu }_{c-v}({\mathrm{\Phi }}_{V_i,\varphi }(1-{\mathrm{\Pi }}_{\varphi (x)}({\sigma }^{\prime }(x))))=\frac{{\pi }^{\prime }(i)}{|{𝒰}_i|}$ for all $x\in {𝒰}_i$, $\varphi \in {ℛ}_i$, and $0$ on all other elements. Similarly, Given a probability distribution ${\pi }^{\prime }$ on $[m]$, we define the weighted assignment algebra to be ${𝒜}_a(S)=ℂ{\mathbb{Z}}_k^{\ast 𝒳}$, along with the weight function ${\mu }_{a,{\pi }^{\prime }}({\mathrm{\Phi }}_{{𝒰}_i,\varphi })={\pi }^{\prime }(i)$ for all $\varphi \notin {ℛ}_i$, and $0$ on all other elements.

The point of these algebras is the following lemma.

See [8] for a more complete treatment of the weighted algebra formalism.

In this section, we establish the $\mathrm{RE}$-hardness of smooth label cover. Our reduction is based on the following hardness result involving the quantum value of a $3\mathrm{S}\mathrm{A}\mathrm{T}{5}^{\ast }$ instance.

We reserve the proof until Section 4. Using Theorem 5, we will prove the following theorem.

The proof can be seen as a quantum analog of Theorem 3.5 in [18]. In particular, the proof of Theorem 6 is based on the construction in Section 2.2 of [23], and in Appendix A of [18]. Before we give the proof, we require several intermediary results and definitions.

The purpose of the $(J,R)$-dummy variable game is twofold. It both amplifies the soundness of the original BCS game and ensures the smoothness property with respect to any assignments of the BCS. We start by establishing how the $(J,R)$-dummy variable game exponentially amplifies the soundness with respect to the quantum synchronous value.