Tsirelson Polytopes and Randomness Generation
Peter Bierhorst Yanbao Zhang
quant-ph




Tsirelson Polytopes and Randomness Generation



Peter Bierhorst[Mathematics Department, University of New Orleans, Louisiana, USA] and Yanbao Zhang[NTT Basic Research Laboratories and NTT Research Center for Theoretical Quantum Physics, Japan]





We classify the extreme points of a polytope of probability distributions in the (2,2,2) CHSH-Bell setting that is induced by a single Tsirelson bound. We do the same for a class of polytopes obtained from a parametrized family of multiple Tsirelson bounds interacting non-trivially. Such constructions can be applied to device-independent random number generation using the method of probability estimation factors <cit.>. We demonstrate a meaningful improvement in certified randomness applying the new polytopes characterized here. 





§ INTRODUCTION




The phenomenon of Bell nonlocality <cit.> is a prediction of quantum physics in which entangled particles display behavior incompatible with any local realistic (or “classical”) explanation. Originally discovered during an examination of foundational assumptions about physics, Bell nonlocality was later found to have applications to tasks in quantum information theory. Specifically, communication protocols based on an underlying Bell nonlocality experiment can be designed to be “device-independent,” in the sense that users of the protocols can be assured of security so long as the observed data meets certain statistical benchmarks, without having to make detailed assumptions about the internal functioning of their devices. Applications include device-independent quantum key distribution <cit.> and device-independent random number generation <cit.>.

A Bell experiment will generate measurement outcomes according to a probability distribution. Only certain probability distributions exhibit Bell nonlocality while others do not, and only those exhibiting Bell nonlocality are resources for device-independent tasks. The set of quantum-achievable probability distributions that do exhibit Bell nonlocality is hard to characterize with a curved boundary <cit.>. Even in the simplest (2,2,2) Bell scenario (2 parties, 2 settings, 2 outcomes), new discoveries about the structure of this set are still being made <cit.>.

Here, we describe a method for approximating the set of quantum-achievable distributions from the outside with convex polytopes,
motivated by an application to device-independent random number generation <cit.>. We obtain the approximation by first restricting to the set of no-signaling probability distributions – itself a polytope containing the quantum set <cit.> – and then reducing to a smaller polytope by intersecting with half-spaces defined by so-called “Tsirelson” inequalities: linear constraints obeyed by quantum-achievable probability distributions. We did this in an earlier work <cit.> for single instances of Tsirelson's original inequality <cit.>; in the current paper, we generalize and formalize this approach to apply to any generalized Tsirelson inequality such as those found in Refs. <cit.>. We also simultaneously incorporate multiple Tsirelson inequalities that interact non-trivially and describe the resulting smaller polytopes. While the extreme points of a given polytope characterized by known linear constraints can be found algorithmically, our work goes beyond this in classifying polytopes as parametrized families depending on parameters of the generalized Tsirelson inequalities that induce them. These analytic results provide a useful tool for optimizing approximating polytopes for a given task.

The specific application motivating our study is the Probability Estimation Factor (PEF) method <cit.> for device-independent random number generation. As demonstrated recently <cit.> the PEF method is effective for certifying randomness in feasible experiments. In its basic form it certifies randomness secure against an adversary holding classical side information, as done in <cit.>, and it can also be used <cit.> as a tool for constructing the necessary machinery to execute the quantum probability estimation protocol of <cit.> which is secure against more general quantum side information. 

The relevance of bounding polytopes to the PEF method is explained in detail in Section <ref> below, but it can be understood roughly as follows: if a candidate for a randomness certifying function is found to be valid, loosely speaking, for a finite set of probability distributions, then it will be valid for any convex mixture of these probability distributions. If the set of these convex mixtures – which is a polytope – contains the entire quantum set, the function is then confirmed to be appropriate for certifying randomness, having only had to check the validity condition for a finite number of probability distributions. In contrast to the polytopes presented here, other methods for approximating the quantum set, such as the non-linear methods of Navascués, Pironio, and Acín <cit.>, are not readily applicable to the PEF method. It is possible then that our results may have applications to other quantum information tasks for which a polytope approximation of the quantum set is desirable, and readers unfamiliar with the PEF method do not need to review it to understand the polytope approximations described in Sections <ref> and <ref>. 

In the remainder of the paper, we review basic facts about the set of quantum-achievable probability distributions and related polytopes (Section <ref>), then derive our results about Tsirelson polytopes in Section <ref>. In Section <ref>, we review the PEF method and present a scenario in which using the new polytopes yields a demonstrable improvement over previous implementations, and then we finish with concluding remarks in Section <ref>. An appendix contains some of the more technical proofs.



§ DEFINITIONS AND BACKGROUND




Our setting is the (2,2,2) Bell scenario, in which there are two spatially separated parties (“Alice" and “Bob") making measurements, two measurement settings for each party, and two possible measurement outcomes for each party. We can use random variables O_A and O_B to represent Alice's and Bob's outcomes, respectively, and random variables S_A and S_B to represent their respective settings. The outcome random variables O_A and O_B both take values in the set {0,+} and the settings random variables S_A and S_B take values in the sets {a,a'} and {b,b'}, respectively. A (2,2,2) Bell experiment is thus governed by a set of four conditional probability distributions corresponding to the four possible measurement configurations: {S_A=a}∩{S_B=b}, {S_A=a}∩{S_B=b'}, etc. We will use the shorthand where P(0+| a'b) is understood to mean P({O_A=0}∩{O_B=+}| {S_A=a'}∩{S_B=b}), and we follow the terminology of <cit.>:
 
A behavior, denoted P⃗, is a vector in ℝ^16 listing the set of 16 conditional probabilities P(++| ab), P(+0| ab), ... , P(00| a'b') corresponding to all possible measurement configurations and outcomes of the (2,2,2) experiment. A Bell function is a vector B⃗ in ℝ^16 inducing a function from behaviors to ℝ via the dot product: B⃗·P⃗:ℝ^16→ℝ. 

Bell functions will be used to introduce constraints of the form B⃗·P⃗≤ R, where R is a real number, which will be satisfied only by some behaviors.

By the laws of probability, any valid behavior P⃗ must have only nonnegative entries and satisfy the following normalization equations:

    1    =   P(++| ab)+ P(+0| ab) + P(0+| ab)+ P(00| ab) 
    
    1    =    P(++| ab')+ P(+0| ab') + P(0+| ab')+ P(00| ab')   
    
    1    =    P(++| a'b)+ P(+0| a'b) + P(0+| a'b)+ P(00| a'b) 
    
    1    =    P(++| a'b')+ P(+0| a'b') + P(0+| a'b')+ P(00| a'b')  .

Furthermore, we will study only behaviors that additionally satisfy the no-signaling constraints:

    P(++| ab)+ P(+0| ab)    =    P(++| ab')+ P(+0| ab')
    
    P(++| a'b)+ P(+0| a'b)    =    P(++| a'b')+ P(+0| a'b')
    
    P(++| ab)+ P(0+| ab)    =    P(++| a'b)+ P(0+| a'b)
    
    P(++| ab')+ P(0+| ab')    =    P(++| a'b')+ P(0+| a'b')

The no-signaling constraints express the condition that Alice's marginal outcome distribution should not depend on Bob's measurement choice and vice versa. For instance, the first equation above requires that when Alice's setting is a, her probability of getting a “+" is the same whether Bob has setting b or b'. The first equation also implies, when combined with the laws of probability expressed in (<ref>), that Alice's probability of getting a “0" does not depend on Bob's setting.

We will refer to the class of valid behaviors satisfying (<ref>) as the no-signaling set 𝒩𝒮. 𝒩𝒮 forms a closed convex polytope: a bounded set formed by the intersection of finitely many closed half spaces. For 𝒩𝒮, the half spaces are obtained from the 8 linear equality constraints in (<ref>) and (<ref>) combined with 16 linear inequality constraints ensuring that all entries are nonnegative, and the boundedness follows from the observation that 𝒩𝒮⊆ [0,1]^16. It is well known <cit.> that 𝒩𝒮 can be expressed as the convex hull of 24 so-called extreme points, 8 of which are called “Popescu-Rohrlich (PR) boxes" <cit.> and 16 of which are called “local deterministic" behaviors; see <cit.> Tables A1 and A2 for a list. We denote these extremal behaviors as {P⃗R⃗_i}_i=1^8 and {L⃗_i}_i=1^16, respectively. The standard definition (such as in <cit.>) of an extreme point of a set 𝒮 is one that cannot be expressed as non-trivial convex combinations of other points in 𝒮, and the Krein-Milman theorem implies that any convex compact set in ℝ^n will be equal to the convex hull of its extreme points. This allows us to use the following working definition of a set of extreme points:



 
Given a convex set 𝒮, a subset ℰ⊆𝒮 is the set of extreme points of 𝒮 if 


  * 𝒮 is contained in the convex hull of ℰ, denoted 𝒮∈Conv(ℰ )

  * No element of ℰ can be expressed as a convex combination of other points in ℰ 



There are two important subsets of 𝒩𝒮 to mention. First is the quantum set 𝒬, consisting of behaviors that can be induced by quantum measurements of a quantum system. Second is the local set ℒ, consisting of behaviors that admit a decomposition of the form P(O_A,O_B|S_A,S_B) = ∑_λ P(O_A|S_A,Λ = λ)P(0_B|S_B,Λ=λ)P(Λ=λ) for a random variable Λ that represents local hidden variables. ℒ is equal to the convex hull of the 16 local deterministic distributions {L⃗_i}_i=1^16; recall these are some (but not all) of the extreme points of the set 𝒩𝒮. Quantum behaviors in 𝒩𝒮∖ℒ can be shown to contain certifiable randomness.

Every Bell function has a maximum local value, a maximum quantum value, and a maximum no-signaling value which, given a Bell function B⃗, we define as

    LB    =   sup_P⃗∈ℒB⃗·P⃗  (Local Bound)
    
    TB    =   sup_P⃗∈𝒬B⃗·P⃗  (Tsirelson Bound)
    
    NSB    =   sup_P⃗∈𝒩𝒮B⃗·P⃗  (No-Signaling Bound)


For ℒ and 𝒩𝒮, the above suprema are indeed maxima, as the maximum values are achieved. This follows because ℒ and 𝒩𝒮 are each equal to the convex hull of a finite set of extreme points, and so for such a scenario, given a behavior P⃗ we can re-express B⃗·P⃗ as 

    B⃗·P⃗=B⃗· ( ∑_i=1^n λ_i E⃗_i)=∑_i=1^n λ_i (B⃗·E⃗_i),

where the E⃗_i are elements of the set of extreme points and the λ_i are nonnegative numbers summing to one. Therefore no behavior can have a value of B⃗·P⃗ that is greater than max_E⃗_i∈ℰB⃗·E⃗_i. The fact that the maxima for ℒ and 𝒩𝒮 are achieved at extreme points will be useful in the arguments below. Regarding the question of whether the supremum over the quantum set is a proper maximum, the situation is more complicated and discussed in <cit.>, but this question is not material for the work below. Finally, it is well known that ℒ⊆𝒬⊆𝒩𝒮, and so the following inequality holds in general:

    LB ≤ TB ≤ NSB

Thus Bell functions B⃗ for which LB < TB holds strictly can be used to witness certifiable randomness in quantum behaviors P⃗ satisfying B⃗·P⃗ > LB. 


One particularly important Bell function that we will discuss is the Clauser-Horne-Shimony-Holt (CHSH) Bell function B⃗ ^CHSH <cit.>, whose coefficients are given in Table <ref>. 

The famous CHSH inequality, B⃗ ^CHSH·P⃗≤ 2 for P⃗∈ℒ, is a statement that LB is 2 for B⃗ ^CHSH. The Tsirelson bound TB for B⃗ ^CHSH is 2√(2) <cit.>. The no-signaling bound NSB of 4 is achieved by the PR box behavior in Table <ref>  <cit.>. The local bound LB of 2 is achieved by eight local deterministic behaviors; each of these eight behaviors has a entry of “1" in exactly one place where the PR box has a “0," and this location is unique to each of the eight saturating local behaviors. 


There are symmetries of the convex sets 𝒩𝒮, 𝒬, and ℒ, for which the associated transformations applied to the CHSH inequality generate new inequalities. There are eight inequivalent versions of the CHSH inequality obtained this way. Each version of the CHSH inequality corresponds to a unique PR box behavior obtaining the NSB of 4 with a corresponding set of eight local deterministic behaviors obtaining the LB of 2.



§ TSIRELSON POLYTOPES


Given a Bell function B⃗ and a real number TB^* satisfying TB≤ TB^* ≤ NSB, we define the corresponding Tsirelson Polytope 𝒬_T to be {P⃗∈𝒩𝒮 | B⃗·P⃗≤ TB^*}. We allow for TB^* to exceed the quantum supremum TB, because we might want to consider Bell functions for which the exact quantum limit is not known but a numerical upper bound can be found <cit.>. As 𝒬_T is the intersection of 𝒩𝒮 with a half space defined by a linear inequality, 𝒬_T will form a polytope.

Not all Bell functions will lead to scenarios worth studying. For our purposes, any interesting Bell function should not have NSB=LB, which by (<ref>) would lead to the degeneracy LB = TB = NSB, so we only consider Bell functions for which LB <NSB holds strictly. For a given Bell function B⃗, one can effectively determine whether the strict inequality holds by checking the value of B⃗·E⃗ for all extreme points of ℒ and 𝒩𝒮. Here is a useful lemma about such Bell functions:

For any Bell function B⃗ for which LB < NSB holds, there is exactly one PR box for which B⃗·P⃗R⃗>LB, and B⃗·P⃗R⃗ = NSB for this PR box.

Proof.
NSB will be achieved at an extreme point of 𝒩𝒮, and the assumption LB < NSB implies that this extreme point must be one of the PR boxes. If a second PR box satisfied B⃗·P⃗R⃗>LB, then an equal mixture of these two PR boxes – which is in the local set ℒ (see Theorem 2.1 in <cit.>) – would exceed the local bound, a contradiction.




A priori, any Bell function satisfying LB <NSB will fall into one of two categories.: LB≤ TB < NSB and LB < TB =  NSB. It turns out the latter of these is impossible: Appendix D of <cit.> explains that if TB = NSB, then LB = TB = NSB. Thus we need only consider Bell functions for which LB≤ TB < NSB; this forms our general scenario of interest. For the rest of this paper, we assume this condition, as well as TB^*< NSB (as TB^*=NSB yields 𝒬_T = 𝒩𝒮).

Lemma <ref> tells us that when we intersect 𝒩𝒮 with {P⃗ | B⃗·P⃗≤ TB^*} for some TB^*∈ [TB,NSB), the resulting set contains all of the extreme points of 𝒩𝒮 save one – the sole PR box for which B⃗·P⃗R⃗ =NSB>LB. Thus many of the extreme points of 𝒩𝒮 are extreme points of 𝒬_T. The following theorem, proved in the appendix, classifies the rest of the extreme points of 𝒬_T.


Let B⃗ be a Bell function for which LB≤ TB < NSB holds, and let P⃗R⃗_1 denote the PR box for which B⃗·P⃗R⃗_1=NSB. Let TB^*∈ [TB,NSB) and define 𝒬_T= {P⃗∈𝒩𝒮|B⃗·P⃗≤ TB^*}. Then the set of extreme points of 𝒬_T is equal to the set ℰ defined as follows: all of the local deterministic distributions, all of the PR boxes except P⃗R⃗_1, and all behaviors of the form

    E⃗_i = λ_iP⃗R⃗_1 + (1-λ_i)L⃗_i

where L⃗_i is one of the eight local distributions saturating the version of the CHSH inequality maximally violated by P⃗R⃗_1, and λ_i=(TB^*-B_i)/(NSB-B_i) with B_i = B⃗·L⃗_i.

We note that if LB=TB^* holds, a behavior defined by (<ref>) can coincide with a local deterministic distribution, in which case the statement of the theorem refers to this behavior twice in defining the set ℰ. 


Applying the above theorem to the special case of the original Tsirelson bound of 2√(2) for B⃗ ^CHSH, one obtains the same value of λ_i = √(2) - 1 for all eight versions of the E⃗_i behavior in (<ref>). Furthermore, if one simultaneously introduces all eight versions of the CHSH inequality with Tsirelson bounds 2√(2), it follows from the above arguments that each version causes the corresponding PR box behavior achieving NSB=4 to split into eight extreme points of the form (<ref>), resulting in a polytope with 80 extreme points, as described in <cit.>.

The scenario of the 80-vertex polytope is straightforward to describe because the different Tsirelson bounds do not “interact" in the sense that the respective no-signaling maxima for their corresponding Bell functions are achieved by different PR box behaviors; this is depicted schematically in Figure <ref>. However, the situation is more complicated if Tsirlson bounds are introduced for two distinct Bell functions maximized by the same PR box, as represented in Figure <ref>. This turns out to be the scenario that yields improvement for randomness certification.







With a little effort, the proof method for Theorem <ref> can be adapted to find the extreme points of the more complicated polytopes with two Tsirelson bounds interacting non-trivially.

As an example, let us consider the “tilted" CHSH Bell function B⃗^α whose coefficients are given in Table <ref>. 

The Tsirelson bound for this Bell function is derived in Ref. <cit.>, valid for all values of α>1:

    B⃗^α·P⃗≤ 2√(1+α^2)   for all P⃗∈𝒬

There is a quantum behavior saturating the bound. For a fixed α >1, the extreme points of the polytope induced by (<ref>) alone are given by Theorem <ref>. Now let us consider the polytope of behaviors that obey Tsirelson's original inequality B⃗ ^CHSH·P⃗≤ 2√(2) as well as (<ref>) for a fixed value of α>1, as depicted schematically in Figure <ref>.

To describe the extreme points of this polytope, first we remark that of the eight local deterministic behaviors satisfying B⃗ ^CHSH·L⃗=2, four of them will have a B⃗^α·L⃗ value of 2, and four of them will have a B⃗^α·L⃗ value of 2α. This is confirmed by inspection of Table <ref>. We can label the first four of these local deterministic behaviors {L⃗^top_i}_i=1^4, and the second four {L⃗^bot_i}_i=1^4. 

We assert that the extreme points of the polytope are those for 𝒩𝒮, minus the single PR box that violates both Tsirelson bounds, plus 24 new extreme points. Four of these extreme points are obtained from the expression (<ref>) using L⃗^top_i vectors with NSB, B_i, and TB^* generated by B⃗ ^CHSH, and four are obtained from the expression (<ref>) using the L⃗^bot_i vectors with NSB, B_i, and TB^* generated by B⃗^α. Note these behaviors each saturate one of the two Tsirelson inequalities while strictly obeying the other one. The remaining 16 extreme points, which saturate both Tsirelson inequalities, are given as

    λ_PRP⃗R⃗_1 + λ_topL⃗^top_i+ λ_botL⃗^bot_j

for all choices of i,j ∈{1,2,3,4}, where the λ coefficients are found by solving the simultaneous set of equations

    (2+2α)λ_PR  + 2λ_top+ 2αλ_bot   =   2√(1+α^2)
    
    4λ_PR  + 2λ_top+ 2λ_bot   =   2√(2)
    λ_PR  + λ_top+ λ_bot   =   1.


The following values solve this set of equations:


    λ_PR=√(2)-1      λ_top=1-√(1+α^2)-√(2)/α-1      λ_bot=1-α√(2)-√(1+α^2)/α-1

Furthermore, the condition α>1 ensures the above coefficients are nonnegative,[The subtracted fractions in the expressions for λ_top and λ_bot are less than one:α>1 ⇒ 1+α^2 +(2√(2)-2)(α-1)>1+α^2
⇒ (α -1 +√(2))^2>1+α^2
⇒α -1 >√(1+α^2)-√(2), and α>1 ⇒ 1+α^2-(2√(2)-2)α(α-1)<1+α^2
⇒ [(√(2)-1)α+1]^2<1+α^2
⇒α√(2)-√(1+α^2)<α-1.
]
 so the expression (<ref>) with the coefficients in (<ref>) yields a valid convex combination. An outline of the proof that these are the extreme points is given in the appendix.




§ APPLICATIONS TO DEVICE INDEPENDENT RANDOM NUMBER GENERATION



The constructions of Section <ref> can be applied to the task of device-independent random number generation via the method of probability estimation factors <cit.>, which we now briefly review. In the context of device-independent randomness, a probability estimation factor (PEF)  is a function, satisfying certain conditions, that maps the result of a Bell experiment to the nonnegative real numbers. It is essentially a score function that assigns higher values to more nonlocal results, thereby quantifying certifiable randomness. In our (2,2,2) Bell scenario, the result of an experimental trial consists of the two settings choices and two outcomes for Alice and Bob, so any PEF is a function F: (O_A,O_B,S_A,S_B)→ℝ^+∪{0} with sixteen possible inputs. The precise definition of a PEF in this scenario is as follows: for a collection of behaviors 𝒫 and a parameter β>0, a PEF with power β is a nonnegative function satisfying the following inequality for all behaviors P⃗∈𝒫:

    E_P⃗ [F(O_A,O_B,S_A,S_B)P(O_A,O_B|S_A,S_B)^β]≤ 1,

where E_P⃗ [· ] denotes expected value with respect to the joint distribution P(O_A,O_B,S_A,S_B) of the settings and outcomes given by the behavior P⃗ with a fixed settings distribution. The probability P(O_A,O_B|S_A,S_B) in (<ref>) is also according to the behavior P⃗. 

Equation (<ref>) can be used to prove that a certain function of the cumulative value of PEF scores over a sequence of n repeated trials of a Bell experiment is a bound on the probability of the string of observed outcomes, and thus a witness to the presence of randomness. Specifically, in <cit.> it is shown that if F is a PEF with power β for a collection of behaviors 𝒫, then for any ϵ>0, the following holds for any probability distribution P governing all n trials in which the trial-by-trial, settings-conditional outcome distributions are (possibly different) behaviors in 𝒫:

    P[P(outcome string|setting string)≥(ϵ∏_i=1^nF_i)^-1/β]≤ϵ.

The above expression, roughly speaking, says that when the product of the trial-by-trial PEF values F_i is large  – and so the quantity (ϵ∏_i=1^nF_i)^-1/β is small – it is unlikely (outer probability less than epsilon) that the observed outcome string occurs with more than a small probability (inner inequality). Often, we assume that the collection of behaviors 𝒫 is the set of quantum-achievable behaviors, and so (<ref>) will hold under the assumption that quantum mechanics is correct. Importantly, it is not necessary to assume that that the n trials are independent and identically distributed (i.i.d.); the behavior can vary within 𝒫 from trial to trial and (<ref>) will still hold. Equation (<ref>) will only be useful in the presence of nonlocal behaviors: barring an unlikely statistical fluctuation, classical behaviors admitting a local realistic description will yield a trivial probability bound (ϵ∏_i=1^nF_i)^-1/β in the sense that the bound will be greater than or equal to 1.

Polytopes containing the quantum set of behaviors 𝒬 can be used to effectively construct valid PEFs satisfying the defining constraint (<ref>). Specifically, Section V of the supplemental material of <cit.> shows that anything satisfying the PEF defining condition (<ref>) for the extreme points of a polytope containing 𝒫 will satisfy (<ref>) for all the behaviors in 𝒫. Hence it becomes possible to check that a PEF is valid by checking only a finite number of linear inequality constraints, one for each extreme point.

The probability bound of (ϵ∏_i=1^nF_i)^-1/β in (<ref>) is a rough measure of how much randomness is available in the data of a Bell experiment. To illustrate, suppose an experiment is run and (ϵ∏_i=1^nF_i)^-1/β comes out to equal, say, (1/2)^26. Then (<ref>) implies that, modulo an error probability of ϵ, the likelihood of the observed outcome string was no more than the likelihood of observing a particular 26-bit string drawn from a uniform stream of random bits. However, the actual outcome string of the raw data of the Bell experiment may be thousands of bits long; to process the randomness in this long string into a shorter, near-uniform output string for information-theoretic applications, further work can be done <cit.> to account for the non-unity probability that the PEF product exceeds a certain threshold and to properly apply classical postprocessing machinery such as an extractor function <cit.>. These steps consume some of the randomness and would result in a final output string of fewer than 26 bits. However, we will not implement these final steps and will just use the probability bound of (ϵ∏_i=1^nF_i)^-1/β in (<ref>) as a measure of available certifiable randomness for comparing performance of various PEFs. This is reasonable because in the limit of a large number of i.i.d. trials sampled from a nonlocal behavior, the negative base-2 logarithm of the probability bound (ϵ∏_i=1^nF_i)^-1/β converges asymptotically to the number of extractable bits <cit.>. We use the negative base-2 logarithm scale when reporting results.

Given a quantum-achievable behavior, we can compare the performance of PEFs for it by fixing an error bound ϵ, fixing a number n of i.i.d. trials sampled from the quantum behavior with equiprobable settings, and computing (ϵ∏_i=1^nF_i)^-1/β in (<ref>). Since ∏_i=1^nF_i is a random variable, the probability bound will depend on the particular instance of the experiment. However, we can anticipate a likely value for ∏_i=1^nF_i using the fact that for sufficiently large n, ∑_i=1^nln ( F_i ) will be either greater than or less than n E(ln F) with roughly equal probability, where the expectation E is computed according to the chosen quantum behavior with equiprobable settings. (This follows from the Central Limit Theorem; see <cit.>, or <cit.> Supplementary Information Section 3 for details.) Hence we use 

    {ϵexp [n E(ln F)]}^-1/β,

where exp denotes the exponential function, as the median anticipated value for (ϵ∏_i=1^nF_i)^-1/β. Since it is desirable for the probability bound (ϵ∏_i=1^nF_i)^-1/β in (<ref>) to be small (lower probabilities correspond to more randomness), finding a PEF that minimizes (<ref>) will optimize performance.




Given a set of extreme points ℰ of a polytope containing the quantum set 𝒬, we can perform a maximization procedure to find a PEF, valid for all quantum behaviors, that optimizes the quantity (<ref>) for a fixed number of trials n and a fixed error parameter ϵ. The procedure is as follows: first fix a choice of β, and note that with n, ϵ, and β fixed, (<ref>) is a monotone decreasing function of E(ln F). Now, in order to minimize (<ref>), we need to solve the following convex optimization problem:

    FMaximize        E(ln F)
    Subject to       E_E⃗ [F(O_A,O_B,S_A,S_B)P_E⃗(O_A,O_B|S_A,S_B)^β]≤ 1,   ∀E⃗∈ℰ
           F(O_A,O_B,S_A,S_B)≥ 0,   ∀ O_A,O_B,S_A,S_B.

This can be solved effectively with standard computer algorithms. Once this is done, plug the resulting optimized value of E(ln F) into (<ref>). Then repeat the procedure for various values of β looking for the lowest possible value of (<ref>). By numerics, we found that the optimal value of β for each example studied in this work lies in the interval [0.001, 0.100]. To obtain the lowest possible value of (<ref>) and the corresponding optimal value of β, we tested 100 equally spaced values of β between 0.001 and 0.100, which yields a curve with a clear optimum as illustrated in Figure <ref>.




Results. To demonstrate the method, we considered the amount of randomness certifiable from a specific quantum-achievable behavior. Our choice was the unique quantum behavior, given in <cit.>, that maximizes the Bell function in Table <ref> when α=2. Since this Bell function uniquely determines the behavior, a reasonable conjecture might be that the polytope obtained from the corresponding Tsirelson bound (<ref>) with α=2 would result in a larger amount of randomness than could be obtained using the polytope induced by the original Tsirelson bound B⃗^CHSH·P⃗≤ 2√(2) (equivalent to (<ref>) with α=1). We found that the opposite was true. However, including both bounds to create a smaller polytope does result in a meaningful improvement compared to using either bound individually. Note that <cit.> all use the polytope with only B⃗^CHSH≤ 2√(2), so our observation that the polytope using both bounds results in an improvement of almost 18% to the number of certified random bits is relevant for future implementations. Our results are summarized in Table <ref>. 




We are of course not limited to the three polytopes analyzed in Table <ref>. We have derived a parametrized family of two-inequality polytopes for different values of α. Figure <ref> displays interesting behavior for the amount of certifiable randomness at different values of α, and supports the notion that the α=2 figure of 6,805.23 reported in Table <ref> is near-optimal for this family of polytopes. Numerical evidence indicates that the optimal value of α is closer to 2.03. The abrupt cusp in the curve at this maximum is a striking feature, especially as the extreme points E⃗_i given by (<ref>) and (<ref>) vary continuously as a function of α. We speculate it may indicate that the restrictions imposed by the constraints in the PEF optimization (<ref>) are dominated by one particular E⃗_i and the cusp occurs at a location where there is a switch in which E⃗_i dominates. Exploring the causes and prevalence of this type of feature could be an aspect of future work.

There are many different scenarios that can also be examined. The Tsirelson bound for expression (17) of Ref. <cit.>, computed using the analytic technique of Wolfe and Yelin <cit.>, is saturated by a quantum behavior as well as a local deterministic behavior – and consequently is saturated by any convex mixture of these two behaviors. We found that the amount of randomness that can be certified from such a convex mixture is greater using the standard CHSH inequality polytope, compared to what can be certified using the polytope induced by (17) in Ref. <cit.>, paralleling our finding above for the single-inequality polytopes induced by B⃗^α and B⃗^CHSH. Furthermore, initial explorations employing polytopes with two non-trivially interacting Tsirelson bounds to certify randomness in existing experimentally generated data sets, such as the data in Ref. <cit.>, produced only marginal improvements over the results reported in the reference (which uses only the original Tsirelson inequality). It may be that the meaningful improvements reported in Table <ref> are more characteristic of behaviors near the quantum boundary and/or behaviors inducing a large absolute violation of the original CHSH inequality. This is worth considering if loophole-free Bell experiments employing atoms <cit.>, which achieve higher violations of the CHSH inequality than photonic loophole-free Bell experiments <cit.>, begin to reach the higher data rates characteristic of photonic experiments. To date, only photonic systems have reached data rates sufficient to enable practical demonstrations of device-independent random number generation <cit.>.









§ CONCLUSION


We have derived formulas for identifying the extreme points of polytopes induced by multiple Tsirelson bounds, relating the structure of these polytopes to parameters in the defining inequalities. We have demonstrated that these results can be used to improve the performance of the probability estimation factor method for certifying device-independent randomness. Our techniques outline a general approach for classifying the extreme points of such polytopes, and in future work it may be useful to incorporate three or more non-trivially interacting Tsirelson bounds to obtain better approximations of the quantum set. Unfortunately, the complexity of a polytope grows with each additional constraint and a law of diminishing returns will apply as each iteration removes a smaller volume of behaviors than the one before it. Ideally the limiting behavior of performance enhancements will become apparent before the procedure becomes intractable. Even small improvements can be worth pursuing: in current device-independent random number generation experiments <cit.>, the speed of randomness generation tops out at kilobits per second, whereas even a partial relaxation of assumptions such as in semi-device independent protocols with an uncharacterized source and characterized measurements <cit.> can yield generation rates in the range of gigabits per second. This highlights how improvements to the amount of randomness on the scale reported in this paper could be quite valuable in applications where the full security of a completely device-independent implementation, with its attendant reduction in randomness generation rate, is demanded. The results presented here may also find applications beyond probability estimation, given the growing scope of quantum information theory and in particular device-independent protocols. 





§ ACKNOWLEDGEMENTS
 The authors thank Emanuel Knill for helpful input on this project. This work was partially supported by National Science Foundation award number 1839223 and the Louisiana Board of Regents contract number LEQSF(2019-22)-RD-A-27.




§ PROOFS OF RESULTS


In this appendix, we prove Theorem <ref>, and then outline the proof of the classification of the extreme points of the polytope induced by B⃗ ^CHSH and B⃗ ^α.






Theorem 3.1 Let B⃗ be a Bell function for which LB≤ TB < NSB holds, and let P⃗R⃗_1 denote the PR box for which B⃗·P⃗R⃗_1=NSB. Let TB^*∈ [TB,NSB) and define 𝒬_T= {P⃗∈𝒩𝒮|B⃗·P⃗≤ TB^*}. Then the set of extreme points of 𝒬_T is equal to the set ℰ defined as follows: all of the local deterministic distributions, all of the PR boxes except P⃗R⃗_1, and all behaviors of the form

    E⃗_i = λ_iP⃗R⃗_1 + (1-λ_i)L⃗_i

where L⃗_i is one of the eight local distributions saturating the version of the CHSH inequality maximally violated by P⃗R⃗_1, and λ_i=(TB^*-B_i)/(NSB-B_i) with B_i = B⃗·L⃗_i.






Proof. First note that the relation B_i ≤ LB≤ TB^* < NSB ensures that 0≤λ_i < 1 holds. Thus (<ref>) defines a convex combination of the behaviors PR_1 and L⃗_i, so the E⃗_i are valid behaviors in 𝒩𝒮. Furthermore, one can check directly that B⃗·E⃗_i≤ TB^* holds for any i (indeed, B⃗·E⃗_i= TB^*) so the E⃗_i are contained in 𝒬_T. As for the other elements of ℰ, these are all local deterministic distributions or PR boxes other than P⃗R _1, which all satisfy B⃗·P⃗≤ LB≤ TB^*. Thus ℰ⊆ Q_T. 

Now we demonstrate that ℰ satisfies the statement of Definition <ref>. The first step is to show that every element of 𝒬_T is in the convex hull of ℰ. To do this, note that the convex hull of ℰ includes ℒ as well as every convex combination of local deterministic distributions and PR boxes other than P⃗R⃗_1. By the remarks following Theorem 2.2 of <cit.>, any element of 𝒩𝒮 that does not fall into one of these categories can be expressed as a convex combination of the following form:

    p_PRP⃗R⃗_1+∑_i=1^8p_iL⃗_i.

The p coefficients are nonnegative and satisfy p_PR+∑_i=1^8p_i=1. To show 𝒬_T ⊆Conv(ℰ), it will thus suffice to show that any behavior P⃗ of the form (<ref>) that obeys B⃗·P⃗≤ TB^* can be expressed as convex combination of the E⃗_i behaviors defined in (<ref>) and the local distributions L⃗_i. 

Our strategy for this is to first re-write expression (<ref>) as

    [p_PRP⃗R⃗_1+p_1L⃗_1 ] + ∑_i=2^8p_iL⃗_i
    =[p_PR'P⃗R⃗_1+ p_1'L⃗_1+p_E_1E⃗_⃗1⃗] + ∑_i=2^8p_iL⃗_i

where the new set of p coefficients on the right side of (<ref>) are still nonnegative and sum to one, and the new coefficient p_PR' for P⃗R⃗_1 is smaller than p_PR. This process can be re-applied to p_PR'P⃗R⃗_1+p_2L⃗_2 to further lessen the coefficient p_PR', and the process is repeated while cycling from L⃗_1 through L⃗_8, until the entire weight of PR_1 is replaced with weight on the E⃗ vertices, leaving a convex combination solely of elements of ℰ.

To demonstrate that it is possible to execute the step displayed in (<ref>), we divide the problem into cases. First, let us suppose that TB^*-B_1  0 and that p_1 ≥ [(NSB-TB^*)/(TB^*-B_1)]p_PR. Then the following equality holds:

    p_PRP⃗R⃗_1+p_1L⃗_1 = p_PR(NSB-B_1/TB^*-B_1)×E⃗_1 + [p_1-(NSB-TB^*/TB^*-B_1)p_PR]×L⃗_1.

Our case assumptions assure that the coefficients of E⃗_1 and L⃗_1 are nonnegative, and furthermore the sum of the coefficients of E⃗_1 and L⃗_1 is equal to p_PR+p_1. Thus (<ref>) can replace the P⃗R⃗ and L⃗_1 terms in (<ref>) to obtain a well-defined convex combination of E⃗_1 and L⃗_1,...,L⃗_8 yielding the same behavior. In this case, containment in Conv(ℰ) is demonstrated and further iterations of the procedure are unnecessary.

Now let us suppose that either TB^*-B_1 = 0, or TB^*-B_1 > 0 and p_1 < [(NSB-TB^*)/(TB^*-B_1)]p_PR. In either case the following equality holds:

    p_PRP⃗R⃗_1+p_1L⃗_1 = p_1(NSB-B_1/NSB-TB^*)×E⃗_1 + [p_PR-(TB^*-B_1/NSB-TB^*)p_1]×P⃗R⃗_1.

Once again, the coefficients on the right side of the above equation are nonnnegative and sum to p_PR+p_1, and so (<ref>) can replace the P⃗R⃗ and L⃗_1 terms in (<ref>). Now there will remain some weight on the PR box in the new convex combination, but it will be reduced (unless p_1=0 or TB^*=B_1, in which case it is unchanged), and the above process can be reapplied to [p_PR-(TB^*-B1/NSB-TB^*)p_1]×P⃗R⃗_1+p_2L⃗_2. 

The key is that repeated applications of the (<ref>)-type substitution to successive L⃗_i terms must eventually terminate with a (<ref>)-type substitution that eliminates the coefficient of P⃗R⃗_1, prior to cycling through all eight of the L⃗_i. If this did not happen, the final expression after eight applications of (<ref>)-type substitutions would be of the form ∑_i=1^8p̂_iE⃗_i + p̂_PRP⃗R⃗_1 with p̂_PR>0. But it is not possible for such an expression to be equivalent to (<ref>), because B⃗·E⃗_i = TB^* for all i and B⃗·P⃗R⃗_1  > TB^*, so the new expression would violate the bound B⃗·P⃗≤ TB^*, whereas the behavior in (<ref>) was assumed to obey it.

We have thus shown that 𝒬_T ⊆Conv(ℰ). To complete the proof, we need to show the second part of Definition <ref> is satisfied; that is, no element of ℰ can be expressed as a convex combination of other points in ℰ. We need only check this for new behaviors E⃗_i defined in (<ref>). Note first that if TB^*-B_i=0, then E⃗_i=L⃗_1, and L⃗_i is already known to be extremal, so let us assume TB^*-B_i>0. In this case, E⃗_i violates the version of the CHSH inequality that is maximially violated by P⃗R⃗_1 and saturated by L⃗_1. This version of the CHSH inequality is not violated by any of the local deterministic distributions or PR boxes in ℰ, so any non-trivial convex combination of elements of ℰ equaling E⃗_i would require positive weight on at least one of the other behaviors defined by expression (<ref>). But this is impossible: if we refer to Table 2 of <cit.>, we see that each E⃗_i behavior looks like the one in Table <ref>.

Importantly, there is a single location containing the entry p_i and seven locations containing zero, all located outside the support of the PR box. Furthermore, each different E⃗_i defined by (<ref>) will contain a positive p_i entry in a different one of these eight cells outside the support of the PR box, and zeros in the rest. This feature implies that no convex combination equaling E⃗_i can contain positive weight on any other E⃗_j with j i. 





Now we outline the proof that the extreme points of the polytope induced by B⃗ ^CHSH and B⃗ ^α are given by the expressions at the end of Section <ref>. 

To demonstrate part 1 of Definition <ref>, consider an expression of the form (<ref>) that obeys both Tsirelson bounds. Then, analogously to (<ref>), replace a portion of the weight on the PR box with weight on one of the 16 behaviors of the form (<ref>). This will be possible so long as there is positive weight on at least one L⃗^top_i behavior and at least one L⃗^bot_i behavior. Repeat this process with different choices of the 16 behaviors of the form (<ref>) until it is no longer possible – either 1) all PR box weight has been converted, 2) there is no remaining weight on L⃗^top_i behaviors, or 3) there is no remaining weight on L⃗^bot_i behaviors. In case of (1), the process is complete; in case of (2), one can continue to replace PR box weight with E⃗_i-type behaviors as defined in (<ref>) with L⃗^bot_i behaviors (which saturate (<ref>), and strictly satisfy B⃗ ^CHSH·P⃗ < 2√(2)); and in case of (3), one can instead continue to replace PR box weight with E⃗_i-type behaviors as defined in (<ref>) with L⃗^top_i behaviors (which, conversely, strictly satisfy (<ref>) and saturate B⃗ ^CHSH·P⃗≤ 2√(2)). The fact that the original behavior (<ref>) satisfies both Tsirelson inequalities ensures that in all cases, this process terminates with an equivalent expression consisting of a convex combination with weight solely on the new extreme points, and zero weight on the PR box. 

To demonstrate part 2 of Definition <ref>, note that the 24 new extreme points all violate the CHSH inequality, and the other extreme points do not, so any convex combination replicating one of the 24 new extreme points would have to contain weight on the other 23 new extreme points. However, it can be verified by inspection that this cannot occur by considering where these 24 extreme points contain zeros (recall Table <ref>) and which Tsirelson inequalities the extreme points saturate and/or strictly satisfy.


unsrt

