With independent copies of a Popescu–Rohrlich correlation [1 ] , Bob can recover whichever bit he requests from an arbitrarily long database of independent bits using one bit from Alice. Alice never learns which bit Bob wants, and the correlations respect the prohibition on faster-than-light signalling [2 , 3 ] . Information causality (IC) requires that the information Bob gains about the requested bit, summed over all possible requests, be at most the number of bits Alice sends [2 ] . Quantum theory obeys this bound, whose derivation uses nonsignalling and entropy rules that can be stated independently of quantum theory (Methods).
The Navascués–Pironio–Acín (NPA) hierarchy bounds the correlations between distant measurements by imposing successively stronger consistency conditions on the measured probabilities [4 , 5 ] . For a fixed Bell scenario, its levels converge to the commuting-operator correlation set, in which the parties’ measurements act on a common Hilbert space and commute across parties. The first level, Q 1 Q_1 Q 1 , coincides with macroscopic locality, which requires the fluctuations in outcome counts from many independent pairs to admit a local description [6 ] . Both macroscopic locality and IC give the quantum bound on the Clauser–Horne–Shimony–Holt (CHSH) expression.
Cavalcanti, Salles and Scarani found IC violations in Q 1 Q_1 Q 1 using larger outcome alphabets and concatenation [7 ] . The almost-quantum set Q 1 + A B Q_{1+AB} Q 1 + A B lies between Q 1 Q_1 Q 1 and Q 2 Q_2 Q 2 and satisfied the numerical IC tests reported when it was introduced [8 ] . Das Bhowmik and Banik obtained unbounded IC violations with a single use of an almost-quantum correlation and one communicated bit [9 ] , using the correlations of Gazi et al. [10 ] . The question is whether stronger consistency conditions can enforce IC at a finite level that works independently of the number of measurement settings.
For each fixed finite NPA level, we construct a family of binary-outcome correlations that satisfy every constraint at that level and violate IC by an amount that grows without bound as the number of settings increases. Each protocol uses the correlation once and sends one bit from Alice to Bob. The optimal information gain grows logarithmically with the number of settings at each fixed level. To enforce the quantum one-bit bound across these Bell scenarios, the hierarchy level must grow with the number of settings.
Reading a database with one bit
We construct binary-outcome correlations in which Alice and Bob can both obtain zero only when their measurement settings agree. At each fixed NPA level L ≥ 2 L \ge2 L ≥ 2 , this event has the same probability s L > 0 s_L > 0 s L > 0 at every pair of equal settings, independent of how many settings each party has. Let x , y ∈ { 1 , … , N } x,y \in\{1,\ldots,N\} x , y ∈ { 1 , … , N } be Alice’s and Bob’s settings, and let a , b ∈ { 0 , 1 } a,b \in\{0,1\} a , b ∈ { 0 , 1 } be their outcomes. Either party obtains zero with probability 3 s L 3s_L 3 s L at every setting, as in the almost-quantum correlations of Gazi et al. [10 ] . Write Q L ( N , N , 2 , 2 ) Q_L(N,N,2,2) Q L ( N , N , 2 , 2 ) for the level-L L L set in this scenario and δ x y \delta_{xy} δ x y for the indicator of x = y x=y x = y . For each integer L ≥ 2 L \ge2 L ≥ 2 , we choose a rational s L > 1 / ( 185 L 3 ) s_L > 1/(185L^3) s L > 1/ ( 185 L 3 ) so that, for every N ≥ 2 N \ge2 N ≥ 2 , the following correlation belongs to Q L ( N , N , 2 , 2 ) Q_L(N,N,2,2) Q L ( N , N , 2 , 2 ) :
p L , N ( a , b ∣ x , y ) = { s L δ x y , a = b = 0 , 3 s L − s L δ x y , a ≠ b , 1 − 6 s L + s L δ x y , a = b = 1. (1) p_{L,N}(a,b \mid x,y)=
\begin{cases}
s_L\delta_{xy}, & a=b=0,\\
3s_L-s_L\delta_{xy}, & a\ne b,\\
1-6s_L+s_L\delta_{xy}, & a=b=1.
\end{cases} \tag*{(1)} p L , N ( a , b ∣ x , y ) = ⎩ ⎨ ⎧ s L δ x y , 3 s L − s L δ x y , 1 − 6 s L + s L δ x y , a = b = 0 , a = b , a = b = 1. (1)
A nonsignalling correlation cannot by itself transmit information from Alice to Bob. Information causality constrains how much information Bob can gain when Alice also sends him a classical message. To test IC, we therefore need a communication task and a protocol that uses the correlation.
In the IC task, Alice holds independent database bits R i R_i R i and Bob is asked for one of them, without revealing the requested position i i i to Alice. Their shared nonsignalling resource is independent of the database and request. She sends him a classical message M M M of at most m m m bits. Let G i G_i G i be Bob’s output for request i i i , obtained using the message and their shared correlation. Information causality requires that the Shannon mutual information, measured in bits and summed over possible requests, obey [2 ]
I : = ∑ i I ( R i : G i ) ≤ m . (2) \mathcal{I} := \sum_i I(R_i:G_i) \le m. \tag*{(2)} I := i ∑ I ( R i : G i ) ≤ m . (2)
This bound must hold for every communication protocol. To exhibit a violation, we therefore need to specify how Alice encodes the database, how the parties use the correlation, and how Bob produces his output. We do so with one use of Eq. (1) and one communicated bit, for which the IC bound is I ≤ 1 \mathcal{I} \le1 I ≤ 1 .
Take N N N database bits, each equal to one with probability r r r , where 0 < r < 1 0 < r < 1 0 < r < 1 . Alice uses the position of the first one as her setting x x x and sends her outcome M = a M=a M = a , adapting the block-selection protocol of Ref. [9 ] to biased bits. If there is no one, she uses any fixed setting and sends M = 1 M=1 M = 1 . Bob uses the requested position i i i as his setting. He sets G i = 1 G_i=1 G i = 1 when M = b = 0 M=b=0 M = b = 0 and G i = 0 G_i=0 G i = 0 otherwise (Figure 1 a). Joint zeros are impossible for x ≠ i x\ne i x = i , so G i = 1 G_i=1 G i = 1 certifies that Alice’s first-one position is i i i and hence that R i = 1 R_i=1 R i = 1 .
Figure 1. One-bit communication and matching settings. a, Alice’s independent database bits are one with probability 1 / N 1/N 1/ N . She uses the position x x x of the first one as her setting and sends her outcome M = a M=a M = a . She sends M = 1 M=1 M = 1 on an all-zero database. Bob uses the requested position i i i as his setting. The circles mark equal settings, where both outcomes are zero with probability s L s_L s L . The filled circle marks the example x = y = i = 3 x=y=i=3 x = y = i = 3 . Bob records G i = 1 G_i=1 G i = 1 if M = b = 0 M=b=0 M = b = 0 , which implies R i = 1 R_i=1 R i = 1 , and G i = 0 G_i=0 G i = 0 otherwise. b, The solid line gives the lower bound ( 1 − e − 1 ) X (1-e^{-1})X ( 1 − e − 1 ) X on the information score for X = s L log 2 N X=s_L\log_2N X = s L log 2 N . The dashed line marks the one-bit quantum bound. The shading marks the amount by which the lower bound exceeds it. At fixed NPA level L L L , the rate s L > 0 s_L>0 s L > 0 is independent of N N N , so increasing N N N makes the lower bound arbitrarily large.
Upon seeing G i = 1 G_i=1 G i = 1 , Bob learns that R i = 1 R_i=1 R i = 1 , which had prior probability r r r . The relative entropy of this posterior from the prior is log 2 ( 1 / r ) \log_2(1/r) log 2 ( 1/ r ) bits. For request i i i , this outcome has probability s L r ( 1 − r ) i − 1 s_Lr(1-r)^{i-1} s L r ( 1 − r ) i − 1 , since i i i must be the first position with a one. For a given database, only a request for that position can give G i = 1 G_i=1 G i = 1 . Summing over requests therefore gives s L s_L s L times the chance that there is a one in the database. The output G i = 0 G_i=0 G i = 0 also contributes a nonnegative term, so the total information I \mathcal{I} I obeys
I ≥ s L [ 1 − ( 1 − r ) N ] log 2 ( 1 / r ) . (3) \mathcal{I} \ge s_L\left[1-(1-r)^N\right]\log_2(1/r). \tag*{(3)} I ≥ s L [ 1 − ( 1 − r ) N ] log 2 ( 1/ r ) . (3)
At r = 1 / N r=1/N r = 1/ N , a one is rare at any given address and the probability of at least one in the database is at least 1 − e − 1 1-e^{-1} 1 − e − 1 . The lower bound is ( 1 − e − 1 ) s L log 2 N (1-e^{-1})s_L\log_2N ( 1 − e − 1 ) s L log 2 N (Figure 1 b).
The same encoding works with fair bits by grouping them into blocks. Alice chooses the first all-ones block from N N N blocks of k k k independent fair bits and sends her outcome; if no such block exists, she sends one. Bob chooses the block containing his requested bit. This is the original block protocol [9 ] . Joint zeros imply that every bit of the selected block is one. For each of the k k k requests within that block, the probability of a one changes from the prior 1 / 2 1/2 1/2 to certainty, giving one bit of relative entropy. An all-ones block has probability 2 − k 2^{-k} 2 − k , so the score is at least k s L [ 1 − ( 1 − 2 − k ) N ] ks_L[1-(1-2^{-k})^N] k s L [ 1 − ( 1 − 2 − k ) N ] . Taking k = ⌊ log 2 N ⌋ k=\lfloor\log_2N\rfloor k = ⌊ log 2 N ⌋ also gives logarithmic growth.
If joint zeros never occur at unequal settings, quantum correlations have average joint-zero probability at most 1 / N 1/N 1/ N across the N N N equal settings. The same bound holds in the commuting-operator set Q c \mathcal{Q}_c Q c . In this model, Alice’s and Bob’s projectors act on a common Hilbert space and commute across parties; measurements on separate tensor factors are included. Let s i = p ( 0 , 0 ∣ i , i ) s_i=p(0,0\mid i,i) s i = p ( 0 , 0 ∣ i , i ) , with no restriction on the marginals. Let Alice measure her projectors in order, stopping at the first zero. Conditional on Bob obtaining zero at setting i i i , Alice cannot obtain zero at any earlier setting because joint zeros are absent at unequal settings. Each earlier measurement therefore gives outcome one with certainty and leaves her conditional state unchanged. The joint probability of Bob’s zero and Alice’s first zero at i i i is therefore s i s_i s i . Alice’s distribution for the position of her first zero is independent of Bob’s setting by nonsignalling. The unconditional probability of her first zero at i i i is at least s i s_i s i . These events are disjoint, so ∑ i s i ≤ 1 \sum_i s_i\le1 ∑ i s i ≤ 1 [10 , 11 ] . A shared uniform label attains the bound if each party outputs zero exactly when its setting equals that label.
To determine how fast the information can grow, let F L ( N ) F_L(N) F L ( N ) be the supremum of I \mathcal{I} I over all correlations in Q L ( N , N , 2 , 2 ) \mathcal{Q}_L(N,N,2,2) Q L ( N , N , 2 , 2 ) and all protocols with at most one use of the correlation and at most one classical bit from Alice to Bob. The database may be any finite collection of independent bits with arbitrary biases. Shared randomness is independent of the database, the request and the correlation. The message alphabet has at most two values, including on runs where the correlation is unused. Bob may choose his setting using the message, and his output G i G_i G i may be his full transcript. In quantum theory this optimum is one, attained by sending a fair database bit.
For a nonsignalling correlation, transmitting Alice’s setting as well as her bit is sufficient to reproduce Bob’s transcript classically. Before either party receives an input, draw a table with one sample of Alice’s outcome at each of her settings. For each sampled outcome, draw a response for every Bob setting, conditioned on that Alice setting and outcome. In the simulation Alice generates her message using the table outcome at her actual setting. Bob receives the setting and the message, applies his original setting rule and reads the corresponding response. The table and all random controls are independent of the database. Data processing and independence of the bits bound the score by the conditional entropy of the setting and bit given this shared information, at most log 2 N + 1 \log_2N+1 log 2 N + 1 . At powers of two this bound is attained by a nonsignalling correlation (Methods). Combining this upper bound with Eq. (3) and s L > 1 / ( 185 L 3 ) s_L>1/(185L^3) s L > 1/ ( 185 L 3 ) gives, for N , L ≥ 2 N,L\ge2 N , L ≥ 2 ,
( 1 − e − 1 ) log 2 N 185 L 3 ≤ F L ( N ) ≤ log 2 N + 1. (4) \frac{(1-e^{-1})\log_2N}{185L^3}\le F_L(N)\le\log_2N+1. \tag*{(4)} 185 L 3 ( 1 − e − 1 ) log 2 N ≤ F L ( N ) ≤ log 2 N + 1. (4)
Hence F L ( N ) = Θ L ( log N ) F_L(N)=\Theta_L(\log N) F L ( N ) = Θ L ( log N ) at each fixed L ≥ 2 L\ge2 L ≥ 2 . By containment of level two in level one, this order also holds for L = 1 L=1 L = 1 .
For the correlation in Eq. (1) , the probability s L s_L s L of two zeros on equal settings fixes the leading coefficient of the optimal information gain. Let J L ( N ) J_L(N) J L ( N ) be the supremum over the same one-copy, one-bit protocols with this correlation fixed. Then
J L ( N ) = s L log 2 N + O ( 1 ) . (5) J_L(N)=s_L\log_2N+O(1). \tag*{(5)} J L ( N ) = s L log 2 N + O ( 1 ) . (5)
The additive bounds are uniform in L L L . To make Alice use every setting equally often, give her N − 1 N-1 N − 1 independent bits with Pr ( R i = 1 ) = 1 / ( N − i + 1 ) \Pr(R_i=1)=1/(N-i+1) Pr ( R i = 1 ) = 1/ ( N − i + 1 ) . She uses the first-one position, or setting N N N on an all-zero database, and sends her outcome in either case. The chosen setting is uniform over all N N N labels. For each request i < N i<N i < N , the outcome G i = 1 G_i=1 G i = 1 occurs with probability s L / N s_L/N s L / N and implies R i = 1 R_i=1 R i = 1 , an event of prior probability 1 / ( N − i + 1 ) 1/(N-i+1) 1/ ( N − i + 1 ) . The information from these outcomes sums to ( s L / N ) log 2 ( N ! ) ≥ s L log 2 N − s L log 2 e (s_L/N)\log_2(N!)\ge s_L\log_2N-s_L\log_2e ( s L / N ) log 2 ( N !) ≥ s L log 2 N − s L log 2 e .
The upper bound uses a table that reproduces Bob’s possible responses. An outcome impossible at unequal settings identifies Alice’s setting in this table. For Eq. (1) , that outcome is two zeros, with probability s L s_L s L on equal settings. In the remaining cases the table contains only a bounded amount of information about Alice’s setting (Methods and Supplementary Information).
False coincidences and the optimal score
If two zero outcomes can occur at unequal settings, Bob can see M = b = 0 M=b=0 M = b = 0 even when the addresses differ. Mix the correlation in Eq. (1) with a fixed fraction 0 < ϵ < 1 0<\epsilon<1 0 < ϵ < 1 of a local product correlation in which each party independently outputs zero with probability 0 < u N ≤ 1 / 2 0<u_N\le1/2 0 < u N ≤ 1/2 . Neither party knows which correlation was used on a given run. Write c = ( 1 − ϵ ) s L c=(1-\epsilon)s_L c = ( 1 − ϵ ) s L and t N = ϵ u N 2 t_N=\epsilon u_N^2 t N = ϵ u N 2 , so joint zeros have probability c + t N c+t_N c + t N on equal settings and t N t_N t N on unequal settings. The optimal one-copy, one-bit score for this mixture is
J N = c log 2 ( N 1 + N t N / c ) + O ( 1 ) , (6) J_N=c\log_2\left(\frac{N}{1+Nt_N/c}\right)+O(1), \tag*{(6)} J N = c log 2 ( 1 + N t N / c N ) + O ( 1 ) , (6)
with the remainder bounded uniformly in N N N and u N u_N u N at fixed s L , ϵ s_L,\epsilon s L , ϵ (Supplementary Information). The database with a uniform first-one index attains the lower bound up to an additive constant.
For this database the event M = b = 0 M=b=0 M = b = 0 has probability t N + c / N t_N+c/N t N + c / N at each request. The signal contributes c / N c/N c / N because Alice uses each address with probability 1 / N 1/N 1/ N . If N t N ≪ c Nt_N\ll c N t N ≪ c , the optimum grows as c log 2 N c\log_2N c log 2 N . If N t N ≫ c Nt_N\gg c N t N ≫ c , the scale is c log 2 ( c / t N ) c\log_2(c/t_N) c log 2 ( c / t N ) up to an additive constant. In particular u N = 1 2 N − α / 2 u_N=\frac{1}{2}N^{-\alpha/2} u N = 2 1 N − α /2 gives a coefficient c min { α , 1 } c\min\{\alpha,1\} c min { α , 1 } of log 2 N \log_2N log 2 N in the optimal score. Every α > 0 \alpha>0 α > 0 allows an unbounded growth with positive probabilities for all outcomes. Uniform binary product noise ( u N = 1 / 2 , α = 0 ) (u_N=1/2,\alpha=0) ( u N = 1/2 , α = 0 ) bounds the optimum independently of N N N for each fixed ϵ \epsilon ϵ .
To preserve a score of at least two, the noise may vary across settings. At each fixed level there is a positive tolerance in total variation, independent of N N N , such that any nonsignalling correlation within that tolerance of Eq. (1) at every setting pair achieves this score for all sufficiently large N N N (Supplementary Information).
Locality on prescribed sets of settings
How many settings must a Bell test use to detect the nonlocality of a correlation that violates the one-bit budget? Fix a level L L L , a number K K K of settings per party and a target score V V V . For sufficiently large N N N , a level-L L L correlation gives a one-copy, one-bit score above V V V , with Bell-local models on every restriction to at most K K K settings per party and all outcome probabilities at least 1 / ( 2 N ) 1/(2N) 1/ ( 2 N ) (Supplementary Information).
Mixing Eq. (1) with the deterministic outcome ( 1 , 1 ) (1,1) ( 1 , 1 ) lowers the probability of two zeros on equal settings until its restriction to any choice of at most K K K settings on each side admits a local model. Mixing the diluted correlation in equal proportions with local product noise of zero-outcome probability 1 / N 1/\sqrt{N} 1/ N preserves those local models and gives every joint outcome probability at least 1 / ( 2 N ) 1/(2N) 1/ ( 2 N ) . The first-one protocol with r = 1 / N r=1/N r = 1/ N on the resulting correlation achieves at least
( 1 − e − 1 ) log 2 N 2 max { 185 max ( L , 2 ) 3 , K + 5 } − 1. \frac{(1-e^{-1})\log_2 N}{2\max\{185\max(L,2)^3,K+5\}}-1. 2 max { 185 max ( L , 2 ) 3 , K + 5 } ( 1 − e − 1 ) log 2 N − 1.
Constructing correlations at a fixed NPA level
We must construct a positive moment matrix for Eq. (1) while keeping s L s_L s L independent of N N N . The proof has three steps: choose reference vectors with the required unnormalized probabilities, replace the vector for the identity while preserving every tested inner product, and bound the replacement norm independently of N N N . Fix L ≥ 2 L\ge2 L ≥ 2 , and let A x A_x A x and B y B_y B y be the projectors for outcome zero, with complements I − A x I-A_x I − A x and I − B y I-B_y I − B y . An ordered product of the outcome-zero projectors is a word w w w , of length ∣ w ∣ |w| ∣ w ∣ . At level L L L , the measured probabilities must admit a positive semidefinite moment matrix indexed by words of length at most L L L , with entries consistent with the projector identities and commutation across parties. The outcome-one projectors are recovered as complements. For a reference vector R N R_N R N , the vectors w R N wR_N w R N with ∣ w ∣ ≤ L |w|\le L ∣ w ∣ ≤ L define an unnormalized Gram matrix. The empty word is the identity, so its vector is R N R_N R N . Normalizing the corresponding diagonal entry to one divides every moment by ∥ R N ∥ 2 \lVert R_N\rVert^2 ∥ R N ∥ 2 .
1. Fix the unnormalized probabilities. Choose projectors and R N R_N R N with the desired unnormalized moments.
In a tensor-product block, R N R_N R N pairs orthogonal directions of Alice and Bob bearing the same setting label. Each outcome-zero projector has a component along its own labelled direction. The two projectors select a matched component exactly when x = y x=y x = y , giving ⟨ R N , A x B y R N ⟩ = δ x y \langle R_N,A_xB_yR_N\rangle=\delta_{xy} ⟨ R N , A x B y R N ⟩ = δ x y . Two auxiliary blocks, one for each party, give the unnormalized single-party zero moments from two to three and leave the joint-zero moments unchanged (Methods). The tensor-product block contributes 4 N 4N 4 N to ∥ R N ∥ 2 \lVert R_N\rVert^2 ∥ R N ∥ 2 , so ordinary normalization would send the probability on equal settings to zero.
2. Replace the identity vector. At level L L L , only the vectors with ∣ w ∣ ≤ L |w|\le L ∣ w ∣ ≤ L enter the Gram matrix. Replace the identity vector R N R_N R N by S L S_L S L , leaving the nonempty-word vectors and all their mutual inner products unchanged. Matching the inner products of S L S_L S L with those vectors to the original ones then changes only the identity diagonal. For words in the outcome-zero projectors, we require
⟨ S L , w R N ⟩ = ⟨ R N , w R N ⟩ ( 1 ≤ ∣ w ∣ ≤ L ) , C L = ∥ S L ∥ 2 . (7) \langle S_L,wR_N\rangle=\langle R_N,wR_N\rangle\quad(1\le|w|\le L), \qquad C_L=\lVert S_L\rVert^2. \tag*{(7)} ⟨ S L , w R N ⟩ = ⟨ R N , w R N ⟩ ( 1 ≤ ∣ w ∣ ≤ L ) , C L = ∥ S L ∥ 2 . (7)
These conditions fix the projection of S L S_L S L onto the span of the nonempty-word vectors, leaving its orthogonal component free. The condition at w = A x B x w=A_xB_x w = A x B x is one, so C L > 0 C_L>0 C L > 0 . Because the unnormalized joint-zero moment is one on equal settings, normalization by C L C_L C L gives s L = 1 / C L s_L=1/C_L s L = 1/ C L . It remains to make C L C_L C L independent of N N N .
The deterministic assignment in which both parties always output one gives an evaluation map ε \varepsilon ε that obeys the projector identities. This multiplicative map sends the identity to one and every nonempty word in the outcome-zero projectors to zero. We use it to change the identity moment from ∥ R N ∥ 2 \lVert R_N\rVert^2 ∥ R N ∥ 2 to C L C_L C L . For a polynomial p p p in the projectors, define
C L ℓ ( p ) = ⟨ R N , p R N ⟩ + ( C L − ∥ R N ∥ 2 ) ε ( p ) . (8) C_L\ell(p)=\langle R_N,pR_N\rangle+(C_L-\lVert R_N\rVert^2)\varepsilon(p). \tag*{(8)} C L ℓ ( p ) = ⟨ R N , p R N ⟩ + ( C L − ∥ R N ∥ 2 ) ε ( p ) . (8)
The two terms obey the projector identities, including those for the complementary outcomes. The correction gives ℓ ( I ) = 1 \ell(\mathbb{I})=1 ℓ ( I ) = 1 and vanishes on each nonempty word in the outcome-zero projectors.
The projector identities impose linear constraints on the moments; positivity still has to hold for every tested polynomial. Write a polynomial f f f of degree at most L L L as f = c I + g f=c\mathbb{I}+g f = c I + g , with c = ε ( f ) c=\varepsilon(f) c = ε ( f ) and ε ( g ) = 0 \varepsilon(g)=0 ε ( g ) = 0 . Multiplicativity gives ε ( g † g ) = 0 \varepsilon(g^\dagger g)=0 ε ( g † g ) = 0 , so the quadratic term remains ∥ g R N ∥ 2 \lVert gR_N\rVert^2 ∥ g R N ∥ 2 , involving reference moments through degree 2 L 2L 2 L . Equation (7) replaces ⟨ R N , g R N ⟩ \langle R_N,gR_N\rangle ⟨ R N , g R N ⟩ by ⟨ S L , g R N ⟩ \langle S_L,gR_N\rangle ⟨ S L , g R N ⟩ in the cross terms, which involve polynomials through degree L L L . The scalar term is ∣ c ∣ 2 C L |c|^2C_L ∣ c ∣ 2 C L . Thus
C L ℓ ( f † f ) = ∥ c S L + g R N ∥ 2 . (9) C_L\ell(f^\dagger f)=\lVert cS_L+gR_N\rVert^2. \tag*{(9)} C L ℓ ( f † f ) = ∥ c S L + g R N ∥ 2 . (9)
The identity gives ℓ ( f † f ) ≥ 0 \ell(f^\dagger f)\ge0 ℓ ( f † f ) ≥ 0 for every polynomial of degree at most L L L , making the moment matrix Γ u , v = ℓ ( u † v ) \Gamma_{u,v}=\ell(u^\dagger v) Γ u , v = ℓ ( u † v ) positive semidefinite. Expanding each outcome-one projector as the identity minus its outcome-zero projector preserves the degree bound. Each joint-outcome projector E E E has degree at most two, so at L ≥ 2 L \ge2 L ≥ 2 its probability is ℓ ( E ) = ℓ ( E † E ) ≥ 0 \ell(E) = \ell(E^\dagger E) \ge0 ℓ ( E ) = ℓ ( E † E ) ≥ 0 . Summing over either party’s outcomes gives the other party’s marginal, and the probabilities sum to ℓ ( I ) = 1 \ell(I) = 1 ℓ ( I ) = 1 . The joint-zero moments and zero-outcome marginals are the reference values divided by C L C_L C L , giving Eq. (1) with s L = 1 / C L s_L = 1/C_L s L = 1/ C L . Thus a vector satisfying Eq. (7) gives a valid level-L L L moment matrix. It remains to construct such a vector with norm bounded independently of N N N .
Bound the normalization independently of the number of settings
To choose S L S_L S L with bounded norm, give each local outcome-zero projector a direction with a component unique to its setting and components in modes common to all settings. The common components carry independent random signs, identical for Alice and Bob at each setting and mode. A product of rank-one projectors contains overlaps between consecutive directions along a sequence of settings. In the tensor-product block, a word involving both parties annihilates the reference vector unless the terminal setting in each party’s sequence is the same. When they agree, join the sequences there, reversing Bob’s. The reference pairing then requires the other endpoints to agree as well. The replacement vector pairs shared modes and inserts the corresponding signs at these endpoints. The auxiliary blocks supply the same endpoint condition for words from only one party (Methods).
For a closed sequence, or walk, the two endpoint signs in a mode multiply to one. For an open walk, expanding the overlaps assigns a mode to each step. Any overlap term with no step in the marked mode is independent of the two inserted endpoint signs, whose product has zero mean. The surviving average is a polynomial in the marked mode weight with zero constant term and degree at most the number of overlaps (Methods). Thus preserving closed-walk pairings and cancelling open-walk pairings reduces all the required inner products to finitely many conditions on the mode weights.
The longest walk has at most L − 1 L - 1 L − 1 overlaps. It suffices to choose signed coefficients whose weighted sum evaluates every polynomial of degree at most L − 1 L - 1 L − 1 at zero: the sum preserves the closed-walk averages and cancels the open-walk averages. Lagrange interpolation supplies such coefficients at L L L positive nodes proportional to ( j − 1 2 ) 2 (j - \frac{1}{2})^2 ( j − 2 1 ) 2 , for j = 1 , … , L j = 1,\ldots,L j = 1 , … , L . Splitting a coefficient equally among orthogonal modes of the same weight preserves the evaluating sum and reduces its contribution to the squared tensor-product norm in proportion to the number of modes. A mode of coefficient zero supplies the remaining weight so that the common component has squared norm 1 / 2 1/2 1/2 . The multiplicities in Methods give
C L < 185 L 3 C_L < 185L^3 C L < 185 L 3
for every N N N . Since s L = 1 / C L s_L = 1/C_L s L = 1/ C L ,
s L > 1 185 L 3 . (10) s_L > \frac{1}{185L^3}. \tag*{(10)} s L > 185 L 3 1 . (10)
The matching conditions and this norm bound give a normalized level-L L L correlation for every N N N , with s L s_L s L independent of N N N . All weights and the normalization can be chosen rational. Allowing the ratio of the zero-outcome marginals to the diagonal probability to depend on L L L gives a certificate with rate s ~ L > 1 / ( 165 L 3 ) \tilde{s}_L > 1/(165L^3) s ~ L > 1/ ( 165 L 3 ) (Supplementary Information). With the rate in Eq. (10) , Eq. (4) guarantees a violation whenever 185 L 3 < ( 1 − e − 1 ) log 2 N 185L^3 < (1-e^{-1})\log_2 N 185 L 3 < ( 1 − e − 1 ) log 2 N . The score also diverges along sequences with L = o ( ( log 2 N ) 1 / 3 ) L = o((\log_2 N)^{1/3}) L = o (( log 2 N ) 1/3 ) .
An upper bound on exact equality certificates
For any level-L L L correlation in which joint zeros are impossible at unequal settings, write s i = p ( 0 , 0 ∣ i , i ) s_i = p(0,0 \mid i,i) s i = p ( 0 , 0 ∣ i , i ) . Such an outcome is an exact equality certificate: observing it proves that the settings agree. A polynomial in J = ∑ j = 1 N A j J = \sum_{j=1}^{N} A_j J = ∑ j = 1 N A j bounds the average of the s i s_i s i , without assuming equal diagonal probabilities or marginals 3 s L 3s_L 3 s L (Methods).
For each positive odd integer K ≤ 2 L − 3 K \le2L - 3 K ≤ 2 L − 3 satisfying K 2 < 6 N + 1 K^2 < 6N + 1 K 2 < 6 N + 1 , the average diagonal rate satisfies
1 N ∑ i = 1 N s i ≤ 1 K 2 ( 1 − K 2 − 1 6 N ) − 2 . (11) \frac{1}{N}\sum_{i=1}^{N} s_i \le\frac{1}{K^2}\left(1-\frac{K^2-1}{6N}\right)^{-2}. \tag*{(11)} N 1 i = 1 ∑ N s i ≤ K 2 1 ( 1 − 6 N K 2 − 1 ) − 2 . (11)
A rate s L s_L s L feasible uniformly in N N N then obeys s L ≤ ( 2 L − 3 ) − 2 s_L \le(2L - 3)^{-2} s L ≤ ( 2 L − 3 ) − 2 , by taking K = 2 L − 3 K = 2L - 3 K = 2 L − 3 and letting N N N grow. At finite N N N , use the largest odd K ≤ 2 N K \le\sqrt{2N} K ≤ 2 N . For L ≥ ( K + 3 ) / 2 L \ge(K+3)/2 L ≥ ( K + 3 ) /2 , this bounds the average rate by ( 9 / 8 + O ( N − 1 ) ) / N (9/8 + O(N^{-1}))/N ( 9/8 + O ( N − 1 )) / N . At level N N N , the sequential projector argument recovers the exact quantum bound 1 / N 1/N 1/ N on the average joint-zero probability on equal settings for an exact certificate. For N ≥ L ≥ 2 N \ge L \ge2 N ≥ L ≥ 2 , the same argument gives s L ≤ 1 / ( L + 2 ) s_L \le1/(L+2) s L ≤ 1/ ( L + 2 ) for the family with marginals 3 s L 3s_L 3 s L (Supplementary Information).
Computing equality without errors
The same joint outcome can be used to decide whether two labels agree. Alice receives x x x and Bob receives y y y in { 1 , … , N } \{1,\ldots,N\} { 1 , … , N } . Bob may declare them equal or unequal, or abstain. Every conclusive answer must be correct. For each input pair, the probability of giving one must be at least 1 / 2 1/2 1/2 . Using the labels as measurement settings, two zero outcomes certify equality. To certify inequality, the parties share a random binary hash with independently sampled fair values at the labels, independent of the copies. Equal labels have the same hash bit; each unequal pair has different hash bits with probability 1 / 2 1/2 1/2 .
Independent copies form a correlation in the same NPA level, with tuples of copy outcomes as the local outcomes (Supplementary Information). The parties use their labels as settings in every copy. For equal labels, at least one joint zero occurs with probability 1 − ( 1 − s L ) m 1-(1-s_L)^m 1 − ( 1 − s L ) m , which is at least 1 / 2 1/2 1/2 for m = ⌈ ln 2 / [ − ln ( 1 − s L ) ] ⌉ m=\lceil\ln2/[-\ln(1-s_L)]\rceil m = ⌈ ln 2/ [ − ln ( 1 − s L )]⌉ . Alice sends her m m m outcomes and her hash bit in one message. Bob declares equality if any copy gives a joint zero, declares inequality if the hash bits differ, and otherwise abstains. The declarations are always correct, and the probability of a conclusive result is at least 1 / 2 1/2 1/2 on each input pair. Equation [10 ] bounds the message length m + 1 m+1 m + 1 by O ( L ) O(L) O ( L ) bits, independently of N N N . For N = 2 n N=2^n N = 2 n , the minimum one-way cost with quantum or commuting-operator correlations is n n n bits at this worst-case conclusive probability [10 ] . For a related equality task with one-sided error, extended IC yields a linear one-way lower bound [12 ] .
Within the three-block rank-one construction specified in Supplementary Information, with zero-outcome marginals fixed at 3 s 2 3s_2 3 s 2 , the maximum certificate probability at level two is s 2 2 = 1 / ( 35 + 18 2 ) s_2^2=1/(35+18\sqrt{2}) s 2 2 = 1/ ( 35 + 18 2 ) (Supplementary Information). A rational choice gives s 2 r a t = 7 / 424 s_2^{\mathrm{rat}}=7/424 s 2 rat = 7/424 . This takes 42 copies, for a total of 43 bits including the hash, irrespective of N N N .
Hardy and Cabello tests also use forbidden events to draw conclusions from observed probabilities. They have been developed into device-independent dimension witnesses [13 ] and self-tests of quantum states [14 , 15 ] . Hardy correlations can also assist reverse zero-error channel coding: a noiseless channel with smaller input and output alphabets can simulate a larger noisy channel with their help [16 ] . In our equality task, the zeros at unequal settings ensure that a joint-zero event cannot give a false equality declaration.
With the Bell scenario held fixed, the NPA hierarchy converges to Q c Q_c Q c [5 ] . Even there, the upper bound on a fixed Bell functional can remain above the commuting-operator value at every finite level [17 ] . Self-testing analyses of doubly-tilted CHSH inequalities have already revealed gaps between quantum maxima and high finite NPA levels [18 ] . In the binary-input, binary-output scenario, the symmetrically doubly-tilted CHSH family separates each finite level from the quantum set near its critical tilt [19 ] . With the level fixed and the number of settings growing, our one-bit protocol gives an arbitrarily large IC violation. For sufficiently large N N N , the functional in Eq. (8) assigns a negative value to a square of higher degree (Supplementary Information).
Some correlations excluded by macroscopic locality obey the necessary inequalities used in equal-bias tests [20 ] . Earlier comparisons also used Hardy’s paradox: local orthogonality tightened the available IC and macroscopic-locality bounds on its success probability [21 ] . Allowing a noisy communication channel yields additional IC constraints [22 , 23 ] . With correlated database entries, IC gives polynomial inequalities across bipartite scenarios [24 ] . A noisy-channel formulation with correlated entries also implies the Tsirelson–Landau–Masanes condition for the four normalized covariances in the binary-input, binary-output scenario [25 ] . The full behavior also depends on the marginals. Variational and matrix inequalities give single-copy tests in fixed scenarios [26 ] . Nonsignalling also imposes complementarity relations between genuine multipartite nonlocality and the nonlocality of subsets [27 ] . In multipartite scenarios IC constrains the sharing of Bell violations and device-independent key rates against individual attacks [28 , 29 ] . Communication constraints also exclude correlations through tasks beyond random access codes, independently of a particular encoding and decoding strategy [30 ] .
The communication task determines which property of a correlation is tested. Bell inequalities can be tailored to bounded-message tasks so that their violation expresses an advantage from entanglement-assisted classical communication [31 ] . Bounding how well the message reveals the sender’s input gives a different measure of communication: quantum advantage can then grow without bound in random-access and equality tasks [32 ] . With prior entanglement, the comparison also depends on whether message dimension or input distinguishability is constrained [33 ] . Allowing the communicated system itself to vary, IC-based random-access tests also constrain how locally quantum systems may be composed [34 ] .
Random-access tasks admit further operational restrictions. The receiver may request functions of the input string [35 ] , or the message may be required to conceal parities of that string [36 ] . Preparation contextuality can be witnessed through quantum advantages in oblivious communication tasks [37 ] . Semidefinite relaxations also bound quantum behaviours in prepare-and-measure contextuality scenarios [38 ] . Random-access performance also supports semi-device-independent key distribution under a dimension bound [39 ] or operational constraints on the source [40 ] . In the present task, the fixed classical message length gives the IC bound, and a single protocol exceeding it excludes the shared correlation.
Pompili and Weinmann give correlations outside the almost-quantum set that obey IC for every one-way protocol using finitely many independent copies, including adaptive protocols [41 ] . They lie outside every standard NPA level L ≥ 2 L\geq2 L ≥ 2 , since these levels are contained in the almost-quantum set. Duplicating their settings puts the example in the same scenarios as our construction: a protocol using a duplicate can use the original setting, and restricting to the original settings still gives a correlation outside Q L Q_L Q L . For each fixed L ≥ 2 L\geq2 L ≥ 2 and sufficiently large N N N , our correlation belongs to Q L Q_L Q L and violates IC in one use, whereas their extended correlation obeys IC for every one-way protocol using finitely many independent copies, including adaptive protocols, and lies outside Q L Q_L Q L . The two sets are therefore incomparable in these scenarios.
Methods
The information budget from nonsignalling and entropy rules. Let R = ( R j ) j R = (R_j)_j R = ( R j ) j be a database of independent classical entries, B B B Bob’s system before receipt of the message, and M M M Alice’s classical message. Assume a symmetric, nonnegative mutual information on these systems and their composites. It agrees with Shannon mutual information on classical registers and obeys data processing under local transformations. We also assume the chain rule,
I ( A : B C ) − I ( A : C ) = I ( B : A C ) − I ( B : C ) . I(A : BC) - I(A : C) = I(B : AC) - I(B : C). I ( A : B C ) − I ( A : C ) = I ( B : A C ) − I ( B : C ) .
This difference defines I ( A : B ∣ C ) I(A : B \mid C) I ( A : B ∣ C ) [2 , 42 , 43 ] . For request j j j , Bob obtains G j G_j G j by local processing of ( M , B ) (M, B) ( M , B ) . Write R < j R_{<j} R < j for the database entries before j j j . Data processing and the chain rule give
∑ j I ( R j : G j ) ≤ ∑ j I ( R j : M B ) ≤ ∑ j I ( R j : R < j M B ) = I ( R : M B ) . \begin{aligned}
\sum_j I(R_j : G_j) \le\sum_j I(R_j : MB) \\
&\le\sum_j I(R_j : R_{<j}MB) \\
&= I(R : MB).
\end{aligned} j ∑ I ( R j : G j ) ≤ j ∑ I ( R j : M B ) ≤ j ∑ I ( R j : R < j M B ) = I ( R : M B ) .
Independence gives I ( R j : R < j ) = 0 I(R_j : R_{<j}) = 0 I ( R j : R < j ) = 0 , so each term on the second line equals I ( R j : M B ∣ R < j ) I(R_j : MB \mid R_{<j}) I ( R j : M B ∣ R < j ) . Summing over j j j gives I ( R : M B ) I(R : MB) I ( R : M B ) by the chain rule. Before communication, nonsignalling keeps Bob’s system independent of the database. Data processing from a trivial register then gives I ( R : B ) = 0 I(R : B) = 0 I ( R : B ) = 0 . By the chain rule and I ( B : M ) ≥ 0 I(B : M) \ge0 I ( B : M ) ≥ 0 , we have I ( R : M B ) = I ( R : M ∣ B ) ≤ I ( R B : M ) I(R : MB) = I(R : M \mid B) \le I(RB : M) I ( R : M B ) = I ( R : M ∣ B ) ≤ I ( R B : M ) .
Because M M M is classical, we may introduce a copy M ′ M' M ′ to bound its information. Data processing under local copying and discarding gives I ( R B : M M ′ ) = I ( R B : M ′ ) I(RB : MM') = I(RB : M') I ( R B : M M ′ ) = I ( R B : M ′ ) , so I ( R B : M ∣ M ′ ) = 0 I(RB : M \mid M') = 0 I ( R B : M ∣ M ′ ) = 0 . Therefore
I ( R B : M ) ≤ I ( R B M ′ : M ) = I ( M ′ : M ) + I ( R B : M ∣ M ′ ) = H ( M ) . \begin{aligned}
I(RB : M) \le I(RBM' : M) \\
&= I(M' : M) + I(RB : M \mid M') = H(M).
\end{aligned} I ( R B : M ) ≤ I ( R B M ′ : M ) = I ( M ′ : M ) + I ( R B : M ∣ M ′ ) = H ( M ) .
For an m m m -bit message, H ( M ) ≤ m H(M) \le m H ( M ) ≤ m , proving the information-causality bound.
Simulating one copy with a setting label and one bit. Condition on the classical randomness used by the original protocol, which is independent of the supplied correlation. Represent a run that skips the query by a fixed setting whose outcome is ignored. Write X X X , A A A , M M M for Alice’s setting, outcome and one-bit message. Before the database and request arrive, use additional shared randomness to draw one outcome a x ∼ p A ( ⋅ ∣ x ) a_x \sim p_A(\mathord{\cdot} \mid x) a x ∼ p A ( ⋅ ∣ x ) at each Alice setting x x x . Nonsignalling makes p A p_A p A independent of Bob’s setting. Conditional on each a x a_x a x , draw responses g x ( y ) g_x(y) g x ( y ) independently from p ( ⋅ ∣ a x , x , y ) p(\mathord{\cdot} \mid a_x, x, y) p ( ⋅ ∣ a x , x , y ) for all of Bob’s settings y y y .
Alice uses a X a_X a X to generate M M M by her original rule and sends ( X , M ) (X, M) ( X , M ) . Bob chooses y y y by his original rule, which may depend on M M M , and uses g X ( y ) g_X(y) g X ( y ) as his outcome. For each request this reproduces the original joint distribution of the database and Bob’s transcript. Let T T T collect the original classical randomness and the response table. At a fixed request, Bob’s transcript is a function of ( X , M , T ) (X, M, T) ( X , M , T ) . Since T T T is independent of the database,
∑ j I ( R j : G j ) ≤ ∑ j I ( R j : X , M ∣ T ) ≤ I ( R : X , M ∣ T ) ≤ H ( X , M ∣ T ) ≤ log 2 N + 1. \begin{aligned}
\sum_j I(R_j : G_j) \le\sum_j I(R_j : X, M \mid T) \\
&\le I(R : X, M \mid T) \\
&\le H(X, M \mid T) \le\log_2 N + 1.
\end{aligned} j ∑ I ( R j : G j ) ≤ j ∑ I ( R j : X , M ∣ T ) ≤ I ( R : X , M ∣ T ) ≤ H ( X , M ∣ T ) ≤ log 2 N + 1.
The database entries are independent conditional on T T T , giving the second inequality.
For N = 2 k N = 2^k N = 2 k with k ≥ 1 k \ge1 k ≥ 1 , a nonsignalling correlation attains this bound. Give Alice k + 1 k + 1 k + 1 independent fair bits R 0 , … , R k R_0, \ldots, R_k R 0 , … , R k . She chooses x = ( R 1 ⊕ R 0 , … , R k ⊕ R 0 ) x = (R_1 \oplus R_0, \ldots, R_k \oplus R_0) x = ( R 1 ⊕ R 0 , … , R k ⊕ R 0 ) and sets x 0 = 0 x_0 = 0 x 0 = 0 . Alice’s outcome is uniform, and Bob’s outcome is b = a ⊕ R y b = a \oplus R_y b = a ⊕ R y for his setting y ∈ { 0 , … , k } y \in\{0, \ldots, k\} y ∈ { 0 , … , k } . Since k + 1 ≤ 2 k k + 1 \le2^k k + 1 ≤ 2 k , any remaining Bob settings can duplicate setting zero. Both outcome marginals are uniform, so the correlation is nonsignalling. Alice sends M = a ⊕ R 0 M = a \oplus R_0 M = a ⊕ R 0 and Bob obtains M ⊕ b = R y M \oplus b = R_y M ⊕ b = R y for every request, for a score of k + 1 k + 1 k + 1 .
For the correlation in Eq. (1) , fair database bits also attain the leading coefficient s L s_L s L . The all-ones block protocol gives a score of at least k s L [ 1 − ( 1 − 2 − k ) N ] k s_L[1 - (1 - 2^{-k})^N] k s L [ 1 − ( 1 − 2 − k ) N ] . For large N N N , take k = ⌊ log 2 N − log 2 log N ⌋ k = \lfloor\log_2 N - \log_2 \log N \rfloor k = ⌊ log 2 N − log 2 log N ⌋ . Then N 2 − k ≥ log 2 N N2^{-k} \ge\log_2 N N 2 − k ≥ log 2 N , and the score is at least s L log 2 N − O L ( log log N ) s_L \log_2 N - O_L(\log\log N) s L log 2 N − O L ( log log N ) .
The leading coefficient of the information gain. Fix two joint-outcome distributions with identical single-party marginals, using one on equal settings and the other on unequal settings. Let p p p be the equal-setting probability of outcome pairs impossible at unequal settings. For a given Alice setting and outcome, draw a table of independent responses for Bob’s possible settings. The entry at Alice’s setting uses the equal-setting conditional distribution; all other entries use the unequal-setting distribution. For each request and fixed classical randomness in the original protocol, Bob chooses his setting by the original rule, which may depend on the message, and reads that entry.
An entry impossible under the unequal-setting conditional distribution identifies Alice’s setting. Averaged over Alice’s outcome, this event has probability ρ \rho ρ . On the remaining runs, fix Alice’s outcome a a a . Let V a V_a V a be Bob’s unequal-setting outcome law and U a U_a U a his equal-setting law conditioned on outcomes possible under V a V_a V a . For any fixed Alice setting, the table differs from the reference law V a ⊗ N V_a^{\otimes N} V a ⊗ N in just one entry. Its relative entropy from that law is D ( U a ∥ V a ) D(U_a \Vert V_a) D ( U a ∥ V a ) , independent of N N N . The relative-entropy chain rule therefore bounds the table’s information about Alice’s setting by this same quantity. Averaging over Alice’s outcomes and the two kinds of runs gives an upper bound ρ log 2 N + O ( 1 ) \rho\log_2 N + O(1) ρ log 2 N + O ( 1 ) for any fixed message alphabet (Supplementary Information, Sec. S2.4). Choosing the independent bit biases so that Alice’s setting is uniform attains the coefficient whenever the message can encode her outcome. In Eq. (1) , two zeros are the only outcome pair impossible at unequal settings, so ρ = s L \rho=s_L ρ = s L .
Projectors and reference vectors. We construct the reference vector R N R_N R N and replacement vector S L S_L S L required by Eq. (7) . Choose finitely many modes α \alpha α with positive weights λ α \lambda_\alpha λ α summing to 1 / 2 1/2 1/2 , and independent fair signs σ i , α ∈ { − 1 , 1 } \sigma_{i,\alpha}\in\{-1,1\} σ i , α ∈ { − 1 , 1 } for every setting i i i and mode α \alpha α . The mode weights and coefficients below depend on L L L alone. Alice and Bob use separate local spaces with the same sign assignment.
In Alice’s space, let e i e_i e i be orthonormal setting-specific directions and g A , α g_{A,\alpha} g A , α orthonormal shared directions, orthogonal to all the e i e_i e i . Bob has corresponding directions f i f_i f i and g B , α g_{B,\alpha} g B , α . Put h A , i = ∑ α λ α σ i , α g A , α h_{A,i}=\sum_\alpha\sqrt{\lambda_\alpha}\sigma_{i,\alpha}g_{A,\alpha} h A , i = ∑ α λ α σ i , α g A , α and define h B , i h_{B,i} h B , i with the same signs. In the tensor-product block, A i A_i A i and B i B_i B i project onto the unit vectors u i = h A , i + e i / 2 u_i=h_{A,i}+e_i/\sqrt{2} u i = h A , i + e i / 2 and v i = h B , i + f i / 2 v_i=h_{B,i}+f_i/\sqrt{2} v i = h B , i + f i / 2 in their respective factors. For i ≠ j i\ne j i = j , only the shared components contribute to the overlap,
X i j = ∑ α λ α σ i , α σ j , α . (12) X_{ij}=\sum_\alpha\lambda_\alpha\sigma_{i,\alpha}\sigma_{j,\alpha}. \tag*{(12)} X ij = α ∑ λ α σ i , α σ j , α . (12)
Use T N = 2 ∑ i e i ⊗ f i T_N=2\sum_i e_i\otimes f_i T N = 2 ∑ i e i ⊗ f i as the reference vector in this block. It has squared norm 4 N 4N 4 N and satisfies A i B j T N = δ i j u i ⊗ v i A_iB_jT_N=\delta_{ij}u_i\otimes v_i A i B j T N = δ ij u i ⊗ v i . Its unnormalized joint-zero moments on equal settings are one, and its single-party zero moments are two.
The replacement vector pairs shared modes. Let ν α \nu_\alpha ν α be real coefficients, not all zero, to be chosen so that the word pairings agree. An endpoint in mode α \alpha α contributes λ α \sqrt{\lambda_\alpha} λ α ; dividing by λ α \lambda_\alpha λ α cancels the two endpoint factors and leaves coefficient ν α \nu_\alpha ν α . Thus take
S 0 = ∑ α ( ν α / λ α ) g A , α ⊗ g B , α . S_0=\sum_\alpha(\nu_\alpha/\lambda_\alpha)g_{A,\alpha}\otimes g_{B,\alpha}. S 0 = α ∑ ( ν α / λ α ) g A , α ⊗ g B , α .
For a word from only one party, the other party’s factor remains in its setting-specific subspace, so its pairing with S 0 S_0 S 0 vanishes. Add one auxiliary block with Alice’s projectors as before and all B i = 0 B_i=0 B i = 0 , and a second block with the parties interchanged. In each block the inactive party’s outcome-one projector is the identity. Choose positive q α q_\alpha q α on the modes with ν α ≠ 0 \nu_\alpha\ne0 ν α = 0 , with ∑ α q α 2 = 1 \sum_\alpha q_\alpha^2=1 ∑ α q α 2 = 1 , and use
R a u x = ∑ α : ν α ≠ 0 q α λ α g α R_{\mathrm{aux}}=\sum_{\alpha:\nu_\alpha\ne0}\frac{q_\alpha}{\sqrt{\lambda_\alpha}}g_\alpha R aux = α : ν α = 0 ∑ λ α q α g α
S a u x = ∑ α : ν α ≠ 0 q α + 2 ν α / q α λ α g α . S_{\mathrm{aux}}=\sum_{\alpha:\nu_\alpha\ne0}\frac{q_\alpha+2\nu_\alpha/q_\alpha}{\sqrt{\lambda_\alpha}}g_\alpha. S aux = α : ν α = 0 ∑ λ α q α + 2 ν α / q α g α .
In a fixed mode, these coefficients change the product of endpoint amplitudes from q α 2 q_\alpha^2 q α 2 in the reference pairing to q α 2 + 2 ν α q_\alpha^2+2\nu_\alpha q α 2 + 2 ν α in the replacement pairing. The extra term will supply the missing tensor-product contribution for one-party words.
Take R N = T N ⊕ R a u x ⊕ R a u x R_N=T_N\oplus R_{\mathrm{aux}}\oplus R_{\mathrm{aux}} R N = T N ⊕ R aux ⊕ R aux and S L = S 0 ⊕ S a u x ⊕ S a u x S_L=S_0\oplus S_{\mathrm{aux}}\oplus S_{\mathrm{aux}} S L = S 0 ⊕ S aux ⊕ S aux , using the modes in their respective spaces. The squared reference norm is 4 N + 2 ∥ R a u x ∥ 2 4N+2\lVert R_{\mathrm{aux}}\rVert^2 4 N + 2 ∥ R aux ∥ 2 . Average over signs by taking a finite direct sum over all sign assignments, weighting each vector by the square root of the assignment’s uniform probability. Each auxiliary block adds one to the active party’s unnormalized marginal and leaves all mixed moments unchanged. The complete reference therefore has joint-zero moments δ i j \delta_{ij} δ ij and single-party zero moments three, as required.
Reducing word pairings to endpoint averages. Commute projectors of different parties and remove consecutive repeated settings by idempotence. Each party’s product gives one overlap from Eq. (12) for every step along its sequence of settings. We call this sequence a walk. A one-party word has at most L − 1 L-1 L − 1 steps. A mixed word gives two walks with at most L − 2 L-2 L − 2 steps in total and acts nontrivially on T N T_N T N only when their terminal labels agree. Join Alice’s walk to the reverse of Bob’s at that label. For either kind of word, write W = ( i 0 , … , i e ) W=(i_0,\ldots,i_e) W = ( i 0 , … , i e ) for the resulting walk and M W M_W M W for its product of overlaps.
For a mixed word with matching terminal labels, pairing with T N T_N T N also requires i 0 = i e i_0=i_e i 0 = i e , giving δ i 0 i e E M W \delta_{i_0i_e}\mathbb{E}M_W δ i 0 i e E M W . Pairing with S 0 S_0 S 0 inserts the two endpoint signs in the same mode, giving
∑ α ν α E [ σ i 0 , α σ i e , α M W ] . \sum_\alpha\nu_\alpha\mathbb{E}[\sigma_{i_0,\alpha}\sigma_{i_e,\alpha}M_W]. α ∑ ν α E [ σ i 0 , α σ i e , α M W ] .
A one-party word gives 2 δ i 0 i e E M W 2\delta_{i_0i_e}\mathbb{E}M_W 2 δ i 0 i e E M W in the tensor-product reference and zero in its replacement. In its auxiliary block, a term with distinct endpoint modes averages to zero: flipping all signs in one mode reverses its sign and leaves every overlap unchanged. For equal endpoint modes, the difference between the auxiliary replacement and reference pairings is twice the sum above. It therefore suffices to make this sum equal to δ i 0 i e E M W \delta_{i_0i_e}\mathbb{E}M_W δ i 0 i e E M W for every walk of at most L − 1 L-1 L − 1 steps.
Choosing the coefficients to match every word. When the walk closes, the endpoint signs multiply to one, so ∑ α ν α = 1 \sum_\alpha\nu_\alpha=1 ∑ α ν α = 1 preserves its reference average. For a single open step, E [ σ i , α σ j , α X i j ] = λ α \mathbb{E}[\sigma_{i,\alpha}\sigma_{j,\alpha}X_{ij}]=\lambda_\alpha E [ σ i , α σ j , α X ij ] = λ α , and cancellation requires ∑ α ν α λ α = 0 \sum_\alpha\nu_\alpha\lambda_\alpha=0 ∑ α ν α λ α = 0 . Longer open walks give polynomials in the marked mode weight; their degree is bounded by the number of steps.
Fix an open walk W = ( i 0 , … , i e ) W=(i_0,\ldots,i_e) W = ( i 0 , … , i e ) with i 0 ≠ i e i_0\ne i_e i 0 = i e and write F α = E [ σ i 0 , α σ i e , α M W ] F_\alpha=\mathbb{E}[\sigma_{i_0,\alpha}\sigma_{i_e,\alpha}M_W] F α = E [ σ i 0 , α σ i e , α M W ] . Expanding the overlap product assigns a mode to each edge. A term with no edge in mode α \alpha α averages to zero because the product is independent of the two inserted signs. Group the other terms by the number r r r of edges in mode α \alpha α to obtain
F α = ∑ r = 1 e λ α r Q W , r ( ( λ β ) β ≠ α ) . F_\alpha=\sum_{r=1}^{e}\lambda_\alpha^rQ_{W,r}\bigl((\lambda_\beta)_{\beta\ne\alpha}\bigr). F α = r = 1 ∑ e λ α r Q W , r ( ( λ β ) β = α ) .
Permuting the unmarked modes leaves the sign average unchanged. Thus Q W , r Q_{W,r} Q W , r is the same symmetric polynomial for each marked mode α \alpha α , homogeneous of degree e − r e-r e − r in the other weights.
Write p k = ∑ β λ β k p_k=\sum_\beta\lambda_\beta^k p k = ∑ β λ β k for the full power sums. We express Q W , r Q_{W,r} Q W , r using the power sums over the list that omits α \alpha α . For a list with power sums P k P_k P k , let D ( d 1 , … , d m ) D(d_1,\ldots,d_m) D ( d 1 , … , d m ) be the sum of λ b 1 d 1 ⋯ λ b m d m \lambda_{b_1}^{d_1}\cdots\lambda_{b_m}^{d_m} λ b 1 d 1 ⋯ λ b m d m over distinct indices. Multiplying D ( d 2 , … , d m ) D(d_2,\ldots,d_m) D ( d 2 , … , d m ) by P d 1 P_{d_1} P d 1 allows the new index to equal one of the others. Subtract the terms with these coincidences to obtain
D ( d 1 , … , d m ) = P d 1 D ( d 2 , … , d m ) − ∑ j = 2 m D ( d 2 , … , d j + d 1 , … , d m ) . D(d_1,\ldots,d_m)=P_{d_1}D(d_2,\ldots,d_m)-\sum_{j=2}^{m}D(d_2,\ldots,d_j+d_1,\ldots,d_m). D ( d 1 , … , d m ) = P d 1 D ( d 2 , … , d m ) − j = 2 ∑ m D ( d 2 , … , d j + d 1 , … , d m ) .
Starting from D ( d 1 ) = P d 1 D(d_1)=P_{d_1} D ( d 1 ) = P d 1 gives a power-sum expression for each such symmetric sum that preserves its total degree. Grouping the monomials by their permutations writes Q W , r Q_{W,r} Q W , r as a linear combination of these sums. For the list excluding α \alpha α , use P k = p k − λ α k P_k=p_k-\lambda_\alpha^k P k = p k − λ α k . With the full sums p k p_k p k held fixed, this gives
F α = P W ( λ α ) , deg P W ≤ e , P W ( 0 ) = 0. F_\alpha=P_W(\lambda_\alpha),\qquad\deg P_W\le e,\qquad P_W(0)=0. F α = P W ( λ α ) , deg P W ≤ e , P W ( 0 ) = 0.
The coefficients of P W P_W P W are independent of α \alpha α . For the three-edge walk ( i , j , i , j ) (i,j,i,j) ( i , j , i , j ) the expression is
E [ σ i , α σ j , α X i j 3 ] = 3 p 2 λ α − 2 λ α 3 . \mathbb{E}[\sigma_{i,\alpha}\sigma_{j,\alpha}X_{ij}^{3}]=3p_2\lambda_\alpha-2\lambda_\alpha^3. E [ σ i , α σ j , α X ij 3 ] = 3 p 2 λ α − 2 λ α 3 .
To preserve closed-walk averages and cancel every open-walk polynomial of degree at most L − 1 L-1 L − 1 , choose
∑ α ν α = 1 , ∑ α ν α λ α k = 0 ( 1 ≤ k ≤ L − 1 ) . (13) \sum_\alpha\nu_\alpha=1,\qquad\sum_\alpha\nu_\alpha\lambda_\alpha^k=0\quad(1\le k\le L-1). \tag*{(13)} α ∑ ν α = 1 , α ∑ ν α λ α k = 0 ( 1 ≤ k ≤ L − 1 ) . (13)
These conditions make the signed sum evaluate every such polynomial at zero. Since P W ( 0 ) = 0 P_W(0)=0 P W ( 0 ) = 0 for an open walk, its pairing vanishes; for a closed walk, the average is unchanged. The reference and replacement vectors therefore satisfy Eq. (7) for every nonempty word of length at most L L L .
Bounding the replacement norm. We choose the interpolation weights so that ∥ S L ∥ 2 \lVert S_L\rVert^2 ∥ S L ∥ 2 grows at most cubically with L L L and is independent of N N N . For 1 ≤ j ≤ L 1\le j\le L 1 ≤ j ≤ L , let t j = j − 1 2 t_j=j-\frac12 t j = j − 2 1 , T = 4 ∑ j t j 2 = ( 4 L 3 − L ) / 3 T=4\sum_j t_j^2=(4L^3-L)/3 T = 4 ∑ j t j 2 = ( 4 L 3 − L ) /3 and λ j = 3 t j 2 / ( 2 T ) \lambda_j=3t_j^2/(2T) λ j = 3 t j 2 / ( 2 T ) . The Lagrange coefficients μ j = ∏ k ≠ j λ k / ( λ k − λ j ) \mu_j=\prod_{k\ne j}\lambda_k/(\lambda_k-\lambda_j) μ j = ∏ k = j λ k / ( λ k − λ j ) evaluate polynomials of degree at most L − 1 L-1 L − 1 at zero. They obey ∣ μ j ∣ ≤ 2 / ( π t j ) |\mu_j|\le2/(\pi t_j) ∣ μ j ∣ ≤ 2/ ( π t j ) and ∑ j μ j 2 ≤ 2 \sum_j\mu_j^2\le2 ∑ j μ j 2 ≤ 2 (Supplementary Information).
Splitting a coefficient among orthogonal modes of equal weight leaves the signed moments unchanged and reduces its contribution to the norm. At each node, take n j = ⌈ T / ( 60 t j 4 ) ⌉ n_j=\lceil T/(60t_j^4)\rceil n j = ⌈ T / ( 60 t j 4 )⌉ independent modes of weight λ j \lambda_j λ j , each with signed coefficient μ j / n j \mu_j/n_j μ j / n j . Their total weight is at most 3 / 8 + ∑ j t j − 2 / 40 ≤ 3 / 8 + π 2 / 80 < 1 / 2 3/8+\sum_jt_j^{-2}/40\le3/8+\pi^2/80<1/2 3/8 + ∑ j t j − 2 /40 ≤ 3/8 + π 2 /80 < 1/2 . Add one mode of the remaining weight with signed coefficient zero. The signed moments in Eq. (13) are unchanged by splitting the coefficients, and the squared norm of S 0 S_0 S 0 satisfies
∥ S 0 ∥ 2 = ∑ j μ j 2 n j λ j 2 ≤ 160 3 T . \lVert S_0\rVert^2=\sum_j\frac{\mu_j^2}{n_j\lambda_j^2}\le\frac{160}{3}T. ∥ S 0 ∥ 2 = j ∑ n j λ j 2 μ j 2 ≤ 3 160 T .
For the two auxiliary blocks, set H ∗ = ∑ α ∣ ν α ∣ / λ α H_*=\sum_\alpha|\nu_\alpha|/\sqrt{\lambda_\alpha} H ∗ = ∑ α ∣ ν α ∣/ λ α and q α 2 = ∣ ν α ∣ / ( H ∗ λ α ) q_\alpha^2=|\nu_\alpha|/(H_*\sqrt{\lambda_\alpha}) q α 2 = ∣ ν α ∣/ ( H ∗ λ α ) on the active modes. Then ∑ α q α 2 = 1 \sum_\alpha q_\alpha^2=1 ∑ α q α 2 = 1 and H ∗ 2 ≤ 2 π 2 T / 3 H_*^2\le2\pi^2T/3 H ∗ 2 ≤ 2 π 2 T /3 . To evaluate the signed sum that enters the auxiliary norm, use the polynomial [ 1 − ∏ j ( 1 − z / λ j ) ] / z [1-\prod_j(1-z/\lambda_j)]/z [ 1 − ∏ j ( 1 − z / λ j )] / z . It takes the value 1 / λ j 1/\lambda_j 1/ λ j at node j j j and ∑ j 1 / λ j \sum_j1/\lambda_j ∑ j 1/ λ j at zero. Interpolation gives ∑ α ν α / λ α = ∑ j 1 / λ j ≤ π 2 T / 3 \sum_\alpha\nu_\alpha/\lambda_\alpha=\sum_j1/\lambda_j\le\pi^2T/3 ∑ α ν α / λ α = ∑ j 1/ λ j ≤ π 2 T /3 . The remaining sum ∑ α q α 2 / λ α \sum_\alpha q_\alpha^2/\lambda_\alpha ∑ α q α 2 / λ α is at most 1 / λ 1 = 8 T / 3 1/\lambda_1=8T/3 1/ λ 1 = 8 T /3 . The expanded auxiliary norm then obeys
∥ S a u x ∥ 2 = ∑ α q α 2 λ α + 4 ∑ α ν α λ α + 4 H ∗ 2 ≤ ( 8 3 + 4 π 2 ) T . \lVert S_{\mathrm{aux}}\rVert^2=\sum_\alpha\frac{q_\alpha^2}{\lambda_\alpha}+4\sum_\alpha\frac{\nu_\alpha}{\lambda_\alpha}+4H_*^2
\le\left(\frac{8}{3}+4\pi^2\right)T. ∥ S aux ∥ 2 = α ∑ λ α q α 2 + 4 α ∑ λ α ν α + 4 H ∗ 2 ≤ ( 3 8 + 4 π 2 ) T .
so adding the three blocks gives
C L ≤ ( 176 3 + 8 π 2 ) T < 1664 9 L 3 < 185 L 3 . C_L\le\left(\frac{176}{3}+8\pi^2\right)T<\frac{1664}{9}L^3<185L^3. C L ≤ ( 3 176 + 8 π 2 ) T < 9 1664 L 3 < 185 L 3 .
For a mode of weight λ j \lambda_j λ j , the factor H ∗ λ j = t j ∑ k ∣ μ k ∣ / t k H_*\sqrt{\lambda_j}=t_j\sum_k|\mu_k|/t_k H ∗ λ j = t j ∑ k ∣ μ k ∣/ t k is rational. All weights, signed coefficients and q α 2 q_\alpha^2 q α 2 are rational, so the norm formula gives rational C L C_L C L and s L = 1 / C L s_L=1/C_L s L = 1/ C L .
Polynomial bound for exact certificates. Suppose joint zeros are impossible on unequal settings. At level L ≥ 2 L\ge2 L ≥ 2 , let the moment vector for A j B i A_jB_i A j B i then vanishes whenever j ≠ i j\ne i j = i , since its squared norm is p ( 0 , 0 ∣ j , i ) p(0,0\mid j,i) p ( 0 , 0 ∣ j , i ) . With J = ∑ j = 1 N A j J=\sum_{j=1}^{N}A_j J = ∑ j = 1 N A j , the vectors for J B i JB_i J B i and A i B i A_iB_i A i B i coincide. This fixes the first two moments of J J J at B i B_i B i to s i s_i s i . We use a polynomial q ( J ) q(J) q ( J ) to make the sum of squared moment norms of A i q ( J ) A_iq(J) A i q ( J ) small. The same polynomial keeps the inner products of A i q ( J ) B i A_iq(J)B_i A i q ( J ) B i with the diagonal vectors A i B i A_iB_i A i B i large. Summing these overlaps gives a lower bound in terms of ∑ i s i \sum_i s_i ∑ i s i . The polynomial’s degree determines the level needed for both bounds.
Let ℓ \ell ℓ be the normalized level-L L L moment functional of an exact equality certificate and write ∥ f ∥ ℓ 2 = ℓ ( f † f ) \lVert f\rVert_\ell^2=\ell(f^\dagger f) ∥ f ∥ ℓ 2 = ℓ ( f † f ) for the moment seminorm of a polynomial with deg f ≤ L \deg f\le L deg f ≤ L . Choose K = 2 d + 1 K=2d+1 K = 2 d + 1 with 0 ≤ d ≤ L − 2 0\le d\le L-2 0 ≤ d ≤ L − 2 and K 2 < 6 N + 1 K^2<6N+1 K 2 < 6 N + 1 . For x = N sin 2 θ x=N\sin^2\theta x = N sin 2 θ , 0 ≤ θ ≤ π / 2 0\le\theta\le\pi/2 0 ≤ θ ≤ π /2 , define the degree-d d d polynomials
q ( x ) = sin ( K θ ) K sin θ , t ( x ) = cos ( K θ ) cos θ . q(x)=\frac{\sin(K\theta)}{K\sin\theta},\qquad t(x)=\frac{\cos(K\theta)}{\cos\theta}. q ( x ) = K sin θ sin ( K θ ) , t ( x ) = cos θ cos ( K θ ) .
Both quotients have continuous extensions at the endpoints. The sum of squared moment norms of A i q ( J ) A_iq(J) A i q ( J ) is ℓ ( J q ( J ) 2 ) \ell(Jq(J)^2) ℓ ( J q ( J ) 2 ) . To bound it, use
N K 2 − x q ( x ) 2 = N − x K 2 t ( x ) 2 . \frac{N}{K^2}-xq(x)^2=\frac{N-x}{K^2}t(x)^2. K 2 N − x q ( x ) 2 = K 2 N − x t ( x ) 2 .
At J J J , the right-hand side is a sum of squares of K − 1 ( 1 − A j ) t ( J ) K^{-1}(1-A_j)t(J) K − 1 ( 1 − A j ) t ( J ) , giving ℓ ( J q ( J ) 2 ) ≤ N / K 2 \ell(Jq(J)^2) \le N/K^2 ℓ ( J q ( J ) 2 ) ≤ N / K 2 .
To control the diagonal overlaps, set Δ = 1 − ( K 2 − 1 ) / ( 6 N ) > 0 \Delta= 1-(K^2-1)/(6N)>0 Δ = 1 − ( K 2 − 1 ) / ( 6 N ) > 0 and h ( x ) = x [ q ( x ) − 1 + ( K 2 − 1 ) x / ( 6 N ) ] h(x)=x[q(x)-1+(K^2-1)x/(6N)] h ( x ) = x [ q ( x ) − 1 + ( K 2 − 1 ) x / ( 6 N )] . The first two moments of J J J at B i B_i B i both equal s i s_i s i , so we need ℓ ( B i h ( J ) B i ) ≥ 0 \ell(B_i h(J) B_i)\ge0 ℓ ( B i h ( J ) B i ) ≥ 0 . The cosine expansion of q q q writes h h h as a positive weighted sum of x 2 sin 2 ( r θ ) x^2\sin^2(r\theta) x 2 sin 2 ( r θ ) for integers 1 ≤ r ≤ d − 1 1\le r\le d-1 1 ≤ r ≤ d − 1 . These terms are nonnegative multiples of x 3 P ( x ) 2 x^3P(x)^2 x 3 P ( x ) 2 for odd r r r and x 3 ( N − x ) P ( x ) 2 x^3(N-x)P(x)^2 x 3 ( N − x ) P ( x ) 2 for even r r r , for polynomials P P P of suitable degree. With J = ∑ j A j 2 J=\sum_j A_j^2 J = ∑ j A j 2 and J ( N − J ) = ∑ j < k ( A j − A k ) 2 J(N-J)=\sum_{j<k}(A_j-A_k)^2 J ( N − J ) = ∑ j < k ( A j − A k ) 2 , the expression B i h ( J ) B i B_i h(J) B_i B i h ( J ) B i is a sum of squares of polynomials of degree at most d + 2 d+2 d + 2 (Supplementary Information). Since d + 2 ≤ L d+2\le L d + 2 ≤ L , level-L L L positivity applies to these squares.
Using ℓ ( B i J B i ) = ℓ ( B i J 2 B i ) = s i \ell(B_iJB_i)=\ell(B_iJ^2B_i)=s_i ℓ ( B i J B i ) = ℓ ( B i J 2 B i ) = s i now yields ℓ ( B i J q ( J ) B i ) ≥ Δ s i \ell(B_iJq(J)B_i)\ge\Delta s_i ℓ ( B i J q ( J ) B i ) ≥ Δ s i . Since the vectors for J B i JB_i J B i and A i B i A_iB_i A i B i coincide, idempotence of A i A_i A i makes this last moment the inner product of A i B i A_iB_i A i B i with A i q ( J ) B i A_iq(J)B_i A i q ( J ) B i . Both vectors have degree at most d + 2 ≤ L d+2\le L d + 2 ≤ L . Cauchy–Schwarz gives ∥ A i q ( J ) B i ∥ ℓ 2 ≥ Δ 2 s i \lVert A_iq(J)B_i\rVert_\ell^2\ge\Delta^2s_i ∥ A i q ( J ) B i ∥ ℓ 2 ≥ Δ 2 s i . By commutation across parties, the squared seminorm ∥ A i q ( J ) ∥ ℓ 2 \lVert A_iq(J)\rVert_\ell^2 ∥ A i q ( J ) ∥ ℓ 2 splits into contributions from B i B_i B i and its complementary outcome, so it bounds the B i B_i B i contribution from above. Summing over i i i gives Δ 2 ∑ i s i ≤ ℓ ( J q ( J ) 2 ) ≤ N / K 2 \Delta^2\sum_i s_i\le\ell(Jq(J)^2)\le N/K^2 Δ 2 ∑ i s i ≤ ℓ ( J q ( J ) 2 ) ≤ N / K 2 .
M.P. acknowledges support from the International Research Agendas programme of the Foundation for Polish Science (FNP), through the ICTQT 2.0 project (FENG.02.01-IP.05-0006/23), financed by the European Funds for Smart Economy 2021–2027, Priority FENG.02, Measure FENG.02.01.
Acknowledgments
References
Alice sends Bob her outcome as a single bit. When that bit and his own outcome are both zero, Bob knows that their settings agree. At each fixed NPA level, we construct correlations for which the probability of two zero outcomes on equal settings stays constant as the number of settings grows. In the database protocol, a joint zero outcome certifies that the requested bit is one and gives more information when the prior probability of a one is smaller. With independent copies and a shared random hash, Bob can decide equality of long strings without error on conclusive runs.
The finite-level equality certificate
Fix an integer hierarchy level L ≥ 2 L \ge2 L ≥ 2 . We allow the number of settings N N N to be any positive integer and seek one certificate probability that works for all of them. Alice’s and Bob’s settings are i , j ∈ { 1 , … , N } i,j \in\{1,\ldots,N\} i , j ∈ { 1 , … , N } , and their respective outcomes are a , b ∈ { 0 , 1 } a,b \in\{0,1\} a , b ∈ { 0 , 1 } . Write p ( a , b ∣ i , j ) p(a,b \mid i,j) p ( a , b ∣ i , j ) for the conditional probabilities and p A , p B p_A,p_B p A , p B for their marginals. The joint outcome ( 0 , 0 ) (0,0) ( 0 , 0 ) must be impossible for unequal settings. On equal settings it will have the same probability s L s_L s L for every label. We construct a rational s L > ( 185 L 3 ) − 1 s_L > (185L^3)^{-1} s L > ( 185 L 3 ) − 1 and a correlation at level L L L of the Navascués–Pironio–Acín (NPA) hierarchy with the following probabilities, where δ i j = 1 \delta_{ij}=1 δ ij = 1 if i = j i=j i = j and δ i j = 0 \delta_{ij}=0 δ ij = 0 otherwise,
p ( 00 ∣ i , j ) = s L δ i j , p A ( 0 ∣ i ) = p B ( 0 ∣ i ) = 3 s L . p(00 \mid i,j)=s_L\delta_{ij}, \qquad p_A(0 \mid i)=p_B(0 \mid i)=3s_L. p ( 00 ∣ i , j ) = s L δ ij , p A ( 0 ∣ i ) = p B ( 0 ∣ i ) = 3 s L .
Write Q L ( N , N , 2 , 2 ) Q_L(N,N,2,2) Q L ( N , N , 2 , 2 ) for the set of correlations that satisfy the level-L L L NPA moment constraints.
Positivity at a finite level
In a projector model, apply an ordered product of measurement projectors to the state. The resulting vectors give a Gram matrix, with an entry for each inner product between two such vectors. The level-L L L test asks for a positive semidefinite matrix of this form through words of length L L L , with entries obeying all equalities implied by the projector relations.
Let [ N ] = { 1 , … , N } [N]=\{1,\ldots,N\} [ N ] = { 1 , … , N } . We use the unital complex ∗ * ∗ -algebra generated by A i A_i A i and B j B_j B j , the projectors for outcome 0 0 0 at Alice’s setting i i i and Bob’s setting j j j . The local generators are self-adjoint and idempotent, and projectors belonging to different parties commute,
A i ∗ = A i 2 = A i , B j ∗ = B j 2 = B j , A i B j = B j A i . (14) A_i^*=A_i^2=A_i,\qquad B_j^*=B_j^2=B_j,\qquad A_iB_j=B_jA_i. \tag*{(14)} A i ∗ = A i 2 = A i , B j ∗ = B j 2 = B j , A i B j = B j A i . (14)
The outcome-1 projectors are 1 − A i 1-A_i 1 − A i and 1 − B j 1-B_j 1 − B j . Words in the generators multiply by concatenation, and the adjoint reverses the order of the letters. The empty word is 1 1 1 , and the length of a word is its number of letters. A degree-at-most-L L L polynomial is a linear combination of words of length at most L L L . Using a complementary outcome in a word preserves this bound after expansion.
In a commuting-operator model with unit state vector ψ \psi ψ , the moment of a polynomial f f f is ⟨ ψ , f ψ ⟩ \langle\psi,f\psi\rangle ⟨ ψ , f ψ ⟩ , with the inner product linear in its second argument. At level L L L of the NPA hierarchy [5 ] , candidate moments are the values of a linear functional ℓ \ell ℓ on the projector algebra. The functional satisfies ℓ ( 1 ) = 1 \ell(1)=1 ℓ ( 1 ) = 1 and ℓ ( f ∗ f ) ≥ 0 \ell(f^*f)\ge0 ℓ ( f ∗ f ) ≥ 0 for every f f f of degree at most L L L . Thus Γ u , v = ℓ ( u ∗ v ) \Gamma_{u,v}=\ell(u^*v) Γ u , v = ℓ ( u ∗ v ) is a positive semidefinite matrix on the words of length at most L L L . For f = ∑ v α v v f=\sum_v\alpha_vv f = ∑ v α v v , the quadratic form is ℓ ( f ∗ f ) = ∑ u , v α u ‾ Γ u , v α v \ell(f^*f)=\sum_{u,v}\overline{\alpha_u}\Gamma_{u,v}\alpha_v ℓ ( f ∗ f ) = ∑ u , v α u Γ u , v α v . The products u ∗ v u^*v u ∗ v can have length up to 2 L 2L 2 L . If two products agree in the algebra, evaluating ℓ \ell ℓ gives the same entry for both. We write Q L Q_L Q L for the set of correlations with such a matrix. For example, the entry for u = A i u=A_i u = A i and v = B j v=B_j v = B j is the joint zero-outcome probability. The entries for u = 1 u=1 u = 1 and v = A i v=A_i v = A i or B j B_j B j give the single-party zero-outcome probabilities.
We start with projectors and an unnormalized reference vector R N R_N R N whose joint moments are ⟨ R N , A i B j R N ⟩ = δ i j \langle R_N,A_iB_jR_N\rangle=\delta_{ij} ⟨ R N , A i B j R N ⟩ = δ ij . The construction assigns a private direction to each setting, so the squared norm of the reference vector grows with N N N . Normalizing the vectors R N R_N R N by ∥ R N ∥ \|R_N\| ∥ R N ∥ would make the certificate probability ∥ R N ∥ − 2 \|R_N\|^{-2} ∥ R N ∥ − 2 tend to zero. The normalization comes entirely from the entry for the empty word paired with itself. We look for a replacement S L S_L S L of bounded norm for that word, preserving its pairings with every nonempty word w w w of length ∣ w ∣ ≤ L |w|\le L ∣ w ∣ ≤ L ,
⟨ S L , w R N ⟩ = ⟨ R N , w R N ⟩ ( 0 < ∣ w ∣ ≤ L ) . (15) \langle S_L,wR_N\rangle=\langle R_N,wR_N\rangle\qquad(0<|w|\le L). \tag*{(15)} ⟨ S L , w R N ⟩ = ⟨ R N , w R N ⟩ ( 0 < ∣ w ∣ ≤ L ) . (15)
Equation (S2) leaves all entries involving nonempty words at their reference values before normalization. Dividing the Gram vectors by ∥ S L ∥ \|S_L\| ∥ S L ∥ now gives a joint diagonal probability of ∥ S L ∥ − 2 \|S_L\|^{-2} ∥ S L ∥ − 2 . The replacement must match a separate pairing for every retained word. We use independent signs to enforce their common dependence on the first and last labels of the word.
Averaging the random signs
In a product of rank-one projectors, each pair of successive projectors supplies the overlap of their unit vectors. The settings in a word can therefore be read as a walk, with an overlap for each step. The private directions in R N R_N R N select matching endpoint labels. To reproduce that selection using common directions, we assign each common direction its own independent signs and form a weighted average with the signs at both endpoints inserted.
Index these common directions, or modes, by α \alpha α . Choose finitely many weights λ α > 0 \lambda_\alpha> 0 λ α > 0 with total 1 / 2 1/2 1/2 . The real, signed coefficients ν α \nu_\alpha ν α will reproduce the reference endpoint condition. A word of length at most L L L gives at most L − 1 L-1 L − 1 successive overlaps. The sign average below is a polynomial in the marked mode weight of at most this degree. We therefore require the signed coefficients to preserve its constant term and cancel powers one through L − 1 L-1 L − 1 ,
∑ α ν α = 1 , ∑ α ν α λ α k = 0 ( 1 ≤ k ≤ L − 1 ) . (16) \sum_\alpha\nu_\alpha= 1,\qquad\sum_\alpha\nu_\alpha\lambda_\alpha^k = 0\quad(1\leq k\leq L-1). \tag*{(16)} α ∑ ν α = 1 , α ∑ ν α λ α k = 0 ( 1 ≤ k ≤ L − 1 ) . (16)
For each pair ( i , α ) (i,\alpha) ( i , α ) , draw an independent uniform sign σ i , α ∈ { − 1 , 1 } \sigma_{i,\alpha}\in\{-1,1\} σ i , α ∈ { − 1 , 1 } . In the orthonormal common basis g α g_\alpha g α , the vector h i = ∑ α λ α σ i , α g α h_i=\sum_\alpha\sqrt{\lambda_\alpha}\sigma_{i,\alpha}g_\alpha h i = ∑ α λ α σ i , α g α has squared norm 1 / 2 1/2 1/2 and overlaps X i j = ⟨ h i , h j ⟩ = ∑ α λ α σ i , α σ j , α X_{ij}=\langle h_i,h_j\rangle=\sum_\alpha\lambda_\alpha\sigma_{i,\alpha}\sigma_{j,\alpha} X ij = ⟨ h i , h j ⟩ = ∑ α λ α σ i , α σ j , α . Write E \mathbb{E} E for expectation over the signs. For a one-step walk between distinct settings, inserting the signs from mode α \alpha α at both ends leaves only the term λ α \lambda_\alpha λ α after averaging. Its signed sum is zero by Eq. (16) . For any walk W = ( i 0 , … , i e ) W=(i_0,\ldots,i_e) W = ( i 0 , … , i e ) of 0 ≤ e ≤ L − 1 0\leq e\leq L-1 0 ≤ e ≤ L − 1 steps, let M W = ∏ t = 1 e X i t − 1 , i t M_W=\prod_{t=1}^{e}X_{i_{t-1},i_t} M W = ∏ t = 1 e X i t − 1 , i t , with the empty product equal to one. Write 1 E \mathbf{1}_E 1 E for the indicator of a condition E E E . The same signed average gives the ordinary overlap average when the walk closes and zero when its endpoints differ,
∑ α ν α E [ σ i 0 , α σ i e , α M W ] = 1 i 0 = i e E M W . (17) \sum_\alpha\nu_\alpha\mathbb{E}[\sigma_{i_0,\alpha}\sigma_{i_e,\alpha}M_W]=\mathbf{1}_{i_0=i_e}\mathbb{E}M_W. \tag*{(17)} α ∑ ν α E [ σ i 0 , α σ i e , α M W ] = 1 i 0 = i e E M W . (17)
Give each step t t t its own formal variable z t z_t z t , including when the walk revisits a setting. The exponential exp ( ∑ t z t X i t − 1 , i t ) \exp\left(\sum_t z_tX_{i_{t-1},i_t}\right) exp ( ∑ t z t X i t − 1 , i t ) factors into one exponential for each step. Taking the coefficient of z 1 ⋯ z e z_1\cdots z_e z 1 ⋯ z e selects the linear term from every factor and therefore gives M W M_W M W , even when two steps use the same pair of settings. For independent uniform signs ϵ i \epsilon_i ϵ i in a single mode, write G G G for the series averaging the exponential and H H H for the series averaging it with the two endpoint signs inserted,
G ( z ) = E e ∑ t z t ϵ i t − 1 ϵ i t , H ( z ) = E [ ϵ i 0 ϵ i e e ∑ t z t ϵ i t − 1 ϵ i t ] . G(z)=\mathbb{E}e^{\sum_t z_t\epsilon_{i_{t-1}}\epsilon_{i_t}},\qquad H(z)=\mathbb{E}\left[\epsilon_{i_0}\epsilon_{i_e}e^{\sum_t z_t\epsilon_{i_{t-1}}\epsilon_{i_t}}\right]. G ( z ) = E e ∑ t z t ϵ i t − 1 ϵ i t , H ( z ) = E [ ϵ i 0 ϵ i e e ∑ t z t ϵ i t − 1 ϵ i t ] .
Independence across modes factors the expectation. An insertion in mode α \alpha α replaces its G G G factor by H H H , so the two averages have the same coefficient formula with a single extra quotient. Write [ z 1 ⋯ z e ] [z_1\cdots z_e] [ z 1 ⋯ z e ] for the coefficient of that monomial,
E M W = [ z 1 ⋯ z e ] ∏ β G ( λ β z ) , \mathbb{E}M_W=[z_1\cdots z_e]\prod_\beta G(\lambda_\beta z), E M W = [ z 1 ⋯ z e ] β ∏ G ( λ β z ) ,
E [ σ i 0 , α σ i e , α M W ] = [ z 1 ⋯ z e ] ( ∏ β G ( λ β z ) ) H ( λ α z ) G ( λ α z ) . \mathbb{E}[\sigma_{i_0,\alpha}\sigma_{i_e,\alpha}M_W]=[z_1\cdots z_e]\left(\prod_\beta G(\lambda_\beta z)\right)\frac{H(\lambda_\alpha z)}{G(\lambda_\alpha z)}. E [ σ i 0 , α σ i e , α M W ] = [ z 1 ⋯ z e ] β ∏ G ( λ β z ) G ( λ α z ) H ( λ α z ) .
Since G ( 0 ) = 1 G(0)=1 G ( 0 ) = 1 , the quotient is a formal power series. For each monomial of degree k k k , its coefficient in the quotient for mode α \alpha α is its coefficient in H ( z ) / G ( z ) H(z)/G(z) H ( z ) / G ( z ) times λ α k \lambda_\alpha^k λ α k . Equation Eq. (16) cancels degrees 1 1 1 through L − 1 L-1 L − 1 in the signed sum of quotients. The remaining constant term is H ( 0 ) = E [ ϵ i 0 ϵ i e ] = 1 i 0 = i e H(0)=\mathbb{E}[\epsilon_{i_0}\epsilon_{i_e}]=\mathbf{1}_{i_0=i_e} H ( 0 ) = E [ ϵ i 0 ϵ i e ] = 1 i 0 = i e . Multiplying the sum by ∏ β G ( λ β z ) \prod_\beta G(\lambda_\beta z) ∏ β G ( λ β z ) and extracting the coefficient of z 1 ⋯ z e z_1\cdots z_e z 1 ⋯ z e gives Eq. (17) . The product can only use quotient terms of degree at most e e e , so the higher powers of the mode weights are immaterial at level L L L .
Polynomial in the marked weight
For an open walk, the endpoint average is a polynomial in the marked mode’s weight, with coefficients common to all marked modes. Let W = ( i 0 , … , i e ) W=(i_0,\ldots,i_e) W = ( i 0 , … , i e ) have distinct endpoints, and mark a mode α \alpha α . Expand the product M W M_W M W by assigning a mode to each of its e e e edge positions. A term that never uses α \alpha α vanishes after averaging the inserted endpoint signs. Every remaining term contains at least one factor λ α \lambda_\alpha λ α .
Fix the nonempty set of positions that use α \alpha α , and partition the remaining positions according to equality of their mode labels. Order these blocks by their first position. If their sizes are d 1 , … , d r d_1,\ldots,d_r d 1 , … , d r , the sum of weights over the possible distinct unmarked labels is
D α ( d 1 , … , d r ) = ∑ β 1 , … , β r ≠ α pairwise distinct λ β 1 d 1 ⋯ λ β r d r . D_\alpha(d_1,\ldots,d_r)=\sum_{\substack{\beta_1,\ldots,\beta_r\ne\alpha\\\text{pairwise distinct}}}\lambda_{\beta_1}^{d_1}\cdots\lambda_{\beta_r}^{d_r}. D α ( d 1 , … , d r ) = β 1 , … , β r = α pairwise distinct ∑ λ β 1 d 1 ⋯ λ β r d r .
The sign expectation for this assignment pattern is independent of the names of these labels. Modes with equal numerical weights can have distinct labels in this sum.
Put q k = ∑ β ≠ α λ β k q_k=\sum_{\beta\ne\alpha}\lambda_\beta^k q k = ∑ β = α λ β k and D α ( ∅ ) = 1 D_\alpha(\varnothing)=1 D α ( ∅ ) = 1 . Multiplying q d 1 q_{d_1} q d 1 by the distinct-index sum for the other blocks includes all allowed assignments. It also includes assignments in which the first index coincides with exactly one of the other, mutually distinct indices. Subtracting them gives
D α ( d 1 , … , d r ) = q d 1 D α ( d 2 , … , d r ) − ∑ j = 2 r D α ( d 2 , … , d j + d 1 , … , d r ) . D_\alpha(d_1,\ldots,d_r)=q_{d_1}D_\alpha(d_2,\ldots,d_r)-\sum_{j=2}^{r}D_\alpha(d_2,\ldots,d_j+d_1,\ldots,d_r). D α ( d 1 , … , d r ) = q d 1 D α ( d 2 , … , d r ) − j = 2 ∑ r D α ( d 2 , … , d j + d 1 , … , d r ) .
Induction on the number of blocks expresses every such sum in the q k q_k q k . Giving q k q_k q k degree k k k preserves the total degree d 1 + ⋯ + d r d_1+\cdots+d_r d 1 + ⋯ + d r .
Now define the full sums p k = ∑ β λ β k p_k=\sum_\beta\lambda_\beta^k p k = ∑ β λ β k and replace q k q_k q k by p k − t k p_k-t^k p k − t k . If the marked mode occupied k k k edge positions, its pattern contributes t k D α ( d 1 , … , d r ) t^kD_\alpha(d_1,\ldots,d_r) t k D α ( d 1 , … , d r ) after this substitution, with degree at most e e e and a factor t t t . Summing the patterns gives one polynomial P W ( t ) P_W(t) P W ( t ) for which
E [ σ i 0 , α σ i e , α M W ] = P W ( λ α ) , deg P W ≤ e , P W ( 0 ) = 0. \mathbb{E}[\sigma_{i_0,\alpha}\sigma_{i_e,\alpha}M_W]=P_W(\lambda_\alpha),\qquad\deg P_W\le e,\qquad P_W(0)=0. E [ σ i 0 , α σ i e , α M W ] = P W ( λ α ) , deg P W ≤ e , P W ( 0 ) = 0.
All coefficients depend on the walk and on the full sums, which are fixed for every evaluation. The conditions in Eq. (16) therefore cancel the polynomial when e ≤ L − 1 e\le L-1 e ≤ L − 1 . Closed walks need only ∑ α ν α = 1 \sum_\alpha\nu_\alpha=1 ∑ α ν α = 1 , since their endpoint signs multiply to one.
The projector construction
The outcome-zero projectors need a common part to carry the overlap products and a private part to select matching labels. In Alice’s space let g A , α g_{A,\alpha} g A , α be the orthonormal common modes and e i e_i e i the orthonormal private directions, perpendicular to all the common modes. Use g B , α g_{B,\alpha} g B , α and f i f_i f i in Bob’s space. The parties use the same signs to construct their common vectors h A , i h_{A,i} h A , i and h B , i h_{B,i} h B , i by the formula for h i h_i h i . In the tensor-product block, A i , B i A_i,B_i A i , B i project onto u i = h A , i + e i / 2 u_i=h_{A,i}+e_i/\sqrt{2} u i = h A , i + e i / 2 and v i = h B , i + f i / 2 v_i=h_{B,i}+f_i/\sqrt{2} v i = h B , i + f i / 2 in their respective factors and act as the identity on the other factor. Both vectors are unit. Their within-party overlaps are X i j + δ i j / 2 X_{ij}+\delta_{ij}/2 X ij + δ ij /2 , so only X i j X_{ij} X ij enters when successive labels are distinct. The reference vector pairs matching private directions. The replacement pairs common directions, with 1 / λ α 1/\lambda_\alpha 1/ λ α cancelling the two endpoint factors of λ α \sqrt{\lambda_\alpha} λ α ,
R 0 = 2 ∑ i e i ⊗ f i , S 0 = ∑ α ( ν α / λ α ) g A , α ⊗ g B , α . R_0=2\sum_i e_i\otimes f_i,\qquad S_0=\sum_\alpha(\nu_\alpha/\lambda_\alpha)g_{A,\alpha}\otimes g_{B,\alpha}. R 0 = 2 i ∑ e i ⊗ f i , S 0 = α ∑ ( ν α / λ α ) g A , α ⊗ g B , α .
Applying one projector in each party gives A i B j R 0 = δ i j u i ⊗ v j A_iB_jR_0=\delta_{ij}u_i\otimes v_j A i B j R 0 = δ ij u i ⊗ v j . A word with projectors from just one party, called a pure word, leaves a private direction in the other factor. This direction gives zero pairing with S 0 S_0 S 0 . We supply the missing pairings in one auxiliary block for each party, where the other party’s outcome-zero projectors vanish and every mixed word is zero. In Alice’s block A i A_i A i projects onto u i u_i u i and B i = 0 B_i=0 B i = 0 . Bob’s block interchanges the roles. In each of these local spaces let g α g_\alpha g α denote its common directions. Take q α > 0 q_\alpha>0 q α > 0 on the modes with ν α ≠ 0 \nu_\alpha\ne0 ν α = 0 , q α = 0 q_\alpha=0 q α = 0 otherwise, and ∑ α q α 2 = 1 \sum_\alpha q_\alpha^2=1 ∑ α q α 2 = 1 . The reference amplitude at the endpoint of a pure word is q α σ i , α q_{\alpha}\sigma_{i,\alpha} q α σ i , α . The replacement adds an endpoint term ( 2 ν α / q α ) σ i , α (2\nu_{\alpha}/q_{\alpha})\sigma_{i,\alpha} ( 2 ν α / q α ) σ i , α , so the two amplitudes supply 2 ν α 2\nu_{\alpha} 2 ν α when the endpoint modes agree. Use
R a u x = ∑ α : ν α ≠ 0 q α λ α g α , S a u x = ∑ α : ν α ≠ 0 q α + 2 ν α / q α λ α g α . R_{\mathrm{aux}}=\sum_{\alpha:\nu_{\alpha}\ne0}\frac{q_{\alpha}}{\sqrt{\lambda_{\alpha}}}g_{\alpha},\qquad S_{\mathrm{aux}}=\sum_{\alpha:\nu_{\alpha}\ne0}\frac{q_{\alpha}+2\nu_{\alpha}/q_{\alpha}}{\sqrt{\lambda_{\alpha}}}g_{\alpha}. R aux = α : ν α = 0 ∑ λ α q α g α , S aux = α : ν α = 0 ∑ λ α q α + 2 ν α / q α g α .
For each sign assignment use the direct sums R 0 ⊕ R a u x ⊕ R a u x R_0\oplus R_{\mathrm{aux}}\oplus R_{\mathrm{aux}} R 0 ⊕ R aux ⊕ R aux and S 0 ⊕ S a u x ⊕ S a u x S_0\oplus S_{\mathrm{aux}}\oplus S_{\mathrm{aux}} S 0 ⊕ S aux ⊕ S aux . Take a further direct sum over all assignments, weighting each vector in an assignment by the square root of its probability. The resulting reference and replacement vectors are denoted by R N R_N R N and S L S_L S L . The projectors act separately on each assignment and commute across parties. An inner product of the complete vectors is the average of the sum of the three block pairings. The squared norm of S L S_L S L is independent of N N N and determined by λ α \lambda_{\alpha} λ α , ν α \nu_{\alpha} ν α , q α q_{\alpha} q α .
For a pure Alice word w w w , idempotence removes consecutive equal settings. Read the remaining labels from left to right as the walk W = ( i 0 , … , i e ) W=(i_0,\ldots,i_e) W = ( i 0 , … , i e ) . The rightmost projector acts first, selecting the private direction with label i e i_e i e . For a fixed assignment, w R 0 = 2 M W u i 0 ⊗ f i e wR_0=\sqrt{2}M_Wu_{i_0}\otimes f_{i_e} w R 0 = 2 M W u i 0 ⊗ f i e . Pairing with R 0 R_0 R 0 and averaging gives 21 i 0 = i e E M W 2\mathbf{1}_{i_0=i_e}\mathbb{E}M_W 2 1 i 0 = i e E M W . Pairing with S 0 S_0 S 0 gives zero because of the private Bob factor f i e f_{i_e} f i e . The difference ⟨ S a u x − R a u x , w R a u x ⟩ \langle S_{\mathrm{aux}}-R_{\mathrm{aux}},wR_{\mathrm{aux}}\rangle ⟨ S aux − R aux , w R aux ⟩ of the replacement and reference pairings in Alice’s auxiliary block must equal the missing reference pairing. For that difference, each terminal projector supplies λ α σ i , α \sqrt{\lambda_{\alpha}}\sigma_{i,\alpha} λ α σ i , α , cancelling the denominator in the auxiliary vector. Insert the added amplitude ( 2 ν α / q α ) σ i 0 , α (2\nu_{\alpha}/q_{\alpha})\sigma_{i_0,\alpha} ( 2 ν α / q α ) σ i 0 , α at the first endpoint and the reference amplitude q β σ i e , β q_{\beta}\sigma_{i_e,\beta} q β σ i e , β at the last endpoint to obtain
2 ∑ α , β ν α q β q α E [ σ i 0 , α σ i e , β M W ] . 2\sum_{\alpha,\beta}\frac{\nu_{\alpha}q_{\beta}}{q_{\alpha}}\mathbb{E}[\sigma_{i_0,\alpha}\sigma_{i_e,\beta}M_W]. 2 α , β ∑ q α ν α q β E [ σ i 0 , α σ i e , β M W ] .
where both sums are over modes with nonzero coefficient. When α ≠ β \alpha\ne\beta α = β , flipping the signs at every setting in mode α \alpha α preserves M W M_W M W and changes the sign of the integrand. Only α = β \alpha=\beta α = β survives the average. Equation (17) gives exactly the tensor-product reference pairing. The pure Bob words obey the same identity after interchanging the parties.
For a mixed word, cross-party commutation collects Alice’s and Bob’s projectors into two ordered products. Idempotence removes consecutive equal labels in each product, giving w = A i 1 ⋯ A i p B j 1 ⋯ B j q w=A_{i_1}\cdots A_{i_p}B_{j_1}\cdots B_{j_q} w = A i 1 ⋯ A i p B j 1 ⋯ B j q with p , q ≥ 1 p,q\ge1 p , q ≥ 1 and p + q ≤ L p+q\le L p + q ≤ L . Let M A , M B M_A,M_B M A , M B be the overlap products along the two walks. The auxiliary blocks vanish. In the tensor-product block the two rightmost local projectors must act on the same private label of R 0 R_0 R 0 , so within an assignment
w R 0 = 1 i p = j q M A M B u i 1 ⊗ v j 1 . wR_0=\mathbf{1}_{i_p=j_q}M_AM_Bu_{i_1}\otimes v_{j_1}. w R 0 = 1 i p = j q M A M B u i 1 ⊗ v j 1 .
If the terminal labels agree, append Bob’s reversed walk to Alice’s walk. Because X i j = X j i X_{ij}=X_{ji} X ij = X j i , the joined walk has overlap product M A M B M_AM_B M A M B . It runs from i 1 i_1 i 1 to j 1 j_1 j 1 in ( p − 1 ) + ( q − 1 ) ≤ L − 2 (p-1)+(q-1)\le L-2 ( p − 1 ) + ( q − 1 ) ≤ L − 2 steps. In its pairing with R 0 R_0 R 0 , the coefficient two cancels the two private endpoint amplitudes 1 / 2 1/\sqrt{2} 1/ 2 . Averaging gives 1 i 1 = j 1 E ( M A M B ) \mathbf{1}_{i_1=j_1}\mathbb{E}(M_AM_B) 1 i 1 = j 1 E ( M A M B ) . In the pairing with S 0 S_0 S 0 , the coefficient ν α / λ α \nu_{\alpha}/\lambda_{\alpha} ν α / λ α cancels the two shared endpoint amplitudes λ α \sqrt{\lambda_{\alpha}} λ α , leaving the two endpoint signs with weight ν α \nu_{\alpha} ν α . Equation (17) gives ⟨ S L , w R N ⟩ = ⟨ R N , w R N ⟩ \langle S_L,wR_N\rangle=\langle R_N,wR_N\rangle ⟨ S L , w R N ⟩ = ⟨ R N , w R N ⟩ for every nonempty word of length at most L L L .
Normalization and positivity of the moment matrix
To preserve the projector identities while changing the empty-word diagonal, let ε \varepsilon ε be evaluation at the deterministic assignment of outcome 1 to every setting. It is an algebra character, meaning that it takes products to products. It respects Eq. (14) and maps the identity to one and every nonempty word in outcome-zero projectors to zero. Write C L = ∥ S L ∥ 2 C_L=\|S_L\|^2 C L = ∥ S L ∥ 2 . The character lets us change the empty-word entry from ∥ R N ∥ 2 \|R_N\|^2 ∥ R N ∥ 2 to C L C_L C L while keeping every nonempty moment at its reference value before normalization,
C L ℓ ( p ) = ⟨ R N , p R N ⟩ + ( C L − ∥ R N ∥ 2 ) ε ( p ) . (18) C_L\ell(p)=\langle R_N,pR_N\rangle+(C_L-\|R_N\|^2)\varepsilon(p). \tag*{(18)} C L ℓ ( p ) = ⟨ R N , p R N ⟩ + ( C L − ∥ R N ∥ 2 ) ε ( p ) . (18)
For N ≥ 1 N \ge1 N ≥ 1 , the vector A i B i R N A_iB_iR_N A i B i R N has norm one and inner product one with S L S_L S L . Thus Cauchy–Schwarz gives C L ≥ 1 C_L \ge1 C L ≥ 1 . Evaluating Eq. (18) at the identity gives ℓ ( 1 ) = 1 \ell(1)=1 ℓ ( 1 ) = 1 . Both terms are functionals on the quotient algebra, so ℓ \ell ℓ respects adjoints and every projector identity in every context.
The character’s coefficient in Eq. (18) may be negative. Positivity through level L L L comes from the matched pairings. Take a complex polynomial f f f of degree at most L L L . Write f = c 1 + g f=c1+g f = c 1 + g , where c = ε ( f ) c=\varepsilon(f) c = ε ( f ) and ε ( g ) = 0 \varepsilon(g)=0 ε ( g ) = 0 , so g g g is a combination of nonempty words of degree at most L L L . Equation (15) matches the terms linear in g g g , and ε ( g ∗ g ) = 0 \varepsilon(g^*g)=0 ε ( g ∗ g ) = 0 leaves the quadratic term ⟨ R N , g ∗ g R N ⟩ \langle R_N,g^*gR_N\rangle ⟨ R N , g ∗ g R N ⟩ from the reference vector. The constant term has coefficient C L C_L C L , so all three terms come from the squared norm of the same linear combination of Gram vectors,
C L ℓ ( f ∗ f ) = ∥ c S L + g R N ∥ 2 ≥ 0. (19) C_L\ell(f^*f)=\lVert cS_L+gR_N\rVert^2\ge0. \tag*{(19)} C L ℓ ( f ∗ f ) = ∥ c S L + g R N ∥ 2 ≥ 0. (19)
Equation (19) proves positivity of the moment matrix indexed by words of length at most L L L , whose pairwise products can have length up to 2 L 2L 2 L .
For outcome a a a , write A i 0 = A i A_i^0=A_i A i 0 = A i , A i 1 = 1 − A i A_i^1=1-A_i A i 1 = 1 − A i , and similarly for Bob. A product of these projectors expands to words of at most its original degree. Its moment matrix is therefore positive by the same square identity. The full outcome projectors obey orthogonality, completeness, self-adjointness, idempotence and cross-party commutation in the algebra, so their moments satisfy the corresponding NPA equalities. Each joint outcome E = A i a B j b E=A_i^aB_j^b E = A i a B j b is a self-adjoint projector of degree at most two. Since L ≥ 2 L\ge2 L ≥ 2 , p ( a , b ∣ i , j ) = ℓ ( E ) = ℓ ( E ∗ E ) ≥ 0 p(a,b\mid i,j)=\ell(E)=\ell(E^*E)\ge0 p ( a , b ∣ i , j ) = ℓ ( E ) = ℓ ( E ∗ E ) ≥ 0 . Completeness makes the joint projectors sum to one. Summing over one party’s outcomes gives the other party’s marginal projector regardless of the first party’s setting, proving nonsignalling.
The tensor-product block gives unnormalized mixed moments δ i j \delta_{ij} δ ij and singleton moments two. The auxiliary block for that singleton adds E ( ∑ α q α σ i , α ) 2 = ∑ α q α 2 = 1 \mathbb{E}\left(\sum_\alpha q_\alpha\sigma_{i,\alpha}\right)^2=\sum_\alpha q_\alpha^2=1 E ( ∑ α q α σ i , α ) 2 = ∑ α q α 2 = 1 . The functional therefore gives
ℓ ( A i B j ) = δ i j C L , ℓ ( A i ) = ℓ ( B i ) = 3 C L . (20) \ell(A_iB_j)=\frac{\delta_{ij}}{C_L},\qquad\ell(A_i)=\ell(B_i)=\frac{3}{C_L}. \tag*{(20)} ℓ ( A i B j ) = C L δ ij , ℓ ( A i ) = ℓ ( B i ) = C L 3 . (20)
With s L = 1 / C L s_L=1/C_L s L = 1/ C L , the marginals and normalization give
b = 0 b = 1 a = 0 s L δ i j 3 s L − s L δ i j a = 1 3 s L − s L δ i j 1 − 6 s L + s L δ i j (21) \begin{array}{c|cc}
& b=0 & b=1\\
\hline
a=0 & s_L\delta_{ij} & 3s_L-s_L\delta_{ij}\\
a=1 & 3s_L-s_L\delta_{ij} & 1-6s_L+s_L\delta_{ij} \tag*{(21)}
\end{array} a = 0 a = 1 b = 0 s L δ ij 3 s L − s L δ ij b = 1 3 s L − s L δ ij 1 − 6 s L + s L δ ij (21)
We denote this correlation by p L p_L p L . An upper bound on C L C_L C L gives a lower bound on its diagonal rate s L s_L s L .
A cubic bound on the normalization
For 1 ≤ j ≤ L 1\le j\le L 1 ≤ j ≤ L , we use interpolation nodes proportional to the squares of the half-integers t j = j − 1 2 t_j=j-\frac{1}{2} t j = j − 2 1 ,
T = 4 ∑ j = 1 L t j 2 = 4 L 3 − L 3 , λ j = 3 t j 2 2 T . T=4\sum_{j=1}^{L}t_j^2=\frac{4L^3-L}{3},\qquad\lambda_j=\frac{3t_j^2}{2T}. T = 4 j = 1 ∑ L t j 2 = 3 4 L 3 − L , λ j = 2 T 3 t j 2 .
The Lagrange coefficient for evaluation at zero is
μ j = ∏ k ≠ j λ k λ k − λ j = 2 ( − 1 ) j − 1 P 2 t j ( L − j ) ! ( L + j − 1 ) ! , P = ( 2 L ) ! 4 L L ! . (22) \mu_j=\prod_{k\ne j}\frac{\lambda_k}{\lambda_k-\lambda_j}
=\frac{2(-1)^{j-1}P^2}{t_j(L-j)!(L+j-1)!},\qquad P=\frac{(2L)!}{4^LL!}. \tag*{(22)} μ j = k = j ∏ λ k − λ j λ k = t j ( L − j )! ( L + j − 1 )! 2 ( − 1 ) j − 1 P 2 , P = 4 L L ! ( 2 L )! . (22)
The factorial formula uses t k 2 − t j 2 = ( k − j ) ( k + j − 1 ) t_k^2-t_j^2=(k-j)(k+j-1) t k 2 − t j 2 = ( k − j ) ( k + j − 1 ) . For every polynomial F F F of degree at most L − 1 L-1 L − 1 , ∑ j μ j F ( λ j ) = F ( 0 ) \sum_j\mu_jF(\lambda_j)=F(0) ∑ j μ j F ( λ j ) = F ( 0 ) . Since ( L − j ) ! ( L + j − 1 ) ! (L-j)!(L+j-1)! ( L − j )! ( L + j − 1 )! increases with j j j , P 2 / [ ( L − 1 ) ! L ! ] = L [ 4 − L ( 2 L L ) ] 2 P^2/[(L-1)!L!]=L[4^{-L}\binom{2L}{L}]^2 P 2 / [( L − 1 )! L !] = L [ 4 − L ( L 2 L ) ] 2 bounds the ratio of P 2 P^2 P 2 to the factorial product for every node. To bound this last expression, write a = 4 − L ( 2 L L ) a=4^{-L}\binom{2L}{L} a = 4 − L ( L 2 L ) . The integrals of sin 2 L θ \sin^{2L}\theta sin 2 L θ and sin 2 L − 1 θ \sin^{2L-1}\theta sin 2 L − 1 θ over [ 0 , π / 2 ] [0,\pi/2] [ 0 , π /2 ] equal π a / 2 \pi a/2 π a /2 and 1 / ( 2 L a ) 1/(2La) 1/ ( 2 L a ) respectively. The first is at most the second, so L a 2 ≤ 1 / π La^2\le1/\pi L a 2 ≤ 1/ π . Using ∑ j ≥ 1 t j − 2 = π 2 / 2 \sum_{j\ge1}t_j^{-2}=\pi^2/2 ∑ j ≥ 1 t j − 2 = π 2 /2 gives
∣ μ j ∣ ≤ 2 π t j 2 , ∑ j = 1 L μ j 2 ≤ 2. (23) |\mu_j|\le\frac{2}{\pi t_j^2},\qquad\sum_{j=1}^{L}\mu_j^2\le2. \tag*{(23)} ∣ μ j ∣ ≤ π t j 2 2 , j = 1 ∑ L μ j 2 ≤ 2. (23)
Use n j n_j n j independent modes of weight λ j \lambda_j λ j , each with signed coefficient ν α = μ j / n j \nu_\alpha=\mu_j/n_j ν α = μ j / n j , where
n j = ⌊ T 60 t j 4 ⌋ . (24) n_j=\left\lfloor\frac{T}{60t_j^4}\right\rfloor. \tag*{(24)} n j = ⌊ 60 t j 4 T ⌋ . (24)
Their total weight satisfies
∑ j n j λ j ≤ ∑ j λ j + 1 40 ∑ j t j − 2 ≤ 3 8 + π 2 80 < 1 2 . \sum_j n_j\lambda_j\le\sum_j\lambda_j+\frac{1}{40}\sum_j t_j^{-2}\le\frac{3}{8}+\frac{\pi^2}{80}<\frac{1}{2}. j ∑ n j λ j ≤ j ∑ λ j + 40 1 j ∑ t j − 2 ≤ 8 3 + 80 π 2 < 2 1 .
Add one mode of the remaining weight with signed coefficient zero. Each replicated node keeps the same aggregate signed coefficient, so the conditions in Eq. (16) hold. Its squared norm contribution is divided by the multiplicity, giving
∥ S 0 ∥ 2 = ∑ j μ j 2 n j λ j 2 ≤ 80 3 T ∑ j μ j 2 ≤ 160 3 T . \lVert S_0\rVert^2=\sum_j\frac{\mu_j^2}{n_j\lambda_j^2}\le\frac{80}{3}T\sum_j\mu_j^2\le\frac{160}{3}T. ∥ S 0 ∥ 2 = j ∑ n j λ j 2 μ j 2 ≤ 3 80 T j ∑ μ j 2 ≤ 3 160 T .
To give the auxiliary block unnormalized marginal one, set q α 2 = ∣ ν α ∣ / ( H ∗ λ α ) q_\alpha^2=|\nu_\alpha|/(H_*\sqrt{\lambda_\alpha}) q α 2 = ∣ ν α ∣/ ( H ∗ λ α ) on the active modes and zero on the added mode, with
H ∗ = ∑ α ∣ ν α ∣ λ α = ∑ j ∣ μ j ∣ λ j ≤ π 2 T 3 . H_*=\sum_\alpha\frac{|\nu_\alpha|}{\sqrt{\lambda_\alpha}}=\sum_j\frac{|\mu_j|}{\sqrt{\lambda_j}}\le\pi\sqrt{\frac{2T}{3}}. H ∗ = α ∑ λ α ∣ ν α ∣ = j ∑ λ j ∣ μ j ∣ ≤ π 3 2 T .
These squared amplitudes sum to one. The exact auxiliary norm is
∥ S a u x ∥ 2 = ∑ α : ν α ≠ 0 q α 2 λ α + 4 ∑ α ν α λ α + 4 H ∗ 2 . \lVert S_{\mathrm{aux}}\rVert^2=\sum_{\alpha:\nu_\alpha\ne0}\frac{q_\alpha^2}{\lambda_\alpha}+4\sum_\alpha\frac{\nu_\alpha}{\lambda_\alpha}+4H_*^2. ∥ S aux ∥ 2 = α : ν α = 0 ∑ λ α q α 2 + 4 α ∑ λ α ν α + 4 H ∗ 2 .
Here the first sum is at most 1 / λ 1 = 8 T / 3 1/\lambda_1=8T/3 1/ λ 1 = 8 T /3 . To evaluate the signed sum, interpolate the degree-L − 1 L-1 L − 1 polynomial
F ( z ) = 1 − ∏ j = 1 L ( 1 − z / λ j ) z . F(z)=\frac{1-\prod_{j=1}^{L}(1-z/\lambda_j)}{z}. F ( z ) = z 1 − ∏ j = 1 L ( 1 − z / λ j ) .
It takes the value 1 / λ j 1/\lambda_j 1/ λ j at each node and has constant term ∑ j 1 / λ j \sum_j1/\lambda_j ∑ j 1/ λ j . Hence
∑ α ν α λ α = ∑ j μ j λ j = ∑ j 1 λ j ≤ π 2 T 3 . \sum_\alpha\frac{\nu_\alpha}{\lambda_\alpha}=\sum_j\frac{\mu_j}{\lambda_j}=\sum_j\frac{1}{\lambda_j}\le\frac{\pi^2T}{3}. α ∑ λ α ν α = j ∑ λ j μ j = j ∑ λ j 1 ≤ 3 π 2 T .
It follows that ∥ S a u x ∥ 2 ≤ ( 8 / 3 + 4 π 2 ) T \lVert S_{\mathrm{aux}}\rVert^2\le(8/3+4\pi^2)T ∥ S aux ∥ 2 ≤ ( 8/3 + 4 π 2 ) T . Adding the tensor-product block and the two auxiliary blocks gives
C L ≤ ( 176 3 + 8 π 2 ) T < 1664 9 L 3 < 185 L 3 , s L > 1 185 L 3 . (25) C_L\le\left(\frac{176}{3}+8\pi^2\right)T<\frac{1664}{9}L^3<185L^3,\qquad s_L>\frac{1}{185L^3}. \tag*{(25)} C L ≤ ( 3 176 + 8 π 2 ) T < 9 1664 L 3 < 185 L 3 , s L > 185 L 3 1 . (25)
All the mode weights and signed coefficients are rational. For each active mode of weight λ j \lambda_j λ j , the factor H ∗ λ j = t j ∑ k ∣ μ k ∣ / t k H_*\sqrt{\lambda_j}=t_j\sum_k|\mu_k|/t_k H ∗ λ j = t j ∑ k ∣ μ k ∣/ t k is rational, so q α 2 q_\alpha^2 q α 2 is rational. The expanded norm is a rational expression in these quantities, giving rational C L C_L C L , s L s_L s L and probabilities in Eq. (21) .
A larger guaranteed rate with level-dependent marginals
Allowing the unnormalized marginals to depend on L L L gives a guaranteed diagonal rate s ~ L > 1 / ( 165 L 3 ) \tilde{s}_L>1/(165L^3) s ~ L > 1/ ( 165 L 3 ) . For each L ≥ 2 L\ge2 L ≥ 2 there are rational s ~ L \tilde{s}_L s ~ L and β L = O ( log L ) \beta_L=O(\log L) β L = O ( log L ) such that the following correlation belongs to Q L ( N , N , 2 , 2 ) Q_L(N,N,2,2) Q L ( N , N , 2 , 2 ) for every N N N ,
p ( 0 , 0 ∣ i , j ) = s ~ L δ i j , p(0,0\mid i,j)=\tilde{s}_L\delta_{ij}, p ( 0 , 0 ∣ i , j ) = s ~ L δ ij ,
p ( 0 , 1 ∣ i , j ) = p ( 1 , 0 ∣ i , j ) = s ~ L ( β L − δ i j ) , p(0,1\mid i,j)=p(1,0\mid i,j)=\tilde{s}_L(\beta_L-\delta_{ij}), p ( 0 , 1 ∣ i , j ) = p ( 1 , 0 ∣ i , j ) = s ~ L ( β L − δ ij ) ,
p ( 1 , 1 ∣ i , j ) = 1 − 2 β L s ~ L + s ~ L δ i j . p(1,1\mid i,j)=1-2\beta_L\tilde{s}_L+\tilde{s}_L\delta_{ij}. p ( 1 , 1 ∣ i , j ) = 1 − 2 β L s ~ L + s ~ L δ ij .
The one-bit protocol using joint zero outcomes has the same score bound with s ~ L \widetilde{s}_L s L in place of s L s_L s L .
Keep the expressions for the reference and replacement vectors and set q ~ α 2 = 2 ∣ ν ~ α ∣ \widetilde{q}_{\alpha}^{2}=2|\widetilde{\nu}_{\alpha}| q α 2 = 2∣ ν α ∣ on the active modes.
The difference between the auxiliary vectors has coefficient 2 ν ~ α / ( q ~ α λ ~ α ) 2\widetilde{\nu}_{\alpha}/(\widetilde{q}_{\alpha}\sqrt{\widetilde{\lambda}_{\alpha}}) 2 ν α / ( q α λ α ) in mode α \alpha α . Its product with the corresponding reference coefficient still gives the signed pairing after the endpoint overlaps contribute λ ~ α \widetilde{\lambda}_{\alpha} λ α . Therefore the empty-word pairings agree by the same interpolation conditions. The two unnormalized marginals are now β L = 2 + ∑ α q ~ α 2 = 2 + 2 ∑ α ∣ ν ~ α ∣ \beta_L=2+\sum_{\alpha}\widetilde{q}_{\alpha}^{2}=2+2\sum_{\alpha}|\widetilde{\nu}_{\alpha}| β L = 2 + ∑ α q α 2 = 2 + 2 ∑ α ∣ ν α ∣ . The squared numerator of each auxiliary replacement coefficient is 8 ν ~ α 8\widetilde{\nu}_{\alpha} 8 ν α if ν ~ α > 0 \widetilde{\nu}_{\alpha}>0 ν α > 0 and zero if ν ~ α < 0 \widetilde{\nu}_{\alpha}<0 ν α < 0 . Thus
C ~ L = ∑ α ν ~ α 2 λ ~ α 2 + 16 ∑ α : ν ~ α > 0 ν ~ α λ ~ α . \widetilde{C}_L=\sum_{\alpha}\frac{\widetilde{\nu}_{\alpha}^{2}}{\widetilde{\lambda}_{\alpha}^{2}}+16\sum_{\alpha:\widetilde{\nu}_{\alpha}>0}\frac{\widetilde{\nu}_{\alpha}}{\widetilde{\lambda}_{\alpha}}. C L = α ∑ λ α 2 ν α 2 + 16 α : ν α > 0 ∑ λ α ν α .
Use nodes λ ~ j = t j 2 / T \widetilde{\lambda}_j=t_j^2/T λ j = t j 2 / T . A common rescaling of the nodes leaves the Lagrange coefficients μ j \mu_j μ j unchanged. Split μ j \mu_j μ j equally among n ~ j = ⌈ T / ( 2 π 2 t j 2 ) ⌉ \widetilde{n}_j=\lceil T/(2\pi^2t_j^2)\rceil n j = ⌈ T / ( 2 π 2 t j 2 )⌉ independent modes at λ ~ j \widetilde{\lambda}_j λ j . Their total weight is at most 1 / 4 + ∑ j = 1 L t j − 2 / ( 2 π 2 ) < 1 / 2 1/4+\sum_{j=1}^{L}t_j^{-2}/(2\pi^2)<1/2 1/4 + ∑ j = 1 L t j − 2 / ( 2 π 2 ) < 1/2 . Add one mode of the remaining weight with signed coefficient zero. The first sum in C ~ L \widetilde{C}_L C L is bounded by
∑ j μ j 2 n ~ j λ ~ j 2 ≤ 2 π 2 T ∑ j μ j 2 ≤ 4 π 2 T . \sum_j\frac{\mu_j^2}{\widetilde{n}_j\widetilde{\lambda}_j^2}\le2\pi^2T\sum_j\mu_j^2\le4\pi^2T. j ∑ n j λ j 2 μ j 2 ≤ 2 π 2 T j ∑ μ j 2 ≤ 4 π 2 T .
The positive coefficients occur at odd j j j . Equation (23) gives
16 ∑ j o d d μ j λ ~ j ≤ 32 T π ∑ j o d d t j − 3 ≤ 32 T π ( 8 + 2 9 ) , 16\sum_{j\ \mathrm{odd}}\frac{\mu_j}{\widetilde{\lambda}_j}\le\frac{32T}{\pi}\sum_{j\ \mathrm{odd}}t_j^{-3}\le\frac{32T}{\pi}\left(8+\frac{2}{9}\right), 16 j odd ∑ λ j μ j ≤ π 32 T j odd ∑ t j − 3 ≤ π 32 T ( 8 + 9 2 ) ,
where t 1 − 3 = 8 t_1^{-3}=8 t 1 − 3 = 8 and the contribution of j ≥ 3 j\ge3 j ≥ 3 is bounded by ∫ 2 ∞ ( z − 1 2 ) − 3 d z = 2 / 9 \int_{2}^{\infty}(z-\frac{1}{2})^{-3}\,dz=2/9 ∫ 2 ∞ ( z − 2 1 ) − 3 d z = 2/9 . Adding both terms gives
C ~ L ≤ ( 4 π 2 + 2368 9 π ) T < 165 L 3 , s ~ L = 1 / C ~ L . \widetilde{C}_L\le\left(4\pi^2+\frac{2368}{9\pi}\right)T<165L^3,\qquad\widetilde{s}_L=1/\widetilde{C}_L. C L ≤ ( 4 π 2 + 9 π 2368 ) T < 165 L 3 , s L = 1/ C L .
The strict inequality uses 3.14 < π < 22 / 7 3.14<\pi<22/7 3.14 < π < 22/7 and T < 4 L 3 / 3 T<4L^3/3 T < 4 L 3 /3 . The weights and signed coefficients are rational, so C ~ L \widetilde{C}_L C L , s ~ L \widetilde{s}_L s L and β L \beta_L β L are rational. The bound ∑ α ∣ ν ~ α ∣ = ∑ j ∣ μ j ∣ ≤ ( 2 / π ) ∑ j 1 / t j \sum_{\alpha}|\widetilde{\nu}_{\alpha}|=\sum_j|\mu_j|\le(2/\pi)\sum_j1/t_j ∑ α ∣ ν α ∣ = ∑ j ∣ μ j ∣ ≤ ( 2/ π ) ∑ j 1/ t j gives β L = O ( log L ) \beta_L=O(\log L) β L = O ( log L ) .
Normalization required by the sign construction
The signed-moment conditions already force a cubic cost in the tensor-product term ∥ S 0 ∥ 2 = ∑ α ν α 2 / λ α 2 \|S_0\|^2=\sum_{\alpha}\nu_{\alpha}^2/\lambda_{\alpha}^2 ∥ S 0 ∥ 2 = ∑ α ν α 2 / λ α 2 . List the positive mode weights in decreasing order λ ( 1 ) ≥ λ ( 2 ) ≥ ⋯ \lambda_{(1)}\ge\lambda_{(2)}\ge\cdots λ ( 1 ) ≥ λ ( 2 ) ≥ ⋯ , including repetitions. There are at least L L L distinct weights with nonzero coefficient. Otherwise a polynomial of degree at most L − 1 L-1 L − 1 that vanishes at all such weights and equals one at zero would violate Eq. (16) .
Fix 1 ≤ u ≤ L 1\le u\le L 1 ≤ u ≤ L , put r = λ ( u ) r=\lambda_{(u)} r = λ ( u ) and d = L − u d=L-u d = L − u . The total weight 1 / 2 1/2 1/2 gives r ≤ 1 / ( 2 u ) r\le1/(2u) r ≤ 1/ ( 2 u ) . For x = sin 2 θ ∈ [ 0 , 1 ] x=\sin^2\theta\in[0,1] x = sin 2 θ ∈ [ 0 , 1 ] , define
q d ( x ) = sin ( ( 2 d + 1 ) θ ) ( 2 d + 1 ) sin θ . q_d(x)=\frac{\sin((2d+1)\theta)}{(2d+1)\sin\theta}. q d ( x ) = ( 2 d + 1 ) sin θ sin (( 2 d + 1 ) θ ) .
The expansion sin ( ( 2 d + 1 ) θ ) / sin θ = 1 + 2 ∑ j = 1 d cos ( 2 j θ ) \sin((2d+1)\theta)/\sin\theta=1+2\sum_{j=1}^{d}\cos(2j\theta) sin (( 2 d + 1 ) θ ) / sin θ = 1 + 2 ∑ j = 1 d cos ( 2 j θ ) gives a polynomial of degree d d d with q d ( 0 ) = 1 q_d(0)=1 q d ( 0 ) = 1 . It satisfies x ∣ q d ( x ) ∣ ≤ ( 2 d + 1 ) − 1 \sqrt{x}|q_d(x)|\le(2d+1)^{-1} x ∣ q d ( x ) ∣ ≤ ( 2 d + 1 ) − 1 . Rescale it to [ 0 , r ] [0,r] [ 0 , r ] and include factors that vanish on the first u − 1 u-1 u − 1 weights,
p ( x ) = q d ( x / r ) ∏ j = 1 u − 1 ( 1 − x / λ ( j ) ) . p(x)=q_d(x/r)\prod_{j=1}^{u-1}(1-x/\lambda_{(j)}). p ( x ) = q d ( x / r ) j = 1 ∏ u − 1 ( 1 − x / λ ( j ) ) .
This polynomial has degree at most L − 1 L-1 L − 1 and p ( 0 ) = 1 p(0)=1 p ( 0 ) = 1 . At every remaining weight the product lies in [ 0 , 1 ] [0,1] [ 0 , 1 ] . In particular λ α ∣ p ( λ α ) ∣ ≤ r / ( 2 d + 1 ) \sqrt{\lambda_{\alpha}}|p(\lambda_{\alpha})|\le\sqrt{r}/(2d+1) λ α ∣ p ( λ α ) ∣ ≤ r / ( 2 d + 1 ) at every mode weight. Signed evaluation and Cauchy–Schwarz give
1 = ∑ α ν α p ( λ α ) ≤ r 2 d + 1 ∑ α ∣ ν α ∣ λ α ≤ r ( 2 d + 1 ) 2 ∥ S 0 ∥ . 1=\sum_{\alpha}\nu_{\alpha}p(\lambda_{\alpha})\le\frac{\sqrt{r}}{2d+1}\sum_{\alpha}\frac{|\nu_{\alpha}|}{\sqrt{\lambda_{\alpha}}}\le\frac{\sqrt{r}}{(2d+1)\sqrt{2}}\|S_0\|. 1 = α ∑ ν α p ( λ α ) ≤ 2 d + 1 r α ∑ λ α ∣ ν α ∣ ≤ ( 2 d + 1 ) 2 r ∥ S 0 ∥.
Using r ≤ 1 / ( 2 u ) r \le1/(2u) r ≤ 1/ ( 2 u ) and maximizing over u u u gives
C L ≥ ∥ S 0 ∥ 2 2 ≥ max 1 ≤ u ≤ L 4 u ( 2 L + 1 − 2 u ) 2 . C_L \ge\lVert S_0\rVert_2^2 \ge\max_{1\le u\le L} 4u(2L+1-2u)^2. C L ≥ ∥ S 0 ∥ 2 2 ≥ 1 ≤ u ≤ L max 4 u ( 2 L + 1 − 2 u ) 2 .
Choosing u = 1 u=1 u = 1 gives C L ≥ 36 C_L \ge36 C L ≥ 36 for all L ≥ 2 L \ge2 L ≥ 2 . An admissible integer nearest to ( 2 L + 1 ) / 6 (2L+1)/6 ( 2 L + 1 ) /6 gives lim inf L → ∞ ∥ S 0 ∥ 2 2 / L 3 ≥ 64 / 27 \liminf_{L\to\infty}\lVert S_0\rVert_2^2/L^3 \ge64/27 lim inf L → ∞ ∥ S 0 ∥ 2 2 / L 3 ≥ 64/27 .
A cubic cost for rank-one projectors with independent settings
Keeping the mixed-word Gram block and its original pairings with the empty word imposes a cubic normalization cost for the rank-one projectors below. The bound allows arbitrary auxiliary blocks annihilated by mixed words.
Consider unit vectors u i = h i + α i e i u_i=h_i+\sqrt{\alpha_i}e_i u i = h i + α i e i , with orthonormal private directions e i e_i e i orthogonal to a common subspace containing all h i h_i h i , and α i = 1 − ∥ h i ∥ 2 > 0 \alpha_i=1-\lVert h_i\rVert^2>0 α i = 1 − ∥ h i ∥ 2 > 0 . For each N N N these subspaces are fixed before averaging. The h i h_i h i may be random, with inner products averaged over their joint law. The two parties project onto u i u_i u i and u i ‾ \overline{u_i} u i in conjugate local spaces, and the reference vector in this tensor-product block is R 0 = ∑ i α i − 1 e i ⊗ e i ‾ R_0=\sum_i\alpha_i^{-1}e_i\otimes\overline{e_i} R 0 = ∑ i α i − 1 e i ⊗ e i . We assume the reference vector is square integrable. The signs of the preceding construction are one choice of the h i h_i h i . Put
K N = E [ 1 N ∑ i ∣ h i ⟩ ⟨ h i ∣ ] . (26) K_N=\mathbb{E}\left[\frac{1}{N}\sum_i |h_i\rangle\langle h_i|\right]. \tag*{(26)} K N = E [ N 1 i ∑ ∣ h i ⟩ ⟨ h i ∣ ] . (26)
If the h i h_i h i are independent across settings and Tr K N ≤ τ \operatorname{Tr}K_N\le\tau Tr K N ≤ τ for a fixed 0 < τ ≤ 1 0<\tau\le1 0 < τ ≤ 1 , then every positive semidefinite completion of the indicated Gram block with its original empty-word pairings obeys
lim inf N → ∞ C L , N ≥ max 1 ≤ u ≤ L − 1 u ( 2 L − 2 u − 1 ) 2 τ 2 , (27) \liminf_{N\to\infty} C_{L,N}\ge\max_{1\le u\le L-1}\frac{u(2L-2u-1)^2}{\tau^2}, \tag*{(27)} N → ∞ lim inf C L , N ≥ 1 ≤ u ≤ L − 1 max τ 2 u ( 2 L − 2 u − 1 ) 2 , (27)
where C L , N C_{L,N} C L , N is the unnormalized empty-word diagonal and L ≥ 2 L\ge2 L ≥ 2 is fixed. The number of common directions and the distributions may vary with N N N . In particular, when τ = 1 / 2 \tau=1/2 τ = 1/2 , the bound on C L , N C_{L,N} C L , N grows asymptotically at least as ( 64 / 27 + o ( 1 ) ) L 3 (64/27+o(1))L^3 ( 64/27 + o ( 1 )) L 3 after taking N N N large at each fixed L L L .
To prove this bound, let P i = ∣ u i ⟩ ⟨ u i ∣ P_i=|u_i\rangle\langle u_i| P i = ∣ u i ⟩ ⟨ u i ∣ be Alice’s local projector. For 0 ≤ e ≤ L − 2 0\le e\le L-2 0 ≤ e ≤ L − 2 , consider the row of the mixed word A i 0 ⋯ A i e B i e A_{i_0}\cdots A_{i_e}B_{i_e} A i 0 ⋯ A i e B i e . On the reference vector it equals vec ( P i 0 ⋯ P i e ) \operatorname{vec}(P_{i_0}\cdots P_{i_e}) vec ( P i 0 ⋯ P i e ) , where vec ( ∣ v ⟩ ⟨ w ∣ ) = v ⊗ w ‾ \operatorname{vec}(|v\rangle\langle w|)=v\otimes\overline{w} vec ( ∣ v ⟩ ⟨ w ∣ ) = v ⊗ w . Indeed, the two projectors with label i e i_e i e select only its private reference term, and their two factors of α i e \sqrt{\alpha_{i_e}} α i e cancel its coefficient. Average these rows over all ordered, distinct labels i 0 , … , i e i_0,\ldots,i_e i 0 , … , i e , and call the vector Z e Z_e Z e . The original empty-word pairing of Z e Z_e Z e is one for e = 0 e=0 e = 0 and zero for e > 0 e>0 e > 0 . For e > 0 e>0 e > 0 the two endpoint directions selected by the word are attached to distinct private labels, which have zero pairing with the matched reference.
We bound the averaged row using the empirical projectors P ‾ = N − 1 ∑ i P i \overline{P}=N^{-1}\sum_iP_i P = N − 1 ∑ i P i and the empirical common block K ‾ = N − 1 ∑ i ∣ h i ⟩ ⟨ h i ∣ \overline{K}=N^{-1}\sum_i|h_i\rangle\langle h_i| K = N − 1 ∑ i ∣ h i ⟩ ⟨ h i ∣ . Throughout, matrix norms in the following estimates are Hilbert–Schmidt norms, with the expectation of their squares taken over the shared randomness. The average over tuples sampled with replacement is vec ( P ‾ e + 1 ) \operatorname{vec}(\overline{P}^{e+1}) vec ( P e + 1 ) . Every product of the rank-one projectors has Hilbert–Schmidt norm at most one. Hence conditioning on no repeated labels changes the average by at most twice the collision probability, which is at most e ( e + 1 ) / N e(e+1)/N e ( e + 1 ) / N . Furthermore, the orthogonal private directions give in each realization
∥ P ‾ − K ‾ ∥ H S 2 = 1 N 2 ∑ i [ α i 2 + 2 α i ( 1 − α i ) ] ≤ 1 N . (28) \lVert\overline{P}-\overline{K}\rVert_{\mathrm{HS}}^2
=\frac{1}{N^2}\sum_i[\alpha_i^2+2\alpha_i(1-\alpha_i)]\le\frac{1}{N}. \tag*{(28)} ∥ P − K ∥ HS 2 = N 2 1 i ∑ [ α i 2 + 2 α i ( 1 − α i )] ≤ N 1 . (28)
The matrices P ‾ \overline{P} P , K ‾ \overline{K} K and K N K_N K N are contractions. For powers of order e + 1 e+1 e + 1 , the difference of the powers telescopes, giving a Hilbert–Schmidt norm at most e + 1 e+1 e + 1 times the norm of the difference of the matrices. Thus, for N ≥ L − 1 N\ge L-1 N ≥ L − 1 ,
∥ Z e − vec ( K N e + 1 ) ∥ ≤ e ( e + 1 ) N + ( e + 1 ) ( N − 1 / 2 + Δ N ) , Δ N 2 = E ∥ K ‾ − K N ∥ H S 2 . (29) \lVert Z_e-\operatorname{vec}(K_N^{e+1})\rVert
\le\frac{e(e+1)}{N}+(e+1)(N^{-1/2}+\Delta_N),\qquad
\Delta_N^2=\mathbb{E}\lVert\overline{K}-K_N\rVert_{\mathrm{HS}}^2. \tag*{(29)} ∥ Z e − vec ( K N e + 1 )∥ ≤ N e ( e + 1 ) + ( e + 1 ) ( N − 1/2 + Δ N ) , Δ N 2 = E ∥ K − K N ∥ HS 2 . (29)
The norm on the left is the averaged Hilbert-space norm. Independence across settings gives Δ N 2 ≤ 1 / N \Delta_N^2 \le1/N Δ N 2 ≤ 1/ N , by adding the variances of the N N N common rank-one terms. The approximation also applies to correlated choices with Δ N → 0 \Delta_N \to0 Δ N → 0 .
It remains to combine the averaged rows. Fix 1 ≤ u ≤ L − 1 1 \le u \le L - 1 1 ≤ u ≤ L − 1 , put d = L − u − 1 d = L - u - 1 d = L − u − 1 and r = τ / u r = \tau/u r = τ / u , and write λ a \lambda_a λ a for the positive eigenvalues of K N K_N K N counted with multiplicity. There are at most u − 1 u - 1 u − 1 eigenvalues strictly above r r r . For x = sin 2 θ ∈ [ 0 , 1 ] x = \sin^2 \theta\in[0,1] x = sin 2 θ ∈ [ 0 , 1 ] , define the degree-d d d polynomial
q d ( x ) = sin ( ( 2 d + 1 ) θ ) ( 2 d + 1 ) sin θ . (30) q_d(x) = \frac{\sin((2d+1)\theta)}{(2d+1)\sin\theta}. \tag*{(30)} q d ( x ) = ( 2 d + 1 ) sin θ sin (( 2 d + 1 ) θ ) . (30)
It has q d ( 0 ) = 1 q_d(0) = 1 q d ( 0 ) = 1 and x ∣ q d ( x ) ∣ ≤ 1 / ( 2 d + 1 ) \sqrt{x}|q_d(x)| \le1/(2d+1) x ∣ q d ( x ) ∣ ≤ 1/ ( 2 d + 1 ) . The polynomial
F ( z ) = q d ( z / r ) ∏ λ a > r ( 1 − z / λ a ) = ∑ e = 0 L − 2 f e z e (31) F(z) = q_d(z/r) \prod_{\lambda_a>r} (1-z/\lambda_a) = \sum_{e=0}^{L-2} f_e z^e \tag*{(31)} F ( z ) = q d ( z / r ) λ a > r ∏ ( 1 − z / λ a ) = e = 0 ∑ L − 2 f e z e (31)
has F ( 0 ) = 1 F(0) = 1 F ( 0 ) = 1 . At every eigenvalue at most r r r the linear factors lie in [ 0 , 1 ] [0,1] [ 0 , 1 ] , while the other eigenvalues are zeros of F F F . Therefore
∥ K N F ( K N ) ∥ H S 2 = ∑ a λ a 2 ∣ F ( λ a ) ∣ 2 ≤ r Tr K N ( 2 d + 1 ) 2 ≤ τ 2 u ( 2 d + 1 ) 2 . (32) \lVert K_N F(K_N)\rVert_{\mathrm{HS}}^2 = \sum_a \lambda_a^2 |F(\lambda_a)|^2 \le\frac{r\operatorname{Tr}K_N}{(2d+1)^2} \le\frac{\tau^2}{u(2d+1)^2}. \tag*{(32)} ∥ K N F ( K N ) ∥ HS 2 = a ∑ λ a 2 ∣ F ( λ a ) ∣ 2 ≤ ( 2 d + 1 ) 2 r Tr K N ≤ u ( 2 d + 1 ) 2 τ 2 . (32)
The sum of the absolute coefficients of F F F is bounded by D = ( 1 + 1 / r ) u − 1 ∥ q d ( ⋅ / r ) ∥ c o e f , 1 D = (1+1/r)^{u-1}\lVert q_d(\mathord{\cdot}/r)\rVert_{\mathrm{coef},1} D = ( 1 + 1/ r ) u − 1 ∥ q d ( ⋅ / r ) ∥ coef , 1 , independently of N N N and the eigenvalues. By Eq. (29) , the norm of V = ∑ e f e Z e V = \sum_e f_e Z_e V = ∑ e f e Z e therefore satisfies
∥ V ∥ ≤ τ u ( 2 d + 1 ) + D [ ( L − 1 ) ( L − 2 ) N + ( L − 1 ) ( N − 1 / 2 + Δ N ) ] . (33) \lVert V\rVert\le\frac{\tau}{\sqrt{u}(2d+1)} + D\left[\frac{(L-1)(L-2)}{N} + (L-1)(N^{-1/2}+\Delta_N)\right]. \tag*{(33)} ∥ V ∥ ≤ u ( 2 d + 1 ) τ + D [ N ( L − 1 ) ( L − 2 ) + ( L − 1 ) ( N − 1/2 + Δ N ) ] . (33)
The original empty-word pairing of V V V is its constant coefficient f 0 = 1 f_0 = 1 f 0 = 1 . The principal 2 × 2 2 \times2 2 × 2 matrix on the empty word and this linear combination must be positive semidefinite. It gives 1 ≤ C L , N ∥ V ∥ 2 1 \le C_{L,N}\lVert V\rVert^2 1 ≤ C L , N ∥ V ∥ 2 . Taking N → ∞ N \to\infty N → ∞ at fixed L L L gives Eq. (27) . To get the cubic coefficient, take an admissible integer u u u nearest to ( 2 L − 1 ) / 6 (2L-1)/6 ( 2 L − 1 ) /6 .
Alice holds a database R = ( R 1 , … , R n R ) R = (R_1,\ldots,R_{n_R}) R = ( R 1 , … , R n R ) of n R n_R n R independent bits. Bob alone receives an index j ∈ { 1 , … , n R } j \in\{1,\ldots,n_R\} j ∈ { 1 , … , n R } , chosen independently of the database. Alice sends her message without knowing this index. Write G j G_j G j for Bob’s output when he is asked for entry j j j . The information-causality (IC) score I I C = ∑ j I ( R j : G j ) I_{\mathrm{IC}} = \sum_j I(R_j:G_j) I IC = ∑ j I ( R j : G j ) , in bits, sums the Shannon mutual information I ( R j : G j ) I(R_j:G_j) I ( R j : G j ) for each possible request.
Let F L ( N ) F_L(N) F L ( N ) be the supremum of this score for level-L L L correlations with N N N settings per party and two outcomes, over finite databases whose independent bits may have arbitrary biases. The database and the request are independent of the supplied correlation. Alice and Bob may use shared randomness independent of these inputs and of the correlation, as well as private randomness. They have at most one use of the correlation and at most one bit of communication from Alice to Bob. The message has two possible values, including on runs where the correlation is unused. Bob can choose his setting after receiving the message and keep his full transcript.
Consider a nonsignalling theory with a finite, symmetric and nonnegative mutual information on the relevant systems and their composites. It agrees with Shannon mutual information when both systems are classical, and local transformations cannot increase it. The chain rule requires that I ( A : B C ) − I ( A : C ) = I ( B : A C ) − I ( B : C ) I(A:BC)-I(A:C)=I(B:AC)-I(B:C) I ( A : B C ) − I ( A : C ) = I ( B : A C ) − I ( B : C ) , with the common difference denoted by I ( A : B ∣ C ) I(A:B\mid C) I ( A : B ∣ C ) for systems A A A , B B B , C C C [2 , 42 , 43 ] . Juxtaposition denotes the composite of the indicated systems. Classical registers can be copied and discarded.
Let B B B contain Bob’s resources before he receives the classical message M M M . Bob may defer earlier operations to his decoder, with their choices made independently of M M M . After Alice forms M M M , the state of B B B averaged over the message is independent of R R R by nonsignalling. Consequently I ( R : B ) = 0 I(R:B)=0 I ( R : B ) = 0 . The two independent systems can be prepared locally from constant classical registers, whose mutual information is zero, and this preparation cannot increase mutual information.
The information added by the message is I ( R : M ∣ B ) I(R:M\mid B) I ( R : M ∣ B ) . By the symmetric chain rule this is I ( R B : M ) − I ( B : M ) I(RB:M)-I(B:M) I ( R B : M ) − I ( B : M ) . Take M ′ M' M ′ to be an exact classical copy of M M M . Adding it to R B RB R B can only increase the mutual information with M M M . The chain rule gives
I ( R : B M ) = I ( R : M ∣ B ) ≤ I ( R B : M ) ≤ I ( R B M ′ : M ) , I ( R B M ′ : M ) = I ( M ′ : M ) + I ( R B : M ∣ M ′ ) = H ( M ) . (34) \begin{aligned}
I(R:BM)&=I(R:M\mid B)\le I(RB:M)\le I(RBM':M),\\
I(RBM':M)&=I(M':M)+I(RB:M\mid M')=H(M). \tag*{(34)}
\end{aligned} I ( R : B M ) I ( R B M ′ : M ) = I ( R : M ∣ B ) ≤ I ( R B : M ) ≤ I ( R B M ′ : M ) , = I ( M ′ : M ) + I ( R B : M ∣ M ′ ) = H ( M ) . (34)
Data processing for copying M ′ M' M ′ and for discarding the copy gives I ( R B : M ′ M ) = I ( R B : M ′ ) I(RB:M'M)=I(RB:M') I ( R B : M ′ M ) = I ( R B : M ′ ) in both directions, so the conditional term vanishes. Classical consistency gives I ( M ′ : M ) = H ( M ) I(M':M)=H(M) I ( M ′ : M ) = H ( M ) .
For each request j j j , Bob obtains G j G_j G j by processing his resources W = B M W=BM W = B M . All requests thus admit the same bound I ( R j : G j ) ≤ I ( R j : W ) I(R_j:G_j)\le I(R_j:W) I ( R j : G j ) ≤ I ( R j : W ) . To sum these bounds, put R < j = ( R 1 , … , R j − 1 ) R_{<j}=(R_1,\ldots,R_{j-1}) R < j = ( R 1 , … , R j − 1 ) . Independence gives I ( R j : R < j ) = 0 I(R_j:R_{<j})=0 I ( R j : R < j ) = 0 , so
I ( R : W ) = ∑ j I ( R j : W ∣ R < j ) = ∑ j I ( R j : W R < j ) . I(R:W)=\sum_j I(R_j:W\mid R_{<j})=\sum_j I(R_j:WR_{<j}). I ( R : W ) = j ∑ I ( R j : W ∣ R < j ) = j ∑ I ( R j : W R < j ) .
Discarding R < j R_{<j} R < j bounds each I ( R j : W ) I(R_j:W) I ( R j : W ) by the corresponding term on the right. Hence ∑ j I ( R j : G j ) ≤ I ( R : W ) ≤ H ( M ) \sum_j I(R_j:G_j)\le I(R:W)\le H(M) ∑ j I ( R j : G j ) ≤ I ( R : W ) ≤ H ( M ) , and a two-valued message has H ( M ) ≤ 1 H(M)\le1 H ( M ) ≤ 1 . Classical and quantum mutual information obey the required rules in their respective theories, so the upper bound applies to both.
Lower bound from equality certification {#sec: S2.2}
The equality certificate can tell Bob that his requested bit has the rare value one. Let Alice’s N N N independent bits each be one with probability r ∈ ( 0 , 1 ) r\in(0,1) r ∈ ( 0 , 1 ) . When the database contains a one, Alice uses the correlation of Eq. (21) with setting x x x equal to the index of the first one. She sends her outcome a a a . If the database contains only zeros, she sends one. Bob uses his requested index i i i as the setting. He raises the flag G i = 1 G_i=1 G i = 1 when the message and his outcome are both zero, and sets G i = 0 G_i=0 G i = 0 on every other run. A flag requires x = i x=i x = i , so it certifies R i = 1 R_i=1 R i = 1 . Its probability is t i = s L r ( 1 − r ) i − 1 t_i=s_Lr(1-r)^{i-1} t i = s L r ( 1 − r ) i − 1 , since the entries before i i i must be zero and entry i i i must be one.
To count the information in a flag, average the relative entropy D ( P R i ∣ G i = g ∥ P R i ) D(P_{R_i\mid G_i=g}\mathbin\Vert P_{R_i}) D ( P R i ∣ G i = g ∥ P R i ) of each posterior from the prior over Bob’s outputs g ∈ { 0 , 1 } g\in\{0,1\} g ∈ { 0 , 1 } . This gives I ( R i : G i ) = ∑ g Pr ( G i = g ) D ( P R i ∣ G i = g ∥ P R i ) I(R_i:G_i)=\sum_g\Pr(G_i=g)D(P_{R_i\mid G_i=g}\mathbin\Vert P_{R_i}) I ( R i : G i ) = ∑ g Pr ( G i = g ) D ( P R i ∣ G i = g ∥ P R i ) . The flagged posterior is concentrated on one, an event of prior probability r r r , and hence has relative entropy log 2 ( 1 / r ) \log_2(1/r) log 2 ( 1/ r ) bits. Its contribution gives a lower bound because the unflagged posterior also has nonnegative relative entropy,
I ( R i : G i ) ≥ t i log 2 ( 1 / r ) . (35) I(R_i:G_i)\ge t_i\log_2(1/r). \tag*{(35)} I ( R i : G i ) ≥ t i log 2 ( 1/ r ) . (35)
The events that select the first one are disjoint. The sum of their certificate probabilities is s L s_L s L times the probability of any one in the database, so the total score satisfies
I I C ≥ s L [ 1 − ( 1 − r ) N ] log 2 ( 1 / r ) . (36) I_{\mathrm{IC}}\ge s_L\left[1-(1-r)^N\right]\log_2(1/r). \tag*{(36)} I IC ≥ s L [ 1 − ( 1 − r ) N ] log 2 ( 1/ r ) . (36)
Decreasing r r r increases the information per flag. Increasing N N N lets the chance of finding a one remain appreciable at the smaller value of r r r .
For N ≥ 2 N\ge2 N ≥ 2 , choose r = 1 / N r=1/N r = 1/ N . On average there is one entry equal to one. The probability of at least one such entry is at least 1 − e − 1 1-e^{-1} 1 − e − 1 , so
F L ( N ) ≥ ( 1 − e − 1 ) s L log 2 N . (37) F_L(N)\ge(1-e^{-1})s_L\log_2N. \tag*{(37)} F L ( N ) ≥ ( 1 − e − 1 ) s L log 2 N . (37)
Taking r = ( ln N ) / N r = (\ln N)/N r = ( ln N ) / N , where ln \ln ln denotes the natural logarithm, makes the probability of finding a one at least 1 − N − 1 1 - N^{-1} 1 − N − 1 . Each flag contributes log 2 N − log 2 ln N \log_{2} N - \log_{2} \ln N log 2 N − log 2 ln N bits when it occurs. Equation (36) gives
F L ( N ) ≥ s L ( 1 − N − 1 ) ( log 2 N − log 2 ln N ) = s L log 2 N − O L ( log log N ) . (38) F_{L}(N) \ge s_{L}(1-N^{-1})(\log_{2}N-\log_{2}\ln N)=s_{L}\log_{2}N-O_{L}(\log\log N). \tag*{(38)} F L ( N ) ≥ s L ( 1 − N − 1 ) ( log 2 N − log 2 ln N ) = s L log 2 N − O L ( log log N ) . (38)
At each fixed L L L the score thus grows without bound as N N N increases. The constants in O L O_{L} O L can depend on L L L . With tensor-product quantum correlations, the bound of one bit follows from Eq. (34) and is attained by sending a fair database bit [2 ] .
Fair independent bits. With fair bits the rare event can be an entire block of ones, as in the protocol of Das Bhowmik and Banik [9 ] . Divide the database into N N N blocks of k k k independent fair bits. The all-ones string occurs in a block with probability r = 2 − k r=2^{-k} r = 2 − k . Alice uses the index of the first all-ones block and sends her outcome, or sends one if there is no such block. Bob uses the index of the block containing his requested bit. He returns one precisely when his outcome and the message are both zero. This flag certifies that every bit of the requested block is one. The flag for block i i i occurs with probability t i = s L r ( 1 − r ) i − 1 t_i=s_{L}r(1-r)^{i-1} t i = s L r ( 1 − r ) i − 1 . For each of its k k k possible requests the flag contributes t i t_i t i bits of mutual information in the score, for a total of t i log 2 ( 1 / r ) = k t i t_i\log_{2}(1/r)=kt_i t i log 2 ( 1/ r ) = k t i bits from that block. Summing gives
I I C ≥ k s L [ 1 − ( 1 − 2 − k ) N ] . (39) I_{\mathrm{IC}} \ge ks_{L}\left[1-(1-2^{-k})^{N}\right]. \tag*{(39)} I IC ≥ k s L [ 1 − ( 1 − 2 − k ) N ] . (39)
Taking k = ⌊ log 2 N ⌋ k=\lfloor\log_{2}N\rfloor k = ⌊ log 2 N ⌋ keeps the expected number of all-ones blocks at least one and bounds the score from below by ( 1 − e − 1 ) s L ⌊ log 2 N ⌋ (1-e^{-1})s_{L}\lfloor\log_{2}N\rfloor ( 1 − e − 1 ) s L ⌊ log 2 N ⌋ . For x = log 2 N x=\log_{2}N x = log 2 N sufficiently large, k = ⌊ x − log 2 x ⌋ k=\lfloor x-\log_{2}x\rfloor k = ⌊ x − log 2 x ⌋ gives the lower bound s L ( x − log 2 x − 1 ) ( 1 − e − 1 ) s_{L}(x-\log_{2}x-1)(1-e^{-1}) s L ( x − log 2 x − 1 ) ( 1 − e − 1 ) , with the same leading term as Eq. (38) . When no block is all ones, Alice can omit the query or ignore its outcome.
Nonsignalling upper bound
To bound the growth of the score, ask how much classical communication would reproduce a protocol using one nonsignalling correlation p ( a , b ∣ x , y ) p(a,b\mid x,y) p ( a , b ∣ x , y ) . There are N N N Alice settings x x x , and Alice’s message lies in the finite alphabet M \mathcal{M} M . Sending the setting along with the original message lets Bob pick out one row of a table sampled in advance. Before either party gets an input, sample the shared seed and private controls. For each setting x x x , use additional shared randomness to draw an outcome a x a_{x} a x from p A ( ⋅ ∣ x ) p_{A}(\cdot\mid x) p A ( ⋅ ∣ x ) . Nonsignalling makes this distribution independent of Bob’s setting. For each drawn a x a_{x} a x , sample a response row g x g_{x} g x with an independent entry for each Bob setting y y y . Each entry has Bob’s conditional outcome law given the sampled Alice outcome,
Pr [ g x ( y ) = b ∣ a x ] = p ( a x , b ∣ x , y ) / p A ( a x ∣ x ) . \Pr[g_{x}(y)=b\mid a_{x}]=p(a_{x},b\mid x,y)/p_{A}(a_{x}\mid x). Pr [ g x ( y ) = b ∣ a x ] = p ( a x , b ∣ x , y ) / p A ( a x ∣ x ) .
The denominator is positive on every sampled outcome. If the shared seed selects from a family of nonsignalling correlations, the table is sampled from the selected correlation.
Alice chooses X X X from her database and the controls, computes her original message M M M using a X a_{X} a X , and sends ( X , M ) (X,M) ( X , M ) in the simulation. Bob uses his original rule to choose y y y from his request and, when available at that step of the original protocol, M M M . He then uses g X ( y ) g_{X}(y) g X ( y ) as his outcome. Conditional on X , a X , M X,a_{X},M X , a X , M and the controls, the setting choice uses no entry of the row. Its selected entry therefore has the required conditional distribution, so the simulation reproduces the joint law of the database and Bob’s entire transcript for each request. If Alice skips her query, she may send a dummy setting and ignore a X a_{X} a X . If Bob skips it, he omits the lookup.
Let Λ \Lambda Λ contain the random controls and the table, which are independent of the database and request. For each request Bob’s output is a function of ( X , M , Λ ) (X,M,\Lambda) ( X , M , Λ ) . Data processing, independence of the database bits, and the alphabet size of the simulated message give
∑ j I ( R j : G j ) ≤ ∑ j I ( R j : X , M , Λ ) ≤ I ( R : X , M ∣ Λ ) ≤ log 2 N + log 2 ∣ M ∣ . (40) \sum_{j} I(R_{j}:G_{j})\le\sum_{j}I(R_{j}:X,M,\Lambda)\le I(R:X,M\mid\Lambda)\le\log_{2}N+\log_{2}|\mathcal{M}|. \tag*{(40)} j ∑ I ( R j : G j ) ≤ j ∑ I ( R j : X , M , Λ ) ≤ I ( R : X , M ∣ Λ ) ≤ log 2 N + log 2 ∣ M ∣. (40)
The entries are independent conditional on Λ \Lambda Λ , giving H ( R ∣ Λ ) = ∑ j H ( R j ) H(R\mid\Lambda)=\sum_{j}H(R_{j}) H ( R ∣ Λ ) = ∑ j H ( R j ) . Conditional entropy is subadditive, H ( R ∣ X , M , Λ ) ≤ ∑ j H ( R j ∣ X , M , Λ ) H(R\mid X,M,\Lambda)\le\sum_{j}H(R_{j}\mid X,M,\Lambda) H ( R ∣ X , M , Λ ) ≤ ∑ j H ( R j ∣ X , M , Λ ) , which gives the middle inequality. The final bound counts the possible pairs ( X , M ) (X, M) ( X , M ) . For a two-symbol message, Eqs. (37) and (40) give F L ( N ) = Θ L ( log N ) F_L(N) = \Theta_L(\log N) F L ( N ) = Θ L ( log N ) , with multiplicative constants independent of N N N at fixed L L L .
The bound is attained under nonsignalling at N = 2 k N = 2^k N = 2 k for k ≥ 1 k \ge1 k ≥ 1 . Alice has k + 1 k + 1 k + 1 independent fair bits R 0 , … , R k R_0, \ldots, R_k R 0 , … , R k . Her setting encodes each bit’s parity with a reference bit R 0 R_0 R 0 . With ⊕ \oplus ⊕ denoting addition modulo two, she inputs x = ( R 1 ⊕ R 0 , … , R k ⊕ R 0 ) x = (R_1 \oplus R_0, \ldots, R_k \oplus R_0) x = ( R 1 ⊕ R 0 , … , R k ⊕ R 0 ) and sets x 0 = 0 x_0 = 0 x 0 = 0 . For Bob’s setting y ∈ { 0 , … , k } y \in\{0, \ldots, k\} y ∈ { 0 , … , k } , the correlation supplies a uniform a a a and b = a ⊕ x y b = a \oplus x_y b = a ⊕ x y , so both marginals are uniform. There are enough settings because k + 1 ≤ 2 k k + 1 \le2^k k + 1 ≤ 2 k , and unused Bob settings duplicate setting zero. Alice sends M = a ⊕ R 0 M = a \oplus R_0 M = a ⊕ R 0 and Bob recovers M ⊕ b = R y M \oplus b = R_y M ⊕ b = R y on every request. The score is k + 1 k + 1 k + 1 .
Optimal one-copy information growth for equality correlations
Let P = P_= P = and P ≠ P_{\ne} P = be laws on finite outcome alphabets A × B \mathcal{A} \times\mathcal{B} A × B with the same Alice marginals and the same Bob marginals. Alice and Bob each have N ≥ 2 N \ge2 N ≥ 2 settings. Their joint outcomes follow P = P_= P = for equal settings and P ≠ P_{\ne} P = for unequal settings. The database R = ( R i ) i R = (R_i)_i R = ( R i ) i consists of a finite number of independent bits with arbitrary biases. Bob’s request is independent of the database and the random controls, and Alice does not know it. The parties may use the correlation once and send one message from Alice to Bob in an alphabet M \mathcal{M} M . The message alphabet includes any distinguishable silence and accounts for all communication. Shared and private random controls are independent of R R R , the request and the correlation. Bob may choose his setting after receiving the message and take his full local transcript as G i G_i G i . Write J N J_N J N for the supremum of ∑ i I ( R i : G i ) \sum_i I(R_i:G_i) ∑ i I ( R i : G i ) over these protocols.
An outcome pair outside the support of P ≠ P_{\ne} P = certifies that the settings agree. Its total probability on equal settings is
ρ = ∑ a , b : P ≠ ( a , b ) = 0 P = ( a , b ) . (41) \rho= \sum_{a,b:\,P_{\ne}(a,b)=0} P_=(a,b). \tag*{(41)} ρ = a , b : P = ( a , b ) = 0 ∑ P = ( a , b ) . (41)
For each Alice outcome a a a of positive common marginal probability α a \alpha_a α a , let V a = P ≠ ( B = ⋅ ∣ A = a ) V_a = P_{\ne}(B = \mathord{\cdot}\mid A = a) V a = P = ( B = ⋅ ∣ A = a ) and W a = P = ( B = ⋅ ∣ A = a ) W_a = P_=(B = \mathord{\cdot}\mid A = a) W a = P = ( B = ⋅ ∣ A = a ) be Bob’s conditional outcome laws. Write η a = W a ( B ∖ supp V a ) \eta_a = W_a(B \setminus\operatorname{supp} V_a) η a = W a ( B ∖ supp V a ) for the probability of certification conditional on a a a . If η a < 1 \eta_a < 1 η a < 1 , let U a U_a U a be W a W_a W a conditioned on supp V a \operatorname{supp} V_a supp V a . The information from these supported outcomes is bounded by the relative entropy D ( U a ∥ V a ) D(U_a\Vert V_a) D ( U a ∥ V a ) , in bits. The resulting upper bound is
J N ≤ ρ log 2 N + log 2 ∣ M ∣ + ∑ a : α a > 0 , η a < 1 α a ( 1 − η a ) D ( U a ∥ V a ) . (42) J_N \le\rho\log_2 N + \log_2 |\mathcal{M}| + \sum_{\substack{a:\,\alpha_a>0,\,\eta_a<1}} \alpha_a(1-\eta_a)D(U_a\Vert V_a). \tag*{(42)} J N ≤ ρ log 2 N + log 2 ∣ M ∣ + a : α a > 0 , η a < 1 ∑ α a ( 1 − η a ) D ( U a ∥ V a ) . (42)
If ∣ M ∣ ≥ ∣ A ∣ |\mathcal{M}| \ge|\mathcal{A}| ∣ M ∣ ≥ ∣ A ∣ , Alice can send her outcome and achieve
J N ≥ ρ N log 2 ( N ! ) ≥ ρ log 2 N − ρ log 2 e . (43) J_N \ge\frac{\rho}{N}\log_2(N!) \ge\rho\log_2 N - \rho\log_2 e. \tag*{(43)} J N ≥ N ρ log 2 ( N !) ≥ ρ log 2 N − ρ log 2 e . (43)
Thus J N = ρ log 2 N + O ( 1 ) J_N = \rho\log_2 N + O(1) J N = ρ log 2 N + O ( 1 ) when the outcome laws and message alphabet are fixed, and the alphabet can carry Alice’s outcome.
Upper bound. To bound the sum over alternative requests, we reproduce each request’s transcript from a single collection of classical variables. Sample the original random controls Λ \Lambda Λ independently of the database and request. Conditioned on their values, Alice chooses her setting X X X from R R R . She generates her message M M M from R R R and her outcome A A A . A skipped query can be represented by a fixed dummy setting whose outcome Alice ignores. The marginal of A A A is ( α a ) a (\alpha_a)_a ( α a ) a at every setting, so we can draw A A A independently of ( R , Λ ) (R,\Lambda) ( R , Λ ) and then compute M M M by Alice’s rule.
Given A = a A = a A = a and X = x X = x X = x , draw a table T = ( T 1 , … , T N ) T = (T_1,\ldots,T_N) T = ( T 1 , … , T N ) of independent entries. Draw T x T_x T x from W a W_a W a and every other entry from V a V_a V a . At request i i i , Bob’s original setting rule selects an entry using his random controls and i i i , and also M M M if he queries after receiving it. Each choice precedes reading the entry. If Bob queries, the selected entry has the required law conditional on A A A and the settings. If he skips the query, his transcript needs no entry. Thus each request has the original joint law of R R R and G i G_i G i . In this coupling G i G_i G i is a function of ( Λ , A , M , T ) (\Lambda,A,M,T) ( Λ , A , M , T ) for fixed i i i , even when it contains Bob’s entire transcript. Data processing and independence of the R i R_i R i bound the score by the information that this collection of variables carries about R R R . Since ( Λ , A ) (\Lambda,A) ( Λ , A ) is independent of R R R , the chain rule gives
∑ i I ( R i : G i ) ≤ I ( R : Λ , A , M , T ) ≤ log 2 ∣ M ∣ + I ( R : T ∣ Λ , A , M ) . (44) \sum_i I(R_i:G_i) \le I(R:\Lambda,A,M,T) \le\log_2|\mathcal{M}| + I(R:T\mid\Lambda,A,M). \tag*{(44)} i ∑ I ( R i : G i ) ≤ I ( R : Λ , A , M , T ) ≤ log 2 ∣ M ∣ + I ( R : T ∣ Λ , A , M ) . (44)
Indeed, for any common variable Z Z Z , ∑ i I ( R i : Z ) ≤ I ( R : Z ) \sum_i I(R_i:Z)\le I(R:Z) ∑ i I ( R i : Z ) ≤ I ( R : Z ) by H ( R ) = ∑ i H ( R i ) H(R)=\sum_i H(R_i) H ( R ) = ∑ i H ( R i ) and H ( R ∣ Z ) ≤ ∑ i H ( R i ∣ Z ) H(R\mid Z)\le\sum_i H(R_i\mid Z) H ( R ∣ Z ) ≤ ∑ i H ( R i ∣ Z ) . The message term in Eq. (44) is bounded by H ( M ∣ Λ , A ) ≤ log 2 ∣ M ∣ H(M\mid\Lambda,A)\le\log_2|\mathcal{M}| H ( M ∣ Λ , A ) ≤ log 2 ∣ M ∣ .
Let E E E indicate whether T X T_X T X lies outside supp V A \operatorname{supp} V_A supp V A , and put C = ( Λ , A , M ) C=(\Lambda,A,M) C = ( Λ , A , M ) . Given C C C with A = a A=a A = a , the probability of E = 1 E=1 E = 1 is η a \eta_a η a for every database, so I ( R : E ∣ C ) = 0 I(R:E\mid C)=0 I ( R : E ∣ C ) = 0 . We may bound I ( R : T ∣ C ) I(R:T\mid C) I ( R : T ∣ C ) by I ( R : T , E ∣ C ) = I ( R : T ∣ C , E ) I(R:T,E\mid C)=I(R:T\mid C,E) I ( R : T , E ∣ C ) = I ( R : T ∣ C , E ) . On E = 1 E=1 E = 1 , the conditional table law depends on R R R only through X X X , so the conditional information is at most log 2 N \log_2 N log 2 N .
On E = 0 E=0 E = 0 , the table differs from the reference law V a ⊗ N V_a^{\otimes N} V a ⊗ N in one entry. At each fixed R R R and C C C , its relative entropy from this reference is D ( U a ∥ V a ) D(U_a\|V_a) D ( U a ∥ V a ) . To bound the information in the table, fix a value z z z of C C C with A = a A=a A = a and average this relative entropy over R R R conditional on C = z , E = 0 C=z,E=0 C = z , E = 0 . The relative-entropy chain rule gives
E [ D ( P T ∣ R , C = z , E = 0 ∥ V a ⊗ N ) | C = z , E = 0 ] = I ( R : T ∣ C = z , E = 0 ) + D ( P T ∣ C = z , E = 0 ∥ V a ⊗ N ) . \mathbb{E}\left[D\left(P_{T\mid R,C=z,E=0}\middle\|V_a^{\otimes N}\right)\middle|C=z,E=0\right]
=I(R:T\mid C=z,E=0)+D\left(P_{T\mid C=z,E=0}\middle\|V_a^{\otimes N}\right). E [ D ( P T ∣ R , C = z , E = 0 V a ⊗ N ) C = z , E = 0 ] = I ( R : T ∣ C = z , E = 0 ) + D ( P T ∣ C = z , E = 0 V a ⊗ N ) .
The last term is nonnegative, so D ( U a ∥ V a ) D(U_a\|V_a) D ( U a ∥ V a ) bounds the conditional information for every posterior distribution of X X X after the message. Averaging over C C C and E E E , and using ∑ a α a η a = ρ \sum_a\alpha_a\eta_a=\rho ∑ a α a η a = ρ , gives Eq. (42) .
Achievability. Use N − 1 N-1 N − 1 independent bits with r i = Pr ( R i = 1 ) = 1 / ( N − i + 1 ) r_i=\Pr(R_i=1)=1/(N-i+1) r i = Pr ( R i = 1 ) = 1/ ( N − i + 1 ) for $1\le i\le N-1$. Alice chooses X X X as the first index with R i = 1 R_i=1 R i = 1 , with setting N N N assigned to the all-zero database. For i ≤ N − 1 i\le N-1 i ≤ N − 1 , the first i − 1 i-1 i − 1 bits are zero with probability ( N − i + 1 ) / N (N-i+1)/N ( N − i + 1 ) / N , and the all-zero probability is 1 / N 1/N 1/ N . Thus X X X is uniform on [ N ] [N] [ N ] . Alice sends A A A . For request i i i , Bob queries setting i i i and flags an outcome pair outside supp P ≠ \operatorname{supp}P_{\ne} supp P = . The flag occurs with probability ρ / N \rho/N ρ / N and certifies X = i X=i X = i and R i = 1 R_i=1 R i = 1 . For ρ > 0 \rho>0 ρ > 0 , its contribution to I ( R i : G i ) I(R_i:G_i) I ( R i : G i ) is ( ρ / N ) log 2 ( 1 / r i ) (\rho/N)\log_2(1/r_i) ( ρ / N ) log 2 ( 1/ r i ) . The other output contributes a nonnegative term. Summing over the N − 1 N-1 N − 1 requests and using ln ( N ! ) ≥ ∫ 1 N ln t d t \ln(N!)\ge\int_1^N\ln t\,dt ln ( N !) ≥ ∫ 1 N ln t d t gives Eq. (43) , which also holds at $\rho=0.
Application to the binary equality correlations. Suppose p ( 0 , 0 ∣ x , y ) = s 1 x = y p(0,0\mid x,y)=s\mathbf{1}_{x=y} p ( 0 , 0 ∣ x , y ) = s 1 x = y and the two zero-outcome marginals are m s ms m s , where s > 0 s>0 s > 0 , m ≥ 1 m\ge1 m ≥ 1 and 2 m s ≤ 1 2ms\le1 2 m s ≤ 1 . When 2 m s < 1 2ms<1 2 m s < 1 , the outcome ( 0 , 0 ) (0,0) ( 0 , 0 ) is the only certifying pair of positive probability, so ρ = s \rho=s ρ = s . Conditional on A = 0 A=0 A = 0 , the unequal-setting law of B B B is a point mass at one, and the supported part of the equal-setting law is the same point mass whenever it has positive weight. For A = 1 A=1 A = 1 , the equal- and unequal-setting probabilities of B = 0 B=0 B = 0 are ( m − 1 ) s / ( 1 − m s ) (m-1)s/(1-ms) ( m − 1 ) s / ( 1 − m s ) and m s / ( 1 − m s ) ms/(1-ms) m s / ( 1 − m s ) . Substituting into Eqs. (42) and (43) for a one-bit message gives
s N log 2 ( N ! ) ≤ J N ≤ s log 2 N + 1 + ( 1 − m s ) D B e r ( ( m − 1 ) s 1 − m s ∥ m s 1 − m s ) , (45) \frac{s}{N}\log_2(N!)\le J_N\le s\log_2N+1+(1-ms)D_{\mathrm{Ber}}\left(\frac{(m-1)s}{1-ms}\middle\|\frac{ms}{1-ms}\right), \tag*{(45)} N s log 2 ( N !) ≤ J N ≤ s log 2 N + 1 + ( 1 − m s ) D Ber ( 1 − m s ( m − 1 ) s 1 − m s m s ) , (45)
where D B e r ( p ∥ q ) D_{\mathrm{Ber}}(p\|q) D Ber ( p ∥ q ) is the relative entropy in bits of the Bernoulli laws of parameters p p p and q q q . For Eq. (21) , m = 3 m=3 m = 3 and the normalization satisfies C L ≥ ∣ S 0 ∣ 2 ≥ 4 ( 2 L − 1 ) 2 C_L\ge|S_0|^2\ge4(2L-1)^2 C L ≥ ∣ S 0 ∣ 2 ≥ 4 ( 2 L − 1 ) 2 , so s L ≤ 1 / 36 s_L\le1/36 s L ≤ 1/36 . The inequality ln t ≤ t − 1 \ln t\le t-1 ln t ≤ t − 1 gives D B e r ( p ∥ q ) ≤ ( p − q ) 2 / [ q ( 1 − q ) ln 2 ] D_{\mathrm{Ber}}(p\|q)\le(p-q)^2/[q(1-q)\ln2] D Ber ( p ∥ q ) ≤ ( p − q ) 2 / [ q ( 1 − q ) ln 2 ] for 0 < q < 1 0<q<1 0 < q < 1 . The last term in Eq. (45) is therefore at most s L ( 1 − 3 s L ) / [ 3 ( 1 − 6 s L ) ln 2 ] ≤ s L log 2 e s_L(1-3s_L)/[3(1-6s_L)\ln2]\le s_L\log_2e s L ( 1 − 3 s L ) / [ 3 ( 1 − 6 s L ) ln 2 ] ≤ s L log 2 e .
At 2 m s = 1 2ms=1 2 m s = 1 , the pair ( 1 , 1 ) (1,1) ( 1 , 1 ) also certifies equality, with probability s s s . Conditional on either value of A A A , Bob's unequal-setting law is a point mass, so the relative-entropy term vanishes. With ρ = 2 s \rho=2s ρ = 2 s , the one-bit score satisfies
2 s N log 2 ( N ! ) ≤ J N ≤ 2 s log 2 N + 1. (46) \frac{2s}{N}\log_2(N!)\le J_N\le2s\log_2N+1. \tag*{(46)} N 2 s log 2 ( N !) ≤ J N ≤ 2 s log 2 N + 1. (46)
Let p s ( 0 , 0 ∣ x , y ) = s 1 x = y p_s(0,0\mid x,y)=s\mathbf{1}_{x=y} p s ( 0 , 0 ∣ x , y ) = s 1 x = y , with zero-outcome marginals 3 s 3s 3 s on both sides and 0 < s < 1 / 6 0<s<1/6 0 < s < 1/6 . Mix p s p_s p s with a setting-independent product correlation U N U_N U N whose zero-outcome marginal on each side is 0 < u N ≤ 1 / 2 0<u_N\le1/2 0 < u N ≤ 1/2 .
For a fixed mixture weight 0 < ϵ < 1 0 < \epsilon< 1 0 < ϵ < 1 , the parties use q N = ( 1 − ϵ ) p s + ϵ U N q_N = (1-\epsilon)p_s + \epsilon U_N q N = ( 1 − ϵ ) p s + ϵ U N with the mixture label hidden. Write c = ( 1 − ϵ ) s c = (1-\epsilon)s c = ( 1 − ϵ ) s for the diagonal excess and t N = ϵ u N 2 t_N = \epsilon u_N^2 t N = ϵ u N 2 for the unequal-setting joint-zero probability. The equal-setting joint-zero probability is c + t N c + t_N c + t N . Over the one-copy, one-bit protocols defined above, the optimal score for N ≥ 2 N \ge2 N ≥ 2 is
J N ( q N ) = c log 2 ( N 1 + N t N / c ) + O s , ϵ ( 1 ) , (47) J_N(q_N) = c\log_2\left(\frac{N}{1+Nt_N/c}\right) + O_{s,\epsilon}(1), \tag*{(47)} J N ( q N ) = c log 2 ( 1 + N t N / c N ) + O s , ϵ ( 1 ) , (47)
with an additive bound uniform in N N N and u N u_N u N .
Upper bound. The mixture label is independent of the database. Append it to Bob’s output in each request. The score of these enlarged outputs is the weighted sum of the two scores conditional on the label and upper bounds the original score by data processing. The product branch has one-bit score at most one. The certificate branch obeys Eq. (45) , so J N ( q N ) ≤ c log 2 N + O s ( 1 ) J_N(q_N) \le c\log_2 N + O_s(1) J N ( q N ) ≤ c log 2 N + O s ( 1 ) .
A second bound follows from the equal- and unequal-setting outcome laws P = P_= P = and P ≠ P_{\ne} P = of q N q_N q N . Both laws have full support, so ρ = 0 \rho= 0 ρ = 0 in Eq. (42) . Their Alice marginal is common. The relative-entropy chain rule thus gives J N ( q N ) ≤ 1 + D ( P = ∥ P ≠ ) J_N(q_N) \le1 + D(P_=\mathbin\Vert P_{\ne}) J N ( q N ) ≤ 1 + D ( P = ∥ P = ) . In this divergence the 01 and 10 terms are nonpositive since each equal-setting probability is lower by c c c . The 00 term is at most c log 2 ( 1 + c / t N ) + c log 2 e c\log_2(1+c/t_N) + c\log_2 e c log 2 ( 1 + c / t N ) + c log 2 e , by applying ln ( 1 + c / t N ) ≤ c / t N \ln(1+c/t_N) \le c/t_N ln ( 1 + c / t N ) ≤ c / t N to the part weighted by t N t_N t N . The 11 term is P = ( 11 ) log 2 [ 1 + c / P ≠ ( 11 ) ] ≤ c log 2 e / [ ( 1 − ϵ ) ( 1 − 6 s ) ] P_=(11)\log_2[1+c/P_{\ne}(11)] \le c\log_2 e/[(1-\epsilon)(1-6s)] P = ( 11 ) log 2 [ 1 + c / P = ( 11 )] ≤ c log 2 e / [( 1 − ϵ ) ( 1 − 6 s )] . The two bounds together give J N ( q N ) ≤ c log 2 min { N , 1 + c / t N } + O s , ϵ ( 1 ) J_N(q_N) \le c\log_2\min\{N,1+c/t_N\} + O_{s,\epsilon}(1) J N ( q N ) ≤ c log 2 min { N , 1 + c / t N } + O s , ϵ ( 1 ) . For B = c / t N > 0 B = c/t_N > 0 B = c / t N > 0 ,
min { N , 1 + B } ≤ ( 1 + 1 / B ) min { N , B } ≤ 2 ( 1 + t N / c ) N 1 + N t N / c . \min\{N,1+B\} \le(1+1/B)\min\{N,B\} \le2(1+t_N/c)\frac{N}{1+Nt_N/c}. min { N , 1 + B } ≤ ( 1 + 1/ B ) min { N , B } ≤ 2 ( 1 + t N / c ) 1 + N t N / c N .
The logarithm of the prefactor contributes at most c + t N log 2 e c + t_N\log_2 e c + t N log 2 e to the bound on J N ( q N ) J_N(q_N) J N ( q N ) . For the constructed family, s ≤ 1 / 36 s \le1/36 s ≤ 1/36 and P ≠ ( 11 ) ≥ 1 / 4 P_{\ne}(11) \ge1/4 P = ( 11 ) ≥ 1/4 , since both 1 − 6 s 1-6s 1 − 6 s and ( 1 − u N ) 2 (1-u_N)^2 ( 1 − u N ) 2 are at least 1 / 4 1/4 1/4 . The mixture-label bound has additive term at most 1 + c log 2 e 1+c\log_2 e 1 + c log 2 e by Eq. (45) , and the relative-entropy bound has additive term at most 1 + 5 c log 2 e 1+5c\log_2 e 1 + 5 c log 2 e since P = ( 11 ) ≤ 1 P_=(11) \le1 P = ( 11 ) ≤ 1 . Including the prefactor gives a total additive upper bound of 1 + c + ( 5 c + t N ) log 2 e 1+c+(5c+t_N)\log_2 e 1 + c + ( 5 c + t N ) log 2 e , uniform in the hierarchy level.
Lower bound. Use the N − 1 N-1 N − 1 independent bits of § 0.15.4 , with r i = Pr ( R i = 1 ) = 1 / ( N − i + 1 ) r_i = \Pr(R_i=1) = 1/(N-i+1) r i = Pr ( R i = 1 ) = 1/ ( N − i + 1 ) . The first-one setting X X X is uniform on [ N ] [N] [ N ] , including setting N N N for an all-zero database. Alice sends her outcome for every setting. For request i i i , Bob queries i i i and flags the joint-zero outcome. The flag probability is t N + c 1 X = i t_N+c\mathbf{1}_{X=i} t N + c 1 X = i conditional on X X X , and X = i X=i X = i implies R i = 1 R_i=1 R i = 1 . Consequently the marginal flag probability is v = Pr ( G i = 1 ) = t N + c / N v = \Pr(G_i=1) = t_N+c/N v = Pr ( G i = 1 ) = t N + c / N and its joint probability with R i = 1 R_i=1 R i = 1 is w i = Pr ( G i = 1 , R i = 1 ) = t N r i + c / N w_i = \Pr(G_i=1,R_i=1) = t_Nr_i+c/N w i = Pr ( G i = 1 , R i = 1 ) = t N r i + c / N .
The flag contributes v D B e r ( w i / v ∥ r i ) vD_{\mathrm{Ber}}(w_i/v\mathbin\Vert r_i) v D Ber ( w i / v ∥ r i ) to the mutual information. The term weighted by v − w i v-w_i v − w i in this divergence is bounded below by − ( w i − v r i ) log 2 e -(w_i-vr_i)\log_2 e − ( w i − v r i ) log 2 e using ln ( a / b ) ≥ a − b \ln(a/b) \ge a-b ln ( a / b ) ≥ a − b . The unflagged output contributes a nonnegative amount, so
I ( R i : G i ) ≥ w i log 2 w i v r i − ( w i − v r i ) log 2 e . (48) I(R_i:G_i) \ge w_i\log_2\frac{w_i}{vr_i}-(w_i-vr_i)\log_2 e. \tag*{(48)} I ( R i : G i ) ≥ w i log 2 v r i w i − ( w i − v r i ) log 2 e . (48)
Here w i − v r i = c ( 1 − r i ) / N w_i-vr_i = c(1-r_i)/N w i − v r i = c ( 1 − r i ) / N . With k = N − i + 1 k=N-i+1 k = N − i + 1 , the first logarithm has argument ( t N + c k / N ) / ( t N + c / N ) ≥ 1 (t_N+ck/N)/(t_N+c/N) \ge1 ( t N + c k / N ) / ( t N + c / N ) ≥ 1 . We may therefore replace its coefficient w i w_i w i by c / N c/N c / N in the lower bound. Its argument is at least k / ( 1 + N t N / c ) k/(1+Nt_N/c) k / ( 1 + N t N / c ) . Summing over k = 2 , … , N k=2,\ldots,N k = 2 , … , N and using ln ( N ! ) ≥ N ln N − N \ln(N!) \ge N\ln N-N ln ( N !) ≥ N ln N − N yields
J N ( q N ) ≥ c N log 2 ( N ! ) − c ( 1 − 1 N ) log 2 ( 1 + N t N / c ) − c log 2 e ≥ c log 2 ( N 1 + N t N / c ) − 2 c log 2 e . (49) \begin{aligned}
J_N(q_N) \ge\frac{c}{N}\log_2(N!)-c\left(1-\frac{1}{N}\right)\log_2(1+Nt_N/c)-c\log_2 e \\
&\ge c\log_2\left(\frac{N}{1+Nt_N/c}\right)-2c\log_2 e. \tag*{(49)}
\end{aligned} J N ( q N ) ≥ N c log 2 ( N !) − c ( 1 − N 1 ) log 2 ( 1 + N t N / c ) − c log 2 e ≥ c log 2 ( 1 + N t N / c N ) − 2 c log 2 e . (49)
Noise that decreases as a power of N N N . For u N = 1 2 N − α / 2 u_N=\frac{1}{2}N^{-\alpha/2} u N = 2 1 N − α /2 with α ≥ 0 \alpha\ge0 α ≥ 0 , the denominator in Eq. (47) is 1 + ( ϵ / 4 c ) N 1 − α 1+(\epsilon/4c)N^{1-\alpha} 1 + ( ϵ /4 c ) N 1 − α . The optimal score is then
J N ( q N ) = c min { α , 1 } log 2 N + O s , ϵ ( 1 ) . (50) J_N(q_N)=c\min\{\alpha,1\}\log_2 N+O_{s,\epsilon}(1). \tag*{(50)} J N ( q N ) = c min { α , 1 } log 2 N + O s , ϵ ( 1 ) . (50)
All outcome probabilities are at least t N = ( ϵ / 4 ) N − α t_N=(\epsilon/4)N^{-\alpha} t N = ( ϵ /4 ) N − α , the smallest contribution from the product branch. At α = 0 \alpha=0 α = 0 , the uniform noise bounds the score independently of N N N . At every α > 0 \alpha>0 α > 0 the score diverges, with coefficient c c c when α ≥ 1 \alpha\ge1 α ≥ 1 . If p s ∈ Q L p_s \in Q_L p s ∈ Q L , then q N ∈ Q L q_N \in Q_L q N ∈ Q L by convexity. For N > K N > K N > K and ( K + 5 ) s ≤ 1 (K+5)s \le1 ( K + 5 ) s ≤ 1 , every restriction to at most K K K settings per party stays local by Eq. (69) .
Strict violations with positive outcome probabilities
Fix a finite protocol of Sec. S2.2. Mix p L p_L p L with the local correlation U U U with U ( a , b ∣ x , y ) = 1 / 4 U(a,b \mid x,y)=1/4 U ( a , b ∣ x , y ) = 1/4 at every setting pair, using a mixing weight 0 ≤ δ ≤ 1 0 \le\delta\le1 0 ≤ δ ≤ 1 . By convexity, p δ = ( 1 − δ ) p L + δ U p_\delta=(1-\delta)p_L+\delta U p δ = ( 1 − δ ) p L + δ U is at level L L L , with every outcome probability positive for δ > 0 \delta>0 δ > 0 . The mixing adds false flags and changes Bob’s output probabilities. For each database string, and hence conditional on any bit value, the guess law changes by at most δ \delta δ in total variation, the half-sum of the absolute differences of probabilities. For 0 ≤ δ ≤ 1 / 2 0 \le\delta\le1/2 0 ≤ δ ≤ 1/2 , couple the old and new binary guesses so their probability of disagreement is at most δ \delta δ . Either guess plus the disagreement indicator determines the other, so the entropy changes by at most the binary entropy h 2 ( δ ) = − δ log 2 δ − ( 1 − δ ) log 2 ( 1 − δ ) h_2(\delta)=-\delta\log_2\delta-(1-\delta)\log_2(1-\delta) h 2 ( δ ) = − δ log 2 δ − ( 1 − δ ) log 2 ( 1 − δ ) , continued to zero. Apply this bound to the unconditional and conditional guess entropies for each of the n R n_R n R database bits,
I I C ( p δ ) ≥ I I C ( p L ) − 2 n R h 2 ( δ ) . (51) I_{\mathrm{IC}}(p_\delta) \ge I_{\mathrm{IC}}(p_L)-2n_Rh_2(\delta). \tag*{(51)} I IC ( p δ ) ≥ I IC ( p L ) − 2 n R h 2 ( δ ) . (51)
Every strict finite violation persists for positive δ \delta δ sufficiently close to zero. Here n R = N n_R=N n R = N for the sparse bits and n R = k N n_R=kN n R = k N for the fair bits in blocks. Choosing k = ⌈ 4 / s L ⌉ k=\lceil4/s_L\rceil k = ⌈ 4/ s L ⌉ and N = k 2 k N=k2^k N = k 2 k gives a score above 2 by Eq. (39) . Hence 0 < δ ≤ 1 / 2 0<\delta\le1/2 0 < δ ≤ 1/2 with 2 k N h 2 ( δ ) < 1 2kNh_2(\delta)<1 2 k N h 2 ( δ ) < 1 preserves a violation.
A noise tolerance independent of the setting count
Conditioning on the requested bit gives a noise tolerance independent of the number of settings. Use the protocol of Sec. S2.2 with r = 1 / N r=1/N r = 1/ N , and write s = s L s=s_L s = s L for the exact certificate’s diagonal probability. Let p ~ \tilde{p} p ~ be any nonsignalling correlation within total variation distance δ \delta δ of p L p_L p L at every setting pair. The score on p ~ \tilde{p} p ~ is at least 2 whenever
N ≥ ⌈ 4 e 2 4 / s ⌉ , δ ≤ s 4 e 2 − 4 / s . (52) N \ge\left\lceil4e\,2^{4/s}\right\rceil,\qquad\delta\le\frac{s}{4e}2^{-4/s}. \tag*{(52)} N ≥ ⌈ 4 e 2 4/ s ⌉ , δ ≤ 4 e s 2 − 4/ s . (52)
At fixed L L L this choice allows the same positive noise tolerance for every sufficiently large N N N . For p ~ = ( 1 − η ) p L + η U \tilde{p}=(1-\eta)p_L+\eta U p ~ = ( 1 − η ) p L + η U , where U U U is the uniform local correlation and 0 < η ≤ δ 0<\eta\le\delta 0 < η ≤ δ , convexity gives p ~ ∈ Q L \tilde{p}\in Q_L p ~ ∈ Q L , and every outcome probability is positive.
We compare the flag probability given a one with the unconditional flag probability. Under p ~ \tilde{p} p ~ , write a i = Pr ( G i = 1 ∣ R i = 1 ) a_i=\Pr(G_i=1\mid R_i=1) a i = Pr ( G i = 1 ∣ R i = 1 ) and b i = Pr ( G i = 1 ) b_i=\Pr(G_i=1) b i = Pr ( G i = 1 ) for these probabilities. Conditional on any nonzero database string, the flag probability is p ~ ( 0 , 0 ∣ x , i ) \tilde{p}(0,0\mid x,i) p ~ ( 0 , 0 ∣ x , i ) , where x x x is the position of the first one. On the all-zero string Alice sends one without needing the box, so the flag probability is zero for both correlations. The per-setting total variation bound thus controls the change in each flag probability by δ \delta δ , even after conditioning on R i = 1 R_i=1 R i = 1 . In particular, when R i = 1 R_i=1 R i = 1 and the preceding entries are zero, the diagonal flag probability is at least s − δ s-\delta s − δ . Hence
a i ≥ ( s − δ ) ( 1 − r ) i − 1 , b i ≤ s r ( 1 − r ) i − 1 + δ ≤ s / N + δ . (53) a_i \ge(s-\delta)(1-r)^{i-1},\qquad b_i \le sr(1-r)^{i-1}+\delta\le s/N+\delta. \tag*{(53)} a i ≥ ( s − δ ) ( 1 − r ) i − 1 , b i ≤ sr ( 1 − r ) i − 1 + δ ≤ s / N + δ . (53)
The mean a ˉ = N − 1 ∑ i a i \bar{a}=N^{-1}\sum_i a_i a ˉ = N − 1 ∑ i a i is at least ( s − δ ) [ 1 − ( 1 − 1 / N ) N ] (s-\delta)[1-(1-1/N)^N] ( s − δ ) [ 1 − ( 1 − 1/ N ) N ] . Under Eq. (52) , δ ≤ s / 8 \delta\le s/8 δ ≤ s /8 , so a ˉ ≥ ( 7 s / 8 ) ( 1 − e − 1 ) > s / 2 \bar{a}\ge(7s/8)(1-e^{-1})>s/2 a ˉ ≥ ( 7 s /8 ) ( 1 − e − 1 ) > s /2 .
Write b ∗ = s / N + δ b_*=s/N+\delta b ∗ = s / N + δ and let Ber ( a ) \operatorname{Ber}(a) Ber ( a ) denote the Bernoulli law with parameter a a a . The contribution from R i = 1 R_i=1 R i = 1 gives I ( R i : G i ) ≥ r D ( Ber ( a i ) ∥ Ber ( b i ) ) I(R_i:G_i)\ge rD(\operatorname{Ber}(a_i)\Vert\operatorname{Ber}(b_i)) I ( R i : G i ) ≥ r D ( Ber ( a i ) ∥ Ber ( b i )) . In bits, ( 1 − a ) ln ( 1 − a ) ≥ − a (1-a)\ln(1-a)\ge-a ( 1 − a ) ln ( 1 − a ) ≥ − a gives D ( Ber ( a ) ∥ Ber ( b ) ) ≥ a log 2 [ a / ( e b ) ] D(\operatorname{Ber}(a)\Vert\operatorname{Ber}(b))\ge a\log_2[a/(eb)] D ( Ber ( a ) ∥ Ber ( b )) ≥ a log 2 [ a / ( e b )] . To sum the contributions, replace each b i b_i b i by its upper bound b ∗ b_* b ∗ and use convexity of a log 2 a a\log_2a a log 2 a to lower bound the sum by its value at the mean a ˉ \bar{a} a ˉ ,
I I C ( p ~ ) ≥ a ˉ log 2 a ˉ e b ∗ ≥ s 2 log 2 s 2 e b ∗ ≥ 2. (54) I_{\mathrm{IC}}(\tilde{p}) \ge\bar{a}\log_2\frac{\bar{a}}{eb_*}\ge\frac{s}{2}\log_2\frac{s}{2eb_*}\ge2. \tag*{(54)} I IC ( p ~ ) ≥ a ˉ log 2 e b ∗ a ˉ ≥ 2 s log 2 2 e b ∗ s ≥ 2. (54)
Here b ∗ ≤ ( s / ( 2 e ) ) 2 − 4 / s b_* \le(s/(2e))^{2-4/s} b ∗ ≤ ( s / ( 2 e ) ) 2 − 4/ s , and a log 2 [ a / ( e b ∗ ) ] a \log_2[a/(e b_*)] a log 2 [ a / ( e b ∗ )] is increasing for a ≥ b ∗ a \ge b_* a ≥ b ∗ .
At a fixed positive uniform mixing weight η \eta η , the score of this protocol stays bounded as N N N grows, even if Bob keeps the record T i = ( M , b ) T_i=(M,b) T i = ( M , b ) of the message and his outcome for request i i i . The uniform part puts a floor under every transcript probability. With c = 1 − e − 1 c=1-e^{-1} c = 1 − e − 1 , every value of T i T_i T i has unconditional probability at least c η / 4 c\eta/4 cη /4 , from the uniform outcomes on nonzero database strings. The divergence of the R i = 1 R_i=1 R i = 1 conditional law from the unconditional law is therefore at most log 2 ( 4 / ( c η ) ) \log_2(4/(c\eta)) log 2 ( 4/ ( cη )) . The unconditional law contains the R i = 0 R_i=0 R i = 0 conditional law with weight 1 − r 1-r 1 − r , so the divergence for that branch is at most − log 2 ( 1 − r ) -\log_2(1-r) − log 2 ( 1 − r ) . Summing over requests bounds the score for the full records and, by data processing, for the flags,
I I C ( p ~ ) ≤ log 2 4 c η + log 2 e , (55) I_{\mathrm{IC}}(\widetilde{p}) \le\log_2 \frac{4}{c\eta}+\log_2 e, \tag*{(55)} I IC ( p ) ≤ log 2 cη 4 + log 2 e , (55)
where − ( 1 − r ) ln ( 1 − r ) ≤ r -(1-r)\ln(1-r)\le r − ( 1 − r ) ln ( 1 − r ) ≤ r and N r = 1 Nr=1 N r = 1 .
Zero-error communication with independent copies
Alice and Bob receive labels i , j ∈ [ N ] i,j\in[N] i , j ∈ [ N ] . Bob may abstain, and must give the correct answer whenever he declares the labels equal or unequal. The success criterion is the minimum over input pairs of the probability that he gives either conclusive answer. For one copy Alice uses setting i i i and sends her outcome, while Bob uses setting j j j . The joint zero outcome certifies equality, and by Eq. (20) it occurs with probability s L s_L s L on equal inputs. To certify inequality they share a random map from [ N ] [N] [ N ] to { 0 , 1 } \{0,1\} { 0 , 1 } with independent fair values. Alice sends the hash at i i i . The hashes must agree on equal inputs and differ with probability 1 / 2 1/2 1/2 on unequal inputs.
Alice sends the outcomes of q q q independent copies and her hash bit in one message. On equal labels Bob has a joint zero outcome in at least one copy with probability 1 − ( 1 − s L ) q 1-(1-s_L)^q 1 − ( 1 − s L ) q . On unequal labels the differing hashes are conclusive with probability 1 / 2 1/2 1/2 . Bob abstains if neither event occurs. On equal labels the conclusive probability is at least 1 / 2 1/2 1/2 when ( 1 − s L ) q ≤ 1 / 2 (1-s_L)^q\le1/2 ( 1 − s L ) q ≤ 1/2 . The least such integer is
q = ⌈ ln 2 − ln ( 1 − s L ) ⌉ . q=\left\lceil\frac{\ln2}{-\ln(1-s_L)}\right\rceil. q = ⌈ − ln ( 1 − s L ) ln 2 ⌉ .
The number of copies is q q q and the message has q + 1 q+1 q + 1 bits, both independent of N N N . The rational level-two choice s 2 = 7 / 424 s_2=7/424 s 2 = 7/424 of Sec. S4 gives q = 42 q=42 q = 42 and 43 bits.
Independent copies give another correlation at the same NPA level. The parallel resource has a local outcome for each tuple of local outcomes in the constituent copies. Represent its projector by the tensor product of the component projectors. Completeness and same-setting orthogonality follow from the corresponding relations in each factor, and tensor products also preserve idempotence and cross-party commutation. Each retained word of length at most L L L maps to a tensor of component words of length at most L L L . The u , v u,v u , v entry of the product moment matrix is the product of the entries for the corresponding component words. Taking tensor products of the component Gram vectors realizes this matrix and proves its positivity. The parallel resource is therefore at level L L L . The hash is sampled independently of these copies.
For N = 2 n N=2^n N = 2 n , the labels are n n n -bit strings. Corollary 4 of Gazi et al. [10 ] gives the exact one-way cost n n n bits at the same worst-case success probability throughout the commuting-operator model, including tensor-product quantum theory. Their Proposition 4 gives a lower bound of n − 1 n-1 n − 1 bits for interactive classical communication.
An optimized certificate at level two
At level two the retained words contain at most two projectors. It suffices to match singletons, pure words with distinct labels, and the mixed words A i B j A_iB_j A i B j . Use reference and replacement vectors R , S R,S R , S as in § 0.14 , requiring ⟨ S , w R ⟩ = ⟨ R , w R ⟩ \langle S,wR\rangle=\langle R,wR\rangle ⟨ S , w R ⟩ = ⟨ R , w R ⟩ on these words. Each local space has one common direction in each summand, with a distribution of within-party overlaps. The tensor-product block supplies the mixed-word pairings and two auxiliary blocks supply the missing pure-word pairings. The rate is the reciprocal of C = ∥ S ∥ 2 C = \lVert S\rVert^2 C = ∥ S ∥ 2 . The construction below gives C = 35 + 18 2 C = 35 + 18\sqrt{2} C = 35 + 18 2 with the original equality and marginal relations.
In the tensor-product block choose the within-party overlap d d d for distinct settings from { 0 , 1 / 2 } \{0,1/2\} { 0 , 1/2 } with Pr ( d = 1 / 2 ) = m 0 − 1 \Pr(d = 1/2) = m_0 - 1 Pr ( d = 1/2 ) = m 0 − 1 , where 1 < m 0 ≤ 2 1 < m_0 \le2 1 < m 0 ≤ 2 . Inner products in this block are averages over d d d . Let g A , g B g_A,g_B g A , g B be unit common directions and e i , f i e_i,f_i e i , f i private orthonormal directions in their respective spaces, orthogonal to the common directions. In this block A i , B i A_i,B_i A i , B i project onto
u i = d g A + 1 − d e i , v i = d g B + 1 − d f i u_i = \sqrt{d}\,g_A + \sqrt{1-d}\,e_i,\qquad v_i = \sqrt{d}\,g_B + \sqrt{1-d}\,f_i u i = d g A + 1 − d e i , v i = d g B + 1 − d f i
in the respective tensor factors. The reference vector pairs the private directions at each setting. Its replacement lies along the product of the common directions, with amplitude chosen to match the average inner product with the mixed row,
R 0 = 1 1 − d ∑ i = 1 N e i ⊗ f i , S 0 = d E d 2 g A ⊗ g B . R_0 = \frac{1}{1-d}\sum_{i=1}^{N} e_i \otimes f_i,\qquad S_0 = \frac{d}{\mathbb{E}d^2}\,g_A \otimes g_B. R 0 = 1 − d 1 i = 1 ∑ N e i ⊗ f i , S 0 = E d 2 d g A ⊗ g B .
The mixed row A i B j R 0 = δ i j u i ⊗ v j A_iB_jR_0 = \delta_{ij}u_i \otimes v_j A i B j R 0 = δ ij u i ⊗ v j has reference pairing δ i j \delta_{ij} δ ij for each d d d . Pairing this vector with S 0 S_0 S 0 and averaging gives δ i j E [ d 2 ] / E [ d 2 ] = δ i j \delta_{ij}\mathbb{E}[d^2]/\mathbb{E}[d^2] = \delta_{ij} δ ij E [ d 2 ] / E [ d 2 ] = δ ij . With Alice’s projector alone, A i R 0 = u i ⊗ f i / 1 − d A_iR_0 = u_i \otimes f_i/\sqrt{1-d} A i R 0 = u i ⊗ f i / 1 − d has reference pairing 1 / ( 1 − d ) 1/(1-d) 1/ ( 1 − d ) , whose average is m 0 m_0 m 0 . For distinct i , j i,j i , j , A i A j R 0 = d u i ⊗ f j / 1 − d A_iA_jR_0 = d\,u_i \otimes f_j/\sqrt{1-d} A i A j R 0 = d u i ⊗ f j / 1 − d , whose reference pairing vanishes by orthogonality of the private directions. The private Bob factor in both Alice rows is orthogonal to the common factor of S 0 S_0 S 0 . The same holds for pure Bob rows with the factors interchanged. A repeated label reduces to a word of length one by idempotence. The tensor-product replacement costs its mean squared norm,
C 0 = 1 E d 2 = 4 m 0 − 1 . C_0 = \frac{1}{\mathbb{E}d^2} = \frac{4}{m_0-1}. C 0 = E d 2 1 = m 0 − 1 4 .
The auxiliary blocks must supply the rest of the pure-word pairings. The desired singleton moment is three before normalization. Since the tensor-product reference vector contributes m 0 m_0 m 0 , each auxiliary reference vector must supply β = 3 − m 0 \beta= 3-m_0 β = 3 − m 0 for its party. In Alice’s block all B i B_i B i are zero and A i A_i A i projects onto t g + 1 − t e i \sqrt{t}\,g+\sqrt{1-t}\,e_i t g + 1 − t e i , where g g g is a unit common direction, the e i e_i e i are private orthonormal directions orthogonal to g g g , and 0 < t ≤ 1 0 < t \le1 0 < t ≤ 1 . Here t t t is the inner product between vectors for distinct settings. Let R A = β / t g R_A = \sqrt{\beta/t}\,g R A = β / t g and S A = f ( t ) R A S_A = f(t)R_A S A = f ( t ) R A for real f f f , with inner products averaged over t t t . The reference pairings for A i A_i A i and A i A j A_iA_j A i A j with i ≠ j i\ne j i = j are β \beta β and β t \beta t β t , respectively. The corresponding replacement pairings are β f ( t ) \beta f(t) β f ( t ) and β t f ( t ) \beta t f(t) β t f ( t ) . Bob’s block interchanges the parties. The total replacement pairing for a singleton comes entirely from its auxiliary block, so β E f = 3 \beta\mathbb{E}f = 3 β E f = 3 . At distinct labels the tensor-product pairings are both zero, so E [ t f ] = E t \mathbb{E}[tf] = \mathbb{E}t E [ t f ] = E t .
The following two-point distribution satisfies both matching conditions and minimizes the auxiliary squared norm β E [ f 2 / t ] \beta\mathbb{E}[f^2/t] β E [ f 2 / t ] ,
r = 9 36 − 8 β , t ∈ { r , 1 } , Pr ( t = r ) = 3 − 4 r 3 − 3 r , r = \frac{9}{36-8\beta},\qquad t\in\{r,1\},\qquad\Pr(t=r)=\frac{3-4r}{3-3r}, r = 36 − 8 β 9 , t ∈ { r , 1 } , Pr ( t = r ) = 3 − 3 r 3 − 4 r ,
f ( r ) = 4 r 4 r − 1 , f ( 1 ) = 4 ( 2 r − 1 ) 4 r − 1 . f(r)=\frac{4r}{4r-1},\qquad f(1)=\frac{4(2r-1)}{4r-1}. f ( r ) = 4 r − 1 4 r , f ( 1 ) = 4 r − 1 4 ( 2 r − 1 ) .
For 1 ≤ β < 2 1\le\beta<2 1 ≤ β < 2 this defines probabilities and gives E t = 4 r / 3 \mathbb{E}t=4r/3 E t = 4 r /3 , E f = 8 r / [ 3 ( 4 r − 1 ) ] = 3 / β \mathbb{E}f=8r/[3(4r-1)]=3/\beta E f = 8 r / [ 3 ( 4 r − 1 )] = 3/ β , and E [ t f ] = 4 r / 3 \mathbb{E}[tf]=4r/3 E [ t f ] = 4 r /3 . The squared norm in each auxiliary block is C A = C B = β E [ f 2 / t ] = 81 / β − 24 C_A=C_B=\beta\mathbb{E}[f^2/t]=81/\beta-24 C A = C B = β E [ f 2 / t ] = 81/ β − 24 .
The direct sums R = R 0 ⊕ R A ⊕ R B R=R_0\oplus R_A\oplus R_B R = R 0 ⊕ R A ⊕ R B and S = S 0 ⊕ S A ⊕ S B S=S_0\oplus S_A\oplus S_B S = S 0 ⊕ S A ⊕ S B match every required pairing. Dividing the singleton moments 3 3 3 and the mixed moments δ i j \delta_{ij} δ ij by the total squared norm gives the zero-outcome marginals 3 / C 3/C 3/ C and p ( 0 , 0 ∣ i , j ) = δ i j / C p(0,0\mid i,j)=\delta_{ij}/C p ( 0 , 0 ∣ i , j ) = δ ij / C . The three blocks’ costs add,
C = 4 m 0 − 1 + 162 3 − m 0 − 48. C=\frac{4}{m_0-1}+\frac{162}{3-m_0}-48. C = m 0 − 1 4 + 3 − m 0 162 − 48.
Raising m 0 m_0 m 0 lowers the tensor-product cost and increases the auxiliary costs. Minimizing their sum over 1 < m 0 ≤ 2 1<m_0\le2 1 < m 0 ≤ 2 gives 35 + 18 2 35+18\sqrt{2} 35 + 18 2 at m 0 = 1 + 4 / ( 2 + 9 2 ) m_0=1+4/(2+9\sqrt{2}) m 0 = 1 + 4/ ( 2 + 9 2 ) . The rational choice m 0 = 5 / 4 m_0=5/4 m 0 = 5/4 gives r = 9 / 22 r=9/22 r = 9/22 , Pr ( t = r ) = 10 / 13 \Pr(t=r)=10/13 Pr ( t = r ) = 10/13 , f ( r ) = 18 / 7 f(r)=18/7 f ( r ) = 18/7 , f ( 1 ) = − 8 / 7 f(1)=-8/7 f ( 1 ) = − 8/7 , and s 2 = 7 / 424 s_2=7/424 s 2 = 7/424 .
Optimality within the three-block rank-one construction. For N ≥ 2 N \ge2 N ≥ 2 , allow any distribution on 0 ≤ d < 1 0 \le d < 1 0 ≤ d < 1 in the tensor-product block and a variable amplitude in R 0 = q ( d ) ( 1 − d ) − 1 ∑ i e i ⊗ f i R_0 = q(d)(1-d)^{-1}\sum_i e_i \otimes f_i R 0 = q ( d ) ( 1 − d ) − 1 ∑ i e i ⊗ f i . The reference pairing for A i B i A_iB_i A i B i requires E q 2 = 1 \mathbb{E}q^2 = 1 E q 2 = 1 . The singleton reference pairing gives m 0 = E [ q 2 / ( 1 − d ) ] m_0 = \mathbb{E}[q^2/(1-d)] m 0 = E [ q 2 / ( 1 − d )] . A replacement along g A ⊗ g B g_A \otimes g_B g A ⊗ g B must have averaged mixed pairing one. Cauchy–Schwarz then gives C 0 ≥ 1 / E [ q 2 d ] C_0 \ge1/\mathbb{E}[q^2d] C 0 ≥ 1/ E [ q 2 d ] . Using d 2 ≤ d / [ 4 ( 1 − d ) ] d^2 \le d/[4(1-d)] d 2 ≤ d / [ 4 ( 1 − d )] gives C 0 ≥ 4 / ( m 0 − 1 ) C_0 \ge4/(m_0-1) C 0 ≥ 4/ ( m 0 − 1 ) .
In the auxiliary blocks allow any distribution on 0 < t ≤ 1 0 < t \le1 0 < t ≤ 1 and any reference amplitude along the common direction. The measure weighted by t ∥ R A ∥ 2 t\|R_A\|^2 t ∥ R A ∥ 2 has total mass β = 3 − m 0 \beta= 3-m_0 β = 3 − m 0 . Normalize it to a probability measure and write S A = f R A S_A = fR_A S A = f R A on the support of the reference amplitude. This gives the same matching conditions and the cost β E [ f 2 / t ] \beta\mathbb{E}[f^2/t] β E [ f 2 / t ] on that support. Where the reference amplitude is zero, the replacement can only add to the squared norm.
To prove a lower bound on the quadratic cost, subtract a square built from f ( t ) / t f(t)/t f ( t ) / t and a linear function α + γ t \alpha+\gamma t α + γ t . The cross term depends only on the known averages of f f f and t f tf t f . For equality, choose the line interpolating f ( t ) / t f(t)/t f ( t ) / t at the two proposed support points. Put n = 4 r − 1 n=4r-1 n = 4 r − 1 , α = 4 ( 1 + 2 r ) / n \alpha=4(1+2r)/n α = 4 ( 1 + 2 r ) / n , and γ = − 8 / n \gamma=-8/n γ = − 8/ n for the same r r r as above. Completing the square with α + γ t \alpha+\gamma t α + γ t and using the two matching conditions gives
β E [ f 2 / t ] ≥ β E [ 2 ( α + γ t ) f − t ( α + γ t ) 2 ] = 6 α + β E [ 2 γ t − t ( α + γ t ) 2 ] . \beta\mathbb{E}[f^2/t] \ge\beta\mathbb{E}[2(\alpha+\gamma t)f-t(\alpha+\gamma t)^2]
=6\alpha+\beta\mathbb{E}[2\gamma t-t(\alpha+\gamma t)^2]. β E [ f 2 / t ] ≥ β E [ 2 ( α + γ t ) f − t ( α + γ t ) 2 ] = 6 α + β E [ 2 γ t − t ( α + γ t ) 2 ] .
The final integrand is 64 [ ( 1 − t ) ( t − r ) 2 − r 2 ] / n 2 64[(1-t)(t-r)^2-r^2]/n^2 64 [( 1 − t ) ( t − r ) 2 − r 2 ] / n 2 , bounded below by − 64 r 2 / n 2 -64r^2/n^2 − 64 r 2 / n 2 because t ≤ 1 t \le1 t ≤ 1 . Substituting r r r gives C A ≥ 81 / β − 24 C_A \ge81/\beta-24 C A ≥ 81/ β − 24 and the same bound for C B C_B C B . At the two support points t = r , 1 t=r,1 t = r , 1 the integrand attains its lower bound and f ( t ) = t ( α + γ t ) f(t)=t(\alpha+\gamma t) f ( t ) = t ( α + γ t ) saturates the square inequality. The sum of the three bounds on C C C is minimized over 1 < m 0 < 3 1<m_0<3 1 < m 0 < 3 at the same m 0 m_0 m 0 as above, which lies in the range of the construction.
Dependence on the hierarchy level
An upper bound on exact equality certification
At higher levels, positivity constrains sequences of projectors that involve more settings. Suppose a level-L L L moment matrix has p ( 0 , 0 ∣ i , j ) = 0 p(0,0\mid i,j)=0 p ( 0 , 0 ∣ i , j ) = 0 for i ≠ j i\ne j i = j . We use this condition to compare every diagonal certificate to a different branch of a single sequence of tests. Choose m m m distinct settings numbered 1 , … , m 1,\ldots,m 1 , … , m , with 2 ≤ m ≤ min ( N , L ) 2\le m\le\min(N,L) 2 ≤ m ≤ min ( N , L ) . Write Q i = 1 − A i Q_i=1-A_i Q i = 1 − A i for the projector onto outcome one. Alice’s j j j th test is affirmative if its outcome is zero, in the range of A j A_j A j . The first affirmative result among the first m − 1 m-1 m − 1 tests gives branch j < m j<m j < m , and all negative results give branch m m m . The polynomial for a branch places the earliest test at the right,
F j = A j Q j − 1 ⋯ Q 1 ( j < m ) , F m = Q m − 1 ⋯ Q 1 . F_j=A_jQ_{j-1}\cdots Q_1\quad(j<m),\qquad F_m=Q_{m-1}\cdots Q_1. F j = A j Q j − 1 ⋯ Q 1 ( j < m ) , F m = Q m − 1 ⋯ Q 1 .
The branch probabilities have a common budget of one. With U j = Q j ⋯ Q 1 U_j=Q_j\cdots Q_1 U j = Q j ⋯ Q 1 and U 0 = 1 U_0=1 U 0 = 1 , the relation A j 2 + Q j 2 = 1 A_j^2+Q_j^2=1 A j 2 + Q j 2 = 1 gives F j ∗ F j + U j ∗ U j = U j − 1 ∗ U j − 1 F_j^*F_j+U_j^*U_j=U_{j-1}^*U_{j-1} F j ∗ F j + U j ∗ U j = U j − 1 ∗ U j − 1 for j < m j<m j < m . Since F m = U m − 1 F_m=U_{m-1} F m = U m − 1 , summing gives ∑ j = 1 m F j ∗ F j = 1 \sum_{j=1}^m F_j^*F_j=1 ∑ j = 1 m F j ∗ F j = 1 .
To compare an individual diagonal certificate with its branch, work with the seminorm ∥ w ∥ ℓ 2 = ℓ ( w ∗ w ) \|w\|_\ell^2=\ell(w^*w) ∥ w ∥ ℓ 2 = ℓ ( w ∗ w ) of polynomials of degree at most L L L , where ℓ \ell ℓ is the moment functional. Positive semidefiniteness makes every vector of seminorm zero orthogonal to all retained vectors. If P P P is an outcome projector and w w w , P w Pw P w both have degree at most L L L , then ∥ P w ∥ ℓ 2 + ∥ ( 1 − P ) w ∥ ℓ 2 = ∥ w ∥ ℓ 2 \|Pw\|_\ell^2+\|(1-P)w\|_\ell^2=\|w\|_\ell^2 ∥ P w ∥ ℓ 2 + ∥ ( 1 − P ) w ∥ ℓ 2 = ∥ w ∥ ℓ 2 . Thus multiplying a zero-seminorm vector on the left by P P P preserves its zero seminorm within the degree bound.
For i ≠ j i\ne j i = j , the joint projector A i B j A_iB_j A i B j has squared seminorm p ( 0 , 0 ∣ i , j ) = 0 p(0,0\mid i,j)=0 p ( 0 , 0 ∣ i , j ) = 0 . On Bob’s outcome-zero branch at setting j j j , every earlier affirmative outcome in Alice’s sequence has such a zero vector. Expand the difference between the sequence of earlier negative tests and the identity to isolate those zero vectors,
Q j − 1 ⋯ Q 1 − 1 = − ∑ i < j Q j − 1 ⋯ Q i + 1 A i . (56) Q_{j-1}\cdots Q_1-1=-\sum_{i<j}Q_{j-1}\cdots Q_{i+1}A_i. \tag*{(56)} Q j − 1 ⋯ Q 1 − 1 = − i < j ∑ Q j − 1 ⋯ Q i + 1 A i . (56)
For j < m j<m j < m , each term of F j B j − A j B j F_jB_j-A_jB_j F j B j − A j B j is obtained from A i B j A_iB_j A i B j by left multiplication by the indicated Q Q Q ’s and A j A_j A j . The degree is at most j + 1 ≤ m j+1\le m j + 1 ≤ m , so the difference has zero seminorm. At j = m j=m j = m , apply the same expansion with F m = U m − 1 F_m=U_{m-1} F m = U m − 1 . It gives F m B m = B m F_mB_m=B_m F m B m = B m up to a zero-seminorm vector, with degrees at most m m m .
Since B j B_j B j and 1 − B j 1-B_j 1 − B j commute with F j F_j F j , they split ∥ F j ∥ ℓ 2 \lVert F_j\rVert_\ell^2 ∥ F j ∥ ℓ 2 into two nonnegative squared seminorms, one of which is ∥ F j B j ∥ ℓ 2 \lVert F_jB_j\rVert_\ell^2 ∥ F j B j ∥ ℓ 2 . The latter seminorm is the diagonal probability for j < m j<m j < m and the marginal for j = m j=m j = m . All the polynomials being squared have degree at most m m m . The branch budget ∑ j F j † F j = 1 \sum_j F_j^\dagger F_j=1 ∑ j F j † F j = 1 therefore gives
∑ j < m p ( 0 , 0 ∣ j , j ) + p B ( 0 ∣ m ) ≤ 1. (57) \sum_{j<m}p(0,0\mid j,j)+p_B(0\mid m)\le1. \tag*{(57)} j < m ∑ p ( 0 , 0 ∣ j , j ) + p B ( 0 ∣ m ) ≤ 1. (57)
If every diagonal probability is s s s , then p B ( 0 ∣ m ) ≥ s p_B(0\mid m)\ge s p B ( 0 ∣ m ) ≥ s , so m s ≤ 1 ms\le1 m s ≤ 1 . A family with a uniform rate for every N N N satisfies s L ≤ 1 / L s_L\le1/L s L ≤ 1/ L . The marginal in Eq. (21) is 3 s L 3s_L 3 s L , which gives C L ≥ L + 2 C_L\ge L+2 C L ≥ L + 2 for N ≥ L N\ge L N ≥ L . For L ≥ N ≥ 2 L\ge N\ge2 L ≥ N ≥ 2 , take m = N m=N m = N in Eq. (57) . Since p B ( 0 ∣ m ) ≥ p ( 0 , 0 ∣ m , m ) p_B(0\mid m)\ge p(0,0\mid m,m) p B ( 0 ∣ m ) ≥ p ( 0 , 0 ∣ m , m ) , the sum of all N N N diagonal probabilities is at most one even when they are unequal. The upper bound 1 / N 1/N 1/ N on the average is attained by drawing a shared uniform label and outputting 0 precisely when the local input equals that label.
A quadratic bound on the probability of exact equality certification
The sequential argument uses one degree for each tested setting. A polynomial in the sum of Alice’s projectors gives a bound using all settings at once. Take a level-L L L correlation, with L ≥ 2 L\ge2 L ≥ 2 and N N N settings per party, whose joint zero outcome vanishes whenever i ≠ j i\ne j i = j . Write s i = p ( 0 , 0 ∣ i , i ) s_i=p(0,0\mid i,i) s i = p ( 0 , 0 ∣ i , i ) for the diagonal rate at setting i i i . The positive odd integer K K K controls the polynomial degree. For every K ≤ 2 L − 3 K\le2L-3 K ≤ 2 L − 3 with K 2 < 6 N + 1 K^2<6N+1 K 2 < 6 N + 1 , the sum of the diagonal rates obeys
∑ i = 1 N s i ≤ N K 2 ( 1 − K 2 − 1 6 N ) − 2 . (58) \sum_{i=1}^{N}s_i\le\frac{N}{K^2}\left(1-\frac{K^2-1}{6N}\right)^{-2}. \tag*{(58)} i = 1 ∑ N s i ≤ K 2 N ( 1 − 6 N K 2 − 1 ) − 2 . (58)
With K = 2 L − 3 K=2L-3 K = 2 L − 3 , this gives s L ≤ ( 2 L − 3 ) − 2 s_L\le(2L-3)^{-2} s L ≤ ( 2 L − 3 ) − 2 for any common rate feasible for arbitrarily many settings at level L L L . For finite N N N , choose the largest odd K ≤ 2 N K\le\sqrt{2N} K ≤ 2 N and take L ≥ ( K + 3 ) / 2 L\ge(K+3)/2 L ≥ ( K + 3 ) /2 . Equation (58) bounds the average diagonal rate by ( 9 / 8 + O ( N − 1 ) ) / N (9/8+O(N^{-1}))/N ( 9/8 + O ( N − 1 )) / N . Indeed, K 2 / N = 2 + O ( N − 1 / 2 ) K^2/N=2+O(N^{-1/2}) K 2 / N = 2 + O ( N − 1/2 ) , and [ y ( 1 − y / 6 ) 2 ] − 1 [y(1-y/6)^2]^{-1} [ y ( 1 − y /6 ) 2 ] − 1 has its stationary point at y = 2 y=2 y = 2 , where the value is 9 / 8 9/8 9/8 . For quantum correlations the sequential argument can use the entire list of settings, giving the exact average rate 1 / N 1/N 1/ N , attained by the shared-label strategy above.
Put J = ∑ j = 1 N A j J=\sum_{j=1}^{N}A_j J = ∑ j = 1 N A j . Its first two moments on Bob’s outcome-zero branch at setting i i i are fixed by s i s_i s i . To derive them, let ℓ \ell ℓ be the level-L L L moment functional. Use the inner product on moment vectors, ⟨ f , g ⟩ ℓ = ℓ ( f † g ) \langle f,g\rangle_\ell=\ell(f^\dagger g) ⟨ f , g ⟩ ℓ = ℓ ( f † g ) for polynomials of degree at most L L L , with † \dagger † denoting the adjoint. Write ∥ f ∥ ℓ 2 = ℓ ( f † f ) \lVert f\rVert_\ell^2=\ell(f^\dagger f) ∥ f ∥ ℓ 2 = ℓ ( f † f ) for the squared seminorm. Every term A j B i A_jB_i A j B i of J B i JB_i J B i with j ≠ i j\ne i j = i is a zero moment vector because it is a projector with zero probability. Thus J B i JB_i J B i and A i B i A_iB_i A i B i have the same pairings. Pairing J B i JB_i J B i with B i B_i B i and with itself gives
ℓ ( B i J B i ) = ℓ ( B i J 2 B i ) = s i . (59) \ell(B_iJB_i)=\ell(B_iJ^2B_i)=s_i. \tag*{(59)} ℓ ( B i J B i ) = ℓ ( B i J 2 B i ) = s i . (59)
We seek a polynomial q q q for which F i = A i q ( J ) F_i=A_iq(J) F i = A i q ( J ) has a small total squared seminorm over all i i i and still pairs strongly with A i B i A_iB_i A i B i on Bob’s branch. The total is ℓ ( J q ( J ) 2 ) \ell(Jq(J)^2) ℓ ( J q ( J ) 2 ) . We can bound it by choosing q q q so that x q ( x ) 2 xq(x)^2 x q ( x ) 2 is uniformly small on [ 0 , N ] [0,N] [ 0 , N ] and proving the bound by squares of low-degree polynomials after substituting x = J x=J x = J . Set d = ( K − 1 ) / 2 ≤ L − 2 d=(K-1)/2\le L-2 d = ( K − 1 ) /2 ≤ L − 2 and write x = N sin 2 θ x=N\sin^2\theta x = N sin 2 θ with 0 ≤ θ ≤ π / 2 0\le\theta\le\pi/2 0 ≤ θ ≤ π /2 . A sine quotient makes x q ( x ) 2 xq(x)^2 x q ( x ) 2 proportional to a bounded sine squared, and its cosine counterpart supplies the difference from the bound,
q ( x ) = sin ( K θ ) K sin θ = 1 + 2 ∑ k = 1 d cos ( 2 k θ ) K , t ( x ) = cos ( K θ ) cos θ . (60) q(x)=\frac{\sin(K\theta)}{K\sin\theta}=\frac{1+2\sum_{k=1}^{d}\cos(2k\theta)}{K},\qquad t(x)=\frac{\cos(K\theta)}{\cos\theta}. \tag*{(60)} q ( x ) = K sin θ sin ( K θ ) = K 1 + 2 ∑ k = 1 d cos ( 2 k θ ) , t ( x ) = cos θ cos ( K θ ) . (60)
Both quotients extend continuously to the endpoints and are polynomials in x x x of degree at most d d d . The sine and cosine squares yield a polynomial identity for the difference between x q ( x ) 2 xq(x)^2 x q ( x ) 2 and its upper bound,
N K 2 − x q ( x ) 2 = N − x K 2 t ( x ) 2 . (61) \frac{N}{K^2}-xq(x)^2=\frac{N-x}{K^2}t(x)^2. \tag*{(61)} K 2 N − x q ( x ) 2 = K 2 N − x t ( x ) 2 . (61)
The identity is useful because N − J = ∑ j ( 1 − A j ) 2 N-J=\sum_j(1-A_j)^2 N − J = ∑ j ( 1 − A j ) 2 . At x = J x=J x = J , the right side is the sum of squares of K − 1 ( 1 − A j ) t ( J ) K^{-1}(1-A_j)t(J) K − 1 ( 1 − A j ) t ( J ) , whose degrees are at most d + 1 d+1 d + 1 . Hence ℓ ( J q ( J ) 2 ) ≤ N / K 2 \ell(Jq(J)^2)\le N/K^2 ℓ ( J q ( J ) 2 ) ≤ N / K 2 . This is the required upper bound on ∑ i ∥ F i ∥ ℓ 2 \sum_i\lVert F_i\rVert_\ell^2 ∑ i ∥ F i ∥ ℓ 2 since A i 2 = A i A_i^2=A_i A i 2 = A i .
For the diagonal pairing, keep the linear and quadratic terms of x q ( x ) xq(x) x q ( x ) , since their moments at B i B_i B i are already fixed by Eq. (59) . Put a = ( K 2 − 1 ) / 6 a=(K^2-1)/6 a = ( K 2 − 1 ) /6 , Δ = 1 − a / N > 0 \Delta=1-a/N>0 Δ = 1 − a / N > 0 and let h ( x ) = x [ q ( x ) − 1 + a x / N ] h(x)=x[q(x)-1+ax/N] h ( x ) = x [ q ( x ) − 1 + a x / N ] be the remainder after subtracting x − ( a / N ) x 2 x-(a/N)x^2 x − ( a / N ) x 2 . A sum of squares for B i h ( J ) B i B_i h(J)B_i B i h ( J ) B i within the allowed degree would give the required lower bound. The cosine expansion of q q q and a = ( 4 / K ) ∑ k = 1 d k 2 a=(4/K)\sum_{k=1}^{d} k^2 a = ( 4/ K ) ∑ k = 1 d k 2 give h ( x ) = 4 x 2 K N ∑ k = 1 d [ k 2 − sin 2 ( k θ ) / sin 2 θ ] h(x)=\frac{4x^2}{KN}\sum_{k=1}^{d}[k^2-\sin^2(k\theta)/\sin^2\theta] h ( x ) = K N 4 x 2 ∑ k = 1 d [ k 2 − sin 2 ( k θ ) / sin 2 θ ] . The squared sine quotient is the squared modulus of a geometric sum. Group the terms by the difference of their indices to write h h h as a nonnegative sum,
k 2 − ∣ ∑ j = 0 k − 1 e 2 i j θ ∣ 2 = 4 ∑ r = 1 k − 1 ( k − r ) sin 2 ( r θ ) . (62) k^2-\left|\sum_{j=0}^{k-1}e^{2ij\theta}\right|^2=4\sum_{r=1}^{k-1}(k-r)\sin^2(r\theta). \tag*{(62)} k 2 − j = 0 ∑ k − 1 e 2 ij θ 2 = 4 r = 1 ∑ k − 1 ( k − r ) sin 2 ( r θ ) . (62)
h ( x ) = 16 x 2 K N ∑ k = 1 d ∑ r = 1 k − 1 ( k − r ) sin 2 ( r θ ) . (63) h(x)=\frac{16x^2}{KN}\sum_{k=1}^{d}\sum_{r=1}^{k-1}(k-r)\sin^2(r\theta). \tag*{(63)} h ( x ) = K N 16 x 2 k = 1 ∑ d r = 1 ∑ k − 1 ( k − r ) sin 2 ( r θ ) . (63)
Each sine squared in Eq. (63) must be converted to a polynomial square of known degree. For odd r r r , P r ( x ) = sin ( r θ ) / sin θ P_r(x)=\sin(r\theta)/\sin\theta P r ( x ) = sin ( r θ ) / sin θ is a polynomial of degree at most ( r − 1 ) / 2 (r-1)/2 ( r − 1 ) /2 . For even r r r , P r ( x ) = sin ( r θ ) / ( sin θ cos θ ) P_r(x)=\sin(r\theta)/(\sin\theta\cos\theta) P r ( x ) = sin ( r θ ) / ( sin θ cos θ ) has degree at most ( r − 2 ) / 2 (r-2)/2 ( r − 2 ) /2 . Expand the imaginary part of ( cos θ + i sin θ ) r (\cos\theta+i\sin\theta)^r ( cos θ + i sin θ ) r and substitute sin 2 θ = x / N \sin^2\theta=x/N sin 2 θ = x / N and cos 2 θ = 1 − x / N \cos^2\theta=1-x/N cos 2 θ = 1 − x / N to obtain these degrees. Accordingly, the summands x 2 sin 2 ( r θ ) x^2\sin^2(r\theta) x 2 sin 2 ( r θ ) in Eq. (63) are x 3 P r ( x ) 2 / N x^3P_r(x)^2/N x 3 P r ( x ) 2 / N for odd r r r and x 2 ( N − x ) P r ( x ) 2 / N 2 x^2(N-x)P_r(x)^2/N^2 x 2 ( N − x ) P r ( x ) 2 / N 2 for even $r.
The remaining factors x x x and N − x N-x N − x are converted to sums of squares by the projector relations. For an odd r r r , substitute J J J and use J = ∑ j A j 2 J=\sum_j A_j^2 J = ∑ j A j 2 . Then B i J 3 P r ( J ) 2 B i B_iJ^3P_r(J)^2B_i B i J 3 P r ( J ) 2 B i is the sum of the squares of A j J P r ( J ) B i A_jJP_r(J)B_i A j J P r ( J ) B i . For an even r r r , use
J ( N − J ) = ∑ j < k ( A j − A k ) 2 (64) J(N-J)=\sum_{j<k}(A_j-A_k)^2 \tag*{(64)} J ( N − J ) = j < k ∑ ( A j − A k ) 2 (64)
to express B i J 2 ( N − J ) P r ( J ) 2 B i B_iJ^2(N-J)P_r(J)^2B_i B i J 2 ( N − J ) P r ( J ) 2 B i as the sum of the squares of ( A j − A k ) J P r ( J ) B i (A_j-A_k)JP_r(J)B_i ( A j − A k ) J P r ( J ) B i . In both cases the polynomials being squared have degree at most deg P r + 3 ≤ d + 2 ≤ L \deg P_r+3\le d+2\le L deg P r + 3 ≤ d + 2 ≤ L , since r ≤ d − 1 r\le d-1 r ≤ d − 1 . Thus ℓ ( B i h ( J ) B i ) ≥ 0 \ell(B_i h(J)B_i)\ge0 ℓ ( B i h ( J ) B i ) ≥ 0 . The contribution from the two known moments in Eq. (59) is ( 1 − a / N ) s i (1-a/N)s_i ( 1 − a / N ) s i , which gives the diagonal lower bound
ℓ ( B i J q ( J ) B i ) ≥ ℓ ( B i [ J − ( a / N ) J 2 ] B i ) = Δ s i . (65) \ell(B_iJq(J)B_i)\ge\ell\bigl(B_i[J-(a/N)J^2]B_i\bigr)=\Delta s_i. \tag*{(65)} ℓ ( B i J q ( J ) B i ) ≥ ℓ ( B i [ J − ( a / N ) J 2 ] B i ) = Δ s i . (65)
The operator A i A_i A i is a projector and A i B i A_iB_i A i B i has the same pairings as J B i JB_i J B i , so the overlap is
⟨ A i B i , F i B i ⟩ ℓ = ⟨ A i B i , q ( J ) B i ⟩ ℓ = ⟨ J B i , q ( J ) B i ⟩ ℓ = ℓ ( B i J q ( J ) B i ) . (66) \langle A_iB_i,F_iB_i\rangle_\ell=\langle A_iB_i,q(J)B_i\rangle_\ell=\langle JB_i,q(J)B_i\rangle_\ell=\ell(B_iJq(J)B_i). \tag*{(66)} ⟨ A i B i , F i B i ⟩ ℓ = ⟨ A i B i , q ( J ) B i ⟩ ℓ = ⟨ J B i , q ( J ) B i ⟩ ℓ = ℓ ( B i J q ( J ) B i ) . (66)
Since ∥ A i B i ∥ ℓ 2 = s i \lVert A_iB_i\rVert_\ell^2=s_i ∥ A i B i ∥ ℓ 2 = s i , Cauchy–Schwarz gives ∥ F i B i ∥ ℓ 2 ≥ Δ 2 s i \lVert F_iB_i\rVert_\ell^2\ge\Delta^2s_i ∥ F i B i ∥ ℓ 2 ≥ Δ 2 s i when s i > 0 s_i>0 s i > 0 . The bound also holds at s i = 0 s_i=0 s i = 0 by positivity. Cross-party commutation gives ∥ F i ∥ ℓ 2 = ∥ F i B i ∥ ℓ 2 + ∥ F i ( 1 − B i ) ∥ ℓ 2 \lVert F_i\rVert_\ell^2=\lVert F_iB_i\rVert_\ell^2+\lVert F_i(1-B_i)\rVert_\ell^2 ∥ F i ∥ ℓ 2 = ∥ F i B i ∥ ℓ 2 + ∥ F i ( 1 − B i ) ∥ ℓ 2 , with all degrees at most d + 2 d+2 d + 2 . Summing and using Eq. (61) gives
Δ 2 ∑ i s i ≤ ∑ i ∥ F i ∥ ℓ 2 = ℓ ( J q ( J ) 2 ) ≤ N / K 2 . (67) \Delta^2\sum_i s_i\le\sum_i\lVert F_i\rVert_\ell^2=\ell(Jq(J)^2)\le N/K^2. \tag*{(67)} Δ 2 i ∑ s i ≤ i ∑ ∥ F i ∥ ℓ 2 = ℓ ( J q ( J ) 2 ) ≤ N / K 2 . (67)
Dividing by Δ 2 \Delta^2 Δ 2 gives Eq. (58) .
Loss of positivity at higher degree
For large enough N N N , the functional in Eq. (18) takes a negative value on a square beyond the tested degree. The term from the character can be negative because the norm of the reference vector grows with N N N . We choose a polynomial that keeps this term fixed while reducing the contribution from the reference vector. Let J = ∑ i A i J=\sum_i A_i J = ∑ i A i in the reference representation and put f m = ( 1 − J / N ) m f_m=(1-J/N)^m f m = ( 1 − J / N ) m for a positive integer m m m . The character sends J J J to zero, so ε ( f m ) = 1 \varepsilon(f_m)=1 ε ( f m ) = 1 . On positive eigenvalues of J J J , increasing m m m attenuates the corresponding component of R N R_N R N .
It suffices to quantify the attenuation in the tensor-product block. There J J J acts on Alice’s factor as ∑ i ∣ u i ⟩ ⟨ u i ∣ \sum_i |u_i\rangle\langle u_i| ∑ i ∣ u i ⟩ ⟨ u i ∣ . If U U U has columns u i u_i u i , then U U ∗ UU^* U U ∗ and U ∗ U U^*U U ∗ U have the same nonzero eigenvalues. The latter is the Gram matrix ( X i j ) i , j = 1 N + I N / 2 (X_{ij})_{i,j=1}^N + I_N/2 ( X ij ) i , j = 1 N + I N /2 , where I N I_N I N is the N N N -dimensional identity matrix. The common directions give the positive semidefinite first term and the private directions give I N / 2 I_N/2 I N /2 , so the nonzero eigenvalues are at least 1 / 2 1/2 1/2 . They are at most N N N because ∥ A i ∥ ≤ 1 \lVert A_i\rVert\le1 ∥ A i ∥ ≤ 1 . To bound the reference weight supported on those eigenvalues, let Π \Pi Π project onto the span of the u i u_i u i on Alice’s factor. Each unit vector u i u_i u i lies in the span, so ∥ Π e i ∥ ≥ ∣ ⟨ u i , e i ⟩ ∣ = 1 / 2 \lVert\Pi e_i\rVert\ge|\langle u_i,e_i\rangle| = 1/\sqrt{2} ∥ Π e i ∥ ≥ ∣ ⟨ u i , e i ⟩ ∣ = 1/ 2 . The f i f_i f i on Bob’s factor are orthonormal, giving
∥ ( Π ⊗ I ) R 0 ∥ 2 = 4 ∑ i ∥ Π e i ∥ 2 ≥ 2 N . \lVert(\Pi\otimes I)R_0\rVert^2 = 4\sum_i \lVert\Pi e_i\rVert^2 \ge2N. ∥( Π ⊗ I ) R 0 ∥ 2 = 4 i ∑ ∥ Π e i ∥ 2 ≥ 2 N .
On this subspace, the squared operator norm of f m f_m f m is at most ( 1 − 1 / ( 2 N ) ) 2 m (1-1/(2N))^{2m} ( 1 − 1/ ( 2 N ) ) 2 m . On the full reference space f m f_m f m is a contraction because 0 ≤ J ≤ N I 0 \le J \le NI 0 ≤ J ≤ N I . Thus ∥ f m R N ∥ 2 \lVert f_mR_N\rVert^2 ∥ f m R N ∥ 2 is smaller than ∥ R N ∥ 2 \lVert R_N\rVert^2 ∥ R N ∥ 2 by at least 2 N [ 1 − ( 1 − 1 / ( 2 N ) ) 2 m ] 2N[1-(1-1/(2N))^{2m}] 2 N [ 1 − ( 1 − 1/ ( 2 N ) ) 2 m ] . Substituting this estimate and ε ( f m ∗ f m ) = 1 \varepsilon(f_m^*f_m)=1 ε ( f m ∗ f m ) = 1 in Eq. (18) gives
ℓ ( f m ∗ f m ) ≤ 1 − 2 N C L [ 1 − ( 1 − 1 2 N ) 2 m ] . (68) \ell(f_m^*f_m) \le1-\frac{2N}{C_L}\left[1-\left(1-\frac{1}{2N}\right)^{2m}\right]. \tag*{(68)} ℓ ( f m ∗ f m ) ≤ 1 − C L 2 N [ 1 − ( 1 − 2 N 1 ) 2 m ] . (68)
For N > C L / 2 N>C_L/2 N > C L /2 , choose m > L m>L m > L sufficiently large to make this bound negative. This square lies beyond those tested by level L L L . At fixed N N N , Eq. (57) bounds the common certificate rate by 1 / N 1/N 1/ N at level N N N .
Fix an integer NPA level L ≥ 1 L \ge1 L ≥ 1 and an integer K ≥ 1 K \ge1 K ≥ 1 . We construct a binary-outcome correlation at level L L L with N N N settings per party for which any choice of at most K K K settings on each side admits a local hidden-variable model. For N ≥ max { 4 , K + 1 } N \ge\max\{4,K+1\} N ≥ max { 4 , K + 1 } , every joint outcome can have probability at least 1 / ( 2 N ) 1/(2N) 1/ ( 2 N ) , and the information score with one use of the full correlation and one classical bit grows without bound as N N N increases at fixed L L L and K K K .
Consider a binary-outcome correlation p s p_s p s on settings x , y ∈ { 1 , … , N } x,y \in\{1,\ldots,N\} x , y ∈ { 1 , … , N } with joint zero probability s δ x y s\delta_{xy} s δ x y and both zero-outcome marginals m s ms m s . Here δ x y \delta_{xy} δ x y is the Kronecker delta, and s ≥ 0 s \ge0 s ≥ 0 and m ≥ 1 m \ge1 m ≥ 1 are such that p s p_s p s is a valid correlation. The certificate in Eq. (21) has m = 3 m=3 m = 3 . Let X X X and Y Y Y be the nonempty sets of labels retained by Alice and Bob, respectively, and write c = ∣ X ∩ Y ∣ c=|X\cap Y| c = ∣ X ∩ Y ∣ for the number of common labels. In a deterministic local strategy, let U ⊆ X U\subseteq X U ⊆ X and W ⊆ Y W\subseteq Y W ⊆ Y be the sets on which Alice and Bob output zero. A strategy of positive weight with both sets nonempty must have U = W = { j } U=W=\{j\} U = W = { j } for some j ∈ X ∩ Y j\in X\cap Y j ∈ X ∩ Y . Otherwise it would assign a joint zero to a pair of unequal settings. This classification of strategies follows the argument of Gazi et al. [10 ] for their almost-quantum example. At each common label j j j the joint zero probability fixes the weight of the corresponding singleton strategy to s s s .
The singleton strategies use weight c s cs cs and supply a zero-outcome marginal s s s at each common label. Alice’s remaining marginal is ( m − 1 ) s (m-1)s ( m − 1 ) s at common labels and m s ms m s at labels in X ∖ Y X\setminus Y X ∖ Y . It must be supplied by strategies with U ≠ ∅ U\ne\varnothing U = ∅ and W = ∅ W=\varnothing W = ∅ , in which Bob always outputs one. They need weight at least Alice’s largest remaining marginal, s [ m − 1 + 1 X ∖ Y ≠ ∅ ] s[m-1+\mathbf{1}_{X\setminus Y\ne\varnothing}] s [ m − 1 + 1 X ∖ Y = ∅ ] , where 1 E \mathbf{1}_E 1 E equals one when condition E E E holds and zero otherwise. Bob’s one-sided strategies, with U = ∅ U=\varnothing U = ∅ and W ≠ ∅ W\ne\varnothing W = ∅ , need at least the weight obtained by exchanging X X X and Y Y Y . The three classes are disjoint, so locality requires
s [ c + 2 ( m − 1 ) + 1 X ∖ Y ≠ ∅ + 1 Y ∖ X ≠ ∅ ] ≤ 1. (69) s\left[c+2(m-1)+\mathbf{1}_{X\setminus Y\ne\varnothing}+\mathbf{1}_{Y\setminus X\ne\varnothing}\right]\le1. \tag*{(69)} s [ c + 2 ( m − 1 ) + 1 X ∖ Y = ∅ + 1 Y ∖ X = ∅ ] ≤ 1. (69)
When this inequality holds, assign weight s s s to each singleton and give each one-sided class exactly the weight equal to its largest remaining marginal. For a class of positive weight, the active party outputs zero at a given setting when a uniform random variable on [ 0 , 1 ] [0,1] [ 0 , 1 ] lies below the remaining marginal for that setting divided by the class weight. A single draw thus specifies a deterministic response at every setting in the class. Omit any class of zero weight and assign the unused probability to the strategy in which both parties always output one. The constructed model reproduces the marginals and joint zero probabilities, which determine all four binary outcome probabilities. Equation (S56) is therefore necessary and sufficient.
For m = 3 m = 3 m = 3 , the rate that makes every restriction local is determined by the largest bracket in Eq. (69) over ∣ X ∣ , ∣ Y ∣ ≤ K |X|, |Y| \le K ∣ X ∣ , ∣ Y ∣ ≤ K . If the sets are identical, the bracket is at most K + 4 K + 4 K + 4 . Distinct sets have at most K − 1 K - 1 K − 1 common labels and can contribute at most two further units from the indicators. For 1 ≤ K < N 1 \le K < N 1 ≤ K < N , two K K K -element sets differing in one label attain the resulting maximum K + 5 K + 5 K + 5 . Thus all these restrictions are local exactly when s ≤ 1 / ( K + 5 ) s \le1/(K + 5) s ≤ 1/ ( K + 5 ) .
To keep the diluted correlation at level L L L and meet the locality condition, set L ′ = max { 2 , L } L' = \max\{2, L\} L ′ = max { 2 , L } , D = max { 185 ( L ′ ) 3 , K + 5 } D = \max\{185(L')^3, K + 5\} D = max { 185 ( L ′ ) 3 , K + 5 } , and s = 1 / D s = 1/D s = 1/ D . For N ≥ K + 1 N \ge K + 1 N ≥ K + 1 , mix the level-L ′ L' L ′ certificate of rate s L ′ > 1 / [ 185 ( L ′ ) 3 ] s_{L'} > 1/[185(L')^3] s L ′ > 1/ [ 185 ( L ′ ) 3 ] with the deterministic correlation returning ( 1 , 1 ) (1, 1) ( 1 , 1 ) , giving the certificate weight s / s L ′ s/s_{L'} s / s L ′ . The joint zero probability and the zero-outcome marginals are reduced in the same proportion, so the resulting correlation is p s p_s p s with m = 3 m = 3 m = 3 . Convexity and nesting give p s ∈ Q L ( N , N , 2 , 2 ) p_s \in Q_L(N, N, 2, 2) p s ∈ Q L ( N , N , 2 , 2 ) , and the bound on s s s gives locality for all prescribed restrictions. The first-one protocol in Sec. S2.2, with independent database bits equal to one with probability 1 / N 1/N 1/ N , gives a score of at least ( 1 − e − 1 ) s log 2 N (1 - e^{-1})s \log_2 N ( 1 − e − 1 ) s log 2 N by Eq. (36) .
To give every joint outcome positive probability while keeping joint zeros rare on unequal settings, let U N U_N U N be the setting-independent local product correlation in which Alice and Bob each output zero with probability N − 1 / 2 N^{-1/2} N − 1/2 . Supply the parties with q = ( p s + U N ) / 2 q = (p_s + U_N)/2 q = ( p s + U N ) /2 without disclosing which component was drawn. For N ≥ max { 4 , K + 1 } N \ge\max\{4, K + 1\} N ≥ max { 4 , K + 1 } , zero is each party’s less probable outcome, possibly tied with one. Hence the smallest product probability is the joint zero probability 1 / N 1/N 1/ N , and q ( a , b ∣ x , y ) ≥ 1 / ( 2 N ) q(a, b \mid x, y) \ge1/(2N) q ( a , b ∣ x , y ) ≥ 1/ ( 2 N ) for each outcome pair a , b ∈ { 0 , 1 } a, b \in\{0, 1\} a , b ∈ { 0 , 1 } and setting pair x , y x, y x , y . The mixture remains at level L L L , and every prescribed restriction remains local because U N U_N U N itself is local.
Use the first-one protocol on q q q with the same database bias. Alice sends her outcome at the index of the first one, or sends one if her database consists of zeros. For a request i i i , Bob uses setting i i i and raises the flag G i = 1 G_i = 1 G i = 1 exactly when both his outcome and Alice’s message are zero. Let R i R_i R i be the requested bit and A N = 1 − ( 1 − 1 / N ) N A_N = 1 - (1 - 1/N)^N A N = 1 − ( 1 − 1/ N ) N the probability that the database contains a one. Write v i = Pr ( G i = 1 ) v_i = \Pr(G_i = 1) v i = Pr ( G i = 1 ) for the flag probability and w i = Pr ( G i = 1 , R i = 1 ) w_i = \Pr(G_i = 1, R_i = 1) w i = Pr ( G i = 1 , R i = 1 ) for the probability of a flag on a bit that is one. In the p s p_s p s component, a flag occurs with probability s s s when the requested index is the first one, and every such flag certifies R i = 1 R_i = 1 R i = 1 . In the U N U_N U N component, each request has flag probability 1 / N 1/N 1/ N conditional on the database containing a one. The first-one index, when it exists, is unique, so summing these contributions over requests gives
∑ i = 1 N w i ≥ s A N 2 , ∑ i = 1 N v i = ( s + 1 ) A N 2 ≤ 1. \sum_{i=1}^{N} w_i \ge\frac{s A_N}{2}, \qquad\sum_{i=1}^{N} v_i = \frac{(s+1)A_N}{2} \le1. i = 1 ∑ N w i ≥ 2 s A N , i = 1 ∑ N v i = 2 ( s + 1 ) A N ≤ 1.
To bound the information in a flag, compare the conditional one-probability w i / v i w_i/v_i w i / v i with the prior 1 / N 1/N 1/ N . Write Ber ( t ) \operatorname{Ber}(t) Ber ( t ) for the Bernoulli law with one-probability t ∈ [ 0 , 1 ] t \in[0,1] t ∈ [ 0 , 1 ] , h 2 ( t ) h_2(t) h 2 ( t ) for its entropy in bits, and D K L D_{\mathrm{KL}} D KL for the relative entropy in bits. The relative entropy of the posterior from the prior can be bounded using h 2 ( t ) ≤ 1 h_2(t) \le1 h 2 ( t ) ≤ 1 ,
D K L ( Ber ( t ) ∥ Ber ( 1 / N ) ) = t log 2 N + ( 1 − t ) log 2 1 1 − 1 / N − h 2 ( t ) ≥ t log 2 N − 1. D_{\mathrm{KL}}\bigl(\operatorname{Ber}(t)\mathbin{\|}\operatorname{Ber}(1/N)\bigr) = t \log_2 N + (1-t)\log_2 \frac{1}{1 - 1/N} - h_2(t) \ge t \log_2 N - 1. D KL ( Ber ( t ) ∥ Ber ( 1/ N ) ) = t log 2 N + ( 1 − t ) log 2 1 − 1/ N 1 − h 2 ( t ) ≥ t log 2 N − 1.
The flag contributes this relative entropy at t = w i / v i t = w_i/v_i t = w i / v i , weighted by v i v_i v i . The outcome G i = 0 G_i = 0 G i = 0 has a nonnegative contribution, so I ( R i : G i ) ≥ w i log 2 N − v i I(R_i : G_i) \ge w_i \log_2 N - v_i I ( R i : G i ) ≥ w i log 2 N − v i . Summing over requests and using A N ≥ 1 − e − 1 A_N \ge1 - e^{-1} A N ≥ 1 − e − 1 gives
∑ i = 1 N I ( R i : G i ) ≥ ( 1 − e − 1 ) log 2 N 2 max { 185 ( L ′ ) 3 , K + 5 } − 1. \sum_{i=1}^{N} I(R_i : G_i) \ge\frac{(1 - e^{-1})\log_2 N}{2\max\{185(L')^3, K + 5\}} - 1. i = 1 ∑ N I ( R i : G i ) ≥ 2 max { 185 ( L ′ ) 3 , K + 5 } ( 1 − e − 1 ) log 2 N − 1.
For N ≥ max { 4 , K + 1 } N \ge\max\{4, K + 1\} N ≥ max { 4 , K + 1 } this bound exceeds any target V ≥ 0 V \ge0 V ≥ 0 once log 2 N > 2 D ( V + 1 ) / ( 1 − e − 1 ) \log_2 N > 2D(V + 1)/(1 - e^{-1}) log 2 N > 2 D ( V + 1 ) / ( 1 − e − 1 ) . It also diverges when L = o ( ( log N ) 1 / 3 ) L = o((\log N)^{1/3}) L = o (( log N ) 1/3 ) and K = o ( log N ) K = o(\log N) K = o ( log N ) simultaneously. A score above one certifies that the full correlation is Bell nonlocal, since a local hidden-variable model gives the classical one-bit bound of Eq. (34) .