Proof. We may restrict our attention to deterministic strategies. Since any such strategy for an XOR game is invariant under the negation of all the answer bits, we may assume that Alice’s answer bit is \(0\) for question \(\perp\). Under this assumption, each cube game for an equation tests the parity of the values associated with the nodes \(011\), \(101\), and \(011\) in the sense that, if the equation is satisfied then the value of that cube game can be \(\frac{3}{4}\); otherwise the value can be at most \(\frac{5}{8}\) (by 1).

If \(\omega(G) \ge 1 - \varepsilon\) then there exists an assignment that satisfies a fraction \(\ge 1-3\varepsilon\) of the equations (weighted by their probabilities). For each satisfied equation, the associated cube game can be won with probability \(\frac{3}{4}\) and, for each unsatisfied equation, it can be won with probability \(\frac{5}{8}\). Averaging and applying 1, we obtain \(\omega(\widetilde{G}) \ge (1-3\varepsilon)\frac{3}{4}+(3\varepsilon)\frac{5}{8} = 1 - \frac{3}{8}\varepsilon\).

If \(\omega(G) < \frac{5}{6} + \varepsilon = 1 - (\frac{1}{6}-\varepsilon)\) then the maximum fraction of satisfied equations (weighted by their probabilities) is \(< 1 - 3(\frac{1}{6} - \varepsilon) = \frac{1}{2} + 3\varepsilon\). Averaging and applying 1 again, we obtain \(\omega(\widetilde{G}) < (\frac{1}{2} + 3\varepsilon)\frac{3}{4} + (\frac{1}{2} - 3\varepsilon)\frac{5}{8} = \frac{11}{16} + \frac{3}{8}\varepsilon\). ◻

Proof. Since \(G\) is the game \(G_{\text{XOR}}\) with additional winning conditions, we can immediately deduce \(\omega(G_{\text{XOR}}) \ge \omega(G)\) and \(\omega^\ast(G_{\text{XOR}}) \ge \omega^\ast(G)\).

For \(\omega(G_{\text{XOR}}) \le \omega(G)\), consider any optimal deterministic strategy \(p(a,b|x,y)=\delta_{g(x),a}\delta_{h(y),b}\) for \(G_{\text{XOR}}\). Then, define the classical strategy \(p'\) for \(G\) via the functions \(g'(x)=g(x) \oplus g(\perp)\) and \(h'(y)=h(y) \oplus g(\perp)\). Since \(g'(x) \oplus h'(y)=g(x) \oplus h(y)\) and \(g'(\perp)=0\), this is a strategy for the tilted XOR game \(G\) with the same value as the value of \(p\) for \(G_{\text{XOR}}\). So, the optimal classical value of \(G\) upper bounds the optimal classical value of \(G_{\text{XOR}}\). ◻

Proof. It is clear that \(\omega^\ast(G^{\Box})\geq\omega(G^{\Box})=\frac{3}{4}\). We use the dual SDP (Eq. 3 discussed in 2.3) to upper bound the quantum value of \(G^{\Box}\). Ordering the elements of \(X_0\) as \((000,011,101,110)\) and the elements of \(X_1\) as \((111,100,010,001)\) the game matrix is \[\begin{align} H=\frac{1}{16}\begin{bmatrix}+1&-1&-1&-1\\-1&+1&-1&-1\\-1&-1&+1&-1\\-1&-1&-1&+1\end{bmatrix}. \end{align}\] Taking the square, we find that \[\begin{align} H^2=\frac{1}{16^2}\begin{bmatrix}4&0&0&0\\0&4&0&0\\0&0&4&0\\0&0&0&4\end{bmatrix}=\frac{1}{64}I, \end{align}\] which implies that the eigenvalues of \(H\) are \(\pm\frac{1}{8}\). Then, the eigenvalues of \(B=\frac{1}{2}\squ*{\begin{smallmatrix}0&H\\H^T&0\end{smallmatrix}}\) are \(\pm\frac{1}{16}\). Therefore, \(\frac{1}{16}I\geq B\), giving that \(a_x=b_y=\frac{1}{8}\) is a feasible point for the dual SDP (Eq. 3 ) for \(G^{\Box}\), giving an upper bound on the bias \(\beta^\ast(G^{\Box})\leq\frac{1}{2}\sum_{x\in X_0}a_x+\frac{1}{2}\sum_{y\in X_1}b_y=\frac{1}{2}\). This gives the upper bound on the value \(\omega^\ast(G^{\Box})\leq\frac{1}{2}+\frac{1}{2}\cdot\frac{1}{2}=\frac{3}{4}\).

Since \(\omega^{\ast}(G^{\rotatebox[origin=c]{-30}{\scriptstyle\square}})\) is sandwiched between \(\omega^\ast(G^{\Box})\) and \(\omega(G^{\rotatebox[origin=c]{-30}{\scriptstyle\square}})\), this implies \(\omega^{\ast}(G^{\rotatebox[origin=c]{-30}{\scriptstyle\square}})=\frac{3}{4}\). ◻

Proof. Since \(\omega^\ast(G^{\Box})=\omega^{\ast}(G^{\rotatebox[origin=c]{-30}{\scriptstyle\square}})\), the correlation \(C\) is also an optimal correlation for \(G^{\Box}\). Let \(\ket{u_x}=(A_x\otimes I)\ket{\psi}\) and \(\ket{v_y}=(I\otimes B_y)\ket{\psi}\). Since the optimal value and the Frobenius norm are equal in terms of the usual and the real inner product, we have by 1 that \(\sum_{x\in X}H_{x,y}\ket{u_x}=\frac{1}{8}\ket{v_y}\) and \(\sum_{y\in Y}H_{x,y}\ket{v_y}=\frac{1}{8}\ket{u_x}\), and therefore \[\begin{align} &\sum_{x}H_{x,y}(A_x\otimes I)\ket{\psi}=\frac{1}{8}(I\otimes B_y)\ket{\psi},\\ &\sum_{y}H_{x,y}(I\otimes B_y)\ket{\psi}=\frac{1}{8}(A_x\otimes I)\ket{\psi}. \end{align}\] Taking the square, \[\begin{align} \frac{1}{64}\ket{\psi}=\frac{1}{64}(I\otimes B_y)^2\ket{\psi}=\frac{1}{8}\sum_{x}H_{x,y}(A_x\otimes B_y)\ket{\psi}=\parens[\Big]{\sum_{x}H_{x,y}(A_x\otimes I)}^2\ket{\psi}. \end{align}\] Now, note that for any \(\ket{v}\) in the support of \(\ket{\psi}\) on \(H_A\), there exists \(\ket{w}\in H_B\) such that \(\ket{v}=(I\otimes\bra{w})\ket{\psi}\). Therefore, \(A_x\ket{v}=8\sum_{y}H_{x,y}(I\otimes \bra{w}B_y)\ket{\psi}\), which remains in the support of \(\ket{\psi}\) on \(H_A\). Thus, the \(A_x\) preserve this space. In the following, we restrict to the support of \(\ket{\psi}\) on \(H_A\).

With the above restriction, \(\parens*{\sum_xH_{x,y}A_x}^2=\frac{1}{64}I\). It follows that, for all \(y \in X_1\), \[\begin{align} (A_{y \oplus 111}-A_{y \oplus 100}-A_{y \oplus 010}-A_{y\oplus 001})^2=4I, \end{align}\] as \(|H_{x,y}|=\frac{1}{16}\). Since \(C\) is a strategy for the tilted XOR game, we know that \(A_{000}=I\). Writing \(A_1=A_{011}\), \(A_2=A_{101}\), and \(A_3=A_{110}\), we get the four relations \[\begin{align} (+I-A_1-A_2-A_3)^2&=4I,\\ (-I+A_1-A_2-A_3)^2&=4I,\\ (-I-A_1+A_2-A_3)^2&=4I,\\ (-I-A_1-A_2+A_3)^2&=4I. \end{align}\] Adding the first two relations gives \[\begin{align} 8I&=((I-A_1)-(A_2+A_3))^2+(-(I-A_1)-(A_2+A_3))^2\\ &=2\parens*{(I-A_1)^2+(A_2+A_3)^2}\\ &=2\parens*{I-2A_1+I+I+A_2A_3+A_3A_2+I}\\ &=2\parens*{4I-2A_1+\{A_2,A_3\}}, \end{align}\] which can be rearranged to give \(\{A_2,A_3\}=2A_1\). By symmetry of the relations, we get the other anticommutation relations \(\{A_1,A_2\}=2A_3\) and \(\{A_1,A_3\}=2A_2\). Consider the following: \[\begin{align} 4A_1&=\{A_2,2A_3\}\\ &=\set*{A_2,\{A_1,A_2\}}\\ &=A_2(A_1A_2+A_2A_1)+(A_1A_2+A_2A_1)A_2\\ &=2\parens*{A_2A_1A_2+A_1}. \end{align}\] Rearranging, we find \(A_2A_1A_2-A_1=0\), and then multiplying by \(A_2\) gives the commutation relation \([A_1,A_2]=0\). In the same way, we find the other commutation relations \([A_1,A_3]=[A_2,A_3]=0\). Hence, Alice’s observables commute. To finish the proof, we see using the commutation relations that \[\begin{align} &A_1A_2A_3=\frac{1}{2}A_1\{A_2,A_3\}=A_1^2=I.\qedhere \end{align}\] ◻

Proof of 3. It is known that \(\text{E3-LIN}_{1,1}^*\) is undecidable [21]. Our reduction from \(\text{E3-LIN}_{1,1}^*\) to \(\text{TXOR}_{\scriptscriptstyle \frac{3}{4},\frac{3}{4}}^\ast\)is based on Håstad’s reduction (reviewed in 2.5), but relies on a different interpretation of the resulting game. Given an E3-LIN game \(G\), let \(\widetilde{G}\) denote the game produced by the gadgets in 3. Rather than viewing \(\widetilde{G}\) as an XOR game, we reinterpret it as a tilted XOR game with distinguished input \(\perp\). We will show that \(\omega^*(\widetilde{G}) = \frac{3}{4}\) if and only if the E3-LIN game has a perfect quantum strategy.

First, suppose that a strategy for the tilted XOR game \(\widetilde{G}\) attains success probability \(\frac{3}{4}\). Then, since \(\widetilde{G}\) is a probabilistic mixture of edge-disjoint tilted cube games, each of which has maximum success probability \(\frac{3}{4}\), it follows that the strategy achieves success probability \(\frac{3}{4}\) for each of the tilted cube games. Therefore, by 4, for each equation of the form \(v_i \oplus v_j \oplus v_k = b\), the corresponding observables \(A_i\), \(A_j\), and \(A_k\) commute and satisfy \(A_iA_jA_k = (-1)^bI\) (when restricted to the support of the shared state on Alice’s system). It follows that the observables corresponding to the variables in the E3-LIN instance are an operator solution to the system of equations, which can be turned into a perfect strategy for the E3-LIN game.

Next, suppose that the E3-LIN game has a perfect quantum strategy. Then, by [20], there exists a \(d\)-dimensional operator solution to the E3-LIN game, which consists of a binary observable \(A_i\) assigned to each variable \(v_i\), where the observables satisfy the following property: for each equation \(v_i \oplus v_j \oplus v_k = b\) in the E3-LIN game, the observables \(A_i\), \(A_j\), and \(A_k\) commute and \(A_iA_jA_k = (-1)^bI\). This can be turned into a strategy for the tilted XOR game that succeeds with probability \(\frac{3}{4}\) as follows. For each cube within the tilted XOR game \(\widetilde{G}\), assign the operators \(A_i\), \(A_j\), and \(A_k\) to the vertices \(i\), \(j\), and \(k\) (respectively) and assign the operator \(I\) to vertex \(\perp\). For the remaining (odd parity) vertices of the cube, assign the binary observables \[\begin{align} B_{111} &= \textstyle{\frac{1}{2}}(+(-1)^bI - A_i^T - A_j^T - A_k^T) \\[1mm] B_{100} &= \textstyle{\frac{1}{2}}(-(-1)^bI + A_i^T - A_j^T - A_k^T) \\[1mm] B_{010} &= \textstyle{\frac{1}{2}}(-(-1)^bI - A_i^T + A_j^T - A_k^T) \\[1mm] B_{001} &= \textstyle{\frac{1}{2}}(-(-1)^bI - A_i^T - A_j^T + A_k^T). \end{align}\] Then it is a straightforward exercise to show the above are proper binary observables (i.e. hermitian unitaries) and, with respect to the entangled state \[\begin{align} \ket{\psi} = \frac{1}{\sqrt{d}} \sum_{k=1}^d\ket{k}\otimes\ket{k}, \end{align}\] the success probability of this strategy for the tilted XOR game \(\widetilde{G}\) succeeds with probability \(\frac{3}{4}\), where we use the fact that \[\require{physics} \begin{align} C(x,y) = \bra{\psi}A_x\otimes B_y\ket{\psi} = \frac{1}{d}\Tr\bigl(A_x^T B_y\bigr). \end{align}\] ◻

Proof. First, write \(n=|X|\) and \(\beta=\beta^\ast(G)\); we know \(\beta=n\alpha\). By definition, there exists some \(\varepsilon'\leq2\varepsilon\) such that \(\sum_{x,y}H_{x,y}\braket{u_x}{v_y}=\beta-\varepsilon'\). Then, we expand the left-hand side from the lemma statement to get that \[\begin{align} \sum_x\norm[\Big]{\sum_yH_{x,y}\ket{v_y}-\alpha\ket{u_x}}^2&=\sum_x\parens[\Big]{\alpha^2-2\alpha\sum_yH_{x,y}\braket{u_x}{v_y}+\norm[\Big]{\sum_yH_{x,y}\ket{v_y}}^2}\\ &=-\alpha\beta+2\alpha\varepsilon'+\sum_x\norm[\Big]{\sum_yH_{x,y}\ket{v_y}}^2 \end{align}\] Now, we focus on bounding the last term. Following the argument of [14], let \(\ket{u_x'}\) be the normalisation of \(\sum_yH_{x,y}\ket{v_y}\) (if \(\sum_yH_{x,y}\ket{v_y}=0\), we take \(\ket{u'_x}\) to be an arbitrary unit vector). Since \[\begin{align} \sum_{x,y}H_{x,y}\braket{u_x'}{v_y}=\sum_{x}\norm[\Big]{\sum_yH_{x,y}\ket{v_y}}\geq\sum_{x,y}H_{x,y}\braket{u_x}{v_y}, \end{align}\] the vector correlation \(C'(x,y)=\braket{u_x'}{v_y}\) is an \(\varepsilon\)-optimal strategy as well, with bias \(\beta-\varepsilon'_B\) for some \(\varepsilon'_B\leq\varepsilon'\leq 2\varepsilon\). Then, \[\begin{align} \sum_x\norm[\Big]{\sum_yH_{x,y}\ket{v_y}}^2&=\sum_x\norm[\Big]{\sum_yH_{x,y}\ket{v_y}-\alpha\ket{u_x'}+\alpha\ket{u_x'}}^2\\ &=\sum_x\parens[\Big]{\alpha^2+2\alpha\sum_yH_{x,y}\braket{u_x'}{v_y}-2\alpha^2+\norm[\Big]{\sum_yH_{x,y}\ket{v_y}-\alpha\ket{u_x'}}^2}\\ &=\alpha\beta-2\alpha\varepsilon'_B+\sum_x\parens[\Big]{\sum_yH_{x,y}\braket{u_x'}{v_y}-\alpha}^2. \end{align}\] As in the SDP formulation, write \(M\) for the \(2n\times 2n\) Gram matrix of the vectors \(\ket{u_x'}\) and \(\ket{v_y}\) over \(x\) and \(y\), and let \[S=\frac{1}{2}\begin{bmatrix}\alpha I&-H\\-H^T&\alpha I\end{bmatrix}.\] We have that \(\require{physics} \varepsilon'_B=\Tr(SM)\), \(\alpha I\geq S\geq 0\), and \(\require{physics} \norm{M}\leq\Tr(M)\leq 2n\). Then, \[\require{physics} \begin{align} \sum_x\parens[\Big]{\sum_yH_{x,y}\braket{u_x'}{v_y}-\alpha}^2&=4\sum_{x\in X}(SM)_{x,x}^2\\ &\leq4\norm{SM}_F^2=4\Tr(SM^2S)\\ &\leq4\norm{S}\norm{M}\Tr(SM)\\ &\leq4(\alpha)(2n)\varepsilon'_B=8\beta\varepsilon'_B. \end{align}\] Putting it all together, \[\begin{align} &\sum_x\norm[\Big]{\sum_yH_{x,y}\ket{v_y}-\alpha\ket{u_x}}^2\leq-\alpha\beta+2\alpha\varepsilon'+(\alpha\beta-2\alpha\varepsilon'_B+8\beta\varepsilon'_B)\\ &\leq4(\alpha+4\beta)\varepsilon.\qedhere \end{align}\] ◻

Proof. Note that Alice’s observable \(A_{000}=I\). Then, as \(\alpha=\frac{1}{8}\) and \(\beta^\ast(G^{\rotatebox[origin=c]{-30}{\scriptstyle\square}})=\frac{3}{4}\), 5 implies that \[\begin{align} \label{eq:basic-rigidity} \sum_y\norm[\Big]{\sum_{x}H_{x,y}(A_x\otimes I)\ket{\psi}-\frac{1}{8}(I\otimes B_y)\ket{\psi}}^2\leq4\parens*{\frac{1}{8}+4\frac{3}{4}}\varepsilon\leq13\varepsilon. \end{align}\tag{4}\] Now, let \(\ket{\psi}=\sum_{i}\sqrt{p_i}\ket{a_i}\otimes\ket{b_i}\) be the Schmidt decomposition of \(\ket{\psi}\), and take \(\lambda:H_B\rightarrow H_A\) to be the operator \(\lambda=\sum_i\sqrt{p_i}\ketbra{a_i}{b_i}\). Then, \(\lambda\lambda^\ast=\psi_A\) and \(\lambda^\ast\lambda=\psi_B\), the marginals of \(\ket{\psi}\) on \(H_A\) and \(H_B\), respectively. We can rewrite 4 in terms of the Frobenius norm as \[\begin{align} \sum_y\norm[\Big]{\sum_{x}H_{x,y}A_x\lambda-\frac{1}{8}\lambda\overline{B}_y}^2_F\leq13\varepsilon, \end{align}\] where the complex conjugate is with respect to the basis \(\{\ket{b_i}\}_i\). Writing \(h_{x,y}=16H_{x,y}\), we have \(|h_{x,y}|=1\) and \[\begin{align} \sum_y\norm[\Big]{\sum_{x}h_{x,y}A_x\lambda-2\lambda\overline{B}_y}^2_F\leq2^{8}\cdot13\varepsilon. \end{align}\] Next, we remove the dependence on \(\overline{B}_y\): \[\begin{align} \norm[\Big]{\parens[\Big]{\sum_{x}h_{x,y}A_x}^2\lambda-4\lambda}_F&\leq\norm[\Big]{\parens[\Big]{\sum_{x}h_{x,y}A_x}^2\lambda-2\sum_{x}h_{x,y}A_x\lambda\overline{B}_y}_F+\norm[\Big]{2\sum_{x}h_{x,y}A_x\lambda\overline{B}_y-4\lambda}_F\\ &\leq\norm[\Big]{\sum_{x}h_{x,y}A_x}\norm[\Big]{\sum_{x}h_{x,y}A_x\lambda-2\lambda\overline{B}_y}_F+2\norm[\Big]{\sum_{x}h_{x,y}A_x\lambda-2\lambda\overline{B}_y}_F\norm[\Big]{\overline{B}_y}\\ &\leq6\norm[\Big]{\sum_{x}h_{x,y}A_x\lambda-2\lambda\overline{B}_y}_F, \end{align}\] and therefore \[\begin{align} \sum_y\norm[\Big]{\parens[\Big]{\sum_{x}h_{x,y}A_x}^2\lambda-4\lambda}_F^2\leq36\sum_y\norm[\Big]{\sum_{x}h_{x,y}A_x\lambda-2\lambda\overline{B}_y}_F^2\leq2^{10}\cdot117\varepsilon. \end{align}\] Now, as in the proof of 4, let \(A_1=A_{011}\), \(A_2=A_{101}\), and \(A_3=A_{110}\). Then we expand to see that \[\begin{align} &\norm*{(I-A_1-A_2-A_3)^2\lambda-4\lambda}_F^2+\norm*{(-I+A_1-A_2-A_3)^2\lambda-4\lambda}_F^2\\ &\qquad+\norm*{(-I-A_1+A_2-A_3)^2\lambda-4\lambda}_F^2+\norm*{(-I-A_1-A_2+A_3)^2\lambda-4\lambda}_F^2\leq 2^{10}\cdot117\varepsilon. \end{align}\] Using the facts that \[\begin{align} (I-A_1-A_2-A_3)^2+(-I+A_1-A_2-A_3)^2&=2\parens*{4I-2A_1+\{A_2,A_3\}}\\ (-I-A_1+A_2-A_3)^2+(-I-A_1-A_2+A_3)^2&=2\parens*{4I+2A_1-\{A_2,A_3\}}, \end{align}\] we find that \[\begin{align} \norm*{\{A_2,A_3\}\lambda-2A_1\lambda}_F^2&=\frac{1}{8}\norm*{(I-A_1-A_2-A_3)^2\lambda+(-I+A_1-A_2-A_3)^2\lambda-8\lambda}_F^2\\ &\qquad+\frac{1}{8}\norm*{(-I-A_1+A_2-A_3)^2\lambda+(-I-A_1-A_2+A_3)^2\lambda-8\lambda}_F^2\\ &\leq\frac{1}{4}\norm*{(I-A_1-A_2-A_3)^2\lambda-4\lambda}_F^2+\frac{1}{4}\norm*{(-I+A_1-A_2-A_3)^2\lambda-4\lambda}_F^2\\ &\qquad+\frac{1}{4}\norm*{(-I-A_1+A_2-A_3)^2\lambda-4\lambda}_F^2+\frac{1}{4}\norm*{(-I-A_1-A_2+A_3)^2\lambda-4\lambda}_F^2\\ &\leq 2^{8}\cdot117\varepsilon. \end{align}\] By symmetry, the other anticommutation relations hold approximately as well, with the same error. Next, let \(\widetilde{B}_1=\frac{1}{2}\parens*{\overline{B}_{100}-\overline{B}_{010}-\overline{B}_{001}-\overline{B}_{111}}\), \(\widetilde{B}_2=\frac{1}{2}\parens*{\overline{B}_{010}-\overline{B}_{100}-\overline{B}_{111}-\overline{B}_{001}}\), and \(\widetilde{B}_3=\frac{1}{2}\parens*{\overline{B}_{001}-\overline{B}_{111}-\overline{B}_{100}-\overline{B}_{010}}\). By construction, \(\norm{\widetilde{B}_i}\leq 2\) and by 5, \(\sum_{i}\norm{A_i\lambda-\lambda\widetilde{B}_i}_F^2\leq 2^{6}\cdot13\varepsilon\). Now, note that \[\begin{align} A_1A_2A_3-I&=\frac{1}{2}\parens*{A_1(\{A_2,A_3\}-2A_1)+A_1[A_2,A_3]}\\ &=\frac{1}{2}A_1(\{A_2,A_3\}-2A_1)-\frac{1}{4}A_1A_2\parens*{\{A_2,\{A_2,A_3\}\}-4A_3}\\ &=\frac{1}{4}A_1(\{A_2,A_3\}-2A_1)-\frac{1}{2}A_1A_2\parens*{\{A_2,A_1\}-2A_3}-\frac{1}{4}A_1A_2(\{A_2,A_3\}-2A_1)A_2 \end{align}\]

Then, we can use this to bound \[\begin{align} \norm*{(A_1A_2A_3-I)\lambda}_F&\leq\frac{1}{4}\norm*{A_1(\{A_2,A_3\}-2A_1)\lambda}_F+\frac{1}{2}\norm*{A_1A_2\parens*{\{A_2,A_1\}-2A_3}\lambda}_F\\ &+\frac{1}{4}\norm*{A_1A_2(\{A_2,A_3\}-2A_1)A_2\lambda}_F\\ &\leq\frac{1}{4}\norm*{(\{A_2,A_3\}-2A_1)\lambda}_F+\frac{1}{2}\norm*{\parens*{\{A_2,A_1\}-2A_3}\lambda}_F\\ &+\frac{1}{4}\norm*{(\{A_2,A_3\}-2A_1)\lambda\widetilde{B}_2}_F+\frac{1}{4}\norm*{(\{A_2,A_3\}-2A_1)(A_2\lambda-\lambda\widetilde{B}_2)}_F\\ &\leq\frac{3}{4}\norm*{(\{A_2,A_3\}-2A_1)\lambda}_F+\frac{1}{2}\norm*{\parens*{\{A_2,A_1\}-2A_3}\lambda}_F+\norm*{A_2\lambda-\lambda\widetilde{B}_2}_F\\ &\leq (\frac{3}{4}+\frac{1}{2})2^4\sqrt{117\varepsilon}+2^3\sqrt{13\varepsilon}\\ &=68\sqrt{13\varepsilon}\qedhere \end{align}\] ◻

Proof. We use the same notation as in [lem:near-optimal], and note that Alice and Bob’s observables are \(A_x=P^x_0-P^x_1\) and \(B_y=Q^y_0-Q^y_1\), respectively. Fix an orthonormal basis \(\{\ket{k}\}_k\) of \(H_A\), and let \(\ket{\phi}=\sum_k\ket{k}\otimes\psi_A^{1/2}\ket{k}\). Let \(\Pi_{\textit{\boldsymbol{a}}}=\overline{P^3_{a_3}P^2_{a_2}P^1_{a_1}P^2_{a_2}P^3_{a_3}}\). Write \[\begin{align} w=\frac{1}{3}\sum_{\substack{\textit{\boldsymbol{a}}\in\{0,1\}^3\\a_1+a_2+a_3=0}}\braket{\phi}{\Pi_{\textit{\boldsymbol{a}}}\otimes(P^{1}_{a_1}+P^{2}_{a_2}+P^{3}_{a_3})}{\phi}. \end{align}\]

We will lower bound this by upper bounding \[\begin{align} 1-w=\frac{1}{3}\sum_{\substack{\textit{\boldsymbol{a}}\in\{0,1\}^3\\a_1+a_2+a_3=0}}\braket{\phi}{\Pi_{\textit{\boldsymbol{a}}}\otimes(P^{1}_{\lnot a_1}+P^{2}_{\lnot a_2}+P^{3}_{\lnot a_3})}{\phi}+\sum_{\substack{\textit{\boldsymbol{a}}\in\{0,1\}^3\\a_1+a_2+a_3=1}}\braket{\phi}{\Pi_{\textit{\boldsymbol{a}}}\otimes I}{\phi}. \end{align}\]

First, we want to show that \(A_i\) approximately commutes with \(\psi_A^{1/2}\). Due to 5, \(\norm{A_i\lambda-\lambda\widetilde{B}_i}_F\leq 8\sqrt{13\varepsilon}\). With the goal of removing \(\widetilde{B}_i\), we first round it to an order-\(2\) unitary. We have \[\begin{align} \norm{\lambda(I-\widetilde{B}_i^2)}_F\leq \norm{A_i^2\lambda-A_i\lambda\widetilde{B}_i}_F+\norm{A_i\lambda\widetilde{B}_i-\lambda\widetilde{B}_i^2}_F\leq3\norm{A_i\lambda-\lambda\widetilde{B}_i}_F\leq 24\sqrt{13\varepsilon}. \end{align}\] Now, let \(C_i=\mathrm{sgn}(\widetilde{B}_i)\), which is an order-\(2\) unitary by construction. We have that \[\begin{align} (I-\widetilde{B}_i^2)^2=(C_i-\widetilde{B}_i)^2(C_i+\widetilde{B}_i)^2\geq(C_i-\widetilde{B}_i)^2, \end{align}\] so \(\norm{\lambda(C_i-\widetilde{B}_i)}_F\leq\norm{\lambda(I-\widetilde{B}_i^2)}_F\leq24\sqrt{13\varepsilon}\). Therefore, we can replace \(\widetilde{B}_i\) with \(C_i\) and find \[\begin{align} \norm{A_i\lambda-\lambda C_i}_F\leq\norm{A_i\lambda-\lambda \widetilde{B}_i}_F+\norm{\lambda(C_i-\widetilde{B}_i)}_F\leq32\sqrt{13\varepsilon}. \end{align}\] To finish this step, we employ the Araki-Yamagami inequality [28], which gives a tight modulus of continuity for the operator absolute value with respect to the Frobenius norm: \[\begin{align} \norm*{|S|-|T|}_F\leq\sqrt{2}\norm*{S-T}_F. \end{align}\] Since \(|\lambda^\ast A_i|=\sqrt{A_i\lambda\lambda^\ast A_i}=A_i\psi_A^{1/2}A_i\) and \(|C_i\lambda^\ast|=\sqrt{\lambda C_i^2\lambda^\ast}=\psi_{A}^{1/2}\), \[\begin{align} \norm*{[A_i,\psi_A^{1/2}]}_F&=\norm*{A_i\psi_A^{1/2}A_i-\psi_A^{1/2}}_F=\norm{|\lambda^\ast A_i|-|C_i\lambda^\ast|}_F\leq\sqrt{2}\norm{\lambda^\ast A_i-C_i\lambda^\ast}_F\leq32\sqrt{26\varepsilon}. \end{align}\]

Next, we show that the \(A_i\) approximately commute. In fact, using the result of [lem:near-optimal], \[\begin{align} \norm{[A_1,A_2]\psi_A^{1/2}}_F&=\norm{(A_1A_2-A_2A_1)\lambda}_F\\ &\leq\norm{(A_1A_2-A_3)\lambda}_F+\norm{(A_2A_1-A_3)\lambda}_F\\ &=\norm{(A_3A_1A_2-I)\lambda}_F+\norm{(A_3A_2A_1-I)\lambda}_F\\ &\leq136\sqrt{13\varepsilon}. \end{align}\]

By symmetry, this bound holds for the other two commutators as well. These commutation relations also apply to the PVM elements: \(\norm{[P^i_a,\psi_A^{1/2}]}_F\leq 16\sqrt{26\varepsilon}\) and \(\norm{[P^i_a,P^j_b]\psi_A^{1/2}}_F\leq34\sqrt{13\varepsilon}\). Now, we bound the terms of \(1-w\) one by one. First, note that, for any \(i\), \[\require{physics} \begin{align} \braket{\phi}{\Pi_{\textit{\boldsymbol{a}}}\otimes P^i_{\lnot a_i}}{\phi}&=\Tr\squ*{\overline{\Pi}_{\textit{\boldsymbol{a}}}\psi_A^{1/2}P^i_{\lnot a_i}\psi_A^{1/2}}=\norm*{P^1_{a_1}P^2_{a_2}P^3_{a_3}\psi_A^{1/2}P^i_{\lnot a_i}}_F^2. \end{align}\] If \(i=3\), \[\begin{align} \norm*{P^1_{a_1}P^2_{a_2}P^3_{a_3}\psi_A^{1/2}P^3_{\lnot a_3}}_F&\leq \norm*{P^1_{a_1}P^2_{a_2}P^3_{a_3}P^3_{\lnot a_3}\psi_A^{1/2}}_F+\norm*{[P^3_{a_3},\psi_A^{1/2}]}_F\\ &\leq 16\sqrt{26\varepsilon}; \end{align}\] if \(i=2\), \[\begin{align} \norm*{P^1_{a_1}P^2_{a_2}P^3_{a_3}\psi_A^{1/2}P^2_{\lnot a_2}}_F&\leq\norm*{P^1_{a_1}P^3_{a_3}P^2_{a_2}\psi_A^{1/2}P^2_{\lnot a_2}}_F+\norm*{[P^2_{a_2},P^3_{a_3}]\psi_A^{1/2}}_F\\ &\leq\norm*{P^1_{a_1}P^3_{a_3}P^2_{a_2}P^2_{\lnot a_2}\psi_A^{1/2}}_F+\norm*{[P^2_{a_2},\psi_A^{1/2}]}_F+\norm*{[P^2_{a_2},P^3_{a_3}]\psi_A^{1/2}}_F\\ &\leq 16\sqrt{26\varepsilon}+34\sqrt{13\varepsilon}=2(8\sqrt{2}+17)\sqrt{13\varepsilon}; \end{align}\] and if \(i=1\), \[\begin{align} \norm*{P^1_{a_1}P^2_{a_2}P^3_{a_3}\psi_A^{1/2}P^1_{\lnot a_1}}_F&\leq\norm*{P^1_{a_1}P^2_{a_2}\psi_A^{1/2}P^3_{a_3}P^1_{\lnot a_1}}_F+16\sqrt{26\varepsilon}\\ &\leq\norm*{P^1_{a_1}P^2_{a_2}\psi_A^{1/2}P^1_{\lnot a_1}P^3_{a_3}}_F+16\sqrt{26\varepsilon}+34\sqrt{13\varepsilon}\\ &\leq\norm*{P^2_{a_2}P^1_{a_1}\psi_A^{1/2}P^1_{\lnot a_1}P^3_{a_3}}_F+16\sqrt{26\varepsilon}+68\sqrt{13\varepsilon}\\ &\leq\norm*{P^2_{a_2}P^1_{a_1}P^1_{\lnot a_1}\psi_A^{1/2}P^3_{a_3}}_F+32\sqrt{26\varepsilon}+68\sqrt{13\varepsilon}\\ &=4(8\sqrt{2}+17)\sqrt{13\varepsilon}. \end{align}\] For the final term, \[\require{physics} \begin{align} &\sum_{\substack{\textit{\boldsymbol{a}}\in\{0,1\}\\a_1+a_2+a_3=1}}\braket{\phi}{\Pi_{\textit{\boldsymbol{a}}}\otimes I}{\phi}=\sum_{\substack{\textit{\boldsymbol{a}}\in\{0,1\}\\a_1+a_2+a_3=1}}\Tr\parens*{P^3_{a_3}P^2_{a_2}P^1_{a_1}P^2_{a_2}P^3_{a_3}\psi_A}\\ &=\frac{1}{32}\sum_{\substack{\textit{\boldsymbol{a}}\in\{0,1\}\\a_1+a_2+a_3=1}}\Tr\squ*{(I+(-1)^{a_3}A_3)(I+(-1)^{a_2}A_2)(I+(-1)^{a_1}A_1)(I+(-1)^{a_2}A_2)(I+(-1)^{a_3}A_3)\psi_A}\\ &=\frac{1}{32}\Tr\squ*{\parens*{4I-4A_1A_2A_3+4I-4A_2A_1A_3+4I-4A_3A_1A_2+4I-A_3A_2A_1}\psi_A}\\ &=\frac{1}{8}\parens*{\norm*{(A_1A_2A_3-I)\lambda}_F^2+\norm*{(A_2A_1A_3+1)\lambda}_F^2}\\ &\leq\frac{1}{4}(68\sqrt{13\varepsilon})^2=4\cdot13\cdot17^2\varepsilon=15028\varepsilon. \end{align}\] Putting everything together, we find the bound \[\begin{align} 1-w&\leq\frac{4}{3}\parens*{(16\sqrt{26\varepsilon})^2+(2(8\sqrt{2}+17)\sqrt{13\varepsilon})^2+(4(8\sqrt{2}+17)\sqrt{13\varepsilon})^2}+15028\varepsilon\\ &=\frac{4}{3}\parens*{6656\varepsilon+260(417+272\sqrt{2})\varepsilon}+15028\varepsilon.\\ &\leq 301814\varepsilon\qedhere \end{align}\] ◻

Proof. Without loss of generality we may suppose that \(\Pi_{\textit{\boldsymbol{a}}}=0\) if \(a_1+a_2+a_3=1\) — we can change Alice’s PVM to one satisfying this condition without decreasing the value. Now write \(\Pi^{011}_a=\sum_{a_2,a_3}\Pi_{aa_2a_3}\), \(\Pi^{101}_a=\sum_{a_1,a_3}\Pi_{a_1aa_3}\), and \(\Pi^{110}_a=\sum_{a_1,a_2}\Pi_{a_1a_2a}\). Let \(A_u=P^u_0-P^u_1\) and \(C_u=\Pi^u_0-\Pi^u_1\) for all \(u\in\{011,101,110\}\); let \(A_{000}=I\) and \(C_{000}=C_{011}C_{101}C_{110}\); and define \(B_v=\frac{1}{2}\parens*{C_{\lnot v}-C_{v+e_1}-C_{v+e_2}-C_{v+e_3}}\) for all \(v\in X_1\). Since the \(C_u\) are commuting order-\(2\) unitaries satisfying \(C_{000}C_{011}C_{101}C_{110}=I\), the \(B_u\) are also order-\(2\) unitaries. Next, writing \(C\) for the correlation corresponding to the strategy \(p\), note that \[\begin{align} 1-\varepsilon&=\frac{1}{3}\sum_{\substack{u\in\{011,101,110\}\\a\in\{0,1\}}}\braket{\psi}{\Pi^u_a\otimes P^u_{a}}{\psi}\\ &=\frac{1}{6}\sum_{u\in X_0}\parens*{1+\braket{\psi}{C_u\otimes A_u}{\psi}}-\frac{1}{6}\parens*{1+\braket{\psi}{C_{000}\otimes I}{\psi}}\\ &=\frac{1}{2}+\frac{1}{6}\sum_{u\in X_0}\braket{\psi}{\frac{1}{2}\parens*{B_{\lnot u}-B_{u+e_1}-B_{u+e_2}-B_{u+e_3}}\otimes A_u}{\psi}\\ &\qquad-\frac{1}{6}\sum_{\textit{\boldsymbol{a}}\in\{0,1\}^3}(-1)^{a_1+a_2+a_3}\braket{\psi}{\Pi_{\textit{\boldsymbol{a}}}\otimes I}{\psi}\\ &=\frac{1}{2}+\frac{4}{3}\beta(G^{\rotatebox[origin=c]{-30}{\scriptstyle\square}},C)-\frac{1}{6}\braket{\psi}{I\otimes I}{\psi}=\frac{1}{3}+\frac{4}{3}\beta(G^{\rotatebox[origin=c]{-30}{\scriptstyle\square}},C). \end{align}\] Hence, we can rearrange and find that \(\beta(G^{\rotatebox[origin=c]{-30}{\scriptstyle\square}},C)\geq\frac{1}{2}-\frac{3}{4}\varepsilon\), as wanted. ◻

Proof of 4. Let \((S,\pi)\) be an instance of succinct E3-LIN. We construct an instance \(G\) of succinct TXOR as follows. We replace each constraint with a copy of the tilted bipartite cube game, where we identify the questions \(011\), \(101\), and \(110\) with the original variables in the constraint, and identify the \(000\) variables from all the cubes, and take this to be the distinguished variable. For those constraints of the form \(x_1+x_2+x_3=1\), we flip the signs of the edges adjacent to \(000\) in the corresponding cube. This reduction is local on each constraint, so it can be effected in polynomial-time on a succinctly-presented instance.

First, we show completeness. If there exists a quantum strategy \(p\) such that \(\omega(G(S,\pi),p)\geq 1-\varepsilon\). Using Naimark dilation, we may assume it is projective. Let \(1-\varepsilon_{b,\textit{\boldsymbol{x}}}\) be the value on the constraint \(x_1+x_2+x_3=b\). Then, by constructing a strategy \(p'\) for \(G\) using 7, the value of the corresponding cube is \(\geq \frac{3}{4}-\frac{3}{8}\varepsilon_{b,\textit{\boldsymbol{x}}}\), and therefore \(\omega(G,p')\geq \frac{3}{4}-\frac{3}{8}\varepsilon\).

Next, we show soundness. Suppose there exists a quantum strategy \(p\) for \(G\) such that \(\omega(G,p)\geq\frac{3}{4}-\delta\). As above, we can suppose the strategy is projective due to Naimark dilation. Then, via 6, there exists a strategy \(p'\) for \(G(S,\pi)\) such that \(\omega(G(S,\pi),p')\geq 1-4\cdot10^6\delta\).

Putting these together, the construction maps \(\text{E3-LIN-MIP}^\ast_{1-\varepsilon,s}\) to \(\text{TXOR-MIP}^\ast_{\frac{3}{4}-\frac{3}{8}\varepsilon,\frac{3}{4}-\frac{1-s}{4\cdot 10^5}}\). ◻

Proof. We define a classical strategy by sampling a random deterministic strategy \(p(a,b|x,y)=\delta_{a,g(x)}\delta_{b,h(y)}\) for \(g\) and \(h\) uniformly random functions. Then, the bias is \(\geq0\), giving that the value of the strategy is \(\geq\frac{1}{2}\). ◻

Proof. Consider the following algorithm (the input is a tilted XOR game \(G\)):

1. Compute \(\omega^\ast(G_{\text{XOR}})\) to precision \(\frac{1}{2}(c-\gamma(s))\), where \(G_{\text{XOR}}\) is the XOR relaxation of \(G\).

2. If \(\omega^\ast(G_{\text{XOR}})\geq c\) then output YES; otherwise, output NO.

Since \(\omega^\ast(G_{\text{XOR}})\) can be computed by an SDP, this algorithm is polynomial-time in the instance size and \(\log(1/(c-\gamma(s)))\). Now, if \(\omega^\ast(G)\geq c\), then \(\omega^\ast(G_{\text{XOR}})\geq\omega^\ast(G)\geq c\), so the algorithm outputs YES correctly. On the other hand, if \(\omega^\ast(G)<s\), then, \(\omega(G_{\text{XOR}})=\omega(G)<s\), so using the assumption on \(\gamma\), \(\omega^\ast(G_{\text{XOR}})<\gamma(s)< c\). As such, the algorithm outputs NO correctly.

The proof for the classical case proceeds identically. ◻

Proof. The first reduction follows simply by taking a convex combination with the XOR games with winning probability \(1\) and \(\frac{1}{2}\). ◻

Proof. Let \(x\) be a Turing machine, and let \(G_x\) be the corresponding tilted XOR game due to 4. Recall that this reduction gives completeness \(\frac{3}{4}-\varepsilon\) and soundness \(\frac{3}{4}-\delta\) for some constant \(\delta>0\) and \(\varepsilon>0\) that may be chosen arbitrarily small. Now, consider the game \(G'_x\) where, with probability \(\frac{1}{2}\), \((G_x)_{\text{XOR}}\) is played and, with probability \(\frac{1}{2}\), \(G_\perp\) is played, which is the game where Alice is asked \(\perp\) and wins iff she responds with \(0\). By using the optimal strategy for \(G_x\), we have that \(\omega^\ast(G_x')\geq \frac{1}{2}\omega^\ast(G_x)+\frac{1}{2}\). Thus, we take \(c=\frac{1}{2}\parens*{\frac{3}{4}-\varepsilon}+\frac{1}{2}=\frac{7}{8}-\varepsilon\) to get completeness. Now we show soundness. Fix \(s=\frac{7}{8}-\eta\) with \(\eta\) to be specified later. If we suppose that for some strategy \(p\), \(\omega(G_x',p)\geq s\), we have that \[\begin{align} \omega(G_\perp,p)\geq2\parens*{s-\frac{1}{2}\omega\bigl((G_x)_{\text{XOR}},p\bigr)}\geq2\parens*{s-\frac{3}{8}}=1-2\eta. \end{align}\] But the value of \(G_\perp\) under strategy \(p\) is simply \(\require{physics} \Tr(P^{\perp}_0\rho_A)=\frac{1}{2}+\frac{1}{2}\Tr(A_\perp\rho_A)\). Hence, \[\begin{align} \norm[\big]{((A_\perp-I)\otimes I)\ket{\psi}}^2=4\braket{\psi}{P^\perp_1\otimes I}{\psi}\leq 8\eta. \end{align}\] Now consider the strategy \(p'\) for \(G_x\) with the same observables as \(p\) — this corresponds to the strategy for \((G_x)_{\text{XOR}}\) with \(A_\perp\) replaced by \(I\). We have that \[\begin{align} \omega(G_x,p') \geq\omega\bigl((G_x)_{\text{XOR}},p\bigr)-\norm[\big]{(A_\perp\otimes I)\ket{\psi}} \geq\frac{3}{4}-2\eta-2\sqrt{2\eta}. \end{align}\] Let \(\eta=\frac{\delta^2}{16}\). Then, \(\omega(G_x,S')\geq\frac{3}{4}-\frac{\delta^2}{8}-\frac{\delta}{\sqrt{2}}\geq\frac{3}{4}-\delta\), giving soundness for the reduction as well. ◻

Proof. The proof is the same proof as of 4, but where we keep all the algebraic equalities up to the action of the involving operators on the state \(\ket{\psi}\). ◻

Proof. It is known that \(\text{E3-LIN}_{1,1}^\text{co}\) is -hard [30]. We shall prove that \(\text{E3-LIN}_{1,1}^\text{co}\) reduces to \(\text{TXOR}_{\scriptscriptstyle \frac{3}{4},\frac{3}{4}}^\text{co}\). The proof is similar to the proof of 3.

Let \(G\) and \(\widetilde{G}\) be as in the proof of 3. We start with completeness. Assume \(G\) has commuting-operator value 1. Then, by [31], there are a Hilbert space \(H'\), a state \(\ket{\psi}\in H'\), and binary observables \(A_i\) and \(B_j\) such that \(A_i\) and \(B_j\) commute for all \(i,j\); for every variable \(v_i\), we have \(A_i\ket{\psi}=B_i\ket{\psi}\); and for every equation \(v_i\oplus v_j\oplus v_k=b\), we have that \([A_x,A_y]\ket{\psi}=0\) for every \(x,y\in\{i,j,k\}\) and \(A_iA_jA_k\ket{\psi}=(-1)^b\ket{\psi}\). Denote \(\mathcal{A}\) and \(\mathcal{B}\) the unital algebras generated by Alice and Bob observables, respectively. As in the proof of Lemma 8 in [31], we set \(H_0 = \overline{\mathcal{A}\ket{\psi}}=\overline{\mathcal{B}\ket{\psi}}\), and for every \(A,A'\in \mathcal{A}\), we have \(A\ket{\psi}=A'\ket{\psi}\) if and only if \(A|_{H_0}=A'|_{H_0}.\) A similar relation holds for the operators in \(\mathcal{B}\).

We will now produce a strategy for the tilted XOR game that succeeds with probability \(\frac{3}{4}\). Let the Hilbert space of the players be \(H = H_0\) and let their shared state be \(\ket{\psi}\). The following operators are defined up to their action on \(H\). For each cube within the tilted XOR game \(\widetilde{G}\) (as illustrated in 3), assign the operators \(A_i,A_j,\) and \(A_k\) to the vertices labelled \(i\), \(j\), and \(k\), and assign the operator \(I\) to the vertex labeled \(\perp\). For the remaining (odd parity) vertices of the cube, assign (separately for each cube) the binary observables \[\begin{align} \widetilde{B}_{111} &= \textstyle{\frac{1}{2}}(+(-1)^bI - B_i - B_j - B_k) \\[1mm] \widetilde{B}_{100} &= \textstyle{\frac{1}{2}}(-(-1)^bI + B_i - B_j - B_k) \\[1mm] \widetilde{B}_{010} &= \textstyle{\frac{1}{2}}(-(-1)^bI - B_i + B_j - B_k) \\[1mm] \widetilde{B}_{001} &= \textstyle{\frac{1}{2}}(-(-1)^bI - B_i - B_j + B_k). \end{align}\] Then it is a straightforward exercise to show that the above are proper binary observables and that the success probability of this strategy for the tilted XOR game \(\widetilde{G}\) is \(\frac{3}{4}\).

In the other direction, let \(\ket{\psi}, A_x,B_y\) be a commuting-operator strategy for the tilted XOR game \(\widetilde{G}\) that wins with probability \(\frac{3}{4}\). As in the proof of 3, it follows that the strategy succeeds in each of the tilted cube games with probability \(\frac{3}{4}\). It follows from 11, that for each equation of the form \(v_i\oplus v_j\oplus v_k=b\), the corresponding observables \(A_i,A_j\) and \(A_k\) commute (up to their action on \(\ket{\psi}\)) and \(A_iA_jA_k\ket{\psi}=(-1)^b\ket{\psi}\). Let \(B_{111},B_{100},B_{010}\) and \(B_{001}\) the corresponding Bob’s observables for the odd parity vertices (on the cube associated to the given equation). We also have, by 1, \[\begin{align} \sum_{y}H_{x,y}B_y\ket{\psi}&=\frac{1}{8}A_x\ket{\psi},\\ \sum_{x}H_{x,y}A_x\ket{\psi}&=\frac{1}{8}B_y\ket{\psi}. \end{align}\] Denote \(\mathcal{A}\) and \(\mathcal{B}\) the unital algebras generated by Alice and Bob observables, respectively. By similar arguments as in the proof of Lemma 8 in [31], we set \(H_0 =\overline{\mathcal{A}\ket{\psi}}=\overline{\mathcal{B}\ket{\psi}}\), and for every \(A,A'\in \mathcal{A}\), it holds that \(A\ket{\psi}=A'\ket{\psi}\) if and only if \(A|_{H_0}=A'|_{H_0}.\) Thus, the operators \(A_i|_{H_0}\), \(A_j|_{H_0}\), and \(A_k|_{H_0}\) commute and \(A_iA_jA_k|_{H_0}=(-1)^bI_{H_0}\). Since the choice of \(H_0\) is independent of the equation, we get that the collection of all operators \(A_i|_{H_0}\) is an operator solution for \(G\); thus \(\omega^{\text{co}}(G)=1\), as required. ◻

Proof. Let \(G'=(X\times Y, X\sqcup Y,\{0,1\},\{0,1\},\pi^{\text{orac}},V')\), where \(V'(a,b|(x,y),z)=\delta_{a+b,f'(x,y,z)}\) for \[f'(x,y,z)=\begin{cases}f(x,y)&z=y\\0&\text{else.}\end{cases}\] By construction, \(G'\) is an XOR game. Now, suppose \(p\) is a strategy for \(G^{\text{orac}}\). We may suppose without loss of generality that \(p((a,b),c|(x,y),z)=0\) if \(a+b\neq f(x,y)\). Then, defining \(p'(a,b|(x,y),z)=p((a,f(x,y)+a),b|(x,y),z)\), \(p'\) is a strategy for \(G'\) and \[\begin{align} \omega(G',p')&=\sum_{x\in X,y\in Y,a\in\{0,1\}}\frac{1}{2}\pi(x,y)\parens*{p'(a,a|(x,y),x)+p'(a,a+f(x,y)|(x,y),y)}\\ &=\sum_{x\in X,y\in Y}\sum_{a,b\in\{0,1\}:\,a+b=f(x,y)}\frac{1}{2}\pi(x,y)\parens*{p((a,b),a|(x,y),x)+p((a,b),b|(x,y),y)}\\ &=\omega(G^{\text{orac}},p). \end{align}\] Doing the same in the other direction and noting that the mapping \(p\mapsto p'\) preserves classical and quantum strategies, we have that \(\omega(G^{\text{orac}})=\omega(G')\) and \(\omega^\ast(G^{\text{orac}})=\omega^\ast(G')\).

Now, consider a deterministic correlation \(C((x,y),z)=(-1)^{g(x,y)+h(z)}\) for \(G'\). Then, the bias \[\begin{align} \beta(G',C)&=\sum_{x\in X,y\in Y}\frac{1}{2}\pi(x,y)\parens*{C((x,y),x)+(-1)^{f(x,y)}C((x,y),y)}\\ &=\sum_{x\in X,y\in Y}\frac{1}{2}\pi(x,y)(-1)^{g(x,y)}\parens*{(-1)^{h(x)}+(-1)^{f(x,y)+h(y)}}. \end{align}\] This is maximised by taking a function \(g(x,y)\) such that \((-1)^{g(x,y)}\parens*{(-1)^{h(x)}+(-1)^{f(x,y)+h(y)}}\) is non-negative, which happens at \(g(x,y)=h(x)\). This gives \[\begin{align} \beta(G',C)&=\sum_{x\in X,y\in Y}\frac{1}{2}\pi(x,y)\parens*{1+(-1)^{f(x,y)+h(x)+h(y)}}=\frac{1}{2}+\frac{1}{2}\omega(G,C_0), \end{align}\] where \(C_0(x,y)=(-1)^{h(x)+h(y)}\). Since \(C_0\) can be taken to be any deterministic correlation we get \(\beta(G')=\frac{1+\beta(G)}{2}\), as wanted.

Next, consider a quantum (vector) correlation \(C((x,y),z)=\braket{u_{x,y}}{v_z}\) for \(G'\). The bias is \[\begin{align} \beta(G',C)&=\sum_{x\in X,y\in Y}\frac{1}{2}\pi(x,y)\parens*{\braket{u_{x,y}}{v_x}+(-1)^{f(x,y)}\braket{u_{x,y}}{v_y}}. \end{align}\] To get the lower bound, note that by taking \(\ket{u_{x,y}}=\ket{v_x}\), we get that \[\begin{align} \beta(G',C)&=\sum_{x\in X,y\in Y}\frac{1}{2}\pi(x,y)\parens*{1+(-1)^{f(x,y)}\braket{v_x}{v_y}}=\frac{1}{2}+\frac{1}{2}\beta(G,C_0), \end{align}\] where \(C_0(x,y)=\braket{v_x}{v_y}\). Taking \(C_0\) to be an optimal quantum correlation for \(G\) gives \(\beta^\ast(G')\geq\frac{1}{2}+\frac{1}{2}\beta^\ast(G)\). To get the upper bound, note that \(\braket{u_{x,y}}{v_x}+(-1)^{f(x,y)}\braket{u_{x,y}}{v_y}\) is maximised among unit vectors \(\ket{u_{x,y}}\) by taking \(\ket{u_{x,y}}\) to be the normalisation of \(\ket{v_x}+(-1)^{f(x,y)}\ket{v_y}\). In this case, \[\begin{align} \beta(G',C)&=\sum_{x\in X,y\in Y}\frac{1}{2}\pi(x,y)\abs*{\ket{v_x}+(-1)^{f(x,y)}\ket{v_y}}\\ &=\sum_{x\in X,y\in Y}\frac{1}{2}\pi(x,y)\sqrt{2+2(-1)^{f(x,y)}\braket{v_x}{v_y}}\\ &\leq\sqrt{\frac{1}{2}+\frac{1}{2}\beta(G,C_0)}, \end{align}\] using Jensen’s inequality, with \(C_0\) as before. This gives the wanted upper bound, which is attained if and only if Jensen’s inequality is in fact an equality here. ◻

Proof. The classical value of \(G^{\Box,\text{orac}}\) follows immediately from 12. For the quantum value, note that, taking \(H_{x,y}=\frac{(-1)^{f(x,y)}}{16}\) to be the game matrix of \(G^{\Box}\), \(8H\) is orthogonal. As such, there exist unit vectors \(\ket{u_x},\ket{v_y}\in\R^4\) such that \(\braket{u_x}{v_y}=8H_{x,y}=\frac{(-1)^{f(x,y)}}{2}\). Hence \(G^{\Box}\) satisfies the necessary and sufficient condition of 12 for the upper bound on the quantum value of \(G^{\Box,\text{orac}}\) to be attained.

Note that, in the oracularisation of a tilted XOR game, the predicate corresponding to the tilted equation of the form \(b=f(\perp,y)\) becomes the pair of predicates \(V((a,b),c|(\perp,y),\perp)=\delta_{b,f(\perp,y)}\delta_{c,a}\) and \(V((a,b),c|(\perp,y),y)=\delta_{b,f(\perp,y)}\delta_{c,b}\). Thus, we may assume that upon receiving a query of the form \((\perp,y)\), Alice always outputs \((0,f(\perp,y))\) and upon receiving the query \(\perp\), Bob always outputs \(0\) (indeed, this will only increase their winning probability). Now, it is direct to see that any such quantum strategy for \(G^{\rotatebox[origin=c]{-30}{\scriptstyle\square},\text{orac}}\) corresponds to a quantum correlation \(C((x,y),z)=\braket{\psi}{A_{x,y}\otimes B_z}{\psi}\) for \({G^{\Box}}'\) where \(B_\perp=I\) and \(A_{\perp,y}=I\). Suppose \(C\) is an optimal quantum correlation for \({G^{\Box}}'\). Using [14], we have that \[\sum_{z\in X\sqcup Y}(-1)^{f'(x,y,z)}\pi^{\text{orac}}((x,y),z)(I\otimes B_z)\ket{\psi}=a_{x,y}(A_{x,y}\otimes I)\ket{\psi}.\] The optimal row bias \(a_{x,y}=\frac{\beta^\ast({G^{\Box}}')}{16}=\frac{\sqrt{3}}{32}\) and \(\pi^{\text{orac}}((x,y),z)\) is only nonzero if \(z=x\) or \(z=y\), so the above simplifies to \[(I\otimes B_x+(-1)^{f(x,y)}I\otimes B_y)\ket{\psi}=\sqrt{3}(A_{x,y}\otimes I)\ket{\psi}.\] Squaring both sides in the standard way gives \((B_x+(-1)^{f(x,y)}B_y)^2=3I\) on the support of \(\psi_B\), which simplifies to \(\{B_x,B_y\}=(-1)^{f(x,y)}I\). Since \(B_\perp=I\), we have that for all \(y\in X_1\) that \((-1)^{f(\perp,y)}I=\{I,B_y\}=2B_y\), so \(B_y=\pm\frac{I}{2}\). Repeating this again for \(x\in X_0\), we have that \((-1)^{f(x,y)}I=\{B_x,\pm\frac{I}{2}\}=\pm B_x\), so \(B_x=\pm I\). Therefore \(C\) is actually a classical correlation, and thus cannot attain the optimal quantum value of \({G^{\Box}}'\), leading to a contradiction. ◻

Proof. Let \(A,B,C\) be three binary observables, \(\alpha\in\{\pm 1\}\) and suppose that \(A\) commutes with \(B\) and with \(C\). Then, we have \[\require{physics} \Tr(A(B+\alpha C))\leq 1+\alpha\Tr(BC).\]

Indeed, \[\require{physics} 1+\alpha\Tr(BC)-\Tr(AB)-\alpha\Tr(AC)=\Tr((I-AB)(I-\alpha AC)),\] and the inequality follows as \(AB\) and \(\alpha AC\) are self-adjoint unitaries and the fact that for non-negative operators \(P\) and \(Q\), \(\require{physics} \Tr(PQ)\geq 0\).

Note that, in the oracularisation of a tilted XOR game, the predicate corresponding to the tilted equation of the form \(b=f(\perp,y)\) becomes the pair of predicates \(V((a,b),c|(\perp,y),\perp)=\delta_{b,f(\perp,y)}\delta_{c,a}\) and \(V((a,b),c|(\perp,y),y)=\delta_{b,f(\perp,y)}\delta_{c,b}\). Thus, we may assume that upon receiving a query of the form \((\perp,y)\), Alice always outputs \((0,f(\perp,y))\) and upon receiving the query \(\perp\), Bob always outputs \(0\) (indeed, this will only increase their winning probability). Now, it is direct to see that any such quantum oracularisable strategy for \(G^{\text{orac}}\) corresponds to a quantum oracularisable correlation \(C((x,y),z)=\tr (A_{x,y} B_z)\) for \((G_\text{XOR})'\) where \(B_\perp=I\) and \(A_{\perp,y}=I\). Recall that \((G_{\text{XOR}})'\) is the XOR game corresponding to the oracularisation of \(G_{\text{XOR}}\) constructed in 12.

To get the upper bound, consider such quantum oracularisable correlation \(C((x,y),z)=\tr(A_{x,y}B_z)\). We have \[\begin{align} \beta(G^{\text{orac}},C)&=\sum_{x\in X\backslash\{\perp\}, y\in Y}\frac{1}{2}\pi(x,y)\parens*{\tr(A_{x,y}B_x+(-1)^{f(x,y)}A_{x,y}B_y)}\\ &+\sum_{ y\in Y}\frac{1}{2}\pi(\perp,y)\parens*{\tr(I+(-1)^{f(x,y)}B_y)}\\ &\leq \frac{1}{2}+\frac{1}{2}\sum_{x\in X, y\in Y}\pi(x,y)(-1)^{f(x,y)}\tr(B_xB_y)\\ &=\frac{1}{2}+\frac{1}{2}\beta(G,C'), \end{align}\] where \(C'\) is the quantum correlation defined by \(C'(x,y)=\tr(B_xB_y)\). The upper bound follows by considering the supremum over all quantum correlations.

Finally, for the lower bound, fix a quantum oracularisable correlation for \(G_\text{XOR}\), \(C(x,y)=\tr(B_xB_y)\), with the convention that \(B_\perp=I\). We define a quantum oracularisable correlation for \(G_\text{XOR}'\), by setting \(C'((x,y),z)=\tr(B_xB_z)\). Since \(B_x\) and \(B_y\) commute (whenever \(\pi(x,y)>0\)), \(C'\) is a well defined quantum oracularisable correlation. Then, the bias is \[\begin{align} \beta(G^{\text{orac}},C')&=\sum_{x\in X, y\in Y}\frac{1}{2}\pi(x,y)\parens*{\tr(A_{x,y}B_x+(-1)^{f(x,y)}A_{x,y}B_y)}\\ &=\sum_{x\in X, y\in Y}\frac{1}{2}\pi(x,y)\parens*{\tr(I+(-1)^{f(x,y)}B_xB_y)}\\ &=\frac{1}{2}+\frac{1}{2}\beta(G,C). \end{align}\]

The lower bound follows by considering the supremum over all possible quantum oracularisable correlations \(C\). ◻

Proof. In [13], the authors construct a succinct E3-LIN protocol for the halting problem, while using the reduction of [37]. As observed in [35], the latter reduction preserves oracularisability. In particular, the YES instances of their reduction admit a perfect quantum oracularisable strategies. Evidently, the completeness argument in [13] also preserves oracularisability.

Next, we show that the completeness argument of the present work, namely, 7, can be adapted so that it will preserve oracularisability. Since for any nonlocal game we have \(\omega^*(G)\geq \omega^\ast_{\text{orac}}(G)\), this will complete the proof.

Let \(\{P^u_a\}_a\), \(\{\Pi_\textit{\boldsymbol{a}}\}_\textit{\boldsymbol{a}}\) and \(\ket{\psi}\) be as in 7, and suppose \(\ket{\psi}\) is the maximally entangled state, and that \([P^u_a,\Pi_\textit{\boldsymbol{a}}]=0\) for every \(u, a\) and \(\textit{\boldsymbol{a}}\). Here we are not changing \(\Pi_\textit{\boldsymbol{a}}\), allowing \(\Pi_\textit{\boldsymbol{a}}\neq0\) even if \(a_1+a_2+a_3=1\). Define the operators \(C_u\) similarly to their definition in 7. Note that they commute with \(A_{u'}=P^{u'}_0-P^{u'}_1\). The analysis of the success probability is similar to that in 7, with the only difference in the last inequality, which here turns to \(1-\varepsilon\leq\frac{1}{2}+\frac{4}{3}\beta(G^{\rotatebox[origin=c]{-30}{\scriptstyle\square}},C)-\frac{1}{6}+2\frac{\varepsilon}{6}\), using the fact that \(\sum_{a_1+a_2+a_3=1}\braket{\psi}{\Pi_\boldsymbol{a}\otimes I}{\psi}\leq \varepsilon\). Therefore, \(\beta(G^{\rotatebox[origin=c]{-30}{\scriptstyle\square}},C)\geq\frac{1}{2}-\varepsilon.\) ◻

Proof. Let \(c\) and \(s\) be as in 4 , fix \(x\in\{0,1\}^*\) and let \(G_x\) be the resulted tilted XOR game of our reduction for the input \(x\). If \(x\) is a no instance, then it is promised that \(\omega^\ast_{\text{orac}}(G_x)\leq\omega^*(G_x)\leq s\). Thus, by 13, we have \(\omega^\ast_{\text{orac}}(G_x^{\text{orac}})\leq\frac{1+\omega^*(G_x)}{2}\leq \frac{1+s}{2}.\)

If, instead, \(x\) is a yes instance (of the halting problem), then it follows the proof of 9, that \(\omega^\ast_{\text{orac}}(G_x)\geq c\). Again, by 13, we get \(\frac{1+c}{2}\leq \frac{1+\omega^\ast_{\text{orac}}(G_x)}{2}\leq \omega^\ast_{\text{orac}}(G^{\text{orac}}).\)

Thus, we can take \(s'=\frac{1+s}{2}\) and \(c'=\frac{1+c}{2}\). ◻

Proof. Let \(x\) be an instance of the halting problem and let \(G_x\) be the corresponding tilted XOR game constructed via the reduction of 9. We will show that \(\omega^\ast_{\text{orac}}(G_x)=\omega^\ast_{\text{orac}}\bigl((G_x)_{\text{XOR}}\bigr)\), getting \(\tsf{RE}\)-hardness for the quantum oracularisable value of XOR games. First, note that the distinguished question \(\perp\) in the tilted bipartite cube game is asked to Alice with every one of Bob’s questions. Hence, in \((G_x)_{\text{XOR}}\), Alice’s observable for \(\perp\) commutes with every one of Bob’s observables in any quantum oracularisable strategy. Fix a strategy for \((G_x)_{\text{XOR}}\) and let \(\Pi\) be the projector onto the \(1\) eigenspace of \(A_\perp\). Consider the new strategy with \(A_x\) replaced with \(\Pi A_x\Pi+(I-\Pi)A_x(1-\Pi)\). This has the same value as the original strategy since \(\Pi\) commutes with all the \(B_y\), and it has the property that \(A_\perp\) commutes with all the observables. Hence, we can multiply all the observables by \(A_\perp\) to get a strategy where \(A_\perp=I\) with the same value, as in the classical case. As such, \(\omega^\ast_{\text{orac}}(G_x)=\omega^\ast_{\text{orac}}\bigl((G_x)_{\text{XOR}}\bigr)\). Thus, we get the wanted hardness. ◻

Proof. Given an instance of the halting problem \(x\), let \(H_x\) be the E3-LIN instance constructed in [13], and let \(G_x\) be the (succinctly-presented) tilted XOR game constructed in 4. Let \(c_0=\frac{3}{4}-\varepsilon\) and \(s_0\) be the constants from 4. First, we show soundness. If \(x\) is a no instance of the halting problem, then \(\omega^{\ast}(G_x)< s_0\). Since every quantum tracial strategy is a quantum strategy, \(\omega^\ast_{\tr}(G_x)<s_0\) as well. To finish, we show completeness. Suppose \(x\) is a yes instance. Then, \(\omega^\ast(H_x)\geq 1-O(\varepsilon)\). But, using [38], [39], we know that near-perfect strategies for projection games may be rounded to tracial strategies. This gives that \(\omega^\ast_{\tr}(H_x)\geq 1-O(\varepsilon^{1/4})\). Due to 7, near-perfect quantum strategies for \(H_x\) give rise to near-optimal quantum strategies for \(G_x\), with the same shared state. In the current setting, this implies that that there is a near-optimal quantum strategy for \(G_x\) with a maximally-entangled state, and hence a near-optimal tracial strategy. Formally, we find \(\omega^\ast_{\tr}(G_x)\geq\frac{3}{4}-O(\varepsilon^{1/4})\). Taking \(c=\frac{3}{4}-O(\varepsilon^{1/4})\) and \(s=s_0\) gives the result. ◻

Proof. Let \(c_0=\frac{3}{4}-\varepsilon>s_0=\frac{3}{4}-\delta\) be the constants from 10. Due to the theorem, it is \(\tsf{RE}\)-hard to decide if the objective value of the following optimisation problem is \(\geq c_0\) or \(<s_0\): given a probability distribution \(\pi\) on \([n]^2\) and a function \(f:[n]^2\rightarrow\{0,1\}\), maximise \[\begin{align} \sum_{i,j\in[n]}\pi(i,j)\frac{1+(-1)^{f(i,j)}\tr(X_iX_j)}{2}, \end{align}\] where each \(X_i\) is a hermitian unitary and \(X_1=I\). This consists of equality and inequality relations; the main part of the reduction to Max-Cut consists of removing the equality relations. Fix an instance of this optimisation problem. We may assume without loss of generality that this instance is constructed from an E3-LIN instance via the construction used in this paper. Due to the construction based on the long code used in [13], the probabilities of sampling an equation of the form \(v_i\oplus v_j\oplus v_k=0\) and of the form \(v_i\oplus v_j\oplus v_k=1\) are equal in the E3-LIN instance. This implies that the probability of sampling an equality relation is exactly \(\frac{5}{16}\) (the two types of cubes are sampled with equal probability; see 3). Define two probability distribution \(\pi_0\) and \(\pi_1\) on \([n]^2\) as \(\pi_0(i,j)=\frac{16}{5}\pi(i,j)\) if \(f(i,j)=0\) and \(\pi_0(i,j)=0\) otherwise; and \(\pi_1(i,j)=\frac{16}{11}\pi(i,j)\) if \(f(i,j)=1\) and \(\pi_1(i,j)=0\) otherwise. By the above they are probability distributions, and they are disjoint by construction. Fix \(\Delta\in(0,1)\). Now, consider the following optimisation problem: maximise \[\begin{align} \sum_{i,j}\parens*{\frac{11}{16}\Delta\pi_1(i,j)\frac{1-\tr(X_iX_j)}{2}+\frac{5}{16}\Delta\pi_0(i,j)\frac{1-\tr(Y_iX_j)}{2}+(1-\Delta)\pi_0(i,j)\frac{1-\tr(Y_iX_i)}{2}}, \end{align}\] where the \(X_i\) and \(Y_i\) are hermitian unitaries, and \(X_1=I\). To show completeness, if the original instance had objective value \(\geq\frac{3}{4}-\varepsilon\), then we can take \(Y_{i}=-X_i\), and see that the new instance has objective value \(\geq\Delta\parens*{\frac{3}{4}-\varepsilon}+(1-\Delta)=1-\frac{1}{4}\Delta-\Delta\varepsilon\eqqcolon c\). To show soundness, suppose that there exists some \(\eta>0\) such that the objective value of the new instance is \(\geq1-\eta\eqqcolon s\). Then, we have in particular that \[\begin{align} \sum_{i,j}\pi_0(i,j)\frac{1-\tr(Y_iX_i)}{2}\geq\frac{1-\eta-\Delta}{1-\Delta}, \end{align}\] and hence \(\sum_{i,j}\pi_0(i,j)\norm{X_i+Y_i}_{f}^2\leq4\frac{\eta}{1-\Delta}\). This implies that \[\begin{align} \sum_{i,j}&\pi(i,j)\frac{1+(-1)^{f(i,j)}\tr(X_iX_j)}{2}\\ &\geq\sum_{i,j}\parens*{\frac{11}{16}\pi_1(i,j)\frac{1-\tr(X_iX_j)}{2}+\frac{5}{16}\pi_0(i,j)\frac{1-\tr(Y_iX_j)}{2}-\frac{5}{32}\pi_0(i,j)\norm{X_i+Y_i}_f}\\ &\geq\frac{\Delta-\eta}{\Delta}-\frac{5}{16}\sqrt{\frac{\eta}{1-\Delta}}. \end{align}\] Now take \(\Delta=\frac{\delta^2}{2}\) and \(\eta=(\frac{1}{4}+\frac{\delta}{2})\frac{\delta^2}{2}\). First, we have that \(s=1-\eta=1-\frac{\Delta}{4}-\frac{\delta\Delta}{2}<1-\frac{1}{4}\Delta-\Delta\varepsilon=c\) for \(\varepsilon\) small enough, giving positive completeness-soundness gap. Also, \[\begin{align} \frac{\Delta-\eta}{\Delta}-\frac{5}{16}\sqrt{\frac{\eta}{1-\Delta}}&=1-\parens*{\frac{1}{4}+\frac{\delta}{2}}-\frac{5}{16}\sqrt{\frac{(\frac{1}{4}+\frac{\delta}{2})\frac{\delta^2}{2}}{1-\frac{\delta^2}{2}}}\\ &\geq\frac{3}{4}-\frac{\delta}{2}-\frac{5}{16}\frac{\delta}{2}>\frac{3}{4}-\delta=s_0, \end{align}\] finishing the proof of soundness of the reduction. To finish, note that we can get rid of the probability distribution by duplicating edges. ◻