# Self-Testing in the Compiled Setting via Tilted-CHSH Inequalities

Arthur Mehta, Connor Paddock, Lewis Wooltorton

► To cite this version:

Arthur Mehta, Connor Paddock, Lewis Wooltorton. Self-Testing in the Compiled Setting via Tilted-CHSH Inequalities. TQC 2025 - Conference on the Theory of Quantum Computation, Communication and Cryptography, Sep 2025, Bengaluru (India), India. pp.8:1-8:19, 10.4230/LIPIcs.TQC.2025.8 . hal-05466801

HAL Id: hal-05466801

https://hal.science/hal-05466801v1

Submitted on 20 Jan 2026

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Self-testing in the compiled setting via tilted-CHSH inequalities

Arthur Mehta*¹, Connor Paddock†¹, and Lewis Wooltorton‡²,³,⁴

¹Department of Mathematics and Statistics, University of Ottawa, Canada

²Department of Mathematics, University of York, UK

³Quantum Engineering Centre for Doctoral Training, H. H. Wills Physics Laboratory and Department of Electrical & Electronic Engineering, University of Bristol, UK

⁴Inria, ENS de Lyon, LIP, 46 Allee d'Italie, 69364 Lyon Cedex 07, France

## Abstract

This work investigates the family of extended tilted-CHSH inequalities in the single-prover cryptographic compiled setting. In particular, we show that a quantum polynomial-time prover can violate these Bell inequalities by at most negligibly more than the violation achieved by two non-communicating quantum provers. To obtain this result, we extend a sum-of-squares technique to monomials with arbitrarily high degree in the Bob operators and degree at most one in the Alice operators. We also introduce a notion of partial self-testing for the compiled setting, which resembles a weaker form of self-testing in the bipartite setting. As opposed to certifying the full model, partial self-testing attempts to certify the reduced states and measurements on separate subsystems. In the compiled setting, this is akin to the states after the first round of interaction and measurements made on that state. Lastly, we show that the extended tilted-CHSH inequalities satisfy this notion of a compiled self-test.

## 1 Introduction

In a bipartite Bell scenario, two non-communicating provers receive inputs $x$ and $y$ and reply with outputs $a$ and $b$ to a verifier. The collection of probabilities of observing outcomes $(a, b)$ given $(x, y)$ determines a correlation $p = \{p(a, b|x, y)\}$. Bell's celebrated theorem implies that if the provers are permitted to share an entangled quantum state and make local quantum measurements, called a bipartite (quantum) model, then certain correlations have no realization by a classical (or local hidden-variable) model [Bel64]. The distinction between quantum and classical correlations is often explored through Bell inequalities. A Bell inequality is a linear inequality on the set of correlations which is satisfied by all classical correlations. Hence, these inequalities can be violated by certain models using quantum entanglement, realizing correlations that are not classical. The quantum value of a Bell inequality refers to the largest violation achievable by a bipartite (quantum) model. A prominent example is the Clauser-Horne-Shimony-Holt (CHSH) inequality, where the classical bound is 2, but the quantum value is $2\sqrt{2}$ [CHSH69].

Due to their ability to witness these non-classical effects, Bell inequality violations play a major role in areas like device-independent cryptography [ABG+07, Col07, PAM+10, PAB+09, Sca12],

<footnote>*amehta2@uottawa.ca</footnote>

<footnote>†cpaulpad@uottawa.ca</footnote>

<footnote>‡lewis.wooltorton@ens-lyon.fr</footnote>
protocols for verifiable delegated quantum computation [RUV13, Gri19, CGJV24], and in the study
of multiprover interactive proofs (MIPs) and the variant MIP* with entangled provers [CHTW04],
also called nonlocal games. Many of the key applications of Bell inequalities rely on a remarkable
property known as self-testing [MY04, MYS12, YN13, ŠB20]. Informally, a Bell inequality is a
self-test for an ideal bipartite (quantum) model Q if there exist local isometries which transform
any employed bipartite model Q' achieving maximum Bell violation into the ideal model Q. It is
well-known that the CHSH inequality is a self-test for the bipartite model employing a maximally
entangled state on two qubits, along with the Pauli σₓ and σᵧ measurements, among others [MY04].
Another prominent example is the family of tilted-CHSH inequalities [AMP12, YN13, BP15], which
self-test partially entangled two-qubit states, and were integral in the work of Coladangelo, Goh,
and Scarani who employed them as part of a protocol to self-test any pure bipartite entangled state
[CGS17].

Despite the enormous success of self-testing, a practical drawback is the requirement of mul-
tiple non-communicating quantum provers. Recently, a number of cryptographic approaches have
been proposed that replace the non-communication assumption with computational assumptions
[KLVY23, MV21, KMCVY22]. This makes the setting more practical by having a single quan-
tum prover, rather than multiple. One new and prominent approach is the Kalai-Lombardi-
Vaikuntanathan-Yang (KLVY) compilation procedure introduced in [KLVY23], which transforms
a 2-prover 1-round Bell scenario into a 1-prover 2-round scenario with a single computationally
bounded prover. The core ingredient in the KLVY compilation procedure is quantum homomor-
phic encryption (QHE), which emulates, to a certain extent, the non-communication between the
rounds of interaction. In the compiled game, the inputs to the prover happens sequentially. In the
first round, the prover obtains an encryption $\chi$ of the input $x$ from the verifier. Without breaking
the security, the prover cannot distinguish between encryptions of different inputs. The prover per-
forms a polynomial time quantum circuit on $\chi$, and then returns an output $\alpha$ to the verifier. In the
second round, the information about $x$ has already been “hidden” from the prover, so the verifier
can send input $y$ in the plain (i.e. unencrypted) to the prover, upon which the prover can perform a
measurement and return outcome $b$ to the verifier. The verifier checks for a Bell inequality violation
(across many such interactions) using the values of $x$, the decryption of $\alpha$, along with $(y, b)$. QHE
has two key features that makes this resemble the bipartite setting. Firstly, it allows the first round
quantum prover to perform measurements as they would have in the bipartite setting, without
knowing the input. Secondly, the encryption ensures that no classical polynomial-time prover can
violate a Bell inequality by more than an negligible amount (see Section 3 details). Both of these
facts are non-trivial and were the subject of [KLVY23].

In a follow-up work, Natarajan and Zhang showed that the maximal quantum violation of the
CHSH inequality in the compiled setting is bounded by the maximal violation in the bipartite set-
ting, up to negligible factors in the security parameter [NZ23]. Subsequent works have analyzed the
quantum soundness of the KLVY compilation procedure for other multiprover scenarious, includ-
ing all 2-player XOR nonlocal games [CMM+24], Bell inequalities tailored to maximally entangled
bipartite states [BVB+24], delegated quantum computation with a single-device [NZ23, MNZ24],
and even in the study of contextuality [ABCC24]. Despite these advancements, many results have
yet to be reproduced in the compiled setting. Our work takes another step in growing the list of
protocols that will function as desired in the compiled setting.

**Upper bounding compiled Bell violations** As mentioned, the compiled value of a Bell in-
equality is always at least the quantum value. This is because any bipartite (quantum) model can
be implemented with homomorphic encryption via a *correctness* property of the QHE scheme used
in the procedure. On the other hand, establishing upper bounds on the largest violation possible
in the compiled setting is challenging, as general techniques for bounding these violations depend
on the spatial separation between the two provers. Nonetheless, upper bounds on the violations of
a certain Bell inequalities in the compiled setting can be verified using the sum-of-squares (SOS)
technique [NZ23, CMM$^+$24, BVB$^+$24]. The SOS approach is a powerful method and has been
used extensively to upper bound Bell inequality violations and the values of nonlocal games in
the bipartite setting. Informally, this technique relates the maximum compiled value $\eta$, of a Bell
functional $I$, to a decomposition of the Bell operator or Bell polynomial $S$ as a sum of Hermitian
squares, $\eta 1 - S = \sum_i P_i^\dagger P_i$. Before our work, progress was made on realizing this approach in
the compiled setting, however, there were some limitations. In particular, it was required that the
polynomials $P_i$ involved in the decomposition were at most degree two in both Alice's and Bob's
observables, restricting the technique to Bell inequalities with an SOS decomposition of this form;
this excludes, for example, the family of tilted-CHSH inequalities.

Our first result extends the SOS technique to a larger family of Bell polynomials. More specif-
ically, we extend the pseudo-expectation techniques in [NZ23, CMM$^+$24] to allow for evaluations
on polynomial terms $P_i$ that consist of arbitrary monomials in the algebra generated by Bob's
observables. In Theorem 3.3 we prove that an extended pseudo-expectation will be positive on the
corresponding Hermitian square $P_i^\dagger P_i$ for any such term $P_i$. Consequently, we show that for any
Bell inequality with an SOS decomposition in which $P_i$ are of the form $P_i = \sum_j \gamma_j (A_x)^{k_j} w_j(B)$
for some $\gamma_j \in \mathbb{C}$, $k_j \in \{0, 1\}$ and $w_j(B)$ being arbitrary monomials in Bob's observables, $\eta$ is an
upper-bound on the maximum compiled quantum value. Our extension captures a wide class of Bell
inequalities including tilted-CHSH, enabling us to bound the compiled value of the tilted-CHSH
inequalities, by the quantum value and a negligible function of security parameter, see Theorem 3.5
for details.

**A compiled self-testing result** Our second contribution is a concept of self-testing in the compiled setting. One of the main obstacles to deriving self-testing results in the compiled setting is the lack of techniques for extracting any algebraic relations on the measurement operators acting under the encryption. Nevertheless, it remains possible to derive relations on the observables in the second round. With this in mind, we consider a partial notion of self-testing that applies to the measurements made by the prover in the second round. In particular, our definition only requires the existence of an isometry robustly certifying the ideal post-measurement state after the first round, and the action of the measurements made in the second; see Theorem 4.5 for details.

As our final result, we provide an example by showing violations of the compiled tilted-CHSH
inequalities satisfy this notion of partial self-testing. This family of inequalities was introduced by
Acín, Massar, and Pironio [AMP12], and the Bell functionals take the form $\alpha_\theta \langle A_0 \rangle + \langle A_0 B_0 \rangle +
\langle A_0 B_1 \rangle + \langle A_1 B_0 \rangle - \langle A_1 B_1 \rangle$, where $\langle A_x B_y \rangle$, $\langle A_x \rangle$
denote the expectation of measurements corre-
sponding to settings $X = x$, $Y = y$, and $\alpha_\theta \in \mathbb{R}$. Notably, they are tailored to robustly self-test
the two qubit states $\cos(\theta)|00\rangle + \sin(\theta)|11\rangle$ [YN13, BP15], and were used as part of a more complex
protocol to obtain self-testing for all pure bipartite entangled states [CGS17]. The work of Barizien,
Sekatski, and Bancal [BSB24] extended this family to include extra degrees of freedom in Bob's
measurements, which we will refer to as “extended” tilted-CHSH inequalities.

We apply Theorem 3.3 to the SOS decomposition for the extended tilted-CHSH inequalities
presented in [BSB24]. Specifically, in Theorem 3.5 we prove that the maximum quantum value
achieved for any of the extended tilted-CHSH functionals is preserved by the KLVY compilation
procedure. Then in Theorem 4.6 we use this same decomposition to prove that this family of games
is a compiled self-test according to Theorem 4.5.
**Related work** A recent work of [KMP$^{+24}$] implies that the compiled value of any 2-prover Bell scenario is bounded by the largest violation possible among so-called *commuting operator models*. However, unlike some previous results, such as [BVB$^{+24}$, CMM$^{+24}$], the upper bound in [KMP$^{+24}$] lacks a dependence on the security parameter $\lambda$, making it unclear how the compiled value is related to the quantum value at fixed security parameters. Hence, results such as ours, which obtain a bound on the compiled value that depends negligibly on the security parameter, remain of great importance. Furthermore, [KMP$^{+24}$] also considers a notion of self-testing in the compiled setting, however, due to their methods the results are in terms of commuting operator self-tests (as defined in [PSZZ23, Proposition 7.8]) and only hold in the limit of the security parameter $\lambda \to \infty$.

Another related work is [MV21], which presents a protocol for certifying that an unknown computationally bounded device has prepared a maximally entangled pair of qubits, and whether a measurement was performed on each qubit in either the computational or Hadamard basis. The techniques used to prove our compiled self-test have similarities to those of [MV21], particularly in the choice of isometry (see Definition 4.5) and proof structure, which in turn resembles self-testing techniques in the bipartite setting [BP15]. There are however some key differences. Firstly, [MV21] certifies the preparation of a maximally entangled state by the device before any measurements are made. While our results are tailored to the more general class of partially entangled states, we only make statements about the post-measurement states after each round. It is an interesting open question if our results can be extended in this way (see Section 4.1 for more details), and statements weaker than certifying the prepared state could also be possible. For example, can a compiled self-test be used to show the prepared state must have been entangled? Another significant difference to [MV21] is that the self-testing protocol in this work strongly resembles the bipartite case, owing to the compilation procedure mapping bipartite nonlocal scenarios to single prover scenarios. Our main result can therefore be interpreted as translating a self-testing statement in the Bell scenario to one in the compiled Bell scenario. On the other hand, the authors of [MV21] describe their approach as more “custom”, guided by the available cryptographic primitives, and pose the open question of finding a general procedure for translating self-testing results from the nonlocal setting. We showed this is possible for the special case of titled-CHSH inequalities.

**Future outlook** Moving forward, we consider several natural directions for following up on this work:

1. Tilted-CHSH inequalities were an integral component of the self-testing for all pure bipartite entangled states [CGS17]. Building off of our work on compiled tilted-CHSH inequalities, a natural question is whether similar results can be obtained in the compiled setting.

2. It would be desirable to understand the fundamental limitations of our notion of self-testing and other similar notions such as the computational self-testing given in [MV21]. Furthermore, is a finer notion of self-testing in the compiled setting that characterizes both Alice's and Bob's operators and the initial state possible without specifying the underlying QHE scheme? Moreover, is every self-test in the standard Bell scenario also a compiled self-test, and vice-versa?

3. Many current techniques for bounding the value of compiled nonlocal games/Bell inequalities can be obtained using some variant of the sum-of-squares decomposition approach. Given our improvements to this approach outlined in Theorem 3.3, it is possible to search for valid decompositions which include arbitrary words in Bob's operators. Is it possible to use this approach to give a limited variant of the NPA hierarchy [NPA08] in the compiled setting?
# Acknowledgments

The authors thank Simon Schmidt, Ivan Šupić, Anand Natarajan, and Tina Zhang for helpful discussions. We also thank the anonymous TQC reviewers for valuable feedback. AM is supported by the NSERC Alliance Consortia Quantum grants program, reference number: ALLRP 578455 - 22 and the NSERC Discovery Grants program 2024-06049. CP is supported by the Digital Horizon Europe project FoQaCiA, Foundations of quantum computational advantage, grant no. 101070558, and the Natural Sciences and Engineering Research Council of Canada (NSERC) reference number: ALLRP 578455 - 22. LW is supported by the Engineering and Physical Sciences Research Council (EPSRC Grant No. EP/SO23607/1) and the European Union's Horizon Europe research and innovation programme under the project "Quantum Security Networks Partnership" (QSNP, grant agreement No. 101114043).

# 2 Background

## 2.1 Mathematical notation

Throughout the article, Hilbert spaces are denoted by $\mathcal{H}$, and are assumed to be finite-dimensional unless explicitly stated otherwise. Elements of $\mathcal{H}$ are denoted by $|v\rangle \in \mathcal{H}$, where the inner product $\langle u|v\rangle$ for $|v\rangle, |u\rangle \in \mathcal{H}$ is linear in the second argument and defines the vector norm $|||v\rangle|| = \sqrt{\langle v|v\rangle}$. Quantum pure states are the norm 1 elements of $\mathcal{H}$. In this work, $\mathbb{B}(\mathcal{H})$ denotes the unital $\dagger$-algebra of bounded linear operators on $\mathcal{H}$ with norm $||M||_\text{op}^2 = \sup_{|v\rangle \in \mathcal{H}, |v\rangle \neq 0} \langle v|M^\dagger M|v\rangle/\langle v|v\rangle$. We also write $||A||_2 = \sqrt{\text{tr}(A^\dagger A)}$ to denote the Schatten 2-norm for $A \in \mathbb{B}(\mathbb{C}^d) \cong M_d(\mathbb{C})$. The unit in $\mathbb{B}(\mathcal{H})$ is denoted by $1$, and we write $|M| = \sqrt{M^\dagger M}$ for the positive part of $M \in \mathbb{B}(\mathcal{H})$. Given a finite set $\mathcal{A}$, a collection of positive operators $\{M_a \ge 0 : a \in \mathcal{A}\}$ with the property that $\sum_{a \in \mathcal{A}} M_a = 1$, is called a POVM over $\mathcal{A}$. When the operators in a POVM are orthogonal projections, we call it a PVM. Given a random variable $X$, which takes values $X = x \in \mathcal{X}$ according to a distribution $\mu: \mathcal{X} \to \mathbb{R}_{\ge 0}$ such that $\sum_{x \in X} \mu(x) = 1$, we denote the expectation of $X$ by $\mathbb{E}[X] = \sum_{x \in \mathcal{X}} \mu(x) \cdot x$. For $a, b \in \mathbb{R}$ and $\delta > 0$, $a \approx_{\delta} b$ is short for $|a - b| \le \delta$. A function $\text{negl}: \mathbb{N} \to \mathbb{R}$ is called negligible if for all $k \in \mathbb{N}$ there exists $N \in \mathbb{N}$ such that for every $n \ge N$ it holds that $\text{negl}(n) \le \frac{1}{n^k}$.

## 2.2 Bell scenarios, inequalities, and violations

Before we discuss compiled Bell inequalities, let us recall the bipartite case. Here we let $\mathcal{A}, \mathcal{B}, \mathcal{X}$, and $\mathcal{Y}$ be finite sets, with $|\mathcal{A}| = m_A, |\mathcal{B}| = m_B, |\mathcal{X}| = n_A$, and $|\mathcal{Y}| = n_B$. A bipartite Bell scenario is described by the tuple $\mathcal{S} = (\mathcal{A}, \mathcal{B}, \mathcal{X}, \mathcal{Y}, \pi)$, where $\pi: \mathcal{X} \times \mathcal{Y} \to \mathbb{R}_{\ge 0}$ is a distribution over the measurement settings. In a scenario, each party receives an input $x \in \mathcal{X}$ (resp. $y \in \mathcal{Y}$) sampled according to $\pi$, and returns outputs $a \in \mathcal{A}$ (resp. $b \in \mathcal{B}$). The parties are non-communicating, and therefore cannot coordinate their outputs. The behaviour of the provers is characterized by a correlation, a set of conditional probabilities $\mathbf{p} = \{p(a, b|x, y) : a \in \mathcal{A}, b \in \mathcal{B}, x \in \mathcal{X}, y \in \mathcal{Y}\}$, which is realized by an underlying physical theory or model. In the quantum setting, we allow the provers to share a bipartite quantum state, and say the correlation $\mathbf{p}$ is realized by a **bipartite (quantum) model**

$$Q = (\mathcal{H}_A, \mathcal{H}_B, \{\{M_{a|x}\}_{a \in \mathcal{A}}\}_{x \in \mathcal{X}}, \{\{N_{b|y}\}_{b \in \mathcal{B}}\}_{y \in \mathcal{Y}}, |\Psi\rangle_{AB}), \quad (2.1)$$

where $\mathcal{H}_A$ and $\mathcal{H}_B$ are Hilbert spaces, $\{M_{a|x}\}_{a \in \mathcal{A}}$ and $\{N_{b|y}\}_{b \in \mathcal{B}}$ are POVMs on $\mathcal{H}_A$ and $\mathcal{H}_B$ respectively, and $|\Psi\rangle_{AB}$ is a vector state in $\mathcal{H}_A \otimes \mathcal{H}_B$. More generally, a correlation $\mathbf{p}$ is quantum (or an element of $C_q(n_A, n_B, m_A, m_B)$) if there exists a bipartite model $Q$ for which $\mathbf{p}$ can be realized
via the Born rule as $p(a, b|x, y) = \langle\Psi|M_{a|x} \otimes N_{b|y}|\Psi\rangle$. We denote the class of bipartite (quantum) models by $\mathcal{Q}(n_A, n_B, m_A, m_B)$. From now on we will refer to such models simply as **bipartite models**.

In contrast to the set of quantum correlations, we have the collection of local correlations $C_{\text{loc}}(n_A, n_B, m_A, m_B)$. These are the correlations $\{p(a, b|x, y)\}$ for which there exists a **classical model**, that is a probability distribution $\mu_k$ and a local distributions $p_k^A(a|x)$ and $p_k^B(b|y)$ such that $p(a, b|x, y) = \sum_k \mu_k p_k^A(a|x) p_k^B(b|y)$. We let $C = (\mu_k, \{p_k^A\}, \{p_k^B\})$ denote a **classical model** and let $\mathcal{L}(n_A, n_B, m_A, m_B)$ denote the class of all classical models. In what follows we consider Bell scenarios where $n_A = n_B = n$, and $m_A = m_B = m$. With this notation Bell's theorem [Bel64] states that $C_{\text{loc}}(2, 2)$ is a strict subset of $C_q(2, 2)$.

Given a Bell scenario $\mathcal{S}$, one can consider a linear (or Bell) functional on the set of correlations

$$I = \sum_{a \in \mathcal{A}, b \in \mathcal{B}, x \in \mathcal{X}, y \in \mathcal{Y}} w_{abxy} p(a, b|x, y), \qquad (2.2)$$

for coefficients $w_{abxy} \in \mathbb{R}$. A **Bell inequality** is a functional $I$ and a bound $\eta > 0$ such that $I \le \eta$ for all $\mathbf{p} \in C_{\text{loc}}(n, m)$. Given a functional $I$, the classical value is the maximal value achieved by the classical correlations $\mathbf{p} \in C_{\text{loc}}(n, m)$. We denote this value by $\eta^L := \sup_{\mathbf{p} \in C_{\text{loc}}(m, n)} I$. The quantum value for $I$ is the maximal value achieved by the set of quantum correlations $\mathbf{p} \in C_q(m, n)$, and we denote the quantum value on $I$ by $\eta^Q := \sup_{\mathbf{p} \in C_q(m, n)} I$. Hence, a Bell violation occurs whenever there is a $\mathbf{p} \in C_q(m, n)$ for which $I > \eta^L$. A violation of a Bell inequality by non-communicating provers employing a quantum model is an indication of entanglement between provers.

Typically when $\eta^L$ is known for a given $I$, the main challenge is finding an upper bound on $\eta^Q$. In this case, one often considers the **Bell operator**$^1$ $S = \sum_{abxy} w_{abxy} M_{a|x} \otimes N_{b|y}$, and $\langle S \rangle = \langle\Psi|S|\Psi\rangle$ its quantum expectation with respect to $|\Psi\rangle \in \mathcal{H}_A \otimes \mathcal{H}_B$. Since bipartite models with separable quantum states generate the classical correlations $C_q(m, n)$, $\langle\Psi|S|\Psi\rangle \le \eta^L$ whenever $|\Psi\rangle$ is separable (unentangled). However, it's possible that there could be entangled states for which $\langle\Psi'|S|\Psi'\rangle > \eta^L$. Hence, given a Bell operator $S$, we can recover the maximum classical and quantum values $\eta^L = \sup_{C \in \mathcal{L}(n, m)} \langle S \rangle$ and $\eta^Q = \sup_{Q \in \mathcal{Q}(n, m)} \langle S \rangle$ respectively. Technically, we have not fixed the dimensions of the Bell operator as we want to consider any finite-dimensional model. Hence, the supremum is implicitly over all finite-dimensional Hilbert spaces $\mathcal{H}_A \otimes \mathcal{H}_B$.

An approach to establishing upper bounds on $\langle S \rangle$ is using sum-of-squares techniques. Let $S$ be a Bell operator and $\eta' > 0$. The shifted Bell operator $\eta'1 - S$ admits a **sum-of-squares** (SOS) decomposition if there exists a set of polynomials $\{P_i\}_{i \in \mathcal{I}}$ in the elements $\{M_{a|x}, N_{b|y} : a \in \mathcal{A}, b \in \mathcal{B}, x \in \mathcal{X}, y \in \mathcal{Y}\}$ satisfying $\eta'1 - S = \sum_{i \in \mathcal{I}} P_i^\dagger P_i$. The existence of an SOS decomposition for the operator $\eta'1 - S$ implies that $\eta'1 - S$ is positive, and therefore $\eta'$ is an upper bound on the maximum quantum value of $\langle S \rangle$. Additionally, if $\eta'$ is achievable by a bipartite model, then we write $\eta' = \eta^Q$. In this case, the shifted Bell operator is $\bar{S} = \eta^Q1 - S$, and observing $\langle\Psi|\bar{S}|\Psi\rangle = 0$ implies the constraints $P_i|\Psi\rangle = 0$ for all $i \in \mathcal{I}$; these constraints can often be used to infer the algebraic structure (rigidity) of the measurements $\{M_{a|x}\}_{a \in \mathcal{A}, x \in \mathcal{X}}$, $\{N_{b|y}\}_{b \in \mathcal{B}, y \in \mathcal{Y}}$ which achieve $\langle S \rangle = \eta^Q$.

## 3 Compiled Bell scenarios

The compilation procedure of a Bell scenario is essentially the same as the procedure for compiling nonlocal games outlined in [KLVY23]. Let $\mathcal{S} = (\mathcal{X}, \mathcal{Y}, \mathcal{A}, \mathcal{B}, \pi)$ be a 2-prover Bell scenario and fix

<footnote n="1">¹For a more mathematically rigorous treatment of Bell operators and the SOS approach consult [CMM+24].</footnote>
a quantum homomorphic encryption scheme with security against quantum distinguishers and correctness with respect to auxiliary input. Readers unfamiliar with QHE schemes and these properties can refer to Theorem A.2 found in the appendix.

A compiled Bell scenario is the following 2-round single-prover scenario. To setup, the verifier samples a secret key sk ← Gen(1^λ). Then, the verifier samples a pair of inputs (x, y) ∈ X × Y according to the distribution π : X × Y → R≥0, and encrypts the first input as the ciphertext χ ← Enc(sk, x).

1. The verifier sends the ciphertext χ to the prover. The prover replies with a ciphertext α encoding their output. The verifier decrypts obtaining outcome a ← Dec(sk, α) from A.

2. The verifier sends the sampled (plaintext) input y ∈ Y to the prover, who replies with another outcome b ∈ B.

In the compiled scenario, for a chosen security parameter λ, the prover prepares an initial quantum polynomial time (QPT) preparable state |Ψ(λ)⟩ ∈ Ĥ(λ) where Ĥ(λ) is a single Hilbert space (see Theorem A.1 for details on efficient quantum procedures). Then, the first round of the protocol is characterized by a family of POVMs {{M̃(λ) α |χ }} α ∈ Ā}χ ∈ ¯X and unitaries {U(λ) α ,χ } α ∈ Ā,χ ∈ ¯X, where ¯X and Ā are the set of all valid ciphertexts of the first round input and output, respectively. Unlike in the bipartite setting, we must account for unitary operations applied to the post-measurement state in the first round. With this in mind, we denote the sub-normalized post-measurement state given the measurement over ciphertext χ and encrypted outcome α by

$$
U_{\alpha, \chi}^{(\lambda)} \tilde{M}_{\alpha|\chi}^{(\lambda)} |\Psi^{(\lambda)}\rangle := |\Psi_{\alpha|\chi}^{(\lambda)}\rangle. \quad (3.1)
$$

Note that these vectors are sub-normalized. In particular, the probability of obtaining α ∈ Ā given χ ∈ ¯X is given by ⟨Ψ(λ) α |χ |Ψ(λ) α |χ ⟩. In the second round, the device makes a POVM measurement {{N(λ) b |y }} b ∈B}y ∈Y, where the resulting conditional probability is given by

$$
\langle \Psi^{(\lambda)} | \widetilde{M}_{\alpha|\chi}^{(\lambda)} \dagger U_{\alpha,\chi}^{(\lambda)} \dagger N_{b|y}^{(\lambda)} U_{\alpha,\chi}^{(\lambda)} \widetilde{M}_{\alpha|\chi}^{(\lambda)} | \Psi^{(\lambda)} \rangle = \langle \Psi_{\alpha|\chi}^{(\lambda)} | N_{b|y}^{(\lambda)} | \Psi_{\alpha|\chi}^{(\lambda)} \rangle, \quad (3.2)
$$

for a fixed, λ ∈ N, sk ← Gen(1^λ), ciphertexts χ ∈ ¯X, α ∈ Ā, and plaintexts y ∈ Y, b ∈ B.

To summarize, for a fixed QHE scheme, λ ∈ N, a compiled (quantum) model is given by a tuple

$$
\tilde{Q}^{(\lambda)} = (\tilde{\mathcal{H}}^{(\lambda)}, \{|\Psi_{\alpha|\chi}^{(\lambda)}\rangle\}_{\alpha \in \bar{\mathcal{A}}, \chi \in \bar{\mathcal{X}}}, \{{N_{b|y}^{(\lambda)}}\}_{b \in \mathcal{B}}\}_{y \in \mathcal{Y}}), \quad (3.3)
$$

where all the relevant measurements and states are obtained by some QPT procedure. We remark that one can consider a description of the model which includes the initial state |Ψ(λ)⟩ and the operators {U(λ) α ,χ ̃M(λ) α |χ } α ∈ ¯A,χ ∈ ¯X, rather than the post-measurement states |Ψ(λ) α |χ⟩. Hence, ˜Q(λ) is really a coarse description of a quantum model in the compiled setting. The joint distribution of the outcomes after both rounds is given by

$$
p^{(\lambda)}(a, b|x, y) = \mathbb{E}_{\text{sk} \leftarrow \text{Gen}(1^{\lambda})} \mathbb{E}_{\chi: \text{Enc}(x)=\chi} \sum_{\alpha: \text{Dec}(\alpha)=a} \langle \Psi_{\alpha|\chi}^{(\lambda)} | N_{b|y}^{(\lambda)} | \Psi_{\alpha|\chi}^{(\lambda)} \rangle. \quad (3.4)
$$

Note that the marginal distribution p(λ)(a|x) obtained from Eq. (3.4) will be independent of the second input y due to the sequential nature of the protocol. However, the marginal p(λ)(b|y, x) currently depends on x. The aim of what follows is to establish a computational independence between this distribution and the inputs x. To do so we will need to consider the distributions
of the decrypted outputs and appeal to the security promise of the QHE scheme. Specifically, we require a key lemma which has appeared in several works [NZ23, CMM+24, BVB+24]. We borrow a version from [KMP+24] and we refer the reader to the reference for the proof.

**Lemma 3.1** ([KMP+24], Proposition 4.6). Let $\tilde{Q}^{(\lambda)}$ be a compiled quantum model, and $\mathcal{N}^{(\lambda)} = w(\{N_{b|y}^{(\lambda)}\}_{b \in \mathcal{B}, y \in \mathcal{Y}})$ be a monomial in the measurement operators $\{N_{b|y}^{(\lambda)}\}_{b \in \mathcal{B}, y \in \mathcal{Y}}$, where $\lambda \in \mathbb{N}$ is the security parameter for a fixed QHE scheme. Then, for any two QPT sampleable distributions $\mathcal{D}_1, \mathcal{D}_2$ over plaintext inputs $x \in \mathcal{X}$ there exists a negligible function $\text{negl}(\lambda)$ of the security parameter $\lambda$ such that the following holds

$$ \left| \mathbb{E}_{\text{sk} \leftarrow \text{Gen}(1^{\lambda})} \mathbb{E}_{x \leftarrow \mathcal{D}_1} \mathbb{E}_{\chi: \text{Enc}(x) = \chi} \sum_{\alpha \in \bar{\mathcal{A}}} \langle \Psi_{\alpha|\chi}^{(\lambda)} | \mathcal{N}^{(\lambda)} | \Psi_{\alpha|\chi}^{(\lambda)} \rangle - \mathbb{E}_{\text{sk} \leftarrow \text{Gen}(1^{\lambda})} \mathbb{E}_{x \leftarrow \mathcal{D}_2} \mathbb{E}_{\chi: \text{Enc}(x) = \chi} \sum_{\alpha \in \bar{\mathcal{A}}} \langle \Psi_{\alpha|\chi}^{(\lambda)} | \mathcal{N}^{(\lambda)} | \Psi_{\alpha|\chi}^{(\lambda)} \rangle \right| \le \text{negl}(\lambda). $$

The approximate no-signalling conditions from Alice to Bob can then be seen by applying Theorem 3.1 to the monomials of degree 1 in the QPT measurement operators $\{N_{b|y}^{(\lambda)}\}_{b \in \mathcal{B}, y \in \mathcal{Y}}$, since

$$ \left| \mathbb{E}_{\text{sk} \leftarrow \text{Gen}(1^{\lambda})} \mathbb{E}_{\chi: \text{Enc}(x) = \chi} \sum_{\alpha \in \bar{\mathcal{A}}} \langle \Psi_{\alpha|\chi}^{(\lambda)} | N_{b|y}^{(\lambda)} | \Psi_{\alpha|\chi}^{(\lambda)} \rangle - \mathbb{E}_{\text{sk} \leftarrow \text{Gen}(1^{\lambda})} \mathbb{E}_{\chi: \text{Enc}(x') = \chi} \sum_{\alpha \in \bar{\mathcal{A}}} \langle \Psi_{\alpha|\chi}^{(\lambda)} | N_{b|y}^{(\lambda)} | \Psi_{\alpha|\chi}^{(\lambda)} \rangle \right| \le \text{negl}(\lambda) \quad (3.5) $$

holds for all $b \in \mathcal{B}, y \in \mathcal{Y}$ and $x, x' \in \mathcal{X}$ with $x \neq x'$.

In the above statements, the measurements are completely general, and the states are sub-normalized vectors. The following lemma shows that when considering the compiled value, we can assume that the states and measurement operators in the compiled strategy are pure and projective.

**Lemma 3.2.** Let $\mathcal{H}^{(\lambda)}$ be the Hilbert space of the device, and $\{\{\rho_{\alpha|\chi}^{(\lambda)}\}_{\alpha \in \bar{\mathcal{A}}}\}_{\chi \in \bar{\mathcal{X}}}^{}$ be a family of QPT-preparable sub-normalized states on $\mathcal{H}^{(\lambda)}$ after the first round. Let $\{\{N_{b|y}^{(\lambda)}\}_{b \in \mathcal{B}}\}_{y \in \mathcal{Y}}^{}$ be a family of QPT-implementable POVMs on $\mathcal{H}^{(\lambda)}$, which induce the behaviour $p^{(\lambda)}(\alpha, b|\chi, y) = \text{tr}[N_{b|y}^{(\lambda)} \rho_{\alpha|\chi}^{(\lambda)}]$. Then there exists a Hilbert space $\mathcal{H}^{(\lambda)}$, a family of QPT-preparable sub-normalized states $\{|\Psi_{\alpha|\chi}^{(\lambda)}\}_{\alpha \in \bar{\mathcal{A}}}\}_{\chi \in \bar{\mathcal{X}}}^{}$ in $\mathcal{H}^{(\lambda)}$, and a family of QPT-implementable PVMs $\{\{N_{b|y}^{(\lambda)}\}_{b \in \mathcal{B}}\}_{y \in \mathcal{Y}}^{}$ on $\mathcal{H}^{(\lambda)}$ which satisfy

$$ \langle \Psi_{\alpha|\chi}^{(\lambda)} | N_{b|y}^{(\lambda)} | \Psi_{\alpha|\chi}^{(\lambda)} \rangle = p^{(\lambda)}(\alpha, b|\chi, y), \quad \forall \alpha \in \bar{\mathcal{A}}, \chi \in \bar{\mathcal{X}}, b \in \mathcal{B}, y \in \mathcal{Y}. \quad (3.6) $$

See Section A.2 for the proof of Theorem 3.2.

We say a compiled model $\tilde{Q}^{(\lambda)} = (\tilde{\mathcal{H}}^{(\lambda)}, \{|\Psi_{\alpha|\chi}^{(\lambda)}\}_{\alpha \in \bar{\mathcal{A}}, \chi \in \bar{\mathcal{X}}}^{}\}_{\lambda \in \bar{\mathcal{X}}}, \{\{N_{b|y}^{(\lambda)}\}_{b \in \mathcal{B}}\}_{y \in \mathcal{Y}}^{}\}$ is pure and projective whenever the states $|\Psi_{\alpha|\chi}^{(\lambda)}\rangle$ are all pure and the measurements $N_{b|y}^{(\lambda)}$ are all projective (i.e. PVMS).

## 3.1 Quantum bounds for compiled inequalities

A compiled (quantum) model $\tilde{Q}^{(\lambda)}$ describes the correlations $p^{(\lambda)} = \{p^{(\lambda)}(a, b|x, y)\}_{a \in \mathcal{A}, b \in \mathcal{B}, x \in \mathcal{X}, y \in \mathcal{Y}}^{}$ observed in a compiled Bell scenario. A compiled Bell functional is a linear functional $I^{(\lambda)}$
evaluated on correlations realized by compiled models. That is

$$I^{(\lambda)} = \sum_{abxy} w_{abxy} \sum_{\substack{\text{sk}\leftarrow\text{Gen}(1^{\lambda}) \\ \chi:\text{Enc}(x)=\chi}} \sum_{\alpha:\text{Dec}(\alpha)=a} \langle \Psi_{\alpha|\chi}^{(\lambda)} | N_{b|y}^{(\lambda)} | \Psi_{\alpha|\chi}^{(\lambda)} \rangle. \quad (3.7)$$

By the properties of the compilation procedure [KLVY23, Theorem 3.2], Bell inequalities are preserved under compilation (up to negligible error). In particular, for large security parameter, efficient classical provers cannot violate a Bell inequality by much more than they could in the (bipartite) scenario. From now on, we will suppress the security parameter $\lambda \in \mathbb{N}$ along with the expectation over secret keys $E_{\text{sk}\leftarrow\text{Gen}(1^{\lambda})}$ and simply write the expectation for a fixed key. In particular, we express the compiled model as $\tilde{Q}$ and Eq. (3.7) as

$$I = \sum_{abxy} w_{abxy} \sum_{\substack{\chi:\text{Enc}(x)=\chi \\ \alpha:\text{Dec}(\alpha)=a}} \sum_{\alpha:\text{Dec}(\alpha)=a} \langle \Psi_{\alpha|\chi} | N_{b|y} | \Psi_{\alpha|\chi} \rangle.$$

We now turn our attention to the maximum value $I$ can take in the compiled setting with an efficient quantum prover. The results of [KLVY23] imply that an efficient quantum prover can achieve the same violation in the bipartite setting. However, the existence of a quantum compiled behavior which exceeds the maximal quantum Bell violation in the bipartite case (by more than negligible factors) has not been ruled out. Nonetheless, in several cases (like the CHSH inequality and more generally all XOR games [CMM$^{+24}$]) we know that the quantum compiled behavior cannot exceed the value $\eta^Q$ by more than negligible amounts. One technique for establishing such bounds was introduced in [NZ23] and uses SOS techniques to bound the quantum violation of the compiled Bell functional.

## 3.2 Extending the pseudo-expectations

Our approach builds off the methods used in [NZ23] and [CMM$^{+24}$]. To explain this approach we recall that a pseudo-expectation is a unital, linear map from a subspace $\mathcal{T}$ of the algebra generated by $\{M_{a|x}, N_{b|y}\}_{a \in A, x \in \mathcal{X}, b \in B, y \in \mathcal{Y}}$ to the complex numbers, $\tilde{\mathbb{E}}_S : \mathcal{T} \to \mathbb{C}$, which is determined by a compiled quantum model $\tilde{Q}$. In the case $n = m = 2$, it suffices to define the pseudo-expectation $\tilde{\mathbb{E}}_S$ on the observables $A_x = \sum_{a \in \{0,1\}} (-1)^a M_{a|x}$, $B_y = \sum_{b \in \{0,1\}} (-1)^b N_{b|y}$ and require that they are mapped to their expectations in the compiled scenario$^2$. We further assume that all measurements are projective (cf. Theorem 3.2). In previous works, the definition of the pseudo-expectation had been restricted to monomials consisting of at most one Alice and one Bob observable as outlined below:

$$\begin{align}
\tilde{\mathbb{E}}_S[A_x B_y] &:= \sum_{\chi:\text{Enc}(x)=\chi} (-1)^{\text{Dec}(\alpha)} \langle \Psi_{\alpha|\chi} | B_y | \Psi_{\alpha|\chi} \rangle, \nonumber \\
\tilde{\mathbb{E}}_S[A_x A_{x'}] &:= \delta_{x,x'}, \nonumber \\
\tilde{\mathbb{E}}_S[B_y B_{y'}] &:= \sum_{\chi:\text{Enc}(x)=\chi} \sum_{\alpha} \langle \Psi_{\alpha|\chi} | B_y B_{y'} | \Psi_{\alpha|\chi} \rangle, \nonumber \\
\tilde{\mathbb{E}}_S[A_x] &:= \sum_{\chi:\text{Enc}(x)=\chi} (-1)^{\text{Dec}(\alpha)} \langle \Psi_{\alpha|\chi} | \Psi_{\alpha|\chi} \rangle, \tag{3.8} \\
\tilde{\mathbb{E}}_S[B_y] &:= \sum_{\chi:\text{Enc}(x)=\chi} \sum_{\alpha} \langle \Psi_{\alpha|\chi} | B_y | \Psi_{\alpha|\chi} \rangle, \nonumber \\
\tilde{\mathbb{E}}_S[1] &:= 1, \nonumber
\end{align}$$

<footnote>$^2$Though in the following we define $\tilde{\mathbb{E}}_S$ for $n = m = 2$, this can be directly extended to arbitrary Bell scenarios by defining $\tilde{\mathbb{E}}_S$ on the POVM elements $M_{a|x}, N_{b|y}$ in an analogous way.</footnote>
where $\mathbb{E}_{x \in \mathcal{X}}$ denotes the expectation according to an arbitrary fixed distribution over $\mathcal{X}$. This is already sufficient to handle known SOS decompositions for a variety of well-studied Bell inequalities whenever the polynomials are expressed in the basis $\{1, A_x, B_y\}_{x \in \mathcal{X}, y \in \mathcal{Y}}$. However, there are Bell inequalities, such as the tilted-CHSH inequality [BP15, BSB24], for which no known SOS decomposition exists in the basis $\{1, A_x, B_y\}_{x \in \mathcal{X}, y \in \mathcal{Y}}$.

The contribution of this section is to expand the definition of the pseudo-expectation to the basis encompassing all monomials in $A_x, B_0, B_1$, for a fixed $x \in \mathcal{X}$, in a way that is approximately non-negative on Hermitian squares. This allows us to handle more general SOS decompositions, and in particular, the tilted-CHSH inequalities. Let $w(A_x, B_0, B_1)$ be a monomial in the elements $\{A_x, B_0, B_1\}$. Importantly, $x$ is fixed, and we do not consider monomials of the form $A_0 A_1 B_y$ for example. Let $\bar{w}$ be the canonical form of $w$ under the relations $[A_x, B_y] = 0, (B_y)^2 = (A_x)^2 = 1$, where all $A_x$ terms are commuted to the left. Since we only consider one value of $x$, these will all be of the form $(A_x)^i \bar{w}(B_0, B_1)$ for some $i \in \{0, 1\}$, where the monomial $\bar{w}(B_0, B_1)$ cannot be reduced further. We then define the pseudo-expectation

$$ \tilde{\mathbb{E}}_S[w(A_x, B_0, B_1)] := \tilde{\mathbb{E}}_S[(A_x)^i \bar{w}(B_0, B_1)]. \quad (3.9) $$

For the case $i = 0$, we define

$$ \tilde{\mathbb{E}}_S[\bar{w}(B_0, B_1)] := \mathbb{E}_{x \in \mathcal{X}} \mathbb{E}_{\chi: \mathrm{Enc}(x)=\chi} \sum_{\alpha} \langle \Psi_{\alpha|\chi} | \bar{w}(B_0, B_1) | \Psi_{\alpha|\chi} \rangle, \quad (3.10) $$

and for the case $i = 1$,

$$ \tilde{\mathbb{E}}_S[A_x \bar{w}(B_0, B_1)] := \mathbb{E}_{\chi: \mathrm{Enc}(x)=\chi} \sum_{\alpha} (-1)^{\mathrm{Dec}(\alpha)} \langle \Psi_{\alpha|\chi} | \bar{w}(B_0, B_1) | \Psi_{\alpha|\chi} \rangle. \quad (3.11) $$

From the above definitions, we next state the main result of this section, which can be applied generally to any polynomial expressible in the basis $\{A_x, B_0, B_1\}$.

**Theorem 3.3.** Let $\{A_x\}_{x \in \mathcal{X}}$ and $\{B_y\}_{y \in \mathcal{Y}}$ be binary observables, and let

$$ P = \sum_i \gamma_i (A_x)^{k_i} w_i(B_0, B_1), \quad (3.12) $$

where $\gamma_i \in \mathbb{C}$, $k_i \in \{0, 1\}$ and each $w_i(B_0, B_1)$ is any monomial in the algebra of $\{B_0, B_1\}$. Then there exists a negligible function $\mathrm{negl}(\lambda)$ of the security parameter $\lambda \in \mathbb{N}$ such that

$$ \tilde{\mathbb{E}}_S[P^\dagger P] \geq -\mathrm{negl}(\lambda). \quad (3.13) $$

Furthermore, for a given Bell functional $I$, and a compiled model $\tilde{Q}$, $\tilde{\mathbb{E}}_S(I)$ is the expected value of the compiled model $\tilde{Q}$ on $I$.

The proof can be found in Section A.2.

### 3.3 Quantum bounds for compiled tilted-CHSH expressions

We now present the family of extended tilted-CHSH type expressions and their SOS decompositions discovered in [BSB24]. Let $\theta \in (0, \pi/4]$, $\phi \in (\max\{-2\theta, -\pi + 2\theta\}, \min\{2\theta, \pi - 2\theta\}) \setminus \{0\}$, and $\tau_{\theta, \phi} \in \mathbb{R}$ such that

$$ \frac{1}{\tau_{\theta, \phi}^2} = \frac{\sin^2(2\theta)}{\tan^2(\phi)} - \cos^2(2\theta). \quad (3.14) $$
From here, we define the following expressions:

$$ 
\begin{aligned}
S_{\theta, \phi} &:= A_0 \otimes \frac{B_0 + B_1}{\cos(\phi)} + \tau_{\theta, \phi}^2 \left[ \sin(2\theta) A_1 \otimes \frac{B_0 - B_1}{\sin(\phi)} + \cos(2\theta) \mathbf{1} \otimes \frac{B_0 + B_1}{\cos(\phi)} \right], \\
\eta_{\theta, \phi}^Q &:= 2(1 + \tau_{\theta, \phi}^2).
\end{aligned} 
\quad (3.15) 
$$

We also let $I_{\theta, \phi}$ denote the corresponding Bell functional, and recall the following result.

**Lemma 3.4** ([BSB24], Section 3.2.1). Let $\theta \in (0, \pi/4]$, $\phi \in (\max\{-2\theta, -\pi + 2\theta\}, \min\{2\theta, \pi - 2\theta\}) \setminus \{0\}$, $\tau_{\theta, \phi}$ be given by Eq. (3.14) and $S_{\theta, \phi}, \eta_{\theta, \phi}^Q$ be defined in Eq. (3.15). Define the following polynomials:

$$ 
\begin{aligned}
N_0 &:= A_0 \otimes \mathbf{1} - \mathbf{1} \otimes \frac{B_0 + B_1}{2 \cos(\phi)}, \\
N_1 &:= A_1 \otimes \mathbf{1} - \sin(2\theta) \mathbf{1} \otimes \frac{B_0 - B_1}{2 \sin(\phi)} - \cos(2\theta) A_1 \otimes \frac{B_0 + B_1}{2 \cos(\phi)}.
\end{aligned} 
\quad (3.16) 
$$

Then the shifted Bell operator $\bar{S}_{\theta, \phi} = \eta_{\theta, \phi}^Q \mathbf{1} - S_{\theta, \phi}$ admits the SOS decomposition

$$ \bar{S}_{\theta, \phi} = N_0^{\dagger} N_0 + \tau_{\theta, \phi}^2 N_1^{\dagger} N_1. \quad (3.17) $$

Using the decomposition in Theorem 3.4, it was shown in [BSB24] that the inequality $\langle S_{\theta, \phi} \rangle \le \eta_{\theta, \phi}^Q$ self-tests following state and measurements:

$$ 
\begin{aligned}
|\psi_{\theta}\rangle &= \cos(\theta)|00\rangle + \sin(\theta)|11\rangle, \\
A_0 &= \sigma_Z, \quad A_1 = \sigma_X, \\
B_y &= \cos(\phi)\sigma_Z + (-1)^y \sin(\phi)\sigma_X, \quad y \in \{0, 1\},
\end{aligned} 
\quad (3.18) 
$$

where $\sigma_Z, \sigma_X$ are the Pauli operators. Notably, by setting $\phi = \mu_\theta$ where $\tan(\mu_\theta) = \sin(2\theta)$, this family encompasses what are most commonly referred to as “tilted-CHSH inequalities” given by the Bell operator

$$ T_{\theta} = \alpha_{\theta} A_{0} \otimes \mathbf{1} + A_{0} \otimes (B_{0} + B_{1}) + A_{1} \otimes (B_{0} - B_{1}), \quad (3.19) $$

where $\alpha_\theta = 2/\sqrt{1+2\tan^2(2\theta)}$ [AMP12, YN13, BP15]. Compared to the SOS decompositions for $T_\theta$ from [BP15], the decomposition of [BSB24] is expressed in the basis for which our extended pseudo-expectation is well defined (cf. Theorem 3.3), allowing us to provide bounds on the compiled value of $T_\theta$, and more generally the family $S_{\theta, \phi}$.

**Theorem 3.5.** Let $\theta \in (0, \pi/4]$, $\phi \in (\max\{-2\theta, -\pi + 2\theta\}, \min\{2\theta, \pi - 2\theta\}) \setminus \{0\}$, and let $\langle S_{\theta, \phi} \rangle \le \eta_{\theta, \phi}^Q$ be the extended tilted-CHSH inequality for the expressions defined in Eq. (3.15). Then the maximum quantum value of the corresponding compiled Bell inequality is given by $\eta_{\theta, \phi}^Q + \text{negl}(\lambda)'$, where $\text{negl}(\lambda)'$ is a negligible function of the security parameter.

*Proof.* We evaluate the pseudo-expectation on the shifted Bell expression $\bar{S}_{\theta, \phi}$:

$$ \tilde{\mathbb{E}}_S[\bar{S}_{\theta, \phi}] = \tilde{\mathbb{E}}_S[N_0^\dagger N_0] + \tau_{\theta, \phi}^2 \tilde{\mathbb{E}}_S[N_1^\dagger N_1], \quad (3.20) $$

where we used the decomposition in Theorem 3.4. The polynomial $N_0$ is expressed in the basis $\{A_0, B_0, B_1\}$, and we find by Theorem 3.3 that

$$ \tilde{\mathbb{E}}_S[N_0^\dagger N_0] \ge -\text{negl}(\lambda). \quad (3.21) $$
Similarly, $N_1$ is expressed in the basis $\{A_1, B_0, B_1\}$, and we see by Theorem 3.3 that $\tilde{\mathbb{E}}_S[N_1^\dagger N_1] \ge -\text{negl}(\lambda)$. Putting these together, we obtain

$$ \tilde{\mathbb{E}}_S[\bar{S}_{\theta,\phi}] \ge -\text{negl}(\lambda)(1 + \tau_{\theta,\phi}^2) =: -\text{negl}(\lambda)', \quad (3.22) $$

which implies $\tilde{\mathbb{E}}_S[S_{\theta,\phi}] \le \eta_{\theta,\phi}^Q + \text{negl}(\lambda)'$ as desired, where $\tilde{\mathbb{E}}_S[S_{\theta,\phi}]$ is the expected value of the compiled Bell inequality. $\square$

**Remark 3.6.** The extension of the $S_{\theta,\phi}$ family presented in [BSB24, Section 3.2.3] self-tests the state $|\psi_\theta\rangle$ along with the more general measurements

$$ \begin{align} A_0 &= \sigma_Z, \quad A_1 = \sigma_X, \nonumber \\ B_0 &= \cos(\phi) \sigma_Z + \sin(\phi) \sigma_X, \tag{3.23} \\ B_1 &= \cos(\omega) \sigma_Z + \sin(\omega) \sigma_X, \nonumber \end{align} $$

for $\phi \in (-2\theta, 0)$ and $\omega \in (0, 2\theta)$. This family of Bell inequalities can also be compiled under our definition of the pseudo-expectation. This is because each SOS polynomial is given in the basis $\{A_x, B_0, B_1\}$ for a fixed $x$, and we can apply Theorem 3.3 directly as was done in Theorem 3.5. We omit the explicit proof of this for brevity.

# 4 Self-testing in the compiled setting

Recall that a bipartite (quantum) model Q, consists of a shared state $|\Psi\rangle$, along with local POVM measurements $\{M_{a|x}\}$ and $\{N_{b|y}\}$ for Alice and Bob, respectively. Given a Bell expression $I$, the inequality $I \le \eta^Q$ self-tests an ideal bipartite model $Q^*$ if any optimal bipartite model is essentially the same as $Q^*$, modulo some physically irrelevant degrees of freedom. This is more formally stated in terms or the existence of local isometries which maps the employed model to the ideal one. When small errors are permitted, one considers the following definition of robust self-testing.

**Definition 4.1 (Bipartite self-test).** The inequality $I \le \eta^Q$ is a self-test for a bipartite model $Q^* = (\{P_{a|x}\}, \{Q_{b|y}\}, |\phi\rangle)$ if there exist a non-negative function $f(\epsilon)$ such that $f(\epsilon) \to 0$ as $\epsilon \to 0$, such that for any bipartite model $Q = (\{M_{a|x}\}, \{N_{b|y}\}, |\Psi\rangle)$ achieving $I \ge \eta^Q - \epsilon$ for $\epsilon \ge 0$, there exists a Hilbert space $\mathcal{H}_{\text{aux}}$, an auxiliary state $|\zeta\rangle \in \mathcal{H}_{\text{aux}}$ and local isometries $V_A$ and $V_B$, such that defining $V: \mathcal{H}_A \otimes \mathcal{H}_B \to \mathbb{C}^d \otimes \mathbb{C}^d \otimes \mathcal{H}_{\text{aux}}$, $V = V_A \otimes V_B$, the following is satisfied for all $x, y, a, b$:

$$ \|V_A \otimes V_B(M_{a|x} \otimes N_{b|y}) |\Psi\rangle - (P_{a|x} \otimes Q_{b|y}) |\phi\rangle \otimes |\zeta\rangle\| \le f(\epsilon). $$

In the bipartite setting, one could consider the situation where Alice measures first using a POVM $\{P_{a|x}\}$, collapsing the state to a post-measurement state $\rho_{a|x}$ on Bob's subsystem $\mathcal{H}_B$, upon which Bob performs his measurement, resulting in the application of the POVM element $Q_{b|y}$. With this in mind, we consider the setting where the only relevant features of the model are those from Bob's (resp. Alice's) perspective. In particular, subsystem A is traced out following the recorded measurement of outcome of a given $x$.

**Definition 4.2 (Partial model).** Given a bipartite model $Q = (\{M_{a|x}\}, \{N_{b|y}\}, |\Psi\rangle)$, we define the partial model of $Q$ by $Q' = (\{N_{b|y}\}, \{\rho_{a|x}\})$ where

$$ \rho_{a|x} = \text{tr}_A[(M_{a|x} \otimes \mathbb{1}_B)|\Psi\rangle\langle\Psi|]. \quad (4.1) $$

We note that $\rho_{a|x}$ will generally be mixed. When each $\rho_{a|x}$ is pure, we say that $Q$ has a pure partial model, denoted by $Q' = (\{N_{b|y}\}, \{|\phi_{a|x}\rangle\})$.
Symmetrically, given a bipartite model one can consider a (pure) partial model on $\mathcal{H}_A$ by tracing out subsystem $B$. However, because our motivation is the compiled setting, we will focus on the partial models on $\mathcal{H}_B$. Furthermore, we remark that the notion of pure partial models is not vacuous. In particular, the optimal bipartite model for the CHSH inequality has a pure partial model on $\mathcal{H}_B$ [CHSH69]. With the notion of a partial quantum model, we define the notion of a partial (or one-sided) self-test for a bipartite model.

**Definition 4.3 (Partial self-test).** The inequality $I \le \eta^Q$ is a partial self-test for a bipartite model $Q^* = (\{P_{a|x}\}, \{Q_{b|y}\}, |\phi\rangle)$ with a pure partial model $(\{Q_{b|y}\}, \{|\phi_{a|x}\rangle\})$ if there exists a non-negative function $f(\epsilon)$ such that $f(\epsilon) \to 0$ as $\epsilon \to 0$, such that for any partial quantum model $Q = (\{N_{b|y}\}, \{\rho_{a|x}\})$ achieving $I \ge \eta^Q - \epsilon$ for $\epsilon \ge 0$, there exist a Hilbert space $\mathcal{H}_{\text{aux}}$, a collection of auxiliary states $\{\sigma_{a|x}\}$ and an isometry $V: \mathcal{H}_B \to \mathbb{C}^d \otimes \mathcal{H}_{\text{aux}}$ such that the following is satisfied for all $x, y, a, b$:

$$ \|VN_{b|y}\rho_{a|x}N_{b|y}V^\dagger - Q_{b|y}|\phi_{a|x}\rangle\langle\phi_{a|x}|Q_{b|y} \otimes \sigma_{a|x}\|_2 \le f(\epsilon) $$

$$ \text{and} \quad \|V\rho_{a|x}V^\dagger - |\phi_{a|x}\rangle\langle\phi_{a|x}| \otimes \sigma_{a|x}\|_2 \le f(\epsilon), $$

Give the symmetry of $\mathcal{H}_A$ and $\mathcal{H}_B$ in the bipartite case, one can define a notion of partial self-test for either subsystem. Given a bipartite self-test, one can check that tracing out either subsystem results in a partial self-test. We leave it as an open question as to whether a partial self-test (say over $\mathcal{H}_A$ and over $\mathcal{H}_B$) implies that the correlation is a bipartite self-test.

## 4.1 Compiled self-tests from partial models

There are two main difficulties with self-testing in the compiled setting. Firstly, the correctness with respect to auxiliary systems property of the compiler (see Property (1) in Theorem A.2) only guarantees that a QPT prover can prepare states (possibly mixed) $\rho_{a|x}$ over $\mathcal{H}_B$ that are negligible in trace distance from the post measurement states $P_{a|x}|\Psi\rangle\langle\Psi|P_{a|x}/p(a|x)$ of the ideal bipartite model $Q$. This puts a fundamental constraint on our ability to exactly describe the set of ideal models in the compiled setting. Secondly, unlike in the nonlocal setting, it is not clear how to extract information about the measurements and states in the first round due to the homomorphic evaluation of the measurements and preparation of the states. To address these challenges we introduce the compiled counter-part of a partial quantum model.

Recall that a compiled (quantum) model $\tilde{Q}$ consists of a family of post-measurement states for “Alice” $|\tilde{\phi}_{\alpha|\chi}\rangle$, which correspond to the state of the device following the encrypted question $\chi$, and encrypted answer $\alpha$, and a POVM $\{N_{b|y}\}$ employed by “Bob”. One could also consider a more general compiled quantum model, which includes a description of the initial state and Alice’s operators. The point of taking the coarser model is that it allows us to introduce the notion of the compiled-counterpart of a bipartite model $Q$, which relates the post-measurement information in the bipartite setting with another bipartite model that resembles a compiled model.

**Definition 4.4 (Compiled-counterpart model).** Given a pure partial model $Q'$, the compiled-counterpart model of $Q'$ is the pure partial model $\tilde{Q}^{(\lambda)} = (\{|\tilde{\phi}_{\alpha|\chi}^{(\lambda)}\rangle, \{Q_{b|y}^{(\lambda)}\})$ satisfying the following conditions for all $\lambda \in \mathbb{N}$:

$$ |\tilde{\phi}_{\alpha|\chi}^{(\lambda)}\rangle = |\phi_{a|x}\rangle, \quad \text{for all } sk: \text{Gen}(1^{\lambda}) = sk, \chi: \text{Enc}(x, sk) = \chi, \alpha: \text{Dec}(\alpha, sk) = a. $$

$$ N_{b|y}^{(\lambda)} = Q_{b|y}, \quad \text{for all } b, y. $$

We remark that the compiled counterpart need not be an actual compiled model. For example, it is not required to satisfy the QPT conditions needed of a compiled model. Instead it is a
model that resembles an idealized version of an honest implementation of a partial model under homomorphic encryption. We proceed with a definition of self-testing in the compiled setting that resembles partial self-testing in the bipartite setting in the context of these compiled-counterparts.

**Definition 4.5 (Compiled self-test).** Let $I$ denote a Bell expression with an optimal pure partial model $\tilde{Q}^*$. The inequality $I \le \eta^Q$ is a compiled self-test for the corresponding compiled-counterpart $\tilde{Q}^* = (\{|\tilde{\phi}_{\alpha|\chi}\rangle\}, \{Q_{b|y}\})$, if there exists a non-negative function $f(\epsilon)$ such that $f(\epsilon) \to 0$ as $\epsilon \to 0$, such that for every pure and projective compiled model $\tilde{Q} = (\{|\Psi_{\alpha|\chi}\rangle\}, \{N_{b|y}\})$ that achieves $I \ge \eta^Q - \epsilon$ for some $\epsilon \ge 0$, there exists a negligible function $\text{negl}(\lambda)$, an isometry $V: \tilde{\mathcal{H}} \to \mathbb{C}^d \otimes \mathcal{H}_{\text{aux}}$, and auxiliary states $|\text{aux}_{\alpha|\chi}\rangle \in \mathcal{H}_{\text{aux}}$, which satisfy the following for all $x, b, y$:

$$ \sum_{\chi:\text{Enc}(x)=\chi} \left\| V |\Psi_{\alpha|\chi}\rangle - |\tilde{\phi}_{\alpha|\chi}\rangle \otimes |\text{aux}_{\alpha|\chi}\rangle \right\|^2 \le \text{negl}(\lambda) + f(\epsilon), \quad \text{and} \quad (4.2a) $$

$$ \sum_{\chi:\text{Enc}(x)=\chi} \left\| V N_{b|y} |\Psi_{\alpha|\chi}\rangle - Q_{b|y} |\tilde{\phi}_{\alpha|\chi}\rangle \otimes |\text{aux}_{\alpha|\chi}\rangle \right\|^2 \le \text{negl}(\lambda) + f(\epsilon). \quad (4.2b) $$

Equation (4.2a) is a statement about the provers state after the first round. It asserts that, given a question $x$ and answer $a$, the post-measurement state is negligibly close to that of an ideal prover implementing the honest bipartite model. To see this concretely, suppose the right hand side was exactly equal to zero. Then we have the equality $V|\Psi_{\alpha|\chi}\rangle = |\tilde{\phi}_{\alpha|\chi}\rangle \otimes |\text{aux}_{\alpha|\chi}\rangle$ for all $\chi$ such that $\text{Enc}(x) = \chi$ and all $\alpha$. Substituting $|\tilde{\phi}_{\alpha|\chi}\rangle$ for the states $|\phi_{a|x}\rangle$ from Definition 4.4, we obtain

$$ V |\Psi_{\alpha|\chi}\rangle = |\phi_{a|x}\rangle \otimes |\text{aux}_{\alpha|\chi}\rangle \quad (4.3) $$

whenever $\text{Enc}(x) = \chi$ and $\text{Dec}(\alpha) = a$. That is, the post-measurement states are equal to the target states up an isometry. Therefore, we interpret (4.2a) as an approximate version of Eq. (4.3), which accounts for a finite size security parameter $\lambda$ and small errors in the Bell violation $\epsilon$. Equation (4.2b) is the analogous statement including the measurements in the second round. We remark that if $V$ could depend on the question $x$ and answer $a$, (4.2a) would trivially hold regardless of the compiled Bell violation, since the states $|\phi_{a|x}\rangle$ could be prepared directly. It is therefore essential to enforce the same isometry is applied for all $a$ and $x$. Furthermore, (4.2b) captures several existing self-testing results in the compiled setting. For example those presented in [NZ23, Lemma 34], [CMM$^{+24}$, Theorem 3.6] and [BVB$^{+24}$, Eqs. 98 and 103]. Our proposed definition then goes further by also certifying the states after the first round but before Bob's measurements, as captured by (4.2a).

It is natural to ask if Definition 4.5 is the strongest form of self-testing possible in this scenario, or if one can also certify the initial state $|\Psi\rangle$ before Alice's measurements. An initial guess would be to show there exists an isometry $V$ satisfying

$$ V |\Psi\rangle \approx_{\text{negl}(\lambda)} |\phi\rangle \otimes |\text{aux}\rangle, \quad (4.4) $$

where $|\phi\rangle$ is the ideal bipartite entangled state. However, on its own this statement is not very useful: such an isometry always exists, namely, one which ignores $|\Psi\rangle$ and prepares $|\phi\rangle$ directly. A possible way around is to demand the same $V$ also satisfies (4.2). At a glance, this suggests certifying the initial state alone is not meaningful in the single prover setting; one always needs to also consider the measurements. This contrasts the two prover setting, where self-testing statements made only about the state are known [SB20] and non-trivial due to the space-like separation of the provers. Another question worth asking is if the assumption of having a pure projective models $\tilde{Q}$ can be relaxed in the definition Theorem 4.5.
## 4.2 Compiled self-test for tilted-CHSH inequalities

Our final result is that the extended tilted-CHSH Bell inequalities are compiled self-tests according to Theorem 4.5. In particular, we have the following result.

**Theorem 4.6.** Let $\theta \in (0, \pi/4]$, $\phi \in (\max\{-2\theta, -\pi + 2\theta\}, \min\{2\theta, \pi - 2\theta\}) \setminus \{0\}$, and let $I_{\theta,\phi}$ be the generalized tilted-CHSH functional with quantum bound $\eta_{\theta,\phi}^Q$ according to Eq. (3.15). Then the inequality $I_{\theta,\phi} \le \eta_{\theta,\phi}^Q$ is a compiled self-test for the compiled-counter part of Eq. (3.18) according to Theorem 4.5.

The proof is reminiscent of the approach in [BP15], and includes similar calculations to those used in [NZ23, BVB$^+$24] which establish rigidity statements in the compiled setting. The remainder of this section is devoted to proving the above theorem. Recall the SOS decomposition for $\bar{S}_{\theta,\phi}$, given by the polynomials $N_0, N_1$ defined in Eq. (3.16). Then for compiled models $I_{\theta,\phi} = \tilde{\mathbb{E}}_S[S_{\theta,\phi}] \ge \eta_{\theta,\phi}^Q - \epsilon$, for some $\epsilon \ge 0$, implies $\tilde{\mathbb{E}}_S[\bar{S}_{\theta,\phi}] = \eta_{\theta,\phi}^Q - \tilde{\mathbb{E}}_S[S_{\theta,\phi}] \le \epsilon$. Using the calculation in Eq. (A.7) with $P = N_0$ and $P = N_1$ respectively, we find

$$ \begin{aligned} \tilde{\mathbb{E}}_S[N_0^\dagger N_0] &\approx_{\text{negl}(\lambda)} \mathbb{E}_{\chi:\text{Enc}(x=0)=\chi} \sum_{\alpha} \langle \Psi_{\alpha|\chi} | (-1)^{\text{Dec}(\alpha)} 1 - Z_B | \Psi_{\alpha|\chi} \rangle =: \hat{E}_0, \\ \tilde{\mathbb{E}}_S[N_1^\dagger N_1] &\approx_{\text{negl}(\lambda)} \mathbb{E}_{\chi:\text{Enc}(x=1)=\chi} \sum_{\alpha} \langle \Psi_{\alpha|\chi} | 1 - (-1)^{\text{Dec}(\alpha)} \sin(2\theta) X_B - \cos(2\theta) Z_B | \Psi_{\alpha|\chi} \rangle =: \hat{E}_1, \end{aligned} \quad (4.5) $$

where we defined $Z_B := (B_0 + B_1)/(2 \cos(\phi))$ and $X_B := (B_0 - B_1)/(2 \sin(\phi))$, and note that $\hat{E}_i \ge 0$ for $i = 0, 1$. This implies $\tilde{\mathbb{E}}_S[N_i^\dagger N_i] \ge \hat{E}_i - \text{negl}(\lambda)$, from which we observe that

$$ \hat{E}_0 + \tau_{\theta,\phi}^2 \hat{E}_1 \le \tilde{\mathbb{E}}_S[N_0^\dagger N_0] + \tau_{\theta,\phi}^2 \tilde{\mathbb{E}}_S[N_1^\dagger N_1] + \text{negl}(\lambda)' = \tilde{\mathbb{E}}_S[\bar{S}_{\theta,\phi}] + \text{negl}(\lambda)' \le \epsilon + \text{negl}(\lambda)', \quad (4.6) $$

where $\text{negl}(\lambda)' = (1 + \tau_{\theta,\phi}^2)\text{negl}(\lambda)$. Since $\hat{E}_i \ge 0$, we arrive at

$$ \hat{E}_0 \le \epsilon + \text{negl}(\lambda)' \quad \text{and} \quad \tau_{\theta,\phi}^2 \hat{E}_1 \le \epsilon + \text{negl}(\lambda)'. \quad (4.7) $$

The next part of the proof proceeds as follows: using each constraint in Eq. (4.7), we deduce the (approximate) algebraic structure of the operators $Z_B$ and $X_B$ on the states $|\Psi_{\alpha|\chi}\rangle$. Namely, we establish anti-commutation relations and approximate unitary relations. We break the proof up into two sections: extracting the states, and extracting the measurements.

**Extracting the states** We begin by studying the relations imposed by $\hat{E}_0 \le \epsilon + \text{negl}(\lambda)'.$ Define $\delta_0 := \epsilon + \text{negl}(\lambda)'.$ We begin with several claims:

**Claim 1.** $\hat{E}_0 = \mathbb{E}_{\chi:\text{Enc}(x=0)=\chi} \sum_{\alpha} \|((-1)^{\text{Dec}(\alpha)} 1 - Z_B) |\Psi_{\alpha|\chi}\rangle\|^2 \le \delta_0$.

**Claim 2.** $\mathbb{E}_{\chi:\text{Enc}(x=0)=\chi} \sum_{\alpha} \|(1 - (Z_B)^2) |\Psi_{\alpha|\chi}\rangle\|^2 \le \delta_0 (1 + 1/\cos(\phi))^2 =: \delta_1$.

*Proof.* Note that

$$ \begin{aligned} \|(1 - (Z_B)^2) |\Psi_{\alpha|\chi}\rangle\| &\le \|Z_B((-1)^{\text{Dec}(\alpha)} 1 - Z_B) |\Psi_{\alpha|\chi}\rangle\| \\ &\quad + \|( (-1)^{\text{Dec}(\alpha)} 1 - Z_B) |\Psi_{\alpha|\chi}\rangle\| \\ &\le (1 + \|Z_B\|_{\text{op}}) \|( (-1)^{\text{Dec}(\alpha)} 1 - Z_B) |\Psi_{\alpha|\chi}\rangle\|. \end{aligned} $$
In the first inequality, we used the triangle inequality, and for the second inequality, we used the definition of the operator norm $||A|\psi\rangle|| \le ||A||_{op}||\psi\rangle||$, $\forall |\psi\rangle \in \mathcal{H}$. By the definition of $Z_B$, $||Z_B||_{op} \le (1/(2\cos(\phi)))(||B_0||_{op}+||B_1||_{op}) = 1/\cos(\phi)$. Squaring both sides, taking the expectation over $\chi$: $\text{Enc}(x=0) = \chi$ and summing over $\alpha$, we can apply Claim 1 to get the desired bound. $\square$

**Claim 3.** $\mathbb{E}_{\chi:\text{Enc}(x=0)=\chi} \sum_{\alpha} ||(2\cos(2\phi)1 - \{B_0, B_1\})|\Psi_{\alpha|\chi}\rangle||^2 \le 16\cos^4(\phi)\delta_1 =: \delta_2$.

*Proof.* Note that $(Z_B)^2 = (21 + \{B_0, B_1\})/(4\cos^2(\phi))$, and therefore

$$ \begin{aligned} ||(1 - (Z_B)^2)|\Psi_{\alpha|\chi}\rangle||^2 &= ||(1 - (21 + \{B_0, B_1\})/(4\cos^2(\phi)))|\Psi_{\alpha|\chi}\rangle||^2 \\ &= \frac{1}{16\cos^4(\phi)} ||(2\cos(2\phi)1 - \{B_0, B_1\})|\Psi_{\alpha|\chi}\rangle||^2. \end{aligned} $$

Taking the expectation over $\chi$: $\text{Enc}(x=0) = \chi$ and summing over $\alpha$, followed by applying Claim 2, establishes the desired bound. $\square$

**Claim 4.** $\mathbb{E}_{\chi:\text{Enc}(x=0)=\chi} \sum_{\alpha} ||(1 - (X_B)^2)|\Psi_{\alpha|\chi}\rangle||^2 \le \delta_1/\tan^4(\phi) =: \delta_3$.

*Proof.* Noting $(X_B)^2 = (21 - \{B_0, B_1\})/(4\sin^2(\phi))$,

$$ \begin{aligned} ||(1 - (X_B)^2)|\Psi_{\alpha|\chi}\rangle||^2 &= ||(1 - (21 - \{B_0, B_1\})/(4\sin^2(\phi)))|\Psi_{\alpha|\chi}\rangle||^2 \\ &= \frac{1}{16\sin^4(\phi)} ||(2\cos(2\phi)1 - \{B_0, B_1\})|\Psi_{\alpha|\chi}\rangle||^2. \end{aligned} $$

We obtain the claim by taking the expectation over $\chi$: $\text{Enc}(x=0) = \chi$, summing over $\alpha$ and applying Claim 3. $\square$

To define the isometry, we need to define unitary operators $\tilde{Z}_B$ and $\tilde{X}_B$ from $Z_B$ and $X_B$, which maintain the above relations. For this, we follow the regularization procedure of [YN13, MYS12, BP15]: define $Z_B^*$ from $Z_B$ by changing all zero eigenvalues of $Z_B$ to 1, and define the operator $\tilde{Z}_B := Z_B^*|Z_B^*|^{-1}$. Then $\tilde{Z}_B$ is unitary, self-adjoint, commutes with $Z_B$ and satisfies $\tilde{Z}_B Z_B = |Z_B|$. We now establish the following:

**Claim 5.** $\mathbb{E}_{\chi:\text{Enc}(x=0)=\chi} \sum_{\alpha} ||(\tilde{Z}_B - Z_B)|\Psi_{\alpha|\chi}\rangle||^2 \le \delta_0$.

*Proof.* Using the fact that $\tilde{Z}_B^\dagger$ is unitary and $\tilde{Z}_B Z_B = |Z_B|$,

$$ ||(\tilde{Z}_B - Z_B)|\Psi_{\alpha|\chi}\rangle||^2 = ||(1 - |(-1)^{\text{Dec}(\alpha)}Z_B|)|\Psi_{\alpha|\chi}\rangle||^2. $$

For any self-adjoint operator $A$, we have $||(1 - |A|)|\psi\rangle||^2 = \langle\psi|(1 + |A|^2 - 2|A|)|\psi\rangle \le \langle\psi|(1 + |A|^2 - 2A)|\psi\rangle =||(1 - A)|\psi\rangle||^2$. Applying this with $A = (-1)^{\text{Dec}(\alpha)}Z_B$, taking the expectation over $\chi$: $\text{Enc}(x=0) = \chi$ and summing over $\alpha$, we can directly apply Claim 1 to get the desired bound. $\square$

**Claim 6.** $\mathbb{E}_{\chi:\text{Enc}(x=0)=\chi} \sum_{\alpha} ||(\tilde{X}_B - X_B)|\Psi_{\alpha|\chi}\rangle||^2 \le \delta_1/\tan^2(\phi) =: \delta_4$.

*Proof.* Note that

$$ \begin{aligned} ||(\tilde{X}_B - X_B)|\Psi_{\alpha|\chi}\rangle||^2 &= ||(1 - |X_B|)|\Psi_{\alpha|\chi}\rangle||^2 \\ &\le ||(1 + |X_B|)(1 - |X_B|)|\Psi_{\alpha|\chi}\rangle||^2, \end{aligned} $$
where we used the same steps in Claim 5 for the first equality, and the operator inequality $1+|X_B| \ge 1$ for the inequality. Notice that $|X_B|^2 = (X_B)^2$, which satisfies $\cos^2(\phi)(Z_B)^2 + \sin^2(\phi)(X_B)^2 = 1$ by definition. Inserting this into the above expression we find that

$$ \|(1 + |X_B|)(1 - |X_B|)|\Psi_{\alpha|\chi}\rangle\|^2 = \frac{1}{\tan^2(\phi)}\|(1 - (Z_B)^2)|\Psi_{\alpha|\chi}\rangle\|^2, $$

and taking the expectation over $\chi: \text{Enc}(x=0) = \chi$, summing over $\alpha$ and applying Claim 2 we obtain the desired bound. $\square$

Next, we define the operators $P_B^b = \frac{1}{2}(1 + (-1)^b \tilde{Z}_B)$ for $b \in \{0, 1\}$ and note a key property.

**Claim 7.** $\mathbb{E}_{\chi: \text{Enc}(x=0)=\chi} \sum_{\alpha} \|(P_B^b - \delta_{\text{Dec}(\alpha),b} 1)|\Psi_{\alpha|\chi}\rangle\|^2 \le \delta_0$.

*Proof.* Note that

$$ \|(P_B^b - \delta_{\text{Dec}(\alpha),b} 1)|\Psi_{\alpha|\chi}\rangle\| = \frac{1}{2}\|(\tilde{Z}_B - (-1)^{\text{Dec}(\alpha)} 1)|\Psi_{\alpha|\chi}\rangle\|, $$

where we used the definition of $P_B^b$ and $\delta_{\text{Dec}(\alpha),b} = \frac{1}{2}(1 + (-1)^{\text{Dec}(\alpha)+b})$. Applying the triangle inequality,

$$ \|(\tilde{Z}_B - (-1)^{\text{Dec}(\alpha)} 1)|\Psi_{\alpha|\chi}\rangle\| \le \|(Z_B - (-1)^{\text{Dec}(\alpha)} 1)|\Psi_{\alpha|\chi}\rangle\| + \|(\tilde{Z}_B - Z_B)|\Psi_{\alpha|\chi}\rangle\|. $$

Next, we square both sides of the above, and use the fact that for two real numbers $a, b$, $(a+b)^2 \le 2(a^2 + b^2)$, to obtain

$$ \|(\tilde{Z}_B - (-1)^{\text{Dec}(\alpha)} 1)|\Psi_{\alpha|\chi}\rangle\|^2 \le 2\|(Z_B - (-1)^{\text{Dec}(\alpha)} 1)|\Psi_{\alpha|\chi}\rangle\|^2 + 2\|(\tilde{Z}_B - Z_B)|\Psi_{\alpha|\chi}\rangle\|^2. \quad (4.8) $$

By taking the expectation over $\chi: \text{Enc}(x=0) = \chi$ and summing over $\alpha$, the first term can be bounded by applying Claim 1, while the second can be bounded by applying Claim 5. $\square$

Having established the above relations for the case $\chi = \text{Enc}(x=0)$, we are now ready to define the isometry $V: \mathcal{H} \to \mathbb{C}^2 \otimes \mathcal{H}$,

$$ V = \sum_{b \in \{0,1\}} |b\rangle \otimes (\tilde{X}_B)^b P_B^b. \quad (4.9) $$

This isometry is based on the “SWAP gate isometry” [MYS12, YN13].

Using Claim 7, we establish the following lemma:

**Lemma 4.7.** Let $\tilde{Q}$ be any compiled model which satisfies $\tilde{\mathbb{E}}_S[S_{\theta,\phi}] \ge \eta_{\theta,\phi}^Q - \epsilon$, and let $V$ be the isometry defined in Eq. (4.9). Then there exists auxiliary states $\{|\text{aux}_{\alpha|\chi}\rangle\}_{\alpha,\chi}$ such that

$$ \mathbb{E}_{\chi: \text{Enc}(x=0)=\chi} \sum_{\alpha} \|V|\Psi_{\alpha|\chi}\rangle - |\text{Dec}(\alpha)\rangle \otimes |\text{aux}_{\alpha|\chi}\rangle\|^2 \le 2\delta_0. \quad (4.10) $$

*Proof.* Consider the states $|\text{aux}_{\alpha|\chi}\rangle = (\tilde{X}_B)^{\text{Dec}(\alpha)}|\Psi_{\alpha|\chi}\rangle$. Then

$$ |\text{Dec}(\alpha)\rangle \otimes |\text{aux}_{\alpha|\chi}\rangle = \sum_{b \in \{0,1\}} \delta_{b, \text{Dec}(\alpha)} |b\rangle \otimes (\tilde{X}_B)^b |\Psi_{\alpha|\chi}\rangle, $$
and we have

$$
\begin{aligned}
\|V|\Psi_{\alpha|\chi}\rangle - |\text{Dec}(\alpha)\rangle \otimes |\text{aux}_{\alpha|\chi}\rangle\|^2 &= \left\| \sum_{b \in \{0,1\}} |b\rangle \otimes (\tilde{X}_B)^b (P_B^b - \delta_{b,\text{Dec}(\alpha)} 1) |\Psi_{\alpha|\chi}\rangle \right\|^2 \\
&\le \sum_{b \in \{0,1\}} \|(P_B^b - \delta_{b,\text{Dec}(\alpha)} 1) |\Psi_{\alpha|\chi}\rangle\|^2.
\end{aligned}
$$

By taking the expectation over $\chi: \text{Enc}(x=0) = \chi$, and summing over $\alpha$, we can apply Claim 7 to obtain the desired bound. $\square$

We now proceed to study the relations imposed by the second SOS polynomial, which imply $\hat{E}_1 \le \delta_0/\tau_{\theta,\phi}^2$. Before we begin, we note that in any earlier claim that did not include a factor of $(-1)^{\text{Dec}(\alpha)}$, we can always apply Theorem 3.1 to exchange the expectation over encryptions of $x=0$ to an expectation over encryptions of $x=1$ at the cost of adding negl($\lambda$) to the bound. This follows from the fact that such claims are bounding the expectation of operators $\mathcal{N}$ constructed from sums of products of $B_0$ and $B_1$ only along with the fact that $\mathbb{E}_{\chi:\text{Enc}(x=0)=\chi} \sum_{\alpha} \langle \Psi_{\alpha|\chi} | \mathcal{N} | \Psi_{\alpha|\chi} \rangle \approx_{\text{negl}(\lambda)} \mathbb{E}_{\chi:\text{Enc}(x=1)=\chi} \sum_{\alpha} \langle \Psi_{\alpha|\chi} | \mathcal{N} | \Psi_{\alpha|\chi} \rangle$.

**Claim 8.** $\hat{E}_1 = \mathbb{E}_{\chi:\text{Enc}(x=1)=\chi} \sum_{\alpha} \|(1 - (-1)^{\text{Dec}(\alpha)} \sin(2\theta)X_B - \cos(2\theta)Z_B) |\Psi_{\alpha|\chi}\rangle\|^2 \le \delta_0/\tau_{\theta,\phi}^2$.

**Claim 9.** $\mathbb{E}_{\chi:\text{Enc}(x=1)=\chi} \sum_{\alpha} \|(1 - (-1)^{\text{Dec}(\alpha)} \sin(2\theta)\tilde{X}_B - \cos(2\theta)\tilde{Z}_B) |\Psi_{\alpha|\chi}\rangle\|^2 \le \delta_5$, where $\delta_5 := 2\delta_0/\tau_{\theta,\phi}^2 + 4\sin^2(2\theta)(\delta_4 + \text{negl}(\lambda)) + 4\cos^2(2\theta)(\delta_0 + \text{negl}(\lambda))$.

*Proof.* Using the triangle inequality we obtain

$$
\begin{aligned}
& \|(1 - (-1)^{\text{Dec}(\alpha)} \sin(2\theta) \tilde{X}_B - \cos(2\theta) \tilde{Z}_B) |\Psi_{\alpha|\chi}\rangle \| \\
& \le \|(1 - (-1)^{\text{Dec}(\alpha)} \sin(2\theta) X_B - \cos(2\theta) Z_B) |\Psi_{\alpha|\chi}\rangle \| \\
& \quad + \| \sin(2\theta) (X_B - \tilde{X}_B) |\Psi_{\alpha|\chi}\rangle \| + \| \cos(2\theta) (Z_B - \tilde{Z}_B) |\Psi_{\alpha|\chi}\rangle \|.
\end{aligned}
$$

Next, we square both sides, and use the fact that, for three real numbers $a, b, c$, $(a + b + c)^2 \le 4(a^2 + b^2) + 2c^2$, to arrive at

$$
\begin{aligned}
& \|(1 - (-1)^{\text{Dec}(\alpha)} \sin(2\theta) \tilde{X}_B - \cos(2\theta) \tilde{Z}_B) |\Psi_{\alpha|\chi}\rangle\|^2 \\
& \le 2 \|(1 - (-1)^{\text{Dec}(\alpha)} \sin(2\theta) X_B - \cos(2\theta) Z_B) |\Psi_{\alpha|\chi}\rangle\|^2 \\
& \quad + 4 \| \sin(2\theta) (X_B - \tilde{X}_B) |\Psi_{\alpha|\chi}\rangle\|^2 + 4 \| \cos(2\theta) (Z_B - \tilde{Z}_B) |\Psi_{\alpha|\chi}\rangle\|^2.
\end{aligned}
$$

We now take the expectation over $\chi: \text{Enc}(x=1) = \chi$, and sum over $\alpha$. This allows us to apply Claim 8 to the first term, Theorem 3.1 followed by Claim 6 to the second, and Theorem 3.1 followed by Claim 5 to the final term, giving the desired bound. $\square$

**Claim 10.** $\mathbb{E}_{\chi:\text{Enc}(x=1)=\chi} \sum_{\alpha} \|\{\tilde{Z}_B, \tilde{X}_B\} |\Psi_{\alpha|\chi}\rangle\|^2 \le \delta_6$, where $\delta_6 := 2(\delta_0 + \text{negl}(\lambda)) + 8(\delta_4 + \text{negl}(\lambda)) + 8(\delta_0 + \text{negl}(\lambda))/(2\sin^2(\phi)) + 16(1 + 1/(2\cos^2(\phi)))\delta_0/(\sin(2\theta)\tau_{\theta,\phi})^2 + 16(1/\sin^2(2\theta) + 1/(2\cos^2(\phi)\tan^2(2\theta)))(\delta_0 + \text{negl}(\lambda))$.

*Proof.* We begin by applying the triangle inequality to obtain

$$
\|\{\tilde{Z}_B, \tilde{X}_B\} |\Psi_{\alpha|\chi}\rangle\|^2 \le 2 \|\tilde{X}_B (\tilde{Z}_B - (-1)^{\text{Dec}(\alpha)} 1) |\Psi_{\alpha|\chi}\rangle\|^2 + 2 \|(\tilde{Z}_B + (-1)^{\text{Dec}(\alpha)} 1) \tilde{X}_B |\Psi_{\alpha|\chi}\rangle\|^2.
$$
For the first term, we can use the fact that $\tilde{X}_B$ is unitary, and when taking the expectation over $\chi: \text{Enc}(x=1) = \chi$ and sum over $\alpha$, we can apply Theorem 3.1 followed by Claim 1 to obtain a bound of $2(\delta_0 + \text{negl}(\lambda))$. For the second term,

$$ 
\begin{aligned}
2 \|(\tilde{Z}_B + (-1)^{\text{Dec}(\alpha)} 1) \tilde{X}_B |\Psi_{\alpha|\chi}\rangle\|^2 &\le 4 \|(\tilde{Z}_B + (-1)^{\text{Dec}(\alpha)} 1)(\tilde{X}_B - X_B) |\Psi_{\alpha|\chi}\rangle\|^2 \\
&\quad + 4 \|(\tilde{Z}_B + (-1)^{\text{Dec}(\alpha)} 1) X_B |\Psi_{\alpha|\chi}\rangle\|^2 \\
&\le 4 \|(\tilde{Z}_B + (-1)^{\text{Dec}(\alpha)} 1)\|_{\text{op}}^2 \|(\tilde{X}_B - X_B) |\Psi_{\alpha|\chi}\rangle\|^2 \\
&\quad + 8 \|(Z_B + (-1)^{\text{Dec}(\alpha)} 1) X_B |\Psi_{\alpha|\chi}\rangle\|^2 \\
&\quad + 8 \|(\tilde{Z}_B - Z_B) X_B |\Psi_{\alpha|\chi}\rangle\|^2.
\end{aligned}
$$

Since $\tilde{Z}_B$ is unitary $\|(\tilde{Z}_B + (-1)^{\text{Dec}(\alpha)} 1)\|_{\text{op}}^2 \le 2$, hence when taking the expectation over $\chi: \text{Enc}(x=1) = \chi$ and sum over $\alpha$ for the first term above, we can apply Theorem 3.1 followed by Claim 6 to $\|(\tilde{X}_B - X_B) |\Psi_{\alpha|\chi}\rangle\|^2$; the product results in a contribution $8(\delta_4 + \text{negl}(\lambda))$. Next, we note that

$$ 
\begin{aligned}
8 \|(Z_B + (-1)^{\text{Dec}(\alpha)} 1) X_B |\Psi_{\alpha|\chi}\rangle\|^2 &= 8 \|X_B (Z_B - (-1)^{\text{Dec}(\alpha)} 1) |\Psi_{\alpha|\chi}\rangle\|^2 \\
&\le 8 \|X_B\|_{\text{op}}^2 \|(Z_B - (-1)^{\text{Dec}(\alpha)} 1) |\Psi_{\alpha|\chi}\rangle\|^2,
\end{aligned}
$$

where the equality follows since $\{Z_B, X_B\} = 0$ by definition. Now $\|X_B\|_{\text{op}}^2 \le 1/(2 \sin^2(\phi))$, and when taking the expectation over $\chi: \text{Enc}(x=1) = \chi$ and sum over $\alpha$, we can apply Theorem 3.1 followed by Claim 1, resulting in a contribution of $8(\delta_0 + \text{negl}(\lambda))/(2 \sin^2(\phi))$.

We now address the term $8\|(\tilde{Z}_B - Z_B) X_B |\Psi_{\alpha|\chi}\rangle\|^2$. Claim 8 tells us that

$$ \chi: \text{Enc}(x=1) = \chi \sum_{\alpha} \|(X_B - (-1)^{\text{Dec}(\alpha)} \tau_{\theta, \phi}) |\Psi_{\alpha|\chi}\rangle\|^2 \le \delta_0 / (\sin(2\theta) \tau_{\theta, \phi})^2, \quad (4.11) $$

where $\tau_{\theta, \phi} = \frac{1}{\sin(2\theta)}(1 - \cos(2\theta)Z_B)$, which implies

$$ 
\begin{aligned}
8 \|(\tilde{Z}_B - Z_B) X_B |\Psi_{\alpha|\chi}\rangle\|^2 &\le 16 \|(\tilde{Z}_B - Z_B) \tau_{\theta, \phi} |\Psi_{\alpha|\chi}\rangle\|^2 \\
&\quad + 16 \|(\tilde{Z}_B - Z_B) (X_B - (-1)^{\text{Dec}(\alpha)} \tau_{\theta, \phi}) |\Psi_{\alpha|\chi}\rangle\|^2 \\
&\le 16 \|(\tilde{Z}_B - Z_B) \tau_{\theta, \phi} |\Psi_{\alpha|\chi}\rangle\|^2 \\
&\quad + 16 \|\tilde{Z}_B - Z_B\|_{\text{op}}^2 \|(X_B - (-1)^{\text{Dec}(\alpha)} \tau_{\theta, \phi}) |\Psi_{\alpha|\chi}\rangle\|^2.
\end{aligned}
$$

For the second term above, we have that $\|\tilde{Z}_B - Z_B\|_{\text{op}}^2 \le 1 + 1/(2 \cos^2(\phi))$, and when taking the expectation over $\chi: \text{Enc}(x=1) = \chi$ and summing over $\alpha$, we can apply Eq. (4.11) to obtain a contribution of $16(1 + 1/(2 \cos^2(\phi)))\delta_0/(\sin(2\theta)\tau_{\theta, \phi})^2$. Finally, we bound the first term above using the fact that $\tilde{Z}_B$ and $Z_B$ commute, that is,

$$ 
\begin{aligned}
16 \|(\tilde{Z}_B - Z_B) \tau_{\theta, \phi} |\Psi_{\alpha|\chi}\rangle\|^2 &= 16 \|\tau_{\theta, \phi} (\tilde{Z}_B - Z_B) |\Psi_{\alpha|\chi}\rangle\|^2 \\
&\le 16 \|\tau_{\theta, \phi}\|_{\text{op}}^2 \|(\tilde{Z}_B - Z_B) |\Psi_{\alpha|\chi}\rangle\|^2.
\end{aligned}
$$

The operator norm is bounded by $1/\sin^2(2\theta)+1/(2 \cos^2(\phi) \tan^2(2\theta))$, and when taking the expectation over $\chi: \text{Enc}(x=1) = \chi$ and summing over $\alpha$, we can apply Theorem 3.1 followed by Claim 5, resulting in a contribution of $16(1/\sin^2(2\theta) + 1/(2 \cos^2(\phi) \tan^2(2\theta)))(\delta_0 + \text{negl}(\lambda))$. By summing all the contributions from every use of the triangle inequality, we obtain the desired bound. $\square$
**Claim 11.** $\mathbb{E}_{\chi:Enc(x=1)=\chi} \sum_{\alpha} \|(\tilde{X}_B P_B^1 - P_B^0 \tilde{X}_B)|\Psi_{\alpha|\chi}\|^2 \le \delta_6/4$.

*Proof.* Note that

$$ \tilde{X}_B P_B^1 - P_B^0 \tilde{X}_B = -\frac{1}{2}\{\tilde{Z}_B, \tilde{X}_B\}, $$

and hence the claim immediately follows from Claim 10. □

We are now ready to prove the self-testing statement on the state when $Enc(x = 1) = \chi$:

**Lemma 4.8.** Let $\tilde{Q}$ be any compiled model which satisfies $\tilde{\mathbb{E}}_S[S_{\theta,\phi}] \ge \eta_{\theta,\phi}^Q - \epsilon$, and let $V$ be the SWAP isometry defined in Eq. (4.9). Then there exists auxiliary states $\{|\text{aux}_{\alpha|\chi}\rangle\}_{\alpha,\chi}$ such that

$$ \mathbb{E}_{\chi:Enc(x=1)=\chi} \sum_{\alpha} \|V|\Psi_{\alpha|\chi}\rangle - (\cos(\theta)|0\rangle + (-1)^{\text{Dec}(\alpha)} \sin(\theta)|1\rangle) \otimes |\text{aux}_{\alpha|\chi}\rangle\|^2 \le \delta_7, \quad (4.12) $$

where $\delta_7 := \delta_6/2 + 2\delta_5/(\sin^2(2\theta))$.

*Proof.* Consider the choice $|\text{aux}_{\alpha|\chi}\rangle = \frac{1}{\cos(\theta)} P_B^0 |\Psi_{\alpha|\chi}\rangle$. Then,

$$ \begin{aligned} & \|V|\Psi_{\alpha|\chi}\rangle - (\cos(\theta)|0\rangle + (-1)^{\text{Dec}(\alpha)} \sin(\theta)|1\rangle) \otimes |\text{aux}_{\alpha|\chi}\rangle\|^2 \\ & = \|1\rangle \otimes (\tilde{X}_B P_B^1 - (-1)^{\text{Dec}(\alpha)} \tan(\theta) P_B^0) |\Psi_{\alpha|\chi}\rangle\|^2 \\ & \le 2 \|(P_B^0 \tilde{X}_B - (-1)^{\text{Dec}(\alpha)} \tan(\theta) P_B^0) |\Psi_{\alpha|\chi}\rangle\|^2 + 2 \|(\tilde{X}_B P_B^1 - P_B^0 \tilde{X}_B) |\Psi_{\alpha|\chi}\rangle\|^2. \end{aligned} $$

Taking the expectation over $\chi: \text{Enc}(x = 1) = \chi$ and summing over $\alpha$, we can bound the second term by $\delta_6/2$ using Claim 11. Using the triangle inequality again,

$$ \begin{aligned} & 2\|(P_B^0 \tilde{X}_B - (-1)^{\text{Dec}(\alpha)} \tan(\theta) P_B^0) |\Psi_{\alpha|\chi}\rangle\|^2 \\ & \le 4\|((-1)^{\text{Dec}(\alpha)} P_B^0 \tilde{T}_{\theta,\phi} - (-1)^{\text{Dec}(\alpha)} \tan(\theta) P_B^0) |\Psi_{\alpha|\chi}\rangle\|^2 \\ & + 4\|P_B^0 (\tilde{X}_B - (-1)^{\text{Dec}(\alpha)} \tilde{T}_{\theta,\phi}) |\Psi_{\alpha|\chi}\rangle\|^2 \\ & \le 4\|(P_B^0 \tilde{T}_{\theta,\phi} - \tan(\theta) P_B^0) |\Psi_{\alpha|\chi}\rangle\|^2 \\ & + 4\|P_B^0\|_{\text{op}}^2 \|(\tilde{X}_B - (-1)^{\text{Dec}(\alpha)} \tilde{T}_{\theta,\phi}) |\Psi_{\alpha|\chi}\rangle\|^2, \end{aligned} $$

where $\tilde{T}_{\theta,\phi} = \frac{1}{\sin(2\theta)}(1 - \cos(2\theta)\tilde{Z}_B)$. Recall that $\|P_B^0\|_{\text{op}}^2 \le 1/2$, and after taking the expectation over $\chi: \text{Enc}(x = 1) = \chi$ and summing over $\alpha$, we can bound the second term using Claim 9, resulting in a contribution of $2\delta_5/(\sin^2(2\theta))$ to the final bound. Finally, by direct calculation we obtain

$$ P_B^0 \tilde{T}_{\theta,\phi} = \frac{1}{\sin(2\theta)} (P_B^0 - \cos(2\theta) P_B^0 \tilde{Z}_B) = \frac{1 - \cos(2\theta)}{\sin(2\theta)} P_B^0 = \tan(\theta) P_B^0, \quad (4.13) $$

which implies $\|(P_B^0 \tilde{T}_{\theta,\phi} - \tan(\theta) P_B^0) |\Psi_{\alpha|\chi}\rangle\|^2 = 0$. Summing the contributions from each application of the triangle inequality we arrive at the final bound. □

Theorems 4.7 and 4.8 complete the self-testing statement of the model without the action of measurements in the second round according to Theorem 4.5.
**Extracting the measurements** Next we turn our attention to the measurements.

**Claim 12.** $\mathbb{E}_{\chi:\text{Enc}(x)=\chi} \sum_{\alpha} \|(VZ_B - (\sigma_Z \otimes 1)V)|\Psi_{\alpha|\chi}\|^2 \le \delta_{8,x}$, where $\delta_{8,x} = \delta_0 + x \cdot \text{negl}(\lambda)$ for $x \in \{0,1\}$.

*Proof.* We first notice that

$$ (\sigma_Z \otimes 1)V|\Psi_{\alpha|\chi}\rangle = \sum_{b \in \{0,1\}} (-1)^b |b\rangle \otimes (\tilde{X}_B)^b P_B^b |\Psi_{\alpha|\chi}\rangle \\ = \sum_{b \in \{0,1\}} |b\rangle \otimes (\tilde{X}_B)^b P_B^b \tilde{Z}_B |\Psi_{\alpha|\chi}\rangle, $$

where we used the fact that $P_B^b \tilde{Z}_B = (-1)^b P_B^b$. Thus,

$$ \begin{aligned} \|(VZ_B - (\sigma_Z \otimes 1)V)|\Psi_{\alpha|\chi}\rangle\|^2 &= \left\| \sum_{b \in \{0,1\}} |b\rangle \otimes (\tilde{X}_B)^b P_B^b (Z_B - \tilde{Z}_B) |\Psi_{\alpha|\chi}\rangle \right\|^2 \\ &\le \left( \sum_{b \in \{0,1\}} \|(\tilde{X}_B)^b P_B^b\|_{\text{op}}^2 \right) \|(Z_B - \tilde{Z}_B) |\Psi_{\alpha|\chi}\rangle\|^2 \\ &\le \|(Z_B - \tilde{Z}_B) |\Psi_{\alpha|\chi}\rangle\|^2, \end{aligned} $$

For the second inequality, we used the fact that $\|P_B^b\|_{\text{op}}^2 \le 1/2$ and $\|\tilde{X}_B P_B^1\|_{\text{op}} = \|P_B^1\|_{\text{op}}$ since $\tilde{X}_B$ is unitary. For the case $\text{Enc}(x=0) = \chi$, taking the expectation, summing over $\alpha$ and applying Claim 5 recovers the desired bound. For the case $\text{Enc}(x=1) = \chi$, the same procedure with an intermediate application of Theorem 3.1, which accumulates an extra factor of $\text{negl}(\lambda)$, obtains the desired bound. $\square$

**Claim 13.** $\mathbb{E}_{\chi:\text{Enc}(x)=\chi} \sum_{\alpha} \|(VX_B - (\sigma_X \otimes 1)V)|\Psi_{\alpha|\chi}\rangle\|^2 \le \delta_{9,x}$, where $\delta_{9,x} = 2\delta_4 + 2\text{negl}(\lambda) \cdot (2-x) + \delta_6$.

*Proof.* By the triangle inequality

$$ \begin{aligned} \|(VX_B - (\sigma_X \otimes 1)V)|\Psi_{\alpha|\chi}\rangle\|^2 &\le 2\|V(X_B - \tilde{X}_B)|\Psi_{\alpha|\chi}\rangle\|^2 \\ &\quad + 2\|(V\tilde{X}_B - (\sigma_X \otimes 1)V)|\Psi_{\alpha|\chi}\rangle\|^2. \end{aligned} $$

For the first term,

$$ 2\|V(X_B - \tilde{X}_B)|\Psi_{\alpha|\chi}\rangle\|^2 \le 2\left(\sum_{b \in \{0,1\}} \|(\tilde{X}_B)^b P_B^b\|_{\text{op}}^2\right) \|(X_B - \tilde{X}_B)|\Psi_{\alpha|\chi}\rangle\|^2, $$

where we performed the same calculation in Claim 12, which after taking the expectation over $\text{Enc}(x) = \chi$ and summing over $\alpha$, results in a contribution of $2\delta_4$ when $x=0$ by Claim 6, and $2(\delta_4 + \text{negl}(\lambda))$ by Theorem 3.1 and Claim 6 when $x=1$.

For the second term we explicitly calculate

$$ V\tilde{X}_B - (\sigma_X \otimes 1)V = |0\rangle \otimes (P_B^0 \tilde{X}_B - \tilde{X}_B P_B^1) + |1\rangle \otimes (\tilde{X}_B P_B^1 \tilde{X}_B - P_B^0). $$

Taking the norm squared, we end up with the sum of two terms. The first is given by

$$ 2\|(P_B^0 \tilde{X}_B - \tilde{X}_B P_B^1)|\Psi_{\alpha|\chi}\rangle\|^2, $$
which after taking the expectation over $\text{Enc}(x) = \chi$ and summing over $\alpha$ results in a contribution of $\delta_6/2$ for $x = 1$ by Claim 11, and $2(\delta_6/4 + \text{negl}(\lambda))$ for $x = 0$ by Theorem 3.1 and Claim 11. By the unitarity of $\tilde{X}_B$ the second is equal to $\|(P_B^1 \tilde{X}_B - \tilde{X}_B P_B^0) |\Psi_{\alpha|\chi}\|^2$. This is bounded by the same quantity as the previous, by noting that the proof of Claim 11 is nearly identical with only the values $b$ of $P_B^b$ switched. $\square$

We are now ready to prove the final self-testing statement.

**Lemma 4.9.** Let $\tilde{Q}$ be any compiled model which satisfies $\tilde{\mathbb{E}}_S[S_{\theta,\phi}] \ge \eta_{\theta,\phi}^Q - \epsilon$, $\tilde{Q}^*$ be the compiled counterpart of model given in Eq. (3.18), and let $V$ be the SWAP isometry defined in Eq. (4.9). Then there exists auxiliary states $\{|\text{aux}_{\alpha|\chi}\rangle\}_{\alpha,\chi}$ such that for $x \in \{0,1\}$

$$ \chi: \text{Enc}(x) = \chi \sum_{\alpha} \| V N_{b|y} |\Psi_{\alpha|\chi}\rangle - Q_{b|y} |\varphi_{\text{Dec}(\alpha)|\chi}\rangle \otimes |\text{aux}_{\alpha|\chi}\rangle \|^2 \le \zeta_x, \quad (4.14) $$

$$ \text{where } \zeta_x = (\cos^2(\phi) \delta_{8,x} + \sin^2(\phi) \delta_{9,x})/2 + 2(1-x) \cdot \delta_7 + 2x \cdot \delta_0. $$

*Proof.* By definition $N_{b|y} = (1/2)(1 + (-1)^b[\cos(\phi) Z_B + (-1)^y \sin(\phi) X_B])$. We also have that the target measurements are given by $Q_{b|y} = (1/2)(1 + (-1)^b[\cos(\phi) \sigma_Z + (-1)^y \sin(\phi) \sigma_X])$ in Eq. (3.18). We first calculate

$$ \begin{aligned} VN_{b|y} |\Psi_{\alpha|\chi}\rangle - (Q_{b|y} \otimes 1)V |\Psi_{\alpha|\chi}\rangle &= \frac{(-1)^b \cos(\phi)}{2} (V Z_B - (\sigma_Z \otimes 1)V) |\Psi_{\alpha|\chi}\rangle \\ &\quad + \frac{(-1)^{b+y} \sin(\phi)}{2} (V X_B - (\sigma_X \otimes 1)V) |\Psi_{\alpha|\chi}\rangle. \end{aligned} $$

Taking the vector norm of both sides, applying the triangle inequality, then taking the expectation over $\text{Enc}(x) = \chi$ and summing over $\alpha$, we arrive at

$$ \chi: \text{Enc}(x) = \chi \sum_{\alpha} \|(VN_{b|y} - (Q_{b|y} \otimes 1)V)|\Psi_{\alpha|\chi}\rangle\|^2 \le \frac{\cos^2(\phi) \delta_{8,x} + \sin^2(\phi) \delta_{9,x}}{4} \quad (4.15) $$

by Claim 12 and Claim 13. Finally, we note that Theorems 4.7 and 4.8 imply the existence of states $\{|\text{aux}'_{\alpha|\chi}\rangle\}_{\alpha,\chi}$ such that

$$ \begin{aligned} \chi: \text{Enc}(x=0) = \chi \sum_{\alpha} \|(Q_{b|y} \otimes 1)V |\Psi_{\alpha|\chi}\rangle - Q_{b|y} |\text{Dec}(\alpha)\rangle \otimes |\text{aux}'_{\alpha|\chi}\rangle \|^2 &\le \delta_0, \\ \chi: \text{Enc}(x=1) = \chi \sum_{\alpha} \|(Q_{b|y} \otimes 1)V |\Psi_{\alpha|\chi}\rangle - Q_{b|y} (\cos(\theta)|0\rangle + (-1)^{\text{Dec}(\alpha)} \sin(\theta)|1\rangle) \otimes |\text{aux}'_{\alpha|\chi}\rangle \|^2 &\le \delta_7, \end{aligned} \quad (4.16) $$

where we used that vector norm can only decrease under the application of a projector $Q_{b|y} \otimes 1$. Note that for the honest strategy in Eq. (3.18), the compiled counterpart consists of the sub-normalized states

$$ \begin{aligned} |\varphi_{a|x=0}\rangle &= \begin{cases} \cos(\theta)|0\rangle_B & \text{if } a=0, \\ \sin(\theta)|1\rangle_B & \text{if } a=1, \end{cases} \\ |\varphi_{a|x=1}\rangle &= \frac{\cos(\theta)|0\rangle_B + (-1)^a \sin(\theta)|1\rangle_B}{\sqrt{2}}. \end{aligned} $$

For $\chi: \text{Enc}(x = 0) = \chi$, define $|\text{aux}_{\alpha|\chi}\rangle := |\text{aux}'_{\alpha|\chi}\rangle / \cos(\theta)$ for $\alpha: \text{Dec}(\alpha) = 0$, and $|\text{aux}_{\alpha|\chi}\rangle := |\text{aux}'_{\alpha|\chi}\rangle / \sin(\theta)$ for $\alpha: \text{Dec}(\alpha) = 1$. For $\chi: \text{Enc}(x = 1) = \chi$, define $|\text{aux}_{\alpha|\chi}\rangle := \sqrt{2}|\text{aux}'_{\alpha|\chi}\rangle$ for all $\alpha$.
Then the triangle inequality implies

$$ \|VN_{b|y}|\Psi_{\alpha|\chi}\rangle - Q_{b|y}|\varphi_{\text{Dec}(\alpha)|x}\rangle \otimes |\text{aux}_{\alpha|\chi}\rangle\|^2 \le 2\|VN_{b|y}|\Psi_{\alpha|\chi}\rangle - (Q_{b|y} \otimes 1)V|\Psi_{\alpha|\chi}\rangle\|^2 \\ + 2\|(Q_{b|y} \otimes 1)V|\Psi_{\alpha|\chi}\rangle - Q_{b|y}|\varphi_{\text{Dec}(\alpha)|\chi}\rangle \otimes |\text{aux}_{\alpha|\chi}\rangle\|^2, $$

which is bounded by Eqs. (4.15) and (4.16), after taking the expectation over $Enc(x) = \chi$ and summing over $\alpha$, by $\zeta_x = (\cos^2(\phi) \delta_{8,x} + \sin^2(\phi) \delta_{9,x}) + 2(1-x) \cdot \delta_7 + 2x \cdot \delta_0$. $\square$

*Proof of Theorem 4.6.* By noting that, for $x \in \{0, 1\}$, the functions $\zeta_x$, $\delta_0$, and $\delta_7$ are of the form $f(\epsilon) + \text{negl}(\lambda)''$, where $f(\epsilon) \ge 0$ and $f(0) = 0$, we see that Theorem 4.7 and Theorem 4.8 establish Eq. (4.2a), while Theorem 4.9 establishes Eq. (4.2b). Together this shows that the generalized tilted-CHSH expressions are a self-test according to Theorem 4.5, completing the proof. $\square$

## References

[ABCC24] Atul Singh Arora, Kishor Bharti, Alexandru Cojocaru, and Andrea Coladangelo. A computational test of contextuality and, even simpler proofs of quantumness. In *2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)*, page 1106–1125. IEEE, October 2024.

[ABG$^{+07}$] Antonio Acin, Nicolas Brunner, Nicolas Gisin, Serge Massar, Stefano Pironio, and Valerio Scarani. Device-independent security of quantum cryptography against collective attacks. *Physical Review Letters*, 98:230501, 2007.

[AMP12] Antonio Acín, Serge Massar, and Stefano Pironio. Randomness versus nonlocality and entanglement. *Physical Review Letters*, 108:100402, Mar 2012.

[Bel64] John S. Bell. On the Einstein Podolsky Rosen paradox. *Physics Physique Fizika*, 1(3):195, 1964.

[BJ15] Anne Broadbent and Stacey Jeffery. Quantum homomorphic encryption for circuits of low T-gate complexity. In *Annual Cryptology Conference*, pages 609–629. Springer, 2015.

[BP15] Cédric Bamps and Stefano Pironio. Sum-of-squares decompositions for a family of Clauser-Horne-Shimony-Holt-like inequalities and their application to self-testing. *Physical Review A*, 91:052111, May 2015.

[Bra18] Zvika Brakerski. Quantum FHE (almost) as secure as classical. In *Annual International Cryptology Conference*, pages 67–95. Springer, 2018.

[BSB24] Victor Barizien, Pavel Sekatski, and Jean-Daniel Bancal. Custom Bell inequalities from formal sums of squares. *Quantum*, 8:1333, May 2024.

[BVB$^{+24}$] Matilde Baroni, Quoc-Huy Vu, Boris Bourdoncle, Eleni Diamanti, Damian Markham, and Ivan Šupić. Quantum bounds for compiled XOR games and d-outcome CHSH games. *arXiv:2403.05502*, 2024.

[CGJV24] Andrea Coladangelo, Alex B Grilo, Stacey Jeffery, and Thomas Vidick. Verifier-on-a-leash: New schemes for verifiable delegated quantum computation, with quasilinear resources. *Theory of Computing*, 20(1):1–87, 2024.
[CGS17] Andrea Coladangelo, Koon Tong Goh, and Valerio Scarani. All pure bipartite entangled states can be self-tested. *Nature Communications*, 8(1), May 2017.

[CHSH69] J. F. Clauser, M. A. Horne, A. Shimony, and R. A. Holt. Proposed experiment to test local hidden-variable theories. *Physical Review Letters*, 23:880–884, 1969.

[CHTW04] Richard Cleve, Peter Hoyer, Benjamin Toner, and John Watrous. Consequences and limits of nonlocal strategies. In *Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004.*, pages 236–249. IEEE, 2004.

[CMM+24] David Cui, Giulio Malavolta, Arthur Mehta, Anand Natarajan, Connor Paddock, Simon Schmidt, Michael Walter, and Tina Zhang. A computational Tsirelson's theorem for the value of compiled XOR games. *arXiv preprint arXiv:2402.17301*, 2024.

[Col07] Roger Colbeck. *Quantum and Relativistic Protocols For Secure Multi-Party Computation*. PhD thesis, University of Cambridge, 2007. Also available as *arXiv:0911.3814*.

[Gri19] Alex Grilo. A simple protocol for verifiable delegation of quantum computation in one round. In *icalp2019*, pages 28:1–28:13, 2019.

[KLVY23] Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Lisa Yang. Quantum advantage from any non-local game. In *Proceedings of the 55th Annual ACM Symposium on Theory of Computing*, pages 1617–1628, 2023.

[KMCVY22] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani, and Norman Y. Yao. Classically verifiable quantum advantage from a computational Bell test. *Nature Physics*, 18(8):918–924, August 2022.

[KMP+24] Alexander Kulpe, Giulio Malavolta, Connor Paddock, Simon Schmidt, and Michael Walter. A bound on the quantum value of all compiled nonlocal games. *arXiv:2408.06711*, 2024.

[Mah20] Urmila Mahadev. Classical homomorphic encryption for quantum circuits. *SIAM Journal on Computing*, 52(6):FOCS18–189, 2020.

[MNZ24] Tony Metger, Anand Natarajan, and Tina Zhang. Succinct arguments for QMA from standard assumptions via compiled nonlocal games. *arXiv:2404.19754*, 2024.

[MV21] Tony Metger and Thomas Vidick. Self-testing of a single quantum device under computational assumptions. *Quantum*, 5:544, 2021.

[MY04] Dominic Mayers and Andrew Yao. Self testing quantum apparatus. *Quantum Information and Computation*, 4:273–286, 2004.

[MYS12] Matthew McKague, Tzyh Haur Yang, and Valerio Scarani. Robust self-testing of the singlet. *Journal of Physics A: Mathematical and Theoretical*, 45(45):455304, 2012.

[NPA08] Miguel Navascués, Stefano Pironio, and Antonio Acín. A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations. *New Journal of Physics*, 10(7):073013, 2008.

[NZ23] Anand Natarajan and Tina Zhang. Bounding the quantum value of compiled nonlocal games: from CHSH to BQP verification. In *2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)*, pages 1342–1348. IEEE, 2023.
[PAB+09] Stefano Pironio, Antonio Acin, Nicolas Brunner, Nicolas Gisin, Serge Massar, and Vallerio Scarani. Device-independent quantum key distribution secure against collective attacks. *New Journal of Physics*, 11(4):045021, 2009.

[PAM+10] S. Pironio, A. Acin, S. Massar, A. Boyer de la Giroday, D. N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T. A. Manning, and C. Monroe. Random numbers certified by Bell's theorem. *Nature*, 464:1021-1024, 2010.

[PSZZ23] Connor Paddock, William Slofstra, Yuming Zhao, and Yangchen Zhou. An operator-algebraic formulation of self-testing. *Annales Henri Poincaré*, 25(10):4283-4319, October 2023.

[RUV13] Ben Reichardt, Falk Unger, and Umesh Vazirani. Classical command of quantum systems. *Nature*, 496(7446):456-460, 2013.

[ŠB20] Ivan Šupić and Joseph Bowles. Self-testing of quantum systems: a review. *Quantum*, 4:337, Sep 2020.

[Sca12] Valerio Scarani. The device-independent outlook on quantum physics. *Acta Physica Slovaca*, 62(4):347-409, 2012.

[YN13] Tzyh Haur Yang and Miguel Navascués. Robust self-testing of unknown quantum systems into any entangled two-qubit states. *Physical Review A*, 87:050102, May 2013.

# A Appendix

## A.1 Efficient quantum circuits and homomorphic encryption

To define a quantum homomorphic encryption scheme we require the following concepts from quantum cryptography.

**Definition A.1.** A procedure $\mathcal{P}$ is quantum polynomial time (QPT) if:

1. there exists a uniform logspace family of quantum circuits that implement $\mathcal{P}$, and

2. the runtime of the circuit is polynomial in the number of qubits and the security parameter $\lambda \in \mathbb{N}$.

A family of quantum states $\mathcal{F}$ is QPT (preparable) if there is a QPT $\mathcal{P}$ for preparing $\mathcal{F}$.

We now define a quantum homomorphic encryption (QHE) scheme. A formal definition of QHE first appeared in [BJ15]. We follow the description of QHE outlined in [KLVY23, Bra18]:

**Definition A.2.** A quantum homomorphic encryption scheme $\mathcal{Q}$ for a family of circuits $\mathcal{C}$ consists of a security parameter $\lambda \in \mathbb{N}$ and the following algorithms:

(i) A PPT algorithm $\text{Gen}$ which takes as input a unary encoding $1^{\lambda}$ of the security parameter $\lambda \in \mathbb{N}$ and outputs a secret key $\text{sk}$.

(ii) A PPT algorithm $\text{Enc}$ which takes as input the secret key $\text{sk}$ and a plaintext $x \in \{0, 1\}^n$ and produces a ciphertext $\chi \in \{0, 1\}^k$.
(iii) A QPT algorithm Eval which takes as input a classical description of a quantum circuit C : $\mathcal{H} \otimes (\mathbb{C}^2)^{\otimes n} \to (\mathbb{C}^2)^{\otimes m}$ from $\mathcal{C}$, a quantum plaintext $|\Psi\rangle \in \mathcal{H}$ on a Hilbert space, a ciphertext $\chi$, and evaluates a quantum circuit Eval$_{C}(|\Psi\rangle \otimes |0\rangle)^{\text{poly}(\lambda,n)}$, $\chi$ producing a ciphertext $\alpha \in \{0, 1\}^l$.

(iv) A QPT algorithm Dec which takes as input ciphertext $\alpha$, and secret key sk, and produces a quantum state $|\Psi'\rangle$.

Although the existence of algorithms (i)-(iv) defines a QHE scheme, we consider several additional important properties a scheme may or may not possess:

1. (Correctness with auxiliary input). For every security parameter $\lambda \in \mathbb{N}$, secret key sk $\leftarrow$ Gen$(1^{\lambda})$, classical circuit C : $\mathcal{H}_A \otimes (\mathbb{C}^2)^{\otimes n} \to \{0, 1\}^m$, quantum state $|\Psi\rangle_{AB} \in \mathcal{H}_A \otimes \mathcal{H}_B$, plaintext $x \in \{0, 1\}^n$ ciphertext $\chi \leftarrow$ Enc$(x, sk)$, the following procedures produce states with negligible trace distance with respect to $\lambda$:

(a) Starting from the pair $(x, |\Psi\rangle_{AB})$, run the quantum circuit C on register A, outputting the classical string $a \in \{0, 1\}^m$ along with the contents of register B.

(b) Starting from $(\chi, |\Psi\rangle_{AB})$, run the circuit Eval$_{C}(\cdot)$ on register A, obtaining ciphertext $\alpha \in \{0, 1\}^l$, output $a' = \text{Dec}(\alpha, sk)$ along with the contents of register B.

2. (Security against efficient quantum distinguishers). Fix a secret key sk $\leftarrow$ Gen$(1^{\lambda})$. Any quantum polynomial time adversary $\mathfrak{A}$ with access to Enc$(\cdot, sk)$ (but does not know sk) cannot distinguish between ciphertexts $\chi \leftarrow$ Enc$(x_0, sk)$ and $\chi' \leftarrow$ Enc$(x_1, sk)$ with non-negligible probability in $\lambda$, where $x_0$ and $x_1$ are any plaintexts chosen by the adversary. That is

$$| \Pr[\mathfrak{A}^{\text{Enc}}(x_0, sk)(x_0) = 1] - \Pr[\mathfrak{A}^{\text{Enc}}(x_0, sk)(x_1) = 1] | \le \text{negl}(\lambda),$$

for all pairs $(x_0, x_1)$.

The KLVY compilation procedure requires schemes that satisfy (1) and (2). QHE schemes satisfying (1) and (2) have been described in [Mah20, Bra18].

## A.2 Additional proofs

*Proof of Theorem 3.2.* Let $V_y^{(\lambda)} : \mathcal{H}^{(\lambda)} \to \mathbb{C}^{|\mathcal{B}|} \otimes \mathcal{H}^{(\lambda)}$ be the isometry defined by

$$V_y^{(\lambda)}|\phi\rangle = \sum_{b \in \mathcal{B}} |b\rangle \otimes \sqrt{N_{b|y}^{(\lambda)}}|\phi\rangle, \quad \forall |\phi\rangle \in \mathcal{H}^{(\lambda)}. \qquad (A.1)$$

Furthermore, let $U_y^{(\lambda)}$ be the unitary which satisfies $U_y^{(\lambda)}(|0\rangle \otimes |\phi\rangle) = V_y^{(\lambda)}|\phi\rangle$ for all $|\phi\rangle \in \mathcal{H}^{(\lambda)}$. Define the projectors,

$$\tilde{N}_{b|y}^{(\lambda)} := U_y^{(\lambda)\dagger}(|b\rangle\langle b| \otimes \mathbb{1}) U_y^{(\lambda)}. \qquad (A.2)$$

Since $|\mathcal{B}|$ is constant with respect to $\lambda$ and each $N_{b|y}^{(\lambda)}$ is QPT, the resulting PVMs $\{\tilde{N}_{b|y}^{(\lambda)}\}_{b \in \mathcal{B}}$ are QPT for every $y \in \mathcal{Y}$. For the sub-normalized states, let $|\tilde{\Psi}_{\alpha|\chi}\rangle \in \mathcal{H}^{(\lambda)} \otimes \tilde{\mathcal{H}}^{(\lambda)}$ be any purification$^3$ of $\rho_{\alpha|\chi}^{(\lambda)}$ with $\mathcal{H}^{(\lambda)} \cong \tilde{\mathcal{H}}^{(\lambda)}$, and define

$$|\Psi_{\alpha|\chi}^{(\lambda)}\rangle := |0\rangle \otimes |\tilde{\Psi}_{\alpha|\chi}^{(\lambda)}\rangle \in \mathbb{C}^{|\mathcal{X}|} \otimes \mathcal{H}^{(\lambda)} \otimes \tilde{\mathcal{H}}^{(\lambda)} =: \mathcal{H}^{(\lambda)}. \qquad (A.3)$$

<footnote>$^3$Strictly speaking, since $\rho_{\alpha|\chi}^{(\lambda)}$ is sub-normalized, $|\tilde{\Psi}_{\alpha|\chi}^{(\lambda)}\rangle$ is equal to the purification of $\rho_{\alpha|\chi}^{(\lambda)}/\text{tr}[\rho_{\alpha|\chi}^{(\lambda)}]$ weighted by $\text{tr}[\rho_{\alpha|\chi}^{(\lambda)}]$, whenever $\text{tr}[\rho_{\alpha|\chi}^{(\lambda)}] > 0$.</footnote>
Again, since $|\chi|$ is constant with respect to $\lambda$ the (sub-normalized) states $|\Psi_{\alpha|\chi}^{(\lambda)}\rangle$ are QPT-preparable.

Now, extend each $\tilde{N}_{b|y}^{(\lambda)}$ to act trivially on the purifying system $\tilde{\mathcal{H}}^{(\lambda)}$ by defining $N_{b|y}^{(\lambda)} := \tilde{N}_{b|y}^{(\lambda)} \otimes 1$.
We observe

$$ 
\begin{align}
\mathrm{tr}[N_{b|y}^{(\lambda)} |\Psi_{\alpha|\chi}^{(\lambda)}\rangle\langle\Psi_{\alpha|\chi}^{(\lambda)}|] &= \mathrm{tr}[\tilde{N}_{b|y}^{(\lambda)} \mathrm{tr}_{\tilde{Q}}[|\Psi_{\alpha|\chi}^{(\lambda)}\rangle\langle\psi_{\alpha|\chi}^{(\lambda)}|]] \nonumber \\
&= \mathrm{tr}[\tilde{N}_{b|y}^{(\lambda)} (|0\rangle\langle0| \otimes \rho_{\alpha|\chi}^{(\lambda)})] \nonumber \\
&= \mathrm{tr}[(|b\rangle\langle b| \otimes 1) U_y^{(\lambda)} (|0\rangle\langle0| \otimes \rho_{\alpha|\chi}) U_y^{(\lambda)\dagger}] \tag{A.4} \\
&= \mathrm{tr}[\sqrt{N_{b|y}^{(\lambda)}} \rho_{\alpha|\chi}^{(\lambda)} \sqrt{N_{b|y}^{(\lambda)}}] = p^{(\lambda)}(\alpha, b|\chi, x), \nonumber
\end{align}
$$

where $\tilde{Q}$ denotes the purifying system $\tilde{\mathcal{H}}^{(\lambda)}$. Since $\tilde{\mathcal{H}}^{(\lambda)}$ has the same dimensions as $\mathcal{H}^{(\lambda)}$, the PVMs $N_{b|y}^{(\lambda)}$ are indeed QPT. $\square$

*Proof of Theorem 3.3.* To begin, we write

$$ 
\begin{align}
\tilde{\mathbb{E}}_S[P^\dagger P] &= \sum_{ij} \gamma_i^* \gamma_j \tilde{\mathbb{E}}_S[(A_x)^{k_i} w_i(B_0, B_1)(A_x)^{k_j} w_j(B_0, B_1)] \nonumber \\
&= \sum_{ij} \gamma_i^* \gamma_j \tilde{\mathbb{E}}_S[(A_x)^{k_i+k_j} \bar{w}_{ij}(B_0, B_1)], \tag{A.5}
\end{align}
$$

where we used the linearity of $\tilde{\mathbb{E}}_S[\cdot]$ in the first line, and in the second line we used the fact that $\tilde{\mathbb{E}}_S[w] = \tilde{\mathbb{E}}_S[\bar{w}]$ (where $\bar{w}$ is the canonical form of the monomial $w$), and defined $\bar{w}_{ij}$ to be the canonical form of $w_i w_j$. We now need to consider two types of terms. First, when $k_i \oplus k_j = 0$, we apply the definition in Eq. (3.10) in conjunction with Theorem 3.1 to write

$$ 
\begin{align}
& \sum_{ij:k_i \oplus k_j=0} \gamma_i^* \gamma_j \tilde{\mathbb{E}}_S[\bar{w}_{ij}(B_0, B_1)] \nonumber \\
&= \mathbb{E}_{x' \in \chi} \mathbb{E}_{\chi: \mathrm{Enc}(x')=\chi} \sum_{\alpha} \langle \Psi_{\alpha|\chi} | \left( \sum_{ij:k_i \oplus k_j=0} \gamma_i^* \gamma_j \bar{w}_{ij}(B_0, B_1) \right) | \Psi_{\alpha|\chi} \rangle \nonumber \\
&\approx_{\mathrm{negl}(\lambda)} \mathbb{E}_{\chi: \mathrm{Enc}(x)=\chi} \sum_{\alpha} \langle \Psi_{\alpha|\chi} | \left( \sum_{ij:k_i \oplus k_j=0} \gamma_i^* \gamma_j \bar{w}_{ij}(B_0, B_1) \right) | \Psi_{\alpha|\chi} \rangle \tag{A.6} \\
&= \sum_{ij:k_i \oplus k_j=0} \gamma_i^* \gamma_j \mathbb{E}_{\chi: \mathrm{Enc}(x)=\chi} \sum_{\alpha} \langle \Psi_{\alpha|\chi} | \bar{w}_{ij}(B_0, B_1) | \Psi_{\alpha|\chi} \rangle. \nonumber
\end{align}
$$
When $k_i \oplus k_j = 1$, we can apply Eq. (3.11) directly. Putting these two together, we observe

$$
\begin{align}
& \sum_{ij} \gamma_i^* \gamma_j \tilde{\mathbb{E}}_S [ (A_x)^{k_i+k_j} \bar{w}_{ij}(B_0, B_1) ] \nonumber \\
&= \sum_{ij:k_i \oplus k_j=0} \gamma_i^* \gamma_j \tilde{\mathbb{E}}_S [ \bar{w}_{ij} ] + \sum_{ij:k_i \oplus k_j=1} \gamma_i^* \gamma_j \tilde{\mathbb{E}}_S [ A_x \bar{w}_{ij} ] \nonumber \\
&\approx_{\text{negl}(\lambda)} \sum_{ij:k_i \oplus k_j=0} \gamma_i^* \gamma_j \sum_{\chi: \text{Enc}(x)=\chi} \langle \Psi_{\alpha|\chi} | \bar{w}_{ij}(B_0, B_1) | \Psi_{\alpha|\chi} \rangle \nonumber \\
&\quad + \sum_{ij:k_i \oplus k_j=1} \gamma_i^* \gamma_j \sum_{\chi: \text{Enc}(x)=\chi} (-1)^{\text{Dec}(\alpha)} \langle \Psi_{\alpha|\chi} | \bar{w}_{ij}(B_0, B_1) | \Psi_{\alpha|\chi} \rangle \tag{A.7} \\
&= \sum_{\chi: \text{Enc}(x)=\chi} \langle \Psi_{\alpha|\chi} | \sum_{ij} (-1)^{\text{Dec}(\alpha) \cdot (k_i+k_j)} \gamma_i^* \gamma_j w_i(B_0, B_1) w_j(B_0, B_1) | \Psi_{\alpha|\chi} \rangle \nonumber \\
&= \sum_{\chi: \text{Enc}(x)=\chi} \langle \Psi_{\alpha|\chi} | \left| \sum_i (-1)^{\text{Dec}(\alpha) \cdot k_i} \gamma_i w_i(B_0, B_1) \right|^2 | \Psi_{\alpha|\chi} \rangle \ge 0. \nonumber
\end{align}
$$

Where in the fifth line, we used the fact that Bob's observables satisfy the canonical relations, so we can always replace the canonical monomial $\bar{w}_{ij}$ with $w_i w_j$. The final line is obtained by noting the square inside the expectation. We therefore conclude $\tilde{\mathbb{E}}_S[P^\dagger P] \approx_{\text{negl}(\lambda)} h$ for some $h \ge 0$, which implies $|\tilde{\mathbb{E}}_S[P^\dagger P] - h| \le \text{negl}(\lambda)$, and $\tilde{\mathbb{E}}_S[P^\dagger P] \ge h - \text{negl}(\lambda) \ge -\text{negl}(\lambda)$ as required. Lastly, it is straightforward to verify from the definition that for any Bell functional $I$ we have $\tilde{\mathbb{E}}_S(I)$ recovers the expected value under $\tilde{\mathcal{Q}}$. $\square$