Device-independent Certification of One-shot Distillable Entanglement
Rotem Arnon-Friedman Jean-Daniel Bancal
quant-ph




1]Rotem Arnon-Friedman
2]Jean-Daniel Bancal
[1]Institute for Theoretical Physics, ETH-Zürich, CH-8093, Zürich, Switzerland
[2]Department of Physics, University of Basel, CH-4056, Basel, Switzerland




Device-independent Certification of

One-shot Distillable Entanglement
    [
    
======================================================================




	Entanglement sources that produce many entangled states act as a main component in applications exploiting quantum physics such as quantum communication and cryptography. 
	Realistic sources are inherently noisy, cannot run for an infinitely long time, and do not necessarily behave in an independent and identically distributed manner. 
	An important question then arises – how can one test, or certify, that a realistic source produces high amounts of entanglement? 
	Crucially, a meaningful and operational solution should allow us to certify the entanglement which is available for further applications after performing the test itself (in contrast to assuming the availability of an additional source which can produce more entangled states, identical to those which were tested).
	To answer the above question and lower bound the amount of entanglement produced by an uncharacterised source, we present a protocol that can be run by  interacting classically with uncharacterised (but not entangled to one another) measurement devices used to measure the states produced by the source. A successful run of the protocol implies that the remaining quantum state has high amounts of one-shot distillable entanglement. That is, one can distill many maximally entangled states out of the single remaining state. Importantly, our protocol can tolerate noise and, thus, certify entanglement produced by realistic sources.
	With the above properties, the protocol acts as the first “operational device-independent entanglement certification protocol” and allows one to test and benchmark uncharacterised entanglement sources which may  be otherwise incomparable. 





§ INTRODUCTION



	Entanglement is one of the most fundamental concepts of quantum physics, distinguishing it from classical physics <cit.>. Furthermore, it plays a crucial role in the advantages gained by considering applications of quantum physics such as quantum computation <cit.>, communication <cit.>, and cryptography <cit.>.
	
	For most applications utilising entanglement, a single entangled pair of particles, e.g., a maximally entangled state |Φ^+⟩ = 1/√(2)(|00⟩+|11⟩), is not sufficient. Instead, one must use many copies of entangled states or, to put differently, a highly entangled state, such as the maximally entangled state  |Φ^L⟩= 1/√(L)∑_i=1^L |i⟩|i⟩ of rank L. Sources that produce high amounts of entanglement are, thus, a prerequisite for gaining from the computational and cryptographic advantages that quantum physics and quantum information unveil. 
	
	Three interesting questions then arise. Firstly, how should one quantify the amount of entanglement produced by a source? Secondly, how can one compare, or benchmark, different  types of entanglement sources? Thirdly, how can one test, or certify, that high amounts of entanglement are indeed being produced by the source? 
	
	Importantly, we would like to answer these questions in an operational way. That is: (a) the suggested answer should be relevant for realistic sources and experimental settings. (b) When considering possible certification procedures, the statement should apply to the entanglement which is still present after the test rather than the entanglement which was already used and, hence, destroyed by the performed certification procedure itself. 

	The current work is concerned with certifying entanglement in such an operational way. 
	Realistic sources are inherently noisy: they produce at best noisy entangled states. Moreover, a source creating  many entangled pairs might produce systems that are correlated with one another due to, e.g., drifting of the source with time or the presence of a memory inside the source. In other words, the overall state produced by the source (after using it many times) is not an independent and identically distributed (IID) state. We call such sources noisy non-IID sources.

	Clearly, in order to make any estimation of the quality of the source one must collect some data regarding the produced entanglement by performing certain measurements on the quantum states produced by the source. Similarly to the considerations regarding the source, the measurement devices might also behave in a noisy and non-IID manner. 

	

 §.§ Device-independent entanglement certification (DIEC)


		We fix as a target to answer our questions while accommodating the noisy non-IID nature of the problem in the so called device-independent (DI) framework <cit.>. In the DI approach one treats the quantum apparatuses as black boxes with which we can only interact classically. That is, we assume no prior knowledge regarding the internal behaviour of the source and the measurement devices. Assumptions are made, however, on the relation that certain devices can have with each other, and on the communication allowed between them. Concretely, we only interact with those devices by “pushing buttons” and collecting the classical data output by them. For example, we may push a button on the source apparatus to produce a state and then another button on the measurement device to ask it to perform a measurement with “input” 0 or 1. The state produced by the source is uncharacterised and we do not know which measurements are actually being performed when we use the inputs 0 and 1.

		As widely known, the only way to demonstrate that the actions of physical devices cannot be explained by classical physics in a DI manner is to perform some Bell tests using the devices and observe a violation of the considered Bell inequality <cit.>. A Bell violation acts as a “witness” attesting to the quantum (in fact, non-local) nature of the devices used to violate the inequality. This can then be used to derive conclusions regarding, e.g., the structure of the underlying quantum states <cit.> or the randomness of the measurements' outcomes <cit.>.
		
		We remark that by using the DI method we do not only treat imperfections in the quantum apparatuses which are known or can be characterised in advance. The DI approach allows one to derive conclusions without making assumptions regarding the types of imperfections. Even more drastically, the devices can be assumed to be “malicious”[“Malicious devices” should be understood here as devices that “try to convince” a verifier that they produce highly entangled states while this is not the case. This is relevant, e.g., in the context of benchmarking, where one may argue, intentionally or not, that a given source is better than another even though this is not true.]; as long as a violation of a Bell inequality is observed, the observer, or verifier, can be sure of the quantum nature of the systems without placing significant trust in the manufacture of the devices. 


		Most previous works, both theoretical and experimental, that can be seen as DI entanglement certification (DIEC) procedures work only under the IID assumption and thus fail to be operational in the sense defined above.[This statement also holds for works in the semi-DI setting; see, e.g., <cit.>.] This includes tests concerned with the demonstration of entanglement via an entanglement witness (i.e. answering a yes-no question) <cit.>, as well as more quantitative analyses of entanglement measures such as  the negativity  and dimension witness <cit.>. In all of these works, the focus is on relating properties of a single multipartite state to some asymptotic statistics. An application of these works in an experimental setting is then most straightforwardly obtained under the assumption that the experiment consists in a repetition of identical rounds in which the same state is produced independently each time, i.e., under the IID assumption. The same assumption is inherent to claims regarding the amount of remaining entanglement which was not consumed by the estimation procedure: such claims rely on the assumption that more states, identical to those which were used for the testing phase, can be created by the source.


		Another line of recent works deals with self-testing of high dimensional entangled states <cit.>. The goal of such works is more ambitious than entanglement certification; they aim to quantify the distance of the state used to perform the relevant tests from some specific target state, e.g., |Φ^L⟩ (up to local isometries, which cannot be excluded in the DI setting). 
		Of course, once such a bound is derived it also implies lower bounds on various (continuous) entanglement measures. 
		
		A crucial disadvantage of these works is that they are not noise-tolerant in any realistic sense and therefore are not adequate when dealing with noisy sources of entanglement. For example, IID noisy sources, which produce many IID copies of a noisy entangled state, e.g., the two-qubit Werner state σ = (1-ξ) |ϕ^+⟩⟨ϕ^+| + ξ𝕀/4 for some constant (i.e., independent of the number of copies being created) noise value ξ∈[0,1], pass the considered self-tests only with negligible probability. Thus, no conclusion regarding the amount of entanglement produced by such IID noisy sources can be derived.[Note that this issue is inherent to the distance measures used in all self-testing works (i.e., their objective) rather than some non-optimal properties of the specific tests considered in the mentioned works.] Furthermore, here as well, most self-testing results can only be used to describe the entanglement which was already consumed in the self-test. As far as we are aware, the only self-testing works where this is not the case are <cit.>.


	

 §.§ Distillable entanglement


		There are many different ways of quantifying entanglement, some of which were already mentioned above (for surveys see <cit.>). One of the most basic and meaningful measures of entanglement is the distillable entanglement. 
		Roughly speaking, given a multipartite state, its distillable entanglement describes the number of maximally entangled states that can be “extracted” out of it by employing only local operations and classical communication (LOCC). Since LOCC cannot be used to create entanglement between the parties, such a process, termed  entanglement distillation, indeed quantifies the entanglement of the initial state itself. 
		
		The task of entanglement distillation was first considered in <cit.>. There, two parties, Alice and Bob, share n copies of a bipartite mixed states σ. Their goal is to apply some LOCC to create r<n copies of, say, |Φ^+⟩.
		This motivates the following, widely used, definition of distillable entanglement:
		
			The asymptotic IID distillable entanglement of a bipartite state σ∈ℋ_A ⊗ℋ_B is given by
			
    E_D^∞(σ) = sup{ r | lim_n→∞(  sup_Γ F ( Γ(σ^⊗ n), Φ^2^r n) =1 ) } ,

			where Γ is an LOCC map (with respect to the bipartition of σ) and F is the fidelity.
		
		
		
		Equation (<ref>) describes a scenario in which one starts with n independent copies of σ and requires that, as n goes to infinity, the error of the distillation protocol goes to zero.
		This explains why we call it here the asymptotic IID distillable entanglement and not simply the distillable entanglement as it is usually called in the literature.
		However, as we claimed above, the sources that we consider do not necessarily produce IID states σ^⊗ n (and they, definitely, do not emit n→∞ entangled states). Hence, E_D^∞(σ) does not truly quantify the entanglement produced in our scenario. 
		
		For our purpose, a more suitable entanglement measure is the one-shot distillable entanglement <cit.>.  
		In the one-shot scenario Alice and Bob share a single copy of a bipartite state ρ and their goal is to convert it to the maximally entangled state |Φ^L⟩, for the maximal  possible value L, using only LOCC. 
		We say that the distillation protocol is successful when the resulting state is ε-close to |Φ^L⟩ for some fixed ε. 
		
		To state the definition of the one-shot distillable entanglement in a way comparable to its asymptotic IID counterpart E_D^∞, we consider ρ∈ℋ_A^⊗ n⊗ℋ_B^⊗ n for a fixed n and some Hilbert spaces ℋ_A and ℋ_B (while ρ itself does not necessarily have the IID form σ^⊗ n). We then identify the one-shot distillation rate as r=log(L)/ n.[For a given ρ there are different ways of choosing n, ℋ_A and ℋ_B such that ρ∈ℋ_A^⊗ n⊗ℋ_B^⊗ n. Thus, different choices can lead to different distillation rates r=log(L)/ n (while n   E_D^n,ε(ρ) is independent of these choices). Later on there will be no ambiguity regarding the value of n and hence the used definition will be the one most relevant for us.] 
		We can now use the following definition:
		
			Let n∈ℕ_+ and ε∈ [0,1]. The one-shot distillable entanglement of a bipartite state ρ∈ℋ_A^⊗ n⊗ℋ_B^⊗ n is given by
			
    E_D^n,ε(ρ) = sup{log(L)/ n | sup_Γ F(   Γ(ρ),  Φ^L) =1-ε} ,

			where Γ is an LOCC map (with respect to the bipartition of ρ) and F is the fidelity.
		

		E_D^n,ε(ρ) describes the number of maximally entangled states which can be extracted, using LOCC, from a single copy of an arbitrary bipartite state ρ while allowing for some error ε. Hence, it captures the amount of entanglement available in ρ when using it as a resource in quantum information processing tasks. 


		

  
*Structure of the paper. 
		The following sections are arranged as follows. 
		In Section <ref> we present our contribution: our definition of an operational DIEC, the considered setting, and our results (the protocol and achieved rates). 
		One can find all the necessary preliminary information and notation in Section <ref>.
		Section <ref> is devoted to presenting the main steps of the proof and Section <ref> includes several remaining open questions.
		All the technical details of the proofs can be found in the appendix. 
		
		



§ OUR CONTRIBUTION: OPERATIONAL DIEC

	
	After setting the stage in the previous section, we are now ready to state the objective of the current work – DI certification of one-shot distillable entanglement – and our results. 
	We start in Section <ref> by introducing and motivating our definition of an operational DIEC protocol. We then explain in Section <ref> the exact setting of the source and measurement devices considered in our work. In Section <ref> we present our results. 
	
	

 §.§ The goal

			
		Let us start by defining explicitly  what we mean by a DIEC protocol and, by this, set the goal of this work.
		Given an uncharacterised source of entanglement producing n bipartite systems globally described by the  state ϕ∈ℋ_Ã^⊗ n⊗ℋ_B̃^⊗ n for some (unknown) Hilbert spaces ℋ_A and ℋ_B and (at least) two measurement devices not entangled to one another but otherwise uncharacterised, our goal is to find a DIEC protocol, employing only LOCC, that certifies that ϕ is highly entangled in a meaningful operational way. The certification protocol is going to act on ϕ, using the measurement devices, and we would  like to claim (roughly) that, if the protocol does not abort, then the final state has high amount of one-shot distillable entanglement. 
		
		More precisely, we define a DIEC as follows.
		
			For any n∈ℕ_+ let ε_dist,ε_snd,ε_cmp∈ [0,1] be the desired error constants, and r∈ [0,1] the desired threshold distillation rate. 
			Furthermore, let 𝒮^honest be a set of states ϕ^honest produced by a desired “honest source” and 𝒟^honest the set of the desired “honest measurement devices”.[Mathematically, this set can be defined as, e.g., a set of projectors applied by the measurement devices for the different possible inputs.]
			Let P be a protocol employing only LOCC that given a state ϕ∈ℋ_Ã^⊗ n⊗ℋ_B̃^⊗ n creates a state ρ∈ℋ_A^⊗ n⊗ℋ_B^⊗ n. We denote the final state conditioned on not aborting the protocol by ρ_|Ω.

			The protocol P is said to be a DIEC protocol if the following two properties hold:
			
				
  * Noise-tolerance (completeness): The probability that P aborts when applied on any ϕ^honest∈𝒮^honest using honest measurement devices from 𝒟^honest  is at most ε_cmp.
				
  * Entanglement certification (soundness): For any source and measurement devices either P aborts with probability greater than 1-ε_snd when applied on ϕ or E_D^n,ε_dist(ρ_|Ω) ≥ r.
			
			
		
		
		There are several important remarks to make regarding the above definition. 
		
			
  * One possible example for an honest source is a source producing n independent copies of the Werner state σ = (1-ξ) |ϕ^+⟩⟨ϕ^+| + ξ𝕀/4 for some maximal value of ξ>0. 
			We can then define  
			
    𝒮^honest = {( (1-ξ̃) |ϕ^+⟩⟨ϕ^+| + ξ̃𝕀/4)^⊗ n  |  ξ̃≤ξ } .

			𝒟^honest can be defined to include, e.g., the measurement devices that apply the optimal measurements performed in the CHSH game. 
			The noise-tolerance property, also termed completeness, states that the protocol should not abort, with high probability, for any ϕ^honest∈𝒮^honest even though some noise ξ>0 is present. 
			This implies (in combination with the soundness property) that P is able to certify the entanglement produced by the honest source. 
			Of course, the honest sets 𝒮^honest and 𝒟^honest can be chosen in any way one wishes and depending on the experimental setting one has in mind. For instance, it could include states with a different noise model than the Werner state.
			In most cases the manufacture of the entanglement source (the experimentalist) has some “guess” for a realistic description of the source and measurement devices. In most applications, these define the sets that should be chosen as the honest sets.
			
			
  * The entanglement certification, or soundness, property means that for any state produced by the unknown source and any measurement devices either the protocol identifies that the apparatus is not sufficiently good, and therefore the protocol aborts, or the post-protocol state ρ_|Ω is highly entangled, in the sense that there exists a way to distill (close to) nr maximally entangled states out of it.
			The protocol therefore certifies that ρ_|Ω is indeed useful for subsequent applications.[Note that below we only claim that a distillation protocol exists but we do not present it explicitly.] 
			
			
  * To be able to quantify the entanglement produced by the source itself, rather than the entanglement that could be present inside the measurement devices, we need to assume that the measurement devices were not entangled before the start of the protocol. This situation is somehow similar to the requirement for measurement independence in a Bell test: if the measurement settings used in a Bell test are chosen by a device correlated with the source, then quantum statistics can be reproduced by local models <cit.>. In practice, measurement independence is guaranteed by assuming that the devices used to produce the measurement settings behave independently from the rest of the setup. Similarly, we could assume that the measurement device of each party is independent from all other devices involved in the protocol. However, this hypothesis is stronger than necessary. We thus make the lighter assumption that the measurement devices share no entanglement with each other at the beginning of the protocol.
			
			
			
  * Only LOCC protocols should be considered as DIEC protocols since we would like to certify the distillable entanglement produced by the source and not the entanglement that may be produced by a protocol employing operations that cannot be explained via LOCC.[Another option may be to consider protocols that employ only separability preserving operations; see <cit.>.]
			
			
  * In a way, the definition of a DIEC can be seen as an extension of the so called SWAP technique <cit.>, used in self-testing works, to the non-IID setting. Roughly speaking, by constructing the SWAP operators one can claim that a state close to, e.g., the maximally entangled state, up to local isometries can be “extracted” out of the uncharacterised devices. The construction of a DIEC protocol implies that one can extract a state close to many maximally entangled states using LOCC.
			
			
  * The above definition allows us to use DIEC protocols as a way to compare different entanglement sources which are otherwise incomparable. For example, one can consider two sources developed by different experimental groups. One source produces, say, many identical copies of the Werner state while the other creates many identical copies of perfect partially entangled states. 
			Each group is free to choose a DIEC protocol, as in Definition <ref>, that will result in the highest lower bound on the distillable entanglement produced by its source. 
			If one group wishes to claim that its source is “better”, then the certified distillation rate of their source (which can be verified by any user) must be higher than that of the competing source. 
			The protocols allow us to benchmark one source against the other in a meaningful way by allowing any user to verify a claimed lower bound on the produced entanglement available for further applications. 
		
		 	
	
	

 §.§ The setting: source and measurement devices

	
		Here we describe the theoretical setting considered in our work to which our results apply, i.e., under which we will prove the soundness of our DIEC protocol.
		
		Different variants of this setting can be chosen depending on one's interest; we choose the presented one as we believe it is both realistic and simple to discuss. 
		This setting is compatible with the standard assumptions used in the DI setting (e.g., when testing the CHSH Bell inequality in DI quantum key distribution or randomness generation protocols).
		In particular, we employ the following standard assumptions: the measurement devices are separated in space and are the verifier can restrict their communication in different stages of the protocol and the verifier holds a trusted random number generator and is able to make basic classical calculations required to run the protocol. 
		In addition, we assume that quantum physics is correct.  
		
		
		
		
		

		

  §.§.§ The theoretical setting: source, measurement devices, and quantum registers
	
		
			In order to be able to talk about the entanglement available after running the DIEC protocol we must be able to have a well defined state at hand, whose entanglement we are quantifying. For this, we consider a theoretical setting which fulfils the following  two conditions. 

			First, the production of any entangled states (if such are being created) can be attributed only to the source. In other words, we assume that the measurement devices neither produce nor hold additional entanglement. This implies a distinction between the source and the measurement devices. 
			


			Second, the state produced by the source, or the “post-protocol state”, can be kept in some registers, i.e., quantum memory. This is necessary at the theoretical level since we wish to discuss the remaining entanglement in a meaningful way. The registers are trusted, in the sense that they cannot be manipulated by the devices after they are accessed during the protocol. Indeed, if the devices are allowed to, e.g., measure the registers in which the final state is being kept then, clearly, one cannot say anything regarding the entanglement left in the system.[This also fits the distinction we made above between the source and the measurement devices. If the entanglement is produced by the measurement devices and is kept “inside of them” then they can also destroy whatever is left in the end of the protocol.]


			Note that by considering the one-shot distillable entanglement we are already hinting that one should be able to apply an entanglement distillation protocol on the certified state (at least in theory). To apply such a protocol, the state must be available somewhere so it can be manipulated. Defining some quantum registers in which the state is being kept is therefore necessary in our context. 
			The quantum registers are merely a theoretical tool, they are not needed in an experimental implementation of our DIEC protocol.
			
			
			The reminder of the current section is devoted to explaining precisely the setting, fulfilling the above conditions that we consider in the current work. The setting is illustrated in Figure <ref>.
		
		
			
		
		
		
			The entity wanting to certify the entanglement produced by the source is called the verifier. 
			To run the DIEC protocol the verifier holds two separated (space-like or otherwise shielded) measurement devices. As we consider two measurement devices we can also treat the verifier as two parties, Alice and Bob (both the “verifier” and “Alice and Bob” are used below, depending on the context).
		
			We consider an uncharacterised source emitting a sequence of entangled quantum systems . (For example, one can imagine a source that emits pairs of entangled photons one after the other).
			We denote by n∈ℕ_+ the number of systems  produced by the source, i.e., the number of times the source is being used during the DIEC protocol. 
			For every i∈[n], the source produces some unknown state ϕ^i that is being kept in the memory.
			The verifier then chooses whether to measure the state using his measurement devices or not. 
			If he measures the state then the classical inputs given to the devices and the outputs produced by them are kept in a classical  memory. If ϕ^i is not measured then it is kept as is in a quantum memory. 
	

			The next state produced by the source,  ϕ^i+1, can  depend on all of the previous classical information, i.e., which of the previous states were measured and what were the inputs and outputs in those rounds.
			Note that while ϕ^i+1 can depend on whether a test was made in a previous round j<i+1, the source and the measurement devices have no further access to the quantum states ϕ^j which were not measured. That is, we assume that each ϕ^j which was not measured is not affected by the devices after the j'th round.
			Again, this is necessary as otherwise the remaining entanglement can be destroyed by the devices. We emphasise that this does not imply that the systems of the different rounds cannot be entangled with one another. 

		
			We use the above model in our protocol and its analysis. However, we remark that the protocol and analysis can be adapted to capture other models with a sequential structure. 

		
		

		

	

 §.§ Results

	
		

  §.§.§ Our DIEC protocol and the achieved rates

		

			Our DIEC protocol is presented as Protocol <ref>. It is based on the CHSH inequality (see Section <ref> for the necessary basic information). Similar protocols can also be considered for other Bell inequalities. 
	
			
	
			As mentioned in the previous section, we consider a source which produces a sequence of bipartite states, denoted by ϕ^i for i∈[n]. 
			The verifier chooses whether to measure ϕ^i or keep it as is in the memory. The register T_i describes whether a test was performed or not. 
			If a test is performed, the registers X_iY_iA_iB_i hold the classical inputs and outputs. The register W_i is set to 1 when the CHSH game is won in the i'th round and 0 otherwise. 
			When a test is not being performed, the state ϕ^i is kept in the quantum registers Â_iB̂_i.
			We allow the source to “know” all the classical information of the previous rounds, i.e., (TABXYW)_1,…,i-1 and hence ϕ^i can also depend on this information.
			
			We denote the state in the end of Protocol <ref>, before Step <ref>, by 
			
    ρ = ρ_ÂB̂ABXYTW .

			
			Denote by χ the indicator function, i.e. χ=1 if T_i=1, and χ=0 otherwise.
			Let Ω be the event ∑_i χ(T_i=1) W_i ≥ (ω_expγ - δ_est) n, i.e., the event of not aborting the protocol. 
			We denote the state after the end of the protocol, conditioned on not aborting, by
			
    ρ_|Ω = ρ_ÂB̂ABXYTW|Ω .

	
			We define the bipartition of ρ and ρ_|Ω as Q^A=Â vs. Q^B= B̂ABXYTW. 
			It is easy to see that for this bipartition Protocol <ref> employs only LOCC for any measurement devices in our setting (i.e., initially non-entangled devices that do not communicate during the time of the measurement).
	
			Our main result states that Protocol <ref> is indeed an operational DIEC protocol. That is, it fulfils the requirements of Definition <ref>. 
			
		
			As the honest source and devices we choose to consider a source that produces identical and independent copies of a state ϕ^i=σ and  measurement devices that apply the same measurements in each round when they are used. The state σ and the measurements are such that the winning probability achieved in the CHSH game is at least ω_exp. 
			For example, one can choose 𝒟^honest to include the measurement devices that apply the optimal measurements performed in the CHSH game and the
			 set 𝒮^honest to include all states ϕ^honest=σ^⊗ n for σ any noisy maximally entangled state that will result in winning probability ≥ω_exp.

			
			

			
			

			
			The following theorem states our main result.
			
				For any n∈ℕ_+, ε_dist,ε_snd∈ [0,1], and ε_smo∈[0,√(ε_dist)), Protocol <ref> is a DIEC protocol with:
				
					
  * Noise-tolerance (completeness): The probability that P aborts when applied on any ϕ^honest∈𝒮^honest using honest measurement devices from 𝒟^honest  is at most ε_cmp≤exp(- 2 nδ_est^2 ).
					
  * Entanglement certification (soundness): For any source and measurement devices in the considered setting, either Protocol <ref> aborts with probability greater than 1-ε_snd when applied on ϕ or 
					E_D^n,ε_dist(ρ_|Ω) ≥ r for r=log(L)/ n and
					
    log L= - n·η_opt(ε_smo,ε_snd) -4log(  1/√(ε_dist)-ε_smo)  ∈Ω(n)

					where  η_opt is defined in Equation (<ref>). 
				
			

			The exact bound on the certified distillation rate r is not very informative, so we postpone discussing its explicit form to later. 
			Instead, we plot the distillation rate in Figure <ref> for some choices of parameters. 
			Clearly, the optimal distillation rate is upper bounded by 1 and hence log L ∈Ω(n), as achieved in our work, is optimal in terms of the asymptotic dependency on n. 
			
			To discuss the tightness of the derived rates more concretely we need to first say few words about our proof technique. 
			To prove Theorem <ref> we use two independent results.
			The first is a lower bound on the one-shot distillable entanglement in terms of the negative 
			of the conditional smooth max-entropy H_max^ε_smo(Q^A|Q^B)_ρ_|Ω <cit.>. This allows us to reduce the task of proving Theorem <ref> to that of (upper) bounding H_max^ε_smo(Q^A|Q^B)_ρ_|Ω. 
			The main tool used to derive a bound on the smooth max-entropy is the entropy accumulation theorem <cit.>.
			
			Our bound on  H_max^ε_smo(Q^A|Q^B)_ρ_|Ω is tight to first order in n and hence cannot be significantly improved. 
			In particular, this means that the regime of Bell violations ω_exp⪅ 0.775 in which our distillation rate is zero, although the verifier observes a violation, cannot be improved by better bounding H_max^ε_smo(Q^A|Q^B)_ρ_|Ω.
			
			Qualitatively, it is not surprising that such a regime exists. Indeed, it was already shown that, in general, Bell non-locality is fundamentally different from distillable entanglement (this stands in contrast to the so called Peres conjecture). That is, there are bound entangled states (i.e., entangled state which cannot be distilled)  that can be used to violate some Bell inequalities <cit.>.
			For the CHSH inequality, however, this is not the case <cit.>: bound entangled states cannot be used to violate the CHSH inequality. Hence, asymptotically, one should be able to certify distillable entanglement for any violation ω_exp>0.75. 
			
			This implies that, although our bound on  H_max^ε_smo(Q^A|Q^B)_ρ_|Ω is tight, the relation between the smooth max-entropy and the one-shot distillable entanglement is not; it only gives a lower bound on the amount of distillable entanglement but it should be possible to distill more (see Section <ref> for more details).

			
		

  §.§.§ von Neumann entropy as a function of the CHSH violation

		
			As a step in our proof of Theorem <ref> we derive an upper bound on the conditional von Neumann entropy H(Â_i|B̂_i)_σ for any Bell-diagonal quantum state σ_Â_iB̂_i that can be used to win the CHSH game with winning probability ω∈[3/4,2+√(2)/4]. The conditional von Neumann entropy is negative only when evaluated over entangled states. Thus, an upper bound on it can be seen, by itself, as a quantitive certificate of entanglement (though not in our operational sense). Such a bound might be of independent interest in other contexts. 
			
			Inspired by <cit.>, in which a “dual quantity”[In <cit.> a bound on H(A|E) was derived, where A is the measurement outcome on Alice's side (when measuring σ_Â_i in our notation) and E describes a system used to purify σ_Â_iB̂_i.] was bounded, we derive a bound for Bell diagonal states. We prove the following:


			
				For any Bell diagonal state σ_Â_iB̂_i that can be used to violate the CHSH inequality with violation ω∈[3/4,2+√(2)/4],
				
    H(Â_i|B̂_i)_σ≤ 2h(1/2-2ω -1/√(2)) - 1  ,

				where h is the binary entropy function.
			


			The bound given in Equation (<ref>) is plotted in Figure <ref>. The bound is tight, i.e., there exist states that saturate it. 
			As mentioned above, the “interesting” regime of the bound is that in which the conditional entropy is negative, i.e. ω⪆ 0.775 (β⪆ 2.2).
			A similar bound, but for the conditional max-entropy H_max(Â_i|B̂_i)_σ was derived in <cit.>. As H_max(Â_i|B̂_i)_σ≥ H(Â_i|B̂_i)_σ, their bound can also be used to upper bound the von Neumann entropy. However, using our bound directly leads to better quantitive results. In particular, the bound derived in <cit.> only leads to a negative upper bound for β⪆ 2.5.
			
			The observation that there exists a regime in which the conditional entropy is positive although the CHSH inequality is violated is not new. Indeed, it was already known that  that some states, e.g., the Werner state, can be used to violate the CHSH inequality while presenting positive conditional entropy <cit.>. 
			
			The fact that the bound (<ref>) on the conditional entropy is negative as soon as the winning probability is larger than ω⪆ 0.775 allows our scheme to certify entanglement for honest implementations based only on their CHSH winning probability. In particular, the honest implementation might be different than the Werner state we considered above as an example. At the same time, since the minimum winning probability required to obtain a useful bound on the conditional entropy is larger than 0.75, a significant Bell violation is required. This has implications on the critical detection efficiency of the scheme: whereas a violation of the CHSH Bell inequality is possible as soon as the detection efficiency is larger than 66.7% <cit.>, the minimal detection efficiency required to reach a CHSH value of 2.2 is 85.3%.
			
			
			







§ PRELIMINARIES


	

 §.§ General notation

		
		The set {1,2,…,n} is denoted by [n]. 
		
		All logarithms are in base 2. 
		Random variables (RV) are denoted by capital letters while specific values are denoted by small letters.
		Sets are denoted with calligraphic fonts.
		For example, we use X_i to denote a RV over 𝒳 and x_i to denote a certain value x_i∈𝒳.

		
		Most RV will refer to a specific i∈[n] denoted in their subscript, as in X_i above. RV describing a range between i,j∈[n] for i<j are written as X_i,⋯,j=X_i,⋯,X_j. When no subscript appears then the range is from 1 to n, i.e., X=X_1,⋯,X_n.
		
		The fidelity of two quantum states is given by F(ρ,σ)=√(ρ)√(σ)_1^2.

	

 §.§ The CHSH  inequality and game

		
		In a bipartite scenario where each party, Alice and Bob, can perform one of two possible measurements, indexed by X_i,Y_i∈{0,1}, and with outcomes denoted by A_i,B_i∈{0,1}, a Bell inequality is a linear constraint on the conditional probability distributions P(A_i,B_i|X_i,Y_i) which is satisfied by all local hidden variable models <cit.>. One Bell inequality of special interest is the so-called Clauser-Horne-Shimony-Holt (CHSH) inequality <cit.>, which takes the form
		
    β = ∑_a_i,b_i,x_i,y_i (-1)^a_i+b_i+x_i y_i P(a_i,b_i|x_i,y_i) ≤ 2  .

		
		This inequality admits a maximum quantum violation of β=2√(2). To achieve this maximal violation Alice and Bob can share the maximally entangled state |Φ^+⟩ = (|00⟩+|11⟩)/√(2) and measure it with the following measurements: Alice's measurements X_i=0 and X_i=1 correspond to the Pauli operators σ_z and σ_x respectively and Bob's measurements Y_i=0 and Y_i=1 to (σ_z + σ_x)/√(2) and (σ_z - σ_x)/√(2) respectively.
		We can therefore restrict our attention to β∈[2,2√(2)]. 
		
		The CHSH inequality can be equivalently expressed in terms of a game. The game is defined via the  winning condition 
		w_CHSH=1 iff A_i⊕ B_i = X_i · Y_i. 
		The optimal quantum strategy described above achieves winning probability ω = 2+√(2)/4≈ 0.85, while the optimal classical strategy achieves a winning probability of 0.75.
		The relation between the winning probability in the  game and the violation of CHSH inequality is given by ω=1/2+β/8 and we have ω∈[ 3/4, 2+√(2)/4].

		
	
	

 §.§ Quantum entropies and Markov chains

	
		

  
*Shannon entropy.
		The Shannon entropy of a probability distribution {p_i} is given by H({p_i})=-∑_p_ip_ilog(p_i).
		For a Bernoulli process with probability p the we use the binary entropy function h(p)=-plog (p) -(1-p)log (1-p).

		

  
*von Neumann entropy.
		The von Neumann entropy H(ρ) of a quantum state ρ is given by H(ρ)=- (ρlogρ). 
		Given a bipartite state ρ_AB∈ℋ_A⊗ℋ_B the conditional von Neumann entropy is 
		
    H(A|B)_ρ_AB = H(ρ_AB) -H(ρ_B) .

		When the state on which the entropy is evaluated is clear from the context we drop the subscript and write H(A|B).
	
		

  
*Max-entropy.
		The explicit definition of the quantum max-entropy will not be of use in the current work. Yet, we state it here for completeness. 
		The conditional smooth max-entropy of a bipartite quantum state ρ_AB is given by 
		
    H^ε_max(A|B)_ρ_AB = loginf_σ_AB∈ℬ^ε(ρ_AB)sup_τ_Bσ_AB^1/2τ_B^-1/2_1^2  ,

		where  ℬ^ε(ρ_AB) the set of sub-normalised states σ_AB with P(ρ_AB,σ_AB) ≤ε and P is the purified distance <cit.>.

		

  
*Markov chains.
		A tripartite quantum state ρ_ABC is said to fulfil the Markov chain condition A↔ B ↔ C if I(A:C|B) = 0, where I(A:C|B)= H(AB) + H(BC) - H(B) - H(ABC) is the conditional mutual information. Note that I(A:C|B) = 0 if and only if given B, A and C are independent.
		
	

 §.§ The entropy accumulation theorem

	
		The entropy accumulation theorem (EAT) <cit.> gives us a way of bounding the amount of smooth min- or max-entropy accumulated during a sequential process fulfilling certain conditions. In contrast to previous works where a bound on the smooth min-entropy was derived using the EAT, the current work uses the EAT to bound the smooth max-entropy. 
		We state here the necessary details in the context of our work. 

		To apply the EAT one needs to define “EAT channels” which describe the sequential process under consideration (in our case, for example, the channels are defined via the actions of our DIEC protocol). EAT channels are defined as follows.
		
			EAT channels 𝒩_i:R_i-1→ R_i O_i S_i W_i, for i∈[n], are CPTP maps such that for all i∈ [n]:
			
				
  * O_i are finite dimensional quantum systems of dimension d_O_i and W_i are finite-dimensional classical systems (RV).  
					S_i and R_i are arbitrary quantum systems. 
				
  * For any i∈[n] and any input state σ_R_i-1, the output state σ_R_i O_i S_iW_i =  𝒩_i  (σ_R_i-1) has the property that the classical value W_i can be measured from the marginal σ_O_iS_i without changing the state. 
						That is, for the map 𝒯_i :O_iS_i→ O_iS_iW_i describing the process of deriving W_i from O_i and S_i, it holds that _W_i∘𝒯_i (σ_O_iS_i) = σ_O_iS_i.
				
  * For any initial state 
				τ_R_0^0, the final state τ_OSW = ( _R_n∘𝒩_n ∘…∘𝒩_1)  τ_R_0^0 
				fulfils the Markov chain condition O_1… i-1↔ S_1… i-1↔ S_i for each i∈[n]. 
			
		

		We will use below the following notation. Given a value w=w_1, …, w_n ∈𝒲^n, where 𝒲 is a finite alphabet, we denote by freq_w the probability distribution over 𝒲 defined by freq_w(w̃) = | { i | w_i = w̃} |/n for w̃∈𝒲.
		If τ is a state classical on W we write [w]_τ to denote the probability that τ assigns to w. 
		
		
			Let 𝒩_1,…,𝒩_n be a family of EAT channels. Let 𝒲 denote the common alphabet of W_1,…,W_n. 	
			A concave[Let  Ω̂ be a set of frequencies defined via freq_w(w̃)∈Ω̂ if and only if w̃∈Ω.
			We can consider concave functions, in contrast to affine ones <cit.>, since the event Ω defined in the current work results in a convex set Ω̂.]  function f_max from the set of probability distributions p over 𝒲 to the real numbers is called a max-tradeoff function for {𝒩_i} if it satisfies
			
    f_max(p) ≥sup_σ_R_i-1:𝒩_i(σ)_W_i=p H( O_i | S_i  )_𝒩_i(σ)

			for all i∈ [n], where the supremum is taken over all input states of 𝒩_i for which the marginal on W_i of the output state is the probability distribution p.  
		
		
		
		


		The statement of the EAT, relevant for the smooth max-entropy, is given below.
		
			Let 𝒩_i:R_i-1→ R_i O_i S_i W_i for i∈ [n] be EAT channels as in Definition <ref>,  τ_OSW = ( _R_n∘𝒩_n ∘…∘𝒩_1) τ_R_0 be the final state, 
			Ω an event  defined over 𝒲^n, [Ω]_τ the probability of Ω in τ, 
			and τ_|Ω the final state conditioned on Ω. Let ε_smo∈ (0,1).
			
			For f_max a max-tradeoff function for  {𝒩_i} as in Definition <ref> and any t∈ℝ such that f_max(freq_w ) ≤ t for any w∈𝒲^n for which [w]_τ_|Ω> 0,
			
    H_max^ε_smo( O|S )_τ_|Ω≤ n t + v√(n) ,

			where v = 2(log(1+2 d_O_i ) + ⌈▿ f_max_∞⌉)√(1-2log (ε_smo·[Ω]_τ)) and d_O_i denotes the dimension of O_i.
		
		
		We used above a slightly and trivially modified statement of the EAT, compared to that of <cit.>. 
		The definition of the max-tradeoff function used in <cit.> consideres H( O_i | S_i  R' ) where R' is isomorphic to to R_i-1. For the calculation of the supremum one can always assume that the system on R' is in product with the rest of the system and hence drop it here (see Remark 4.2 in <cit.>). 
		Furthermore, in <cit.> the EAT is stated with H_max^ε_smo(O|SE) where E denotes a system extending the initial state τ_R_0, i.e., we have _E(τ_R_0E) = τ_R_0. 
			The E, in fact, can be dropped as the theorem must hold for any τ_R_0E and, hence, in particular for τ_R_0E=τ_R_0⊗τ_E as in Theorem <ref>, for which the conditional smooth max-entropy is maximal.
			In our context, an alternative way of thinking about this is to note that our goal is to bound H_max^ε_smo( O|S )_τ_|Ω. As it clearly depends only on the registers O and S, E does not take part in the proof and we can, w.l.o.g., consider an initial state of the form τ_R_0⊗τ_E. The final state then also has a tensor product form.







§ MAIN PARTS OF THE PROOF


	In this section we present the main steps and ideas used in the proof of Theorem <ref>. The full details are given in the Appendix. 

	

 §.§ Modified protocol

	
		As explained above, our goal is to show that there exists an entanglement distillation protocol that can distill the entanglement present in  ρ_|Ω. 
		Instead of considering an entanglement distillation protocol that acts on the state ρ_|Ω directly, we consider a slightly modified scenario. The modified scenario will result in a state τ_|Ω, closely related to ρ_|Ω, from which at least same amount of entanglement can be distilled. 
		
		Concretely, we modify the real DIEC, Protocol <ref>, to define the modified protocol stated as Protocol <ref>. The only difference between this protocol and Protocol <ref> is in Steps <ref> and <ref>, which we explain below.
		
		We remark that Protocol <ref> is being used only as a step in the proof of our theorem. We do not claim at any point that this modified protocol can be implemented by the verifier given the uncharacterised devices (in fact, it cannot). 
		It will become clear later on why the modified protocol is, nevertheless, needed in our proof.
		
		
	
			
			

  §.§.§ First modification: reduction to qubits

			
				When a test is not being performed by the verifier the state produced by the source is being kept in the memory. In Protocol <ref> the state is being kept as is. In contrast, in Protocol <ref> we first project the state such that the resulting state is a two qubit state. The projection, described by two local projections, can obviously only decrease the amount of entanglement of the kept state. 
				
				As one can guess, we define the specific projection via the measurements performed by the measurement devices.[These are unknown to the verifier but, as mentioned above, Protocol <ref> does not need to be implemented in practice by the verifier. The only thing that matters is that such projectors exist.]
				Formally, due to Jordan's lemma (see, e.g., <cit.>), the measurements operators Π_a|x^A_i, Π_b|y^B_i of each party, Alice and Bob, in each round i∈[n] can be written in a suitable local basis as
				
    Π^A_i_0|0 - Π^A_i_1|0   = c_i⊕ A_0^c_i = c_i⊕σ_z^c_i
    Π^B_i_0|0 - Π^B_i_1|0   = d_i⊕ B_0^d_i = d_i⊕σ_z^d_i
    Π^A_i_0|1 - Π^A_i_1|1   = c_i⊕ A_1^c_i= c_i⊕cos(α_c_i) σ_z^c_i + sin(α_c_i)σ_x^c_i
    Π^B_i_0|1 - Π^B_i_1|1   = d_i⊕ B_1^d_i = d_i⊕cos(β_d_i) σ_z^d_i + sin(β_d_i)σ_x^d_i

				with parameters α_c_i and β_d_i and the different σ's denoting the Pauli matrices. 
				
	
				With this in mind, when T_i=0 we let each party perform a measurement on ρ^i_Â_iB̂_i (which is identical to ϕ^i in the case T_i=0) according to the following operators:
				
    Π^Â_i_c_i   = |c_i⟩⟨c_i|⊗𝕀
    Π^B̂_i_d_i   = |d_i⟩⟨d_i|⊗𝕀.

				This gives  each party the index of her/his respective Jordan blocks c_i and d_i. 
				We denote by p(c_i,d_i) the probability of observing the indices c_i,d_i. 
				The global system is projected into the two-qubit state 
				
    ρ̅^i_Â_iB̂_i C_i D_i = (Π^Â_i_c_i⊗Π^B̂_i_d_i)ρ^i_Â_iB̂_i(Π^Â_i_c_i⊗Π^B̂_i_d_i)/(Π^Â_i_c_i⊗Π^B̂_i_d_iρ^i_Â_iB̂_i)⊗|c_i⟩⟨c_i|⊗|d_i⟩⟨d_i| ,

				where we added a classical register for the measurement outcomes. At this stage, the parties exchange their indices c_i and d_i with each other. It is easy to see that the considered projection step can be described via LOCC.
				
					
				Note the following:
				
					
  * Due to the projection, the registers Â_iB̂_i are now qubit registers. 
					
  * Since the projectors given in Equation (<ref>) are defined via the measurements used by the device when T_i=1, they could also be applied when T_i=1 without changing the resulting state. This is made formal in Lemma <ref> below (for the proof see Appendix <ref>). 
				
				
				
				
					Consider a scenario in which the projection to the two qubit space is applied on the state ϕ^i directly after it is produced by the source in the i'th round (i.e., before choosing the value of T_i). Denote the resulting state in the end of the i'th round in such a case by ρ̅̅̅^i. Then 
					
    ρ̅̅̅^i_Â_iB̂_i A_iB_i C_i D_iX_iY_i = ρ̅^i_Â_iB̂_i A_iB_i C_i D_iX_iY_i ,

					where ρ̅^i is as defined in Equation (<ref>).
				
	
				It is clear that for the state ρ̅̅̅^i the measurements in the case of T_i=1 act on the subspace of the same Hilbert space which is otherwise kept in Â_iB̂_i when T_i=0, since the projection is made before choosing the value of T_i. Lemma <ref> implies that this is also the case when the projection is applied only when T_i=0 as in our modification.
				Without this property one could not argue that the test rounds, i.e., those for which T_i=1, represent also the rounds with T_i=0.

			

  §.§.§ Second modification: reduction to Bell diagonal states

			
				After the projection, we apply another step that can be seen as a symmetrisation step, also called twirling in the literature.	
				In each round for which T_i=0, a one-qubit unitary U is chosen uniformly within the set {𝕀,σ_x,σ_y,σ_z} and applied on both systems Â and B̂. That is,
				
    ρ̃^i_Â_iB̂_i|c_i,d_i = 1/4∑_U(U⊗ U) ρ̅^i_Â_iB̂_i|c_i,d_i(U⊗ U)^† ,

				where ρ̅^i_Â_iB̂_i is defined in Equation (<ref>) and the sum is over U∈{𝕀,σ_x,σ_y,σ_z}.
				
				It was shown in <cit.> that the resulting state is diagonal in the Bell basis {|Φ^+⟩,|Φ^-⟩,|Ψ^+⟩,|Ψ^-⟩}. In our notation, we get the following corollary:
				
				
					For all i∈[n] with T_i=0,  
					
    ρ̃^i_Â_iB̂_iC_iD_i=∑_c_i,d_i p(c_i,d_i) ρ̃^i_Â_iB̂_i|c_i,d_i⊗|c_i⟩⟨c_i|⊗|d_i⟩⟨d_i|
 
					where each ρ̃^i_Â_iB̂_i|c_i,d_i is diagonal in the Bell basis. That is, it can be written as 
					
    ρ̃^i_Â_iB̂_i|c_i,d_i = [ λ_Φ^+                  ;       λ_Φ^-            ;             λ_Ψ^+      ;                   λ_Ψ^- ]

					in the basis of the Bell states ordered as {|Φ^+⟩,|Φ^-⟩,|Ψ^+⟩,|Ψ^-⟩} for some eigenvalues. 			
				
				
	
	
				As in the projection step, the effect of applying a random unitary is restricted to the case T_i=0 and can be done with only LOCC. The importance of this step lies in the following:
				
					
  * After the twirling step, the resulting two qubit state is a convex combination of Bell diagonal states (Corollary <ref>). This simplifies the analysis in the rest of the proof.
					
  * This step decouples ρ̃^i_Â_iB̂_iC_iD_i from other registers while maintaining the entanglement of ρ̃^i_Â_iB̂_i; see Lemma <ref> below for the formal statement. This property is crucial later on, in Section <ref>. 
				
			

			

  §.§.§ Properties of the modified protocol

			
			Protocol <ref> can be described mathematically by an application of a sequence of maps one after the other. The maps describe both the actions of the verifier defined by the protocol as well as the actions of the measurement devices.  We denote these maps by
			
    𝒩_i:R_i-1→ R_iÂ_iB̂_iA_iB_iC_iD_iX_iY_iW_i  .

			The register R_i-1 holds here the state of the uncharacterised devices in the beginning of the i'th round. That is, R_i-1 includes the state ϕ^i produced by the source as well as any other information kept by the measurement devices. R_i describes a register which can be used as internal memory for the devices.  
			
			The final state in the end of Protocol <ref> is denoted by 
			
    τ = τ_ÂB̂ABCDXYTW

			and the state conditioned on not aborting by τ_|Ω.
			
			We now present 3 statements regarding the modified protocol. All the proofs are  rather simple and are given in Appendix <ref>.
		
			For start, it follows from the definition of Protocol <ref> that the observed statistic of ρ (the state in the end of Protocol <ref>) and τ (the state in the end of Protocol <ref>) are the same. This, in particular, implies that the probabilities of aborting Protocol <ref> and Protocol <ref> are identical. 
			
				The observed statistics and, hence, the probabilities of aborting Protocol <ref> and Protocol <ref> are the same. That is,
				ρ_ABXYTW = τ_ABXYTW and
				[Ω]_ρ = [Ω]_τ.
			
			
			Second, as mentioned in the previous section, the final state of Protocol <ref>, τ, has the property that for any i∈[n] the registers Â_i B̂_i are decoupled from the other registers. This can be shown using the structure of the state given in Equation (<ref>). 
			The formal statement needed in the next sections is given in the next lemma.
		
			
				Let τ denote the state after all rounds of Protocol <ref> (before conditioning on Ω).
				For every i∈[n] let K include all registers different than Â_i B̂_iC_iD_iT_i such that we can write 
				
    τ_ÂB̂ABCDXYTW = τ_Â_i B̂_iC_iD_iT_iK .
 
				Then,
				
    H(Â_i|B̂_iC_iD_iT_iK)_τ = H(Â_i|B̂_iC_iD_iT_i)_τ .

			

			The last thing which will be of use later is that ρ_|Ω is at least as entangled as τ_|Ω. That is, if one can distill |Φ^L⟩ from τ_|Ω then one can also distill |Φ^L⟩, for the same L, from ρ_|Ω 
			This follows from the fact that both modifications described above can be implemented using LOCC, and hence they cannot increase the entanglement. The formal statement is given in the last lemma of this section. 
	
			
				Let Γ denote the LOCC protocol used to distill 
				|Φ^L⟩= 1/√(L)∑_i=1^L |i⟩|i⟩
				from τ_|Ω with error probability ε. 
				Then, there exists another LOCC protocol Δ which can be used to distill |Φ^L⟩ from ρ_|Ω with the same error probability.
			

			Lemma <ref> implies that instead of proving that there exists an entanglement distillation protocol starting from ρ_|Ω one can prove that there exists an entanglement distillation protocol starting from τ_|Ω. The advantage of doing this is that τ_|Ω has some nice properties as was shown above. These will be of use in our proof given in the next sections. 
			We emphasise again that Protocol <ref> acts just as a step in the proof. This is not a real protocol which we expect the verifier to implement in order to verify that the state produced by the source is highly entangled. 
	

	
	

 §.§ Single-round bound on the von Neumann entropy

	
		The goal of the current section is to upper bound the conditional von Neumann entropy H(Â_i|B̂_i) of the states produced by the source and kept in the memory in Protocol <ref>. As explained in Section <ref>, a negative value of the conditional von Neumann entropy can be used to quantify the amount of entanglement present in the considered state. While there are many ways to quantify  entanglement, the conditional von Neumann entropy is the one relevant for our proof technique (as will become clear below). 
			
		The first lemma of this section was already presented as Lemma <ref> in Section <ref>.
		To simplify the equations in the lemmas below we use the notation of a Bell violation β∈[2,2√(2)] instead of the winning probability ω∈[3/4,2+√(2)/4] (used in Lemma <ref>). The two are related via ω=1/2+β/8; the transformation back to ω will be done in the end.
			
		
			For any Bell diagonal state σ_Â_iB̂_i as in Equation (<ref>)  that can be used to violate the CHSH inequality with violation β∈[2,2√(2)],
			
    H(Â_i|B̂_i)_σ≤ℋ(β) - 1  ,

			where
			
    ℋ(β) = 2h(1/2-β/4√(2))

			and h is the binary entropy function.
		
	
		The function ℋ(β) - 1 is plotted in Figure <ref> as a function of the CHSH violation β and the winning probability ω.
	
		The proof is inspired by the work of <cit.>, though we derive a bound on a different quantity. Neither result follows from the other.
		We give the proof sketch here; the full details are given in Appendix <ref>.
		
		
			First note that 
			
    H(Â_i|B̂_i)  = H(Â_iB̂_i) - H(B̂_i) = H(Â_iB̂_i) -1

			since the marginal σ_B̂_i is a completely mixed qubit state (for a Bell diagonal state σ_Â_iB̂_i). 
			
			We are left to upper bound H(Â_iB̂_i) which, given that the state is Bell diagonal, is simply the Shannon entropy H(λ⃗) of the probability distribution λ⃗=(λ_Φ^+,λ_Φ^-,λ_Ψ^+,λ_Ψ^-) defined by the four eigenvalues of σ.[This observation was already made in <cit.>. In the context of <cit.>, the eigenvalues λ⃗ are known. What we do here can be seen as an extension to the case where only the Bell violation is known and not the eigenvalues.] Hence, our goal is to maximise H(λ⃗) under the constraint of having the correct Bell violation β.  
			
			Following <cit.> and <cit.> we translate the constraint on the violation of the state to the following constraint on the eigenvalues:
			
    β = max{    2√(2)√((λ_Φ^+-λ_Ψ^+)^2+(λ_Φ^--λ_Ψ^-)^2) , 
        2√(2)√((λ_Φ^+-λ_Ψ^-)^2+(λ_Φ^--λ_Ψ^+)^2) , 
        2√(2)√((λ_Φ^+-λ_Φ^-)^2+(λ_Ψ^+-λ_Ψ^-)^2)} .

	
			Using the symmetry of our problem (e.g., under the exchange λ_Ψ^+↔λ_Ψ^-) one can simplify the above constraint and write the optimisation problem of interest as
			
    max     H(λ⃗) 
    s.t.     λ_Φ^+ = 1/2(1- λ_Ψ^- - λ_Φ^- + √(β^2/8 - (λ_Ψ^- - λ_Φ^-)^2)) 
       λ_Φ^+,λ_Ψ^+,λ_Φ^-,λ_Ψ^-≥ 0 
       λ_Φ^++λ_Ψ^++λ_Φ^-+λ_Ψ^- =1

			
			The constraints of the optimisation problem imply that we can write H(λ⃗) as a function of only two variables, λ_Ψ^- and λ_Φ^-, for any value of β. As an example, H(λ⃗) is presented in Figure <ref> for β=2.5.
			
	
			One can solve this optimisation problem numerically; the solution is given by  
			
    λ_Φ^+^*=  (1/2-β/4√(2))^2  ;   λ_Ψ^+^* = (1/2+β/4√(2))^2  ; 
       λ_Φ^-^* = λ_Ψ^-^* = (1/2-β/4√(2))(1/2+β/4√(2))   .

			
			
			
			Now that we have a solution in hand, we can verify that it is indeed the correct local optimal solution. This can be done by taking the derivatives in the relevant directions and verifying that the point given in Equation (<ref>) is indeed a maxima.
		
			
		Next, we extend the claim of Lemma <ref> also to convex combinations of Bell diagonal states. This can be done easily using the definition of the conditional entropy. The proof is given in Appendix <ref>.
			
		
			Let ℋ(β) be as in Equation (<ref>). 
			Then, for any state σ_Â_iB̂_iC_iD_i as in Equation (<ref>) that can be used to violate the CHSH inequality with violation β∈[2,2√(2)],
			
    H(Â_i|B̂_iC_iD_i)_σ≤ℋ(β) - 1  .

		
	
		Two remarks are in order:
		
			
  * The derived upper bound on H(Â_i|B̂_iC_iD_i) is tight; it is saturated by the Bell diagonal state defined via the eigenvalues given in Equation (<ref>). 
			
  * As can be seen from Figure <ref>, there is a regime of parameters  (β⪅ 2.2) in which the conditional entropy is positive even though the state violates the CHSH inequality and, hence, is entangled. Indeed, it is known that some states, e.g., the Werner state, can be used to violate the CHSH inequality while presenting positive conditional entropy <cit.>. This implies that the conditional entropy is not the optimal quantity to use when certifying entanglement in a DI manner. Yet, it is the relevant quantity when bounding the operationally distillable entanglement (using the known techniques) as we do below.
		
	
		For the coming steps of our proof, we need an upper bound on
		
    sup_σ∈Σ H(Â_i|B̂_iA_iB_iC_iD_iX_iY_i)_𝒩_i(σ) ,

		where 𝒩_i describes the maps defining the rounds of Protocol <ref>, as in Equation (<ref>), and
		Σ describes the set of possible states for which Protocol <ref> does not abort. 
		On the conceptual level, the protocol does not abort when the observed frequency defined by the registers W imply that the average Bell violation is sufficiently high.[On the technical level we will need to consider some further details; see Section <ref>.] Thus, we shall now consider the set Σ defined as Σ = {σ | w(σ) ≥ω_th} where w(σ) is the winning probability in the CHSH game of the state σ and ω_th is some threshold winning probability. 
		
		The following lemma can be proven using the above lemmas together with the definition of the conditional entropy and the transformation between β and ω; see Appendix <ref> for the proof. 
		
			For any ω_th∈[3/4,2+√(2)/4], let Σ = {σ | w(σ) ≥ω_th} . Then,
			
    sup_σ∈Σ H(Â_i|B̂_iA_iB_iC_iD_iX_iY_i)_𝒩_i(σ)≤(1-γ) · g(ω_th)  ,

			where 
			
    g(ω_th)=2h(1/2-2ω_th -1/√(2)) -1

			 and	h is the binary entropy function.
		


	
	

 §.§ Upper bound on the total smooth max-entropy

	
		As mentioned in Section <ref>, a lower bound on the one-shot distillable entanglement can be calculated using the conditional smooth max-entropy H_max^ε_smo. 
		The following quantitive relation was derived in <cit.> :
		
			For any θ_ÂB̂, ε_dist∈[ 0,1], and ε_smo∈ 0,√(ε_dist)) there exists a one-way entanglement distillation protocol Γ, utilising classical communication from Alice to Bob, such that
			
    F(Φ^L,Γ(θ_ÂB̂))≥ 1-ε_dist,

			where Φ^L is a maximally entangled state of Schmidt rank L for
			
    log L=-H_max^ε_smo(Â|B̂)_θ-4log(  1/√(ε_dist)-ε_smo)   .

		
	
		The objective of this section is, thus, to supply a negative upper bound on 
		
    H^ε_smo_max(Â|B̂ABCDXY)_τ_|Ω .

		
		
		We do this using the entropy accumulation theorem (EAT) <cit.>. 
		The EAT gives a way of bounding conditional smooth min- and max-entropies in sequential processes in which certain systems of interest are being produced one after the other in overall n steps (not necessarily in an IID way). It, roughly, states that the total amount of smooth entropy accumulated during the entire process is n times the von Neumann entropy produced in a single step of the process. In our context, this translates to saying that the total amount of smooth max-entropy can be related to the von Neumann entropy considered in Section <ref>.
		All the definitions and statements of the EAT  which are necessary for our work are presented in Section <ref>.
	
		

  §.§.§ Prerequisites of the EAT

	
			Before applying the EAT, we show that the prerequisites of the EAT hold. 
			
			
			Specifically, 𝒩_i:R_i-1→ R_iÂ_iB̂_iA_iB_iC_iD_iX_iY_iW_i are the channels defined by Protocol <ref> and will act as our “EAT channels”.
			We need to show that these are indeed EAT channels, i.e., that they fulfil Definition <ref> (see Section <ref>). To verify that this is the case note the following:
			
				
  * W_i are classical finite-dimensional systems. d_Â_i = 2 (due to the projection step of Protocol <ref>).
				
  * The classical value W_i is a function of A_iB_iX_iY_i. Hence, it can be measured from the output of the EAT channels (for any input state) without modifying the state.
				
  * The necessary Markov-chain conditions hold, as stated in the next lemma.
			
	
			
				For all i∈[n] and any initial state,
				
    Â_1^i-1↔B̂_1^i-1A_1^i-1B_1^i-1C_1^i-1D_1^i-1X_1^i-1Y_1^i-1 E  ↔B̂_iA_iB_iC_iD_iX_iY_i

				holds for the final state  τ of Protocol <ref>.
			
			The crucial ingredient in the proof is Lemma <ref>, which asserts that the twirling step (Step <ref> of Protocol <ref>) decouples the states kept in each round from the other registers; see Appendix <ref> for the details.
			It now becomes clear why the twirling step is necessary – without it the required Markov-chain conditions do not hold. 
			For example, one can imagine a source that creates two bipartite states ϕ^1 and ϕ^2  entangled with one another. In such a case the above Markov-chain conditions do not hold. 
			Step <ref> therefore enforces the necessary conditions while not destroying the entanglement between Â_i and B̂_i.

		

  §.§.§ Max-tradeoff function

	
			To apply the EAT we need to define a concave max-tradeoff function, as defined in Definition <ref>. We construct one by following similar steps used to define min-tradeoff functions in <cit.>.
				
			Let p be a probability distribution over {0,1,⊥} resulting from the observed data w, i.e., p(w̃)=| { i | w_i = w̃} |/n for w̃∈{0,1,⊥},
			and define 
			
    Σ^p = {σ | 𝒩_i(σ)_W_i = p } .

			
			Below we focus on probability distributions for which p(0)+p(1)=γ. The reason is that for p(0)+p(1)≠γ the set Σ^p is empty and the condition on the max-tradeoff function becomes trivial. 
			For such p we can write ω=p(1)/p(0)+p(1)=p(1)/γ.
			
			Lemma <ref> can now be used to define a max-tradeoff function for any p with p(1)/γ∈[3/4,2+√(2)/4]. 
			Define a function f by  
			
    f(p)  = (1-γ) · g(p(1)/γ)    p(1)/γ∈[0,2+√(2)/4] 
    γ-1   p(1)/γ∈[2+√(2)/4,1]  ,

			where g is as in Lemma <ref>:
			
    g(ω)=2h(1/2-2ω -1/√(2)) -1

			for h the binary entropy function.
	
			
			From Lemma <ref> we have 
			
    sup_σ∈Σ^p H(Â_i|B̂_iA_iB_iC_iD_iX_iY_i)_𝒩_i(σ)≤(1-γ) · g(p(1)/γ)  ,

			and, hence, it follows that any choice of f_max(p) that is differentiable and satisfies f_max(p) ≥ f(p) for all p will be a valid max-tradeoff function for our EAT channels.
			
			For the final bound derived using the EAT to be meaningful we choose f_max for which ▿ f_max_∞ is finite (for f given above the derivative at p(1)/γ=2+√(2)/4 is infinite).
			Let 
			
    f_max(p,p_t) = 
    					f(p)      p(1) ≤ p_t(1) 
    
    					a(p_t) · p(1) + b(p_t)     p(1)> p_t(1) ,

			where p_t is a probability distribution over {0,1,⊥} and
			
    a(p_t)= d/dp(1) f(p)|_p_t    and     b(p_t) =  f(p_t)-a(p_t)· p_t(1).

			
			It follows from the definition of a and b given in the above equation that f_max is differentiable and, for any p_t, ▿ f_max(·,p_t) _∞≤ a(p_t). 
			Furthermore, as f is a concave function, we also have that f_max(p) ≥ f(p) for all p. Thus, f_max(p) is indeed a max-tradeoff function.
	
		

  §.§.§ Applying the EAT

		
			We are finally ready to apply the EAT, stated as Theorem <ref>, to derive an upper-bound on the smooth max-entropy. 
			The smooth max-entropy rate is governed by the following functions:
			
    f(p) =  
    					(1-γ) · g(p(1)/γ)    p(1)/γ∈[0,2+√(2)/4] 
    γ-1   p(1)/γ∈[2+√(2)/4,1]  ,
    					
       f_max(p,p_t) = 
    					
    						f(p)     p(1) ≤ p_t(1)  
    d/dp(1) f(p)|_p_t· p(1)+ ( f(p_t) -	d/dp(1) f(p)|_p_t· p_t(1) )    p(1)> p_t(1) ,
    					
       η(p,p_t,ε_smo,ε_snd) =  
    					f_max(p, p_t) + 1/√(n)2( log 5 + | d/dp(1) g(p)|_p_t| )√(1-2 log (ε_smo·ε_snd)) , 
       η_opt(ε_smo, ε_snd) =
    					 min_p_t: 3/4 < p_t(1)/γ < 2+√(2)/4 η(ω_expγ - δ_est,p_t,ε_smo,ε_snd) .

			
		
			
				For any source and measurement device in the considered setting, let τ the state generated using Protocol <ref>, Ω the event that Protocol <ref> does not abort, and τ_|Ω the state conditioned on Ω.
				Then, for any ε_smo,ε_snd∈ (0,1), either Protocol <ref> aborts with probability greater than 1-ε_snd or
				
    H^ε_smo_max( Â|B̂ABCDXY )_τ_|Ω < n·η_opt(ε_smo,ε_snd)  ,

				where  η_opt is defined in Equation (<ref>). 
			
			
			
				In Sections <ref> and <ref> we showed that the prerequisites of the EAT hold and that f_max defined above is a max-tradeoff function for the EAT channels defined via Protocol <ref>. The statement of the lemma then follows by applying the EAT, stated as Theorem <ref>, with the above choices.
			

	

	
	

 §.§ Final statement


		We are ready to prove our main theorem, Theorem <ref>. For convenience, we restate the theorem here. 
		𝒮^honest and 𝒟^honest are as discussed in Section <ref> (or see Section <ref> below).
		
		<ref>[Main theorem]
			For any n∈ℕ_+, ε_dist,ε_snd∈ [0,1], and ε_smo∈[0,√(ε_dist)), Protocol <ref> is a DIEC protocol with:
			
				
  * Noise-tolerance (completeness): The probability that P aborts when applied on any ϕ^honest∈𝒮^honest using honest measurement devices from 𝒟^honest  is at most ε_cmp≤exp(- 2 nδ_est^2 ).
				
  * Entanglement certification (soundness): For any source and measurement devices in the considered setting, either Protocol <ref> aborts with probability greater than 1-ε_snd when applied on ϕ or 
				E_D^n,ε_dist(ρ_|Ω) ≥ r for r=log(L)/ n and
				
    log L= - n·η_opt(ε_smo,ε_snd) -4log(  1/√(ε_dist)-ε_smo) ,

				where η_opt is defined in Equation (<ref>). 
			
		
		
		The theorem follows from the combination of Lemmas <ref> and <ref> given below.
		
		

  §.§.§ Noise-tolerance (completeness)

			
			As the honest source and devices we choose to consider a source that produces identical and independent copies of a state ϕ^i=σ and  measurement devices that apply the same measurements in each round when they are used. The state σ and the measurements are such that the winning probability achieved in the CHSH game is at least ω_exp. 
			For example, one can choose 𝒟^honest to include the measurement devices that apply the optimal measurements performed in the CHSH game and the
			 set 𝒮^honest to include all states ϕ^honest=σ^⊗ n for σ any noisy maximally entangled state that will result in winning probability ≥ω_exp.
			The following lemma bounds the probability of Protocol <ref> aborting when using an honest device as above.
	
			
				The probability that Protocol <ref> aborts for an honest implementation discussed above is at most ε_cmp≤exp(- 2 nδ_est^2 ).		
			
			
			
				The protocol aborts in Step <ref> when the sum of the W_i obtained during the test rounds is not sufficiently high (this happens when the estimated Bell violation is too low or when not enough test rounds were chosen). In the honest implementation the products χ(T_i=1) W_i are IID RVs with 𝔼[ χ(T_i=1) W_i] = ω_expγ. Therefore, we can use Hoeffding's inequality:
				
    ε_cmp =  [ ∑_i χ(T_i=1)  W_i ≤(ω_expγ - δ_est) · n ] ≤exp(- 2 n δ_est^2 )  .

			
	
			
		

  §.§.§ Entanglement certification (soundness)

		
			
				For any source and measurement devices in the considered setting, denote by ρ_|Ω the state in the end of the DIEC protocol, Protocol <ref>, conditioned on not aborting.
				 Let ε_dist,ε_snd∈[0,1] and ε_smo∈[0,√(ε_dist)).
				
				Then, either Protocol <ref> aborts with probability greater than 1-ε_snd 
				or E_D^n,ε_dist(ρ_|Ω) ≥ r for r=log(L)/ n and
				
    log L= - n·η_opt(ε_smo,ε_snd) -4log(  1/√(ε_dist)-ε_smo) ,

				where η_opt is defined in Equation (<ref>). 
			
			
			
				Given a source and measurement devices in the considered setting, we first consider the hypothetical scenario in which Protocol <ref> is being ran using the given devices.  
				Putting Lemmas <ref> and <ref> together we learn that
				either Protocol <ref> aborts with probability greater than 1-ε_snd or
				there exists an entanglement distillation protocol Γ such that  
				
    F( Γ(τ_|Ω), |Φ^L⟩⟨Φ^L|) ≤ε_dist ,

				for L as in Equation (<ref>).
				
				According to Lemma <ref>, Equation (<ref>) implies that there exists an entanglement distillation protocol Δ such that  
				
    F( Δ(ρ_|Ω), |Φ^L⟩⟨Φ^L|) ≤ε_dist ,

				with the same choice of parameters, i.e., L is as in Equation (<ref>).
				By the definition of the one-shot distillable entanglement, given in Equation (<ref>), we get that E_D^n,ε_dist(ρ_|Ω) ≥ r for r=log(L)/ n.
		
				Finally, Lemma <ref> tells us that if  Protocol <ref> aborts with probability greater than 1-ε_snd then Protocol <ref> aborts with probability greater than 1-ε_snd as well.
							
				Combining the above observations, the lemma follows.
			
	
			The resulting distillable entanglement rates, (log L)/n, are plotted in Figure <ref> as a function of the expected winning probability in the CHSH game ω_exp for different values of n. As seen from the figure, as the number of rounds of the protocol n increases our rate approach the optimal rate, for our proof technique, given by the IID asymptotic rate; see Section <ref> for further details. 
			
		
			We remark that one can also derive improved rates for finite number of rounds n by considering a slightly modified version of our DIEC protocol, similarly to what was done in <cit.>. As the modification of the protocol, the analysis, and the resulting rates follow directly by combining the analysis done here and that of <cit.> we do not present the details here. 
	




§ OPEN QUESTIONS

	
	

  §.§.§ Tightness of our result

	
		As mention in the previous sections, if one chooses to take the path of bounding the one-shot distillable entanglement using the smooth max-entropy, as done in the current work, then our quantitive results are tight to first order of n. 
		However, this may not be the only way to go. Considering other proof techniques is crucial in order to achieve a result in which there is positive certified distillable entanglement regime whenever a violation of the CHSH inequality is being detected.
		
		In general, it is known that there are Bell inequalities which can be violated by bound entangled states, i.e., entangled state which cannot be distilled <cit.> and, thus, for some Bell inequalities a zero rate regime, similar to the one observed here, is of a fundamental nature. 
		However, for the CHSH inequality this is not the case <cit.>: bound entangled states cannot violate the CHSH inequality. Hence, asymptotically, one should be able to certify distillable entanglement for any violation. 
				
				
		One way of assessing how far our results are from the optimal results, achievable using any proof technique, is to find upper bounds on the asymptotic distillable entanglement of the states achieving the highest conditional entropy given their Bell violation (see Section <ref>).
		One possible starting point is to consider the sets of states described in <cit.>. 
		
	

  §.§.§ Possible extensions of our result

	
		There are many possible ways of extending our work.
	
		
			
  * Our protocol and proof technique can also be modified to work with other Bell inequalities instead of the CHSH. This can potentially increase the rates when considering different types of honest sources of entanglement. For example, if one is interested in a source that emits partially entangled states then it probably makes more sense to consider the tilted CHSH inequalities <cit.> rather than the CHSH. The only part of the proof which requiers a modification is the upper bound on the von Neumann entropy for a single round given in Section <ref>. We remark that one can achieve such a bound for any Bell inequality for which a robust self-testing result is known, e.g., <cit.>, combined with the continuity of the von Neumann entropy <cit.>. However, it is likely that such an approach will lead to relatively weak quantitive results. Thus, considering the von Neumann entropy directly for other Bell inequalities is a more promising direction. 
		
			
  * An important direction to consider is the extension of our work to entanglement shared between more than two parties. This can then be used, for example, to consider scenarios and results as those derived in <cit.> and extend them beyond the IID setting.
			
			
  * Another possible extension of the analysis done here is to consider DIEC protocols that employ the more general (but less fundamental) separability preserving operations <cit.> rather than LOCC. To do so one should first consider one-shot distillation protocols which use separability preserving operations <cit.>.

			
  * One can also try to bound other operational measures of  entanglement. 
			For example, it will be interesting to lower bound the one-shot entanglement cost.[In a related work <cit.>, a lower bound on the entanglement of formation of a quantum state (closely related to its entanglement cost) as a function of its Bell violation is derived. The considered setting and type of statement are different than the ones presented here and are not operational in our sense. For further details see <cit.>.] Such a bound can be viewed as a “dual” of the one achieved in this work.  
			Given the results of <cit.>, it is plausible that a similar proof technique as presented here can be used to achieve such a bound.
		
			
  * In a different direction, it can also be of interest to consider other settings than the one considered in the current work (as described in Section <ref>). As different experiments may require different sets of assumptions, formulating other interesting scenarios and modifying the proof  accordingly can be relevant. 
			
			
  * Similarly, one may consider device-dependent and semi-DI versions of our work. For example, it is possible to study a one-sided DI scenario in which one of the measurement devices is completely characterised. 
			The only part of our proof that needs be to modified in such a case is that given in Section <ref> while replacing Bell inequalities with Steering inequalities <cit.>. The rest of the proof will follow as is.
			The additional assumptions can potentially result in certification rates higher than the ones presented in the current work. 
		
			
		
	
		


§ ACKNOWLEDGMENTS

We thank Renato Renner, David Sutter, and Thomas Vidick for helpful discussions.
We also thank Valerio Scarani for inviting RAF to visit his group at CQT Singapore, where the work on this project was initiated. 
RAF is supported by the Swiss National Science Foundation (grant No. 200020-135048) via the National Centre of Competence in Research “Quantum Science and Technology” and by the US Air Force Office of Scientific Research (grant No. FA9550-16-1-0245).	 
JDB  acknowledges  support  from the Swiss National Science Foundation (SNSF), through the NCCR QSIT and the Grant number PP00P2-150579.	









§ PROOFS OF THE LEMMAS IN SECTION <REF>


<ref>
	Consider a scenario in which the projection to the two qubit space is applied on the state ϕ^i directly after it is produced by the source in the i'th round (i.e., before choosing the value of T_i). Denote the resulting state in the end of the i'th round in such a case by ρ̅̅̅^i. Then 
	
    ρ̅̅̅^i_Â_iB̂_i A_iB_i C_i D_iX_iY_i = ρ̅^i_Â_iB̂_i A_iB_i C_i D_iX_iY_i ,

	where ρ̅^i is as defined in Equation (<ref>).


	Firstly, for the rounds in which T_i=0 there is clearly no difference between ρ̅̅̅^i_|T_i=0 and ρ̅^i_|T_i=0.
	We show that the same holds also when T_i=1. To this end we need to prove that  
	
    ρ̅̅̅^i_A_iB_iX_iY_i|T_i=1 = ρ̅^i_A_iB_iX_iY_i|T_i=1 .

	To see that this is indeed the case note that the successive application of the projections given in Equation (<ref>) and of the measurement as applied to create ρ̅̅̅^i has the exact same effect as applying the measurement alone.
	Indeed,
	
    Π_a|x^A_i = ∑_c_iΠ_a|x^A_iΠ^A_i_c_i

	and similarly for Bob. Therefore, after tracing out the block registers C_i and D_i, both final states are identical.
	
	As the probability for choosing T_i=0 is, obviously, independent of when the projection is made the combination of the above statements implies the lemma.



<ref>
	The observed statistics and, hence, the probabilities of aborting Protocol <ref> and Protocol <ref> are the same. That is,
	ρ_ABXYTW = τ_ABXYTW and
	[Ω]_ρ = [Ω]_τ.


	The only difference between Protocol <ref> and Protocol <ref> is in the rounds in which T_i=0. The observed statistics over ABXYT and, hence, also W, depend however only on the rounds in which T_i=1. Thus, ρ_ABXYTW = τ_ABXYTW . The event Ω is defined according to the registers W and therefore the lemma follows.



<ref>
	Let τ denote the state after all rounds of Protocol <ref> (before conditioning on Ω).
	For every i∈[n] let K include all registers different than Â_i B̂_iC_iD_iT_i such that we can write 
	
    τ_ÂB̂ABCDXYTW = τ_Â_i B̂_iC_iD_iT_iK .
 
	Then,
	
    H(Â_i|B̂_iC_iD_iT_iK) = H(Â_i|B̂_iC_iD_iT_i)  .




	We prove below that for all c_i and d_i we have
	
    H(Â_i|B̂_iT_iK,C_i=c_i,D_i=d_i) = H(Â_i|B̂_iT_i,C_i=c_i,D_i=d_i)  .

	Then, using the definition of the conditional entropy we write
	
    H(Â_i|B̂_iC_iD_iT_iK)    = ∑_c_i,d_i p(c_i,d_i) H(Â_i|B̂_iT_iK,C_i=c_i,D_i=d_i) 
       = ∑_c_i,d_i p(c_i,d_i)H(Â_i|B̂_iT_i,C_i=c_i,D_i=d_i) 
       = H(Â_i|B̂_iC_iD_iT_i)

	and the lemma follows.
	We are therefore left to prove that Equation (<ref>) holds. 			

	We split the proof to two parts corresponding to the different values of T_i.
	When T_i=1 the register Â_i has a deterministic value. Hence,
	
    H(Â_i|B̂_iK,C_i=c_i,D_i=d_i,T_i=1) = H(Â_i|B̂_i,C_i=c_i,D_i=d_i,T_i=1) = 0  .

	
	The interesting case is thus T_i=0. 
	For T_i=0 we can use the Bell diagonal structure of the state as given in Equation (<ref>). Consider the purification of the state τ_Â_iB̂_i|c_i,d_i:
	
    |τ⟩_Â_iB̂_iF_i^c_i,d_i =   √(λ_Φ^+)|Φ^+⟩_Â_iB̂_i|1⟩_F_i	+
    		√(λ_Φ^-)|Φ^-⟩_Â_iB̂_i|2⟩_F_i
       + √(λ_Ψ^+)|Ψ^+⟩_Â_iB̂_i|3⟩_F_i	+
    		√(λ_Ψ^-)|Ψ^-⟩_Â_iB̂_i|4⟩_F_i .

	
	Note that K does not include the information encoded in F_i by the definition of K.
	Thus, including the register F_i we must have 
	
    τ_Â_i B̂_iF_iK|C_i=c_i,D_i=d_i,T_i=0 = τ_Â_i B̂_iF_i|T_i=0⊗τ_K|C_i=c_i,D_i=d_i,T_i=0 .

	Moreover, we can freely trace F_i out while preserving the tensor product structure
	
	
    τ_Â_i B̂_iK|C_i=c_i,D_i=d_i,T_i=0 = τ_Â_i B̂_i|T_i=0⊗τ_K|C_i=c_i,D_i=d_i,T_i=0 ,

	from which it follows that 
	
    H(Â_i|B̂_iK,C_i=c_i,D_i=d_i,T_i=0) = H(Â_i|B̂_i,C_i=c_i,D_i=d_i,T_i=0)  .

	The combination of Equations (<ref>) and (<ref>), together with the definition of the conditional entropy, implies the lemma. 

<ref>
	Let Γ denote the LOCC protocol used to distill 
	|Φ^L⟩= 1/√(L)∑_i=1^L |i⟩|i⟩
	from τ_|Ω with error probability ε. 
	Then, there exists another LOCC protocol Δ which can be used to distill |Φ^L⟩ from ρ_|Ω with the same error probability.	


	The only difference between Protocol <ref> and Protocol <ref> is the addition of Steps <ref> and <ref>.
	
	These steps are such that their effect is restricted to the round in which they are applied. That is, whether we apply them or not in round i does not effect all other rounds j≠ i. In other words, they commute with the rest of the operations made in the protocol. We can therefore postpone them (for all steps i with T_i=0) to the end of the protocol. 
	
	Furthermore, according to Lemma <ref> the additional steps do not change the observed statistics and the probability of the event Ω. Thus, we can also postpone them for after making the projection on Ω. 
	
	Denoting the combination of all the projections and rotations for all relevant rounds by the map Λ, the above means that the relation
	
    Λ(ρ_|Ω) = τ_|Ω

	holds. Moreover, Λ can be implemented using only LOCC by definition of the Steps <ref> and <ref>. 
	
	Let Γ denote the LOCC protocol used to distill |Φ^L⟩ from τ_|Ω with error probability ε. We define
	
    Δ = Γ·Λ

	to be the successive application of Λ and Γ. As both are LOCC protocols, Δ by itself is an LOCC protocol. 
	From Equations (<ref>) and (<ref>) it follows that 
	
    Δ(ρ_|Ω) = Γ( Λ(ρ_|Ω) ) = Γ( τ_|Ω)  .

	Additionally, the operation Λ alway succeeds (i.e., Equation (<ref>) is always true). 
	Therefore, Δ is an LOCC protocol  which can be used to distill |Φ^L⟩ from ρ_|Ω with the same error probability as Γ.






§ PROOFS OF THE LEMMAS IN SECTION <REF>


<ref>
	For any Bell diagonal state σ_Â_iB̂_i as in Equation (<ref>)  that can be used to violate the CHSH inequality with violation β∈[2,2√(2)],
	
    H(Â_i|B̂_i)_σ≤ℋ(β) - 1  ,

	where
	
    ℋ(β) = 2h(1/2-β/4√(2))

	and h is the binary entropy function.


	First note that 
	
    H(Â_i|B̂_i)  = H(Â_iB̂_i) - H(B̂_i) = H(Â_iB̂_i) -1

	since the marginal σ_B̂_i is a completely mixed qubit state. 
	
	We are left to upper bound H(Â_iB̂_i) which, given that the state is Bell diagonal, is simply the Shannon entropy H(λ⃗) of the probability distribution λ⃗=(λ_Φ^+,λ_Φ^-,λ_Ψ^+,λ_Ψ^-) defined by the four eigenvalues of σ. Hence, our goal is to maximise H(λ⃗) under the constraint of having the correct Bell violation β.  
	
	Following <cit.> and <cit.> we translate the constraint on the violation of the state to the following constraint on the eigenvalues:
	
    β = max{    2√(2)√((λ_Φ^+-λ_Ψ^+)^2+(λ_Φ^--λ_Ψ^-)^2) , 
        2√(2)√((λ_Φ^+-λ_Ψ^-)^2+(λ_Φ^--λ_Ψ^+)^2) , 
        2√(2)√((λ_Φ^+-λ_Φ^-)^2+(λ_Ψ^+-λ_Ψ^-)^2)} .

	
	To simplify the constraint we observe that both the objective function H(λ⃗) and the above constraint are invariant under the exchange of the eigenvalues with one another. Thus, we can assume without loss of generality that the optimal solution is restricted by, say, the first term in Equation (<ref>). That is, the eigenvalues of the state that maximise the entropy are such that 
	
    β = 2√(2)√((λ_Φ^+-λ_Ψ^+)^2+(λ_Φ^--λ_Ψ^-)^2)
       β≤ 2√(2)√((λ_Φ^+-λ_Ψ^-)^2+(λ_Φ^--λ_Ψ^+)^2)
       β≤ 2√(2)√((λ_Φ^+-λ_Φ^-)^2+(λ_Ψ^+-λ_Ψ^-)^2).

	To see that this is indeed the case one can assume by contradiction that the second term in Equation (<ref>), and not the first one, is the one restricting the optimal solution. Then, by exchanging the values of λ_Ψ^+ with λ_Ψ^- we get a different state, which is restricted by the first term instead of the second one, but attains the same value H(λ⃗). Hence, the solution defined by this exchange must be an optimal solution as well and we can work with it instead. 
	
	We can therefore restrict our attention to the optimisation problem 
	
    λ⃗max     H(λ⃗) 
    s.t.     β = 2√(2)√((λ_Φ^+-λ_Ψ^+)^2+(λ_Φ^--λ_Ψ^-)^2)
       λ_Φ^+,λ_Ψ^+,λ_Φ^-,λ_Ψ^-≥ 0 
       λ_Φ^++λ_Ψ^++λ_Φ^-+λ_Ψ^- =1


	The constraints stated in the optimisation problem given as Equation (<ref>) imply the constraint:
	
    λ_Φ^+ = 1/2(1- λ_Φ^- - λ_Ψ^- + √(β^2/8 - (λ_Φ^- - λ_Ψ^-)^2))  .

	Hence, H(λ⃗) can be written as a function of only two variables, λ_Φ^- and λ_Ψ^-, for any value of β.

	Let us identify the region of interest in this plane. First, we have the linear conditions
	
    λ_Φ^-,λ_Ψ^-≥ 0 
    λ_Φ^- + λ_Ψ^-≤ 1

	Noticing that the optimisation (<ref>) is invariant under exchange of (λ_Φ^+,λ_Ψ^+) and (λ_Φ^-,λ_Ψ^-), we can restrict our attention to solutions for which (λ_Φ^--λ_Ψ^-)^2 ≤ (λ_Φ^+-λ_Ψ^+)^2. Expressed in terms of our two independent variable λ_Φ^- and λ_Ψ^-, this condition is equivalent to
	
    |λ_Φ^- - λ_Ψ^-|≤β/4.

	This condition defines a diagonal band of interest in the space of λ_Φ^- and λ_Ψ^-.
	
	Using the condition λ_Φ^+≥ 0, we further restrict our region of interest:
	
    (λ_Φ^--1/2)^2 + (λ_Ψ^--1/2)^2 ≥(β/4)^2

	This condition describes the outside of a disk centred at λ_Φ^-=λ_Ψ^-=1/2. For all β>2, this identifies a unique region within the set defined by (<ref>)-(<ref>). Our objective function, the entropy H(λ⃗) is presented in Figure <ref> on our region of interest for β=2.5.
	
	The above optimisation can thus be re-expressed in terms of only two variables as
	
    λ_Φ^-,λ_Ψ^-max     H(λ⃗) 
    s.t.     λ_Φ^+ = 1/2(1- λ_Φ^- - λ_Ψ^- + √(β^2/8 - (λ_Φ^- - λ_Ψ^-)^2)) 
       λ_Ψ^+ = 1/2(1- λ_Φ^- - λ_Ψ^- - √(β^2/8 - (λ_Φ^- - λ_Ψ^-)^2)) 
       λ_Φ^-,λ_Ψ^-≥ 0 
        (λ_Φ^--1/2)^2 + (λ_Ψ^--1/2)^2 ≥(β/4)^2.

	
	One can solve this optimisation problem numerically within this region; the solution is given by  
	
    λ_Φ^+^*=  (1/2-β/4√(2))^2  ; 
       λ_Ψ^+^* = (1/2+β/4√(2))^2  ; 
       λ_Φ^-^* = λ_Ψ^-^* = (1/2-β/4√(2))(1/2+β/4√(2))   .

	The white point in Figure <ref> denotes this solution.
	
	Now that we have a solution in hand, we can verify that it is indeed a correct solution (i.e., there are no numerical errors) which is locally optimal. To do so we need to check that the local gradient vanishes at our suggested solution in order to verify that it is indeed the maxima.
	
	The objective function of (<ref>) is invariant under the exchange λ_Φ^-↔λ_Ψ^-. Its derivative in the direction λ_Ψ^--λ_Φ^- must thus vanish at this point. To conclude about the local optimality of this solution, we are left to show that the derivative, on the curve λ_Φ^-=λ_Ψ^-, vanishes at the point given in Equation (<ref>).
	
	Under the constraint λ_Φ^-=λ_Ψ^-, H(λ⃗) can be written as a function of the single variable, say, λ_Ψ^-. Explicitly, it reads
	
    H(λ⃗) =  - 2 λ_Ψ^-log(λ_Ψ^-)
    		   -(1/2-λ_Ψ^- + β/4√(2))log(1/2-λ_Ψ^- + β/4√(2)) 
       - (1/2-λ_Ψ^- - β/4√(2))log(1/2-λ_Ψ^- - β/4√(2)) .

	
	Thus, 
	
    dH(λ⃗)/dλ_Ψ^- = log((1/2-λ_Ψ^-)^2-β/32) - 2log(λ_Ψ^-)

	and we have dH(λ⃗)/dλ_Ψ^-|_λ_Ψ^-=λ_Ψ^-^* =0 
	for λ_Ψ^-^* as in Equation (<ref>), as we were set to show.
	
	Therefore, we have identified a local optimum for our objective function. According to the plot given in Figure <ref>, this local optimum is also a global optimum for Equation (<ref>) and hence Equation (<ref>). As the values of the optimal eigenvalues, given in Equation (<ref>), depend only on the CHSH violation β we can write H(Â_iB̂_i) = H(λ⃗^*)=ℋ(β) as in Equation (<ref>).
	Combined with Equation (<ref>) the lemma follows. 




<ref>
	For any β∈[2,2√(2)] let ℋ(β) be as in Equation (<ref>). 
	Then, for any state σ_Â_iB̂_iC_iD_i as in Equation (<ref>) that can be used to violate the CHSH inequality with violation β,
	
    H(Â_i|B̂_iC_iD_i)_σ≤ℋ(β) - 1  .




	We use the convex combination structure of σ_Â_iB̂_iC_iD_i given in Equation (<ref>). 
	Let β^c_id_i be the violation of the conditional state σ_|c_i,d_i.  Then, 
	
    H(Â_i|B̂_iC_iD_i)    = ∑_c_i,d_i p(c_i,d_i)H(Â_i|B̂_i,C_i=c_i,D_i=d_i) 
       ≤∑_c_i,d_i p(c_i,d_i) (H(β^c_id_i) -1 )
       ≤ H(∑_c_i,d_i p(c_i,d_i)  β^c_id_i) -1 
       =  ℋ(β) -1  ,

	where the first equality follows from the definition of the conditional entropy, the second step holds due to  Lemma <ref>, in the third step we used the concavity of ℋ(β), and the last step follows from β = ∑_c_i,d_i p(c_i,d_i) β^c_id_i.



<ref>
	For any ω_th∈[3/4,2+√(2)/4], let Σ = {σ | w(σ) ≥ω_th} . Then,
	
    sup_σ∈Σ H(Â_i|B̂_iA_iB_iC_iD_iX_iY_i)_𝒩_i(σ)≤(1-γ) · g(ω_th)  ,

	where 
	
    g(ω_th)=2h(1/2-2ω_th -1/√(2)) -1

	 and	h is the binary entropy function.


	We start with the following sequence of equalities that holds for any σ:
	
    H(Â_i|B̂_iA_iB_iC_iD_iX_iY_i)_𝒩_i(σ) =   [A_i,B_i=⊥]· H(Â_i|B̂_iX_iY_iC_iD_i,A_i=⊥,B_i=⊥)_𝒩_i(σ)
        + [A_i,B_i≠⊥]· H(Â_i|B̂_iX_iY_iC_iD_i,A_i≠⊥,B_i≠⊥)_𝒩_i(σ)
    
    		=   [T_i=0]· H(Â_i|B̂_iA_iB_iC_iD_iX_iY_i,T_i=0)_𝒩_i(σ)
        + [T_i=1]· H(Â_i|B̂_iA_iB_iC_iD_iX_iY_i,T_i=1)_𝒩_i(σ)
     
    		=    (1-γ)· H(Â_i|B̂_iA_iB_iC_iD_iX_iY_i,T_i=0)_𝒩_i(σ)
        +γ· H(Â_i|B̂_iA_iB_iC_iD_iX_iY_i,T_i=1)_𝒩_i(σ)
    
    		=   (1-γ)· H(Â_i|B̂_iA_iB_iC_iD_iX_iY_i,T_i=0)_𝒩_i(σ)
    
    		=   (1-γ)· H(Â_i|B̂_iC_iD_i,T_i=0)_𝒩_i(σ)

	
	 
	To get Equation (<ref>) we used the definition of the conditional entropy. Equations (<ref>) and (<ref>) follow from the definition of Protocol <ref>. 
	Equation (<ref>) holds since, by definition, the registers Â_iB̂_i have a deterministic initialisation value when a test is performed (nothing is kept in them) and hence H(Â_i|B̂_iA_iB_iC_iD_iX_iY_i,T_i=1)_𝒩_i(σ)=0. 
	Finally, Equation (<ref>) follows from the fact that when T_i=0 A_iB_iX_iY_i are all ⊥.
	
	The lemma then follows by combining Equation (<ref>) and  Lemma <ref> while using the transformation β = 8ω_th-4 to replace β with ω_th in Equation (<ref>).





§ PROOFS OF THE LEMMAS IN SECTION <REF>


<ref>
	For all i∈[n] and any initial state,
	
    Â_1^i-1↔B̂_1^i-1A_1^i-1B_1^i-1C_1^i-1D_1^i-1X_1^i-1Y_1^i-1 E  ↔B̂_iA_iB_iC_iD_iX_iY_i

	holds for the final state  τ of Protocol <ref>.


	The Markov-chain conditions can be written using the mutual information as 
	
    I(Â_1^i-1 : B̂_iA_iB_iC_iD_iX_iY_i | B̂_1^i-1A_1^i-1B_1^i-1A_1^i-1B_1^i-1X_1^i-1Y_1^i-1 E) =0  .

	
	Using the chain rule for the mutual information the above equation can be alternatively written as 
	
    ∑_j∈ [i-1] I(Â_j : B̂_iA_iB_iC_iD_iX_iY_i | B̂_1^i-1A_1^i-1B_1^i-1A_1^i-1B_1^i-1X_1^i-1Y_1^i-1 E Â_1^j-1) = 0  .

	
	We now prove that for all i∈[n] and j∈ [i-1]
	
    I(Â_j : B̂_iA_iB_iC_iD_iX_iY_i | B̂_jA_jB_jC_jD_jX_jY_j) = 0  ,

	which, in turn, implies the lemma.
	
	To this end, we use the following sequence of equations
	
    H(Â_j | B̂_jA_jB_jC_jD_jX_jY_j) 	
    		   ≤ H(Â_j | B̂_j C_jD_jT_j) 
       =H(Â_j|B̂_jC_jD_jT_jK) 
       ≤ H(Â_j|B̂_jC_jD_jT_j A_jB_jX_jY_jB̂_iA_iB_iC_iD_iX_iY_i)  ,

	where K includes all registers of τ apart from Â_jB̂_jC_jD_jT_j such that we can write
	τ_ÂB̂ABCDXYTW = τ_Â_j B̂_jC_jD_jT_jK. In particular, K includes  
	A_jB_jX_jY_jB̂_̂îA_iB_iC_iD_iX_iY_i. 
	The first and last steps above are due to strong subadditivity of the entropy and the middle one follows from Lemma <ref>.
	
	Using the definition of the mutual information and Equation (<ref>) we get
	
    I(Â_j : B̂_iA_iB_iC_iD_iX_iY_i | B̂_jA_jB_jC_jD_jX_jY_j) =     H(Â_j | B̂_jA_jB_jC_jD_jX_jY_j) 
       - H(Â_j | B̂_jA_jB_jC_jD_jX_jY_jB̂_iA_iB_iC_iD_iX_iY_i ) 
    ≤     H(Â_j|B̂_jT_j A_jB_jC_jD_jX_jY_jB̂_iA_iB_iC_iD_iX_iY_i)
       - H(Â_j | B̂_jA_jB_jC_jD_jX_jY_jB̂_iA_iB_iC_iD_iX_iY_i ) 
    
    		=     0

	and the lemma follows.





	
alpha



