# Composable Framework for Device-Independent State Certification

Rutvij Bhavsar, Lewis Wooltorton, Joonwoo Bae

► To cite this version:

Rutvij Bhavsar, Lewis Wooltorton, Joonwoo Bae. Composable Framework for Device-Independent State Certification. PRX Quantum, 2025, 6 (4), pp.040356. 10.1103/1j5f-qjhx. hal-05466785

HAL Id: hal-05466785

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

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
Composable framework for device-independent state certification

Rutvij Bhavsar<sup>(a) (b)</sup>,<sup>1, *</sup> Lewis Wooltorton<sup>(a)</sup>,<sup>2, 3, 4, †</sup> and Joonwoo Bae<sup>1, ‡</sup>

<sup>1</sup>School of Electrical Engineering, Korea Advanced Institute of Science and Technology (KAIST),
291 Daehak-ro, Yuseong-gu, Daejeon 34141, Republic of Korea

<sup>2</sup>Department of Mathematics, University of York, Heslington, York, YO10 5DD, United Kingdom

<sup>3</sup>Quantum Engineering Centre for Doctoral Training,
H. H. Wills Physics Laboratory and Department of Electrical & Electronic Engineering,
University of Bristol, Bristol BS8 1FD, United Kingdom

<sup>4</sup>Inria, ENS de Lyon, LIP, 46 Allee d'Italie, 69364 Lyon Cedex 07, France

(Dated: 12<sup>th</sup> December, 2025)

Certifying a quantum state in a device-independent (DI) manner, in which no trust is placed on the internal workings of any physical components, is a fundamental task bearing various applications in quantum information theory. The composability of a state certification protocol is key to its integration as a subroutine within information-theoretic protocols. In this work, we present a composable certification of quantum states in a DI manner under the assumption that a source prepares a finite sequence of independent quantum states that are not necessarily identical. We show that the security relies on the DI analog of the fidelity, called the *extractability*. We develop methods to compute this quantity under local operations and classical communication in certain Bell scenarios that self-test the singlet state, which may also be of independent interest. Finally, we demonstrate our framework by certifying the singlet state in a composable and DI manner using the Clauser-Horne-Shimony-Holt inequality.

# I. INTRODUCTION

Certifying the non-classical properties of a source is essential for its use in quantum information processing. This is often achieved by modeling the physical mechanisms which govern either the source's behavior directly, or the measurements used to characterize it. However, deviations between a realistic implementation and this model are difficult to rule out, and any assumptions which are not met in practice could render the certification invalid. The device-independent (DI) approach [1–5] addresses this issue. Here, certification is obtained through the observation of nonlocal input-output correlations, removing the need to understand the source's inner workings or perform trusted measurements.

The aim of DI state certification (DISC) is to certify the presence of a certain multi-partite “target” state in a state that is stored in the memory of the user(s). Recently, there have been significant advances in DISC [6, 7], in which the states and measurements are treated as (separate) black-boxes, and tools from robust self-testing [8–10] enable certification when the source is not assumed to be independent and identically distributed (i.i.d.), and the collected statistics are finite. A related protocol was also outlined in [11, 12], where DI lower bounds on the rate of distillable entanglement were derived for non-i.i.d. sources. Such protocols have also been successfully demonstrated experimentally [13–15].

However, when using any protocol as a subroutine in a larger system, a notion of composability is essential. For example, in cryptography [1–4, 16–24], composable security statements ensure that the concatenation of two secure protocols results in another secure protocol [25, 26]. A composable approach to DISC is therefore crucial if the stored state is intended for many practical purposes.

We here address the need for the framework of composable certification and present composable guarantees for DISC protocols, enabling their integration as subroutines in broader information theoretic tasks, such as cryptography. Furthermore, our protocols only assume that finitely many independent states are emitted by the source, from which a single state is randomly selected and preserved in a memory for future applications. The remaining states then interact with measurement devices that can have a memory in general, and the statistics are used to certify the preserved state.

We prove the security of our protocol using the *extractability*, a DI variant of the fidelity between each measured state and the target [10, 27]. A bound on the extractability follows from observing a Bell inequality violation, and we provide a generic way to compute this quantity in Bell scenarios with binary inputs and binary outputs<fnref n="1" />, which may be of independent interest in the context of nonlocality and entanglement theory. Specifically, the standard definition of extractability quantifies how robust a self-test is, by measuring the minimal distance between a “physical” state which produces a given Bell violation and the target state. This distance is typically computed after applying local operations to the

<footnote>* rutvij.bhavsar@kcl.ac.uk</footnote>

<footnote>† lewis.wooltorton@ens-lyon.fr</footnote>

<footnote>‡ joonwoo.bae@kaist.ac.kr</footnote>

<footnote>(a) These authors contributed equally to this work.</footnote>

<footnote>(b) Current affiliation: Department of Mathematics, King's College London, Strand, London, WC2R 2LS, United Kingdom</footnote>

<footnote n="1">¹ We refer to this scenario with two parties as the minimal Bell scenario.</footnote>
physical state, accounting for degrees of freedom undetectable from the statistics alone [28]. However, this notion can be restrictive in the context of state certification protocols, where the relevant class of free operations may depend on both the intended application and the experimental setup. For example, in cryptographic settings, it is natural to consider local operations and classical communication (LOCC) as the allowed free operations. Our security framework can be applied to any chosen class of operations, and we propose a method to compute bounds on the extractability under LOCC for any Bell inequality in the minimal Bell scenario certifying the singlet state. As LOCC extractability is typically greater than that obtained under local operations alone, our protocols benefit from tighter security bounds than those derived using the standard approach.

The paper is structured as follows. In Sections II and III we provide the necessary background. In Section IV we introduce the measurement scenarios considered. Section V then outlines the corresponding DISC protocols. A composable security framework is then presented in Section VI, and in Section VII we bound the security of the introduced protocols according to this definition. Section VIII discusses the main tool needed to provide security, namely, how to bound the extractability. We then provide an explicit example using the Clauser-Horne-Shimony-Holt (CHSH) inequality in Section IX, and conclude with a discussion in Section X. All protocols and assumptions are detailed in Sections A and B, and the proofs of all security claims can be found in Sections C to E. A detailed derivation of the extractability bounds can be found in Section F.

## II. PRIOR WORK

Certifying properties of entangled states in a device-independent fashion has been extensively studied. Often considered is the amount of private randomness contained in the measurement outcomes, as a function of the observed Bell violation. This can be estimated in the asymptotic regime [2, 29-31], and lifted to the finite size setting using tools such as the entropy accumulation theorem [32-34] and quantum probability estimation framework [35], enabling composably secure DI randomness expansion [3, 4, 21-23], amplification [24, 36] and key distribution [1, 2, 16, 17, 19, 20].

A stronger characterization of the source is possible by estimating properties of the emitted states directly, rather than the measurements performed on them. For example, various entanglement measures can be quantified as a function of the observed Bell violation in the asymptotic regime [11, 37]. In the finite size regime, Refs. [11, 12] certify the largest number of maximally entangled states that can be extracted from an untrusted source under LOCC operations, a quantity known as the one-shot distillable entanglement. This protocol outputs a subset of states (intended for a future task) which the

entanglement certification applies to, and does not require an i.i.d. assumption on the source.

DISC achieves the strongest type of characterization, namely, that the states emitted by the source are close to (many copies of) a target state. Bancal et al. [6] provided a DI state verification protocol (in which all states are measured; see [7] for a detailed comparison between verification and certification) using the CHSH inequality. Notably, this protocol does not require an i.i.d. assumption on the source and was used to verify the successful distribution of entangled states via a quantum network link. Gočanin et al. [7] later developed a general framework for DI state verification based on any robust self-testing result. This approach achieves an optimal sample efficiency in the fully non-i.i.d. setting. The authors of Ref. [7] further propose a framework for DI state certification, which outputs multiple certified copies with an optimal sample efficiency under the assumption of an independently distributed source.

In the framework of Refs. [6, 7], the average extractability of the state ensemble is certified up to a fixed confidence level. This contrasts the definition of composable security adopted in cryptography, such as quantum key distribution (QKD), in which the distinguishability between an idealized version of the protocol and its real implementation is shown to be small [25, 26]. Applying such a framework to DISC is one of the new contributions of our work. Inspired by [7], we present a general framework for DISC based on extractability under the assumption of independent states. The key difference is that we introduce and apply a composable security definition inspired by quantum cryptography. We do however loose the sample efficiency achieved in [7], a trade off which is necessary in the case of exact certification (see Section V for a discussion of different types of certification) owing to the inherently stronger demand of composability [38]. As a proof of principle demonstration, we also consider certifying a single copy of the target state. Extending our framework to the certification of multiple copies in a sample-efficient and fully non-i.i.d. manner is a promising future direction, which we elaborate on in Section X. Additionally, while composability is not directly addressed in Refs. [11, 12], we expect an analysis similar to the one presented here would directly apply to one-shot distillable entanglement certification. However as aforementioned, certifying the state directly as considered in this work and [6, 7] is a stronger demand than certifying its distillable entanglement.

## III. NONLOCALITY AND SELF-TESTING

We now review self-testing, which can be viewed as a form of DI state verification in the asymptotic limit. Consider a bipartite Bell scenario, in which two non-communicating devices perform local measurements on some unknown shared quantum state. The inputs to each device are uniformly distributed binary random
variables, denoted X and Y, respectively. The outputs of each device are binary random variables, denoted A and B, which for a given pair of inputs X = x, Y = y are distributed according to the device's behavior, p = {p(a, b|x, y)}. A behavior is quantum if it can be realized by local quantum measurements on a bipartite state $ρ \in S(H_{QA} \otimes H_{QB})$, where S(H) denotes the set of normalized states on a Hilbert space H. Specifically, the probabilities are given by the Born rule, $p(a, b|x, y) = \text{tr}[(M_{a|x} \otimes N_{b|y})ρ]$, where $\{\{M_{a|x}\}_{a \in \{0,1\}}\}_{x \in \{0,1\}}$ and $\{\{N_{b|y}\}_{b \in \{0,1\}}\}_{y \in \{0,1\}}$ are POVMs on $H_{QA}$ and $H_{QB}$, respectively.

In certain cases, a given quantum behavior $p^* = \{p^*(a, b|x, y)\}$ guarantees the presence of a particular state $|ψ^*⟩$ up to operations which cannot be detected from the behavior, called local isometries. If this is the case, we say the behavior $p^*$ self-tests $|ψ^*⟩$ [8, 27]. Such statements are the strongest form of verification possible. However, in noisy systems it is often the case that the behavior $p^*$ cannot be achieved exactly. We say $p^*$ robustly self-tests $|ψ^*⟩$ if witnessing a behavior $p'$ $\epsilon$-close to $p$ guarantees the presence of a state $ρ'$ $\epsilon$-close to $ψ^* = |ψ^*⟩⟨ψ^*|$, according to a given metric (see, e.g., Ref. [27] for a definition). Robust self-testing can thus be viewed as a form of DI state verification when given access to infinitely many copies of an identical (potentially noisy) state.

Self-testing statements can also be formulated without relying on the full input-output distributions. One approach is to express them in terms of functionals of the behavior, which may be non-linear in general [39]. However, the most common and often more practical method is to use linear functionals, which correspond to Bell inequalities [40, 41].

In the minimal Bell scenario, it will be convenient to work with the expected values $⟨A_x⟩ = \sum_a (-1)^a p(a|x), ⟨B_y⟩ = \sum_b (-1)^b p(b|y)$ and $⟨A_x B_y⟩ = \sum_{a,b} (-1)^{a+b} p(a, b|x, y)$. When the behavior is quantum, we define the associated observables $A_x = \sum_a (-1)^a M_{a|x}$ and $B_y = \sum_b (-1)^b N_{b|y}$, which satisfy $⟨A_x B_y⟩ = \text{tr}[(A_x \otimes B_y)ρ], ⟨A_x⟩ = \text{tr}[(A_x \otimes \mathbb{I}_{QB})ρ]$ and $⟨B_y⟩ = \text{tr}[⟨\mathbb{I}_{QA} \otimes B_y)ρ]$. A Bell expression is then a linear combination of the probabilities $\{p(a, b|x, y)\}$, or equivalently the expectations $\{⟨A_x⟩, ⟨B_y⟩, ⟨A_x B_y⟩\}$, and for quantum behaviors we consider Bell operators of the form [42]

$$B = \sum_{x,y \in \{-1,0,1\}} c_{xy} A_x \otimes B_y, \quad (1)$$

for some real coefficients $c_{xy}$, where we defined $A_{-1} := \mathbb{I}_{QA}$ and $B_{-1} := \mathbb{I}_{QB}$. The Bell value is given by $⟨B⟩ = \text{tr}[Bρ]$ for a state $ρ$, and the maximum quantum and classical values of $⟨B⟩$ are denoted by $η^Q$ and $η^L$, respectively. A Bell inequality $⟨B⟩ \le η^L$ self-tests a state $|ψ^*⟩$ if every quantum state which achieves $⟨B⟩ = η^Q$ is equivalent to $|ψ^*⟩$ up to local isometries.

Of particular interest to this work are Bell inequalities which self-test the maximally entangled pair of qubits,

$φ^+ = |φ^+⟩⟨φ^+|$ where $|φ^+⟩ = (|00⟩ + |11⟩)/\sqrt{2}$. Such inequalities have been fully characterized in the minimal Bell scenario [43–46]. An important example is the CHSH inequality [41], which is the only non-trivial facet Bell inequality in this scenario up to relabelings. Its Bell operator takes the form $B_{CHSH} := A_0 \otimes (B_0 + B_1) + A_1 \otimes (B_0 - B_1)$, and has local and quantum bounds of 2 and $2\sqrt{2}$, respectively.

## IV. MEASUREMENT SCENARIOS

Real sources emit a finite sequence of non-i.i.d. states. Furthermore, a real measurement device may also be non-i.i.d., e.g., through the use of a memory. It is then clear that, on their own, self-testing statements are not enough for state verification or certification in practice. To address this, we consider certifying a source which emits $n$ independent but not necessarily identical states, $ρ = \bigotimes_{i=1}^n ρ_i$, where $ρ_i \in S(H_{QA} \otimes H_{QB})$. We also assume the user has access to a quantum memory in which states can be stored, and treat all measurement devices as black-boxes, making no assumptions on their internal workings.

<figure><img src="image_2.png" /><figcaption>FIG. 1: A figure illustrating the measurement channels on Alice's side. The channels on Bob's side have an identical structure. Solid lines indicate quantum systems, while dashed lines represent classical systems. $I_i^A$ and $O_i^A$ represent auxiliary information available to, and generated by, the measurement of $Q_i^A$, respectively. The generation of Alice's input $X_i$ is absorbed as part of the channel output, whilst $A_i$ represents the output of a quantum measurement.</figcaption></figure>

Associated to each index $i$ is a channel, $N_i^A : I_i^A Q_i^A \to A_i X_i O_i^A$, shown in Fig. 1. The systems $A_i X_i$ are classical, whilst $I_i^A$ contains any auxiliary information available to the device prior to measurement (e.g., information from previous rounds), and $O_i^A$ contains auxiliary output information (e.g., information to pass on to future rounds). The channel $N_i^A$ first samples the input $X_i$ and then performs the corresponding measurement on the (quantum) system held by the measurement device. Thus, while $X_i$ serves as an input to the measurement device, from this perspective it is naturally regarded as an output of the channel $N_i^A$. We similarly define channels $N_i^B : I_i^B Q_i^B \to B_i Y_i O_i^B$. A joint channel $N_i$ is described by performing $N_i^A$ and $N_i^B$ in a space-like separated manner, i.e., $N_i = N_i^A \otimes N_i^B$. Then, the systems
$X_iY_i$ and $A_iB_i$ denote the inputs and outputs to the Bell test, respectively.

We then consider two possible arrangements of the channels, corresponding to parallel and sequential setups. In the parallel setup, $n-1$ isolated measurement devices $M_i$ each receive $\rho_i$ and implement the channel $N_i$. Following the isolation of the devices, the auxiliary systems $I_i^A O_i^A$ and $I_i^B O_i^B$ can be omitted, and all measurements occur simultaneously. This can be equivalently viewed as the action of a single memoryless measurement device acting on each system sequentially. We illustrate this scenario in Fig. 2.

<figure><img src="image_3.png" /><figcaption>FIG. 2: The parallel setup, in which $n-1$ devices each perform an isolated measurement on a composite quantum system $Q_i = Q_i^A Q_i^B$. Each measurement is performed in an isolated manner with respect to the AB partition.</figcaption></figure>

In the sequential scenario, we consider a single measurement device $M$, which performs all channels in sequence. Specifically, the measurement of $\rho_i$ precedes that of $\rho_{i+1}$, and the auxiliary output $O_i^A$ is sent to the input $I_{i+1}^A$ (and similarly for $B$). In other words, we associate $I_{i+1}^A = O_i^A$ and $I_{i+1}^B = O_i^B$. Information in $O_i^A$ could, for example, consist of the inputs and outputs of rounds 1 to $i$. Note that systems pertaining to $A$ and $B$ are still assumed to be separated, e.g., $O_i^A$ cannot influence $I_{i+1}^B$. See Fig. 3 for an illustration.

We also introduce a random variable $T$, which takes values in $t \in \{1, ..., n\}$ according to a known distribution $\text{Pr}[T = t] = p_T(t)$, and is sampled prior to all measurements. Specifically, the value of $T$ decides which state is not measured and, instead, held in the quantum memory. Note that the variables $T$, $X$, and $Y$ are all sampled from distributions known to the users. While these distributions may also be known to the adversary, the adversary cannot access the actual realized values of $T$, $X$, or $Y$. For a detailed list of the assumptions made in this work, see Section A.

<figure><img src="image_4.png" /><figcaption>FIG. 3: The sequential setup, in which a single device performs all channels $N_i$ in a sequence on the systems $Q_i = Q_i^A Q_i^B$. The auxiliary information $O_i = O_i^A O_i^B$ generated by $N_i$ is fed forward as the input register $I_{i+1} = I_{i+1}^A I_{i+1}^B$ for the subsequent measurement $N_{i+1}$.</figcaption></figure>

V. PROTOCOLS

We consider DISC protocols of the following form. First, the state $\otimes_{i=1}^n \rho_i$ is prepared by an untrusted source, and accepted into the secure laboratory. The random variable $T$ is generated, and depending on its value, $T=t$, the state $\rho_t$ is stored in a quantum memory. Next, the remaining states are sent to the measurement device, and either the parallel or sequential measurement setup is performed. The statistics are collected, and if they deviate from an expected value, the protocol aborts. Specifically, Protocols 1 to 3 consist of a parallel setup, while Protocols 4 and 5 consist of a sequential setup.

In the event of not aborting, there are two possible variants of the protocol. In the first, the user applies a pre-decided channel (from the set of free operations) to the state stored in memory, with the aim of “extracting” a target state (Protocols 1, 2 and 4). However, performing this channel in practice may be unrealistic. Thus, in another variant, the user certifies the state held in memory to be equivalent to (i.e., has the potential to be converted to) the target up to the set of free operations (Protocols 3 and 5).

We also allow for freedom in the choice of target state. In Protocol 1, we consider extracting the target state $\psi^*$ (e.g., the maximally entangled state) exactly. Due to imperfections such as noise however, this is out of reach for many practical applications, resulting in an overly stringent security criteria. Instead, the user may wish to relax
this, and extract a state $\varepsilon$-close to $\psi^{*2}$, or guarantee that the final state can be converted to any state $\varepsilon$-close to $\psi^*$ under free operations. We allow for this modification in Protocols 2 to 5, where the distance of interest is the trace distance.

Additionally, we note that while the protocols outlined thus far are concerned with storing and certifying a single state, the proof techniques can be generalized to multiple states. However, the current bounds scale poorly with the number of states measured, and we leave improvements in sample efficiency, such as that presented in Ref. [7], to future work (see Section X for further discussion).

We provide a template for all protocols considered in this work below, followed by a summary of each variant in Table I. All variants are outlined in detail in Section B.

**Example 1 (CHSH-based DISC for the sequential setup).** Consider a source that produces $n$ bipartite states $\{\rho_i\}_{i=1}^n$. The goal is to certify that one of these states is $\varepsilon$-close to the maximally entangled pair of qubits $|\phi^+\rangle\langle\phi^+|$, in the sense that it can be converted by LOCC operations to some state $\tau$ that is $\varepsilon$-close to $|\phi^+\rangle\langle\phi^+|$. The protocol begins by choosing an index $t \in \{1, \dots, n\}$ at random and storing the corresponding state $\rho_t$ in a memory. Each of the remaining $n-1$ states are sent one by one to the same pair of non-communicating measurement devices<fnref n="3" />.

On every round $i \neq t$, each device receives a binary input $x_i$ (resp. $y_i$) chosen at random, and performs an unknown measurement on their share of the state $\rho_i$, producing a binary output $a_i$ (resp. $b_i$). A CHSH game is won in round $i$ if the outputs satisfy $a_i \oplus b_i = x_i \cdot y_i$, and is lost otherwise. From the $n-1$ measurement rounds, the empirical CHSH value is then computed, i.e., a value proportional to the number of rounds in which the CHSH game was won divided by $n-1$.

Depending on the desired security requirement—namely the soundness and completeness parameters introduced in Section VI—an abort threshold for the CHSH value is chosen. If the empirical value does not exceed this value, the protocol aborts. Otherwise, the protocol accepts, and the stored state $\rho_t$ is certified to be $\varepsilon$-close to $|\phi^+\rangle\langle\phi^+|$ under LOCC operations and up to the chosen security requirement. Intuitively, a smaller $\varepsilon$ corresponds to a stricter acceptance condition: for example, exact certification of the target state requires the observed CHSH value to be very close to the maximal quantum value $2\sqrt{2}$.

## Template protocol

Parameters:

$n \in \mathbb{N}^+$ – number of rounds.

$p_T$ – probability distribution of $T$.

$\omega_\#^-$ – expected value of the Bell functional.

$\kappa > 0$ – parameter to set completeness error (see Definition 2).

$\varepsilon \ge 0$ – closeness parameter (See Table I).

1. Generate a random number $T$ according to $p_T$. If $T = t$, then store the state $\rho_t$ in the memory.

2. Generate the input strings $\mathbf{X} = (X_1, \dots, X_n)$ and $\mathbf{Y} = (Y_1, \dots, Y_n)$ uniformly.

3. Depending upon the setup (see Table I and Section IV), perform the Bell tests using the generated input strings.

4. Estimate the Bell parameter $\omega_{\text{exp}}$ using the input-output statistics. If $\omega_{\text{exp}} \le \omega_\#^-$, then abort the protocol.

5. (Optional). From $\rho_t$, extract a state $\tilde{\rho}$ that is $\varepsilon$-close to the target state $\psi^*$.

<table><caption>TABLE I: Summary of all the protocols provided in this paper. “Setup” denotes the choice of measurement apparatus described in Section IV. “Target” indicates whether the final state is assessed to be close to a particular pure entangled state $\psi^*$, or any state $\varepsilon$-close to $\psi^*$ for some $\varepsilon > 0$. “Extraction channel” indicates whether an extraction channel (within the chosen class of free operations) is applied to the final state or not. In general, such a channel cannot be implemented in a device-independent fashion. Note that the assumptions of the parallel setup can also be satisfied using a single memoryless measurement device.</caption><thead><tr><th>Protocol</th><th>Setup</th><th>Target</th><th>Extraction channel</th></tr></thead><tbody><tr><td>1</td><td>Parallel</td><td>ψ<sup>*</sup></td><td>Yes</td></tr><tr><td>2</td><td>Parallel</td><td>ε-close to ψ<sup>*</sup></td><td>Yes</td></tr><tr><td>3</td><td>Parallel</td><td>ε-close to ψ<sup>*</sup></td><td>No</td></tr><tr><td>4</td><td>Sequential</td><td>ε-close to ψ<sup>*</sup></td><td>Yes</td></tr><tr><td>5</td><td>Sequential</td><td>ε-close to ψ<sup>*</sup></td><td>No</td></tr></tbody></table>

# VI. COMPOSABLE FRAMEWORK FOR DEVICE-INDEPENDENT STATE CERTIFICATION

Having outlined the protocol structure, we here introduce a composable security definition for DISC. The security of any protocol must be rigorously defined, and

<footnote n="2">² The notion of closeness referred to here, and throughout the paper, is with respect to the trace distance, unless stated otherwise. Specifically, a state $\rho$ is said to be $\varepsilon$-close to $\sigma$ if $\frac{1}{2}||\rho - \sigma||_1 \le \varepsilon$, where $||A||_1 := \text{tr}[\sqrt{A^\dagger A}]$ denotes the trace norm.</footnote>

<footnote n="3">³ The assumption that the devices are non-communicating can be justified in two standard ways: (i) by employing shielding mechanisms that prevent any exchange of information, or (ii) by enforcing space-like separation during the measurement rounds, which guarantees that the devices cannot signal to one another.</footnote>
the desired definition depends on its intended application. In cryptographic scenarios, the *composable security definition* [17, 24, 25, 26, 46–50] has been adopted as the gold standard. This definition is particularly valuable since it enables a protocol to be securely integrated into a larger, composite system as a subroutine, and typically consists of two error parameters: $\epsilon_s$, known as the *soundness error* (see Definition 1), and $\epsilon_c$, known as the *completeness error* (see Definition 2).

To illustrate the importance of composability in a state certification context, consider one of the DISC protocols described in Section V. A possible application is to use the certified state to generate a bit of secret key. This key might subsequently serve as input to another cryptographic protocol. Thus, proving the security of the DISC protocol in isolation is insufficient; we require a security definition that is robust enough to guarantee security when the protocol is used as a building block within a larger system.

In non-cryptographic contexts, security proofs often involve statements such as: *If the protocol does not abort, it outputs the desired state with a small failure probability.* However, such statements are generally not composable. For instance, consider an extreme adversarial strategy where the adversary sends copies of separable states in each round. By sheer luck, this strategy may achieve a large observed Bell value, despite being exceedingly unlikely. In this case, while the protocol mostly aborts, there remains a nonzero probability that it succeeds with an insecure output. If this output is then used in subsequent protocols (such as QKD) security guarantees break down, since conditioned on not aborting, the output state is always separable. By defining security conditioned on not aborting, the negligibly small probability that this attack succeeds has not been accounted for. In fact, the overall protocol is trivially secure under this attack since it almost always aborts.

Another example of insecurity arises from abort-based attacks. An adversary could manipulate the protocol to abort selectively in ways that are advantageous to them. For instance, consider a scenario where the adversary supplies the state

$$ \rho = \sigma_1 \otimes \psi^* \otimes \psi^* \otimes \dots \otimes \psi^* $$

where $\sigma_1$ is a separable state and the remaining states are target states ($\psi^*$). The adversary could further instruct the devices to perform optimal measurements on $\psi^*$ whenever a specific setting (e.g., $t=1$) is chosen. For all other settings, the adversary forces sub-optimal measurements, ensuring the protocol aborts. In such a scenario, whenever the protocol does not abort, the user is left with a separable state. Consequently, any future protocol relying on the non-aborting behavior of the DISC protocol is rendered insecure.

Adaptive adversarial strategies such as exploiting rare successful outcomes with separable states or leveraging abort-based attacks illustrate the inadequacy of non-composable security definitions. Specifically, while such

attacks can never be ruled out, they can be tolerated using a composable definition as we illustrate below. This is essential to ensure security guarantees remain even when the protocol is integrated into a larger protocol.

To prove that a protocol is componasably secure, it is necessary to define an *ideal protocol* (see, e.g., Refs. [26, 51, 52]), which aborts with the same probability as the real protocol, and produces a perfect output whenever it does not abort. Importantly, the ideal case is a hypothetical construct that cannot be implemented in practice–it represents a theoretically perfect protocol. A real protocol is then deemed secure if it is virtually indistinguishable from this ideal. Specifically, security is quantified via a hypothetical game, in which the user performs either the real or ideal protocol. A third-party, referred to as the *distinguisher*, is then tasked with identifying which protocol the user is running, with their success probability measuring security. Since the success probability of distinguishing two quantum states can be quantified using the trace distance, we define the following soundness criteria.

**Definition 1 (Soundness).** A DISC protocol is $\epsilon_s$-sound if

$$ \frac{1}{2} \| \rho_{\text{real}} - \rho_{\text{ideal}} \|_1 \le \epsilon_s, \qquad (2) $$

where $\rho_{\text{real}}$ and $\rho_{\text{ideal}}$ are the real and ideal protocol outputs, respectively, and $\|M\|_1 = \text{tr}\sqrt{M^\dagger M}$ is the trace norm of an operator $M$.

Note that when computing the distinguishing probability, the distinguisher is assumed to have access to all available side information, along with the output of the real protocol. However, they cannot access any private data generated during the protocol’s execution.

Appropriately defining an ideal protocol can be challenging in general, since one must demonstrate indistinguishability under all possible circumstances. For DISC however, the choice is relatively straightforward, and is inspired by existing definitions in QKD. We consider an ideal DISC protocol which outputs the target state (or an equivalent state up to free operations if the final extraction step is omitted) whenever the protocol does not abort. Furthermore, the ideal protocol aborts with the same probability as the real protocol. Note however this abort probability is not revealed to the user. Similarly, if the goal is to certify a state that is $\epsilon$-close (in trace distance) to the target state, the ideal protocol outputs any state $\rho$ which is $\epsilon$-close to $\psi^*$. A flow diagram comparing the real and ideal DISC protocol can be found in Fig. 4, and we provide technical details for all protocol variants in Sections C and D.

The soundness definition given above ensures that the real protocol is virtually indistinguishable from an ideal one, even under arbitrary adversarial strategies. This includes the aforementioned extreme cases where the protocol frequently aborts. In such situations, both the real and ideal protocols abort with high probability and
<figure><img src="image_5.png" /><figcaption>FIG. 4: Flow diagram describing the structure of the real and ideal DISC protocol. Here, {$\rho_i$}$_{i=1}^n$ denotes a sequence of independent states emitted by the source, $T$ is a uniform random variable which takes values $t \in \{1, ..., n\}$, and {$\rho_i$}$_{i \neq t}$ is shorthand for {$\rho_i$} : $i \in \{1, ..., n\} \setminus t$. The empirical Bell value obtained by measuring {$\rho_i$}$_{i \neq t}$ is denoted $\omega_{\text{exp}}$, while $\omega_{\#} - \kappa$ is the threshold Bell value below which the protocol aborts. For simplicity, we illustrate the variant in which the user outputs the extracted state $\Lambda(\rho_t)$.</figcaption></figure>

are therefore nearly indistinguishable, and hence secure. Specifically, an $\epsilon_s$-sound DISC protocol ensures that an abort based attack can only succeed with probability no larger than $\epsilon_s$.

However, if soundness is used as the sole criterion for security, a critical issue arises: a protocol that always aborts would trivially be considered secure, despite being of no practical use. To rule out such degenerate cases, we additionally require that there exists an honest implementation of the protocol that succeeds with high probability. This is captured by the notion of completeness error.

**Definition 2 (Completeness).** A DISC protocol is said to be $\epsilon_c$-complete if there exists an honest implementation that aborts with probability at most $\epsilon_c$.

An honest implementation of the protocol is a source and set of measurement devices that model the expected behavior of an experimental implementation.

**Example 2 (Honest implementation of a CHSH-based DISC protocol).** As a concrete example, recall the CHSH-based protocol discussed in the previous section (Example 1). An example of an honest implementation in this context is a source $S$ and measurement devices $M$ with the following description. The source prepares $n$ identical states {$\rho_i$}$_{i=1}^n$ of the form

$$ \rho_i = (1 - \mu) |\phi^+\rangle\langle\phi^+| + \mu \frac{\mathbb{I}_4}{4}, $$

where $\mu \in [0, 1]$ (for example, one may take $\mu = (4/3)\epsilon$ to match a desired robustness parameter $\frac{1}{2}\|\rho_i - \phi^+\|_1 = \epsilon$) and $\mathbb{I}_4$ is the identity operator in dimension 4. The measurement devices perform the CHSH projective measurements with observables$^4$

$$ \begin{aligned} A_0 &= \sigma_x, & A_1 &= \sigma_z, \\ B_0 &= \frac{1}{\sqrt{2}}(\sigma_z + \sigma_x), & B_1 &= \frac{1}{\sqrt{2}}(\sigma_z - \sigma_x), \end{aligned} $$

where $\sigma_x$, $\sigma_y$ and $\sigma_z$ are the Pauli operators. Under these settings, the expected value of the CHSH functional for the honest implementation $(S, M)$ is

$$ \omega(S, M) = \text{tr}[\rho_i B_{\text{CHSH}}] = (1 - \mu)2\sqrt{2}. $$

To achieve an $\epsilon_c$-complete protocol, one should compute a small deviation $\kappa > 0$ in the observed empirical value $\omega_{\text{exp}}$ such that

$$ \Pr[\omega_{\text{exp}} \ge \omega(S, M) - \kappa] \ge 1 - \epsilon_c. $$

We refer the reader to Section C for an example of this calculation.

**Remark 1.** An honest implementation is one concrete intended realization of the protocol (honest source and devices) that could be implemented in the lab; it serves as a guarantee that acceptance occurs with high probability for well-behaved devices. This is not to be confused with the ideal protocol in the definition of soundness (Definition 1): when proving soundness, we do not assume that the devices behave honestly.

Combining both completeness and soundness yields a complete notion of security within the composable framework.

**Definition 3 (Security).** A DISC protocol is $(\epsilon_s, \epsilon_c)$-secure if it is both $\epsilon_s$-sound and $\epsilon_c$-complete.

Specifically, this definition ensures that security is preserved when the protocol is composed with other information theoretic tasks. In particular, if a subsequent protocol is $\epsilon'_s$-sound, then the combined protocol that includes both the DISC protocol and the subsequent protocol will be $(\epsilon_s + \epsilon'_s)$-sound.

More concretely, consider a sequence of states $\rho_{\text{init}} = \bigotimes_{i=1}^n \rho_i$ which are certified by a DISC protocol $\mathcal{P}_1$, whose output is given by $\mathcal{P}_1(\rho_{\text{init}}) = \rho_{\text{real}}$ where $\mathcal{P}_1(\cdot)$ is a quantum channel describing the protocol's action. Let $\rho_{\text{ideal}}$ denote the ideal output state of $\mathcal{P}_1$, and suppose $\mathcal{P}_1$ is $\epsilon_1$ sound according to Definition 1, i.e.,

$$ \frac{1}{2} \| \rho_{\text{real}} - \rho_{\text{ideal}} \|_1 \le \epsilon_1. $$

<footnote>$^4$ Recall that, for binary projective measurements derived from observables with eigenvalues $\pm 1$, the POVM elements are $M_{a|x} = \frac{1}{2}(\mathbb{I} + (-1)^a A_x)$ and $N_{b|y} = \frac{1}{2}(\mathbb{I} + (-1)^b B_y)$, so that $M_{0|x} - M_{1|x} = A_x$ and $N_{0|y} - N_{1|y} = B_y$.</footnote>
Let $\mathcal{P}_2$ be a quantum channel describing the action of a subsequent protocol, which is $\epsilon_2$-sound. In particular, $\mathcal{P}_2$ satisfies

$$ \frac{1}{2} \|\mathcal{P}_2(\rho_{\text{ideal}}) - \sigma_{\text{ideal}}\|_1 \le \epsilon_2, $$

where $\sigma_{\text{ideal}}$ is the ideal output state of $\mathcal{P}_2$. What can we say about the composition $\mathcal{P}_2 \circ \mathcal{P}_1$ when acting on $\rho_{\text{init}}$? Using the triangle inequality and the soundness of $\mathcal{P}_2$,

$$ \frac{1}{2} \|\mathcal{P}_2 \circ \mathcal{P}_1(\rho_{\text{init}}) - \sigma_{\text{ideal}}\|_1 \\ \le \frac{1}{2} \|\mathcal{P}_2 \circ \mathcal{P}_1(\rho_{\text{init}}) - \mathcal{P}_2(\rho_{\text{ideal}})\|_1 + \epsilon_2. $$

By the contractivity of the trace distance under quantum channels (see, e.g., [53, Exercise 9.1.9]),

$$ \frac{1}{2} \|\mathcal{P}_2 \circ \mathcal{P}_1(\rho_{\text{init}}) - \mathcal{P}_2(\rho_{\text{ideal}})\|_1 \le \frac{1}{2} \|\mathcal{P}_1(\rho_{\text{init}}) - \rho_{\text{ideal}}\|_1 \le \epsilon_1, $$

where the second equality follows from the soundness of $\mathcal{P}_1$. Combining these facts,

$$ \frac{1}{2} \|\mathcal{P}_2 \circ \mathcal{P}_1(\rho_{\text{init}}) - \sigma_{\text{ideal}}\|_1 \le \epsilon_1 + \epsilon_2. $$

Thus, the protocol formed by composing $\mathcal{P}_1$ and $\mathcal{P}_2$ remains (at least) additively secure. A high level of security for the composite protocol can therefore be achieved whenever the individual protocols are themselves highly secure.

## VII. SECURITY PROOF

We are now ready to present our main result: proving the DISC protocol described in Section V is secure, according to the composable definition given in Section VI. For simplicity, we choose the target state to be the maximally entangled state $|\psi^*\rangle = |\phi^+\rangle$. However, the proof technique is general enough to replace $|\phi^+\rangle$ with any pure state which can be robustly self-tested, in the sense discussed in Section VIII. Furthermore, we restrict our analysis to the case where the abort condition is defined via a single linear function of the statistics. Specifically, we consider Bell functionals of the form

$$ \omega := \sum_{x,y \in \{0,1\}} \gamma_{xy} \langle A_x B_y \rangle, \quad (3) $$

for $\gamma_{xy} \in \mathbb{R}$, and the protocol aborts if the observed value $\omega_{\text{exp}}$ is below a threshold value $\omega_{\#} - \kappa$, where $\kappa > 0$ is chosen to achieve the desired completeness error. The associated Bell operator is given by $B$ in (1), and we define the maximum Bell coefficient $\gamma^* := \max_{x,y} |\gamma_{xy}|$. When dealing with the sequential setup, we present our results for the CHSH functional, i.e., the case $\gamma_{00} = \gamma_{01} = \gamma_{10} = -\gamma_{11} = 1$, and leave generalizations to future work. For the parallel setup however, the protocol allows for the use

of any Bell functional of the form (3), such as the family [46, Proposition 1]. The security proofs of all parallel protocols (Protocols 1 to 3 described in Section B1) are given in Section C. For the sequential protocols (Protocols 4 and 5 described in Section B2), security is proven in Section D.

In the remainder of this section, we present the security proof of one of the aforementioned protocols in detail. All other cases follow a similar structure, and details can be found in the Appendix. Specifically, below we consider the parallel protocol when the objective is to certify a state $\epsilon$-close to the target state, corresponding to Protocol 2 in Section B1.

**Theorem 1.** The DISC protocol 2 is $\epsilon_s$-sound with $\epsilon_s$ equal to the following:

$$ \inf_{\delta>0} \max \left\{ \exp\left(-\frac{n-1}{\gamma^*} \delta^2\right), G_{\epsilon}\left(\frac{n-1}{n}[\omega_{\#} - \kappa - \delta] + \frac{\eta_{\min}^{\text{Q}}}{n}\right) \right\}, $$

where $G_{\epsilon}(\omega)$ is any non-increasing concave function that upper-bounds the function

$$ \Theta(\sqrt{1 - \Xi_B(\omega)} - \epsilon) \cdot (\sqrt{1 - \Xi_B(\omega)} - \epsilon). $$

Here, $\Theta$ is the Heaviside step function, $n$ is the total number of independent states generated by the source, the Bell value $\omega$ is given by (3), which has a minimum quantum value $\eta_{\min}^{\text{Q}}$, $\omega_{\#} - \kappa$ is the value that defines the abort condition where $\kappa > 0$ chosen to achieve the desired completeness error, and $\Xi_B(\omega)$ is the extractability function given in Definition 4 (see also Figure 5).

Proof can be found in Section C2 (cf. Lemma 3). For this work, we choose $G_{\epsilon}(\cdot)$ to be the function

$$ G_{\epsilon}(\omega) := - \text{convenv}\left(-\xi_B(\omega, \epsilon) \cdot \Theta(\xi_B(\omega, \epsilon))\right), \quad (4) $$

where $\xi_B(\omega, \epsilon) := \sqrt{1 - \Xi_B(\omega)} - \epsilon$, and convenv(·) denotes the convex envelope, i.e., the tightest convex lower bound of a given function (see the Remark 6 for details on its computation). This choice ensures that $G_{\epsilon}(\omega)$ is the optimal concave function required in Theorem 1. Moreover, while Theorem 1 is concerned with soundness, we also provide a proof of completeness in Lemma 2.

The soundness parameter $\epsilon_s$ depends on two terms: $\exp(-\frac{n-1}{\gamma^*} \delta^2)$ and $G_{\epsilon}(\frac{n-1}{n}[\omega_{\#} - \kappa - \delta])$. Both need to be sufficiently small to guarantee security, and each can be understood as a distinct type of penalty. The former penalty increases when the number of copies used for testing is small. Finite statistics effects are prominent in this case, resulting in low statistical confidence of the observed Bell value and weaker security. The second penalty is defined in terms of the so-called extractability [10, 54, 55], which is a function that indicates how close a state achieving a given Bell violation is to any state in the equivalence class (i.e., any state that can be transformed into the target state using the allowed class of operations) of the target state. Bounding this quantity then becomes the central task in proving security.
<figure><img src="image_6.png" /><figcaption>FIG. 5: Definition of the extractibility function. Extractibility quantifies how close a state can be to a target state (or to one that can be converted to the target under a chosen set of channels). It is defined via a min-max optimization, which is generally difficult to compute or bound.</figcaption></figure>

VIII. EXTRACTABILITY

Let us here elaborate on the extractability, $\Xi_B(\omega)$, a robustness measure in the context of the security proof. The extractability represents the worst case fidelity between the target state and any state achieving a given Bell violation, following the application of an extraction channel from a set of free operations. Typically, these are taken to be local operations (LO), which originates from the notion of local isometries discussed in Section III (see Ref. [28] for the precise connection). This quantity has played a central role in previous works on DISC [7, 13].

Throughout, we consider the extractability under a general class of operations, denoted by $\mathcal{C}$. The choice of $\mathcal{C}$ can be tailored to specific setups, particularly with future protocols in mind. In tasks such as QKD and entanglement distillation, LOCC can be chosen as the class of free operations. The LOCC class includes the LO class, and its use is beneficial since it provides tighter security. Specifically, computing tight lower bounds on the LO extractability for even the simplest case of the CHSH inequality is currently an open question. It is further known that for any CHSH violation up to approximately 2.05 [28, 56], a non-trivial LO extractability is not possible$^5$. In contrast, tight bounds on the LOCC extractability for the CHSH inequality are known to be non-trivial for any non-zero violation [54].

We emphasize here that permitting LOCC extraction channels does not enable classical communication between the devices during the Bell test. Indeed, if this were the case, DI certification would become impossible. In our protocol, all classical communication happens strictly after the devices have performed their measurements, during which the user can enforce space-like separation.

We also remark that when the target state is the singlet $|\phi^+\rangle$, extractability under LOCC is closely related to the one-shot distillable entanglement defined in [11].

**Definition 4 (Extractability).** Let $\mathcal{C}$ be a class of free operations between a physical system $Q_A Q_B$ and a target system $\hat{Q}_A \hat{Q}_B$, $B$ be a Bell operator, and $\mathcal{B}_\omega \subset \mathcal{S}(\mathcal{H}_{Q_A} \otimes \mathcal{H}_{Q_B})$ be the set of states in $Q_A Q_B$ that can achieve the Bell value $\langle B \rangle \ge \omega$ using some measurements. Given a target state $\psi^* \in \mathcal{S}(\mathcal{H}_{\hat{Q}_A} \otimes \mathcal{H}_{\hat{Q}_B})$, the extractability $\Xi_B(\omega)$ is defined via the following min-max optimization problem:

$$ \Xi_B(\omega) := \inf_{\rho \in \mathcal{B}_\omega} \sup_{\Lambda \in \mathcal{C}} F(\Lambda(\rho), \psi^*), \quad (5) $$

where $F(\rho, \sigma) = \|\sqrt{\rho}\sqrt{\sigma}\|_1^2$ is the fidelity between two states $\rho, \sigma \in \mathcal{S}(\mathcal{H})$.

**Example 3 (Extractability of CHSH under LO channels).** To gain some intuition on how the extractability behaves, consider the CHSH extractability. For simplicity, let us consider the case where $Q_A, Q_B, \hat{Q}_A$ and $\hat{Q}_B$ are all qubit systems, $\mathcal{C}$ is the set of LO operations and $\psi^* = \phi^+$. It is known that all two-qubit states $\rho$ which achieve maximum violation, $\langle B_{CHSH} \rangle = 2\sqrt{2}$, are of the form $(U_A \otimes U_B)\phi^+(U_A \otimes U_B)^\dagger$ for some local unitary $U_A \otimes U_B$ (see, e.g., [46, Lemma 10]). In other words, every $\rho \in \mathcal{B}_{2\sqrt{2}}$ must be of this form. We then immediately see that for any $\rho \in \mathcal{B}_{2\sqrt{2}}$, there exists a $\Lambda \in \mathcal{C}$ such that

$$ F(\Lambda(\rho), \phi^+) = 1, \quad (6) $$

namely, $\Lambda(\rho) = (U_A \otimes U_B)^\dagger \rho (U_A \otimes U_B)$, implying $\Xi_{B_{CHSH}}^{LO}(2\sqrt{2}) = 1$.

For the other extreme, consider the set of possible states which achieve a CHSH value of $\omega = 2$. The extractability can always be lower bounded by choosing a fixed channel of the form $\Lambda(\rho) = |00\rangle\langle 00| \forall \rho$, which satisfies $F(\Lambda(\rho), \phi^+) = 1/2$. We therefore see $\Xi_{B_{CHSH}}^{LO}(2) \ge 1/2$. Moreover, the state $|00\rangle\langle 00|$ belongs to $\mathcal{B}_2$, and $F(\Lambda(|00\rangle\langle 00|), \phi^+) \le 1/2$ for all local channels $\Lambda^6$. This implies $\Xi_{B_{CHSH}}^{LO}(2) \le 1/2$, and hence $\Xi_{B_{CHSH}}^{LO}(2) = 1/2$.

The extractability of CHSH under LO channels thus takes values in the interval $[1/2, 1]$ for $\omega \in [2, 2\sqrt{2}]$. It was shown by Kaniewski [10] that a lower bound for all $\omega \in [2, 2\sqrt{2}]$ is given by

$$ \Xi_{B_{CHSH}}^{LO}(\omega) \ge \max \left\{ \frac{1}{2} \left( 1 + \frac{\omega - \omega^*}{2\sqrt{2} - \omega^*} \right), \frac{1}{2} \right\}, \quad (7) $$

where $\omega^* = (16+14\sqrt{2})/17 \approx 2.11$ is the threshold CHSH value below which the extractibility is trivial (below 1/2).

<footnote n="5">5 The trivial extractability in this context is the maximum fidelity between any separable state and the target state (see [27, Section 3.6] for details). This value can always be achieved regardless of the underlying state. See also Example 3.</footnote>

<footnote n="6">6 This follows from the fact that the maximum fidelity between $\phi^+$ and $\Lambda(|00\rangle\langle 00|)$ is achieved when $\Lambda(|00\rangle\langle 00|)$ is any pure separable state corresponding to the largest Schmidt coefficient of $|\phi^+\rangle$.</footnote>
It was shown by Refs. [28, 56] that this threshold cannot be lowered below ≈ 2.05. This contrasts the tight bound on $\Xi_{B_{CHSH}}$ when $C$ is taken to be the class of LOCC operations, derived by Bardyn et al. [54]:

$$ \Xi_{B_{CHSH}}^{\text{LOCC}}(\omega) = \frac{1}{2} \left(1 + \frac{\omega - 2}{2\sqrt{2} - 2}\right). \qquad (8) $$

The extractability function involves two levels of optimization. The inner optimization considers a state $\rho$ that can achieve the Bell value $\omega$ and aims to transform it, via operations in the class $C$, to a state as close as possible (in terms of fidelity, rather than trace distance) to the target state $\psi^*$. This provides a meaningful measure of how close a state is to the equivalence class of the target state. The outer optimization then finds the state $\rho$ for which this distance is smallest, provided $\rho$ can achieve the given Bell value $\omega$ via some local measurement strategy.

Computing the extractability function is challenging in general, since it involves a min-max optimization. Furthermore, the optimization runs over all channels in a given class, and all states compatible with a Bell value $\omega$, without assuming their dimension. Additionally, the constraint $\rho \in \mathcal{B}_{\omega}$ is nonlinear in both the state and the measurements. To address these challenges, existing works (focused on LO extractability) have bypassed the inner optimization over channels by selecting a fixed channel for all states $\rho$ and values $\omega$, resulting in a valid lower bound [10]. The issue of not assuming the system dimension can, in general, be handled numerically via moment matrix approaches [55], or in the special case of Bell scenarios with binary inputs and binary outputs via a reduction to qubits known as Jordan's lemma [57].

We here derive a sequence of lower bounds on the LOCC extractability in the minimal Bell scenario for Bell functionals of the form (3). Moreover, our bounds can be improved further at the expense of increasing computational cost. Our results are summarized in Theorem 2, and the following text explains how this can be used to obtain a sequence of lower bounds.

**Theorem 2.** Let $B$ be any Bell functional of the form (3) in the minimal Bell scenario. Then the LOCC extractability $\Xi_B(\omega)$ satisfies:

$$ \Xi_B(\omega) \ge \text{convenv} \left( \min_{(a,b) \in \mathcal{F}_{\omega}} f_{a,b}(\omega) \right), \qquad (9) $$

where convenv(·) is the convex envelope (tightest convex lower bound) and

$$ \begin{aligned} f_{a,b}(\omega) &:= \max \lambda \omega + \mu \\ \text{s.t.} \quad & \sigma - \lambda B(a,b) - \mu \mathbb{I}_4 \ge 0, \\ \text{tr}_{\hat{Q}_A}[\sigma] &= \text{tr}_{\hat{Q}_B}[\sigma] = \frac{\mathbb{I}_2}{2}, \\ \sigma &\in \mathcal{S}_2, \quad \lambda \ge 0, \mu \in \mathbb{R}. \end{aligned} \qquad (10) $$

Here $\mathcal{S}_2 = \mathcal{S}(\mathcal{H}_{\hat{Q}_A} \otimes \mathcal{H}_{\hat{Q}_B})$ is the set of two-qubit density operators and $B(a,b)$ is the Bell operator B constructed

from the qubit observables:

$$ \begin{aligned} A_x &= \cos(a) \sigma_Z + (-1)^x \sin(a) \sigma_X, \\ B_y &= \cos(b) \sigma_Z + (-1)^y \sin(b) \sigma_X. \end{aligned} $$

The set $\mathcal{F}_{\omega}$ is defined as:

$$ \mathcal{F}_{\omega} = \{(a, b) \in [0, \pi/2]^{\times 2} : \exists \rho \in \mathcal{S}_2 \text{ s.t. } \text{tr}[B(a, b)\rho] \ge \omega\}. $$

The proof of Theorem 2 is presented in Section F 3, (see also Fig. 11 for an informal overview) and let us here discuss its implications. The first significant aspect of this result is the dimensional reduction of the optimization problem required to compute the extractability. By employing Jordan's lemma, we reduce the problem to effectively computing the extractability function within the state space of a qubit pair. Subsequently, we perform a series of reductions inspired by techniques from device-independent randomness generation and QKD protocols in the minimal Bell scenario [17, 30, 37, 58]. These reductions, combined with other technical results, allow us to reformulate the optimization over unital LOCC channels into a standard optimization problem over a bounded domain.

Assuming the projective measurements performed by the two devices on the qubit pair are known, the extractability can be computed numerically. This follows from the fact that, for a fixed $(a, b) \in \mathbb{R}^2$, the optimization (10) is a semidefinite program (SDP), which can be efficiently solved using numerical techniques [59]. However, the outer maximization over all possible two-qubit Bell operators $B(a, b)$ still remains, complicating the original problem as it is no longer an SDP.

To address this, we develop a technique to discretize the parameter space of the angles $(a, b) \in [0, \pi/2] \times [0, \pi/2]$ into smaller rectangular domains (see Appendix F 4). This discretization transforms the problem into solving multiple SDPs of the form (10), each corresponding to a specific grid point within the rectangular domains. Specifically, for each domain, we relax the optimization problem and introduce a penalty term that scales with the dimensions of the domain, ensuring we reliably lower bound the global minimization. By reducing the size of each rectangular domain, we achieve tighter bounds on the extractability function at the cost of solving more optimization problems, and thus an increased computation time. Furthermore, as the size of each rectangle tends to zero, the method converges to a tighter lower bound on the LOCC extractability.

Note that an analytic method for computing extractability in the LOCC case was first introduced in [54], where only the CHSH functional was considered. The approach presented here is significantly more general, encompassing more self-tests of the singlet– that is, it applies to all Bell inequalities of the form (3). Moreover, our method allows for the simultaneous use of multiple Bell inequalities, or even the full distribution, when bounding
the extractability. As a result, it provides a framework for obtaining lower bounds in the minimal Bell scenario when self-testing the singlet. Additionally, while Theorem 2 addresses the LOCC extractability, our gridding techniques can also be applied to other classes of free operations, such as the LO extractability for arbitrary Bell functionals in the minimal scenario, including those tailored to partially entangled states [28, 60, 61].

## IX. RESULTS FOR EXAMPLE 1: CHSH BASED PROTOCOL FOR CERTIFYING $\phi^+$

To illustrate our results, we consider a DISC protocol based on violating the CHSH inequality in the parallel measurement setup, where the objective is to certify a state $\varepsilon$-close to $\phi^+$ (see Protocol 2 in the appendix). A bound on the CHSH LOCC extractability was provided in [54], given by the linear function $\Xi_{CHSH}(\omega) \geq 1/2 + (\omega - 2)/(4\sqrt{2} - 4) =: g(\omega)$ for $\omega \in [2, 2\sqrt{2}]$. Using this bound, we plot the penalty function $G_{\varepsilon}(\omega)$ (defined via substituting $\Xi_B(\omega)$ in (4) with the function $g(\omega)$) in Fig. 6, which provides an estimate of the security bounds as a function of the chosen abort condition, characterized by the Bell value $\omega$.

<figure><img src="image_7.png" /><figcaption>FIG. 6: Graph of $G_{\varepsilon}(\omega)$ for different values of $\varepsilon$, using LOCC extractability.</figcaption></figure>

Knowing $G_{\varepsilon}(\omega)$ enables us to compute the security bounds for the protocol via Theorem 1, which we present in Fig. 7. From this figure, two key trends emerge: first, we obtain tighter security from higher CHSH values $\omega$, which arises from a smaller value of $G_{\varepsilon}(\omega)$. Secondly, security improves as the number of rounds increases, owing to a smaller penalty due to finite statistics (captured by the exponential term in Theorem 1). Additionally, we observe that for larger values of the closeness parameter $\varepsilon$, security is higher for the same Bell value and number of rounds. This is expected, as certifying a state that is $\varepsilon$-close to the target state requires a lower Bell value than certifying the target state exactly. Thus, increasing $\varepsilon$ results in a smaller values of $G_{\varepsilon}(\omega)$, corresponding to a smaller penalty.

<figure><img src="image_8.png" /><figcaption>(a) Plot of the security parameter $\epsilon_s$ versus the number of rounds $n$ for different CHSH values $\omega$. Here, we set $\varepsilon = 0.1$ and $\kappa$ is chosen to achieve a completeness error of $\epsilon_c = 10^{-2}$. The choice of $\epsilon_c$ follows standard values used in related device-independent protocols (see, e.g., [20]).</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>(b) Plot of the security parameter $\epsilon_s$ versus the number of rounds $n$ for different values of $\varepsilon$, assuming a CHSH value of $\omega = 2\sqrt{2}$. The parameter $\kappa$ is chosen to achieve a completeness error of $\epsilon_c = 10^{-2}$.</figcaption></figure>

<caption>FIG. 7: Comparison of security parameters for different conditions using the CHSH inequality.</caption>

## X. DISCUSSION

We have presented a composable approach for device-independent state certification under the assumption of an independent but not identically distributed source. We introduced a definition for composable DISC security, and provided a general framework for proving security in the two-input two-output Bell scenario under LOCC operations.

For future directions, it would be interesting to apply our protocols in practice. Clearly, the advantage lies in the composable integration of DISC with any other composable protocol. For example, consider a protocol $\mathcal{P}$ which, when given as input the state $\phi^+$, out-
puts a state $\mathcal{P}(\phi^+)$ satisfying $\|\mathcal{P}(\phi^+) - \sigma_{\text{ideal}}\|_1 \le \epsilon'$, where $\sigma_{\text{ideal}}$ is some target output state of $\mathcal{P}$. Now, suppose the DISC protocol outputs a state $\rho_{\text{real}}$ with the property$^7$ $\|\rho_{\text{real}} - \phi_+\|_1 \le \epsilon$. Then the composable security definition ensures that, when the DISC protocol output is used as an input to $\mathcal{P}$, the result is secure: $\|\mathcal{P}(\rho_{\text{real}}) - \sigma_{\text{ideal}}\|_1 \le \epsilon + \epsilon'$. Such applications might include the certification of other quantum resources, along the lines of Ref. [62], where state certification is an essential building block.

We also note that DISC is not vulnerable to the same device-reuse attacks as in, e.g., DIQKD [63]. This follows from the fact that no classical information is kept private from an adversary during the protocol. It is then an interesting question if DISC always remains secure when the measurement devices are reused.

It would also be interesting to improve the DISC security statement. Both a large Bell violation and a large number of copies are currently required to obtain a composable security proof, which is limiting in practice. This could be due to two reasons. First, the proof technique relies on inequalities and bounds that may not be tight, suggesting room for improvement in obtaining sharper security bounds. For example, our security proof employs Hoeffding's inequality, which could potentially be replaced by tighter alternatives such as those used in Ref. [7]. The second reason is that, from a fundamental point of view, it is an inherently strong requirement to ensure general security under any future protocol usage. Consequently, achieving tight security bounds for small Bell violations and low numbers of rounds may be infeasible [38].

Nevertheless, it is notable that composable security can be achieved. Moreover, our security bounds are tighter than those obtained using LO extractability bounds. In realistic experimental implementations, improved certification could be achieved by relaxing the stringent fully DI assumptions and incorporating justified partial assumptions. For instance, the fair sampling assumption could be employed to account for poor detector efficiencies. Additionally, similar results may be obtained in a semi-DI setting, where assumptions on system dimensions are introduced.

Another promising direction would be to certify more than one copy of the target state. In fact, our current approach can be straightforwardly modified to accommodate this. However, the soundness parameter $\epsilon_s$ scales as $\sqrt{1 - c^m}$, where $c$ is the single copy extractability for the threshold Bell value which does not cause the protocol to abort, and $m$ is the number of certified copies. We therefore see that the resulting protocol will not be efficient, in the sense that a large number of copies can only be certified when $c \approx 1$, which demands both a near-maximum

Bell violation and a large number of samples $n$. Furthermore, there are recent no-go results [38] which rule out sample efficient and composable state certification when the desired certification is “exact”, i.e., the target state is certified rather than tolerating small deviations from it. Thus, understanding what is possible for composable multiple copy DI state certification is an appealing direction.

In addition, it would be useful to relax the assumption of independent state preparation in each round. Removing this assumption and allowing for general memory effects would lead to a more general security proof. As discussed in [7], the task of certifying one copy can be achieved under an arbitrarily correlated source (see also [64, 65] for a device dependent approach), and such techniques may provide a path to establishing similar results in our composable framework. However, extending the DISC framework of Ref. [7] to multiple copies in the fully non-i.i.d. setting remains an open question. Due to the more demanding requirement of composability, we expect this will be at least as challenging to establish in our case. Moreover, there are potential limitations when considering a fully general measurement process. As discussed in Ref. [11, Section 2.2.1], the ability to “not measure” a quantum system and hold it in memory necessitates some separation between the state and measurement devices.

Our result on the LOCC extractability for the singlet state may also be of independent interest. This quantity serves as the natural DI counterpart to the well-known singlet fraction [66], extending its relevance to the DI setting. This raises open questions regarding its potential applications in other areas of entanglement theory, as well as in the development of new DI protocols. Additionally, our results provide another avenue for exploring the relationship between nonlocality and entanglement [37], which remains a fundamental topic of investigation.

Finally, it is also interesting to consider a weaker certification criterion— namely, certifying the presence of *any* pure entangled state rather than a specific one. Such a certification could have significant cryptographic applications, as it has been demonstrated that randomness and cryptographic keys can be extracted in a fully device-independent manner from non-maximally entangled, yet still entangled, states [60, 67].

ACKNOWLEDGMENTS

The authors are grateful to Peter Brown, Roger Colbeck and Ivan Šupić for insightful discussions. We also thank Cameron Foreman, Ashutosh Rai, Olgierd Żurek, Mirjam Weilenmann and anonymous referees for their valuable feedback on earlier versions of this work. RB and JB are supported by the National Research Foundation of Korea (Grant No. NRF-2021R1A2C2006309, NRF-2022M1A3C2069728) and the Institute for Information & Communication Technology Promotion (IITP)

<footnote n="7">⁷ Here we have omitted the fact that both the DISC protocol and $\mathcal{P}$ may abort for ease of discussion.</footnote>
(RS-2023-00229524, RS-2025-02304540). LW acknowl-
edges funding support from the Engineering and Phys-
ical Sciences Research Council (EPSRC Grant No.
EP/SO23607/1) and the European Union's Horizon Eu-
rope research and innovation programme under the

project “Quantum Secure Networks Partnership” (QSNP,
grant agreement No. 101114043). Preliminary in-
vestigations for this work were supported by the EP-
SRC via the Quantum Communications Hub (Grant No.
EP/T001011/1) during RB’s time at the University of
York.

[1] A. K. Ekert, “Quantum cryptography based on Bell’s theorem,” Physical Review Letters 67, 661–663 (1991).

[2] A. Acin, N. Brunner, N. Gisin, S. Massar, S. Pironio, and V. Scarani, “Device-independent security of quantum cryptography against collective attacks,” Physical Review Letters 98, 230501 (2007).

[3] R. Colbeck, *Quantum and Relativistic Protocols For Secure Multi-Party Computation*, Ph.D. thesis, University of Cambridge (2007), also available as arXiv:0911.3814.

[4] 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).

[5] J. Barrett, N. Linden, S. Massar, S. Pironio, S. Popescu, and D. Roberts, “Nonlocal correlations as an information-theoretic resource,” Phys. Rev. A 71, 022101 (2005).

[6] J.-D. Bancal, K. Redeker, P. Sekatski, W. Rosenfeld, and N. Sangouard, “Self-testing with finite statistics enabling the certification of a quantum network link,” Quantum 5, 401 (2021).

[7] A. Gočanin, I. Šupić, and B. Dakić, “Sample-efficient device-independent quantum state verification and certification,” PRX Quantum 3, 010317 (2022).

[8] D. Mayers and A. Yao, “Quantum cryptography with imperfect apparatus,” in *Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS-98)* (IEEE Computer Society, Los Alamitos, CA, USA, 1998) pp. 503–509.

[9] D. Mayers and A. Yao, “Self testing quantum apparatus,” (2004), arXiv:quant-ph/0307205 [quant-ph].

[10] J. Kaniewski, “Analytic and nearly optimal self-testing bounds for the Clauser-Horne-Shimony-Holt and Mermin inequalities,” Phys. Rev. Lett. 117, 070402 (2016).

[11] R. Arnon-Friedman and J.-D. Bancal, “Device-independent certification of one-shot distillable entanglement,” New Journal of Physics 21, 033010 (2019).

[12] A. Philip and M. M. Wilde, “Device-independent certification of multipartite distillable entanglement,” Phys. Rev. A 111, 012436 (2025).

[13] L. dos Santos Martins, N. Laurent-Puig, I. Šupić, D. Markham, and E. Diamanti, “Experimental sample-efficient and device-independent GHZ state certification,” (2024), arXiv:2407.13529 [quant-ph].

[14] S. Storz, A. Kulikov, J. D. Schär, V. Barizien, X. Valcarce, F. Berterottière, N. Sangouard, J.-D. Bancal, and A. Wallraff, “Complete self-testing of a system of remote superconducting qubits,” (2024), arXiv:2408.01299 [quant-ph].

[15] M. M. E. Schmid, M. Antesberger, H. Cao, W. hao Zhang, B. Dakič, L. A. Rozema, and P. Walther, “Experimental device-independent certification of GHZ states,”

in *Quantum 2.0 Conference and Exhibition* (Optica Publishing Group, 2024) p. QM2C.7.

[16] J. Barrett, L. Hardy, and A. Kent, “No signalling and quantum key distribution,” Physical Review Letters 95, 010503 (2005).

[17] S. Pironio, A. Acin, N. Brunner, N. Gisin, S. Massar, and V. Scarani, “Device-independent quantum key distribution secure against collective attacks,” New Journal of Physics 11, 045021 (2009).

[18] J. Barrett, R. Colbeck, and A. Kent, “Unconditionally secure device-independent quantum key distribution with only two devices,” Phys. Rev. A 86, 062326 (2012).

[19] U. Vazirani and T. Vidick, “Fully device-independent quantum key distribution,” Phys. Rev. Lett. 113, 140501 (2014).

[20] R. Arnon-Friedman, F. Dupuis, O. Fawzi, R. Renner, and T. Vidick, “Practical device-independent quantum cryptography via entropy accumulation,” Nature communications 9, 459 (2018).

[21] R. Colbeck and A. Kent, “Private randomness expansion with untrusted devices,” Journal of Physics A 44, 095305 (2011).

[22] C. A. Miller and Y. Shi, “Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices,” in *Proceedings of the 46th Annual ACM Symposium on Theory of Computing*, STOC ’14 (ACM, New York, NY, USA, 2014) pp. 417–426.

[23] C. A. Miller and Y. Shi, “Universal security for randomness expansion from the spot-checking protocol,” Siam Journal of Computing 46, 1304–1335 (2017).

[24] R. Colbeck and R. Renner, “Free randomness can be amplified,” Nature Physics 8, 450–453 (2012).

[25] R. Renner, *Security of Quantum Key Distribution*, Ph.D. thesis, Swiss Federal Institute of Technology, Zurich (2005), also available as quant-ph/0512258.

[26] C. Portmann and R. Renner, “Cryptographic security of quantum key distribution,” (2014), arXiv:1409.3525 [quant-ph].

[27] I. Šupić and J. Bowles, “Self-testing of quantum systems: a review,” Quantum 4, 337 (2020).

[28] T. Coopmans, J. Kaniewski, and C. Schaffner, “Robust self-testing of two-qubit states,” Phys. Rev. A 99, 052123 (2019).

[29] E. Y.-Z. Tan, R. Schwonnek, K. T. Goh, I. W. Primaatmaja, and C. C.-W. Lim, “Computing secure key rates for quantum cryptography with untrusted devices,” npj Quantum Information 7, 158 (2021).

[30] R. Bhavsar, S. Ragy, and R. Colbeck, “Improved device-independent randomness expansion rates using two sided randomness,” New Journal of Physics 25, 093035 (2023).

[31] P. Brown, H. Fawzi, and O. Fawzi, “Device-independent lower bounds on the conditional von Neumann entropy,” Quantum 8, 1445 (2024).
[32] F. Dupuis, O. Fawzi, and R. Renner, "Entropy accumulation," Communications in Mathematical Physics **379**, 867-913 (2020).

[33] F. Dupuis and O. Fawzi, "Entropy accumulation with improved second-order term," IEEE Transactions on Information Theory **65**, 7596-7612 (2019).

[34] T. Metger, O. Fawzi, D. Sutter, and R. Renner, "Generalised entropy accumulation," Communications in Mathematical Physics **405**, 261 (2024).

[35] Y. Zhang, H. Fu, and E. Knill, "Efficient randomness certification by quantum probability estimation," Phys. Rev. Res. **2**, 013016 (2020).

[36] C. Foreman, S. Wright, A. Edgington, M. Berta, and F. J. Curchod, "Practical randomness amplification and privatisation with implementations on quantum computers," Quantum **7**, 969 (2023).

[37] Y. Zhu, X. Zhang, and X. Ma, "Interplay among entanglement, measurement incompatibility, and nonlocality," Quantum Science and Technology **9**, 045008 (2024).

[38] F. Wiesner, Z. Chaoui, D. Kessler, A. Pappa, and M. Karvonen, "Why quantum state verification cannot be both efficient and secure: a categorical approach," (2024), arXiv:2411.04767 [quant-ph].

[39] A. Rai, M. Pivoluska, S. Sasmal, M. Banik, S. Ghosh, and M. Plesch, "Self-testing quantum states via nonmaximal violation in Hardy's test of nonlocality," Phys. Rev. A **105**, 052227 (2022).

[40] J. S. Bell, "On the Einstein-Podolsky-Rosen paradox," in *Speakable and unspeakable in quantum mechanics* (Cambridge University Press, 1987) Chap. 2.

[41] 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).

[42] N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, and S. Wehner, "Bell nonlocality," Reviews of Modern Physics **86**, 419-478 (2014).

[43] Y. Wang, X. Wu, and V. Scarani, "All the self-testings of the singlet for two binary measurements," New Journal of Physics **18**, 025021 (2016).

[44] T. P. Le, C. Meroni, B. Sturmfels, R. F. Werner, and T. Ziegler, "Quantum Correlations in the Minimal Scenario," Quantum **7**, 947 (2023).

[45] V. Barizien, P. Sekatski, and J.-D. Bancal, "Custom Bell inequalities from formal sums of squares," Quantum **8**, 1333 (2024).

[46] L. Wooltorton, P. Brown, and R. Colbeck, "Device-independent quantum key distribution with arbitrarily small nonlocality," Phys. Rev. Lett. **132**, 210802 (2024).

[47] M. Ben-Or and D. Mayers, "General security definition and composability for quantum & classical protocols," e-print quant-ph/0409062 (2004).

[48] M. Ben-Or, M. Horodecki, D. W. Leung, D. Mayers, and J. Oppenheim, "The universal composable security of quantum key distribution," in *Theory of Cryptography*, edited by J. Kilian (Springer Berlin Heidelberg, Berlin, Heidelberg, 2005) pp. 386-406.

[49] D. Unruh, "Simulatable security for quantum protocols," e-print quant-ph/0409125 (2004).

[50] R. Renner and R. König, "Universally composable privacy amplification against quantum adversaries," in *Theory of Cryptography Conference* (Springer, 2005) pp. 407-425.

[51] S. Pirandola, U. L. Andersen, L. Banchi, M. Berta, D. Bunandar, R. Colbeck, D. Englund, T. Gehring,

C. Lupo, C. Ottaviani, J. L. Pereira, M. Razavi, J. S. Shaari, M. Tomamichel, V. C. Usenko, G. Vallone, P. Villoresi, and P. Wallden, "Advances in quantum cryptography," Adv. Opt. Photon. **12**, 1012-1236 (2020).

[52] I. W. Primaatmaja, K. T. Goh, E. Y.-Z. Tan, J. T.-F. Khoo, S. Ghorai, and C. C.-W. Lim, "Security of device-independent quantum key distribution protocols: a review," Quantum **7**, 932 (2023).

[53] M. M. Wilde, *Quantum Information Theory* (Cambridge University Press, 2013).

[54] C.-E. Bardyn, T. C. H. Liew, S. Massar, M. McKague, and V. Scarani, "Device-independent state estimation based on Bell's inequalities," Phys. Rev. A **80**, 062327 (2009).

[55] J.-D. Bancal, M. Navascués, V. Scarani, T. Vértesi, and T. H. Yang, "Physical characterization of quantum devices from nonlocal correlations," Phys. Rev. A **91**, 022115 (2015).

[56] X. Valcarce, P. Sekatski, D. Orsucci, E. Oudot, J.-D. Bancal, and N. Sangouard, "What is the minimum CHSH score certifying that a state resembles the singlet?" Quantum **4**, 246 (2020).

[57] C. Jordan, "Essai sur la géométrie à n dimensions," Bulletin de la S. M. F. **3**, 103-174 (1875).

[58] R. Bhavsar, *Improvements on Device Independent and Semi-Device Independent Protocols of Randomness Expansion*, Ph.D. thesis, University of York (2023), also available as arXiv:2311.13528.

[59] S. Boyd and L. Vandenberghe, *Convex Optimization* (Cambridge University Press, Cambridge, UK, 2004).

[60] A. Acín, S. Massar, and S. Pironio, "Randomness versus nonlocality and entanglement," Physical Review Letters **108**, 100402 (2012).

[61] C. Bamps and S. 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 (2015).

[62] P. Sekatski, J.-D. Bancal, S. Wagner, and N. Sangouard, "Certifying the building blocks of quantum computers from Bell's theorem," Phys. Rev. Lett. **121**, 180505 (2018).

[63] J. Barrett, R. Colbeck, and A. Kent, "Memory attacks on device-independent quantum cryptography," Phys. Rev. Lett. **110**, 010503 (2013).

[64] H. Zhu and M. Hayashi, "General framework for verifying pure quantum states in the adversarial scenario," Phys. Rev. A **100**, 062335 (2019).

[65] H. Zhu and M. Hayashi, "Efficient verification of pure quantum states in the adversarial scenario," Phys. Rev. Lett. **123**, 260504 (2019).

[66] M. Horodecki, P. Horodecki, and R. Horodecki, "General teleportation channel, singlet fraction, and quasidistillation," Phys. Rev. A **60**, 1888-1898 (1999).

[67] E. Woodhead, A. Acín, and S. Pironio, "Device-independent quantum key distribution with asymmetric CHSH inequalities," Quantum **5**, 443 (2021).

[68] C. Fuchs and J. van de Graaf, "Cryptographic distinguishability measures for quantum-mechanical states," *IEEE Transactions on Information Theory* **45**, 1216-1227 (1999).

[69] L. Contento, A. Ern, and R. Vermiglio, "A linear-time approximate convex envelope algorithm using the double legendre-fenchel transform with application to phase separation," *Computational Optimization and Applications*
60, 231–261 (2015).

[70] A. M. Zubkov and A. A. Serov, “A complete proof of universal inequalities for the distribution function of the binomial law,” *Theory of Probability & Its Applications* **57**, 539–544 (2013).

[71] S. Simons, “Minimax theorems and their proofs,” in *Minimax and Applications*, edited by D.-Z. Du and P. M. Pardalos (Springer US, Boston, MA, 1995) pp. 1–23.

[72] S. Boyd and L. Vandenberghe, *Convex Optimization* (Cambridge University Press, 2004).

[73] F. Baccari, R. Augusiak, I. Šupić, J. Tura, and A. Acín, “Scalable Bell inequalities for qubit graph states and robust self-testing,” *Phys. Rev. Lett.* **124**, 020402 (2020).

[74] G. Murta and F. Baccari, “Self-testing with dishonest parties and device-independent entanglement certification in quantum communication networks,” *Phys. Rev. Lett.* **131**, 140201 (2023).

[75] T. Sharma, R. Bhavsar, J. Ramakrishnan, P. Chandra-vanshi, S. Prabhakar, A. Biswas, and R. P. Singh, “Enhancing key rates of QKD protocol by coincidence detection,” *Adv Quantum Technol.*, **24**, 00685 (2025).

## Appendix A: Overview of assumptions for DISC protocols

In this section, we outline all assumptions made in our work.

1. Quantum theory is correct and complete.

2. No information can leak in or out of the laboratory once the protocol has begun.

3. The untrusted source generates a sequence of independent states.

4. The user has access to a secure quantum memory, and a trusted means to process classical information.

5. The user has access to a trusted source of perfect, private randomness. In particular, this implies the random variables $X_i$, $Y_i$, and $T$ are uniformly distributed to the user, and to any potential adversary present in the current protocol, or in any future protocol for which the current protocol serves as an input.

6. All initial states from the source are received in the laboratory before the random number $T$ is generated.

It is important to emphasize that, unlike standard device-independent protocols for quantum key distribution and randomness generation, this protocol requires a clear separation between states (generated solely by the source) and measurements (performed by the measurement device), rather than treating them as a single uncharacterized “black-box”. In particular, all entanglement produced during or before the protocol is attributed to the source only. This distinction is critical, since treating states and measurements as a single box would render the protocol trivially insecure. For example, an eavesdropper could prepare a maximally entangled state $|\phi^+\rangle$ in each round, and instruct the devices to measure all states projectively, according to the optimal measurement strategy for some Bell inequality. This would destroy the entanglement in all the states, regardless of whether a particular round was intended to serve in the Bell test or not. Under this attack, the protocol will not abort, however, the output state stored for the user is separable. This violates the security requirement, namely, that the output state resembles $|\phi^+\rangle$ when the protocol does not abort.

In contrast, our protocol eliminates this vulnerability by randomly choosing the output state before any interaction with the measurement device. This state is then held in a trusted quantum memory while the remaining states are measured, ensuring it is shielded from any external influence.

We now discuss Assumption 6. It is essential to have access to a private source of randomness during the protocol in order to choose the stored state and perform the Bell test. In particular, it suffices to assume that this randomness is not available to the adversary before the protocol commences. Otherwise, the adversary could prepare the sequence of states $\bigotimes_{i=1}^n \rho_i$ with $\rho_i = \phi^+$ whenever $i \neq t$ and $\rho_t = \sigma$, where $\sigma$ is some separable state. If the measurement devices are instructed to always perform the optimal measurements for the desired Bell inequality, this would essentially amount to the abort-based attack discussed in the main text, except that it would now succeed with probability one. Assumption 6 excludes this attack, and is indispensable for the protocol to remain secure.

We stress, however, that it is permissible for the adversary to learn the value of the random variable $T$ once the protocol has already commenced. At that stage, the adversary has no ability to pre-program the source and measurement devices in a coordinated manner to break security. Finally, we note that this assumption could be entirely dropped if the random numbers were generated by a randomness-generation protocol that itself is composable.<fnref n="8" />

<footnote n="8">⁸ We thank the authors of [38] for pointing this out to us.</footnote>
Appendix B: Protocols for DISC

We now present the DISC protocols discussed in the main text. Specifically, in Section IV we considered two variants of the measurement setup. The first consists of a parallel scenario, in which each state $\rho_i$ is measured in isolation using a separate measuring device. The second is sequential, where the measurement of $\rho_i$ precedes that of $\rho_{i+1}$, and auxiliary information about the measurement in round $i$ can be used in round $i+1$. This setup consists of a single measurement device. Throughout, we use the notation $M_i$ to denote the measurement channel associated to the index $i$, which include the settings $X_iY_i$ as an input (see Fig. 8). This is not to be confused with the channels $N_i$ described in the main text, in which $X_iY_i$ are included as outputs. We consider both the task of certifying the target state exactly, and a state $\varepsilon$-close to the target state.

1. Parallel setup

For the parallel setup, we remark that instead of requiring $n-1$ different non-communicating measurement devices, the protocol can be reinterpreted as involving a single measurement device without memory. This reformulation aligns the protocol with sequential protocols, where a single memoryless device processes the measurements one at a time. Nonetheless, no assumptions are made regarding the inner workings of the measurement devices. Furthermore, no assumptions are made about the generated states: the channels $M_i$ can be pre-programmed in accordance with the state $\rho_i$, which itself can be pre-set by a potential adversary for the protocol.

With this in mind we present Protocol 1, which consists of certifying the maximally entangled state $|\phi^+\rangle$, following the action of an optimal extraction channel, using generalized Bell functionals of the form

$$ \omega = \sum_{x,y \in \{0,1\}} \gamma_{x,y} \langle A_x B_y \rangle. \qquad (B1) $$

The maximum and minimum values of $\omega$ for quantum behaviors are denoted $\eta_{\min}^Q$ and $\eta_{\max}^Q$, respectively. The maximum and minimum values for local behaviors are denoted $\eta_{\min}^L$ and $\eta_{\max}^L$, respectively. We label the sequence of states produced by the untrusted source $\{\rho_i \in S(H_{Q_i}^A \otimes H_{Q_i}^B)\}_{i=1}^n$, and for each $\rho_i$ we associate a channel $\Lambda_i \in C$ which satisfies $F(\Lambda_i(\rho_i), \phi^+) = \sup_{\Lambda \in C} F(\Lambda(\rho_i), \phi^+)$. Each measurement device is labeled $M_i$, consisting of isolated sub-devices $M_i^A$ and $M_i^B$

**Remark 2.** Note that we have implicitly assumed the supremum over channels in $C$ is achievable. If this is not the case, we define $\Lambda_i$ as any channel which achieves a fidelity arbitrarily close to $\sup_{\Lambda \in C} F(\Lambda(\rho_i), \phi^+)$.

**Protocol 1 (Certification of the $\phi^+$ state). Parameters:**

$n \in \mathbb{N}^+$ – number of rounds

$p_T : \{1, ..., n\} \to [0, 1]$ – probability distribution of the random variable $T$ (taken to be uniform here)

$\omega_i \in [\eta_{\min}^Q, \eta_{\max}^Q]$ – expected value of the Bell functional (B1)

$\kappa > 0$ – completeness parameter.

1. Generate a random variable $T$ according to the distribution $p_T$. If $T = t$, then store the state $\rho_t$ for the remainder of the protocol.

2. Generate the random bit string $\mathbf{X} = (X_1, X_2, ..., X_{t-1}, X_{t+1}, ..., X_n)$ uniformly. Input each bit $X_i$ to the device $M_i^A$, producing the output bit $A_i$. Similarly, generate the random bit string $\mathbf{Y} = (Y_1, Y_2, ..., Y_{t-1}, Y_{t+1}, ..., Y_n)$ uniformly, and input $Y_i$ to the device $M_i^B$, producing the output $B_i$.

3. For $i \in \{1, ..., n\} \setminus t$, set $W_i = \tilde{\gamma}_{X_i, Y_i}$ if $A_i \oplus B_i = X_i \cdot Y_i$, and $W_i = -\tilde{\gamma}_{X_i, Y_i}$ otherwise, where $\tilde{\gamma}_{x,y} = (-1)^{xy}\gamma_{x,y}$.

4. Compute the empirical value:

$$ \omega_{\text{exp}} := \frac{4}{n} \sum_{i=1: i \neq t}^{n} W_i \qquad (B2) $$
and abort the protocol if $\omega_{\text{exp}} \le \omega_{\#} - \kappa$.

5. If the protocol does not abort, apply the optimal channel $\Lambda_t \in \mathcal{C}$ to the state $\rho_t$, which transforms $\rho_t$ to a state $\Lambda_t(\rho_t)$. Output $\Lambda_t(\rho_t)$.

To see how the empirical value relates the Bell functional (B1), consider the variable $W$ for a single round (omitting the index $i$). Then

$$ \mathbb{E}[W] = \sum_{x,y \in \{0,1\}} \left( \mathbb{P}[W = \tilde{\gamma}_{x,y}] \tilde{\gamma}_{x,y} - \mathbb{P}[W = -\tilde{\gamma}_{x,y}] \tilde{\gamma}_{x,y} \right). \qquad (B3) $$

Note that

$$ \begin{aligned} \mathbb{P}[W = \tilde{\gamma}_{x,y}] &= p(x, y) \sum_{a,b: a \oplus b = xy} p(a, b|x, y) \\ &= \frac{1}{8} \sum_{a,b \in \{0,1\}} p(a, b|x, y) (1 + (-1)^{a+b+xy}) \\ &= \frac{1}{8} \left( 1 + (-1)^{xy} \sum_{a,b \in \{0,1\}} (-1)^{a+b} p(a, b|x, y) \right) \\ &= \frac{1}{8} (1 + (-1)^{xy} \langle A_x B_y \rangle), \end{aligned} \qquad (B4) $$

where we used the fact that $p(x, y) = 1/4$. We also have

$$ \mathbb{P}[W = -\tilde{\gamma}_{x,y}] = p(x, y) \left( 1 - \sum_{a,b: a \oplus b = xy} p(a, b|x, y) \right) = \frac{1}{4} - \frac{1}{8} (1 + (-1)^{xy} \langle A_x B_y \rangle). \qquad (B5) $$

As a result,

$$ \mathbb{E}[W] = \frac{1}{4} \sum_{x,y \in \{0,1\}} \tilde{\gamma}_{x,y} (-1)^{xy} \langle A_x B_y \rangle = \frac{1}{4} \sum_{x,y \in \{0,1\}} \gamma_{x,y} \langle A_x B_y \rangle = \frac{1}{4} \omega. \qquad (B6) $$

A graphical description of Protocol 1 can be found in Figure 8.

Protocol 1 certifies the maximally entangled state $|\phi^+\rangle$. However, in practical scenarios, one may wish to certify a quantum state that is $\varepsilon$-close to $\phi^+$, where the closeness is measured using the trace norm. That is, if the protocol does not abort, then the state held in memory, $\Lambda_t(\rho_t)$, satisfies $||\Lambda_t(\rho_t) - \phi^+||_1 \le \varepsilon$. The next protocol we present extends Protocol 1 to account for deviations from the idealized scenario of perfect state preparation. Whilst the steps are the same as Protocol 1, the ideal protocol differs, resulting in a different security proof (see Section C).

**Protocol 2 (Certification of a state $\varepsilon$-close to the $\phi^+$ state). Parameters:**

$n \in \mathbb{N}^+$ – number of rounds

$p_T : \{1, ..., n\} \to [0, 1]$ – probability distribution of the random variable $T$ (taken to be uniform here)

$\omega_{\#} \in [\eta_{\min}^{Q}, \eta_{\max}^{Q}]$ – expected value of the Bell functional (B1)

$\varepsilon \ge 0$ – closeness parameter

$\kappa > 0$ – completeness parameter.

Follow the same steps as in Protocol 1.

Note that in the above protocols, the final step which involves applying the optimal channel $\Lambda_t$ to $\rho_t$ is somewhat fictitious. Indeed, knowing the channels $\Lambda_i$ implies solving the optimization $\sup_{\Lambda \in \mathcal{C}} F(\Lambda(\rho_i), \phi^+)$. This in turn requires knowledge of $\rho_i$, which is inaccessible by definition, since $\rho_i$ is produced by the untrusted source we wish to certify. Moreover, even if the channels $\Lambda_i$ were known, physically implementing them in the lab would go against the device-independent methodology, in which we only have access to observed statistics rather than trusted quantum operations.
<figure><img src="image_10.png" /><figcaption>FIG. 8: (a) Description of Protocol 1 in terms of its individual components. The bold arrows lines indicate quantum systems and the thin arrows represent classical variables. The bold line indicates that no communication is allowed between the components which it separates. (b) Description of the individual measurement channel $M_i$ in terms of devices that perform the Bell test.</figcaption></figure>

In Protocol 1 and Protocol 2 however, we are only concerned with the existence of such channels. In this way, when the protocol does not abort, we are guaranteed the existence of an extraction procedure from $C$ which brings the stored state close to the target state.

To further address this point, we include an additional variant which does not include step 5. Specifically, the protocol outputs $\rho_t$ directly when it does not abort. We then show in the security proof that $\rho_t$ is equivalent to the target state in a well defined sense.

**Protocol 3 (Certification of a state $\epsilon$-close to the $\phi^+$ state). Parameters:**

$n \in \mathbb{N}^+$ – number of rounds

$p_T : \{1, ..., n\} \to [0, 1]$ – probability distribution of the random variable $T$ (taken to be uniform here)

$\omega_i \in [\eta_{\min}^Q, \eta_{\max}^Q]$ – expected value of the Bell functional (B1)

$\epsilon \ge 0$ – closeness parameter

$\kappa > 0$ – completeness parameter.

Follow steps 1 to 4 in Protocol 1.

5. If the protocol does not abort, output $\rho_t$.

## 2. Sequential setup

As discussed above, Protocols 1 to 3 assume that all measurements are independent, which may be unrealistic for real devices. To avoid this assumption, one must use $n-1$ isolated devices, which is wasteful and difficult to implement in practice. Alternatively, the aforementioned protocols are also equivalent to a protocol where a single memoryless measurement device is used. There is therefore strong motivation to lift this independence assumption in the security proof. In the following, we detail Protocol 4 which achieves this using the CHSH Bell score:

$$p^{\text{win}} = \frac{1}{4} \sum_{a,b,x,y \in \{0,1\}} w_{a,b,x,y} p(a, b|x, y), \qquad (B7)$$

where $w_{a,b,x,y} = 1$ if $a \oplus b = x \cdot y$ and zero otherwise.
**Remark 3.** Up until this point, we have exclusively referred to the *value* of a Bell expression, denoted by $\omega = \langle B \rangle \in [\eta_{\min}^Q, \eta_{\min}^Q]$. In particular, this need not correspond to the winning probability of a nonlocal game (i.e., we do not require $\omega \in [0, 1]$). When discussing sequential protocols, we will make use of the nonlocal game formulation of the CHSH inequality $B_{CHSH}$. In this case, we will refer to the CHSH score, denoted $p^{win} \in [0, 1]$, which denotes the winning probability of the CHSH game. Here, the random variables $W_i$ take values in $\{0, 1\}$ indicating whether round $i$ was lost ($W_i = 0$) or won ($W_i = 1$).

As in the parallel setup, the source emits a sequence $\{\rho_i \in S(H_{Q_i}^A \otimes H_{Q_i}^B)\}_{i=1}^n$, each associated to an optimal channel $\Lambda_i \in \mathcal{C}$. Instead of $n-1$ devices, we now consider a single measurement device $M$.

**Protocol 4 (Certification of a state $\varepsilon$-close to the $\phi^+$ state). Parameters:**

$n \in \mathbb{N}^+$ – number of rounds

$p_T : \{1, ..., n\} \rightarrow [0, 1] -$ probability distribution of the random variable $T$ (taken to be uniform here)

$p_{\#}^{win} \in [0, 1]$ – expected CHSH score

$\varepsilon \ge 0$ – closeness parameter

$\kappa > 0$ – completeness parameter.

1. Generate a random variable $T$ according to the distribution $p_T$. If $T = t$, then store the state $\rho_t$. Set $i = 1$.

2. If $i = t - 1$, increase $i$ by 2, otherwise, increase $i$ by 1.

3. Generate the random bit $X_i$ uniformly, and input to $M$ to obtain the output bit $A_i$. Likewise generate $Y_i$ uniformly and input $Y_i$ to $M$, giving the output $B_i$.

4. Set $W_i = 1$ if $A_i \oplus B_i = X_i Y_i$ and $W_i = 0$ otherwise.

5. Return to Step 2 unless $i = n$ or $i = n - 1$ and $t = n$.

6. Calculate the number of rounds in which $W_i = 0$ occurred, and abort the protocol if this is larger than $[(n-1)(1 - p_{\#}^{win} + \kappa)]$.

7. If the protocol does not abort, then apply the optimal LOCC channel $\Lambda_t$ to the state $\rho_t$ that takes $\rho_t$ to a state $\Lambda_t(\rho_t)$. Output $\Lambda_t(\rho_t)$.

A graphical description of Protocol 4 can be found in Figure 9. Similarly to the parallel setup, we also include a variant which omits the final extraction step.

**Protocol 5 (Certification of a state $\varepsilon$-close to the $\phi^+$ state). Parameters:**

$n \in \mathbb{N}^+$ – number of rounds

$p_T : \{1, ..., n\} \rightarrow [0, 1] -$ probability distribution of the random variable $T$ (taken to be uniform here)

$p_{\#}^{win} \in [0, 1]$ – expected CHSH score

$\varepsilon \ge 0$ – closeness parameter

$\kappa > 0$ – completeness parameter.

Follow steps 1 to 6 in Protocol 4.

7. If the protocol does not abort, output $\rho_t$.

## Appendix C: Security proof of Protocols 1 to 3

In this section, we prove the security of the parallel protocols presented in Section B 1. As discussed in the main text, we do so according to a composable definition. This involves specifying an ideal protocol and demonstrating that the real implementation of the protocol cannot be distinguished from the ideal one by any hypothetical distinguisher with a probability higher than a pre-agreed threshold (see [26] for more details).
<figure><img src="image_11.png" /><figcaption>FIG. 9: (a) Description of Protocol 4 in terms of its individual components. The bold arrows indicate quantum systems, while the thin arrows represent classical variables. The measurement channels $\mathcal{M}_i$ are as described in Figure 8 (b). The measurement devices are uncharacterized and may possess memory; however, they measure independently generated states $\rho_i$ one at a time. The gray box, which accepts the input $T$ and $\otimes_i^n \rho_i$, stores the state $\rho_t$ for future use and sends the remaining states to the measurement device in a sequential fashion.</figcaption></figure>

**Remark 4.** Protocols 1 to 5 have been defined with respect to a class of free operations $\mathcal{C}$. As discussed in the main text, we prove security for the class of LOCC operations. However, the proofs can be straightforwardly adapted to any other class, such as local operations, which have been frequently studied in the literature [7, 10]. Provided a lower bound on the LO extractability for the desired Bell inequality is known, this can be directly substituted for the LOCC extractability function used here, for any of the Protocols 1 to 5.

# 1. Security proof of Protocol 1

We begin by mathematically describing the real and ideal implementations of the protocol, followed by a proof of their indistinguishability.

## a. Real protocol

To best describe the real and ideal protocols, we start by examining their classical-quantum (cq) states at key stages. For the real protocol:

1. **Stage 1 (Pre-measurement stage):** The user receives a set of (independently generated) states $\otimes_{i=1}^n \rho_i$ and measurement devices $M_i$ to which the states $\rho_i$ are sent. The variable $T = t$ is sampled to determine which state is kept.

2. **Stage 2 (Post-measurement stage):** For all $i \in \{1, ..., n\} \setminus t$ each device $M_i$ implements the channel $\mathcal{N}_i$ detailed in Section IV (with the input registers $I_i^A, I_i^B$ omitted). The user collects a string of length $n-1$, $\mathbf{w} = (w_1, w_2, ..., w_{t-1}, w_{t+1}, ..., w_n) \in \mathcal{W}^{\times(n-1)}$, where $\mathcal{W} = \{\tilde{\gamma}_{x,y}, -\tilde{\gamma}_{x,y}\}_{x,y \in \{0,1\}}$ consisting of the measurement outcomes of each round, i.e., $\mathbf{w}$ keeps a record of the ordered list of wins that were measured for each of the $n-1$ rounds. This list is stored in a classical register $\mathbf{W}$. The cq-state of the protocol at this stage then becomes:

$$ \rho = \sum_{t=1}^{n} p_T(t) \sum_{\mathbf{w} \in \mathcal{W}^{\times(n-1)}} p(\mathbf{w}|t) |\mathbf{w}\rangle\langle\mathbf{w}|\mathbf{w} \otimes |t\rangle\langle t|_T \otimes \rho_t, $$

where $p(\mathbf{w}|t)$ is the conditional probability of generating the string $\mathbf{w}$ given that $T = t$ is observed during the protocol, and $p_T(t)$ is the probability that $T = t$.
3. **Stage 3 (Parameter estimation stage):** After collecting statistics, the protocol either aborts or proceeds to the final stage. Its state takes the form

$$ \rho = \left( \sum_{t=1}^{n} p_T(t) \sum_{\mathbf{w} \in \Omega} p(\mathbf{w}|t) |\mathbf{w}\rangle\langle\mathbf{w}|\mathbf{w} \otimes |t\rangle\langle t|_T \otimes \rho_t \otimes |\Omega\rangle\langle\Omega| \right) + (1 - p_{\Omega}) |\perp\rangle\langle\perp|, $$

where $\Omega \subset W^{\times(n-1)}$ is the set of observed strings $\mathbf{w}$ which do not cause the protocol to abort, $p_{\Omega} = \sum_{t=1}^{n} \sum_{\mathbf{w} \in \Omega} p(\mathbf{w}|t)p_T(t)$ is the probability of this event and $|\Omega\rangle$ and $|\perp\rangle$ are states indicating whether protocol passes or aborts, respectively.

4. **Stage 4 (Final output state):** Conditioned on not aborting, the user applies the optimal LOCC channel $\Lambda_t$ to the stored state $\rho_t$ to obtain the state $\Lambda_t(\rho_t)$, which may be used for future protocols. The final cq-state of the protocol then takes the form

$$ \rho_{\text{real}} = \sum_{t=1}^{n} p_T(t) \sum_{\mathbf{w} \in \Omega} p(\mathbf{w}|t) |\mathbf{w}\rangle\langle\mathbf{w}|\mathbf{w} \otimes |t\rangle\langle t|_T \otimes \Lambda_t(\rho_t) \otimes |\Omega\rangle\langle\Omega| + (1 - p_{\Omega}) |\perp\rangle\langle\perp|, $$

### b. Ideal protocol

The ideal protocol differs from the real protocol only in stage 3 and 4:

* **Stage 1 and 2:** The ideal protocol runs the real protocol during stage 1 and 2.

* **Stage 3:** The ideal protocol aborts if the real protocol aborts. If the ideal protocol does not abort, then it replaces the stored state $\rho_t$ with the state $\phi^+ \otimes \sigma_{\text{aux}}$, where $\sigma_{\text{aux}} \in S(H_{\text{aux}})$ for some Hilbert space $H_{\text{aux}}$ satisfying $C^2 \otimes C^2 \otimes H_{\text{aux}} \cong H_{Q_t^A} \otimes H_{Q_t^B}$. The cq-state of the ideal protocol at this stage is:

$$ \rho = \left( \sum_{t=1}^{n} p_T(t) \sum_{\mathbf{w} \in \Omega} p(\mathbf{w}|t) |\mathbf{w}\rangle\langle\mathbf{w}|\mathbf{w} \otimes |t\rangle\langle t|_T \otimes \phi^+ \otimes \sigma_{\text{aux}} \otimes |\Omega\rangle\langle\Omega| \right) + (1 - p_{\Omega}) |\perp\rangle\langle\perp|, $$

* **Stage 4:** The ideal protocol throws away the contents of the auxiliary register and outputs $\phi^+$. This will give the final state of the ideal protocol

$$ \rho_{\text{ideal}} = \sum_{t=1}^{n} \sum_{\mathbf{w} \in \Omega} p(\mathbf{w}|t)p_T(t) |\mathbf{w}\rangle\langle\mathbf{w}|\mathbf{w} \otimes |t\rangle\langle t|_T \otimes \phi^+ \otimes |\Omega\rangle\langle\Omega| + (1 - p_{\Omega}) |\perp\rangle\langle\perp|, $$

### c. Soundness

Having defined the real and the ideal protocol, recall the definition of soundness discussed in the main text.

**Definition 5 (Soundness).** A DISC protocol is called $\epsilon_s$-sound if

$$ \frac{1}{2} \| \rho_{\text{real}} - \rho_{\text{ideal}} \|_1 \le \epsilon_s \qquad (C1) $$

where $\rho_{\text{real}}$ and $\rho_{\text{ideal}}$ are the cq-states obtained after a real and ideal implementation of the protocol and $\|\cdot\|_1$ denotes the trace norm.

To prove the soundness of Protocol 1, we require Hoeffding's theorem for independent random variables.

**Theorem 3 (Hoeffding's inequality).** Let $X_1, X_2, \dots, X_n$ be independent random variables such that $a_i \le X_i \le b_i$ for $1 \le i \le n$. Then, for any $r > 0$,

$$ \begin{aligned} \mathbb{P} \left( \left| \sum_{i=1}^{n} (X_i - \mathbb{E}[X_i]) \right| \ge r \right) &\le \exp \left( - \frac{2r^2}{\sum_{i=1}^{n} (b_i - a_i)^2} \right), \quad \text{and} \\ \mathbb{P} \left( \left| \sum_{i=1}^{n} (X_i - \mathbb{E}[X_i]) \right| \le r \right) &\le 2 \exp \left( - \frac{2r^2}{\sum_{i=1}^{n} (b_i - a_i)^2} \right). \end{aligned} \qquad (C2) $$
**Lemma 1.** Protocol 1 is $\epsilon_s$-sound, where

$$ 
\begin{aligned}
\epsilon_s &= \inf_{\delta>0} \max\{a(\delta), b_1(\delta)\}, \\
a(\delta) &= \exp\left(-\frac{(n-1)}{\gamma^*} \delta^2\right), \\
\gamma^* &= \max\{|\gamma_{x,y}|\}_{x,y \in \{0,1\}}, \\
b_1(\delta) &= \sqrt{1 - f\left(\frac{n-1}{n}(\omega_{\#} - \kappa - \delta) + \frac{\eta_{\min}^Q}{n}\right)}.
\end{aligned} 
\quad (C3) 
$$

Here, $f(\omega)$ is any non-decreasing convex function that lower bounds extractability $\Xi_B(\omega)$.

*Proof.* Recall the initial state is denoted by $\rho_0 = \bigotimes_{i=1}^N \rho_i$, and $\mathcal{M}_i$ are the measurement channels (See Figure 8). We further define $\mu_i := \text{tr}(B_i\rho_i)$ as the expected value of the Bell functional from Equation (B1),

$$ B_i = \sum_{x,y \in \{0,1\}} \gamma_{x,y} (A_x^i \otimes B_y^i), \quad (C4) $$

where $A_x^i$ and $B_y^i$ are the observables on $Q_i^A$ and $Q_i^B$ induced by $\mathcal{M}_i$, respectively.

We begin by recalling the probability that the protocol does not abort, denoted by $p_\Omega$, where $\Omega$ is the set of strings $\mathbf{w}$ for which the observed value $\omega$ is at least $\omega_\#$,

$$ p_{\Omega} = \sum_{t=1}^{n} p_{T}(t)p(\Omega|t), \quad (C5) $$

where $p(\Omega|t) = \sum_{\mathbf{w} \in \Omega} p(\mathbf{w}|t)$ is the probability that the protocol does not abort given that state sent in the $t^{\text{th}}$ round is stored. For convenience, we set $p_T(t) = \frac{1}{n}$. Then the trace norm is given by

$$ 
\begin{aligned}
\frac{1}{2} \| \rho_{\text{real}} - \rho_{\text{ideal}} \|_1 &= \frac{1}{2n} \sum_{t=1}^{n} \sum_{\mathbf{w} \in \Omega} p(\mathbf{w}|t) \| \Lambda_t(\rho_t) - \phi^+ \|_1 \\
&= \frac{1}{2n} \sum_{t=1}^{n} p(\Omega|t) \| \Lambda_t(\rho_t) - \phi^+ \|_1 \\
&\le \frac{1}{n} \sum_{t=1}^{n} p(\Omega|t) \sqrt{1 - F(\Lambda_t(\rho_t), \phi^+)}.
\end{aligned} 
\quad (C6) $$

For the inequality, we used the Fuchs van de Graaf inequality $[68] \frac{1}{2} \|\rho-\sigma\|_1 \le \sqrt{1-F(\rho, \sigma)}$ for two states $\rho, \sigma \in S(\mathcal{H})$. Next we use the relation

$$ F(\Lambda_t(\rho_t), \phi^+) = \sup_{\Lambda \in \mathcal{C}} F(\Lambda(\rho_t), \phi^+) \ge \inf_{\rho \in \mathcal{B}_{\mu_t}} \sup_{\Lambda \in \mathcal{C}} F(\Lambda(\rho), \phi^+) = \Xi_B(\mu_t), \quad (C7) $$

which follows from the definition of the optimal channels $\Lambda_t$, and the fact that $\rho_t \in \mathcal{B}_{\mu_t}$, where

$$ \mathcal{B}_{\mu_i} = \{ \rho \in S(\mathcal{H}_{Q_i^A} \otimes \mathcal{H}_{Q_i^B}) : \exists \{A_x\}_x, \{B_y\}_y \text{ s.t. } \text{tr}[B\rho] \ge \mu_i \}, \quad (C8) $$

where $\{A_x\}$ and $\{B_y\}$ are understood to be sets of two-outcome observables on $\mathcal{H}_{Q_i^A}$ and $\mathcal{H}_{Q_i^B}$, respectively, and $B$ is the Bell operator (B1) constructed from $A_x$ and $B_y$. This allows us to write

$$ \frac{1}{n} \sum_{t=1}^{n} p(\Omega|t) \sqrt{1 - F(\Lambda_t(\rho_t), \phi^+)} \le \frac{1}{n} \sum_{t=1}^{n} p(\Omega|t) \sqrt{1 - \Xi_B(\mu_t)}. \quad (C9) $$

Now, by noting $\Xi_{\mu_t} \ge 0$ we can bound the trace norm in terms of the abort probability,

$$ \frac{1}{2} \| \rho_{\text{real}} - \rho_{\text{ideal}} \|_1 \le \frac{1}{n} \sum_{t=1}^{n} p(\Omega|t) = p_{\Omega}. \quad (C10) $$
Alternatively, by noting $p(\Omega|t) \le 1$, we can bound the trace norm in terms of the average extractability,

$$ \frac{1}{2} \| \rho_{\text{real}} - \rho_{\text{ideal}} \|_1 \le \sum_{t=1}^{n} \frac{1}{n} \sqrt{1 - \Xi_B(\mu_t)} \le \sqrt{1 - \frac{1}{n} \sum_{t=1}^{n} \Xi_B(\mu_t)}, \quad (C11) $$

where for the second inequality we used the concavity of the square root.

Based on the above, we consider two cases, and introduce a free parameter $\delta > 0$.

**Case 1:** $\sum_{i=1}^{n} \frac{\mu_i}{n} - \frac{\eta_{\min}^Q}{n} \le \frac{n-1}{n}(\omega_\# - \kappa - \delta)$. That is, the average value of $\mu_i$ is less than $(\omega_\# - \kappa)\frac{n-1}{n} + \frac{\eta_{\min}^Q}{n}$ (recall $\eta_{\min}^Q$ is the minimum quantum value of the Bell expression (B1)). If this is the case, then we have that

$$ \sum_{i \neq t}^{n} \frac{\mu_i}{n-1} \le \sum_{i \neq t}^{n} \frac{\mu_i}{n-1} + \frac{\mu_t - \eta_{\min}^Q}{n-1} = \sum_{i=1}^{n} \frac{\mu_i}{n-1} - \frac{\eta_{\min}^Q}{n-1} \le \omega_\# - \kappa - \delta, \quad (C12) $$

where we used the fact that $\mu_t \ge \eta_{\min}^Q$ for the first inequality. The probability that the protocol does not abort given $T = t$ is given by $p(\Omega|t) = \mathbb{P}(\sum_{i \neq t}^{n} \frac{W_i}{n-1} \ge \omega_\# - \kappa)$. We can now apply Theorem 3, by choosing $X_i = W_i$, $\mathbb{E}[X_i] = \mu_i$, $r = (n-1)\delta$, $b_i = \max\{|\gamma_{xy}|\}$ and $a_i = -\max\{|\gamma_{xy}|\}$ to obtain the following bound:

$$ \begin{aligned} \mathbb{P}\left(\sum_{i \neq t}^{n} \frac{W_i}{n-1} \ge \omega_\# - \kappa\right) &= \mathbb{P}\left(\sum_{i \neq t}^{n} \frac{W_i}{n-1} \ge \omega_\# - \kappa - \delta + \frac{r}{n-1}\right) \\ &\le \mathbb{P}\left(\sum_{i \neq t}^{n} \frac{W_i}{n-1} \ge \sum_{i \neq t}^{n} \frac{\mu_i}{n-1} + \frac{r}{n-1}\right) \quad (C13) \\ &= \mathbb{P}\left(\sum_{i \neq t}^{n} (W_i - \mu_i) \ge r\right) \\ &\le \exp\left(-\frac{(n-1)}{\gamma^*} \delta^2\right) =: a(\delta), \end{aligned} $$

where for the first inequality we applied Equation (C12), and for the second we applied Theorem 3. Since the calculations are identical for all values of $t$, we obtain a bound on $p_\Omega$,

$$ p_{\Omega} \le a(\delta). \quad (C14) $$

Thus, in this case, we have that $\frac{1}{2}\|\rho_{\text{real}} - \rho_{\text{ideal}}\|_1 \le p_\Omega \le a(\delta)$.

**Case 2:** $\sum_{i=1}^{n} \frac{\mu_i}{n} - \frac{\eta_{\min}^Q}{n} > \frac{n-1}{n}(\omega_\# - \kappa - \delta)$. Let $f(\omega)$ be any non-decreasing convex function that lower bounds extractability $\Xi_B(\omega)$. Then

$$ \frac{1}{n} \sum_{i=1}^{n} \Xi(\mu_i) \ge \frac{1}{n} \sum_{i=1}^{n} f(\mu_i) \ge f\left(\frac{1}{n} \sum_{i=1}^{n} \mu_i\right) \ge f\left(\frac{n-1}{n}(\omega_\# - \kappa - \delta) + \frac{\eta_{\min}^Q}{n}\right). \quad (C15) $$

We thus have that

$$ \frac{1}{2} \| \rho_{\text{real}} - \rho_{\text{ideal}} \|_1 \le \sqrt{1 - \frac{1}{n} \sum_{t=1}^{n} \Xi_B(\mu_t)} \le \sqrt{1 - f\left(\frac{n-1}{n}(\omega_\# - \kappa - \delta) + \frac{\eta_{\min}^Q}{n}\right)} =: b_1(\delta), \quad (C16) $$

completing the proof. $\square$

### d. Completeness

**Definition 6 (Completeness).** A DISC protocol is called $\epsilon_c$-complete if there exists an honest implementation such that $p_\Omega \ge 1 - \epsilon_c$.
**Lemma 2.** Protocol 1 is $\epsilon_c$-complete, where

$$ \epsilon_c = 2 \exp \left( \frac{n-1}{\gamma^*} \kappa^2 \right). \qquad (C17) $$

*Proof.* Consider an honest implementation for which the variables $W_1, ..., W_n$ are i.i.d. random variables with $\mathbb{E}[W_i] = \omega_{\#}$. Then

$$ \begin{aligned} p(\Omega|t) &= 1 - \mathbb{P}\left(\sum_{i \neq t}^{n} \frac{W_i}{n-1} < \omega_{\#} - \kappa\right) \\ &= 1 - \mathbb{P}\left(-\sum_{i \neq t}^{n}(W_i - \mathbb{E}[W_i]) > (n-1)\kappa\right) \\ &\geq 1 - \mathbb{P}\left(\left|\sum_{i \neq t}^{n}(W_i - \mathbb{E}[W_i])\right| \geq (n-1)\kappa\right) \\ &\geq 1 - 2 \exp\left(\frac{n-1}{\gamma^*} \kappa^2\right), \end{aligned} \qquad (C18) $$

where we applied Theorem 3 to obtain the final inequality. The claim follows from the fact that $p_{\Omega} = \sum_{t=1}^{n} \frac{p(\Omega|t)}{n}$. $\square$

Combining soundness and completeness, we arrive at our composable security definition for a DISC protocol,

**Definition 7 (Security).** A DISC is $(\epsilon_s, \epsilon_c)$-secure if it is $\epsilon_s$-sound and $\epsilon_c$-complete.

It immediately follows from Lemmas 1 and 2 that Protocol 1 is $(\epsilon_s, \epsilon_c)$-secure, for $\epsilon_s$ and $\epsilon_c$ given by Equation (C3) and Equation (C17), respectively.

## 2. Security proof of Protocol 2

In Protocol 2, we relax the certification goal of the maximally entangled state to a state $\varepsilon$-close to the maximally entangled. The security proof is appropriately modified in the following.

### a. Real protocol

The real protocol is identical to that of Protocol 1, outlined in Section C1a.

### b. Ideal protocol

The ideal protocol is modified as follows. We will need the following definition of the Heaviside step function,

$$ \Theta(x) := \begin{cases} 1 & \text{if } x > 0 \\ 0 & \text{otherwise.} \end{cases} \qquad (C19) $$

* **Stage 1 and 2:** The ideal protocol runs the real protocol during stages 1 and 2.

* **Stage 3:** The ideal protocol aborts if the real protocol aborts. If the ideal protocol does not abort, then it replaces the stored state $\rho_t$ with the state $[(1 - \lambda_t)\Lambda_t(\rho_t) + \lambda_t\phi^+] \otimes \sigma_{aux}$ for any real number $\lambda_t \in (0, 1)$ satisfying

$$ \lambda_t \le \left( 1 - \frac{\varepsilon}{\sqrt{1 - \Xi_B(\mu_t)}} \right) \Theta \left( \sqrt{1 - \Xi_B(\mu_t)} - \varepsilon \right). \qquad (C20) $$
In the above, $\sigma_{\text{aux}} \in S(\mathcal{H}_{\text{aux}})$ is an auxiliary state on a Hilbert space $\mathcal{H}_{\text{aux}}$ satisfying $\mathbb{C}^2 \otimes \mathbb{C}^2 \otimes \mathcal{H}_{\text{aux}} \cong \mathcal{H}_{Q_t^A} \otimes \mathcal{H}_{Q_t^B}$. The cq-state of the ideal protocol at this stage is:

$$ \rho = \left( \sum_{t=1}^{n} p_T(t) \sum_{\mathbf{w} \in \Omega} p(\mathbf{w}|t) |\mathbf{w}\rangle\langle\mathbf{w}|\mathbf{w} \otimes |t\rangle\langle t|_T \otimes [(1-\lambda_t)\Lambda_t(\rho_t) + \lambda_t \phi^+] \otimes \sigma_{\text{aux}} \otimes |\Omega\rangle\langle\Omega| \right) + (1-p_{\Omega}) |\perp\rangle\langle\perp|. $$

* **Stage 4:** The ideal protocol throws away the contents of the auxiliary register and outputs $(1-\lambda_t)\Lambda_t(\rho_t) + \lambda_t \phi^+$. This will give the final state of the ideal protocol

$$ \rho_{\text{ideal}} = \sum_{t=1}^{n} \sum_{\mathbf{w} \in \Omega} p(\mathbf{w}|t)p_T(t)|\mathbf{w}\rangle\langle\mathbf{w}|\mathbf{w} \otimes |t\rangle\langle t|_T \otimes [(1-\lambda_t)\Lambda_t(\rho_t) + \lambda_t \phi^+] \otimes |\Omega\rangle\langle\Omega| + (1-p_{\Omega}) |\perp\rangle\langle\perp|. $$

### c. Soundness

**Lemma 3.** Protocol 2 is $\epsilon_s$-sound, where

$$ \begin{aligned} \epsilon_s &= \inf_{\delta>0} \max\{a(\delta), b_2(\delta)\}, \\ b_2(\delta) &= G_{\epsilon} \left( \frac{n-1}{n}(\omega_{\#} - \kappa - \delta) + \frac{\eta_{\min}^{Q}}{n} \right), \end{aligned} \qquad (C21) $$

$a(\delta)$ is defined in Lemma 1 and $G_{\epsilon}(\omega)$ is any non-increasing concave function that upper bounds the function $\Theta(\sqrt{1-\Xi(\omega)} - \epsilon)(\sqrt{1-\Xi(\omega)} - \epsilon)$.

*Proof.* The proof proceeds similarly to that of Lemma 1, with some key differences. We begin by writing

$$ \begin{aligned} \|\rho_{\text{real}} - \rho_{\text{ideal}}\|_1 &= \frac{1}{n} \sum_{t=1}^{n} \sum_{\mathbf{w} \in \Omega} p(\mathbf{w}|t) \|\Lambda(\rho_t) - (1-\lambda_t)\Lambda_t(\rho_t) - \lambda_t \phi^+\|_1 \\ &= \frac{1}{n} \sum_{t=1}^{n} p(\Omega|t) \lambda_t \|\Lambda_t(\rho_t) - \phi^+\|_1 \\ &\le \frac{2}{n} \sum_{t=1}^{n} p(\Omega|t) \lambda_t \sqrt{1 - F(\Lambda_t(\rho_t), \phi^+)} \qquad (C22) \\ &\le \frac{2}{n} \sum_{t=1}^{n} p(\Omega|t) \left(1 - \frac{\epsilon}{\sqrt{1 - \Xi_B(\mu_t)}}\right) \Theta\left(\sqrt{1 - \Xi_B(\mu_t)} - \epsilon\right) \sqrt{1 - \Xi_B(\mu_t)} \\ &\le \frac{2}{n} \sum_{t=1}^{n} p(\Omega|t) G_{\epsilon}(\mu_t). \end{aligned} $$

For the first inequality we used the relationship between the trace distance and fidelity, for the second we used Equation (C9) and Equation (C20), and for the third we introduced the function $G_{\epsilon}(\omega)$ as described in the theorem statement.

The proof now proceeds in two cases, and we introduce a free parameter $\delta > 0$.

**Case 1:** $\sum_{i=1}^n \frac{\mu_i}{n} - \frac{\eta_{\min}^Q}{n} \le \frac{n-1}{n}(\omega_{\#} - \kappa - \delta)$. The proof proceeds identically to Case 1 in the proof of Lemma 1.

**Case 2:** $\sum_{i=1}^n \frac{\mu_i}{n} - \frac{\eta_{\min}^Q}{n} > \frac{n-1}{n}(\omega_{\#} - \kappa - \delta)$. Following Case 2 in the proof of Lemma 1, we use the bound $p(\Omega|t) \le 1$ and the concavity of $G_{\epsilon}(\omega)$ to obtain

$$ \frac{1}{2} \|\rho_{\text{real}} - \rho_{\text{ideal}}\|_1 \le \frac{1}{n} \sum_{t=1}^{n} G_{\epsilon}(\mu_t) \le G_{\epsilon} \left( \frac{n-1}{n} (\omega_{\#} - \kappa - \delta) + \frac{\eta_{\min}^{Q}}{n} \right) =: b_2(\delta). \qquad (C23) $$

This completes the proof. □
### d. Completeness

Note that Lemma 2 also applies to Protocol 2, resulting in $(\epsilon_s, \epsilon_c)$-security, for $\epsilon_s$ and $\epsilon_c$ given by Equation (C21) and Equation (C17), respectively.

### 3. Security proof of Protocol 3

In this subsection, we prove the security of Protocol 3, which does not require the user to apply the optimal channel $\Lambda_t$ to the stored state. Instead, the user outputs the state $\rho_t$ directly, and the certification of $\rho_t$ is described by its closeness to a companion state.

**Definition 8 (Companion state).** Let $\rho \in S(H_{Q^A} \otimes H_{Q^B})$, $\mu = \text{tr}[B\rho]$ for a given Bell operator $B$, $|\phi\rangle \in H_{\hat{Q}^A} \otimes H_{\hat{Q}^B}$ be a target state and $C$ be a class of free operations. A state $\sigma \in S(H_{\hat{Q}^A} \otimes H_{\hat{Q}^B} \otimes H_{Q^A} \otimes H_{Q^B})$ is a companion state of $\rho$ if it is of the form

$$ \sigma = U^{\dagger}(\phi \otimes \sigma_{\text{aux}})U, \qquad (C24) $$

where $\sigma_{\text{aux}} \in S(H_{Q^A} \otimes H_{Q^B})$, $U$ is a unitary operator on $H_{\hat{Q}^A} \otimes H_{\hat{Q}^B} \otimes H_{Q^A} \otimes H_{Q^B}$ satisfying $\text{tr}_{Q^A Q^B}[U(|00\rangle\langle00| \otimes \tau)U^{\dagger}] = \Lambda(\tau)$ for all $\tau \in S(H_{Q^A} \otimes H_{Q^B})$ and a channel $\Lambda \in C$, and

$$ F(|00\rangle\langle00| \otimes \rho, \sigma) \ge \Xi_B(\mu). \qquad (C25) $$

The existence of a companion state $\sigma$ for a given state $\rho$ is significant, since implies the following chain of inequalities hold,

$$ \Xi_B(\mu) \le F(|00\rangle\langle00| \otimes \rho, \sigma) = F(U(|00\rangle\langle00| \otimes \rho)U^{\dagger}, \phi \otimes \sigma_{\text{aux}}) \le F(\Lambda(\rho), \phi), \qquad (C26) $$

where we used the fact that the fidelity is invariant under unitaries, and does not contract under the partial trace. In words, there exists a channel $\Lambda$ which extracts the target state $\phi$ with fidelity at least $\Xi_B(\mu)$. The set of allowable unitaries $U$ is given by the Naimark dilation of every channel $\Lambda \in C$. For example, if $C$ corresponds to the set of local channels $\Lambda_A \otimes \Lambda_B$, $U = U_A \otimes U_B$ is a local unitary. The following lemma guarantees the existence of a companion state for every state $\rho$.

**Lemma 4.** Let $\rho \in S(H_{Q^A} \otimes H_{Q^B})$, $\mu = \text{tr}[B\rho]$ for a Bell operator $B$, $|\phi\rangle \in H_{\hat{Q}^A} \otimes H_{\hat{Q}^B}$ be a target state and $C$ be a class of free operations. Then there always exists a companion state to $\rho$ according to Definition 8.

*Proof.* We prove the above though an explicit construction. Let

$$ \Lambda^* = \arg\max\{F(\Lambda(\rho), \phi) : \Lambda : S(H_{Q^A} \otimes H_{Q^B}) \to S(H_{\hat{Q}^A} \otimes H_{\hat{Q}^B}), \Lambda \in C\}. \qquad (C27) $$

We can always describe $\Lambda^*$ by the action of an isometry $V : H_{Q^A} \otimes H_{Q^B} \to H_{\hat{Q}^A} \otimes H_{\hat{Q}^B} \otimes H_{Q^A} \otimes H_{Q^B}$ followed by a partial trace over $Q^A Q^B$, $\Lambda^*(\tau) = \text{tr}_{Q^A Q^B}[V\tau V^{\dagger}]$. We can further assume that $V = U(|00\rangle \otimes \mathbb{I}_{Q^A} \otimes \mathbb{I}_{Q^B})$ where $U$ is a unitary on $H_{\hat{Q}^A} \otimes H_{\hat{Q}^B} \otimes H_{Q^A} \otimes H_{Q^B}$. Let $|\Psi\rangle \in H_{Q^A} \otimes H_{Q^B} \otimes H_E$ be any purification of $\rho$. Note that the state $|\Psi'\rangle = (V \otimes \mathbb{I}_E)|\Psi\rangle$ is a purification of $\Lambda^*(\rho)$. To see this, observe

$$ \text{tr}_{\hat{Q}^A \hat{Q}^B E}[\Psi'] = \text{tr}_{\hat{Q}^A \hat{Q}^B} [\text{tr}_E[(V \otimes \mathbb{I}_E)\Psi(V^{\dagger} \otimes \mathbb{I}_E)]] = \text{tr}_{\hat{Q}^A \hat{Q}^B} [V \rho V^{\dagger}] = \Lambda^*(\rho). \qquad (C28) $$

Recall, Uhlmann's theorem (see, e.g., [53, Theorem 9.2.1]) relates the fidelity of two states to the maximum overlap between their purifications,

$$ F(\rho, \sigma) = \max_{|\Psi_{\sigma}\rangle} |\langle\Psi_{\rho}|\Psi_{\sigma}\rangle|^2, \qquad (C29) $$

where $\Psi_{\rho}$ is any purification of $\rho$ and the maximization is taken over all purifications $\Psi_{\sigma}$ of $\sigma$. Applying this to $F(\Lambda^*(\rho), \phi)$, we find

$$ F(\Lambda^*(\rho), \phi) = \max_{|\psi'\rangle} |\langle\psi'|(|\phi\rangle \otimes |\psi'\rangle)|^2 = \max_{|\psi'\rangle} F(\Psi', \phi \otimes \psi'), \qquad (C30) $$
where the maximization is taken over all states $|\psi'\rangle \in \mathcal{H}_{Q^A} \otimes \mathcal{H}_{Q^B} \otimes \mathcal{H}_E$, and we used the fact that the purification of any pure state must be separable. Note that we can write

$$ \Psi' = (V \otimes \mathbb{I}_E)\Psi(V^\dagger \otimes \mathbb{I}_E) = (U \otimes \mathbb{I}_E)(|00\rangle\langle 00| \otimes \Psi)(U^\dagger \otimes \mathbb{I}_E). \quad (C31) $$

This implies

$$ \begin{aligned} F(\Psi', \phi \otimes \psi') &= F((U \otimes \mathbb{I}_E)(|00\rangle\langle 00| \otimes \Psi)(U^\dagger \otimes \mathbb{I}_E), \phi \otimes \psi') \\ &= F(|00\rangle\langle 00| \otimes \Psi, (U^\dagger \otimes \mathbb{I}_E)(\phi \otimes \psi')(U \otimes \mathbb{I}_E)) \\ &\le F(|00\rangle\langle 00| \otimes \rho, \mathrm{tr}_E[(U^\dagger \otimes \mathbb{I}_E)(\phi \otimes \psi')(U \otimes \mathbb{I}_E)]), \end{aligned} \quad (C32) $$

where we used the fact that the fidelity is invariant under unitary operations, followed by its monotonicity under the partial trace. Let

$$ \sigma = \mathrm{tr}_E[(U^\dagger \otimes \mathbb{I}_E)(\phi \otimes \psi^*)(U \otimes \mathbb{I}_E)] = U^\dagger(\phi \otimes \mathrm{tr}_E[\psi^*])U, \quad (C33) $$

where $\psi^*$ achieves the optimal value of the maximization $\max_{|\psi'\rangle} F(\Psi', \phi \otimes \psi')$. Then we see $\sigma$ is of the form in Equation (C24). Furthermore,

$$ F(|00\rangle\langle 00| \otimes \rho, \sigma) \ge F(\Psi', \phi \otimes \psi') = F(\Lambda^*(\rho), \phi) = \sup_{\Lambda \in \mathcal{C}} F(\Lambda(\rho), \phi) \ge \inf_{\rho' \in \mathcal{B}_\mu} \sup_{\Lambda \in \mathcal{C}} F(\Lambda(\rho'), \phi) = \Xi_B(\mu), \quad (C34) $$

where the first inequality follows from Equation (C32), the first equality follows from Equation (C30), the second equality follows from the definition of $\Lambda^*$ and the second inequality follows from the fact that $\rho \in \mathcal{B}_\mu$, where $\mathcal{B}_\mu$ is defined analogously to Equation (C8). Thus, $\sigma$ satisfies Definition 8, completing the proof. $\square$

Having defined a companion state, we can now prove the security of Protocol 5.

### a. Real protocol

The real protocol is identical to the real protocol described in Section C 1 a, except stage 4 is omitted, and it outputs the state $|00\rangle\langle 00| \otimes \rho_t$. We therefore see the final cq-state takes the form

$$ \rho_{\text{real}} = \left( \sum_{t=1}^{n} p_T(t) \sum_{\mathbf{w} \in \Omega} p(\mathbf{w}|t) |\mathbf{w}\rangle\langle\mathbf{w}| \mathbf{w} \otimes |t\rangle\langle t|_T \otimes |00\rangle\langle 00| \otimes \rho_t \otimes |\Omega\rangle\langle\Omega| \right) + (1-p_{\Omega}) |\perp\rangle\langle\perp|. \quad (C35) $$

### b. Ideal protocol

The ideal protocol is modified as follows.

* **Stage 1 and 2:** The ideal protocol runs the real protocol during stages 1 and 2.

* **Stage 3:** The ideal protocol aborts if the real protocol aborts. If the ideal protocol does not abort, then it replaces the stored state $\rho_t$ with the state $(1 - \lambda_t)|00\rangle\langle 00| \otimes \rho_t + \lambda_t \sigma_t$, where $\lambda_t \in (0, 1)$ satisfies Equation (C20) and $\sigma_t$ is a companion state to $\rho_t$. The final cq-state of the ideal protocol is given by

$$ \rho_{\text{ideal}} = \left( \sum_{t=1}^{n} p_T(t) \sum_{\mathbf{w} \in \Omega} p(\mathbf{w}|t) |\mathbf{w}\rangle\langle\mathbf{w}| \mathbf{w} \otimes |t\rangle\langle t|_T \otimes [(1 - \lambda_t)|00\rangle\langle 00| \otimes \rho_t + \lambda_t \sigma_t] \otimes |\Omega\rangle\langle\Omega| \right) + (1 - p_{\Omega}) |\perp\rangle\langle\perp|. $$

### c. Soundness

**Lemma 5.** Protocol 3 is $\epsilon_s$-sound, where $\epsilon_s$ is given by Equation (C21).
Proof. The proof follows that of Lemma 3, expect with $F(\Lambda_t(\rho_t), \phi^+)$ replaced with $F(|00\rangle\langle00| \otimes \rho_t, \sigma_t)$, i.e.,

$$ \|\rho_{\text{real}} - \rho_{\text{ideal}}\|_1 \le \frac{2}{n} \sum_{t=1}^{n} p(\Omega|t)\lambda_t \sqrt{1 - F(|00\rangle\langle00| \otimes \rho_t, \sigma_t)}. \quad (C36) $$

Using the property C25 of $\sigma_t$, we see $F(|00\rangle\langle00| \otimes \rho_t, \sigma_t) \ge \Xi(\mu_t)$, hence

$$ \|\rho_{\text{real}} - \rho_{\text{ideal}}\|_1 \le \frac{2}{n} \sum_{t=1}^{n} p(\Omega|t)\lambda_t \sqrt{1 - \Xi_B(\mu_t)}. \quad (C37) $$

The proof then proceeds identically to that of Lemma 3. □

### d. Completeness

Lemma 2 applies to Protocol 3, resulting in $(\epsilon_s, \epsilon_c)$-security, for $\epsilon_s$ and $\epsilon_c$ given by Equation (C21) and Equation (C17), respectively.

**Remark 5.** We note that the security statements presented in Lemmas 1, 3 and 5 are not tight. To derive an upper bound for the trace norm, we have set $p(\Omega|i)$ to 1, which may not be optimal. In principle, it should be possible to bound this in terms of the average Bell value $\frac{1}{n-1}\sum_{j \ne i} \mu_j$, resulting in a more complex expression for the soundness parameter. We leave this refinement for future work.

**Remark 6.** As the extractability function can be assumed to be convex (if it isn't, one can always take the convex lower bound), the function $G_\epsilon(\omega)$ is automatically concave for $\epsilon = 0$. For $\epsilon > 0$, the optimal way to define the function $G_\epsilon(\omega)$ is by

$$ G_{\epsilon}(\omega) = -\text{conenv} \left( -\Theta(\sqrt{1 - \Xi_B(\omega)} - \epsilon)(\sqrt{1 - \Xi_B(\omega)} - \epsilon) \right), \quad (C38) $$

where conenv is the convex envelope (convex lower bound). Computing the convex envelopes of functions on $\mathbb{R}$ is relatively straightforward (see, for example, [58, Section 8.10]), but for functions on $\mathbb{R}^n$, it can be difficult in general. For $n = 2, 3$, there exist fast algorithms to compute this function (see [69]). We plot the function $G_\epsilon(\omega)$ for different values of $\epsilon$ in Figure 10 also given in the main text and provided here for completeness.

<figure><img src="image_12.png" /><figcaption>FIG. 10: Graph of $G_\epsilon(\omega)$ for different values of $\epsilon$, using LOCC extractability.</figcaption></figure>

## Appendix D: Security proof of Protocols 4 and 5

### 1. Modeling the sequential process

Before proving security of the sequential protocols, we analyze the structure of the channels $N_i = N_i^A \otimes N_i^B$ defined in Section IV. Specifically, $N_i^A : O_{i-1}^A Q_i^A \to A_i X_i O_i^A$ and $N_i^B : O_{i-1}^B Q_i^B \to B_i Y_i O_i^B$, where the systems $O_i^A$ and $O_i^B$
model the internal memory of each device. It is important to emphasize that the channels in each round act on the state generated for round i only, as well as the state held in the device's memory. Mathematically, this independence implies that the input state to $M_i^A$ is given by $\text{tr}_{Q_i^B}(\rho_i) \otimes \sigma_{O_{i-1}}$, where $\sigma_{O_{i-1}}$ represents the quantum state stored in the device's memory. We then have, writing $\tau_{Q_i^A} = \text{tr}_{Q_i^B}(\rho_i)$,

$$ \mathcal{N}_i^A(\tau_{Q_i^A} \otimes \sigma_{O_{i-1}^A}) = \sum_{a,x \in \{0,1\}} p(x) |x\rangle\langle x|_{X_i} \otimes |a\rangle\langle a|_{A_i} \otimes \mathcal{N}_i^{a|x}(\tau_{Q_i^A} \otimes \sigma_{O_{i-1}^A}), \quad (D1) $$

where $\mathcal{N}_i^{a|x} : Q_i^A O_{i-1}^A \to O_i^A$ is a completely positive trace non-increasing map, which satisfies $\sum_a \text{tr}[\mathcal{N}_i^{a|x}(\tau)] = 1$ for all states $\tau \in S(\mathcal{H}_{Q_i^A} \otimes \mathcal{H}_{O_{i-1}^A})$. We denote the marginal probabilities

$$ \begin{aligned} p^{A_i}(a|x) &= \text{tr}[\mathcal{N}_i^{a|x}(\tau \otimes \sigma)] \\ &= \text{tr}[(\tau \otimes \sigma)M_{a|x}^i] \\ &= \text{tr}[(\tau \otimes \mathbb{I}_{O_{i-1}^A})(\mathbb{I}_{Q_i^A} \otimes \sqrt{\sigma})M_{a|x}^i(\mathbb{I}_{Q_i^A} \otimes \sqrt{\sigma})] \\ &= \text{tr}[\tau \text{tr}_{O_{i-1}^A}[(\mathbb{I}_{Q_i^A} \otimes \sqrt{\sigma})M_{a|x}^i(\mathbb{I}_{Q_i^A} \otimes \sqrt{\sigma})]] \\ &= \text{tr}[\tau \tilde{M}_{a|x}^i]. \end{aligned} \quad (D2) $$

In the above, we defined $M_{a|x}^i = \sum_\mu K_\mu^\dagger K_\mu$, where $\{K_\mu\}_\mu$ is a set of Kraus operators for the channel $\mathcal{N}_i^{a|x}$, used the identity $\text{tr}_B[(Y_A \otimes \mathbb{I}_B)X_{AB}] = Y_A \text{tr}_B[X_{AB}]$ for the fourth equality, and defined

$$ \tilde{M}_{a|x}^i := \text{tr}_{O_{i-1}^A}((\mathbb{I}_{Q_i^A} \otimes \sqrt{\sigma})M_{a|x}^i(\mathbb{I}_{Q_i^A} \otimes \sqrt{\sigma})). \quad (D3) $$

Note the set of operators $\{M_{a|x}^i\}_a$ are a POVM, and as a result the set of operators $\{\tilde{M}_{a|x}^i\}_a$ are also a POVM. By a similar procedure, we can define the POVMs $\{\tilde{N}_{b|y}^i\}$ from the channel $\mathcal{N}_i^B$, and describe the joint behavior of round i by

$$ p^i(a, b|x, y) = \text{tr}[\rho_i(\tilde{M}_{a|x}^i \otimes \tilde{N}_{b|y}^i)]. \quad (D4) $$

Thus, from the point of view of the statistics, we can view $\mathcal{N}_i^A \otimes \mathcal{N}_i^B$ as performing an uncharacterized measurement acting on the generated state $\rho_i$, rather than the state and internal device memory.

Based on the above, we define

$$ \mu_i = \text{tr}[\tilde{B}_i \rho_i], \quad (D5) $$

where

$$ \tilde{B}_i = \frac{1}{4} \sum_{a,b,x,y \in \{0,1\}} w_{abxy}(\tilde{M}_{a|x}^i \otimes \tilde{N}_{b|y}^i), \quad (D6) $$

and $w_{abxy} = 1$ if $a \oplus b = x \cdot y$ and 0 otherwise. We also define the optimized CHSH values associated to each state $\rho_i$,

$$ \mu_i^\dagger = \max_{\{\tilde{M}_{a|x}^i\}_a, \{\tilde{N}_{b|y}^i\}_b} \text{tr}[\tilde{B}_i \rho_i]. \quad (D7) $$

Note that $\mu_i^\dagger$ is only dependent on the state $\rho_i$, and not the measurement device. The values $\mu_i^\dagger$ thus only depend on round i.

## 2. Security proof of Protocol 4

### a. Real and ideal protocols

The final state of the real and ideal protocols have an identical structure to that of Protocol 2, though the statistics of each round are no longer distributed independently. For convenience, we recall the real and ideal protocol final
outputs below,

$$
\begin{align}
\rho_{\text{real}} &= \sum_{t=1}^{n} p_T(t) \sum_{\mathbf{w} \in \Omega} p(\mathbf{w}|t) |\mathbf{w}\rangle\langle\mathbf{w}|\mathbf{w} \otimes |t\rangle\langle t|_T \otimes \Lambda_t(\rho_t) \otimes |\Omega\rangle\langle\Omega| + (1-p_{\Omega}) |\perp\rangle\langle\perp|, \tag{D8} \\
\rho_{\text{ideal}} &= \sum_{t=1}^{n} \sum_{\mathbf{w} \in \Omega} p(\mathbf{w}|t) p_T(t) |\mathbf{w}\rangle\langle\mathbf{w}|\mathbf{w} \otimes |t\rangle\langle t|_T \otimes [(1-\lambda_t)\Lambda_t(\rho_t) + \lambda_t \phi^+] \otimes |\Omega\rangle\langle\Omega| + (1-p_{\Omega}) |\perp\rangle\langle\perp|. \nonumber
\end{align}
$$

b. Soundness

**Lemma 6.** Protocol 4 is $\epsilon_s$-sound,

$$
\begin{align}
\epsilon_s &= \inf_{\delta>0} \max\{a_2(\delta), b_3(\delta)\}, \nonumber \\
a_2(\delta) &= \exp\left(-\frac{\lfloor(n-1)\delta\rfloor^2}{n-1}\right), \tag{D9} \\
b_3(\delta) &= G_{\epsilon}\left(\lfloor(n-1)(p_{\#}^{\text{win}} - \kappa - \delta)\rfloor/n\right). \nonumber
\end{align}
$$

*Proof.* We follow the proof of Lemma 3 to obtain

$$
\| \rho_{\text{real}} - \rho_{\text{ideal}} \|_1 \le \frac{2}{n} \sum_{t=1}^{n} p(\Omega|t) \sqrt{1 - F(\Lambda_t(\rho_t), \phi^+)} \quad (\text{D10})
$$

Recall the random variables $W_i$, governed by the distribution $p^i$ from Equation (D4), which indicate whether or not the CHSH game was won on that round, satisfy $\mathbb{P}(W_i = 1) = \mu_i$. We can define a new set of random variables, $\{\hat{W}_i\}_{i,}$ distributed according to the optimized expectation values $\mu_i^\uparrow$, $\mathbb{P}(\hat{W}_i = 1) = \mu_i^\uparrow$. Note that $\{\hat{W}_i\}$ are a set of independently distributed random variables. We now consider two cases, and introduce a free parameter $\delta > 0$.

**Case 1:** $\sum_{i=1}^n \mu_i^\uparrow \le \lfloor (n-1)(p_\#^{\text{win}} - \kappa - \delta) \rfloor$. That is, the average value of $\mu_i^\uparrow$ is less than $\lfloor (n-1)(p_\#^{\text{win}} - \kappa) \rfloor / n$. Note that, since the variables $\hat{W}_i$ are independent, by following the proof Lemma 3 exactly (using the fact that $\mu_i^\uparrow \ge 0$ to omit the contribution of $\eta_{\min}^n$), we find using Theorem 3

$$
\hat{p}(\Omega|t) := \mathbb{P} \left( \sum_{i \neq t}^{n} \hat{W}_i \ge \lfloor (n-1)(p_{\#}^{\text{win}} - \kappa) \rfloor \right) \le \exp \left( - \frac{\lfloor (n-1)\delta \rfloor^2}{n-1} \right) =: a_3(\delta). \quad (\text{D11})
$$

That is, the probability of the independent protocol (which generates the variables $\hat{W}_i$) not aborting is small. However, we have not shown that the probability of the actual protocol not aborting is also small. To establish this, we apply Corollary 1 to show that the former upper bounds the latter. Specifically, we obtain

$$
p(\Omega|t) = \mathbb{P}\left(\sum_{i \neq t}^{n} W_i \ge \lfloor(n-1)(p_{\#}^{\text{win}} - \kappa)\rfloor\right) \le \hat{p}(\Omega|t) \le a_3(\delta), \quad (\text{D12})
$$

which implies (by bounding $\sqrt{1 - F(\Lambda_t(\rho_t), \phi^+)} \le 1$)

$$
\frac{1}{2} \| \rho_{\text{real}} - \rho_{\text{ideal}} \|_1 \le a_2(\delta). \qquad (\text{D13})
$$

**Case 2:** $\sum_{i=1}^n \mu_i^\uparrow \le \lfloor (n-1)(\omega_\# - \kappa - \delta) \rfloor$. We apply the bound $p(\Omega|t) \le 1$ to obtain

$$
\| \rho_{\text{real}} - \rho_{\text{ideal}} \|_1 \le \frac{2}{n} \sum_{t=1}^{n} \sqrt{1 - F(\Lambda_t(\rho_t), \phi^+)} \quad (\text{D14})
$$

We then note

$$
F(\Lambda_t(\rho_t), \phi^+) = \sup_{\Lambda \in \mathcal{C}} F(\Lambda(\rho_t), \phi^+) \ge \inf_{\rho \in \mathcal{B}(\mu_t^\uparrow)} \sup_{\Lambda \in \mathcal{C}} F(\Lambda(\rho), \phi^+) = \Xi_B(\mu_t^\uparrow). \quad (\text{D15})
$$
The inequality follows from the fact that, by the definition of $\mu_t^\uparrow$, there exists measurements which achieve $\text{tr}[\hat{B}_t\rho_t] = \mu_t^\uparrow$, i.e., $\rho_t \in \mathcal{B}(\mu_t^\uparrow)$. This implies

$$ \frac{1}{2} \|\rho_{\text{real}} - \rho_{\text{ideal}}\|_1 \le \frac{1}{n} \sum_{t=1}^{n} \sqrt{1 - \Xi_B(\mu_t^\uparrow)}. \qquad (\text{D16}) $$

The remainder of the proof follows identically that of Lemma 3, Case 2. □

### c. Completeness

We could also apply Lemma 2 to bound the completeness error of Protocol 4. However, since we are restricting to the CHSH case, where the variables $W_i$ are binary, we can use a sharper concentration inequality.

**Theorem 4 ([70]).** Let $n \in \mathbb{N}$, $p \in (0, 1)$ and $Z$ be a random variable distributed according to $Z \sim \text{Binomial}(n, p)$. Then, for every $k = 0, ..., n-1$ we have

$$ C(n, p, k) \le \mathbb{P}(X \le k) \le C(n, p, k+1), \qquad (\text{D17}) $$

where

$$ \begin{aligned} C(n, p, k) &= \Phi(\text{sign}(k/n - p)\sqrt{2nG(k/n, p)}), \\ \Phi(x) &= \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{x} du e^{-u^2/2}, \qquad (\text{D18}) \\ G(x, p) &= x \ln\left(\frac{x}{p}\right) + (1-x) \ln\left(\frac{1-x}{1-p}\right). \end{aligned} $$

**Lemma 7.** Protocol 4 is $\epsilon_c$-complete, where

$$ \epsilon_c = 1 - C(N - 1, p_{\#}^{\text{win}}, \lceil(N - 1)(p_{\#}^{\text{win}} - \kappa)\rceil). \qquad (\text{D19}) $$

*Proof.* Consider an honest implementation for which the variables $W_1, ..., W_n$ are i.i.d. random variables with $\mathbb{E}[W_i] = \omega_{\#}$. Let $\bar{W}_i = 1 - W_i$. Then

$$ \begin{aligned} 1 - p(\Omega|t) &= \mathbb{P}\left(\sum_{i \neq t}^{n} \bar{W}_i > (n-1)(1 - [p_{\#}^{\text{win}} - \kappa])\right) \\ &= 1 - \mathbb{P}\left(\sum_{i \neq t}^{n} \bar{W}_j \le (n-1)(1 - [p_{\#}^{\text{win}} - \kappa])\right) \qquad (\text{D20}) \\ &\le 1 - \mathbb{P}\left(\sum_{i \neq t}^{n} \bar{W}_j \le \lceil(n-1)(1 - [p_{\#}^{\text{win}} - \kappa])\rceil\right). \end{aligned} $$

Let $Z = \sum_{i \neq t}^{n} \bar{W}_i$. Then $Z$ is a random variable distributed according to $\text{Binomial}(n - 1, 1 - p_{\#}^{\text{win}})$. We can therefore apply Theorem 4 to obtain

$$ p(\Omega|t) \ge C(n-1, 1-p_{\#}^{\text{win}}, \lceil(n-1)(1-[p_{\#}^{\text{win}}-\kappa])\rceil). \qquad (\text{D21}) $$

We therefore have

$$ p_{\Omega} = \frac{1}{n} \sum_{t=1}^{n} p(\Omega|t) \ge C(n-1, 1-p_{\#}^{\text{win}}, \lceil(n-1)(1-[p_{\#}^{\text{win}}-\kappa])\rceil), \qquad (\text{D22}) $$

proving the claim. □

As a result, we find Protocol 4 is $(\epsilon_s, \epsilon_c)$-secure where $\epsilon_s$ and $\epsilon_c$ are given by Equation (C21) and Equation (D19), respectively.
### 3. Security proof of Protocol 5

In this final subsection, we prove the security of Protocol 5, which is a variant of Protocol 4 in which the user is not required to apply the final extraction channel $\Lambda_t$.

#### a. Real and ideal protocols

These have an identical structure to that of Protocol 3. Specifically, the final outputs are given by

$$ \rho_{\text{real}} = \left( \sum_{t=1}^{n} p_T(t) \sum_{\mathbf{w} \in \Omega} p(\mathbf{w}|t) |\mathbf{w}\rangle\langle\mathbf{w}|\mathbf{w} \otimes |t\rangle\langle t|_T \otimes |00\rangle\langle 00| \otimes \rho_t \otimes |\Omega\rangle\langle\Omega| \right) + (1 - p_{\Omega}) |\perp\rangle\langle\perp|, \quad (\text{D23}) $$

$$ \rho_{\text{ideal}} = \left( \sum_{t=1}^{n} p_T(t) \sum_{\mathbf{w} \in \Omega} p(\mathbf{w}|t) |\mathbf{w}\rangle\langle\mathbf{w}|\mathbf{w} \otimes |t\rangle\langle t|_T \otimes [(1-\lambda_t)|00\rangle\langle 00| \otimes \rho_t + \lambda_t \sigma_t] \otimes |\Omega\rangle\langle\Omega| \right) + (1-p_{\Omega}) |\perp\rangle\langle\perp|, $$

where $\sigma_t$ is the companion state of $\rho_t$.

#### b. Soundness

**Lemma 8.** Protocol 5 is $\epsilon_s$-sound, where $\epsilon_s$ is given by Equation (D9).

*Proof.* The proof follows the structure to that of Lemma 5, with the same modifications introduced to prove Lemma 6. In detail we have

$$ \|\rho_{\text{real}} - \rho_{\text{ideal}}\|_1 \le \frac{2}{n} \sum_{t=1}^{n} p(\Omega|t) \lambda_t \sqrt{1 - F(|00\rangle\langle 00| \otimes \rho_t, \sigma_t)}. \quad (\text{D24}) $$

**Case 1:** $\sum_{i=1}^n \frac{\mu_i^\uparrow}{n} \le \frac{n-1}{n} (p_{\#}^{\text{win}} - \kappa - \delta)$. Here, the proof proceeds identically to that of Lemma 6, Case 1.

**Case 2:** $\sum_{i=1}^n \frac{\mu_i^\uparrow}{n} > \frac{n-1}{n} (p_{\#}^{\text{win}} - \kappa - \delta)$. We proceed by bounding $p(\Omega|t) \le 1$ and lower bounding the fidelity via the extractability $\Xi_B(\mu_i^\uparrow)$. Since $\sigma_t$ is a companion state of $\rho_t$, and $\rho_t \in \mathcal{B}(\mu_t^\uparrow)$, it follows from the same reasoning used in Equation (C34) that

$$ F(|00\rangle\langle 00| \otimes \rho_t, \sigma_t) \ge \sup_{\Lambda \in \mathcal{C}} F(\Lambda(\rho_t), \phi^+) \ge \inf_{\rho \in \mathcal{B}(\mu_t^\uparrow)} \sup_{\Lambda \in \mathcal{C}} F(\Lambda(\rho), \phi^+) = \Xi_B(\mu_t^\uparrow). \quad (\text{D25}) $$

The remainder of the proof follows identically to that of Lemma 3, Case 2. $\square$

#### c. Completeness

Protocol 5 has a completeness error given by Lemma 7, resulting in $(\epsilon_s, \epsilon_c)$-security where $\epsilon_s$ and $\epsilon_c$ are given by Equation (C21) and Equation (D19), respectively.

### Appendix E: Bounding the abort probability in the sequential setting

The aim of this section is to show that the abort probability of Protocol 4 can be bounded in terms of the maximal achievable CHSH scores $\mu_i^\uparrow$, defined in Equation (D7). To do so, we describe the sequential protocol as stochastic process $(\Gamma, \mathcal{A}, P)$, where

* The sample space $\Gamma$ consists of all possible sequences of outcomes of the experiment. Each round measurement round $i$ results in either a loss (0) or a win (1) of the CHSH game, recorded in the classical register $W_i$. To ease notation, we consider $n$ such rounds, though in the actual protocol there are $n-1$. Hence

$$ \Gamma = \{ \mathbf{w} = (w_1, w_2, \dots, w_n) : w_i \in \{0, 1\} \}. $$
• The sigma algebra $\mathcal{A}$ is defined by the cylinder sets generated by the trajectories $\mathbf{w}$.

• In the CHSH game, the outcomes of future rounds can only depend upon the outcomes of previous rounds. The probability measure $P$ is thus a product measure, i.e., the probability of an outcome $\mathbf{w} = (w_1, w_2, \dots, w_n)$ is given by

$$P(\mathbf{w}) = p_1(w_1)p_2(w_2|w_1)p_3(w_3|w_2, w_1)\cdots p_n(w_n|w_{n-1}, \dots, w_1). \quad (E1)$$

We denote the set of such measures by $\mathfrak{P}$.

Let us also define for a given vector $\mu = [\mu_1, \mu_2, \dots, \mu_n] \in [0, 1]^n$ the set

$$\mathfrak{P}_{\mu} = \{ P \in \mathfrak{P} : p_1(1) \le \mu_1, p_2(1|w_1) \le \mu_2, \dots, p_n(1|w_{n-1}, \dots, w_1) \le \mu_n \quad \forall w_1, \dots, w_{n-1} \in \{0, 1\} \}. \quad (E2)$$

We further define the product probability distribution $P_{\mu}^* \in \mathfrak{P}_{\mu}$, given by

$$P_{\mu}^{*}(\mathbf{w}) = p_{1}^{*}(w_{1})p_{2}^{*}(w_{2})\cdots p_{n}^{*}(w_{n}), \quad (E3)$$

where

$$p_{i}^{*}(1) = \mu_{i}. \quad (E4)$$

Now, consider the following claim.

**Lemma 9.** Let $c \in \mathbb{N}$ be any non-zero natural number. Let $\Omega$ be the event defined by

$$\Omega = \{ \mathbf{w} \in \Gamma : \sum_{i=1}^{n} w_i \ge c \}. \quad (E5)$$

Then for any fixed $\mu \in [0, 1]^n$,

$$\max_{P \in \mathfrak{P}_{\mu}} P(\Omega) = P_{\mu}^{*}(\Omega). \quad (E6)$$

*Proof.* Define for any positive integers $k$ and $m$ satisfying $k \le m \le n$,

$$\Omega_k^m := \{ \mathbf{w} \in \Gamma : \sum_{i=1}^{m} w_i \ge k \}. \quad (E7)$$

This is the set of trajectories $\mathbf{w}$ (of length $n$) for which the total number of wins (that is, the total number of instances when $w_i = 1$) up to round $m$ is at least $k$. Now, suppose for a fixed $\mu$, $P \in \mathfrak{P}_{\mu}$. We then have the following recursion,

$$P(\Omega_k^m) = P(\Omega_k^{m-1}) + \sum_{\substack{\mathbf{w} \in \Gamma \text{ s.t.} \\ \sum_{i=1}^{m-1} w_i = k-1, \\ w_m=1}} P(\mathbf{w}). \quad (E8)$$

This follows from the fact that strings $\mathbf{w}$ achieving a sum of at least $k$ at round $m$ fall into one of two distinct cases.

**Case 1:** Strings $\mathbf{w}$ which have already achieved a sum of at least $k$ by round $m-1$, i.e., $\sum_{i=1}^{m-1} w_i \ge k$.

**Case 2:** Strings $\mathbf{w}$ which achieve a sum of exactly $k-1$ by round $m-1$, i.e., $\sum_{i=1}^{m-1} w_i = k-1$, and then win round $m$, i.e., $w_m = 1$.

The two terms on the right hand side of Equation (E8) account of these cases, respectively. Note that $P(\Omega_k^{m-1})$ is independent of the distribution assigned to final random variable $W_m$, i.e., independent of $p_m(w_m|w_{m-1}, \dots, w_1)$. We can also expand the second term to obtain

$$\begin{align}
\sum_{\substack{\mathbf{w} \in \Gamma \text{ s.t.} \\ \sum_{i=1}^{m-1} w_i = k-1, \\ w_m=1}} P(\mathbf{w}) &= \sum_{\substack{\mathbf{w} \in \Gamma \text{ s.t.} \\ \sum_{i=1}^{m-1} w_i = k-1, \\ w_m=1}} p_1(w_1)p_2(w_2|w_1)\cdots p_{w_{m-1}}(w_{m-1}|w_{m-2}, \dots, w_1)p_{w_m}(1|w_{m-1}, \dots, w_1) \nonumber \\
&\le \sum_{\substack{\mathbf{w} \in \Gamma \text{ s.t.} \\ \sum_{i=1}^{m-1} w_i = k-1, \\ w_m=1}} p_1(w_1)p_2(w_2|w_1)\cdots p_{w_{m-1}}(w_{m-1}|w_{m-2}, \dots, w_1)\mu_m \tag{E9} \\
&= \sum_{\substack{\mathbf{w} \in \Gamma \text{ s.t.} \\ \sum_{i=1}^{m-1} w_i = k-1, \\ w_m=1}} p_1(w_1)p_2(w_2|w_1)\cdots p_{w_{m-1}}(w_{m-1}|w_{m-2}, \dots, w_1)p_m^*(1), \nonumber
\end{align}$$
where we used the fact that $P \in \mathfrak{P}_\mu$ for the inequality and the definition of $P_\mu^*$ for the second equality. We therefore see that probability distribution achieving the optimal value of the maximization $\max_{P \in \mathfrak{P}_\mu} P(\Omega_k^m)$ must satisfy

$$p_m(1|w_{m-1}, \dots, w_1) = p_m^*(1).$$

In particular, $P(\Omega) = P(\Omega_c^n)$, which implies the distribution maximizing the left hand side of Equation (E6) satisfies $p_n(w_n|w_{n-1}, \dots, w_1) = p_n^*(w_n)$. Restricting to distributions satisfying this, consider

$$
\begin{align*}
P(\Omega_c^n) &= \sum_{\substack{\mathbf{w} \in \Gamma \text{ s.t.} \\ \sum_{i=1}^n w_i \ge c}} p_1(w_1)p_2(w_2|w_1) \cdots p_n(w_n|w_{n-1}, \dots, w_1) \\
&= \sum_{z \in \{0,1\}} \sum_{\substack{\mathbf{w} \in \Gamma \text{ s.t.} \\ \sum_{i=1}^{n-1} w_i \ge c-z}} p_1(w_1)p_2(w_2|w_1) \cdots p_n(z|w_{n-1}, \dots, w_1) \tag{E10} \\
&= \sum_{z \in \{0,1\}} p_n^*(z) \sum_{\substack{\mathbf{w} \in \Gamma \text{ s.t.} \\ \sum_{i=1}^{n-1} w_i \ge c-z}} p_1(w_1)p_2(w_2|w_1) \cdots p_{n-1}(w_{n-1}|w_{n-2}, \dots, w_1) \\
&= \sum_{z \in \{0,1\}} p_n^*(z) P(\Omega_{c-z}^{n-1}).
\end{align*}
$$

Notice that, using Equation (E9) by setting $m = n - 1$ and $k = c - z$, the maximum of $P(\Omega_{c-z}^{n-1})$ occurs when $p_{n-1}(w_{n-1}|w_{n-2}, \dots, w_1) = p_{n-1}^*(w_1)$ for both values of $z$. By the same line of reasoning above, we therefore find the optimal distribution $P$ must satisfy this constraint, implying

$$P(\Omega_c^n) = \sum_{z_1, z_2 \in \{0,1\}} p_n^*(z_1) p_{n-1}^*(z_2) P(\Omega_{c-z_1-z_2}^{n-2}). \quad (E11)$$

We can keep iterating the above procedure, until we obtain

$$P(\Omega_c^n) = \sum_{\mathbf{z} \in \Gamma} P_{\mu}^{*}(\mathbf{z}) P(\Omega_{c-\sum_{i=1}^n z_i}^0), \quad (E12)$$

where

$$\Omega_{c-\sum_{i=1}^n z_i}^0 = \{ \mathbf{w} \in \Gamma : 0 \ge c - \sum_{i=1}^n z_i \} = \begin{cases} \Gamma & \text{if } \sum_{i=1}^n z_i \ge c, \\ \emptyset & \text{otherwise.} \end{cases} \quad (E13)$$

Thus $P(\Omega_{c-\sum_{i=1}^n z_i}^0) = 1$ if $\sum_{i=1}^n z_i \ge c$ and zero otherwise, implying

$$\sum_{\mathbf{z} \in \Gamma} P^*(\mathbf{z})_\mu P(\Omega_{c-\sum_{i=1}^n z_i}^0) = \sum_{\substack{\mathbf{z} \in \Gamma \text{ s.t.} \\ \sum_{i=1}^n z_i \ge c}} P_\mu^*(\mathbf{z}) = P_\mu^*(\Omega_c^n). \quad (E14)$$

We have therefore established

$$\max_{P \in \mathfrak{P}_\mu} P(\Omega) \le P_\mu^*(\Omega). \quad (E15)$$

The fact that $P_\mu^* \in \mathfrak{P}_\mu$ completes the proof. $\square$

We now state an immediate corollary for the particular case encountered in this work.

**Corollary 1.** For $i = 1, \dots, n$, let $\rho_i$ and $N_i$ be a sequence of states and channels which induce the binary CHSH variables $W_i$, as described in Section D 1. Let $\mu_i^\dagger$ be defined in Equation (D7) and $\hat{W}_i$ be independent binary random variables defined by $P(\hat{W}_i = 1) = \mu_i^\dagger$. Then for any $t \in \{1, \dots, n\}$,

$$P\left(\sum_{i \neq t}^{n} W_i \ge \lfloor (n-1)(\omega_{\#} - \kappa) \rfloor\right) \le P\left(\sum_{i \neq t}^{n} \hat{W}_i \ge \lfloor (n-1)(\omega_{\#} - \kappa) \rfloor\right). \quad (E16)$$
<figure><img src="image_13.png" /><figcaption>FIG. 11: Sketch of the method for computing lower bounds on singlet extractability. After all reductions, the problem becomes a single maximization that is not an SDP in general, but reduces to an SDP when two parameters (corresponding to the Bell test measurement observables) are fixed. This allows the optimization to be solved by discretizing the parameter space, with a controllable penalty that can be reduced by refining the grid.</figcaption></figure>

*Proof.* Let us relabel the string of $n-1$ binary variables $\mathbf{W} = \{W_i\}_{i \neq t}^n \equiv \{W_1, ..., W_m\}$ where $m = n-1$. They follow a distribution of the form

$$P(\mathbf{W}) = p_1(w_1)p_2(w_2|w_1) \cdots p_m(w_m|w_{m-1}, ..., w_1), \qquad (E17)$$

and by the definition of $\mu_i^\uparrow$, $P$ is a member of $\mathfrak{P}_{\mu^\uparrow}$, where $\mu_i^\uparrow = [\mu_1^\uparrow, ..., \mu_m^\uparrow]$. Let

$$\hat{\Omega} = \{ \mathbf{W} \in \{0,1\}^m : \sum_{i=1}^{m} W_i \geq \lfloor m(\omega_{\#} - \kappa) \rfloor \}. \qquad (E18)$$

Then

$$\mathbb{P}\left(\sum_{i \neq t}^{n} \frac{W_i}{n-1} \geq \omega_{\#} - \kappa\right) \leq P(\hat{\Omega}) \leq \max_{P' \in \mathfrak{P}_{\mu^{\uparrow}}} P'(\hat{\Omega}) = P_{\mu^{\uparrow}}^*(\hat{\Omega}) = \mathbb{P}\left(\sum_{i \neq t}^{n} \hat{W}_i \geq \lfloor (n-1)(\omega_{\#} - \kappa) \rfloor\right) \qquad (E19)$$

as desired, where the final equality follows from the fact that the random variables $\hat{W}_i$ are distributed according to $P_{\mu^\uparrow}^*$. $\square$

## Appendix F: Bounding the LOCC extractability

The objective of this section is to derive reliable lower bounds on the LOCC extractability, as discussed in Section 8 of the main text. We begin by mathematically defining the general problem, followed by a reduction to qubit strategies when working in Bell scenarios with two inputs and two outputs per party. We then present a numerical method to bound the extractability in this case.

### 1. Stating the problem

We begin with some definitions. Recall the bipartite Bell scenario described in the main text, in which two parties perform local measurements on an entangled state $\rho \in \mathcal{S}(\mathcal{H}_{Q_A} \otimes \mathcal{H}_{Q_B})$. Their binary inputs are labeled by $X = x$ and $Y = y$, and outputs by $A = a$ and $B = b$, respectively. We label the corresponding POVMs $\{\{M_{a|x}\}_{a \in \{0,1\}}\}_{x \in \{0,1\}}$ on $\mathcal{H}_{Q_A}$ and $\{\{N_{b|y}\}_{b \in \{0,1\}}\}_{y \in \{0,1\}}$ on $\mathcal{H}_{Q_B}$, which define the observables $\{A_x\}_{x \in \{0,1\}}$ and $\{B_y\}_{y \in \{0,1\}}$. We define

$$\mathcal{B}_{\omega} := \{ \rho \in \mathcal{S}(\mathcal{H}_{Q_A} \otimes \mathcal{H}_{Q_B}) : \exists \{A_x\}_x, \{B_y\}_y \text{ s.t. } \text{tr}[B\rho] \geq \omega \}, \qquad (F1)$$
where

$$B = \sum_{x,y} \gamma_{xy} (A_x \otimes B_y) \qquad (F2)$$

is a Bell operator with some real coefficients $\gamma_{xy}$. Let $C \in \{U, LO, LOSR, LOCC\}$ denote the set of unital, local, LOSR (local operations and shared randomness), LOCC and unital quantum channels from $S(H_{Q_A} \otimes H_{Q_B})$ to $S(C^d \otimes C^d)$, and $\psi^* = |\psi^*\rangle\langle\psi^*| \in S(C^d \otimes C^d)$ be a target state. We also write $S_2 = S(C^2 \otimes C^2)$ for the set of two-qubit states and denote by $C_2$ the set of channels (in the class $C$) from $S_2$ to itself, i.e., from qubits to qubits. We will also label a qubit system held by Alice by $\hat{Q}_A$, and similarly for Bob.

The problem we wish to solve takes the form

$$\Xi_B^C(\omega) = \inf_{\rho \in \mathcal{B}_\omega} \sup_{\Lambda \in \mathcal{C}} F(\Lambda(\rho), \psi^*), \qquad (F3)$$

Note that since $\psi^*$ is pure, we can use the identity $F(\Lambda(\rho), \psi^*) = \text{tr}[\Lambda(\rho)\psi^*]$.

## 2. Reduction to qubits

We now apply Jordan's lemma to reduce the problem to qubits.

**Lemma 10 (Jordan's lemma [57]).** Let $A_0, A_1$ be two binary observables on a Hilbert space $\mathcal{H}$. Then there exists a basis for which $\mathcal{H}$ can be decomposed block diagonally into subspaces with dimension $\le 2$, where each subspace is preserved by $A_0, A_1$.

This allows us to perform the following reduction (see, e.g., [10, 30] for details). We define the set of two-qubit states which can achieve a Bell value $\omega$ below:

$$\mathcal{B}_{2,\omega} = \{ \rho \in \mathcal{S}_2 : \exists (a,b) \in [0, \pi/2] \times [0, \pi/2] \text{ s.t. } \text{tr}[B(a,b)\rho] \ge \omega \}, \qquad (F4)$$

where $B(a, b)$ is the Bell operator $B$ constructed from the qubit observables

$$A_x = \cos(a) \sigma_Z + (-1)^x \sin(a) \sigma_X, \quad B_y = \cos(b) \sigma_Z + (-1)^y \sin(b) \sigma_X. \qquad (F5)$$

**Lemma 11.** Let $B$ be a Bell operator in the bipartite minimal Bell scenario. Then the following inequality holds:

$$\Xi_B^{\text{LOCC}}(\omega) \ge \tilde{f}(\omega), \qquad (F6)$$

where $\tilde{f}(\omega)$ is any convex lower bound on the qubit LO extractability,

$$f_2(\omega) := \inf_{\rho \in \mathcal{B}_{2,\omega}} \sup_{\Lambda \in \mathcal{LO}_2} \text{tr}[\Lambda(\rho)\phi]. \qquad (F7)$$

We refer to the function $f_2(\omega)$ as the singlet fidelity [54].

*Proof.* Applying Lemma 10 to $\mathcal{H}_{Q_A}$ and $\mathcal{H}_{Q_B}$, we can write

$$A_x = \sum_{\alpha} A_x^{(\alpha)} \otimes |\alpha\rangle\langle\alpha|_{F_A}, \quad B_y = \sum_{\beta} B_y^{(\beta)} \otimes |\beta\rangle\langle\beta|_{F_B}. \qquad (F8)$$

Above, we introduced flag registers $F_A$ and $F_B$, and qubit registers $\hat{Q}_A$ and $\hat{Q}_B$, such that $\mathcal{H}_{Q_A} = \mathcal{H}_{\hat{Q}_A} \otimes \mathcal{H}_{F_A}$ and $\mathcal{H}_{Q_B} = \mathcal{H}_{\hat{Q}_B} \otimes \mathcal{H}_{F_B}$. Without loss of generality, we can apply local unitaries to each block such that each qubit measurement is real and lies in the $Z-X$ plane of the Bloch sphere [10], that is

$$A_x^{(\alpha)} = \cos(a_\alpha) \sigma_Z + (-1)^x \sin(a_\alpha) \sigma_X, \quad \text{and} \quad B_y^{(\beta)} = \cos(b_\beta) \sigma_Z + (-1)^y \sin(b_\beta) \sigma_X, \qquad (F9)$$

for some $a_\alpha, b_\beta \in (0, \pi/2]$. The Bell operator $B$ then decomposes,

$$B = \sum_{\alpha, \beta} B^{(\alpha, \beta)} \otimes |\alpha\rangle\langle\alpha|_{F_A} \otimes |\beta\rangle\langle\beta|_{F_B}. \qquad (F10)$$
We denote a generic state $\rho \in S(H_{QA} \otimes H_{QB})$ by

$$ \rho = \sum_{\alpha, \alpha', \beta, \beta'} \rho^{(\alpha, \alpha'), (\beta, \beta')} \otimes |\alpha\rangle\langle\alpha'|_{F_A} \otimes |\beta\rangle\langle\beta'|_{F_B}, \quad (F11) $$

and write $\rho^{(\alpha,\beta)} = p_{\alpha,\beta}\hat{\rho}^{(\alpha,\alpha),(\beta,\beta)}$, where $p_{\alpha,\beta} = \text{tr}[\rho^{(\alpha,\alpha),(\beta,\beta)}]$ and $\hat{\rho}^{(\alpha,\alpha),(\beta,\beta)} = \rho^{(\alpha,\alpha),(\beta,\beta)}/p_{\alpha,\beta}$. We then consider the following LOCC channel:

$$ \Lambda = \mathcal{M} \circ \Pi, \quad (F12) $$

where $\Pi: S(H_{QA} \otimes H_{QB}) \to S(H_{\hat{Q}_A} \otimes H_{\hat{Q}_B} \otimes H_C)$,

$$ \Pi(\sigma_{\hat{Q}_A \hat{Q}_B F_A F_B}) = \sum_{\alpha, \beta} (\mathbb{I}_4 \otimes \langle \alpha |_{F_A} \otimes \langle \beta |_{F_B}) \sigma(\mathbb{I}_4 \otimes | \alpha \rangle_{F_A} \otimes | \beta \rangle_{F_B}) \otimes | \alpha, \beta \rangle \langle \alpha, \beta |_C \quad (F13) $$

and $\mathcal{N}: S(H_{\hat{Q}_A} \otimes H_{\hat{Q}_B} \otimes H_C) \to S(H_{\hat{Q}_A} \otimes H_{\hat{Q}_B})$,

$$ \mathcal{M}(\tau_{\hat{Q}_A \hat{Q}_B C}) = \sum_{\alpha, \beta} \sum_k (E_k^{(\alpha, \beta)} \otimes \langle \alpha, \beta |) \tau(E_k^{(\alpha, \beta)\dagger} \otimes | \alpha, \beta \rangle). \quad (F14) $$

Above, $\{E_k^{(\alpha,\beta)}\}_k$ are the Kraus operators of a quantum channels $\Lambda^{(\alpha,\beta)} \in \text{LO}_2$, i.e., $\Lambda^{(\alpha,\beta)}(\rho_{\hat{Q}_A \hat{Q}_B}) = \sum_k E_k^{(\alpha,\beta)} \rho_k E_k^{(\alpha,\beta)\dagger}$. Note that the register C is shared by both devices, i.e., $\Pi$ is not a local channel. It is however an LOCC channel, since it can be performed by both devices measuring $F_A$ and $F_B$, and communicating the results. Applied to a state of the form (F11), we find

$$ \Lambda(\rho) = \sum_{\alpha, \beta} p_{\alpha, \beta} \Lambda^{(\alpha, \beta)}(\hat{\rho}^{(\alpha, \beta)}), \quad (F15) $$

which implies

$$ \begin{aligned} \Xi_B^{\text{LOCC}}(\omega) &= \inf_{\substack{\rho, \{A_x^{(\alpha)}, B_y^{(\beta)}\}_{\alpha,\beta, x,y} \\ \text{s.t. } \sum_{\alpha,\beta} p_{\alpha,\beta} \text{tr}[B^{(\alpha,\beta)} \hat{\rho}^{(\alpha,\beta)}] \ge \omega}} \sup_{\Lambda \in \text{LOCC}} \text{tr}[\Lambda(\rho)\psi^*] \\ &\ge \inf_{\substack{\hat{\rho}^{(\alpha,\beta)}, p_{\alpha,\beta}, A_x^{(\alpha)}, B_y^{(\beta)} \\ \text{s.t. } \sum_{\alpha,\beta} p_{\alpha,\beta} \text{tr}[B^{(\alpha,\beta)} \hat{\rho}^{(\alpha,\beta)}] \ge \omega}} \sum_{\alpha,\beta} p_{\alpha,\beta} \sup_{\Lambda^{(\alpha,\beta)} \in \text{LO}_2} \text{tr}[\Lambda^{(\alpha,\beta)}(\hat{\rho}^{(\alpha,\beta)})\psi^*]. \end{aligned} \quad (F16) $$

Let $\omega_{\alpha,\beta} = \text{tr}[B^{(\alpha,\beta)}\hat{\rho}^{(\alpha,\beta)}]$, and $g(\rho) = \sup_{\Lambda \in \text{LO}_2} \text{tr}[\Lambda(\rho)\psi^*]$. We then have

$$ \begin{aligned} \inf_{\substack{\{\hat{\rho}^{(\alpha,\beta)}, p_{\alpha,\beta}, A_x^{(\alpha)}, B_y^{(\beta)}\}_{\alpha,\beta} \\ \text{s.t. } \sum_{\alpha,\beta} p_{\alpha,\beta} \text{tr}[B^{(\alpha,\beta)} \hat{\rho}^{(\alpha,\beta)}] \ge \omega}} \sum_{\alpha,\beta} p_{\alpha,\beta} g(\hat{\rho}^{(\alpha,\beta)}) = & \inf_{\substack{\{\omega_{\alpha,\beta}, p_{\alpha,\beta}\}_{\alpha,\beta} \\ \text{s.t. } \sum_{\alpha,\beta} p_{\alpha,\beta} \omega_{\alpha,\beta} \ge \omega}} \sum_{\alpha,\beta} p_{\alpha,\beta} \inf_{\rho \in \mathcal{B}_2(\omega_{\alpha,\beta})} g(\rho). \end{aligned} \quad (F17) $$

Let

$$ f_2(\omega) = \inf_{\rho \in \mathcal{B}_{2,\omega}} g(\rho) \quad (F18) $$

be the qubit LO extractability, and $\tilde{f}_2(\omega)$ be any convex function satisfying $f_2(\omega) \ge \tilde{f}(\omega)$ for all $\omega$. Then

$$ \begin{aligned} \inf_{\substack{\{\omega_{\alpha,\beta}, p_{\alpha,\beta}\}_{\alpha,\beta} \\ \text{s.t. } \sum_{\alpha,\beta} p_{\alpha,\beta} \omega_{\alpha,\beta} \ge \omega}} \sum_{\alpha,\beta} p_{\alpha,\beta} \inf_{\rho \in \mathcal{B}_2(\omega_{\alpha,\beta})} g(\rho) &= \inf_{\substack{\{\omega_{\alpha,\beta}, p_{\alpha,\beta}\}_{\alpha,\beta} \\ \text{s.t. } \sum_{\alpha,\beta} p_{\alpha,\beta} \omega_{\alpha,\beta} \ge \omega}} \sum_{\alpha,\beta} p_{\alpha,\beta} f_2(\omega_{\alpha,\beta}) \\ &\ge \inf_{\substack{\{\omega_{\alpha,\beta}, p_{\alpha,\beta}\}_{\alpha,\beta} \\ \text{s.t. } \sum_{\alpha,\beta} p_{\alpha,\beta} \omega_{\alpha,\beta} \ge \omega}} \tilde{f}\left(\sum_{\alpha,\beta} p_{\alpha,\beta} \omega_{\alpha,\beta}\right) \quad (F19) \\ &\ge \tilde{f}(\omega), \end{aligned} $$

completing the proof. □
### 3. Bounds on the singlet fidelity

In this section, we provide bounds on the singlet fidelity under local channels, $f_2(\omega)$, for the case $\psi^* = \phi^+$. We begin with the following lemmas, which allow us to reduce the problem. Consider writing

$$ \mathrm{tr}[\Lambda(\rho)\phi^+] = \langle\Lambda(\rho), \phi^+\rangle = \langle\rho, \Lambda^\dagger(\phi^+)\rangle = \mathrm{tr}[\rho\Lambda^\dagger(\phi^+)], \qquad (\mathrm{F}20) $$

where $\langle A, B \rangle = \mathrm{tr}[A^\dagger B]$ is the Hilbert Schmidt norm, and $\Lambda^\dagger$ is the adjoint channel of $\Lambda$.

**Lemma 12.** Let $\Lambda_A : S(H_A) \to S(H_A)$ and $\Lambda_B : S(H_B) \to S(H_B)$ be quantum channels and $\rho \in S(H_A \otimes H_B)$. Then

$$ \mathrm{tr}_A[\Lambda_A \otimes \Lambda_B(\rho)] = \Lambda_B(\rho_B), \quad \text{and} \quad \mathrm{tr}_B[\Lambda_A \otimes \Lambda_B(\rho)] = \Lambda_A(\rho_A). \qquad (\mathrm{F}21) $$

*Proof.* This fact is a consequence of the product channel strucuture. Let $\{K_A^i\}_i$ be a set of Kraus operators for $\Lambda_A$, and $\{K_B^j\}_j$ be a set of Kraus operators for $\Lambda_B$. Then we have

$$ \begin{aligned} \mathrm{tr}_A[\Lambda_A \otimes \Lambda_B(\rho)] &= \sum_{i,j} \mathrm{tr}_A[(K_A^i \otimes K_B^j)\rho(K_A^i \otimes K_B^j)^\dagger] \\ &= \sum_j \mathrm{tr}_A\left[\left(\sum_i (K_A^i)^\dagger K_A^i \otimes K_B^j\right)\rho(\mathbb{I}_A \otimes K_B^j)^\dagger\right] \qquad (\mathrm{F}22) \\ &= \sum_j K_B^j \rho_B(K_B^j)^\dagger = \Lambda_B(\rho_B), \end{aligned} $$

where for the second equality we used that the partial trace is cyclic, and for the third we used the identities $\sum_i (K_A^i)^\dagger K_A^i = \mathbb{I}_A$ and $\mathrm{tr}_A[(\mathbb{I}_A \otimes Y_B)X_{AB}(\mathbb{I}_A \otimes Y_B)^\dagger] = Y_B \mathrm{tr}_A[X_{AB}]Y_B^\dagger$. The analogous statement holds when tracing out system B. $\square$

This allows us to show the following.

**Lemma 13.** Let $\Lambda \in \mathcal{LO}_2 \cap \mathcal{U}_2$ be a local, unital quantum channel. Then the state $\sigma = \Lambda^\dagger(\phi^+)$ is Bell diagonal in some basis, i.e., it satisfies

$$ \mathrm{tr}_{\hat{Q}_A}[\sigma] = \mathrm{tr}_{\hat{Q}_B}[\sigma] = \mathbb{I}_2/2. \qquad (\mathrm{F}23) $$

*Proof.* Let $\Lambda = \Lambda_A \otimes \Lambda_B$ where $\Lambda_A(\mathbb{I}_2) = \Lambda_B(\mathbb{I}_2) = \mathbb{I}_2$. This implies that both $\Lambda_A^\dagger$ and $\Lambda_B^\dagger$ are quantum channels. We can therefore apply Lemma 12,

$$ \mathrm{tr}_{\hat{Q}_A}[\sigma] = \mathrm{tr}_{\hat{Q}_A}[\Lambda_A^\dagger \otimes \Lambda_B^\dagger(\phi^+)] = \Lambda_B^\dagger(\mathbb{I}_2/2) = \mathbb{I}_2/2, \qquad (\mathrm{F}24) $$

where for the last line we used that $\Lambda^\dagger$ is unital. The analogous statement holds when tracing out system $\hat{Q}_B$. $\square$

We denote the set of Bell diagonal states, i.e., two-qubit states that satisfy Equation (F23), $BD$. We next prove the converse statement.

**Lemma 14.** For every state $\sigma \in BD$, there exist unital channels $\Lambda_A : S(\mathbb{C}^2) \to S(\mathbb{C}^2)$ and $\Lambda_B : S(\mathbb{C}^2) \to S(\mathbb{C}^2)$ such that

$$ \Lambda_A^\dagger \otimes \Lambda_B^\dagger(\phi^+) = \sigma. \qquad (\mathrm{F}25) $$

*Proof.* Suppose $\sigma$ is Bell diagonal, i.e., there exists a Bell basis $\{\tilde{\Phi}_\alpha\}_{\alpha=0}^3$ and a distribution $\{\lambda_\alpha\}_{\alpha=0}^3$ such that

$$ \sigma = \sum_{\alpha} \lambda_{\alpha} \tilde{\Phi}_{\alpha}. \qquad (\mathrm{F}26) $$
Define the channel $\tilde{\Lambda}_A$ by the following Kraus operators

$$
\begin{align}
E_0 &= \sqrt{\lambda_0} \mathbb{I}, \nonumber \\
E_1 &= \sqrt{\lambda_1} \sigma_Z \sigma_X, \nonumber \\
E_2 &= \sqrt{\lambda_2} \sigma_Z, \nonumber \\
E_3 &= \sqrt{\lambda_3} \sigma_X. \tag{F27}
\end{align}
$$

Note that $\tilde{\Lambda}_A$ is unital, equal to its adjoint, and

$$
\sum_i (E_i \otimes \mathbb{I}_2) \phi^+(E_i \otimes \mathbb{I}_2) = \sum_\alpha \lambda_\alpha \Phi_\alpha, \qquad (\text{F28})
$$

where {$\Phi_{\alpha}$}$_{α}$ is the standard Bell basis, $\Phi_0 = \phi^+$, $\Phi_1 = \psi^-$, $\Phi_2 = \phi^-$ and $\Phi_3 = \psi^+$, where $|\phi^{\pm}\rangle = (|00\rangle \pm |11\rangle)/\sqrt{2}$ and $|\psi^{\pm}\rangle = (|01\rangle \pm |10\rangle)/\sqrt{2}$. Let $U_A \otimes U_B$ be the local unitary which rotates the standard Bell basis $\{\tilde{\Phi}_{\alpha}\}_{\alpha=0}^3$, i.e.,

$$
(U_A \otimes U_B) \left( \sum_{\alpha} \lambda_{\alpha} \Phi_{\alpha} \right) (U_A \otimes U_B)^{\dagger} = \sum_{\alpha} \lambda_{\alpha} \tilde{\Phi}_{\alpha} = \sigma. \qquad (\text{F29})
$$

Define the unital channels

$$
\Lambda_A(\rho) = \tilde{\Lambda}_A(U_A^\dagger \rho U_A), \quad \text{and} \quad \Lambda_B(\tau) = U_B^\dagger \tau U_B. \tag{F30}
$$

We then have

$$
\Lambda_A^\dagger \otimes \Lambda_B^\dagger (\phi^+) = \sum_i (U_A \otimes U_B)(E_i \otimes \mathbb{I}_2)\phi^+(E_i \otimes \mathbb{I}_2)(U_A \otimes U_B)^\dagger = \sigma, \quad (\text{F31})
$$

as desired.

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

By combining Lemmas 13 and 14, we arrive at the following reduction.

**Corollary 2.** Let $\rho \in S_2$ be an arbitrary two-qubit state. Then following equality holds:

$$
\sup_{\Lambda \in \mathcal{L}O_2 \cap U_2} \operatorname{tr}[\rho \Lambda^{\dagger}(\phi^{+})] = \sup_{\sigma \in \mathcal{BD}} \operatorname{tr}[\rho \sigma]. \qquad (\text{F32})
$$

Proof. Let

$$
S = \{ \Lambda^{\dagger}(\phi^{+}) : \Lambda \in \mathcal{LO}_{2} \cap \mathcal{U}_{2} \}. \qquad (\text{F33})
$$

Then by Lemma 13, we know $S \subseteq \mathcal{BD}$, and by Lemma 14, we know $\mathcal{BD} \subseteq S$. We therefore have $S = \mathcal{BD}$, proving the claim. $\square$

Having lower bounded the maximization over local channels by a maximization over states, we now show how, given for fixed pair of measurement angles $a, b \in \mathbb{R}$, the function $f_2(\omega)$ can be bounded by an SDP.

**Lemma 15.** *Define the function*

$$
\begin{align*}
f_{a,b}(\omega) &:= \max_{\lambda,\mu,\sigma} \lambda \omega + \mu \\
\text{s.t.} \quad & \sigma - \lambda B(a,b) - \mu \mathbb{I}_4 \ge 0 \\
& \mathrm{tr}_{\hat{Q}_A}[\sigma] = \frac{\mathbb{I}_2}{2} \tag{F34} \\
& \mathrm{tr}_{\hat{Q}_B}[\sigma] = \frac{\mathbb{I}_2}{2} \\
& \sigma \in S_2, \lambda \ge 0, \mu \in \mathbb{R}.
\end{align*}
$$

Then

$$
f_2(\omega) \ge \min_{(a,b) \in \mathcal{F}_{\omega}} f_{a,b}(\omega), \qquad (\text{F35})
$$

where $\mathcal{F}_{\omega} = \{(a,b) \in [0, \pi/2] \times [0, \pi/2] : \exists \rho \in S_2 \text{ s.t. } \mathrm{tr}[B(a,b)\rho] \ge \omega\}$.
Proof. We first employ the bound $f_2(\omega) = \inf_{\rho \in \mathcal{B}_{2,\omega}} \sup_{\Lambda \in \mathcal{L}_{0,2}} \mathrm{tr}[\Lambda(\rho)\phi] \ge \inf_{\rho \in \mathcal{B}_{2,\omega}} \sup_{\Lambda \in \mathcal{L}_{0,2} \cap U_2} \mathrm{tr}[\Lambda(\rho)\phi]$. Then, by applying Corollary 2, we have

$$
\begin{align*}
f_2(\omega) &\ge \inf_{\rho \in \mathcal{B}_{2,\omega}} \sup_{\sigma \in \mathcal{B}^D} \mathrm{tr}[\rho\sigma] \\
&= \min_{\rho \in \mathcal{B}_{2,\omega}} \max_{\sigma \in \mathcal{B}^D} \mathrm{tr}[\rho\sigma] \tag{F36} \\
&= \min_{(a,b) \in \mathcal{F}_{\omega}} \min_{\rho \in \mathcal{B}_{\omega}^{a,b}} \mathrm{tr}[\rho\sigma] \\
&= \min_{(a,b) \in \mathcal{F}_{\omega}} \max_{\sigma \in \mathcal{B}^D} \min_{\rho \in \mathcal{B}_{\omega}^{a,b}} \mathrm{tr}[\rho\sigma],
\end{align*}
$$

where $\mathcal{B}_{\omega}^{a,b}$ is the set of two-qubit states which can achieve a Bell value of $\omega$ with measurement angles $a, b$, i.e.,

$$ \mathcal{B}_{\omega}^{a,b} = \{ \rho \in \mathcal{S}_2 : \mathrm{tr}[B(a,b)\rho] \ge \omega \}. \qquad (F37) $$

In Equation (F36), we used the following facts:

1. The set $\mathcal{B}_{2,\omega}$ defined in Equation (F4) is compact. For proof see Claim 1.

2. The set $\mathcal{F}_{\omega}$ defined in the lemma statement is compact. For proof see Claim 2.

3. The sets $\mathcal{B}_{\omega}^{a,b}$ and $\mathcal{BD}$ are compact and convex. This follows from the fact that any subset of $\mathcal{S}_2$ defined by linear constraints inherits the compactness and convexity of $\mathcal{S}_2$.

4. For any function $g: \mathcal{S}_2 \to \mathbb{R}$, the set $\mathcal{B}_{2,\omega}$ satisfies $\min_{\rho \in \mathcal{B}_{2,\omega}} g(\rho) = \min_{(a,b) \in \mathcal{F}_{\omega}} \min_{\rho \in \mathcal{B}_{\omega}^{a,b}} g(\rho)$. For proof see Claim 4.

5. The function $g(\rho, \sigma) = \mathrm{tr}[\rho\sigma]$ is linear in one of its arguments when the other is fixed.

The first equality in Equation (F36) then follows from point 1, allowing us to replace $\inf_{\rho \in \mathcal{B}_{2,\omega}}$ with $\min_{\rho \in \mathcal{B}_{2,\omega}}$, and point 3, allowing us to replace $\sup_{\sigma \in \mathcal{B}^D}$ with $\max_{\sigma \in \mathcal{B}^D}$. The second equality follows from point 4. The third equality follows from points 3 and 5, allowing us to apply von Neumann's minimax theorem [71].

Consider, for a fixed $\sigma \in \mathcal{BD}$, $\omega$ and $(a,b) \in [0, \pi/2] \times [0, \pi/2]$ such that $\mathcal{B}_{\omega}^{a,b}$ is non-empty, the optimization

$$
\begin{align}
& \min \mathrm{tr}[\rho\sigma] \nonumber \\
& \text{s.t.} \quad \mathrm{tr}[B(a,b)\rho] \ge \omega \tag{F38} \\
& \qquad \mathrm{tr}[\rho] = 1 \nonumber \\
& \qquad \rho \ge 0. \nonumber
\end{align}
$$

This has the dual (see, e.g., [72, Example 5.11])

$$
\begin{align}
& \max \lambda\omega + \mu \nonumber \\
& \text{s.t.} \quad \sigma - \lambda B(a, b) - \mu \mathbb{I}_4 \ge 0 \tag{F39} \\
& \qquad \lambda \ge 0 \nonumber \\
& \qquad \mu \in \mathbb{R}, \nonumber
\end{align}
$$

whose optimal value lower bounds that of the primal by weak duality. Furthermore, we proceed to show that strong duality holds. Consider the point $(\lambda, \mu) = (1, -\eta_2^Q - \epsilon)$ for any $\epsilon > 0$, where $\eta_2^Q$ is the maximum quantum value of the Bell functional $B$ for qubits, i.e.,

$$ \eta_2^Q = \sup_{\substack{\rho \in \mathcal{S}_2, \\ (a,b) \in [0, \pi/2] \times [0, \pi/2]}} \mathrm{tr}[B(a,b)\rho]. \qquad (F40) $$

The constraint $\sigma - \lambda B(a, b) - \mu \mathbb{I}_4 \ge 0$ is equivalent to

$$ \langle \psi | \sigma | \psi \rangle - \lambda \langle \psi | B(a, b) | \psi \rangle - \mu \ge 0, \quad \forall |\psi\rangle. \qquad (F41) $$

The point $(\lambda, \mu) = (1, -\eta_2^Q - \epsilon)$ satisfies $\lambda > 0$, and

$$
\begin{align}
& \langle \psi | \sigma | \psi \rangle - \lambda \langle \psi | B(a, b) | \psi \rangle - \mu = \langle \psi | \sigma | \psi \rangle - \langle \psi | B(a, b) | \psi \rangle + \eta_2^Q + \epsilon \nonumber \\
& \qquad \ge \epsilon \nonumber \\
& \qquad > 0, \tag{F42}
\end{align}
$$
where we used the fact that $\eta_2^Q \ge \langle \psi | B(a, b) | \psi \rangle$ for all measurements $(a, b)$ and states $|\psi\rangle$, and that $\langle \psi | \sigma | \psi \rangle \ge 0$. We have shown that the dual is strictly feasible, and therefore strong duality holds. Inserting Equation (F39) into Equation (F36) establishes the claim. $\square$

We provide proofs of the referenced claims below.

**Claim 1.** The set $\mathcal{B}_{2,\omega}$ defined in Equation (F4) is compact.

*Proof.* We first show $\mathcal{B}_{2,\omega}$ is closed. Let $K := [0, \frac{\pi}{2}] \times [0, \frac{\pi}{2}]$ and note that $(a, b) \mapsto B(a, b)$ is continuous (see Claim 3). Define

$$f(\rho) := \max_{(a,b) \in K} \mathrm{tr}[B(a,b)\rho].$$

The maximum is achievable because $K$ is compact and $(a, b) \mapsto B(a, b)$ is continuous.

Let $\{\rho_n\}_{n \in \mathbb{N}} \subset \mathcal{B}_{2,\omega}$ be a sequence of states and suppose $\rho_n \to \rho$ (in trace norm) as $n \to \infty$. For any $(a, b) \in K$ and any $\epsilon > 0$, there exists an $n \in \mathbb{N}$ such that

$$|\mathrm{tr}[B(a,b)\rho] - \mathrm{tr}[B(a,b)\rho_n]| \le \|B(a,b)\|_{\infty} \|\rho - \rho_n\|_1 \le c\epsilon,$$

where $c := \max_{(a,b) \in K} \|B(a,b)\|_{\infty}$ and for the first inequality we applied Hölder's inequality. This follows from the fact that $\|\rho - \rho_n\|_1 \to 0$ as $n \to \infty$. Since $\rho_n \in \mathcal{B}_{2,\omega}$, there exist $(a_n, b_n) \in K$ such that $\mathrm{tr}[B(a_n, b_n)\rho_n] \ge \omega$. Applying the above bound with the substitution $(a, b) \mapsto (a_n, b_n)$, for any $\epsilon > 0$ there exists an $n \in \mathbb{N}$ such that

$$\mathrm{tr}[B(a_n, b_n)\rho] \ge \omega - c\epsilon.$$

As this holds for every $\epsilon > 0$, it follows that $f(\rho) \ge \omega - \epsilon'$ for every $\epsilon' > 0$. Taking $\epsilon'$ to be arbitrarily small therefore implies $\rho \in \mathcal{B}_{2,\omega}$.

Finally, $\mathcal{B}_{2,\omega} \subset \mathcal{S}_2$ and the state space $\mathcal{S}_2$ is bounded, so $\mathcal{B}_{2,\omega}$ is a closed and bounded subset of a finite-dimensional space. Therefore, $\mathcal{B}_{2,\omega}$ is compact. $\square$

**Claim 2.** The set $\mathcal{F}_\omega$ defined in Lemma 15 is compact.

*Proof.* We follow an argument analogous to Claim 1.

Let $\{(a_n, b_n)\}_{n \in \mathbb{N}} \subset \mathcal{F}_\omega$ be a sequence and suppose the limit $(a_n, b_n) \to (a, b) \in [0, \pi/2]^2$ as $n \to \infty$ exists. By definition of $\mathcal{F}_\omega$, for each $n$ there exists $\rho_n \in \mathcal{S}_2$ such that

$$\mathrm{tr}[\rho_n B(a_n, b_n)] \ge \omega.$$

Define

$$\tilde{g}(a, b) := \max_{\rho \in \mathcal{S}_2} \mathrm{tr}[\rho B(a, b)].$$

The maximum exists (and is achievable) because $\mathcal{S}_2$ is compact and $(a, b) \mapsto B(a, b)$ is continuous (see Claim 3).

By Hölder's inequality,

$$|\mathrm{tr}[\rho_n B(a_n, b_n)] - \mathrm{tr}[\rho_n B(a, b)]| \le \|B(a_n, b_n) - B(a, b)\|_1 \cdot \|\rho_n\|_{\infty} \le \|B(a_n, b_n) - B(a, b)\|_1.$$

Continuity of $(a, b) \mapsto B(a, b)$ implies $\|B(a_n, b_n) - B(a, b)\|_1 \to 0$ as $n \to \infty$, so for every $\epsilon > 0$ there exists a large enough $n \in \mathbb{N}$ such that

$$\mathrm{tr}[\rho_n B(a, b)] \ge \mathrm{tr}[\rho_n B(a_n, b_n)] - \epsilon \ge \omega - \epsilon.$$

Since $\epsilon > 0$ can be arbitrarily small, we conclude

$$\tilde{g}(a, b) \ge \omega,$$

and hence $(a, b) \in \mathcal{F}_\omega$. Therefore, $\mathcal{F}_\omega$ is closed. The boundedness follows from the boundedness of the Bell operators $B(a, b)$. $\square$

**Claim 3.** The map $(a, b) \mapsto B(a, b)$ is continuous on $[0, \pi/2] \times [0, \pi/2]$, i.e.,

$$\lim_{(a', b') \to (a, b)} \|B(a', b') - B(a, b)\|_1 = 0.$$
**Proof.** Recall that $B(a, b)$ is constructed from tensor products of local operators $A_x(a)$ and $B_y(b)$, each acting on a qubit:

$$B(a, b) = \sum_{x,y} \gamma_{x,y} A_x(a) \otimes B_y(b),$$

where the coefficients $\gamma_{x,y}$ are fixed real constants, and $A_x(a), B_y(b)$ depend continuously on $a$ and $b$.

For any $(a', b') \in [0, \pi/2]^2$, we have

$$ \begin{aligned} \|B(a', b') - B(a, b)\|_1 &= \left\| \sum_{x,y} \gamma_{x,y} (A_x(a') - A_x(a)) \otimes B_y(b') + \sum_{x,y} \gamma_{x,y} A_x(a) \otimes (B_y(b') - B_y(b)) \right\|_1 \\ &\le \sum_{x,y} |\gamma_{x,y}| \|(A_x(a') - A_x(a)) \otimes B_y(b')\|_1 + \sum_{x,y} |\gamma_{x,y}| \|A_x(a) \otimes (B_y(b') - B_y(b))\|_1 \end{aligned} $$

using the triangle inequality.

Using the fact that $\|A \otimes B\|_1 = \|A\|_1 \|B\|_1$ and $A_x(a)^\dagger A_x(a) = B_y(b)^\dagger B_y(b) = \mathbb{I}_2$ (since $A_x(a)$ and $B_y(b)$ are the observables of a rank 1 projective measurement on a qubit),

$$ \|(A_x(a') - A_x(a)) \otimes B_y(b')\|_1 \le 2\|A_x(a') - A_x(a)\|_1, \quad \|A_x(a) \otimes (B_y(b') - B_y(b))\|_1 \le 2\|B_y(b') - B_y(b)\|_1. $$

Hence,

$$ \|B(a', b') - B(a, b)\|_1 \le \sum_{x,y} 2|\gamma_{x,y}| (\|A_x(a') - A_x(a)\|_1 + \|B_y(b') - B_y(b)\|_1). $$

Finally, each $A_x(a)$ and $B_y(b)$ is continuous in trace norm (for instance, $\|A_x(a') - A_x(a)\|_1 = \|(\cos(a') - \cos(a))\sigma_z + (-1)^x(\sin(a') - \sin(a))\sigma_x\|_1 \to 0$ as $a' \to a$, and similarly for $B_y(b)$), so the right-hand side tends to zero as $(a', b') \to (a, b)$. Therefore,

$$ \lim_{(a', b') \to (a, b)} \|B(a', b') - B(a, b)\|_1 = 0, $$

i.e., $B(a, b)$ is continuous in trace norm. $\square$

**Claim 4.** Let $g : S_2 \to \mathbb{R}$ be a function. The set $B_{2,\omega}$ defined in Equation (F4) satisfies $\min_{\rho \in B_{2,\omega}} g(\rho) = \min_{(a,b) \in \mathcal{F}_\omega} \min_{\rho \in B_{\omega}^{a,b}} g(\rho)$, where $B_{\omega}^{a,b}$ and $\mathcal{F}_\omega$ are defined in Equation (F37) and Lemma 15, respectively.

**Proof.** Since $B_{2,\omega}$ is compact by Claim 1, let $\rho^* \in B_{2,\omega}$ denote the optimal state that satisfies $\min_{\rho \in B_{2,\omega}} g(\rho) = g(\rho^*)$. By definition of $B_{2,\omega}$, there exists a pair of angles $(a^*, b^*)$ satisfying $\text{tr}[\rho^* B(a^*, b^*)] \ge \omega$. Hence $\rho^* \in B_{\omega}^{a^*, b^*}$ by the definition of $B_{\omega}^{a^*, b^*}$ in Equation (F37). We therefore have $g(\rho^*) \ge \min_{\rho \in B_{\omega}^{a^*, b^*}} g(\rho) \ge \inf_{(a,b) \in \mathcal{F}_\omega} \min_{\rho \in B_{\omega}^{a,b}} g(\rho)$, where the second inequality follows from the fact that $(a^*, b^*) \in \mathcal{F}_\omega$ as defined in Lemma 15. By Claim 2 $\inf_{(a,b) \in \mathcal{F}_\omega} \min_{\rho \in B_{\omega}^{a^*, b^*}} g(\rho) = \min_{(a,b) \in \mathcal{F}_\omega} \min_{\rho \in B_{\omega}^{a^*, b^*}} g(\rho)$, establishing the lower bound.

For the upper bound, note that the minimization $\min_{(a,b) \in \mathcal{F}_\omega} \min_{\rho \in B_{\omega}^{a^*, b^*}} g(\rho)$ is attained by some state $\tilde{\rho}$ and pair of angles $(\tilde{a}, \tilde{b})$ such that $\text{tr}[\tilde{\rho}B(\tilde{a}, \tilde{b})] \ge \omega$. Hence $\tilde{\rho} \in B_{2,\omega}$, and $\min_{\rho \in B_{2,\omega}} g(\rho) \le g(\tilde{\rho}) = \min_{(a,b) \in \mathcal{F}_\omega} \min_{\rho \in B_{\omega}^{a^*, b^*}} g(\rho)$, completing the proof. $\square$

**Remark 7.** The dual SDP in Equation (F34) is related to the “self-testing via operator inequalities” (STOI) approach first introduced in Ref. [10] (see also Refs. [28, 73, 74]). The STOI approach seeks to lower bound the fidelity under local channels, $F(\Lambda_A \otimes \Lambda_B(\rho), \phi^+) = \text{tr}[\rho(\Lambda_A \otimes \Lambda_B)^\dagger(\phi^+)]$, by establishing an operator inequality of the form $K \ge \lambda B(a, b) + \mu \mathbb{I}_4$, where $K = (\Lambda_A \otimes \Lambda_B)^\dagger(\phi^+)$, $\lambda \ge 0$, $\mu \in \mathbb{R}$ and the inequality holds for all $a, b$. This has the same form as the matrix positivity constraint in Equation (F34). Indeed, for the case of the CHSH inequality, the choice of dephasing channels from [10], which we denote $\Lambda_A = \Lambda_A^*(a)$, $\Lambda_B = \Lambda_B^*(b)$, along with the values $\lambda = \lambda^* = (4 + 5\sqrt{2})/16$, $\mu = \mu^* = -(1 + 2\sqrt{2})/4$, correspond to a feasible point $(\lambda, \mu, \sigma) = (\lambda^*, \mu^*, K(a, b))$ of the SDP in Equation (F34), where $K(a, b) = (\Lambda_A^*(a) \otimes \Lambda_B^*(b))^\dagger(\phi^+)$. $\square$
### 4. Solving the outer minimization via gridding

In the previous subsections, we showed that bounding the LOCC fidelity can be reduced to finding a lower bound on $inf_{(a,b) \in \mathcal{F}_{\omega}} f_{a,b}(\omega)$. In this subsection, we develop a generic approach based on evaluating the function $f_{a,b}(\omega)$ over a finite grid (see also [30, 75] for an application of this technique to generic optimization problems). Let $\mathcal{I} = \{0, 1, ..., |\mathcal{I}| - 1\}$ and

$$ \mathcal{G} = \{(a_j, b_j)\}_{j \in \mathcal{I}} \subset [0, \pi/2] \times [0, \pi/2] \qquad (\text{F43}) $$

be a finite grid over $[0, \pi/2] \times [0, \pi/2]$ with a spacing $|a_i - a_{i+1}| = |b_i - b_{i+1}| = \delta > 0$, containing $|\mathcal{I}|$ points. Consider the region inside a square of length $2\delta$ centered on the point $(a_j, b_j) \in \tilde{G}(\omega)$:

$$ S_j := \{(a_j + \delta(1 - 2\lambda_0), b_j + \delta(1 - 2\lambda_1)) : \lambda_0, \lambda_1 \in [0, 1]\}. \qquad (\text{F44}) $$

We will now upper bound the maximum value of the function $f_{a,b}(\omega)$ for $(a, b) \in S_j$ when the Bell operator $B(a, b)$ admits a first order expansion.

**Lemma 16.** Suppose, for all $(a, b), (a^*, b^*) \in \mathcal{F}_{\omega}$,

$$ \mathrm{tr}[B(a, b)\rho] \le \mathrm{tr}[B(a^*, b^*)\rho] + c_0(a - a^*) + c_1(b - b^*) \qquad (\text{F45}) $$

for some constants $c_0, c_1 \ge 0$. Then for any $(a', b') \in \mathcal{F}_{\omega} \cap S_j$,

$$ \mathcal{B}_{a',b'}^{\omega} \subset \tilde{\mathcal{B}}_{j}^{\omega} := \{ \rho \in S_2 : \mathrm{tr}[B(a_j, b_j)\rho] \ge \omega - \delta(c_0 + c_1) \}. \qquad (\text{F46}) $$

*Proof.* Take any $\rho \in \mathcal{B}_{a',b'}^{\omega}$ for $(a', b') \in \mathcal{F}_{\omega} \cap S_j$ (note $(a', b') \in \mathcal{F}_{\omega}$ implies $\mathcal{B}_{a',b'}^{\omega}$ is non-empty). Then we know $\mathrm{tr}[B(a', b')\rho] \ge \omega$, and there exists constants $\lambda_0, \lambda_1 \in [0, 1]$ such that

$$ a' = a_j + \delta(1 - 2\lambda_0) \quad \text{and} \quad b' = b_j + \delta(1 - 2\lambda_1). \qquad (\text{F47}) $$

We then have by Equation (F45), choosing $a^* = a_j$ and $b^* = b_j$,

$$ \omega \le \mathrm{tr}[B(a', b')\rho] \le \mathrm{tr}[B(a_j, b_j)\rho] + c_0(a' - a_j) + c_1(b' - b_j) = \mathrm{tr}[B(a_j, b_j)\rho] + \delta(1 - 2\lambda_0)c_0 + \delta(1 - 2\lambda_1)c_1. \qquad (\text{F48}) $$

Rearranging, we see

$$ \mathrm{tr}[B(a_j, b_j)\rho] \ge \omega - \delta(1 - 2\lambda_0)c_0 - \delta(1 - 2\lambda_1)c_1 \ge \omega - \delta(c_0 + c_1), \qquad (\text{F49}) $$

where for the second inequality we took $\lambda_0, \lambda_1 \ge 0$. As a result, $\rho \in \mathcal{B}_j(\omega)$ as desired. $\square$

As a consequence, for all $(a', b') \in S_j$ and any function $f: S_2 \to \mathbb{R}$,

$$ \min_{(a,b) \in \mathcal{F}} \min_{\rho \in \mathcal{B}_{\omega}^{a,b}} f(\rho) = \min_{j \in \mathcal{I}} \min_{(a',b') \in S_j} \min_{\rho \in \mathcal{B}_{a',b'}^{\omega}} f(\rho) \ge \min_{j \in \mathcal{I}} \min_{\rho \in \mathcal{B}_{j}^{\omega}} f(\rho). \qquad (\text{F50}) $$

To apply Lemma 16 we require a linear approximation to the Bell operator $B(a, b)$.

**Lemma 17.** Let $A_x = \cos(a) \sigma_Z + (-1)^x \sin(a) \sigma_X$ and $B_y = \cos(b) \sigma_Z + (-1)^y \sin(b) \sigma_X$ be qubit observables parameterized by $(a, b) \in [0, \pi/2] \times [0, \pi/2]$. Let $B(a, b)$ be an arbitrary Bell operator

$$ B(a, b) = \sum_{x \in \{0,1\}} c_x^A (A_x \otimes \mathbb{I}_{\hat{Q}_B}) + \sum_{y \in \{0,1\}} c_y^B (\mathbb{I}_{\hat{Q}_A} \otimes B_y) + \sum_{x,y \in \{0,1\}} c_{x,y}^{AB} (A_x \otimes B_y), \qquad (\text{F51}) $$

with coefficients $c_x^A, c_y^B, c_{xy}^{AB} \in \mathbb{R}$. Then for all $\rho \in S_2$ and $(a', b'), (a, b) \in [0, \pi/2] \times [0, \pi/2]$,

$$ \mathrm{tr}[B(a', b')\rho] \le \mathrm{tr}[B(a, b)\rho] + c_0(a' - a) + c_1(b' - b), \qquad (\text{F52}) $$

where

$$ \begin{align} c_0 &= \sum_{x \in \{0,1\}} |c_x^A| + \sum_{x,y \in \{0,1\}} |c_{x,y}^{AB}|, \quad \text{and} \nonumber \\ c_1 &= \sum_{y \in \{0,1\}} |c_y^B| + \sum_{x,y \in \{0,1\}} |c_{x,y}^{AB}|. \tag{F53} \end{align} $$
Proof. Let $O(\theta) = \cos(\theta) \sigma_Z + \sin(\theta) \sigma_X$ be an arbitrary qubit observable in the ZX plane of the Bloch sphere, parameterized by an angle $\theta \in [-\pi, \pi]$. Let $\delta \in [-\pi/2, \pi/2]$. By direct calculation,

$$ \|O(\theta) - O(\theta + \delta)\|_{\infty} = 2|\sin(\delta/2)| \le |\delta|, \qquad (F54) $$

where $\|A\|_{\infty}$ is the norm of an operator $A$ on a Hilbert space $\mathcal{H}$, equal to its largest eigenvalue. Similarly, for $\delta_0, \delta_1 \in [-\pi/2, \pi/2]$,

$$ \begin{aligned} \|O(\theta) \otimes O(\phi) - O(\theta + \delta_0) \otimes O(\phi + \delta_1)\|_{\infty} &= \sqrt{2|\sin(\delta_0)\sin(\delta_1)| + 2(1 - \cos(\delta_0)\cos(\delta_1))} \\ &= 2|\sin(\frac{\delta_0 \pm \delta_1}{2})| \le |\delta_0 + \delta_1|, \end{aligned} \qquad (F55) $$

where we used the fact that $|\sin(\delta_0)\sin(\delta_1)| = \pm \sin(\delta_0)\sin(\delta_1)$ depending on the values of $\delta_0, \delta_1$, and applied relevant trigonometric identities. The Bell operator $B(a, b)$ is given by

$$ B(a, b) = \sum_x c_x^A (O((-1)^x a] \otimes \mathbb{I}) + \sum_y c_y^B (\mathbb{I} \otimes O((-1)^y b]) + \sum_{x,y} c_{x,y}^{AB} (O((-1)^x a] \otimes O((-1)^y b]). \qquad (F56) $$

Let us define, for $\delta_0, \delta_1 > 0$,

$$ \Delta := B(a, b) - B(a + \delta_0, b + \delta_1). \qquad (F57) $$

Note for any $\rho \in S_2$ with a spectral decomposition $\rho = \sum_i p_i |\phi_i\rangle\langle\phi_i|$,

$$ |\mathrm{tr}[\Delta\rho]| \le \sum_i p_i |\langle\phi_i|\Delta|\phi_i\rangle| \le \|\Delta\|_{\infty}. \qquad (F58) $$

We now bound the operator norm of $\Delta$ by repeatedly applying the triangle inequality, to find

$$ \begin{aligned} \|\Delta\|_{\infty} &\le \sum_x |c_x^A| \cdot \left\| (O((-1)^x a] - O((-1)^x (a + \delta_0)]) \otimes \mathbb{I} \right\|_{\infty} + \sum_y |c_y^B| \cdot \left\| \mathbb{I} \otimes (O((-1)^y b] - O((-1)^y (b + \delta_1)]) \right\|_{\infty} \\ &\quad + \sum_{x,y} |c_{x,y}^{AB}| \cdot \left\| O((-1)^x a] \otimes O((-1)^y b] - O((-1)^x (a + \delta_0)] \otimes O((-1)^y (b + \delta_1)] \right\|_{\infty} \\ &\le \delta_0 \sum_x |c_x^A| + \delta_1 \sum_y |c_y^B| + (\delta_0 + \delta_1) \sum_{x,y} |c_{x,y}^{AB}| \\ &=: c_0 \delta_0 + c_1 \delta_1. \end{aligned} \qquad (F59) $$

For the second equality, we applied Equations (F54) and (F55).

Therefore, we have for all $\rho \in S_2$ and all $(a, b) \in [0, \pi/2] \times [0, \pi/2]$,

$$ |\mathrm{tr}[\Delta\rho]| = |\mathrm{tr}[B(a, b)\rho] - \mathrm{tr}[B(a + \delta_0, b + \delta_1)\rho]| \le c_0 \delta_0 + c_1 \delta_1, \qquad (F60) $$

which implies

$$ \mathrm{tr}[B(a + \delta_0, b + \delta_1)] \le \mathrm{tr}[B(a, b)\rho] + c_0 \delta_0 + c_1 \delta_1. \qquad (F61) $$

Let $a' = a + \delta_0$ and $b' = b + \delta_1$. Then

$$ \mathrm{tr}[B(a', b')\rho] \le \mathrm{tr}[B(a, b)\rho] + c_0 (a' - a) + c_1 (b' - b), \qquad (F62) $$

proving the claim.

□

The approximation given by Lemma 17 is exactly of the form required by Lemma 16. By a modification to the proof of Lemma 15, we arrive at the following consequence.

**Corollary 3.** Let $\mathcal{G} = \{(a_j, b_j) : j \in \mathcal{I}\}$ be a finite grid over $[0, \pi/2] \times [0, \pi/2]$, with a spacing $\delta > 0$. Define $\tilde{\mathcal{I}}_{\omega} = \{j \in \mathcal{I} : (a_j, b_j) \in \mathcal{F}_{\omega}\}$. Let $S_j$ be defined in Equation (F44), $B(a, b), c_0, c_1$ be defined in Lemma 17, and $f_{a,b}(\omega)$ be defined in Lemma 15. Suppose $\mathcal{G}$ satisfies the following property:

$$ \mathcal{F}_{\omega} \subset \bigcap_{j \in \tilde{\mathcal{I}}_{\omega}} S_j. \qquad (F63) $$
Then

$$f_2(\omega) \geq \min_{j \in \tilde{I}_{\omega}} f_{a_j, b_j}(\omega - \delta(c_0 + c_1)). \qquad (F64)$$

*Proof.* We start by writing

$$ \begin{aligned} f_2(\omega) &\geq \inf_{\rho \in \mathcal{B}_{2,\omega}} \sup_{\sigma \in \mathcal{B}^D} \mathrm{tr}[\rho\sigma] \\ &= \min_{(a,b) \in \mathcal{F}_{\omega}} \min_{\rho \in \mathcal{B}_{\omega}^{a,b}} \max_{\sigma \in \mathcal{B}^D} \mathrm{tr}[\rho\sigma], \end{aligned} \qquad (F65) $$

as argued in Equation (F36). By assumption, the grid $\mathcal{G}$ satisfies

$$ \mathcal{F}_{\omega} \subset \bigcap_{j \in \tilde{I}_{\omega}} S_j, \qquad (F66) $$

and $(a_j, b_j) \in \mathcal{F}_{\omega}$ for all $j \in \tilde{I}_{\omega}$. Then for every $(a, b) \in \mathcal{F}_{\omega}$ there exists an index $j(a, b) \in \tilde{I}_{\omega}$ such that $(a, b) \in S_{j(a,b)}$. Since $\mathcal{B}_{a,b}^{\omega} \subset \tilde{\mathcal{B}}_{j(a,b)}^{\omega}$ by Lemma 16 with the Bell operator approximation from Lemma 17,

$$ \begin{aligned} \min_{(a,b) \in \mathcal{F}_{\omega}} \min_{\rho \in \mathcal{B}_{\omega}^{a,b}} \max_{\sigma \in \mathcal{B}^D} \mathrm{tr}[\rho\sigma] &\geq \min_{(a,b) \in \mathcal{F}_{\omega}} \min_{\rho \in \tilde{\mathcal{B}}_{j(a,b)}^{\omega}} \max_{\sigma \in \mathcal{B}^D} \mathrm{tr}[\rho\sigma] \\ &= \min_{j \in \tilde{I}_{\omega}} \min_{\rho \in \tilde{\mathcal{B}}_{j}^{\omega}} \max_{\sigma \in \mathcal{B}^D} \mathrm{tr}[\rho\sigma]. \end{aligned} \qquad (F67) $$

The remainder of the proof follows identically to that of Lemma 15, except with the constraint $\mathrm{tr}[B(a, b)\rho] \geq \omega$ substituted with $\mathrm{tr}[B(a, b)\rho] \geq \omega - \delta(c_0 + c_1)$. $\square$

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

## 5. Example: CHSH

To illustrate the numerical method derived in this section, we applied Corollary 3 to bound the singlet fidelity certified by the CHSH inequality. This is known analytically to equal [54]

$$ f_2(\omega) \geq \frac{1 + \sqrt{(\omega/2)^2 - 1}}{2}, \qquad (F68) $$

where $\omega \in [2, 2\sqrt{2}]$ is the violation of the CHSH inequality in correlator form. In Figure 12 we compare this analytical bound to the lower bound generated by our numerics at different grid spacings $\delta$. One can see that the bounds can be made tighter as the spacing decreases, which results in a larger computation time. Specifically, the computation time scales as $O(1/\delta^2)$.

**Remark 8.** While we have compared our technique to known analytical results for the CHSH inequality, unlike Ref. [54], our approach allows one to bound the singlet fidelity for any Bell inequality, or combination of Bell functionals, in the minimal Bell scenario.
<figure><img src="image_16.png" /><figcaption>FIG. 12: Lower bounds on singlet fidelity $f_2(\omega)$ for a given CHSH violation. Compared are the bounds generated by the numerical method of this work at different grid spacings $\delta$, and the known analytical result of Ref. [54].</figcaption></figure>