Introduction
Quantum theory allows distant observers to share correlations that no classical common cause can explain, and these correlations are a resource for information processing. Shared entanglement can reduce the communication needed to compute distributed functions [1 , 2 ] , in some cases exponentially [3 , 4 , 5 ] . The origin of this advantage is Bell nonlocality [6 , 7 , 8 , 9 ] : correlations that admit a local hidden-variable model can be simulated with shared randomness, whereas violations of Bell inequalities can be converted into communication protocols that outperform every classical one [2 , 10 ] . Quantum theory, however, does not exhaust the correlations compatible with relativistic causality, and stronger correlations would be more powerful still. Popescu–Rohrlich (PR) boxes [11 , 12 ] , for example, would make communication complexity trivial [13 , 14 , 15 ] . Observations of this kind have motivated a long-standing programme to identify physical or information-theoretic principles that rule out supra-quantum correlations and, ideally, single out the quantum set. Prominent candidates include nontrivial communication complexity [14 ] , no advantage for nonlocal computation [16 ] , information causality [17 , 18 , 19 ] , macroscopic locality [20 ] and local orthogonality [21 ] .
Almost-quantum (AQ) correlations [22 ] are the most demanding test case for this programme. They form the “1 + A B 1 + AB 1 + A B ” Level of the Navascués–Pironio–Acín (NPA) hierarchy [23 , 24 ] , a set that strictly contains the quantum set yet is characterized by a single semidefinite program. AQ correlations have been proved to satisfy nontrivial communication complexity, no advantage for nonlocal computation, macroscopic locality and local orthogonality [22 ] , and numerical evidence suggested that they also satisfy information causality [22 ] . They also arise outside the Hilbert-space formalism. In Sorkin’s quantum measure theory [25 ] , a histories-based generalization of quantum mechanics, strongly positive decoherence functionals yield correlations lying between the AQ set and NPA Level 1, and exactly the AQ set when later measurements may depend on earlier outcomes [26 ] . The AQ set also follows from a principle of macroscopic noncontextuality [27 ] . Bipartite principles may in any case be insufficient to recover the quantum set [28 ] , and the known arguments that exclude AQ correlations, based on Specker’s principle in contextuality scenarios [29 ] and on the no-restriction hypothesis for generalized probabilistic theories [30 ] , rely on structure beyond correlations in Bell scenarios. Within Bell scenarios, none of the principles listed above other than information causality is known to exclude AQ correlations; that information causality does so, with the AQ boxes constructed here, is shown in a companion work [31 ] (see the Note added at the end of § 9 ). Is the difference between AQ and quantum correlations then also negligible in operational terms?
Here we show that it is not. We consider a simple communication task. Alice and Bob each receive one of N N N labels, Alice sends a single bit to Bob, and Bob must decide whether their labels coincide; he may abstain, but he must never be wrong. The figure of merit is the worst-case probability that Bob answers conclusively. We prove that, for every N ≥ 3 N \ge3 N ≥ 3 , no quantum strategy exceeds 1 / N 1/N 1/ N , the value already attained with shared randomness. This holds for finite- and infinite-dimensional entanglement alike, and also in the commuting-operator framework of quantum field theory. In contrast, an explicit family of AQ correlations, one for each N N N , achieves 1 / 19 1/19 1/19 , so the ratio between AQ and quantum performance grows without bound. For certificates of equality obtained from binary-outcome boxes, we determine the optimal AQ performance exactly: it exceeds the quantum value precisely when N ≥ 9 N \ge9 N ≥ 9 and tends to 1 / 17 1/17 1/17 as N N N grows. The gap persists for longer messages. Entanglement never saves more than one bit over shared randomness, whereas AQ correlations reduce the one-way zero-error cost of deciding whether two n n n -bit strings are equal, with abstention probability at most 1 / 2 1/2 1/2 on every input pair, from n n n bits to at most 13.
The quantum bound also yields an exact-zero (face) witness of post-quantumness: a linear inequality that holds for all commuting-operator correlations on a face of the nonsignalling polytope, namely for boxes with prescribed vanishing entries, and that our AQ correlations violate by a factor growing linearly with N N N . For tensor-product models, the inequality underlying this witness, as well as linear lower bounds on entanglement-assisted one-sided-error and zero-error communication for equality, were obtained earlier by Klauck and de Wolf [32 ] ; Appendix § 11 compares their results with ours in detail. Our contributions on the quantum side are the exact one-bit value 1 / N 1/N 1/ N , its refinement for longer messages and the extension of both to commuting operators.
The separation arises exactly at the boundary between the commuting-operator set and the AQ set. These differ only in whether Alice’s and Bob’s operators commute as operator identities or merely when acting on the shared state. Our quantum bound rests on a sequential-measurement argument that requires Bob’s operators to commute with products of Alice’s operators. The AQ condition guarantees commutation only for single operators acting on the state, and the correlations we construct exploit precisely this freedom.
The task also separates the AQ set from the next level of the NPA hierarchy. Level 1, the set C V e c C_{\mathrm{Vec}} C Vec of vector correlations, contains the AQ set and coincides with the set singled out by macroscopic locality [20 ] . Its defining semidefinite constraint involves only the vectors ψ \psi ψ , A a ∣ x ψ A_{a|x}\psi A a ∣ x ψ and B b ∣ y ψ B_{b|y}\psi B b ∣ y ψ , whereas that of the 1 + A B 1+\mathrm{AB} 1 + AB level also involves the vectors A a ∣ x B b ∣ y ψ A_{a|x}B_{b|y}\psi A a ∣ x B b ∣ y ψ . For C V e c C_{\mathrm{Vec}} C Vec we determine the optimal certificate of equality from binary-outcome boxes in closed form. It equals N / [ 8 ( N − 2 ) ] N/[8(N-2)] N / [ 8 ( N − 2 )] for every N ≥ 4 N \ge4 N ≥ 4 , exceeds the quantum value precisely when N ≥ 5 N \ge5 N ≥ 5 , and decreases to 1 / 8 1/8 1/8 , more than twice the AQ limit 1 / 17 1/17 1/17 . The proof is elementary: the upper bound follows from the nonnegativity of two squared norms, and an explicit realization in N + 1 N+1 N + 1 dimensions attains it. Since the level-1 optimum exceeds the AQ optimum for every N ≥ 5 N \ge5 N ≥ 5 , the optimal level-1 boxes form an explicit family in C V e c ∖ C A Q C_{\mathrm{Vec}} \setminus C_{\mathrm{AQ}} C Vec ∖ C AQ , and thus separate the two sets analytically in an operational task. Macroscopic locality alone therefore permits certificates of equality approaching 1 / 8 1/8 1/8 , and the constraints that distinguish the 1 + A B 1+\mathrm{AB} 1 + AB level from Level 1 lower this limit to 1 / 17 1/17 1/17 . Combined with the classical certificate of inequality, level-1 correlations also solve the one-bit task with worst-case probability N / ( 10 N − 16 ) > 1 / 10 N/(10N-16) > 1/10 N / ( 10 N − 16 ) > 1/10 for every N ≥ 4 N \ge4 N ≥ 4 .
The paper is organized as follows. § 2 defines the correlation models and records two closure properties of the AQ set, and § 3 introduces the communication task. § 4 proves the packing lemma, the quantum sum rule and the value 1 / N 1/N 1/ N for all quantum models. § 5 constructs the AQ boxes p ⋆ p^\star p ⋆ , reduces AQ membership on the relevant face of the nonsignalling polytope to a condition on vectors with prescribed inner products, and determines the optimal AQ certificate of equality. § 6 derives the exact-zero witness and determines when p ⋆ p^\star p ⋆ is local, and § 7 treats longer messages and communication cost. § 8 determines the optimal certificate of equality at Level 1 of the NPA hierarchy and uses it to separate this level from the AQ set. § 9 discusses the results and open questions, and Appendix § 10 gives an explicit local model for p ⋆ p^\star p ⋆ . Appendix § 11 compares our quantum bounds with the earlier work of Klauck and de Wolf [32 ] . Table 1 summarizes the results: it separates the quantities that are determined exactly from those for which only bounds are known, and lists the values of N N N from which each construction takes effect.
Table 1. Table 1. Summary of the results. Upper part: the efficiencies studied, and what is known about each. Lower part: the smallest N N N from which each explicit construction takes effect. Here η Q ( N ) = 1 / N \eta_{\mathrm{Q}}(N)=1/N η Q ( N ) = 1/ N is the common value of all quantum models.
Correlation models
Consider two spacelike-separated laboratories that share a source. In each round, Alice chooses a measurement setting x ∈ X x \in\mathcal{X} x ∈ X and records an outcome a ∈ A a \in\mathcal{A} a ∈ A ; Bob independently chooses y ∈ Y y \in\mathcal{Y} y ∈ Y and records b ∈ B b \in\mathcal{B} b ∈ B . All four alphabets are finite. Repeating the experiment produces the behaviour (or box ) p = { p ( a , b ∣ x , y ) } \mathbf{p} = \{p(a,b|x,y)\} p = { p ( a , b ∣ x , y )} , with p ( a , b ∣ x , y ) ≥ 0 p(a,b|x,y) \ge0 p ( a , b ∣ x , y ) ≥ 0 and ∑ a , b p ( a , b ∣ x , y ) = 1 \sum_{a,b} p(a,b|x,y) = 1 ∑ a , b p ( a , b ∣ x , y ) = 1 . Throughout, x , y x,y x , y denote box settings and a , b a,b a , b box outcomes; the inputs of the communication task are denoted by s , t s,t s , t . The data alone do not fix a physical model of the source and the devices, and different assumptions about the two laboratories lead to different sets of admissible behaviours [33 , 34 , 35 , 36 ] . The sets relevant here are defined as follows.
Alice’s measurements are denoted { A a ∣ x } a \{A_{a|x}\}_a { A a ∣ x } a and Bob’s { B b ∣ y } b \{B_{b|y}\}_b { B b ∣ y } b . In the Hilbert-space models below they are projective, A a ∣ x = A a ∣ x † = A a ∣ x 2 A_{a|x}=A_{a|x}^{\dagger}=A_{a|x}^{2} A a ∣ x = A a ∣ x † = A a ∣ x 2 and ∑ a A a ∣ x = I \sum_a A_{a|x}=\mathbb{I} ∑ a A a ∣ x = I , and likewise for Bob. For C q C_{\mathrm{q}} C q and C q c C_{\mathrm{q c}} C qc , allowing general POVMs gives the same sets, by Naimark dilation in the first case and by a less elementary argument in the second [36 ] .
[ C L ] [\mathrm{C}_{\mathrm{L}}] [ C L ] Local hidden variables. Alice’s and Bob’s outcomes are spacelike separated. Reichenbach’s common-cause principle [37 ] then requires that their correlation be explained by a common cause λ \lambda λ emitted by the source, and that conditioning on λ \lambda λ screen the outcomes off from each other, p ( a , b ∣ x , y , λ ) = p A ( a ∣ x , λ ) p B ( b ∣ y , λ ) p(a,b|x,y,\lambda)=p_{\mathrm{A}}(a|x,\lambda)p_{\mathrm{B}}(b|y,\lambda) p ( a , b ∣ x , y , λ ) = p A ( a ∣ x , λ ) p B ( b ∣ y , λ ) . In addition, the settings are assumed to be chosen independently of λ \lambda λ . Together these yield Bell’s local-causality condition [6 , 38 ] , p ( a , b ∣ x , y ) = p(a,b|x,y)= p ( a , b ∣ x , y ) = ∑ λ q ( λ ) p A ( a ∣ x , λ ) p B ( b ∣ y , λ ) \sum_{\lambda}q(\lambda)\,p_{\mathrm{A}}(a|x,\lambda)\,p_{\mathrm{B}}(b|y,\lambda) ∑ λ q ( λ ) p A ( a ∣ x , λ ) p B ( b ∣ y , λ ) . Quantum violations of this condition admit no classical causal explanation without fine-tuning [39 ] .
[Cq] Finite-dimensional quantum. Alice’s and Bob’s systems have finite-dimensional Hilbert spaces H A \mathcal{H}_{\mathrm{A}} H A and H B \mathcal{H}_{\mathrm{B}} H B . The source prepares a unit vector ψ ∈ H A ⊗ H B \psi\in\mathcal{H}_{\mathrm{A}}\otimes\mathcal{H}_{\mathrm{B}} ψ ∈ H A ⊗ H B , and p ( a , b ∣ x , y ) = ⟨ ψ , ( A a ∣ x ⊗ B b ∣ y ) ψ ⟩ p(a,b|x,y)=\langle\psi,(\mathsf{A}_{a|x}\otimes\mathsf{B}_{b|y})\psi\rangle p ( a , b ∣ x , y ) = ⟨ ψ , ( A a ∣ x ⊗ B b ∣ y ) ψ ⟩ . Mixed states give nothing new, since they can be purified in a larger finite-dimensional space.
[Cqs] Spatial quantum. As C q \mathrm{C}_{\mathrm{q}} C q , but H A \mathcal{H}_{\mathrm{A}} H A and H B \mathcal{H}_{\mathrm{B}} H B may be infinite dimensional.
[Cqa] Approximately quantum. The closure C q ‾ = C q s \overline{\mathrm{C}_{\mathrm{q}}}=\mathrm{C}_{\mathrm{qs}} C q = C qs : behaviours that can be approximated to arbitrary precision by finite-dimensional quantum experiments.
[Cqc] Commuting-operator quantum. The two laboratories are not assumed to be tensor factors. Instead there is a single Hilbert space H \mathcal{H} H , a unit vector ψ ∈ H \psi\in\mathcal{H} ψ ∈ H , and Alice’s and Bob’s observables commute as operators, [ A a ∣ x , B b ∣ y ] = 0 [\mathsf{A}_{a|x},\mathsf{B}_{b|y}]=0 [ A a ∣ x , B b ∣ y ] = 0 , with p ( a , b ∣ x , y ) = ⟨ ψ , A a ∣ x B b ∣ y ψ ⟩ p(a,b|x,y)=\langle\psi,\mathsf{A}_{a|x}\mathsf{B}_{b|y}\psi\rangle p ( a , b ∣ x , y ) = ⟨ ψ , A a ∣ x B b ∣ y ψ ⟩ . This is how locality is encoded in algebraic quantum field theory, where observables localized in spacelike-separated regions commute [40 ] .
[CAQ] Almost quantum. As C q c \mathrm{C}_{\mathrm{qc}} C qc , but commutation is required only on the state prepared by the source:
Definition 1 (Almost-quantum correlations [22 ] ). A behaviour p p p belongs to C A Q \mathrm{C}_{\mathrm{AQ}} C AQ if there exist a Hilbert space H \mathcal{H} H , a unit vector ψ ∈ H \psi\in\mathcal{H} ψ ∈ H , and projective measurements { A a ∣ x } a \{\mathsf{A}_{a|x}\}_{a} { A a ∣ x } a , { B b ∣ y } b \{\mathsf{B}_{b|y}\}_{b} { B b ∣ y } b on H \mathcal{H} H such that, for all a , b , x , y a,b,x,y a , b , x , y ,
A a ∣ x B b ∣ y ψ = B b ∣ y A a ∣ x ψ and p ( a , b ∣ x , y ) = ⟨ ψ , A a ∣ x B b ∣ y ψ ⟩ . (1) \mathsf{A}_{a|x}\mathsf{B}_{b|y}\psi=\mathsf{B}_{b|y}\mathsf{A}_{a|x}\psi
\quad\text{and}\quad
p(a,b|x,y)=\langle\psi,\mathsf{A}_{a|x}\mathsf{B}_{b|y}\psi\rangle. \tag*{(1)} A a ∣ x B b ∣ y ψ = B b ∣ y A a ∣ x ψ and p ( a , b ∣ x , y ) = ⟨ ψ , A a ∣ x B b ∣ y ψ ⟩ . (1)
Thus C A Q \mathrm{C}_{\mathrm{AQ}} C AQ differs from C q c \mathrm{C}_{\mathrm{qc}} C qc only in that commutation is imposed on the state ψ \psi ψ rather than as an operator identity. Equivalently, C A Q \mathrm{C}_{\mathrm{AQ}} C AQ is Level 1 + AB of the NPA hierarchy, characterized by a single semidefinite program [22 ] .
[CVec] Vector correlations. There exist a unit vector ψ \psi ψ and vectors ξ a ∣ x , ζ b ∣ y \xi_{a|x},\zeta_{b|y} ξ a ∣ x , ζ b ∣ y in a real or complex Hilbert space such that ξ a ∣ x ⊥ ξ a ′ ∣ x \xi_{a|x} \perp\xi_{a'|x} ξ a ∣ x ⊥ ξ a ′ ∣ x for a ≠ a ′ a \ne a' a = a ′ , ζ b ∣ y ⊥ ζ b ′ ∣ y \zeta_{b|y} \perp\zeta_{b'|y} ζ b ∣ y ⊥ ζ b ′ ∣ y for b ≠ b ′ b \ne b' b = b ′ , ∑ a ξ a ∣ x = ψ = ∑ b ζ b ∣ y \sum_a \xi_{a|x}=\psi=\sum_b \zeta_{b|y} ∑ a ξ a ∣ x = ψ = ∑ b ζ b ∣ y , and p ( a , b ∣ x , y ) = ⟨ ξ a ∣ x , ζ b ∣ y ⟩ p(a,b|x,y)=\langle\xi_{a|x},\zeta_{b|y}\rangle p ( a , b ∣ x , y ) = ⟨ ξ a ∣ x , ζ b ∣ y ⟩ . This is Level 1 of the NPA hierarchy [23 ] , and it coincides with the set singled out by macroscopic locality [20 ] . The authors of Ref. [36 ] also call this set “almost quantum”; we follow Ref. [22 ] and reserve that name for C A Q C_{\mathrm{AQ}} C AQ .
[CNS] Nonsignalling. Neither party’s local statistics depend on the other party’s setting, as demanded by relativistic causality. That is, ∑ b p ( a , b ∣ x , y ) \sum_b p(a,b|x,y) ∑ b p ( a , b ∣ x , y ) does not depend on y y y and ∑ a p ( a , b ∣ x , y ) \sum_a p(a,b|x,y) ∑ a p ( a , b ∣ x , y ) does not depend on x x x ; these sums define the marginals p A ( a ∣ x ) p_A(a|x) p A ( a ∣ x ) and p B ( b ∣ y ) p_B(b|y) p B ( b ∣ y ) .
For every Bell scenario,
C L ⊆ C q ⊆ C q s ⊆ C q a ⊆ C q c ⊆ C A Q ⊆ C V e c ⊆ C N S , (2) C_{\mathrm{L}} \subseteq C_{\mathrm{q}} \subseteq C_{\mathrm{qs}} \subseteq C_{\mathrm{qa}} \subseteq C_{\mathrm{qc}} \subseteq C_{\mathrm{AQ}} \subseteq C_{\mathrm{Vec}} \subseteq C_{\mathrm{NS}}, \tag*{(2)} C L ⊆ C q ⊆ C qs ⊆ C qa ⊆ C qc ⊆ C AQ ⊆ C Vec ⊆ C NS , (2)
and these inclusions are known to be strict in some scenario. The inclusions (2) follow from the definitions. Tensor-product observables A ⊗ I A \otimes I A ⊗ I and I ⊗ B I \otimes B I ⊗ B commute, which gives C q s ⊆ C q c C_{\mathrm{qs}} \subseteq C_{\mathrm{qc}} C qs ⊆ C qc ; since C q c C_{\mathrm{qc}} C qc is closed [34 ] , also C q a ⊆ C q c C_{\mathrm{qa}} \subseteq C_{\mathrm{qc}} C qa ⊆ C qc . Commutation as an operator identity implies commutation on ψ \psi ψ , which gives C q c ⊆ C A Q C_{\mathrm{qc}} \subseteq C_{\mathrm{AQ}} C qc ⊆ C AQ . Given an AQ realization, the vectors ξ a ∣ x = A a ∣ x ψ \xi_{a|x}=A_{a|x}\psi ξ a ∣ x = A a ∣ x ψ and ζ b ∣ y = B b ∣ y ψ \zeta_{b|y}=B_{b|y}\psi ζ b ∣ y = B b ∣ y ψ form a vector realization, so C A Q ⊆ C V e c C_{\mathrm{AQ}} \subseteq C_{\mathrm{Vec}} C AQ ⊆ C Vec . Finally, ⟨ ξ a ∣ x , ∑ b ζ b ∣ y ⟩ = ∥ ξ a ∣ x ∥ 2 \langle\xi_{a|x},\sum_b\zeta_{b|y}\rangle=\|\xi_{a|x}\|^2 ⟨ ξ a ∣ x , ∑ b ζ b ∣ y ⟩ = ∥ ξ a ∣ x ∥ 2 does not depend on y y y , which gives C V e c ⊆ C N S C_{\mathrm{Vec}} \subseteq C_{\mathrm{NS}} C Vec ⊆ C NS . Each of the following inclusions is strict in some Bell scenario: C L ⊊ C q C_{\mathrm{L}} \subsetneq C_{\mathrm{q}} C L ⊊ C q by Bell’s theorem [6 ] ; C q ⊊ C q s C_{\mathrm{q}} \subsetneq C_{\mathrm{qs}} C q ⊊ C qs [41 ] ; C q s ⊊ C q a C_{\mathrm{qs}} \subsetneq C_{\mathrm{qa}} C qs ⊊ C qa , because C q s C_{\mathrm{qs}} C qs is not closed [42 ] ; C q a ⊊ C q c C_{\mathrm{qa}} \subsetneq C_{\mathrm{qc}} C qa ⊊ C qc , a negative answer to Tsirelson’s problem [33 , 43 ] , since equality in all scenarios is equivalent to Connes’ embedding conjecture [34 , 35 , 44 ] , which was refuted by M I P ∗ = R E \mathrm{MIP}^{*}=\mathrm{RE} MIP ∗ = RE [45 ] ; C q c ⊊ C A Q C_{\mathrm{qc}} \subsetneq C_{\mathrm{AQ}} C qc ⊊ C AQ [22 ] ; C A Q ⊊ C V e c C_{\mathrm{AQ}} \subsetneq C_{\mathrm{Vec}} C AQ ⊊ C Vec , for instance by the boxes of § 8 ; and C V e c ⊊ C N S C_{\mathrm{Vec}} \subsetneq C_{\mathrm{NS}} C Vec ⊊ C NS , because the PR box [11 ] violates the Tsirelson bound [46 ] , which already holds at NPA Level 1.
Two closure properties of C A Q C_{\mathrm{AQ}} C AQ are used below.
Lemma 1 (Closure properties of C A Q C_{\mathrm{AQ}} C AQ ). (i) C A Q C_{\mathrm{AQ}} C AQ is convex and contains C L C_{\mathrm{L}} C L ; in particular, mixing AQ boxes by means of shared randomness yields an AQ box. (ii) If p 1 , … , p r ∈ C A Q p_1,\ldots,p_r \in C_{\mathrm{AQ}} p 1 , … , p r ∈ C AQ , then the product box p ( a , b ∣ x , y ) = ∏ k = 1 r p k ( a k , b k ∣ x k , y k ) p(a,b|x,y)=\prod_{k=1}^{r}p_k(a_k,b_k|x_k,y_k) p ( a , b ∣ x , y ) = ∏ k = 1 r p k ( a k , b k ∣ x k , y k ) , in which each party holds one setting and one outcome for each factor, belongs to C A Q C_{\mathrm{AQ}} C AQ .
Proof. (i) Classical correlations are AQ by Eq. (2) . If ( ψ k , { A ( k ) } , { B ( k ) } ) (\psi_k,\{A^{(k)}\},\{B^{(k)}\}) ( ψ k , { A ( k ) } , { B ( k ) }) , k = 1 , 2 k=1,2 k = 1 , 2 , realize two AQ boxes, then the state w ψ 1 ⊕ 1 − w ψ 2 \sqrt{w}\,\psi_1\oplus\sqrt{1-w}\,\psi_2 w ψ 1 ⊕ 1 − w ψ 2 with block-diagonal projectors satisfies Eq. (1) and realizes their mixture with weights w w w and 1 − w 1-w 1 − w . (ii) If ( ψ k , { A a k ∣ x k ( k ) } , { B b k ∣ y k ( k ) } ) (\psi_k,\{A^{(k)}_{a_k|x_k}\},\{B^{(k)}_{b_k|y_k}\}) ( ψ k , { A a k ∣ x k ( k ) } , { B b k ∣ y k ( k ) }) , k = 1 , … , r k=1,\ldots,r k = 1 , … , r , realize AQ boxes, then ψ = ⨂ k ψ k \psi=\bigotimes_k\psi_k ψ = ⨂ k ψ k with the product projectors A a ∣ x = ⨂ k A a k ∣ x k ( k ) A_{a|x}=\bigotimes_k A^{(k)}_{a_k|x_k} A a ∣ x = ⨂ k A a k ∣ x k ( k ) and B b ∣ y = ⨂ k B b k ∣ y k ( k ) B_{b|y}=\bigotimes_k B^{(k)}_{b_k|y_k} B b ∣ y = ⨂ k B b k ∣ y k ( k ) realizes the product box, and
A a ∣ x B b ∣ y ψ = ⨂ k A a k ∣ x k ( k ) B b k ∣ y k ( k ) ψ k = ⨂ k B b k ∣ y k ( k ) A a k ∣ x k ( k ) ψ k = B b ∣ y A a ∣ x ψ . A_{a|x}B_{b|y}\psi=\bigotimes_k A^{(k)}_{a_k|x_k}B^{(k)}_{b_k|y_k}\psi_k=\bigotimes_k B^{(k)}_{b_k|y_k}A^{(k)}_{a_k|x_k}\psi_k=B_{b|y}A_{a|x}\psi. A a ∣ x B b ∣ y ψ = k ⨂ A a k ∣ x k ( k ) B b k ∣ y k ( k ) ψ k = k ⨂ B b k ∣ y k ( k ) A a k ∣ x k ( k ) ψ k = B b ∣ y A a ∣ x ψ .
Zero-error certification of equality
Alice and Bob each receive one of N ≥ 3 N \ge3 N ≥ 3 labels, s , t ∈ [ N ] = { 1 , … , N } s,t \in[N]=\{1,\ldots,N\} s , t ∈ [ N ] = { 1 , … , N } , and must decide whether they hold the same one; every pair ( s , t ) (s,t) ( s , t ) is allowed, and the target function is E Q N ( s , t ) = 1 { s = t } \mathrm{EQ}_N(s,t)=\mathbf{1}_{\{s=t\}} EQ N ( s , t ) = 1 { s = t } . Alice may send Bob a single classical bit M ∈ { 0 , 1 } M \in\{0,1\} M ∈ { 0 , 1 } , after which Bob must give an answer that is never wrong: he either certifies “equal” (G = 1 G=1 G = 1 ) or “different” (G = 0 G=0 G = 0 ) with certainty, or abstains (G = ? G=? G = ? ). Abstaining, the analogue of the inconclusive outcome in unambiguous state discrimination [47 , 48 , 49 ] , is always safe but uninformative, so the goal is to answer conclusively as often as possible on every input pair, equal and unequal alike (Figure 1 ).
Figure 1. Zero-error certification of equality with one bit. Alice and Bob receive s , t ∈ [ N ] s,t \in[N] s , t ∈ [ N ] and share a box p ∈ Ω p \in\Omega p ∈ Ω together with shared randomness λ \lambda λ . Alice chooses a setting x x x depending on s s s , obtains a a a , and sends one bit M M M to Bob. Bob chooses a setting y y y depending on t t t and M M M , obtains b b b , and outputs G ∈ { 0 , 1 , ? } G \in\{0,1,?\} G ∈ { 0 , 1 , ?} : G = 1 G=1 G = 1 certifies equality, G = 0 G=0 G = 0 certifies inequality and G = ? G=? G = ? denotes abstention. The protocol must never err, and its efficiency is the worst-case probability of a conclusive answer.
Definition 2 (Zero error and efficiency). A protocol has zero error if
Pr ( G ∉ { EQ N ( s , t ) , ? } ∣ s , t ) = 0 for all s , t ∈ [ N ] . (3) \Pr\left(G \notin\{\operatorname{EQ}_{N}(s,t),?\}\mid s,t\right)=0 \qquad\text{for all }s,t\in[N]. \tag*{(3)} Pr ( G ∈ / { EQ N ( s , t ) , ?} ∣ s , t ) = 0 for all s , t ∈ [ N ] . (3) For a set Ω \Omega Ω of correlations, the optimal efficiency is
η Ω ( N ) = sup zero-error protocols over Ω min s , t ∈ [ N ] Pr ( G ≠ ? ∣ s , t ) . (4) \eta_{\Omega}(N)=\sup_{\text{zero-error protocols over }\Omega}\ \min_{s,t\in[N]}\Pr(G\ne?\mid s,t). \tag*{(4)} η Ω ( N ) = zero-error protocols over Ω sup s , t ∈ [ N ] min Pr ( G = ? ∣ s , t ) . (4) The efficiency is the worst-case probability that Bob answers conclusively, and therefore correctly.
We write η C ≡ η C L \eta_{\mathrm{C}}\equiv\eta_{\mathrm{CL}} η C ≡ η CL (shared randomness), η Q ≡ η C q \eta_{\mathrm{Q}}\equiv\eta_{\mathrm{Cq}} η Q ≡ η Cq (shared entanglement) and η A Q ≡ η C A Q \eta_{\mathrm{AQ}}\equiv\eta_{\mathrm{CAQ}} η AQ ≡ η CAQ . In the quantum model, the parties share an arbitrary finite-dimensional state ρ A B \rho_{AB} ρ A B , perform arbitrary local operations and may keep quantum memory until after the message; no quantum system is communicated. To treat all sets of Eq. (2) on an equal footing, we formulate one-way protocols directly in terms of boxes. A protocol over Ω \Omega Ω uses a box p ∈ Ω p\in\Omega p ∈ Ω in which Alice’s setting is x = s x=s x = s and Bob’s setting is the pair y = ( t , m ) y=(t,m) y = ( t , m ) ; Alice obtains a a a and sends m = a m=a m = a , and Bob’s outcome is G G G . All sets in Eq. (2) are convex and closed under local classical post-processing, so shared randomness and local processing can be absorbed into p p p . Because p p p is nonsignalling, Alice’s outcome distribution does not depend on Bob’s setting, so letting Bob’s setting depend on m = a m=a m = a yields a normalized distribution,
Pr ( G ∣ s , t ) = ∑ a p ( a , G ∣ s , ( t , a ) ) . (5) \Pr(G\mid s,t)=\sum_a p(a,G\mid s,(t,a)). \tag*{(5)} Pr ( G ∣ s , t ) = a ∑ p ( a , G ∣ s , ( t , a )) . (5)
For Ω = C q \Omega=\mathrm{C}_{q} Ω = C q these are exactly the entanglement-assisted protocols, and for Ω = C q c \Omega=\mathrm{C}_{qc} Ω = C q c their commuting-operator counterparts. By construction, η Ω ( N ) \eta_{\Omega}(N) η Ω ( N ) is non-decreasing along the chain (2) .
Equality is the paradigmatic problem of communication complexity, the field introduced by Yao [50 ] . For n n n -bit inputs (N = 2 n N=2^n N = 2 n ), deterministic protocols require n + 1 n+1 n + 1 bits (in Yao’s model, communication is counted until both parties know the answer), whereas public-coin randomized protocols with bounded error need only O ( 1 ) O(1) O ( 1 ) bits [51 , 52 ] . Quantum resources reshape these costs in several models, from quantum fingerprinting [53 ] , which improves exponentially on the classical simultaneous-message cost of equality [54 , 55 ] , to the exponential entanglement-assisted saving for the distributed Deutsch–Jozsa problem [2 , 3 ] . Zero-error (Las Vegas) protocols [56 , 57 ] , which may abstain but never err, show a marked asymmetry: inequality has short certificates, whereas certifying equality requires n n n bits [51 ] . Prior entanglement does not remove this obstruction: entanglement-assisted one-sided-error and zero-error protocols for equality still require communication linear in n n n , even with interaction [32 ] . Our task differs from these settings in three respects: the channel is a single noiseless bit and the figure of merit is the worst-case probability of a conclusive answer; errors are forbidden altogether while abstention is unrestricted, with no promise on the inputs; and shared randomness is free, so the classical benchmark is the strongest public-coin model and entire sets of correlations are compared. In this regime the asymmetry noted above reappears sharply: inequality can be certified with probability 1 / 2 1/2 1/2 using shared randomness alone, whereas certifying equality is the bottleneck.
Quantum correlations offer no advantage
Our quantum bound rests on the following elementary lemma, a zero-error instance of the sequential-measurement technique underlying the gentle-measurement lemma and quantum union bounds [58 , 59 , 60 , 61 ] : a test that is certain to fail on a state leaves that state undisturbed [62 ] . Here T ≥ 0 T \ge0 T ≥ 0 means that T T T is positive semidefinite, T ≤ R T \le R T ≤ R means R − T ≥ 0 R-T \ge0 R − T ≥ 0 , and an effect is an operator 0 ≤ F ≤ I 0 \le F \le I 0 ≤ F ≤ I .
Lemma 2 (Packing). Let R R R be a positive trace-class operator, T 1 , … , T N T_1,\ldots,T_N T 1 , … , T N positive operators and F 1 , … , F N F_1,\ldots,F_N F 1 , … , F N effects such that T i ≤ R T_i \le R T i ≤ R for all i i i and F j T i = 0 F_jT_i=0 F j T i = 0 whenever j < i j<i j < i . Then ∑ i tr ( F i T i ) ≤ tr R \sum_i \operatorname{tr}(F_iT_i) \le\operatorname{tr} R ∑ i tr ( F i T i ) ≤ tr R .
Proof. Each effect F j F_j F j defines a binary test with outcomes “yes” (effect F j F_j F j ) and “no” (effect I − F j I-F_j I − F j ). Apply the tests in the order F 1 , F 2 , … F_1,F_2,\ldots F 1 , F 2 , … using Lüders instruments, and stop at the first “yes”. With C 1 = I C_1=I C 1 = I and C i + 1 = I − F i C i C_{i+1}=\sqrt{I-F_i}C_i C i + 1 = I − F i C i , the outcome “first yes at test i i i ” has effect K i = C i † F i C i ≥ 0 K_i=C_i^\dagger F_iC_i\ge0 K i = C i † F i C i ≥ 0 . Since C i + 1 † C i + 1 = C i † C i − K i C_{i+1}^\dagger C_{i+1}=C_i^\dagger C_i-K_i C i + 1 † C i + 1 = C i † C i − K i , the sum telescopes, ∑ i K i = I − C N + 1 † C N + 1 ≤ I \sum_iK_i=I-C_{N+1}^\dagger C_{N+1}\le I ∑ i K i = I − C N + 1 † C N + 1 ≤ I . Let P i P_i P i project onto the support of T i T_i T i . For j < i j<i j < i , F j T i = 0 F_jT_i=0 F j T i = 0 gives F j P i = 0 F_jP_i=0 F j P i = 0 , hence I − F j P i = P i \sqrt{I-F_j}P_i=P_i I − F j P i = P i . Thus C i P i = P i C_iP_i=P_i C i P i = P i and C i T i C i † = T i C_iT_iC_i^\dagger=T_i C i T i C i † = T i : the earlier tests, being certain to say “no” on T i T_i T i , leave it undisturbed. Therefore tr ( K i T i ) = tr ( F i T i ) \operatorname{tr}(K_iT_i)=\operatorname{tr}(F_iT_i) tr ( K i T i ) = tr ( F i T i ) , and since K i ≥ 0 K_i\ge0 K i ≥ 0 and T i ≤ R T_i\le R T i ≤ R , ∑ i tr ( F i T i ) = ∑ i tr ( K i T i ) ≤ tr [ ( ∑ i K i ) R ] ≤ tr R \sum_i\operatorname{tr}(F_iT_i)=\sum_i\operatorname{tr}(K_iT_i)\le\operatorname{tr}[(\sum_iK_i)R]\le\operatorname{tr}R ∑ i tr ( F i T i ) = ∑ i tr ( K i T i ) ≤ tr [( ∑ i K i ) R ] ≤ tr R .
Only the zeros below the diagonal are needed, and the labels may be ordered at will; in our applications all off-diagonal products vanish. For tensor-product models a closely related statement is Claim 1 of Ref. [32 ] , discussed in Appendix § 11 .
Theorem 1 (Quantum sum rule). Let N ≥ 3 N \ge3 N ≥ 3 . Every zero-error one-bit protocol over C q c \mathcal{C}_{\mathrm{qc}} C qc , and hence every entanglement-assisted protocol, satisfies
∑ t = 1 N Pr ( G = 1 ∣ t , t ) ≤ 1. (6) \sum_{t=1}^{N} \Pr(G=1 \mid t,t) \le1. \tag*{(6)} t = 1 ∑ N Pr ( G = 1 ∣ t , t ) ≤ 1. (6)
We first outline the proof. The proof proceeds in three steps. Steering Bob’s acceptance event onto Alice’s side defines, for each message m m m and input t t t , an unnormalized state T m t T_{mt} T m t of Alice with T m t ≤ ρ A T_{mt}\le\rho_A T m t ≤ ρ A ; zero error forces Alice’s encoding effects E m ∣ s E_{m|s} E m ∣ s to annihilate T m t T_{mt} T m t whenever s ≠ t s\ne t s = t . Since N ≥ 3 N\ge3 N ≥ 3 , a third label u u u shows that the supports associated with the two messages lie in the kernel and in the eigenvalue-one eigenspace of the same effect E 0 ∣ u E_{0|u} E 0∣ u , so the two message sectors are orthogonal. Lemma 2 bounds each message’s contribution by the weight of ρ A \rho_A ρ A in its corresponding subspace. Orthogonality makes these two weights add to at most one, giving Eq. (6) . In the commuting-operator model, the same orthogonality and sequential-measurement argument is carried out directly on the shared Hilbert space.
Proof of Theorem 1: tensor-product models. Let ρ A B \rho_{AB} ρ A B be the shared state and E m ∣ s E_{m|s} E m ∣ s Alice’s effect for sending m m m , with E 0 ∣ s + E 1 ∣ s = I E_{0|s}+E_{1|s}=\mathbf{I} E 0∣ s + E 1∣ s = I . For Bob’s input t t t and received message m m m , let D g ∣ m , t D_{g|m,t} D g ∣ m , t be his effect for announcing G = g G=g G = g ; thus D 1 ∣ m , t D_{1|m,t} D 1∣ m , t corresponds to declaring equality. Local processing and quantum memory are included.
ρ A = tr B ρ A B , T m t = tr B [ ( I ⊗ D 1 ∣ m , t ) ρ A B ( I ⊗ D 1 ∣ m , t ) ] . \rho_A=\operatorname{tr}_B \rho_{AB}, \qquad T_{mt}=\operatorname{tr}_B\left[\left(\mathbf{I}\otimes\sqrt{D_{1|m,t}}\right)\rho_{AB}\left(\mathbf{I}\otimes\sqrt{D_{1|m,t}}\right)\right]. ρ A = tr B ρ A B , T m t = tr B [ ( I ⊗ D 1∣ m , t ) ρ A B ( I ⊗ D 1∣ m , t ) ] .
Here T m t T_{mt} T m t is Alice’s unnormalized state corresponding to Bob’s acceptance. Acceptance and rejection together recover ρ A \rho_A ρ A , so 0 ≤ T m t ≤ ρ A 0\le T_{mt}\le\rho_A 0 ≤ T m t ≤ ρ A . For each message m m m ,
Pr ( M = m , G = 1 ∣ s , t ) = tr A B [ ( E m ∣ s ⊗ D 1 ∣ m , t ) ρ A B ] = tr A ( E m ∣ s T m t ) . \Pr(M=m,G=1\mid s,t)=\operatorname{tr}_{AB}\left[(E_{m|s}\otimes D_{1|m,t})\rho_{AB}\right]
=\operatorname{tr}_A(E_{m|s}T_{mt}). Pr ( M = m , G = 1 ∣ s , t ) = tr A B [ ( E m ∣ s ⊗ D 1∣ m , t ) ρ A B ] = tr A ( E m ∣ s T m t ) .
The first equality is the Born rule; the second follows from the definition of the partial trace and cyclicity of the trace. Summing over the two possible messages gives
Pr ( G = 1 ∣ s , t ) = ∑ m tr ( E m ∣ s T m t ) . \Pr(G=1\mid s,t)=\sum_m\operatorname{tr}(E_{m|s}T_{mt}). Pr ( G = 1 ∣ s , t ) = m ∑ tr ( E m ∣ s T m t ) .
For s ≠ t s\ne t s = t , zero error makes this sum zero. Each term is nonnegative, and a positive effect with zero expectation vanishes on the state’s support (the subspace it occupies). Hence
E m ∣ s T m t = 0 ( s ≠ t ) . (7) E_{m|s}T_{mt}=0 \qquad(s\ne t). \tag*{(7)} E m ∣ s T m t = 0 ( s = t ) . (7)
The key observation is that the states for the two messages occupy orthogonal subspaces. Take v ∈ supp T 0 t v\in\operatorname{supp}T_{0t} v ∈ supp T 0 t and w ∈ supp T 1 t ′ w\in\operatorname{supp}T_{1t'} w ∈ supp T 1 t ′ . Since N ≥ 3 N\ge3 N ≥ 3 , choose u ∉ { t , t ′ } u\notin\{t,t'\} u ∈ / { t , t ′ } . Equation (7) gives
E 0 ∣ u v = 0 , E 1 ∣ u w = 0 , so E 0 ∣ u w = w . E_{0|u}v=0,\qquad E_{1|u}w=0,\qquad\text{so}\qquad E_{0|u}w=w. E 0∣ u v = 0 , E 1∣ u w = 0 , so E 0∣ u w = w .
Therefore ⟨ v , w ⟩ = ⟨ v , E 0 ∣ u w ⟩ = ⟨ E 0 ∣ u v , w ⟩ = 0 \langle v,w\rangle=\langle v,E_{0|u}w\rangle=\langle E_{0|u}v,w\rangle=0 ⟨ v , w ⟩ = ⟨ v , E 0∣ u w ⟩ = ⟨ E 0∣ u v , w ⟩ = 0 . Let H m \mathcal{H}_m H m be the closed span of the supports of all T m t T_{mt} T m t , and let Π m \Pi_m Π m project onto it. The orthogonality just proved gives H 0 ⊥ H 1 \mathcal{H}_0\perp\mathcal{H}_1 H 0 ⊥ H 1 . Thus Π 0 + Π 1 \Pi_0+\Pi_1 Π 0 + Π 1 is the projector onto their combined subspace, so Π 0 + Π 1 ≤ I \Pi_0+\Pi_1\le\mathbf{I} Π 0 + Π 1 ≤ I .
Fix m m m . Each T m t T_{mt} T m t is supported in H m \mathcal{H}_m H m , so projecting onto this subspace leaves it unchanged: T m t = Π m T m t Π m T_{mt}=\Pi_mT_{mt}\Pi_m T m t = Π m T m t Π m . Set R m = Π m ρ A Π m R_m=\Pi_m\rho_A\Pi_m R m = Π m ρ A Π m . Since ρ A − T m t ≥ 0 \rho_A-T_{mt}\ge0 ρ A − T m t ≥ 0 , we have
R m − T m t = Π m ( ρ A − T m t ) Π m ≥ 0. R_m-T_{mt}=\Pi_m(\rho_A-T_{mt})\Pi_m\ge0. R m − T m t = Π m ( ρ A − T m t ) Π m ≥ 0.
Indeed, the expectation of the right-hand operator in any vector x x x is ⟨ Π m x , ( ρ A − T m t ) Π m x ⟩ ≥ 0 \langle\Pi_mx,(\rho_A-T_{mt})\Pi_mx\rangle\ge0 ⟨ Π m x , ( ρ A − T m t ) Π m x ⟩ ≥ 0 . Hence 0 ≤ T m t ≤ R m 0\le T_{mt}\le R_m 0 ≤ T m t ≤ R m for every t t t : all these states have the same positive upper bound.
We can now apply Lemma 2 with T t = T m t T_t=T_{mt} T t = T m t , F t = E m ∣ t F_t=E_{m|t} F t = E m ∣ t and R = R m R=R_m R = R m . The upper-bound condition was just verified; each E m ∣ t E_{m|t} E m ∣ t is an effect; and Eq. (7) gives E m ∣ t T m t ′ = 0 E_{m|t}T_{mt'}=0 E m ∣ t T m t ′ = 0 for t ≠ t ′ t\ne t' t = t ′ . The lemma does not require these effects, which correspond to different inputs, to sum to the identity. It gives
∑ t tr ( E m ∣ t T m t ) ≤ tr R m = tr ( Π m ρ A Π m ) = tr ( ρ A Π m ) , \sum_t\operatorname{tr}(E_{m|t}T_{mt})\le\operatorname{tr}R_m=\operatorname{tr}(\Pi_m\rho_A\Pi_m)=\operatorname{tr}(\rho_A\Pi_m), t ∑ tr ( E m ∣ t T m t ) ≤ tr R m = tr ( Π m ρ A Π m ) = tr ( ρ A Π m ) ,
where the last equality uses cyclicity of the trace and Π m 2 = Π m \Pi_m^2=\Pi_m Π m 2 = Π m . By the Born rule, tr ( ρ A Π m ) \operatorname{tr}(\rho_A\Pi_m) tr ( ρ A Π m ) is the probability that a projection onto H m \mathcal{H}_m H m succeeds on ρ A \rho_A ρ A . This is the weight of ρ A \rho_A ρ A in that subspace. Adding the two message contributions therefore gives
∑ t Pr ( G = 1 ∣ t , t ) = ∑ m = 0 1 ∑ t tr ( E m ∣ t T m t ) ≤ tr [ ρ A ( Π 0 + Π 1 ) ] ≤ tr ρ A = 1. \sum_t \Pr(G=1\mid t,t)=\sum_{m=0}^{1}\sum_t \operatorname{tr}(E_{m\mid t}T_{mt})\leq\operatorname{tr}[\rho_A(\Pi_0+\Pi_1)]\leq\operatorname{tr}\rho_A=1. t ∑ Pr ( G = 1 ∣ t , t ) = m = 0 ∑ 1 t ∑ tr ( E m ∣ t T m t ) ≤ tr [ ρ A ( Π 0 + Π 1 )] ≤ tr ρ A = 1.
This completes the proof. □
Proof of Theorem 1: commuting-operator models. Let ψ \psi ψ be the shared unit vector, with E 0 ∣ s + E 1 ∣ s = I E_{0\mid s}+E_{1\mid s}=I E 0 ∣ s + E 1 ∣ s = I and all Alice effects commuting with all Bob effects. Put v m t = D 1 ∣ m , t ψ v_{mt}=\sqrt{D_{1\mid m,t}}\psi v m t = D 1 ∣ m , t ψ . The Born rule gives
Pr ( G = 1 ∣ s , t ) = ∑ m ∥ E m ∣ s v m t ∥ 2 , \Pr(G=1\mid s,t)=\sum_m\left\|\sqrt{E_{m\mid s}}v_{mt}\right\|^2, Pr ( G = 1 ∣ s , t ) = m ∑ E m ∣ s v m t 2 ,
so zero error implies E m ∣ s v m t = 0 E_{m\mid s}v_{mt}=0 E m ∣ s v m t = 0 whenever s ≠ t s\ne t s = t .
Define
V m t = { v : E m ∣ s v = 0 for every s ≠ t } , V_{mt}=\{v:E_{m\mid s}v=0\text{ for every }s\ne t\}, V m t = { v : E m ∣ s v = 0 for every s = t } ,
and let Π m \Pi_m Π m project onto the closed span H m \mathcal{H}_m H m of V m 1 , … , V m N V_{m1},\ldots,V_{mN} V m 1 , … , V m N . Thus v m t ∈ H m v_{mt}\in\mathcal{H}_m v m t ∈ H m . The same third-label argument as above gives H 0 ⊥ H 1 \mathcal{H}_0\perp\mathcal{H}_1 H 0 ⊥ H 1 , hence Π 0 + Π 1 ≤ I \Pi_0+\Pi_1\leq I Π 0 + Π 1 ≤ I .
Every Bob effect D D D preserves each V m t V_{mt} V m t , since E m ∣ s D v = D E m ∣ s v = 0 E_{m\mid s}Dv=DE_{m\mid s}v=0 E m ∣ s D v = D E m ∣ s v = 0 for v ∈ V m t v\in V_{mt} v ∈ V m t and s ≠ t s\ne t s = t . Thus D D D preserves H m \mathcal{H}_m H m and, being self-adjoint, also H m ⊥ \mathcal{H}_m^\perp H m ⊥ . Consequently D Π m = Π m D D\Pi_m=\Pi_mD D Π m = Π m D .
Now construct one measurement on Alice’s side. First measure Π 0 \Pi_0 Π 0 , Π 1 \Pi_1 Π 1 and I − Π 0 − Π 1 I-\Pi_0-\Pi_1 I − Π 0 − Π 1 . In branch m m m , apply the sequential Lüders tests E m ∣ 1 , … , E m ∣ N E_{m\mid1},\ldots,E_{m\mid N} E m ∣ 1 , … , E m ∣ N from Lemma 2. Let K m t K_{mt} K m t be the effect for the first “yes” at t t t in branch m m m . These are outcomes of one measurement, so ∑ m , t K m t ≤ I \sum_{m,t}K_{mt}\leq I ∑ m , t K m t ≤ I ; they commute with Bob’s effects because all the projectors and update operators used to construct them do.
On v m t v_{mt} v m t , the initial projection and all earlier “no” outcomes leave the vector unchanged, as in Lemma 2. Therefore
⟨ v m t , E m ∣ t v m t ⟩ = ⟨ v m t , K m t v m t ⟩ = ⟨ ψ , K m t D 1 ∣ m , t ψ ⟩ ≤ ⟨ ψ , K m t ψ ⟩ . (8) \begin{aligned}
\langle v_{mt},E_{m\mid t}v_{mt}\rangle&=\langle v_{mt},K_{mt}v_{mt}\rangle\\
&=\langle\psi,K_{mt}D_{1\mid m,t}\psi\rangle\leq\langle\psi,K_{mt}\psi\rangle. \tag*{(8)}
\end{aligned} ⟨ v m t , E m ∣ t v m t ⟩ = ⟨ v m t , K m t v m t ⟩ = ⟨ ψ , K m t D 1 ∣ m , t ψ ⟩ ≤ ⟨ ψ , K m t ψ ⟩ . (8)
The inequality uses commutation and 0 ≤ D 1 ∣ m , t ≤ I 0\leq D_{1\mid m,t}\leq I 0 ≤ D 1 ∣ m , t ≤ I . Summing over the measurement outcomes gives
∑ t Pr ( G = 1 ∣ t , t ) ≤ ∑ m , t ⟨ ψ , K m t ψ ⟩ ≤ 1. \sum_t\Pr(G=1\mid t,t)\leq\sum_{m,t}\langle\psi,K_{mt}\psi\rangle\leq1. t ∑ Pr ( G = 1 ∣ t , t ) ≤ m , t ∑ ⟨ ψ , K m t ψ ⟩ ≤ 1.
This completes the proof. □
Corollary 1. For every N ≥ 3 N\geq3 N ≥ 3 , η Ω ( N ) = 1 / N \eta_{\Omega}(N)=1/N η Ω ( N ) = 1/ N for Ω ∈ { C L , C q , C q s , C q a , C q c } \Omega\in\{\mathrm{C}_L,\mathrm{C}_q,\mathrm{C}_{qs},\mathrm{C}_{qa},\mathrm{C}_{qc}\} Ω ∈ { C L , C q , C q s , C q a , C q c } .
Proof. On a diagonal input ( t , t ) (t,t) ( t , t ) , zero error forces every conclusive answer to be G = 1 G=1 G = 1 , so each term in Eq. (6) is at least the worst-case efficiency, which is therefore at most 1 / N 1/N 1/ N over C q c \mathrm{C}_{qc} C q c , and hence over every smaller set. Conversely, shared randomness attains 1 / N 1/N 1/ N : the parties share a uniform random label L ∈ [ N ] L\in[N] L ∈ [ N ] , Alice sends M = 1 { s = L } M=1\{s=L\} M = 1 { s = L } , and Bob outputs G = M G=M G = M if t = L t=L t = L and abstains otherwise. Bob answers only when t = L t=L t = L , and then M = 1 { s = t } M=1\{s=t\} M = 1 { s = t } , so the protocol never errs and is conclusive with probability exactly 1 / N 1/N 1/ N on every input pair. □
Entanglement thus offers no advantage over shared randomness, and the same holds for the closure C q a \mathrm{C}_{qa} C q a , so no sequence of quantum strategies does better either.
Relation to earlier bounds. For tensor-product models, the inequality underlying Lemma 2 and the witness of Section 6 appears as Claim 1 in the work of Klauck and de Wolf [32 ] . Combined with the removal of communication by teleportation and guessing, it yields linear lower bounds on entanglement-assisted one-sided-error and zero-error communication for equality, even with interaction. For a single classical bit, the same argument gives ∑ t Pr ( G = 1 ∣ t , t ) ≤ 2 \sum_t \Pr(G=1\mid t,t) \le2 ∑ t Pr ( G = 1 ∣ t , t ) ≤ 2 and hence η Q ( N ) ≤ 2 / N \eta_{\mathrm{Q}}(N) \le2/N η Q ( N ) ≤ 2/ N . Theorem 1 removes the factor 2, which is the price of guessing the message, and the resulting value 1 / N 1/N 1/ N is attained. Appendix B recalls their results, extends their argument to commuting-operator models (Propositions 3 and 4) and compares the bounds in detail. The almost-quantum constructions and optimizations of Sections 5 and 8 do not rely on any of these bounds.
Almost-quantum certificates of equality
Explicit almost-quantum boxes for every N N N
Consider the box p ⋆ p^\star p ⋆ of Table 2 , with settings x , y ∈ [ N ] x,y \in[N] x , y ∈ [ N ] and binary outcomes a , b ∈ { 0 , 1 } a,b \in\{0,1\} a , b ∈ { 0 , 1 } . It depends only on whether the settings coincide, its marginals are p A ( 0 ∣ x ) = p B ( 0 ∣ y ) = 3 / 17 p_A(0\mid x)=p_B(0\mid y)=3/17 p A ( 0 ∣ x ) = p B ( 0 ∣ y ) = 3/17 , so it is nonsignalling, and it lies on the face
Table 2. The box p ⋆ ( a , b ∣ x , y ) p^\star(a,b\mid x,y) p ⋆ ( a , b ∣ x , y ) . It depends only on whether the settings coincide and is almost quantum for every N N N .
F 0 = { p : p ( 0 , 0 ∣ x , y ) = 0 for all x ≠ y } (9) F_0=\{p:p(0,0\mid x,y)=0\text{ for all }x\ne y\} \tag*{(9)} F 0 = { p : p ( 0 , 0 ∣ x , y ) = 0 for all x = y } (9)
of the nonsignalling polytope.
Theorem 2. For every N ≥ 2 N \ge2 N ≥ 2 , p ⋆ ∈ C A Q p^\star\in C_{\mathrm{AQ}} p ⋆ ∈ C AQ . Consequently, η A Q ( N ) ≥ 1 / 19 \eta_{\mathrm{AQ}}(N) \ge1/19 η AQ ( N ) ≥ 1/19 for every N ≥ 3 N \ge3 N ≥ 3 , and η A Q ( N ) / η Q ( N ) ≥ N / 19 \eta_{\mathrm{AQ}}(N)/\eta_{\mathrm{Q}}(N) \ge N/19 η AQ ( N ) / η Q ( N ) ≥ N /19 .
Membership in C A Q C_{\mathrm{AQ}} C AQ is proved in Section 5.2 by an explicit realization: the AQ state and all projectors are built from 3 N + 1 3N+1 3 N + 1 real vectors in R 2 N + 3 \mathbb{R}^{2N+3} R 2 N + 3 , and membership is verified by direct multiplication, without numerical semidefinite programming. The dimension 2 N + 3 2N+3 2 N + 3 is a feature of this mathematical representation, not a physical implementation cost. The protocol has three ingredients.
(a) Certificate of equality. Alice uses the setting x = s x=s x = s , obtains a a a and sends M = a M=a M = a . Bob uses the setting y = t y=t y = t , obtains b b b , outputs G = 1 G=1 G = 1 if M = b = 0 M=b=0 M = b = 0 and abstains otherwise. By Table 2 , Pr ( G = 1 ∣ s = t ) = 1 / 17 \Pr(G=1\mid s=t)=1/17 Pr ( G = 1 ∣ s = t ) = 1/17 and Pr ( G = 1 ∣ s ≠ t ) = 0 \Pr(G=1\mid s\ne t)=0 Pr ( G = 1 ∣ s = t ) = 0 . Bob’s setting does not depend on M M M , so the box is used as a plain black box.
(b) Classical certificate of inequality. The parties share independent fair bits Z 1 , … , Z N Z_1,\ldots,Z_N Z 1 , … , Z N . Alice sends M = Z s M=Z_s M = Z s ; Bob outputs G = 0 G=0 G = 0 if M ≠ Z t M\ne Z_t M = Z t and abstains otherwise. Then Pr ( G = 0 ∣ s = t ) = 0 \Pr(G=0\mid s=t)=0 Pr ( G = 0 ∣ s = t ) = 0 and Pr ( G = 0 ∣ s ≠ t ) = 1 / 2 \Pr(G=0\mid s\ne t)=1/2 Pr ( G = 0 ∣ s = t ) = 1/2 .
(c) Mixing. Using shared randomness, the parties run (a) with probability 17 / 19 17/19 17/19 and (b) with probability 2 / 19 2/19 2/19 . Neither branch errs, and the probability of a conclusive answer is 17 / 19 × 1 / 17 = 1 / 19 17/19\times1/17=1/19 17/19 × 1/17 = 1/19 for s = t s=t s = t and 2 / 19 × 1 / 2 = 1 / 19 2/19\times1/2=1/19 2/19 × 1/2 = 1/19 for s ≠ t s\ne t s = t . Mixing with shared randomness keeps the resource almost quantum, because C A Q \mathrm{C}_{\mathrm{AQ}} C AQ is convex and contains all classical correlations (Lemma 1). Together with Corollary 1, this gives an efficiency ratio of at least N / 19 N/19 N /19 , which grows without bound.
Reduction to vectors with prescribed inner products
The AQ condition (1) turns AQ membership of boxes in F 0 \mathrm{F}_0 F 0 into a problem about 3 N + 1 3N+1 3 N + 1 vectors. For binary outcomes write A x ≡ A 0 ∣ x A_x \equiv A_{0|x} A x ≡ A 0∣ x and B y ≡ B 0 ∣ y B_y \equiv B_{0|y} B y ≡ B 0∣ y .
Lemma 3 (Gram reduction). Let p ∈ F 0 p \in\mathrm{F}_0 p ∈ F 0 have binary outcomes, and write p A = p A ( 0 ∣ x ) p_A=p_A(0|x) p A = p A ( 0∣ x ) , p B = p B ( 0 ∣ y ) p_B=p_B(0|y) p B = p B ( 0∣ y ) and q = p ( 0 , 0 ∣ x , x ) q=p(0,0|x,x) q = p ( 0 , 0∣ x , x ) . Then p ∈ C A Q p \in\mathrm{C}_{\mathrm{AQ}} p ∈ C AQ if and only if there exist vectors ψ , a x , b x , w x \psi,a_x,b_x,w_x ψ , a x , b x , w x (x ∈ [ N ] x \in[N] x ∈ [ N ] ) in a real Hilbert space with ∥ ψ ∥ = 1 \lVert\psi\rVert=1 ∥ ψ ∥ = 1 and
⟨ ψ , a x ⟩ = ∥ a x ∥ 2 = p A , ⟨ ψ , b x ⟩ = ∥ b x ∥ 2 = p B , \langle\psi,a_x\rangle=\lVert a_x\rVert^2=p_A,\qquad\langle\psi,b_x\rangle=\lVert b_x\rVert^2=p_B, ⟨ ψ , a x ⟩ = ∥ a x ∥ 2 = p A , ⟨ ψ , b x ⟩ = ∥ b x ∥ 2 = p B , ⟨ ψ , w x ⟩ = ∥ w x ∥ 2 = ⟨ a x , w x ⟩ = ⟨ b x , w x ⟩ = ⟨ a x , b x ⟩ = q , \langle\psi,w_x\rangle=\lVert w_x\rVert^2=\langle a_x,w_x\rangle=\langle b_x,w_x\rangle=\langle a_x,b_x\rangle=q, ⟨ ψ , w x ⟩ = ∥ w x ∥ 2 = ⟨ a x , w x ⟩ = ⟨ b x , w x ⟩ = ⟨ a x , b x ⟩ = q , ⟨ a x , b y ⟩ = ⟨ a x , w y ⟩ = ⟨ b x , w y ⟩ = 0 ( x ≠ y ) . (10) \langle a_x,b_y\rangle=\langle a_x,w_y\rangle=\langle b_x,w_y\rangle=0\qquad(x\ne y). \tag*{(10)} ⟨ a x , b y ⟩ = ⟨ a x , w y ⟩ = ⟨ b x , w y ⟩ = 0 ( x = y ) . (10)
For clarity we state the lemma for x x x -independent p A , p B , q p_A,p_B,q p A , p B , q ; the general case is identical with x x x -dependent values.
Proof. Necessity. Given an AQ realization, set a x = A x ψ a_x=A_x\psi a x = A x ψ , b x = B x ψ b_x=B_x\psi b x = B x ψ and w x = A x B x ψ = B x A x ψ w_x=A_xB_x\psi=B_xA_x\psi w x = A x B x ψ = B x A x ψ . The first two lines of Eq. (10) follow from A x 2 = A x A_x^2=A_x A x 2 = A x , B x 2 = B x B_x^2=B_x B x 2 = B x and commutation on ψ \psi ψ . For x ≠ y x\ne y x = y ,
∥ A x B y ψ ∥ 2 = ⟨ ψ , B y A x B y ψ ⟩ = ⟨ ψ , A x B y ψ ⟩ = p ( 0 , 0 ∣ x , y ) = 0 , \lVert A_xB_y\psi\rVert^2=\langle\psi,B_yA_xB_y\psi\rangle=\langle\psi,A_xB_y\psi\rangle=p(0,0|x,y)=0, ∥ A x B y ψ ∥ 2 = ⟨ ψ , B y A x B y ψ ⟩ = ⟨ ψ , A x B y ψ ⟩ = p ( 0 , 0∣ x , y ) = 0 ,
so A x B y ψ = B y A x ψ = 0 A_xB_y\psi=B_yA_x\psi=0 A x B y ψ = B y A x ψ = 0 . Hence ⟨ a x , b y ⟩ = 0 \langle a_x,b_y\rangle=0 ⟨ a x , b y ⟩ = 0 , ⟨ a x , w y ⟩ = ⟨ A x B y ψ , A y ψ ⟩ = 0 \langle a_x,w_y\rangle=\langle A_xB_y\psi,A_y\psi\rangle=0 ⟨ a x , w y ⟩ = ⟨ A x B y ψ , A y ψ ⟩ = 0 , and similarly ⟨ b x , w y ⟩ = 0 \langle b_x,w_y\rangle=0 ⟨ b x , w y ⟩ = 0 . All prescribed inner products are real, so taking the real part of the Gram matrix yields real vectors with the same properties.
Sufficiency. Let H \mathcal{H} H be the real Hilbert space spanned by ψ \psi ψ and the vectors a x , b x , w x a_x,b_x,w_x a x , b x , w x (its complexification may be used instead). For a subspace V ⊆ H V\subseteq\mathcal{H} V ⊆ H , let Π V \Pi_V Π V denote the projector onto V V V , i.e. Π V 2 = Π V = Π V † \Pi_V^2=\Pi_V=\Pi_V^\dagger Π V 2 = Π V = Π V † and Π V H = V \Pi_V\mathcal{H}=V Π V H = V ; recall that Π V v = u \Pi_Vv=u Π V v = u whenever u ∈ V u\in V u ∈ V and v − u ⊥ V v-u\perp V v − u ⊥ V . For each x ∈ [ N ] x\in[N] x ∈ [ N ] define
A 0 ∣ x ≡ A x = Π span { a x , w x } , A 1 ∣ x = I − A x , B 0 ∣ x ≡ B x = Π span { b x , w x } , B 1 ∣ x = I − B x , A_{0|x}\equiv A_x=\Pi_{\operatorname{span}\{a_x,w_x\}},\quad A_{1|x}=I-A_x,\qquad B_{0|x}\equiv B_x=\Pi_{\operatorname{span}\{b_x,w_x\}},\quad B_{1|x}=I-B_x, A 0∣ x ≡ A x = Π span { a x , w x } , A 1∣ x = I − A x , B 0∣ x ≡ B x = Π span { b x , w x } , B 1∣ x = I − B x ,
so that { A a ∣ x } a \{A_{a|x}\}_a { A a ∣ x } a and { B b ∣ y } b \{B_{b|y}\}_b { B b ∣ y } b are projective measurements. Let x ≠ y x\ne y x = y . By Eq. (10) , each of ψ − a x \psi-a_x ψ − a x , b x − w x b_x-w_x b x − w x and b y b_y b y is orthogonal to both a x a_x a x and w x w_x w x , and each of ψ − b x \psi-b_x ψ − b x , a x − w x a_x-w_x a x − w x and a y a_y a y is orthogonal to both b x b_x b x and w x w_x w x . Hence
A x ψ = a x , A x b x = w x , A x b y = 0 , B x ψ = b x , B x a x = w x , B x a y = 0 , A_x\psi=a_x,\quad A_xb_x=w_x,\quad A_xb_y=0,\qquad B_x\psi=b_x,\quad B_xa_x=w_x,\quad B_xa_y=0, A x ψ = a x , A x b x = w x , A x b y = 0 , B x ψ = b x , B x a x = w x , B x a y = 0 ,
and therefore, for all x , y ∈ [ N ] x,y\in[N] x , y ∈ [ N ] , A x B y ψ = A x b y = δ x y w x = B y a x = B y A x ψ A_xB_y\psi=A_xb_y=\delta_{xy}w_x=B_ya_x=B_yA_x\psi A x B y ψ = A x b y = δ x y w x = B y a x = B y A x ψ . Since A 1 ∣ x = I − A x A_{1|x}=I-A_x A 1∣ x = I − A x and B 1 ∣ y = I − B y B_{1|y}=I-B_y B 1∣ y = I − B y , the identity A a ∣ x B b ∣ y ψ = B b ∣ y A a ∣ x ψ A_{a|x}B_{b|y}\psi=B_{b|y}A_{a|x}\psi A a ∣ x B b ∣ y ψ = B b ∣ y A a ∣ x ψ extends from ( a , b ) = ( 0 , 0 ) (a,b)=(0,0) ( a , b ) = ( 0 , 0 ) to all outcome pairs; for example, A 1 ∣ x B y ψ = b y − δ x y w x = B y A 1 ∣ x ψ A_{1|x}B_y\psi=b_y-\delta_{xy}w_x=B_yA_{1|x}\psi A 1∣ x B y ψ = b y − δ x y w x = B y A 1∣ x ψ . Thus Eq. (1) holds. The realized box has p ( 0 , 0 ∣ x , y ) = ⟨ ψ , A x B y ψ ⟩ = δ x y ⟨ ψ , w x ⟩ = δ x y q p(0,0|x,y)=\langle\psi,A_xB_y\psi\rangle=\delta_{xy}\langle\psi,w_x\rangle=\delta_{xy}q p ( 0 , 0∣ x , y ) = ⟨ ψ , A x B y ψ ⟩ = δ x y ⟨ ψ , w x ⟩ = δ x y q , p A ( 0 ∣ x ) = ⟨ ψ , a x ⟩ = p A p_A(0|x)=\langle\psi,a_x\rangle=p_A p A ( 0∣ x ) = ⟨ ψ , a x ⟩ = p A and p B ( 0 ∣ y ) = ⟨ ψ , b y ⟩ = p B p_B(0|y)=\langle\psi,b_y\rangle=p_B p B ( 0∣ y ) = ⟨ ψ , b y ⟩ = p B . For binary outcomes these values fix all entries, so the realized box is p p p . □
Proof of Theorem 2. Let { ψ , e 1 , e 2 } ∪ { f x , g x } x ∈ [ N ] \{\psi,e_1,e_2\}\cup\{f_x,g_x\}_{x\in[N]} { ψ , e 1 , e 2 } ∪ { f x , g x } x ∈ [ N ] be an orthonormal basis of R 2 N + 3 \mathbb{R}^{2N+3} R 2 N + 3 and define
a x = 3 17 ψ + 1 34 ( 51 e 1 + 15 e 2 ) + 1 2 17 ( f x + 5 g x ) , a_x=\frac{3}{17}\psi+\frac{1}{34}\left(\sqrt{51}e_1+\sqrt{15}e_2\right)+\frac{1}{2\sqrt{17}}\left(f_x+\sqrt{5}g_x\right), a x = 17 3 ψ + 34 1 ( 51 e 1 + 15 e 2 ) + 2 17 1 ( f x + 5 g x ) ,
b x = 3 17 ψ + 1 34 ( − 51 e 1 + 15 e 2 ) + 1 2 17 ( − f x + 5 g x ) , (11) b_x=\frac{3}{17}\psi+\frac{1}{34}\left(-\sqrt{51}e_1+\sqrt{15}e_2\right)+\frac{1}{2\sqrt{17}}\left(-f_x+\sqrt{5}g_x\right), \tag*{(11)} b x = 17 3 ψ + 34 1 ( − 51 e 1 + 15 e 2 ) + 2 17 1 ( − f x + 5 g x ) , (11)
w x = 1 17 ψ − 2 15 85 e 2 + 2 85 g x . w_x=\frac{1}{17}\psi-\frac{2\sqrt{15}}{85}e_2+\frac{2}{\sqrt{85}}g_x. w x = 17 1 ψ − 85 2 15 e 2 + 85 2 g x .
Direct multiplication shows that these vectors satisfy Eq. (10) with p A = p B = 3 / 17 p_A=p_B=3/17 p A = p B = 3/17 and q = 1 / 17 q=1/17 q = 1/17 , and that ⟨ a x , a y ⟩ = ⟨ b x , b y ⟩ = 3 / 34 \langle a_x,a_y\rangle=\langle b_x,b_y\rangle=3/34 ⟨ a x , a y ⟩ = ⟨ b x , b y ⟩ = 3/34 and ⟨ w x , w y ⟩ = 1 / 85 \langle w_x,w_y\rangle=1/85 ⟨ w x , w y ⟩ = 1/85 for x ≠ y x\ne y x = y . By Lemma 3, the projectors A x = Π span { a x , w x } A_x=\Pi_{\operatorname{span}\{a_x,w_x\}} A x = Π span { a x , w x } and B y = Π span { b y , w y } B_y=\Pi_{\operatorname{span}\{b_y,w_y\}} B y = Π span { b y , w y } realize a box in C A Q \mathrm{C}_{\mathrm{AQ}} C AQ with p ( 0 , 0 ∣ x , y ) = δ x y / 17 p(0,0\mid x,y)=\delta_{xy}/17 p ( 0 , 0 ∣ x , y ) = δ x y /17 and p A ( 0 ∣ x ) = p B ( 0 ∣ y ) = 3 / 17 p_A(0\mid x)=p_B(0\mid y)=3/17 p A ( 0 ∣ x ) = p B ( 0 ∣ y ) = 3/17 ; the remaining entries of Table 2 follow from normalization. Since only the equality or inequality of labels enters, the construction is valid for every N ≥ 2 N\ge2 N ≥ 2 . By Lemma 1(i), mixing with shared randomness preserves membership in C A Q \mathrm{C}_{\mathrm{AQ}} C AQ , so the protocol of § 5.1 uses AQ resources and attains 1 / 19 1/19 1/19 .
Optimal almost-quantum certification of equality
The box p ⋆ p^\star p ⋆ is not an isolated construction: it is the large-N N N limit of the optimal AQ boxes. To state this precisely we isolate the hard direction of the task. For binary-outcome boxes, the protocol of (a) never errs if and only if p ∈ F 0 p\in\mathrm{F}_0 p ∈ F 0 , and its worst-case probability of certifying equality is min x p ( 0 , 0 ∣ x , x ) \min_x p(0,0\mid x,x) min x p ( 0 , 0 ∣ x , x ) . We therefore define
η Ω e q ( N ) = sup p ∈ Ω ∩ F 0 min x p ( 0 , 0 ∣ x , x ) . (12) \eta_{\Omega}^{\mathrm{eq}}(N)=\sup_{p\in\Omega\cap\mathrm{F}_0}\min_x p(0,0\mid x,x). \tag*{(12)} η Ω eq ( N ) = p ∈ Ω ∩ F 0 sup x min p ( 0 , 0 ∣ x , x ) . (12)
By Theorem 1, η Ω e q ( N ) = 1 / N \eta_{\Omega}^{\mathrm{eq}}(N)=1/N η Ω eq ( N ) = 1/ N for every Ω \Omega Ω from C L \mathrm{C}_{\mathrm{L}} C L to C q c \mathrm{C}_{\mathrm{qc}} C qc . Mixing an equality certificate of efficiency η e q \eta^{\mathrm{eq}} η eq with the classical inequality certificate, as in (c), gives
η Ω ( N ) ≥ η Ω e q ( N ) 1 + 2 η Ω e q ( N ) . (13) \eta_{\Omega}(N)\ge\frac{\eta_{\Omega}^{\mathrm{eq}}(N)}{1+2\eta_{\Omega}^{\mathrm{eq}}(N)}. \tag*{(13)} η Ω ( N ) ≥ 1 + 2 η Ω eq ( N ) η Ω eq ( N ) . (13)
Theorem 3 (Optimal AQ equality certification). *For every N ≥ 3 N\ge3 N ≥ 3 ,
η A Q e q ( N ) = { 1 / N , 3 ≤ N ≤ 8 , N 2 / ( 17 N 2 − 80 N + 64 ) , N ≥ 8. (14) \eta_{\mathrm{AQ}}^{\mathrm{eq}}(N)=
\begin{cases}
1/N, & 3\le N\le8,\\
N^2/(17N^2-80N+64), & N\ge8.
\end{cases} \tag*{(14)} η AQ eq ( N ) = { 1/ N , N 2 / ( 17 N 2 − 80 N + 64 ) , 3 ≤ N ≤ 8 , N ≥ 8. (14) In particular, for N ≥ 8 N\ge8 N ≥ 8 ,
η A Q e q ( N ) − η Q e q ( N ) = ( N − 1 ) ( N − 8 ) 2 N ( 17 N 2 − 80 N + 64 ) , (15) \eta_{\mathrm{AQ}}^{\mathrm{eq}}(N)-\eta_{\mathrm{Q}}^{\mathrm{eq}}(N)=\frac{(N-1)(N-8)^2}{N(17N^2-80N+64)}, \tag*{(15)} η AQ eq ( N ) − η Q eq ( N ) = N ( 17 N 2 − 80 N + 64 ) ( N − 1 ) ( N − 8 ) 2 , (15) so AQ correlations outperform quantum ones if and only if N ≥ 9 N\ge9 N ≥ 9 , and η A Q e q ( N ) \eta_{\mathrm{AQ}}^{\mathrm{eq}}(N) η AQ eq ( N ) decreases monotonically to 1 / 17 1/17 1/17 as N → ∞ N\to\infty N → ∞ .**
The proof, given below, has two parts. First, the AQ condition (1) reduces membership of a box in F 0 \mathrm{F}_0 F 0 to the existence of 3 N + 1 3N+1 3 N + 1 vectors with prescribed inner products, and permutation symmetry reduces the optimization to six real parameters subject to two small linear matrix inequalities. Second, an explicit dual certificate gives the upper bound and an explicit primal solution attains it. Figure 2 compares the result with the quantum value and with the optimum over Level 1 of the NPA hierarchy, derived in § 8 . The boxes p ⋆ p^\star p ⋆ attain 1 / 17 1/17 1/17 for every N N N , and no construction valid for all N N N at once can do better (see the end of the proof below). With the N N N -dependent optimal boxes, Eq. (13) gives η A Q ( N ) ≥ N 2 / ( 19 N 2 − 80 N + 64 ) \eta_{\mathrm{AQ}}(N)\ge N^2/(19N^2-80N+64) η AQ ( N ) ≥ N 2 / ( 19 N 2 − 80 N + 64 ) for N ≥ 8 N\ge8 N ≥ 8 , which exceeds the quantum value 1 / N 1/N 1/ N for every N ≥ 14 N\ge14 N ≥ 14 . Theorem 3 concerns binary-outcome boxes in which Bob accepts on a single outcome; whether more general boxes, or settings that depend on the message, can do better is left open.
Figure 2. Figure 2. Certifying equality with almost-quantum and level-1 correlations. (a) Optimal probability of certifying equality with binary-outcome boxes. For every quantum model, from finite-dimensional entanglement to commuting operators, the optimum is 1 / N 1/N 1/ N , the value attained with shared randomness (black). The optimal almost-quantum value of Theorem 3 (blue) coincides with 1 / N 1/N 1/ N for N ≤ 8 N \le8 N ≤ 8 , exceeds it for every N ≥ 9 N \ge9 N ≥ 9 , and tends to 1 / 17 1/17 1/17 . The boxes p ⋆ p^\star p ⋆ attain 1 / 17 1/17 1/17 for every N N N (dashed, green). The optimum over Level 1 of the NPA hierarchy, η C V e c e q ( N ) = N / [ 8 ( N − 2 ) ] \eta_{\mathrm{CVec}}^{\mathrm{eq}}(N) = N/[8(N-2)] η CVec eq ( N ) = N / [ 8 ( N − 2 )] (Proposition 2; orange), coincides with 1 / N 1/N 1/ N for N ≤ 4 N \le4 N ≤ 4 , exceeds it for every N ≥ 5 N \ge5 N ≥ 5 , and tends to 1 / 8 1/8 1/8 . It exceeds the AQ optimum for every N ≥ 5 N \ge5 N ≥ 5 , so the boxes that attain it are not almost quantum. (b) Value of the exact-zero (face) witness ∑ x p ( 0 , 0 ∣ x , x ) \sum_x p(0,0|x,x) ∑ x p ( 0 , 0∣ x , x ) on the face F 0 \mathrm{F}_0 F 0 . Every box in C q c ∩ F 0 \mathrm{C}_{\mathrm{qc}} \cap\mathrm{F}_0 C qc ∩ F 0 , and hence every quantum box on this face, satisfies ∑ x p ( 0 , 0 ∣ x , x ) ≤ 1 \sum_x p(0,0|x,x) \le1 ∑ x p ( 0 , 0∣ x , x ) ≤ 1 (black, Corollary 2); values in the shaded region are post-quantum for boxes lying exactly on F 0 \mathrm{F}_0 F 0 . The optimal almost-quantum boxes (blue) give N η A Q e q ( N ) N\eta_{\mathrm{AQ}}^{\mathrm{eq}}(N) N η AQ eq ( N ) , which exceeds 1 1 1 for every N ≥ 9 N \ge9 N ≥ 9 . The box p ⋆ p^\star p ⋆ (green) gives N / 17 N/17 N /17 , which exceeds 1 1 1 for every N ≥ 18 N \ge18 N ≥ 18 . The optimal level-1 boxes (orange) give N η C V e c e q ( N ) = N 2 / [ 8 ( N − 2 ) ] N\eta_{\mathrm{CVec}}^{\mathrm{eq}}(N) = N^2/[8(N-2)] N η CVec eq ( N ) = N 2 / [ 8 ( N − 2 )] , which exceeds 1 1 1 for every N ≥ 5 N \ge5 N ≥ 5 . Dotted lines and coloured labels on the horizontal axis mark the first violations.
Symmetry reduction to two small matrix inequalities. By Lemma 3, computing η A Q e q ( N ) \eta_{\mathrm{AQ}}^{\mathrm{eq}}(N) η AQ eq ( N ) in Eq. (12) is a semidefinite program. A real symmetric matrix is positive semidefinite if and only if it is the Gram matrix of real vectors. So we maximize min x q x \min_x q_x min x q x over positive semidefinite matrices Γ \Gamma Γ , with rows and columns indexed by ψ \psi ψ and a x , b x , w x a_x,b_x,w_x a x , b x , w x (x ∈ [ N ] x \in[N] x ∈ [ N ] ), whose entries satisfy Eq. (10) with label-dependent values p A , x p_{A,x} p A , x , p B , x p_{B,x} p B , x and q x q_x q x . Here M ⪰ 0 M \succeq0 M ⪰ 0 means that the real symmetric matrix M M M is positive semidefinite. Equation (10) fixes every entry of Γ \Gamma Γ except the inner products between vectors of the same type at different labels, ⟨ a x , a y ⟩ \langle a_x,a_y\rangle ⟨ a x , a y ⟩ , ⟨ b x , b y ⟩ \langle b_x,b_y\rangle ⟨ b x , b y ⟩ and ⟨ w x , w y ⟩ \langle w_x,w_y\rangle ⟨ w x , w y ⟩ for x ≠ y x \ne y x = y . These are free variables.
Step 1 (symmetrization): Relabelling x ↦ π ( x ) x \mapsto\pi(x) x ↦ π ( x ) , π ∈ S N \pi\in S_N π ∈ S N , maps feasible matrices to feasible matrices and leaves the objective unchanged. The feasible set is convex and min x q x \min_x q_x min x q x is concave. Hence the average Γ ‾ = 1 N ! ∑ π ∈ S N Γ π \overline{\Gamma} = \frac{1}{N!}\sum_{\pi\in S_N}\Gamma^\pi Γ = N ! 1 ∑ π ∈ S N Γ π of the relabelled copies of a feasible Γ \Gamma Γ is feasible and has an objective value at least as large. The entries of Γ ‾ \overline{\Gamma} Γ depend only on whether two labels coincide. We may therefore assume, without loss of generality, that
⟨ ψ , a x ⟩ = p A , ⟨ ψ , b x ⟩ = p B , ⟨ ψ , w x ⟩ = q , ⟨ a x , a y ⟩ = α , ⟨ b x , b y ⟩ = β , ⟨ w x , w y ⟩ = ω ( x ≠ y ) . \langle\psi,a_x\rangle= p_A,\quad\langle\psi,b_x\rangle= p_B,\quad\langle\psi,w_x\rangle= q,\quad\langle a_x,a_y\rangle= \alpha,\quad\langle b_x,b_y\rangle= \beta,\quad\langle w_x,w_y\rangle= \omega\quad(x \ne y). ⟨ ψ , a x ⟩ = p A , ⟨ ψ , b x ⟩ = p B , ⟨ ψ , w x ⟩ = q , ⟨ a x , a y ⟩ = α , ⟨ b x , b y ⟩ = β , ⟨ w x , w y ⟩ = ω ( x = y ) .
This leaves six real parameters p A , p B , q , α , β , ω p_A,p_B,q,\alpha,\beta,\omega p A , p B , q , α , β , ω , and the objective becomes q q q .
Step 2 (block structure): Order the vectors as ψ , ( a 1 , b 1 , w 1 ) , … , ( a N , b N , w N ) \psi,(a_1,b_1,w_1),\ldots,(a_N,b_N,w_N) ψ , ( a 1 , b 1 , w 1 ) , … , ( a N , b N , w N ) , and set r = r = r =
r = ( p A , p B , q ) T r=(p_A,p_B,q)^{\mathsf T} r = ( p A , p B , q ) T
D = ( p A q q q p B q q q q ) , E = ( α 0 0 0 β 0 0 0 ω ) (16) D=\begin{pmatrix}p_A&q&q\\q&p_B&q\\q&q&q\end{pmatrix},\qquad E=\begin{pmatrix}\alpha&0&0\\0&\beta&0\\0&0&\omega\end{pmatrix} \tag*{(16)} D = p A q q q p B q q q q , E = α 0 0 0 β 0 0 0 ω (16)
Here D D D collects the inner products within one label, and E E E those between different labels. E E E is diagonal because Eq. (10) sets ⟨ a x , b y ⟩ = ⟨ a x , w y ⟩ = ⟨ b x , w y ⟩ = 0 \langle a_x,b_y\rangle=\langle a_x,w_y\rangle=\langle b_x,w_y\rangle=0 ⟨ a x , b y ⟩ = ⟨ a x , w y ⟩ = ⟨ b x , w y ⟩ = 0 for x ≠ y x\ne y x = y . For illustration, take N = 2 N=2 N = 2 . With rows and columns ordered as ψ , a 1 , b 1 , w 1 , a 2 , b 2 , w 2 \psi,a_1,b_1,w_1,a_2,b_2,w_2 ψ , a 1 , b 1 , w 1 , a 2 , b 2 , w 2 , Eq. (10) and Step 1 give
Γ ∣ N = 2 = ψ a 1 b 1 w 1 a 2 b 2 w 2 ψ 1 p A p B q p A p B q a 1 p A p A q q α 0 0 b 1 p B q p B q 0 β 0 w 1 q q q q 0 0 ω a 2 p A α 0 0 p A q q b 2 p B 0 β 0 q p B q w 2 q 0 0 ω q q q \left.\Gamma\right|_{N=2}=
\begin{array}{c|ccccccc}
&\psi&a_1&b_1&w_1&a_2&b_2&w_2\\
\hline
\psi&1&p_A&p_B&q&p_A&p_B&q\\
a_1&p_A&p_A&q&q&\alpha&0&0\\
b_1&p_B&q&p_B&q&0&\beta&0\\
w_1&q&q&q&q&0&0&\omega\\
\hline
a_2&p_A&\alpha&0&0&p_A&q&q\\
b_2&p_B&0&\beta&0&q&p_B&q\\
w_2&q&0&0&\omega&q&q&q
\end{array} Γ ∣ N = 2 = ψ a 1 b 1 w 1 a 2 b 2 w 2 ψ 1 p A p B q p A p B q a 1 p A p A q q α 0 0 b 1 p B q p B q 0 β 0 w 1 q q q q 0 0 ω a 2 p A α 0 0 p A q q b 2 p B 0 β 0 q p B q w 2 q 0 0 ω q q q
The first row and column consist of 1 1 1 and copies of r r r , every diagonal 3 × 3 3\times3 3 × 3 block equals D D D , and every off-diagonal block equals E E E . The same pattern holds for every N N N :
Γ = ( 1 1 T ⊗ r T 1 ⊗ r I N ⊗ D + ( J N − I N ) ⊗ E ) , \Gamma=
\begin{pmatrix}
1&\mathbf{1}^{\mathsf T}\otimes r^{\mathsf T}\\
\mathbf{1}\otimes r&I_N\otimes D+(J_N-I_N)\otimes E
\end{pmatrix}, Γ = ( 1 1 ⊗ r 1 T ⊗ r T I N ⊗ D + ( J N − I N ) ⊗ E ) ,
where 1 ∈ R N \mathbf{1}\in\mathbb{R}^N 1 ∈ R N is the all-ones vector and J N = 11 T J_N=\mathbf{1}\mathbf{1}^{\mathsf T} J N = 1 1 T .
Step 3 (block diagonalization): Let u 0 = 1 / N , u 1 , … , u N − 1 u_0=1/\sqrt{N},u_1,\ldots,u_{N-1} u 0 = 1/ N , u 1 , … , u N − 1 be an orthonormal basis of R N \mathbb{R}^N R N , and let U U U be the matrix with columns u k u_k u k . Replace the label vectors by the combinations
a ^ k = ∑ x ( u k ) x a x , b ^ k = ∑ x ( u k ) x b x , w ^ k = ∑ x ( u k ) x w x ( k = 0 , … , N − 1 ) , \hat{a}_k=\sum_x(u_k)_x a_x,\qquad\hat{b}_k=\sum_x(u_k)_x b_x,\qquad\hat{w}_k=\sum_x(u_k)_x w_x\qquad(k=0,\ldots,N-1), a ^ k = x ∑ ( u k ) x a x , b ^ k = x ∑ ( u k ) x b x , w ^ k = x ∑ ( u k ) x w x ( k = 0 , … , N − 1 ) ,
which is the orthogonal change of basis 1 ⊕ ( U ⊗ I 3 ) 1\oplus(U\otimes I_3) 1 ⊕ ( U ⊗ I 3 ) applied to Γ \Gamma Γ ; in particular, a ^ 0 = N − 1 / 2 ∑ x a x \hat{a}_0=N^{-1/2}\sum_xa_x a ^ 0 = N − 1/2 ∑ x a x is the label average. For v , v ′ ∈ { a , b , w } v,v'\in\{a,b,w\} v , v ′ ∈ { a , b , w } , the entries of Γ \Gamma Γ are ⟨ v x , v y ′ ⟩ = δ x y ( D − E ) v v ′ + E v v ′ \langle v_x,v'_y\rangle=\delta_{xy}(D-E)_{vv'}+E_{vv'} ⟨ v x , v y ′ ⟩ = δ x y ( D − E ) v v ′ + E v v ′ and ⟨ ψ , v x ⟩ = r v \langle\psi,v_x\rangle=r_v ⟨ ψ , v x ⟩ = r v . Using ∑ x ( u k ) x ( u l ) x = δ k l \sum_x(u_k)_x(u_l)_x=\delta_{kl} ∑ x ( u k ) x ( u l ) x = δ k l and ∑ x ( u k ) x = 1 T u k = N δ k 0 \sum_x(u_k)_x=\mathbf{1}^{\mathsf T}u_k=\sqrt{N}\,\delta_{k0} ∑ x ( u k ) x = 1 T u k = N δ k 0 , we obtain
⟨ ψ , v ^ k ⟩ = N δ k 0 r v , ⟨ v ^ k , v ^ l ′ ⟩ = δ k l ( D − E ) v v ′ + N δ k 0 δ l 0 E v v ′ . \langle\psi,\hat{v}_k\rangle=\sqrt{N}\,\delta_{k0}\,r_v,\qquad\langle\hat{v}_k,\hat{v}'_l\rangle=\delta_{kl}(D-E)_{vv'}+N\delta_{k0}\delta_{l0}E_{vv'}. ⟨ ψ , v ^ k ⟩ = N δ k 0 r v , ⟨ v ^ k , v ^ l ′ ⟩ = δ k l ( D − E ) v v ′ + N δ k 0 δ l 0 E v v ′ .
For N = 2 N=2 N = 2 , for instance, u 0 = ( 1 , 1 ) / 2 u_0=(1,1)/\sqrt{2} u 0 = ( 1 , 1 ) / 2 and u 1 = ( 1 , − 1 ) / 2 u_1=(1,-1)/\sqrt{2} u 1 = ( 1 , − 1 ) / 2 , so that a ^ 0 = ( a 1 + a 2 ) / 2 \hat{a}_0=(a_1+a_2)/\sqrt{2} a ^ 0 = ( a 1 + a 2 ) / 2 is the label average and a ^ 1 = ( a 1 − a 2 ) / 2 \hat{a}_1=(a_1-a_2)/\sqrt{2} a ^ 1 = ( a 1 − a 2 ) / 2 the label difference, and similarly for b b b and w w w . In the new basis Γ \Gamma Γ takes the block form
Γ ≅ ( 1 N r T 0 ⋯ 0 N r D + ( N − 1 ) E 0 ⋯ 0 0 0 D − E ⋯ 0 ⋮ ⋮ ⋮ ⋱ ⋮ 0 0 0 ⋯ D − E ) . \Gamma\cong
\begin{pmatrix}
1&\sqrt{N}\,r^{\mathsf T}&0&\cdots&0\\
\sqrt{N}\,r&D+(N-1)E&0&\cdots&0\\
0&0&D-E&\cdots&0\\
\vdots&\vdots&\vdots&\ddots&\vdots\\
0&0&0&\cdots&D-E
\end{pmatrix}. Γ ≅ 1 N r 0 ⋮ 0 N r T D + ( N − 1 ) E 0 ⋮ 0 0 0 D − E ⋮ 0 ⋯ ⋯ ⋯ ⋱ ⋯ 0 0 0 ⋮ D − E .
That is, Γ ≅ L ⊕ ( D − E ) ⊕ ⋯ ⊕ ( D − E ) \Gamma\cong L \oplus(D-E) \oplus\cdots\oplus(D-E) Γ ≅ L ⊕ ( D − E ) ⊕ ⋯ ⊕ ( D − E ) with N − 1 N-1 N − 1 copies, with
L = ( 1 N r T N r D + ( N − 1 ) E ) = ( 1 N p A N p B N q N p A p A + ( N − 1 ) α q q N p B q p B + ( N − 1 ) β q N q q q q + ( N − 1 ) ω ) L=\begin{pmatrix}1 & \sqrt{N}r^{\mathsf T}\\ \sqrt{N}r & D+(N-1)E\end{pmatrix}
=\begin{pmatrix}
1 & \sqrt{N}p_A & \sqrt{N}p_B & \sqrt{N}q\\
\sqrt{N}p_A & p_A+(N-1)\alpha& q & q\\
\sqrt{N}p_B & q & p_B+(N-1)\beta& q\\
\sqrt{N}q & q & q & q+(N-1)\omega
\end{pmatrix} L = ( 1 N r N r T D + ( N − 1 ) E ) = 1 N p A N p B N q N p A p A + ( N − 1 ) α q q N p B q p B + ( N − 1 ) β q N q q q q + ( N − 1 ) ω
and
D − E = ( p A − α q q q p B − β q q q q − ω ) . D-E=\begin{pmatrix}
p_A-\alpha& q & q\\
q & p_B-\beta& q\\
q & q & q-\omega
\end{pmatrix}. D − E = p A − α q q q p B − β q q q q − ω .
An orthogonal change of basis preserves positive semidefiniteness, and a block-diagonal matrix is positive semidefinite if and only if each block is. Hence, for N ≥ 2 N \ge2 N ≥ 2 , Γ ⪰ 0 \Gamma\succeq0 Γ ⪰ 0 if and only if
M 1 ≡ D − E ⪰ 0 and L ⪰ 0. (17) M_1 \equiv D-E \succeq0 \qquad\text{and} \qquad L \succeq0. \tag*{(17)} M 1 ≡ D − E ⪰ 0 and L ⪰ 0. (17)
Consequently,
η A Q e q ( N ) = max { q : ( p A , p B , q , α , β , ω ) ∈ R 6 satisfy Eq. x r e f ‘ ( 17 ) ‘ } , \eta_{\mathrm{AQ}}^{\mathrm{eq}}(N)=\max\left\{q:(p_A,p_B,q,\alpha,\beta,\omega)\in\mathbb{R}^{6}\text{ satisfy Eq. }{xref}`(17)`\right\}, η AQ eq ( N ) = max { q : ( p A , p B , q , α , β , ω ) ∈ R 6 satisfy Eq. x r e f ‘ ( 17 ) ‘ } ,
a semidefinite program in six real variables with one 3 × 3 3\times3 3 × 3 and one 4 × 4 4\times4 4 × 4 matrix inequality. The feasible set is compact, so the maximum is attained.
Proof of Theorem 3. By the symmetry reduction above, η A Q e q ( N ) \eta_{\mathrm{AQ}}^{\mathrm{eq}}(N) η AQ eq ( N ) is the optimal value of the semidefinite program
maximize q over ( p A , p B , q , α , β , ω ) ∈ R 6 subject to M 1 ⪰ 0 , L ⪰ 0. (18) \text{maximize }q\quad\text{over }(p_A,p_B,q,\alpha,\beta,\omega)\in\mathbb{R}^{6}\quad\text{subject to }M_1\succeq0,\quad L\succeq0. \tag*{(18)} maximize q over ( p A , p B , q , α , β , ω ) ∈ R 6 subject to M 1 ⪰ 0 , L ⪰ 0. (18)
We prove matching bounds: an upper bound from an explicit dual certificate, and a lower bound from explicit feasible points. Throughout, e a , e b , e w e_a,e_b,e_w e a , e b , e w denote the standard basis of R 3 \mathbb{R}^{3} R 3 , ordered as the rows of D D D and E E E , and Δ N = 17 N 2 − 80 N + 64 \Delta_N=17N^2-80N+64 Δ N = 17 N 2 − 80 N + 64 . Since L 11 = 1 > 0 L_{11}=1>0 L 11 = 1 > 0 , L ⪰ 0 L\succeq0 L ⪰ 0 if and only if its Schur complement
S ≡ D + ( N − 1 ) E − N r r T = ( D − E ) + N ( E − r r T ) S\equiv D+(N-1)E-Nrr^{\mathsf T}=(D-E)+N(E-rr^{\mathsf T}) S ≡ D + ( N − 1 ) E − N r r T = ( D − E ) + N ( E − r r T )
is positive semidefinite; we use this form to check feasibility.
tr ( Y M 1 ) + tr ( Z L ) ≥ 0. \operatorname{tr}(YM_1)+\operatorname{tr}(ZL)\ge0. tr ( Y M 1 ) + tr ( Z L ) ≥ 0.
The left-hand side is an affine function of the six parameters. Suppose Y Y Y and Z Z Z are chosen so that the coefficients of p A , p B , α , β , ω p_A,p_B,\alpha,\beta,\omega p A , p B , α , β , ω vanish and the constant term equals 1 1 1 . Then the left-hand side equals 1 − c q 1-cq 1 − c q for some number c c c , and the inequality gives q ≤ 1 / c q\le1/c q ≤ 1/ c whenever c > 0 c>0 c > 0 .
Upper bound: the certificate. For t ∈ [ 0 , 2 ] t\in[0,2] t ∈ [ 0 , 2 ] , let
ρ t = − N + 2 ( N − 1 ) t − t 2 N , y t = ( t , t , ρ t ) , z t = ( 1 , − t 2 2 N , − t 2 2 N , ρ t N ) , b = ( 0 , 1 , − 1 , 0 ) , \rho_t=-\frac{N+2(N-1)t-t^2}{N},\qquad y_t=(t,t,\rho_t),\qquad z_t=\left(1,-\frac{t^2}{2\sqrt{N}},-\frac{t^2}{2\sqrt{N}},\frac{\rho_t}{\sqrt{N}}\right),\qquad b=(0,1,-1,0), ρ t = − N N + 2 ( N − 1 ) t − t 2 , y t = ( t , t , ρ t ) , z t = ( 1 , − 2 N t 2 , − 2 N t 2 , N ρ t ) , b = ( 0 , 1 , − 1 , 0 ) ,
and
Y t = N − 1 N y t y t T , Z t = z t z t T + μ t b b T , μ t = t 2 ( 4 − t 2 ) 4 N . Y_t = \frac{N-1}{N} y_t y_t^{\mathsf{T}}, \qquad Z_t = z_t z_t^{\mathsf{T}} + \mu_t bb^{\mathsf{T}}, \qquad\mu_t = \frac{t^2(4-t^2)}{4N}. Y t = N N − 1 y t y t T , Z t = z t z t T + μ t b b T , μ t = 4 N t 2 ( 4 − t 2 ) .
Both matrices are positive semidefinite, since v v T ⪰ 0 vv^{\mathsf{T}} \succeq0 v v T ⪰ 0 for every vector v v v and μ t ≥ 0 \mu_t \ge0 μ t ≥ 0 for t ≤ 2 t \le2 t ≤ 2 . Expanding the traces, one finds that the coefficients of p A , p B , α , β , ω p_A,p_B,\alpha,\beta,\omega p A , p B , α , β , ω vanish identically in t t t , that the constant term is ( Z t ) 11 = 1 (Z_t)_{11}=1 ( Z t ) 11 = 1 , and that
tr ( Y t M 1 ) + tr ( Z t L ) = 1 − c t q , c t = 1 + N − 1 N 2 h ( t ) , h ( t ) = N 2 − ( N − 2 t − t 2 ) 2 . (19) \operatorname{tr}(Y_tM_1) + \operatorname{tr}(Z_tL) = 1-c_tq, \qquad c_t = 1+\frac{N-1}{N^2}h(t), \qquad h(t)=N^2-\left(N-2t-t^2\right)^2. \tag*{(19)} tr ( Y t M 1 ) + tr ( Z t L ) = 1 − c t q , c t = 1 + N 2 N − 1 h ( t ) , h ( t ) = N 2 − ( N − 2 t − t 2 ) 2 . (19)
Hence q ≤ 1 / c t q \le1/c_t q ≤ 1/ c t for every t ∈ [ 0 , 2 ] t \in[0,2] t ∈ [ 0 , 2 ] with c t > 0 c_t>0 c t > 0 . The certificate ( Y t , Z t ) (Y_t,Z_t) ( Y t , Z t ) is a feasible point of the dual program; how it was found plays no role in the proof, which needs only the identity (19) .
Upper bound: the best t t t . The bound 1 / c t 1/c_t 1/ c t is smallest when h ( t ) h(t) h ( t ) is largest. By Eq. (19) , h ( t ) ≤ N 2 h(t) \le N^2 h ( t ) ≤ N 2 , with equality if and only if t 2 + 2 t = N t^2+2t=N t 2 + 2 t = N , i.e., t = t 0 ≡ N + 1 − 1 t=t_0\equiv\sqrt{N+1}-1 t = t 0 ≡ N + 1 − 1 . Moreover t 0 ≤ 2 t_0\le2 t 0 ≤ 2 if and only if N ≤ 8 N\le8 N ≤ 8 .
For 3 ≤ N ≤ 8 3\le N\le8 3 ≤ N ≤ 8 , take t = t 0 ∈ [ 0 , 2 ] t=t_0\in[0,2] t = t 0 ∈ [ 0 , 2 ] . Then h ( t 0 ) = N 2 h(t_0)=N^2 h ( t 0 ) = N 2 , so c t 0 = N c_{t_0}=N c t 0 = N and q ≤ 1 / N q\le1/N q ≤ 1/ N .
For N ≥ 8 N\ge8 N ≥ 8 , N − 2 t − t 2 ≥ N − 8 ≥ 0 N-2t-t^2\ge N-8\ge0 N − 2 t − t 2 ≥ N − 8 ≥ 0 on [ 0 , 2 ] [0,2] [ 0 , 2 ] and decreases with t t t , so h h h is largest at t = 2 t=2 t = 2 , where h ( 2 ) = N 2 − ( N − 8 ) 2 = 16 ( N − 4 ) h(2)=N^2-(N-8)^2=16(N-4) h ( 2 ) = N 2 − ( N − 8 ) 2 = 16 ( N − 4 ) . Then c 2 = 1 + 16 ( N − 1 ) ( N − 4 ) / N 2 = Δ N / N 2 > 0 c_2=1+16(N-1)(N-4)/N^2=\Delta_N/N^2>0 c 2 = 1 + 16 ( N − 1 ) ( N − 4 ) / N 2 = Δ N / N 2 > 0 , so q ≤ N 2 / Δ N q\le N^2/\Delta_N q ≤ N 2 / Δ N .
Lower bound for 3 ≤ N ≤ 8 3\le N\le8 3 ≤ N ≤ 8 . The parties share a uniformly random label u ∈ [ N ] u\in[N] u ∈ [ N ] , and each outputs 0 exactly when their setting equals u u u . Outcome ( 0 , 0 ) (0,0) ( 0 , 0 ) then occurs only when x = y = u x=y=u x = y = u , so this local box lies in F 0 F_0 F 0 , and p ( 0 , 0 ∣ x , x ) = Pr ( u = x ) = 1 / N p(0,0\mid x,x)=\Pr(u=x)=1/N p ( 0 , 0 ∣ x , x ) = Pr ( u = x ) = 1/ N . Local boxes are almost quantum, so η A Q e q ( N ) ≥ 1 / N \eta_{\mathrm{AQ}}^{\mathrm{eq}}(N)\ge1/N η AQ eq ( N ) ≥ 1/ N .
q N = N 2 Δ N , p A = p B = 3 N 2 − 18 N + 16 Δ N , α = β = 3 N 2 − 28 N + 32 2 Δ N , ω = N 2 ( N − 8 ) ( 5 N − 8 ) Δ N . (20) q_N=\frac{N^2}{\Delta_N}, \qquad p_A=p_B=\frac{3N^2-18N+16}{\Delta_N}, \qquad\alpha=\beta=\frac{3N^2-28N+32}{2\Delta_N}, \qquad\omega=\frac{N^2(N-8)}{(5N-8)\Delta_N}. \tag*{(20)} q N = Δ N N 2 , p A = p B = Δ N 3 N 2 − 18 N + 16 , α = β = 2 Δ N 3 N 2 − 28 N + 32 , ω = ( 5 N − 8 ) Δ N N 2 ( N − 8 ) . (20)
Because p A = p B p_A=p_B p A = p B and α = β \alpha=\beta α = β , both M 1 M_1 M 1 and S S S are invariant under exchanging e a e_a e a and e b e_b e b . In the basis { ( e a − e b ) / 2 , ( e a + e b ) / 2 , e w } \{(e_a-e_b)/\sqrt{2},(e_a+e_b)/\sqrt{2},e_w\} {( e a − e b ) / 2 , ( e a + e b ) / 2 , e w } they therefore split into a 1 × 1 1\times1 1 × 1 block and a 2 × 2 2\times2 2 × 2 block:
M 1 ≅ N ( N − 8 ) 2 Δ N ⊕ N Δ N K + , S ≅ 3 N ( N − 1 ) ( N − 8 ) 2 Δ N ⊕ N ( N − 1 ) ( N − 8 ) ( 3 N − 8 ) Δ N 2 K − , M_1 \cong\frac{N(N-8)}{2\Delta_N}\oplus\frac{N}{\Delta_N}K_+, \qquad S\cong\frac{3N(N-1)(N-8)}{2\Delta_N}\oplus\frac{N(N-1)(N-8)(3N-8)}{\Delta_N^2}K_-, M 1 ≅ 2 Δ N N ( N − 8 ) ⊕ Δ N N K + , S ≅ 2 Δ N 3 N ( N − 1 ) ( N − 8 ) ⊕ Δ N 2 N ( N − 1 ) ( N − 8 ) ( 3 N − 8 ) K − ,
where
K ± = ( 5 N − 8 2 ± 2 N ± 2 N 4 N 2 5 N − 8 ) . K_{\pm}=\begin{pmatrix}
\frac{5N-8}{2} & \pm\sqrt{2}N\\
\pm\sqrt{2}N & \frac{4N^2}{5N-8}
\end{pmatrix}. K ± = ( 2 5 N − 8 ± 2 N ± 2 N 5 N − 8 4 N 2 ) .
Each K ± K_{\pm} K ± has positive diagonal entries and determinant 2 N 2 − 2 N 2 = 0 2N^2-2N^2=0 2 N 2 − 2 N 2 = 0 , so it is positive semidefinite (of rank one). For N ≥ 8 N\ge8 N ≥ 8 all prefactors are nonnegative, so M 1 ⪰ 0 M_1\succeq0 M 1 ⪰ 0 and S ⪰ 0 S\succeq0 S ⪰ 0 , and the point (20) is feasible for (18) . Lemma 3 turns it into an AQ box in F 0 F_0 F 0 with p ( 0 , 0 ∣ x , x ) = q N p(0,0\mid x,x)=q_N p ( 0 , 0 ∣ x , x ) = q N , so η A Q e q ( N ) ≥ N 2 / Δ N \eta_{\mathrm{AQ}}^{\mathrm{eq}}(N)\ge N^2/\Delta_N η AQ eq ( N ) ≥ N 2 / Δ N .
Conclusion. The upper and lower bounds coincide, which proves Eq. (14) ; at N = 8 N=8 N = 8 both cases give 1 / 8 1/8 1/8 . The value decreases monotonically in N N N : 1 / N 1/N 1/ N does so for N ≤ 8 N\le8 N ≤ 8 , and for N ≥ 8 N\ge8 N ≥ 8
d d N N 2 Δ N = − 16 N ( 5 N − 8 ) Δ N 2 < 0 , lim N → ∞ N 2 Δ N = 1 17 . \frac{d}{dN}\frac{N^2}{\Delta_N}=-\frac{16N(5N-8)}{\Delta_N^2}<0, \qquad\lim_{N\to\infty}\frac{N^2}{\Delta_N}=\frac{1}{17}. d N d Δ N N 2 = − Δ N 2 16 N ( 5 N − 8 ) < 0 , N → ∞ lim Δ N N 2 = 17 1 .
By Theorem 1, the quantum value is 1 / N 1/N 1/ N , and for N ≥ 8 N\ge8 N ≥ 8
N 2 Δ N − 1 N = N 3 − Δ N N Δ N = ( N − 1 ) ( N − 8 ) 2 N Δ N , \frac{N^2}{\Delta_N}-\frac{1}{N}=\frac{N^3-\Delta_N}{N\Delta_N}=\frac{(N-1)(N-8)^2}{N\Delta_N}, Δ N N 2 − N 1 = N Δ N N 3 − Δ N = N Δ N ( N − 1 ) ( N − 8 ) 2 ,
which is Eq. (15) . It is positive if and only if N ≥ 9 N \ge9 N ≥ 9 .
The box p ⋆ p^\star p ⋆ . As N → ∞ N \to\infty N → ∞ , the parameters {(20)} converge to
( p A , p B , q ) = ( 3 17 , 3 17 , 1 17 ) , α = β = 3 34 , ω = 1 85 , (p_A,p_B,q)=\left(\frac{3}{17},\frac{3}{17},\frac{1}{17}\right),\qquad\alpha=\beta=\frac{3}{34},\qquad\omega=\frac{1}{85}, ( p A , p B , q ) = ( 17 3 , 17 3 , 17 1 ) , α = β = 34 3 , ω = 85 1 , the values realized by the vectors {(11)}. These limiting values are feasible for every N N N . Indeed, D − E D-E D − E has eigenvalues 0 , 1 / 34 , 33 / 170 0,1/34,33/170 0 , 1/34 , 33/170 and E − r r T E-rr^{\mathsf T} E − r r T has eigenvalues 0 , 99 / 2890 , 3 / 34 0,99/2890,3/34 0 , 99/2890 , 3/34 , so M 1 = D − E ⪰ 0 M_1=D-E\succeq0 M 1 = D − E ⪰ 0 and S = ( D − E ) + N ( E − r r T ) ⪰ 0 S=(D-E)+N(E-rr^{\mathsf T})\succeq0 S = ( D − E ) + N ( E − r r T ) ⪰ 0 for all N N N . Thus p ⋆ p^\star p ⋆ attains 1 / 17 1/17 1/17 for every N N N . No construction valid for all N N N at once can do better: a value q q q attained for every N N N satisfies q ≤ η A Q e q ( N ) q\le\eta_{\mathrm{AQ}}^{\mathrm{eq}}(N) q ≤ η AQ eq ( N ) for every N N N , and since η A Q e q ( N ) \eta_{\mathrm{AQ}}^{\mathrm{eq}}(N) η AQ eq ( N ) decreases to 1 / 17 1/17 1/17 , q ≤ 1 / 17 q\le1/17 q ≤ 1/17 .
The separation across correlation models
Combining Corollary [1 ] , Theorems [2 ] and [3 ] , and Proposition [2 ] of § 8 with the monotonicity of η Ω \eta_\Omega η Ω along the chain {(2)} locates the separation precisely.
Theorem 4. For every N ≥ 3 N \ge3 N ≥ 3 :
(i) η Ω ( N ) = η Ω e q ( N ) = 1 / N \eta_\Omega(N)=\eta_\Omega^{\mathrm{eq}}(N)=1/N η Ω ( N ) = η Ω eq ( N ) = 1/ N for Ω ∈ { C L , C q , C q s , C q a , C q c } \Omega\in\{\mathrm{C_L},\mathrm{C_q},\mathrm{C_{qs}},\mathrm{C_{qa}},\mathrm{C_{qc}}\} Ω ∈ { C L , C q , C qs , C qa , C qc } ;
(ii) η A Q ( N ) ≥ 1 / 19 \eta_{\mathrm{AQ}}(N)\ge1/19 η AQ ( N ) ≥ 1/19 , while η A Q e q ( N ) \eta_{\mathrm{AQ}}^{\mathrm{eq}}(N) η AQ eq ( N ) , given by Eq. (14) , exceeds 1 / N 1/N 1/ N if and only if N ≥ 9 N\ge9 N ≥ 9 and decreases to 1 / 17 1/17 1/17 ;
(iii) η C V e c e q ( 3 ) = 1 / 3 \eta_{\mathrm{CVec}}^{\mathrm{eq}}(3)=1/3 η CVec eq ( 3 ) = 1/3 and η C V e c e q ( N ) = N / [ 8 ( N − 2 ) ] \eta_{\mathrm{CVec}}^{\mathrm{eq}}(N)=N/[8(N-2)] η CVec eq ( N ) = N / [ 8 ( N − 2 )] for N ≥ 4 N\ge4 N ≥ 4 , which exceeds 1 / N 1/N 1/ N if and only if N ≥ 5 N\ge5 N ≥ 5 and decreases to 1 / 8 1/8 1/8 ; moreover, η C V e c ( N ) ≥ N / ( 10 N − 16 ) > 1 / 10 \eta_{\mathrm{CVec}}(N)\ge N/(10N-16)>1/10 η CVec ( N ) ≥ N / ( 10 N − 16 ) > 1/10 for N ≥ 4 N\ge4 N ≥ 4 ; and
(iv) η C N S ( N ) = 1 \eta_{\mathrm{CNS}}(N)=1 η CNS ( N ) = 1 .
In particular, η C V e c e q ( N ) > η A Q e q ( N ) \eta_{\mathrm{CVec}}^{\mathrm{eq}}(N)>\eta_{\mathrm{AQ}}^{\mathrm{eq}}(N) η CVec eq ( N ) > η AQ eq ( N ) for every N ≥ 5 N\ge5 N ≥ 5 , and hence C A Q ⊊ C V e c \mathrm{C_{AQ}}\subsetneq\mathrm{C_{Vec}} C AQ ⊊ C Vec .
Parts (i) and (ii) restate Corollary [1 ] , Theorems [2 ] and [3 ] , and the remark after Eq. (12) . Part (iii) is Proposition [2 ] , proved in § 8 , combined with Eq. (13) , whose right-hand side equals N / ( 10 N − 16 ) N/(10N-16) N / ( 10 N − 16 ) for η e q = N / [ 8 ( N − 2 ) ] \eta^{\mathrm{eq}}=N/[8(N-2)] η eq = N / [ 8 ( N − 2 )] . The final statement compares parts (ii) and (iii) (see the end of § 8 ); since η C V e c e q ( N ) \eta_{\mathrm{CVec}}^{\mathrm{eq}}(N) η CVec eq ( N ) is attained, every box that attains it with N ≥ 5 N\ge5 N ≥ 5 lies in C V e c ∖ C A Q \mathrm{C_{Vec}}\setminus\mathrm{C_{AQ}} C Vec ∖ C AQ . Part (iv) follows from the nonsignalling box with p ( a , b ∣ x , y ) = 1 / 2 p(a,b\mid x,y)=1/2 p ( a , b ∣ x , y ) = 1/2 if a ⊕ b = 1 { x = y } a\oplus b=1\{x=y\} a ⊕ b = 1 { x = y } and 0 0 0 otherwise: Alice inputs x = s x=s x = s and sends m = a m=a m = a , and Bob inputs y = t y=t y = t and outputs G = m ⊕ b = 1 { s = t } G=m\oplus b=1\{s=t\} G = m ⊕ b = 1 { s = t } , which is always conclusive and correct. The unbounded gap therefore opens between the adjacent sets C q c \mathrm{C_{qc}} C qc and C A Q \mathrm{C_{AQ}} C AQ , which differ only in whether Alice’s and Bob’s observables commute as operators or merely on the state. Consequently, the separation does not depend on the resolution of Tsirelson’s problem [33 , 43 ] : neither infinite-dimensional entanglement nor the commuting-operator framework of quantum field theory improves on shared randomness for this task. At the other extreme, general nonsignalling correlations solve the task perfectly, as expected from the triviality of communication complexity with PR-type boxes [13 , 14 ] . Parts (ii) and (iii) locate a second, bounded separation, between C A Q \mathrm{C_{AQ}} C AQ and C V e c \mathrm{C_{Vec}} C Vec : the optimal certificates of equality differ for every N ≥ 5 N\ge5 N ≥ 5 , and their limits, 1 / 17 1/17 1/17 and 1 / 8 1/8 1/8 , differ by more than a factor of two.
An exact-zero (face) witness of post-quantumness
Theorem 1 also yields a simple certificate that a given box is not quantum, provided the box lies exactly on the face F 0 F_0 F 0 . For a binary-outcome box p ∈ F 0 p\in F_0 p ∈ F 0 , the protocol of (a) is a zero-error one-bit protocol, and Eq. (6) becomes a linear inequality on the box.
Corollary 2 (Exact-zero (face) witness). For N ≥ 3 N \ge3 N ≥ 3 , every binary-outcome box p ∈ C q c ∩ F 0 p \in\mathrm{C}_{\mathrm{qc}} \cap\mathrm{F}_{0} p ∈ C qc ∩ F 0 satisfies
∑ x = 1 N p ( 0 , 0 ∣ x , x ) ≤ 1. (21) \sum_{x=1}^{N} p(0,0|x,x) \le1. \tag*{(21)} x = 1 ∑ N p ( 0 , 0∣ x , x ) ≤ 1. (21) The box p ⋆ p^\star p ⋆ violates Eq. (21) for every N ≥ 18 N \ge18 N ≥ 18 , and the optimal boxes of Theorem 3 violate it for every N ≥ 9 N \ge9 N ≥ 9 . Hence { p ⋆ } N ≥ 18 \{p^\star\}_{N\ge18} { p ⋆ } N ≥ 18 is an explicit family in C A Q ∖ C q c \mathrm{C}_{\mathrm{AQ}} \setminus\mathrm{C}_{\mathrm{qc}} C AQ ∖ C qc , lying outside C q \mathrm{C}_{q} C q , C q s \mathrm{C}_{qs} C q s and C q a \mathrm{C}_{qa} C q a as well.
Proof. For p ⋆ p^\star p ⋆ the left-hand side of Eq. (21) equals N / 17 N/17 N /17 , which exceeds 1 for N ≥ 18 N \ge18 N ≥ 18 . For the optimal boxes it equals 1 for N ≤ 8 N \le8 N ≤ 8 and N 3 17 N 2 − 80 N + 64 \frac{N^3}{17N^2-80N+64} 17 N 2 − 80 N + 64 N 3 for N ≥ 8 N \ge8 N ≥ 8 ; on the latter branch it exceeds 1 if and only if ( N − 1 ) ( N − 8 ) 2 > 0 (N-1)(N-8)^2 > 0 ( N − 1 ) ( N − 8 ) 2 > 0 , i.e., for N ≥ 9 N \ge9 N ≥ 9 (see Figure 2 ). □
Scope of the witness. Inequality (21) is not valid throughout the quantum set; it holds for boxes whose off-diagonal coincidences p ( 0 , 0 ∣ x , y ) p(0,0|x,y) p ( 0 , 0∣ x , y ) , x ≠ y x \ne y x = y , vanish exactly. Without this condition it fails already for local boxes. Suppose that with probability ε \varepsilon ε both parties output 0 for every setting, and otherwise both output 1. Then p ( 0 , 0 ∣ x , y ) = ε p(0,0|x,y)=\varepsilon p ( 0 , 0∣ x , y ) = ε for all x , y x,y x , y , while ∑ x p ( 0 , 0 ∣ x , x ) = N ε \sum_x p(0,0|x,x)=N\varepsilon ∑ x p ( 0 , 0∣ x , x ) = N ε exceeds 1 once N > 1 / ε N>1/\varepsilon N > 1/ ε . Arbitrarily small off-diagonal coincidences can thus coexist with a large value of the left-hand side, and a violation by a box that lies only approximately on F 0 \mathrm{F}_{0} F 0 certifies nothing. We therefore call Eq. (21) an exact-zero, or face, witness. Neither its growing violation nor the growing efficiency ratio implies noise tolerance or a lower bound on the distance from the quantum set; a quantitative version that allows nonzero off-diagonal coincidences is left for future work. For tensor-product models, Eq. (21) also follows from Claim 1 of Ref. [32 ] , which requires the zeros only for x > y x>y x > y (Appendix § 11 ).
The same triangular-zero bound holds for commuting-operator correlations: apply Alice’s Lüders tests A 0 ∣ N , … , A 0 ∣ 1 A_{0|N},\ldots,A_{0|1} A 0∣ N , … , A 0∣1 in decreasing label order. For v y = B 0 ∣ y ψ v_y=\sqrt{B_{0|y}}\psi v y = B 0∣ y ψ , every earlier test vanishes and leaves v y v_y v y unchanged. The sequential-test estimate (8) in the proof of Theorem 1, with the sector projector set to I, then gives ∑ y p ( 0 , 0 ∣ y , y ) ≤ 1 \sum_y p(0,0|y,y)\le1 ∑ y p ( 0 , 0∣ y , y ) ≤ 1 . Proposition 3 in Appendix § 11 gives the argument in full.
For small N N N , however, p ⋆ p^\star p ⋆ is not even nonlocal.
Proposition 1 (Locality of p ⋆ p^\star p ⋆ ). Every local box on the face F 0 \mathrm{F}_{0} F 0 satisfies
∑ x = 1 N p ( 0 , 0 ∣ x , x ) + 1 N ∑ x = 1 N [ p ( 0 , 1 ∣ x , x ) + p ( 1 , 0 ∣ x , x ) ] ≤ 1. (22) \sum_{x=1}^{N}p(0,0|x,x)+\frac{1}{N}\sum_{x=1}^{N}\left[p(0,1|x,x)+p(1,0|x,x)\right]\le1. \tag*{(22)} x = 1 ∑ N p ( 0 , 0∣ x , x ) + N 1 x = 1 ∑ N [ p ( 0 , 1∣ x , x ) + p ( 1 , 0∣ x , x ) ] ≤ 1. (22) The box p ⋆ p^\star p ⋆ gives ( N + 4 ) / 17 (N+4)/17 ( N + 4 ) /17 on the left-hand side, and it is local if and only if N ≤ 13 N\le13 N ≤ 13 .
Proof. A local box is a mixture of deterministic strategies ( f , g ) (f,g) ( f , g ) , in which Alice outputs a = f ( x ) a=f(x) a = f ( x ) and Bob outputs b = g ( y ) b=g(y) b = g ( y ) . On F 0 \mathrm{F}_{0} F 0 , p ( 0 , 0 ∣ x , y ) = 0 p(0,0|x,y)=0 p ( 0 , 0∣ x , y ) = 0 for x ≠ y x\ne y x = y . This is a sum of nonnegative terms, one per strategy, so every strategy with positive weight lies on F 0 \mathrm{F}_{0} F 0 itself. Writing F A = f − 1 ( 0 ) F_A=f^{-1}(0) F A = f − 1 ( 0 ) and F B = g − 1 ( 0 ) F_B=g^{-1}(0) F B = g − 1 ( 0 ) for the inputs on which Alice and Bob output 0, this means that F A × F B F_A\times F_B F A × F B contains no pair ( x , y ) (x,y) ( x , y ) with x ≠ y x\ne y x = y . Hence one of the following holds: (i) F A = ∅ F_A=\varnothing F A = ∅ , i.e. Alice always outputs 1; (ii) F B = ∅ F_B=\varnothing F B = ∅ , i.e. Bob always outputs 1; (iii) F A = F B = { x 0 } F_A=F_B=\{x_0\} F A = F B = { x 0 } for a single label x 0 x_0 x 0 . It suffices to check each type, since the left-hand side is linear in p p p . In type (i), only the outcome pair ( 1 , 0 ) (1,0) ( 1 , 0 ) can occur, and only for x ∈ F B x\in F_B x ∈ F B , so the left-hand side equals ∣ F B ∣ / N ≤ 1 |F_B|/N\le1 ∣ F B ∣/ N ≤ 1 . Type (ii) gives ∣ F A ∣ / N ≤ 1 |F_A|/N\le1 ∣ F A ∣/ N ≤ 1 in the same way. In type (iii), the parties output ( 0 , 0 ) (0,0) ( 0 , 0 ) on input x 0 x_0 x 0 and ( 1 , 1 ) (1,1) ( 1 , 1 ) otherwise, so the left-hand side equals exactly 1.
For p ⋆ p^\star p ⋆ , p ( 0 , 0 ∣ x , x ) = 1 / 17 p(0,0|x,x)=1/17 p ( 0 , 0∣ x , x ) = 1/17 and p ( 0 , 1 ∣ x , x ) = p ( 1 , 0 ∣ x , x ) = 2 / 17 p(0,1|x,x)=p(1,0|x,x)=2/17 p ( 0 , 1∣ x , x ) = p ( 1 , 0∣ x , x ) = 2/17 , so the left-hand side equals ( N + 4 ) / 17 (N+4)/17 ( N + 4 ) /17 . This exceeds 1 if and only if N ≥ 14 N\ge14 N ≥ 14 .
A local model for N ≤ 13 N\le13 N ≤ 13 is constructed explicitly in Appendix § 10 . □
By Corollary 2, p ⋆ p^\star p ⋆ lies outside C q c \mathrm{C}_{\mathrm{qc}} C qc for N ≥ 18 N \ge18 N ≥ 18 . Whether it is quantum for 14 ≤ N ≤ 17 14 \le N \le17 14 ≤ N ≤ 17 is left open.
Longer messages and communication cost
We now let Alice send one of K K K messages m ∈ { 0 , … , K − 1 } m \in\{0,\ldots,K-1\} m ∈ { 0 , … , K − 1 } ; a k k k -bit message corresponds to K = 2 k K=2^k K = 2 k . Let η Ω ( K ) ( N ) \eta_{\Omega}^{(K)}(N) η Ω ( K ) ( N ) be the optimal worst-case conclusive probability with K K K messages and resources Ω \Omega Ω , so that η Ω = η Ω ( 2 ) \eta_{\Omega}=\eta_{\Omega}^{(2)} η Ω = η Ω ( 2 ) . Longer messages help quantum and classical players almost equally, so the gap to almost-quantum correlations persists.
Shared randomness. For K ≤ N K \le N K ≤ N the following protocol attains ( K − 1 ) / N (K-1)/N ( K − 1 ) / N . The parties share a uniformly random set L ⊂ [ N ] \mathcal{L} \subset[N] L ⊂ [ N ] of K − 1 K-1 K − 1 labels, listed in a fixed order. Alice sends the position of s s s in L \mathcal{L} L if s ∈ L s \in\mathcal{L} s ∈ L , and the remaining K K K th message otherwise. If t ∈ L t \in\mathcal{L} t ∈ L , Bob outputs G = 1 G=1 G = 1 when the message is the position of t t t and G = 0 G=0 G = 0 otherwise; if t ∉ L t \notin\mathcal{L} t ∈ / L , he abstains. Every conclusive answer is correct, and Bob answers whenever t ∈ L t \in\mathcal{L} t ∈ L , which happens with probability ( K − 1 ) / N (K-1)/N ( K − 1 ) / N for every input pair. For N > K N>K N > K this is optimal. In a deterministic protocol, Bob can output G = 1 G=1 G = 1 on ( t , t ) (t,t) ( t , t ) only if no other label is mapped to the same message as t t t ; otherwise he would err on some pair ( s , t ) (s,t) ( s , t ) with s ≠ t s \ne t s = t . Since N > K N>K N > K , the N N N labels cannot be spread one per message, so at most K − 1 K-1 K − 1 messages have exactly one label mapped to them. Hence ∑ t Pr ( G = 1 ∣ t , t ) ≤ K − 1 \sum_t \Pr(G=1\mid t,t) \le K-1 ∑ t Pr ( G = 1 ∣ t , t ) ≤ K − 1 . The same bound holds for mixtures of deterministic protocols, so η C L ( K ) ( N ) = ( K − 1 ) / N \eta_{\mathrm{CL}}^{(K)}(N)=(K-1)/N η CL ( K ) ( N ) = ( K − 1 ) / N for K < N K<N K < N ; for K ≥ N K \ge N K ≥ N , Alice can send s s s itself and η C L ( K ) ( N ) = 1 \eta_{\mathrm{CL}}^{(K)}(N)=1 η CL ( K ) ( N ) = 1 .
Theorem 5 (Sum rule for K K K messages). Let N ≥ 2 N \ge2 N ≥ 2 and K ≥ 2 K \ge2 K ≥ 2 . Every zero-error quantum or commuting-operator protocol with K K K messages satisfies
∑ t ≠ u Pr ( G = 1 ∣ t , t ) ≤ K − 1 for every u ∈ [ N ] . (23) \sum_{t\ne u} \Pr(G=1\mid t,t) \le K-1 \qquad\text{for every } u\in[N]. \tag*{(23)} t = u ∑ Pr ( G = 1 ∣ t , t ) ≤ K − 1 for every u ∈ [ N ] . (23)
Consequently, η C Q c ( K ) ( N ) ≤ ( K − 1 ) / ( N − 1 ) \eta_{\mathrm{CQc}}^{(K)}(N) \le(K-1)/(N-1) η CQc ( K ) ( N ) ≤ ( K − 1 ) / ( N − 1 ) .
The consequence follows because the left-hand side of Eq. (23) has N − 1 N-1 N − 1 terms, each at least η ( K ) \eta^{(K)} η ( K ) . The proof adapts that of Theorem 1.
With one bit, that argument uses the orthogonality of the two message sectors. With K K K messages, we instead fix a label u u u . For t ≠ u t \ne u t = u , zero error places the support of Alice’s steered operator T m t T_{mt} T m t , or the conditional vector D 1 ∣ m , t ψ \sqrt{D_{1\mid m,t}}\psi D 1 ∣ m , t ψ in the commuting-operator model, in the kernel of E m ∣ u E_{m\mid u} E m ∣ u ; otherwise Bob would err on ( u , t ) (u,t) ( u , t ) .
The operator inequality Π ker E ≤ I − E \Pi_{\ker E}\le I-E Π k e r E ≤ I − E , valid for every effect E E E , then bounds the total weight of the K K K message sectors by ∑ m ( I − E m ∣ u ) = ( K − 1 ) I \sum_m(I-E_{m\mid u})=(K-1)I ∑ m ( I − E m ∣ u ) = ( K − 1 ) I . For K = 2 K=2 K = 2 the bound 1 / ( N − 1 ) 1/(N-1) 1/ ( N − 1 ) is slightly weaker than the bound 1 / N 1/N 1/ N of Theorem 1. Comparing with the classical value ( K − 1 ) / N (K-1)/N ( K − 1 ) / N , entanglement, even in the commuting-operator framework, improves on shared randomness by at most a factor N / ( N − 1 ) N/(N-1) N / ( N − 1 ) for every K < N K<N K < N .
Proof of Theorem 5 . In tensor-product models, define E m ∣ s E_{m\mid s} E m ∣ s , D 1 ∣ m , t D_{1\mid m,t} D 1 ∣ m , t and T m t T_{mt} T m t as in the proof of Theorem 1, now with m ∈ { 0 , … , K − 1 } m \in\{0,\ldots,K-1\} m ∈ { 0 , … , K − 1 } ; zero error again gives Eq. (7) . Fix u u u , and let Π m \Pi_m Π m project onto the closed linear span W m = span { supp T m t : t ≠ u } \mathcal{W}_m=\operatorname{span}\{\operatorname{supp}T_{mt}:t\ne u\} W m = span { supp T m t : t = u } . By Eq. (7) , W m \mathcal{W}_m W m lies in the kernel of E m ∣ u E_{m\mid u} E m ∣ u , so Π m ≤ Π ker E m ∣ u ≤ I − E m ∣ u \Pi_m\le\Pi_{\ker E_{m\mid u}}\le I-E_{m\mid u} Π m ≤ Π k e r E m ∣ u ≤ I − E m ∣ u ; the last inequality holds because E m ∣ u E_{m\mid u} E m ∣ u commutes with its kernel projector and I − E m ∣ u ≥ 0 I-E_{m\mid u}\ge0 I − E m ∣ u ≥ 0 . Summing over m m m and using ∑ m E m ∣ u = I \sum_m E_{m\mid u}=I ∑ m E m ∣ u = I gives ∑ m Π m ≤ ( K − 1 ) I \sum_m\Pi_m\le(K-1)I ∑ m Π m ≤ ( K − 1 ) I . For each m m m , apply Lemma 2 to T m t T_{mt} T m t , Π m E m ∣ t Π m \Pi_m E_{m|t}\Pi_m Π m E m ∣ t Π m , and the common upper bound Π m ρ A Π m \Pi_m\rho_A\Pi_m Π m ρ A Π m , with t ≠ u t \ne u t = u . This gives
∑ t ≠ u tr ( E m ∣ t T m t ) ≤ tr ( ρ A Π m ) . \sum_{t\ne u}\operatorname{tr}(E_{m|t}T_{mt}) \le\operatorname{tr}(\rho_A\Pi_m). t = u ∑ tr ( E m ∣ t T m t ) ≤ tr ( ρ A Π m ) .
Summing over m m m , the left-hand side of Eq. (23) is at most tr [ ρ A ∑ m Π m ] ≤ K − 1 \operatorname{tr}[\rho_A\sum_m\Pi_m] \le K-1 tr [ ρ A ∑ m Π m ] ≤ K − 1 . Each of its N − 1 N-1 N − 1 terms is at least the worst-case efficiency, which is therefore at most ( K − 1 ) / ( N − 1 ) (K-1)/(N-1) ( K − 1 ) / ( N − 1 ) .
In commuting-operator models, let ψ \psi ψ be the shared unit vector, let { E m ∣ s } m = 0 K − 1 \{E_{m|s}\}_{m=0}^{K-1} { E m ∣ s } m = 0 K − 1 be Alice’s encoding POVMs, and let D 1 ∣ m , t D_{1|m,t} D 1∣ m , t be Bob’s acceptance effects. Define v m t v_{mt} v m t and V m t V_{mt} V m t as in the proof of Theorem 1. Fix u u u , and let Π m \Pi_m Π m project onto the closed span of { V m t : t ≠ u } \{V_{mt}:t\ne u\} { V m t : t = u } . Since each of these subspaces lies in ker E m ∣ u \ker E_{m|u} ker E m ∣ u ,
Π m ≤ I − E m ∣ u , ∑ m Π m ≤ ( K − 1 ) I . \Pi_m \le I-E_{m|u},\qquad\sum_m\Pi_m\le(K-1)I. Π m ≤ I − E m ∣ u , m ∑ Π m ≤ ( K − 1 ) I .
For each fixed m m m , first test Π m \Pi_m Π m and, on success, apply Alice’s sequential tests with t ≠ u t\ne u t = u . Their conclusive effects satisfy ∑ t ≠ u K m t ≤ Π m \sum_{t\ne u}K_{mt}\le\Pi_m ∑ t = u K m t ≤ Π m . Equation (8) therefore gives
∑ t ≠ u ⟨ v m t , E m ∣ t v m t ⟩ ≤ ⟨ ψ , Π m ψ ⟩ . \sum_{t\ne u}\langle v_{mt},E_{m|t}v_{mt}\rangle\le\langle\psi,\Pi_m\psi\rangle. t = u ∑ ⟨ v m t , E m ∣ t v m t ⟩ ≤ ⟨ ψ , Π m ψ ⟩ .
Here the tests are constructed separately for each m m m ; the projectors Π m \Pi_m Π m need not be mutually orthogonal. Summing over m m m yields
∑ t ≠ u Pr ( G = 1 ∣ t , t ) ≤ ∑ m ⟨ ψ , Π m ψ ⟩ ≤ K − 1 , \sum_{t\ne u}\Pr(G=1\mid t,t)\le\sum_m\langle\psi,\Pi_m\psi\rangle\le K-1, t = u ∑ Pr ( G = 1 ∣ t , t ) ≤ m ∑ ⟨ ψ , Π m ψ ⟩ ≤ K − 1 ,
which completes the proof.
Communication cost. We measure communication by the length of Alice’s message and success by the worst case over input pairs. Message length is counted in the worst case, as the number of classical bits Alice sends; shared randomness and pre-shared correlations are free, and we do not consider quantum messages, expected message lengths or two-way communication. The quantum lower bounds below hold under the same conventions for arbitrary entanglement and in the commuting-operator model. For η ∈ ( 0 , 1 ] \eta\in(0,1] η ∈ ( 0 , 1 ] , let C Ω η ( N ) C_{\Omega}^{\eta}(N) C Ω η ( N ) be the smallest k k k for which some one-way zero-error protocol over Ω \Omega Ω with a k k k -bit message satisfies min s , t Pr ( G ≠ ? ∣ s , t ) ≥ η \min_{s,t}\Pr(G\ne?\mid s,t)\ge\eta min s , t Pr ( G = ? ∣ s , t ) ≥ η .
Corollary 3 (Communication cost). For every η ∈ ( 0 , 1 ] \eta\in(0,1] η ∈ ( 0 , 1 ] ,
⌈ log 2 [ 1 + η ( N − 1 ) ] ⌉ ≤ C q c η ( N ) ≤ C L η ( N ) ≤ min { ⌈ log 2 ( 1 + η N ) ⌉ , ⌈ log 2 N ⌉ } , (24) \left\lceil\log_2[1+\eta(N-1)]\right\rceil\le C_{\mathrm{qc}}^{\eta}(N)\le C_{\mathrm{L}}^{\eta}(N)\le\min\{\lceil\log_2(1+\eta N)\rceil,\lceil\log_2N\rceil\}, \tag*{(24)} ⌈ log 2 [ 1 + η ( N − 1 )] ⌉ ≤ C qc η ( N ) ≤ C L η ( N ) ≤ min {⌈ log 2 ( 1 + η N )⌉ , ⌈ log 2 N ⌉} , (24) whereas C A Q 1 / 19 ( N ) = 1 C_{\mathrm{AQ}}^{1/19}(N)=1 C AQ 1/19 ( N ) = 1 . In particular, for N = 2 n N=2^n N = 2 n inputs, attaining worst-case conclusive probability 1 / 19 1/19 1/19 requires at least n − log 2 19 n-\log_2 19 n − log 2 19 bits with entanglement, but a single bit with almost-quantum correlations.
Proof. By Theorem 5 , a k k k -bit protocol over C q c C_{\mathrm{qc}} C qc with worst-case conclusive probability η \eta η needs ( 2 k − 1 ) / ( N − 1 ) ≥ η (2^k-1)/(N-1)\ge\eta ( 2 k − 1 ) / ( N − 1 ) ≥ η ; since k k k is an integer, this gives the left inequality in Eq. (24) . The middle inequality holds because C L ⊆ C q c C_{\mathrm{L}}\subseteq C_{\mathrm{qc}} C L ⊆ C qc , and the right one follows from the classical protocol with K = 2 k K=2^k K = 2 k messages (Alice sends s s s itself if K ≥ N K\ge N K ≥ N , which gives the cap ⌈ log 2 N ⌉ \lceil\log_2N\rceil ⌈ log 2 N ⌉ ). The outer bounds differ by at most one, because log 2 ( 1 + η N ) − log 2 [ 1 + η ( N − 1 ) ] < 1 \log_2(1+\eta N)-\log_2[1+\eta(N-1)]<1 log 2 ( 1 + η N ) − log 2 [ 1 + η ( N − 1 )] < 1 . Theorem 2 gives C A Q 1 / 19 ( N ) ≤ 1 C_{\mathrm{AQ}}^{1/19}(N)\le1 C AQ 1/19 ( N ) ≤ 1 . Without communication, Bob’s output distribution does not depend on s s s , so zero error forces Pr ( G = 1 ∣ t , t ) = Pr ( G = 1 ∣ s , t ) = 0 \Pr(G=1\mid t,t)=\Pr(G=1\mid s,t)=0 Pr ( G = 1 ∣ t , t ) = Pr ( G = 1 ∣ s , t ) = 0 for s ≠ t s\ne t s = t ; no protocol over C N S C_{\mathrm{NS}} C NS without communication has positive efficiency. Finally, log 2 [ 1 + ( N − 1 ) / 19 ] ≤ log 2 ( N / 19 ) = n − log 2 19 \log_2[1+(N-1)/19]\le\log_2(N/19)=n-\log_2 19 log 2 [ 1 + ( N − 1 ) /19 ] ≤ log 2 ( N /19 ) = n − log 2 19 .
Hence, for every target η \eta η , entanglement, even in the commuting-operator model, shortens Alice’s message by at most one bit relative to shared randomness. Almost-quantum correlations, by contrast, reduce the cost of reaching η = 1 / 19 \eta=1/19 η = 1/19 from at least n − log 2 19 ≈ n − 4.25 n-\log_2 19\approx n-4.25 n − log 2 19 ≈ n − 4.25 bits to a single bit.
Zero-error communication complexity. In the standard zero-error (Las Vegas) model of communication complexity [56 , 57 ] , Bob may abstain with probability at most 1 / 2 1/2 1/2 on every input pair, so the relevant one-way cost is C Ω 1 / 2 ( N ) C_{\Omega}^{1/2}(N) C Ω 1/2 ( N ) . The constant efficiency of almost-quantum correlations can then be amplified by repetition.
Corollary 4 (Zero-error communication complexity). For N = 2 n N = 2^n N = 2 n , C C L 1 / 2 ( N ) = C C q 1 / 2 ( N ) = C C q c 1 / 2 ( N ) = n C_{\mathrm{CL}}^{1/2}(N) = C_{\mathrm{Cq}}^{1/2}(N) = C_{\mathrm{Cqc}}^{1/2}(N) = n C CL 1/2 ( N ) = C Cq 1/2 ( N ) = C Cqc 1/2 ( N ) = n , whereas C A Q 1 / 2 ( N ) ≤ 13 C_{\mathrm{AQ}}^{1/2}(N) \le13 C AQ 1/2 ( N ) ≤ 13 . That is, one-way zero-error protocols for E Q N \mathrm{EQ}_N EQ N that abstain with probability at most 1 / 2 1/2 1/2 on every input pair require exactly n n n bits with shared randomness, with entanglement and in the commuting-operator model, but at most 13 bits with almost-quantum correlations.
Proof. For the lower bound, Eq. (24) with η = 1 / 2 \eta= 1/2 η = 1/2 gives C C q c 1 / 2 ( N ) ≥ ⌈ log 2 ( 2 n − 1 + 1 / 2 ) ⌉ = n C_{\mathrm{Cqc}}^{1/2}(N) \ge\lceil\log_2(2^{n-1} + 1/2) \rceil= n C Cqc 1/2 ( N ) ≥ ⌈ log 2 ( 2 n − 1 + 1/2 )⌉ = n . For the upper bound, Alice can send s s s itself, which costs n n n bits, so C C L 1 / 2 ( N ) ≤ n C_{\mathrm{CL}}^{1/2}(N) \le n C CL 1/2 ( N ) ≤ n . Since C L ⊆ C q ⊆ C q c C_{\mathrm{L}} \subseteq C_{\mathrm{q}} \subseteq C_{\mathrm{qc}} C L ⊆ C q ⊆ C qc , we have n ≤ C C q c 1 / 2 ≤ C C q 1 / 2 ≤ C C L 1 / 2 ≤ n n \le C_{\mathrm{Cqc}}^{1/2} \le C_{\mathrm{Cq}}^{1/2} \le C_{\mathrm{CL}}^{1/2} \le n n ≤ C Cqc 1/2 ≤ C Cq 1/2 ≤ C CL 1/2 ≤ n . With almost-quantum correlations, the parties run 13 independent copies of the one-bit protocol of Theorem 2, each with its own copy of p ⋆ p^\star p ⋆ and its own shared randomness, so Alice sends 13 bits. Each copy never errs and is conclusive with probability 1 / 19 1/19 1/19 on every input pair, independently of the other copies. Bob outputs any conclusive answer. Hence he abstains with probability ( 18 / 19 ) 13 < 0.496 (18/19)^{13} < 0.496 ( 18/19 ) 13 < 0.496 ; twelve copies would not suffice, since ( 18 / 19 ) 12 > 0.52 (18/19)^{12} > 0.52 ( 18/19 ) 12 > 0.52 . The joint resource is almost quantum because tensor products of AQ realizations satisfy Eq. (1) factor by factor (Lemma 1(ii)).
For comparison, the transcript-guessing bound of Ref. [32 ] , adapted to classical messages in Proposition 4, gives 2 c ≥ N / 2 2^c \ge N/2 2 c ≥ N /2 , i.e., at least n − 1 n-1 n − 1 bits, for entanglement-assisted and commuting-operator protocols that exchange c c c classical bits, even interactively, and Klauck and de Wolf [32 ] obtained a lower bound of n / 2 − 1 / 2 n/2 - 1/2 n /2 − 1/2 when the messages are qubits [32 ] . Corollary 4 sharpens the one-way bound for classical messages to exactly n n n bits and extends it to commuting-operator models. Almost-quantum correlations need at most 13 bits.
Equality certification with vector correlations
This section proves part (iii) of Theorem 4 and the separation of C A Q C_{\mathrm{AQ}} C AQ from C V e c C_{\mathrm{Vec}} C Vec stated after it. For certificates of equality from binary-outcome boxes, Level 1 of the NPA hierarchy attains
η C V e c e q ( N ) = N 8 ( N − 2 ) ( N ≥ 4 ) , (25) \eta_{C_{\mathrm{Vec}}}^{\mathrm{eq}}(N) = \frac{N}{8(N-2)} \qquad(N \ge4), \tag*{(25)} η C Vec eq ( N ) = 8 ( N − 2 ) N ( N ≥ 4 ) , (25)
which exceeds the quantum value 1 / N 1/N 1/ N for every N ≥ 5 N \ge5 N ≥ 5 and decreases to 1 / 8 1/8 1/8 (Proposition 2 below). The proof needs no semidefinite programming: the upper bound combines two inequalities, each expressing the nonnegativity of a squared norm, and an explicit realization attains it. Mixing the optimal level-1 certificate with the classical inequality certificate, as in Eq. (13) , gives η C V e c ( N ) ≥ N / ( 10 N − 16 ) > 1 / 10 \eta_{C_{\mathrm{Vec}}}(N) \ge N/(10N-16) > 1/10 η C Vec ( N ) ≥ N / ( 10 N − 16 ) > 1/10 for N ≥ 4 N \ge4 N ≥ 4 , which exceeds the quantum value 1 / N 1/N 1/ N for every N ≥ 9 N \ge9 N ≥ 9 . For every N ≥ 5 N \ge5 N ≥ 5 the optimal level-1 box lies outside C A Q C_{\mathrm{AQ}} C AQ , which yields an explicit, analytic separation C A Q ⊈ C V e c C_{\mathrm{AQ}} \not\subseteq C_{\mathrm{Vec}} C AQ ⊆ C Vec . The difference stems from the vectors A x B x ψ A_xB_x\psi A x B x ψ that the 1 + 1+ 1 + AB level requires and level 1 does not (Lemma 3); they lower the attainable certificate from about 1 / 8 1/8 1/8 to 1 / 17 1/17 1/17 .
For N ≥ 5 N \ge5 N ≥ 5 , vector correlations also violate the witness (21) . The optimal level-1 boxes have the same structure as p ⋆ p^\star p ⋆ and are listed in Table 3 .
Table 3. The level-1 box p N V e c ( a , b ∣ x , y ) p_N^{\mathrm{Vec}}(a,b|x,y) p N Vec ( a , b ∣ x , y ) . Like p ⋆ p^\star p ⋆ , it depends only on whether the settings coincide; its entries depend on N N N . It lies in C V e c ∩ F 0 \mathrm{C}_{\mathrm{Vec}}\cap\mathrm{F}_0 C Vec ∩ F 0 for every N ≥ 4 N\ge4 N ≥ 4 , attains Proposition 2, coincides with a local box for N = 4 N=4 N = 4 and lies outside C A Q \mathrm{C}_{\mathrm{AQ}} C AQ for every N ≥ 5 N\ge5 N ≥ 5 .
Proposition 2 (Equality certification with vector correlations). Let N ≥ 3 N \ge3 N ≥ 3 , and let p ∈ C V e c ∩ F 0 p \in\mathrm{CVec}\cap\mathrm{F}_0 p ∈ CVec ∩ F 0 be a binary-outcome box with N N N settings per party. Then
∑ x = 1 N p ( 0 , 0 ∣ x , x ) ≤ { 1 , N ∈ { 3 , 4 } , N 2 8 ( N − 2 ) , N ≥ 4 , (26) \sum_{x=1}^{N}p(0,0|x,x)\le
\begin{cases}
1, & N\in\{3,4\},\\
\frac{N^2}{8(N-2)}, & N\ge4,
\end{cases} \tag*{(26)} x = 1 ∑ N p ( 0 , 0∣ x , x ) ≤ { 1 , 8 ( N − 2 ) N 2 , N ∈ { 3 , 4 } , N ≥ 4 , (26) where the two expressions agree at N = 4 N=4 N = 4 , and each bound is attained. Consequently η C V e c e q ( 3 ) = 1 / 3 \eta_{\mathrm{CVec}}^{\mathrm{eq}}(3)=1/3 η CVec eq ( 3 ) = 1/3 and
η C V e c e q ( N ) = N 8 ( N − 2 ) , η C V e c e q ( N ) − 1 N = ( N − 4 ) 2 8 N ( N − 2 ) ( N ≥ 4 ) . (27) \eta_{\mathrm{CVec}}^{\mathrm{eq}}(N)=\frac{N}{8(N-2)},\qquad
\eta_{\mathrm{CVec}}^{\mathrm{eq}}(N)-\frac{1}{N}=\frac{(N-4)^2}{8N(N-2)}
\qquad(N\ge4). \tag*{(27)} η CVec eq ( N ) = 8 ( N − 2 ) N , η CVec eq ( N ) − N 1 = 8 N ( N − 2 ) ( N − 4 ) 2 ( N ≥ 4 ) . (27) In particular, η C V e c e q ( N ) > 1 / N \eta_{\mathrm{CVec}}^{\mathrm{eq}}(N)>1/N η CVec eq ( N ) > 1/ N if and only if N ≥ 5 N\ge5 N ≥ 5 , and η C V e c e q ( N ) \eta_{\mathrm{CVec}}^{\mathrm{eq}}(N) η CVec eq ( N ) decreases monotonically to 1 / 8 1/8 1/8 . For N ≥ 4 N\ge4 N ≥ 4 the optimum is attained by the box p N V e c p_N^{\mathrm{Vec}} p N Vec of Table 3 .
Proof. Let ψ \psi ψ , { ξ a ∣ x } \{\xi_{a|x}\} { ξ a ∣ x } and { ζ b ∣ y } \{\zeta_{b|y}\} { ζ b ∣ y } be a vector realization of p p p as in § 2 , and write a x = ξ 0 ∣ x a_x=\xi_{0|x} a x = ξ 0∣ x , b x = ζ 0 ∣ x b_x=\zeta_{0|x} b x = ζ 0∣ x and q x = p ( 0 , 0 ∣ x , x ) q_x=p(0,0|x,x) q x = p ( 0 , 0∣ x , x ) . The proof uses only three properties of these vectors:
(P1) ⟨ ψ , a x ⟩ = ∥ a x ∥ 2 \langle\psi,a_x\rangle=\|a_x\|^2 ⟨ ψ , a x ⟩ = ∥ a x ∥ 2 and ⟨ ψ , b x ⟩ = ∥ b x ∥ 2 \langle\psi,b_x\rangle=\|b_x\|^2 ⟨ ψ , b x ⟩ = ∥ b x ∥ 2 , because ξ 0 ∣ x ⊥ ξ 1 ∣ x \xi_{0|x}\perp\xi_{1|x} ξ 0∣ x ⊥ ξ 1∣ x and ξ 0 ∣ x + ξ 1 ∣ x = ψ \xi_{0|x}+\xi_{1|x}=\psi ξ 0∣ x + ξ 1∣ x = ψ give ⟨ ψ , a x ⟩ = ⟨ a x + ξ 1 ∣ x , a x ⟩ = ∥ a x ∥ 2 \langle\psi,a_x\rangle=\langle a_x+\xi_{1|x},a_x\rangle=\|a_x\|^2 ⟨ ψ , a x ⟩ = ⟨ a x + ξ 1∣ x , a x ⟩ = ∥ a x ∥ 2 , and likewise for Bob;
(P2) ⟨ a x , b y ⟩ = p ( 0 , 0 ∣ x , y ) = q x δ x y \langle a_x,b_y\rangle=p(0,0|x,y)=q_x\delta_{xy} ⟨ a x , b y ⟩ = p ( 0 , 0∣ x , y ) = q x δ x y , because p ∈ F 0 p\in\mathrm{F}_0 p ∈ F 0 ;
(P3) q x ≤ 1 2 ( ∥ a x ∥ 2 + ∥ b x ∥ 2 ) q_x\le\frac{1}{2}(\|a_x\|^2+\|b_x\|^2) q x ≤ 2 1 ( ∥ a x ∥ 2 + ∥ b x ∥ 2 ) , by the Cauchy–Schwarz inequality q x = ⟨ a x , b x ⟩ ≤ ∥ a x ∥ ∥ b x ∥ q_x=\langle a_x,b_x\rangle\le\|a_x\|\|b_x\| q x = ⟨ a x , b x ⟩ ≤ ∥ a x ∥∥ b x ∥ and 2 u v ≤ u 2 + v 2 2uv\le u^2+v^2 2 uv ≤ u 2 + v 2 .
The inner products in (P1) and (P2) are real, so the argument below holds verbatim in a real or a complex Hilbert space. Put
A = ∑ x a x , B = ∑ x b x , S = ∑ x ( ∥ a x ∥ 2 + ∥ b x ∥ 2 ) , Q = ∑ x q x , A=\sum_x a_x,\qquad B=\sum_x b_x,\qquad S=\sum_x(\|a_x\|^2+\|b_x\|^2),\qquad Q=\sum_x q_x, A = x ∑ a x , B = x ∑ b x , S = x ∑ ( ∥ a x ∥ 2 + ∥ b x ∥ 2 ) , Q = x ∑ q x ,
so that the left-hand side of Eq. (26) is Q Q Q . By (P1) and (P2), ⟨ ψ , A + B ⟩ = S \langle\psi,A+B\rangle=S ⟨ ψ , A + B ⟩ = S and ⟨ A , B ⟩ = Q \langle A,B\rangle=Q ⟨ A , B ⟩ = Q .
Upper bound. Let c x = a x − b x c_x=a_x-b_x c x = a x − b x . By (P2), ∥ c x ∥ 2 = ∥ a x ∥ 2 + ∥ b x ∥ 2 − 2 q x \|c_x\|^2=\|a_x\|^2+\|b_x\|^2-2q_x ∥ c x ∥ 2 = ∥ a x ∥ 2 + ∥ b x ∥ 2 − 2 q x , hence ∑ x ∥ c x ∥ 2 = S − 2 Q \sum_x\|c_x\|^2=S-2Q ∑ x ∥ c x ∥ 2 = S − 2 Q ; moreover ∑ x c x = A − B \sum_xc_x=A-B ∑ x c x = A − B and ∥ A − B ∥ 2 = ∥ A ∥ 2 + ∥ B ∥ 2 − 2 Q \|A-B\|^2=\|A\|^2+\|B\|^2-2Q ∥ A − B ∥ 2 = ∥ A ∥ 2 + ∥ B ∥ 2 − 2 Q . Expanding the squares gives the identity
∑ x < y ∥ c x − c y ∥ 2 = N ∑ x ∥ c x ∥ 2 − ∥ ∑ x c x ∥ 2 , \sum_{x<y}\|c_x-c_y\|^2=N\sum_x\|c_x\|^2-\left\|\sum_xc_x\right\|^2, x < y ∑ ∥ c x − c y ∥ 2 = N x ∑ ∥ c x ∥ 2 − x ∑ c x 2 ,
whose left-hand side is nonnegative. Therefore
∥ A ∥ 2 + ∥ B ∥ 2 ≤ N S − 2 ( N − 1 ) Q , (28) \|A\|^2+\|B\|^2\le NS-2(N-1)Q, \tag*{(28)} ∥ A ∥ 2 + ∥ B ∥ 2 ≤ N S − 2 ( N − 1 ) Q , (28)
with equality if and only if all c x c_x c x coincide. Next, for every real λ \lambda λ ,
0 ≤ ∥ ψ − λ ( A + B ) ∥ 2 = 1 − 2 λ S + λ 2 ( ∥ A ∥ 2 + ∥ B ∥ 2 + 2 Q ) , 0\le\|\psi-\lambda(A+B)\|^2=1-2\lambda S+\lambda^2(\|A\|^2+\|B\|^2+2Q), 0 ≤ ∥ ψ − λ ( A + B ) ∥ 2 = 1 − 2 λ S + λ 2 ( ∥ A ∥ 2 + ∥ B ∥ 2 + 2 Q ) ,
and inserting Eq. (28) into the last term gives
0 ≤ 1 − λ ( 2 − λ N ) S − 2 λ 2 ( N − 2 ) Q . (29) 0\le1-\lambda(2-\lambda N)S-2\lambda^2(N-2)Q. \tag*{(29)} 0 ≤ 1 − λ ( 2 − λ N ) S − 2 λ 2 ( N − 2 ) Q . (29)
For N ≥ 4 N\ge4 N ≥ 4 , the choice λ = 2 / N \lambda=2/N λ = 2/ N removes the term in S S S and yields Q ≤ N 2 / [ 8 ( N − 2 ) ] Q\le N^2/[8(N-2)] Q ≤ N 2 / [ 8 ( N − 2 )] ; equality requires equality in Eq. (28) together with ψ = 2 N ( A + B ) \psi=\frac{2}{N}(A+B) ψ = N 2 ( A + B ) . For N ∈ { 3 , 4 } N\in\{3,4\} N ∈ { 3 , 4 } , the choice λ = 1 / 2 \lambda=1/2 λ = 1/2 makes the coefficient of S S S equal to − ( 4 − N ) / 4 ≤ 0 -(4-N)/4 \le0 − ( 4 − N ) /4 ≤ 0 , so the lower bound S ≥ 2 Q S \ge2Q S ≥ 2 Q from (P3) may be inserted, and Eq. (29) becomes
0 ≤ 1 − 4 − N 2 Q − N − 2 2 Q = 1 − Q . 0 \le1-\frac{4-N}{2}Q-\frac{N-2}{2}Q=1-Q. 0 ≤ 1 − 2 4 − N Q − 2 N − 2 Q = 1 − Q .
This proves Eq. (26) . Since min x q x ≤ Q / N \min_x q_x \le Q/N min x q x ≤ Q / N , it also gives η C V e c e q ( 3 ) ≤ 1 / 3 \eta_{\mathrm{CVec}}^{\mathrm{eq}}(3) \le1/3 η CVec eq ( 3 ) ≤ 1/3 and η C V e c e q ( N ) ≤ N / [ 8 ( N − 2 ) ] \eta_{\mathrm{CVec}}^{\mathrm{eq}}(N) \le N/[8(N-2)] η CVec eq ( N ) ≤ N / [ 8 ( N − 2 )] for N ≥ 4 N \ge4 N ≥ 4 .
Attainability. For N = 3 N=3 N = 3 , the local box in the proof of Theorem 3 lies in C L ∩ F 0 ⊆ C V e c ∩ F 0 \mathrm{C_L} \cap\mathrm{F_0} \subseteq\mathrm{CVec} \cap\mathrm{F_0} C L ∩ F 0 ⊆ CVec ∩ F 0 and has p ( 0 , 0 ∣ x , x ) = 1 / 3 p(0,0|x,x)=1/3 p ( 0 , 0∣ x , x ) = 1/3 for every x x x . For N ≥ 4 N \ge4 N ≥ 4 , we construct a box that meets both equality conditions above, namely that all c x c_x c x coincide and ψ = 2 N ( A + B ) \psi=\frac{2}{N}(A+B) ψ = N 2 ( A + B ) . Let ψ \psi ψ and e e e be orthonormal, let g 1 , … , g N g_1,\ldots,g_N g 1 , … , g N be orthonormal and orthogonal to ψ \psi ψ and e e e , and put f x = g x − 1 N ∑ y g y f_x=g_x-\frac{1}{N}\sum_y g_y f x = g x − N 1 ∑ y g y , so that ∑ x f x = 0 \sum_x f_x=0 ∑ x f x = 0 and ⟨ f x , f y ⟩ = δ x y − 1 / N \langle f_x,f_y\rangle=\delta_{xy}-1/N ⟨ f x , f y ⟩ = δ x y − 1/ N . For real σ , τ , δ \sigma,\tau,\delta σ , τ , δ set
a x = σ ψ + τ e + δ f x , b x = σ ψ − τ e + δ f x . a_x=\sigma\psi+\tau e+\delta f_x,\qquad b_x=\sigma\psi-\tau e+\delta f_x. a x = σ ψ + τ e + δ f x , b x = σ ψ − τ e + δ f x .
Then c x = 2 τ e c_x=2\tau e c x = 2 τ e for every x x x , and A + B = 2 N σ ψ A+B=2N\sigma\psi A + B = 2 N σ ψ , so ψ = 2 N ( A + B ) \psi=\frac{2}{N}(A+B) ψ = N 2 ( A + B ) holds if and only if σ = 1 / 4 \sigma=1/4 σ = 1/4 . The relevant inner products are
⟨ ψ , a x ⟩ = ⟨ ψ , b x ⟩ = σ , ∥ a x ∥ 2 = ∥ b x ∥ 2 = σ 2 + τ 2 + δ 2 N − 1 N , \langle\psi,a_x\rangle=\langle\psi,b_x\rangle=\sigma,\qquad
\|a_x\|^2=\|b_x\|^2=\sigma^2+\tau^2+\delta^2\frac{N-1}{N}, ⟨ ψ , a x ⟩ = ⟨ ψ , b x ⟩ = σ , ∥ a x ∥ 2 = ∥ b x ∥ 2 = σ 2 + τ 2 + δ 2 N N − 1 ,
⟨ a x , b y ⟩ = σ 2 − τ 2 + δ 2 ( δ x y − 1 N ) . \langle a_x,b_y\rangle=\sigma^2-\tau^2+\delta^2\left(\delta_{xy}-\frac{1}{N}\right). ⟨ a x , b y ⟩ = σ 2 − τ 2 + δ 2 ( δ x y − N 1 ) .
Property (P2) for x ≠ y x\ne y x = y requires σ 2 − τ 2 = δ 2 / N \sigma^2-\tau^2=\delta^2/N σ 2 − τ 2 = δ 2 / N , and then q : = ⟨ a x , b x ⟩ = δ 2 q:=\langle a_x,b_x\rangle=\delta^2 q := ⟨ a x , b x ⟩ = δ 2 . Property (P1) requires σ = σ 2 + τ 2 + δ 2 ( N − 1 ) / N \sigma=\sigma^2+\tau^2+\delta^2(N-1)/N σ = σ 2 + τ 2 + δ 2 ( N − 1 ) / N . With σ = 1 / 4 \sigma=1/4 σ = 1/4 , these two conditions have the solution
q = δ 2 = N 8 ( N − 2 ) , τ 2 = 1 16 − q N = N − 4 16 ( N − 2 ) , q=\delta^2=\frac{N}{8(N-2)},\qquad
\tau^2=\frac{1}{16}-\frac{q}{N}=\frac{N-4}{16(N-2)}, q = δ 2 = 8 ( N − 2 ) N , τ 2 = 16 1 − N q = 16 ( N − 2 ) N − 4 ,
and τ \tau τ is real if and only if N ≥ 4 N\ge4 N ≥ 4 . Now take ξ 0 ∣ x = a x \xi_{0|x}=a_x ξ 0∣ x = a x , ξ 1 ∣ x = ψ − a x \xi_{1|x}=\psi-a_x ξ 1∣ x = ψ − a x , ζ 0 ∣ y = b y \zeta_{0|y}=b_y ζ 0∣ y = b y and ζ 1 ∣ y = ψ − b y \zeta_{1|y}=\psi-b_y ζ 1∣ y = ψ − b y . By (P1), ξ 0 ∣ x ⊥ ξ 1 ∣ x \xi_{0|x}\perp\xi_{1|x} ξ 0∣ x ⊥ ξ 1∣ x and ζ 0 ∣ y ⊥ ζ 1 ∣ y \zeta_{0|y}\perp\zeta_{1|y} ζ 0∣ y ⊥ ζ 1∣ y , and each pair sums to ψ \psi ψ . Since ⟨ ψ , a x ⟩ = ⟨ ψ , b y ⟩ = 1 / 4 \langle\psi,a_x\rangle=\langle\psi,b_y\rangle=1/4 ⟨ ψ , a x ⟩ = ⟨ ψ , b y ⟩ = 1/4 and ⟨ a x , b y ⟩ = q δ x y \langle a_x,b_y\rangle=q\delta_{xy} ⟨ a x , b y ⟩ = q δ x y , the inner products p ( a , b ∣ x , y ) = ⟨ ξ a ∣ x , ζ b ∣ y ⟩ p(a,b|x,y)=\langle\xi_{a|x},\zeta_{b|y}\rangle p ( a , b ∣ x , y ) = ⟨ ξ a ∣ x , ζ b ∣ y ⟩ are
p ( 0 , 0 ∣ x , y ) = q δ x y , p ( 0 , 1 ∣ x , y ) = 1 4 − q δ x y , p(0,0|x,y)=q\delta_{xy},\qquad p(0,1|x,y)=\frac{1}{4}-q\delta_{xy}, p ( 0 , 0∣ x , y ) = q δ x y , p ( 0 , 1∣ x , y ) = 4 1 − q δ x y ,
p ( 1 , 0 ∣ x , y ) = 1 4 − q δ x y , p ( 1 , 1 ∣ x , y ) = 1 − 1 4 − 1 4 + q δ x y = 1 2 + q δ x y . (30) p(1,0|x,y)=\frac{1}{4}-q\delta_{xy},\qquad p(1,1|x,y)=1-\frac{1}{4}-\frac{1}{4}+q\delta_{xy}=\frac{1}{2}+q\delta_{xy}. \tag*{(30)} p ( 1 , 0∣ x , y ) = 4 1 − q δ x y , p ( 1 , 1∣ x , y ) = 1 − 4 1 − 4 1 + q δ x y = 2 1 + q δ x y . (30)
With q = N / [ 8 ( N − 2 ) ] q=N/[8(N-2)] q = N / [ 8 ( N − 2 )] this is the box p N V e c p_N^{\mathrm{Vec}} p N Vec of Table 3 . Its marginals p A ( 0 ∣ x ) = p B ( 0 ∣ y ) = 1 / 4 p_A(0|x)=p_B(0|y)=1/4 p A ( 0∣ x ) = p B ( 0∣ y ) = 1/4 do not depend on the settings, and all its entries are nonnegative because 1 / 4 − q = ( N − 4 ) / [ 8 ( N − 2 ) ] ≥ 0 1/4-q=(N-4)/[8(N-2)]\ge0 1/4 − q = ( N − 4 ) / [ 8 ( N − 2 )] ≥ 0 . Hence p N V e c ∈ C V e c ∩ F 0 p_N^{\mathrm{Vec}}\in\mathrm{CVec}\cap\mathrm{F_0} p N Vec ∈ CVec ∩ F 0 ; it is realized in the ( N + 1 ) (N+1) ( N + 1 ) -dimensional space spanned by ψ \psi ψ , e e e and the f x f_x f x . Since p ( 0 , 0 ∣ x , x ) = N / [ 8 ( N − 2 ) ] p(0,0|x,x)=N/[8(N-2)] p ( 0 , 0∣ x , x ) = N / [ 8 ( N − 2 )] for every x x x , it attains the bound Q ≤ N 2 / [ 8 ( N − 2 ) ] Q\le N^2/[8(N-2)] Q ≤ N 2 / [ 8 ( N − 2 )] and the worst-case bound η C V e c e q ( N ) ≤ N / [ 8 ( N − 2 ) ] \eta_{\mathrm{CVec}}^{\mathrm{eq}}(N)\le N/[8(N-2)] η CVec eq ( N ) ≤ N / [ 8 ( N − 2 )] . This proves that each bound in Eq. (26) is attained, and the first identity in Eq. (27) . For N = 4 N=4 N = 4 , Table 3 gives p ( 0 , 0 ∣ x , x ) = 1 / 4 p(0,0|x,x)=1/4 p ( 0 , 0∣ x , x ) = 1/4 , p ( 0 , 1 ∣ x , x ) = p ( 1 , 0 ∣ x , x ) = 0 p(0,1|x,x)=p(1,0|x,x)=0 p ( 0 , 1∣ x , x ) = p ( 1 , 0∣ x , x ) = 0 and p ( 1 , 1 ∣ x , x ) = 3 / 4 p(1,1|x,x)=3/4 p ( 1 , 1∣ x , x ) = 3/4 , so p 4 V e c p_4^{\mathrm{Vec}} p 4 Vec coincides with the local box in the proof of Theorem 3, and Q = 1 Q=1 Q = 1 . As N → ∞ N\to\infty N → ∞ , the row x = y x=y x = y of Table 3 tends to ( 1 / 8 , 1 / 8 , 1 / 8 , 5 / 8 ) (1/8,1/8,1/8,5/8) ( 1/8 , 1/8 , 1/8 , 5/8 ) , while the row x ≠ y x\ne y x = y does not depend on N N N .
Comparison with 1 / N 1/N 1/ N . For N ≥ 4 N\ge4 N ≥ 4 ,
N 8 ( N − 2 ) − 1 N = N 2 − 8 ( N − 2 ) 8 N ( N − 2 ) = ( N − 4 ) 2 8 N ( N − 2 ) . \frac{N}{8(N-2)}-\frac{1}{N}
=\frac{N^2-8(N-2)}{8N(N-2)}
=\frac{(N-4)^2}{8N(N-2)}. 8 ( N − 2 ) N − N 1 = 8 N ( N − 2 ) N 2 − 8 ( N − 2 ) = 8 N ( N − 2 ) ( N − 4 ) 2 .
which is positive if and only if N ≥ 5 N\ge5 N ≥ 5 . Finally, η C V e c e q ( 3 ) = 1 / 3 > 1 / 4 = η C V e c e q ( 4 ) \eta_{\mathrm{CVec}}^{\mathrm{eq}}(3)=1/3>1/4=\eta_{\mathrm{CVec}}^{\mathrm{eq}}(4) η CVec eq ( 3 ) = 1/3 > 1/4 = η CVec eq ( 4 ) , d d N N 8 ( N − 2 ) = − 1 4 ( N − 2 ) 2 < 0 \frac{d}{dN}\frac{N}{8(N-2)}=-\frac{1}{4(N-2)^2}<0 d N d 8 ( N − 2 ) N = − 4 ( N − 2 ) 2 1 < 0 and N 8 ( N − 2 ) → 1 8 \frac{N}{8(N-2)}\to\frac{1}{8} 8 ( N − 2 ) N → 8 1 , so η C V e c e q ( N ) \eta_{\mathrm{CVec}}^{\mathrm{eq}}(N) η CVec eq ( N ) decreases monotonically to 1 / 8 1/8 1/8 .
An explicit separation of C A Q \mathrm{C}_{\mathrm{AQ}} C AQ from C V e c \mathrm{C}_{\mathrm{Vec}} C Vec . For every N ≥ 5 N\ge5 N ≥ 5 , the box p N V e c p_N^{\mathrm{Vec}} p N Vec of Table 3 is not almost quantum. If it were, it would be an AQ box on F 0 \mathrm{F}_0 F 0 with min x p ( 0 , 0 ∣ x , x ) = N / [ 8 ( N − 2 ) ] \min_x p(0,0|x,x)=N/[8(N-2)] min x p ( 0 , 0∣ x , x ) = N / [ 8 ( N − 2 )] , so N / [ 8 ( N − 2 ) ] ≤ η A Q e q ( N ) N/[8(N-2)]\le\eta_{\mathrm{AQ}}^{\mathrm{eq}}(N) N / [ 8 ( N − 2 )] ≤ η AQ eq ( N ) by Eq. (12) . This is false. For 5 ≤ N ≤ 8 5\le N\le8 5 ≤ N ≤ 8 , Theorem 3 gives η A Q e q ( N ) = 1 / N \eta_{\mathrm{AQ}}^{\mathrm{eq}}(N)=1/N η AQ eq ( N ) = 1/ N , and N / [ 8 ( N − 2 ) ] > 1 / N N/[8(N-2)]>1/N N / [ 8 ( N − 2 )] > 1/ N by Eq. (27) . For N ≥ 8 N\ge8 N ≥ 8 , η A Q e q ( N ) = N 2 / ( 17 N 2 − 80 N + 64 ) \eta_{\mathrm{AQ}}^{\mathrm{eq}}(N)=N^2/(17N^2-80N+64) η AQ eq ( N ) = N 2 / ( 17 N 2 − 80 N + 64 ) , and N / [ 8 ( N − 2 ) ] > N 2 / ( 17 N 2 − 80 N + 64 ) N/[8(N-2)]>N^2/(17N^2-80N+64) N / [ 8 ( N − 2 )] > N 2 / ( 17 N 2 − 80 N + 64 ) is equivalent to 9 N 2 − 64 N + 64 > 0 9N^2-64N+64>0 9 N 2 − 64 N + 64 > 0 , which holds for every N ≥ 6 N\ge6 N ≥ 6 . Hence { p N V e c } N ≥ 5 \{p_N^{\mathrm{Vec}}\}_{N\ge5} { p N Vec } N ≥ 5 is an explicit family in C V e c ∖ C A Q \mathrm{C}_{\mathrm{Vec}}\setminus\mathrm{C}_{\mathrm{AQ}} C Vec ∖ C AQ , which proves C A Q ⊊ C V e c \mathrm{C}_{\mathrm{AQ}}\subsetneq\mathrm{C}_{\mathrm{Vec}} C AQ ⊊ C Vec .
Discussion
Almost-quantum correlations are known to satisfy nontrivial communication complexity, no advantage for nonlocal computation, macroscopic locality and local orthogonality, and numerical evidence suggested that they also satisfy information causality [22 ] . Satisfying these principles does not, however, make them operationally close to quantum correlations. We have shown that a single bit of communication suffices to separate the two sets, with an efficiency ratio that grows without bound, in the zero-error certification of equality. For every Hilbert-space model of quantum correlations, from finite-dimensional tensor products to commuting operators, the optimal worst-case efficiency is 1 / N 1/N 1/ N , whereas an explicit family of AQ boxes, one for each N N N , attains 1 / 19 1/19 1/19 . With longer messages the gap becomes a gap in communication cost: entanglement saves at most one bit over shared randomness, while AQ correlations attain a constant efficiency with a single bit and reduce the zero-error cost of deciding equality of n n n -bit strings from n n n bits to at most 13. For N = 2 n N=2^n N = 2 n the efficiency ratio is exponential in n n n , while the communication costs are linear versus constant; neither statement implies that the two sets are far apart in a distance on correlations. Nor does the separation conflict with the fact that AQ correlations satisfy nontrivial communication complexity [22 ] : equality is already cheap with bounded error and shared randomness, and the AQ advantage lies in certificates that are perfectly reliable yet arrive with a probability that does not shrink with N N N . The results of this paper do not by themselves bear on information causality; the Note added at the end of this section summarizes a companion work in which the boxes constructed here are shown to violate it.
In this task shared entanglement offers no advantage over shared randomness. Other tasks without quantum advantage are known, such as nonlocal computation [16 ] and the multipartite guess-your-neighbour’s-input game [63 ] . There, however, the classical bound follows from principles that AQ correlations also satisfy, namely no advantage for nonlocal computation and local orthogonality [21 , 22 ] , so AQ correlations offer no advantage either. In our task, quantum and classical correlations again coincide, but AQ correlations do strictly better, for every N ≥ 14 N\ge14 N ≥ 14 by Eq. (13) with the optimal boxes; for certificates of equality from binary-outcome boxes, Theorem 3 shows that they do so precisely when N ≥ 9 N\ge9 N ≥ 9 . The obstruction can be traced to the packing lemma: its sequential argument composes several of Alice’s operators and requires Bob’s operations to commute with such products. Commutation as an operator identity, as in C q c \mathrm{C}_{\mathrm{qc}} C qc , guarantees this. The AQ condition (1) , by contrast, constrains only single operators acting on the state, and the box p ∗ p^* p ∗ exploits exactly this freedom. This identifies a structural obstruction that separates C q c C_{\rm qc} C qc from C A Q C_{\rm AQ} C AQ ; satisfying the sum rule (6) does not by itself characterize commuting-operator correlations, nor does it single out quantum theory. The same sum rule provides an exact-zero (face) witness of post-quantumness whose violation grows linearly in N N N .
It is instructive to compare this separation with earlier ones. That the quantum set is strictly contained in the AQ set was shown already in the simplest Bell scenario, with two settings and two outcomes per party, through a Bell expression whose minimum over quantum correlations lies slightly above − 1 -1 − 1 , while an AQ correlation attains a lower value [22 ] . Such Bell-functional separations, which can be recast as nonlocal games, establish that the two sets differ. Here the separation takes a different form: an explicit family, scalable in N N N , in a zero-error communication task, with a sharp quantum benchmark and an analytically determined binary-box optimum. On the face F 0 F_0 F 0 , the linear functional ∑ x p ( 0 , 0 ∣ x , x ) \sum_x p(0,0|x,x) ∑ x p ( 0 , 0∣ x , x ) has the same maximum, 1 1 1 , over local, quantum and commuting-operator correlations. A violation of Eq. (21) by a box lying exactly on F 0 F_0 F 0 therefore excludes local and quantum explanations alike, and reveals an AQ advantage for an objective on which quantum correlations do not outperform shared randomness. Its maximum over AQ correlations equals N η A Q e q ( N ) N\eta_{\rm AQ}^{\rm eq}(N) N η AQ eq ( N ) , because the permutation symmetry used in § 5.3 lets us take all diagonal terms equal; by Theorem 3 this is N 3 / ( 17 N 2 − 80 N + 64 ) N^3/(17N^2-80N+64) N 3 / ( 17 N 2 − 80 N + 64 ) for N ≥ 8 N \ge8 N ≥ 8 , which grows approximately as N / 17 N/17 N /17 . The ratio of the AQ maximum to the quantum maximum therefore grows without bound, much as the ratio of quantum to local maxima does for families of Bell inequalities with unbounded violation [4 , 64 ] , and here both maxima are known exactly. Over Level 1 of the NPA hierarchy the same functional reaches N 2 / [ 8 ( N − 2 ) ] N^2/[8(N-2)] N 2 / [ 8 ( N − 2 )] for N ≥ 4 N \ge4 N ≥ 4 (Proposition 2), so the constraints of the 1 + 1+ 1 + AB level lower the maximal violation by a factor approaching 17 / 8 17/8 17/8 . The analogy with Bell inequalities has a limitation: unlike a Bell inequality, Eq. (21) holds only on the face F 0 F_0 F 0 , so its growing violation implies neither noise tolerance nor a quantitative distance from the quantum set (see the remark after Corollary 2).
The separation lies between the adjacent sets C q c C_{\rm qc} C qc and C A Q C_{\rm AQ} C AQ and does not depend on the resolution of Tsirelson’s problem. AQ correlations are also more than a convenient semidefinite relaxation. Dowker, Henson and Wallden showed [26 ] that they coincide with the correlations generated by strongly positive decoherence functionals in Sorkin’s quantum measure theory [25 ] when measurements may depend on earlier outcomes. This is a representation result under specified consistency assumptions, not a derivation from a particular model of quantum gravity. Quantum measure theory is a histories-based generalization of quantum mechanics developed with quantum gravity, and causal set theory in particular [65 ] , in mind. Any histories-based model that makes these AQ behaviours available as operational resources would therefore allow the protocols above, so the consistency conditions of such models do not by themselves enforce the quantum bound 1 / N 1/N 1/ N on zero-error certification of equality. Whether a specific theory of this kind realizes these behaviours physically is a separate question.
Several questions remain open. Our sharp quantum bounds concern one-way protocols. Interaction cannot remove the linear quantum lower bound: by the transcript-guessing argument of Ref. [32 ] , every entanglement-assisted or commuting-operator protocol that exchanges c c c classical bits satisfies ∑ t Pr ( G = 1 ∣ t , t ) ≤ 2 c \sum_t \Pr(G=1|t,t) \le2^c ∑ t Pr ( G = 1∣ t , t ) ≤ 2 c (Proposition 4). What remains open is whether interaction can improve on the one-way values, a question about the constant rather than the linear scaling. For messages of k ≥ 2 k \ge2 k ≥ 2 bits, Theorem 5 leaves a small gap between the quantum bound ( 2 k − 1 ) / ( N − 1 ) (2^k-1)/(N-1) ( 2 k − 1 ) / ( N − 1 ) and the classical value ( 2 k − 1 ) / N (2^k-1)/N ( 2 k − 1 ) / N . The separation relies on zero error. This is intrinsic to the task, since with bounded error equality is already easy with shared randomness, but the witness (21) is valid only on the face F 0 F_0 F 0 , and a quantitative version that tolerates nonzero off-diagonal coincidences, together with the precision it requires as a function of N N N , remains to be found. Whether a single AQ box can certify both equality and inequality more efficiently than the mixture (13) , and whether boxes with more outcomes or message-dependent settings improve on Theorem 3, is also open. Finally, it would be interesting to determine whether the decay of zero-error certification efficiency with N N N can be elevated to a physical principle that excludes AQ correlations at the level of Bell scenarios, in the spirit of nontrivial communication complexity [14 ] , information causality [17 ] and local orthogonality [21 ] .
Note added. In a companion work [31 ] , two of present authors (ADB and MB) show that the AQ boxes p ⋆ p^\star p ⋆ of Theorem 2 violate information causality [17 ] , and do so without bound. The protocol uses a single copy of p ⋆ p^\star p ⋆ and one classical bit. Alice receives k N kN k N independent fair bits, grouped into N N N blocks of k k k bits; she inputs into the box the index of the first block that consists only of ones, if there is one, and sends her outcome to Bob. Bob, asked about a bit of block i i i , inputs y = i y=i y = i and guesses 1 if the message and his outcome are both 0, and 0 otherwise. Because p ( 0 , 0 ∣ x , y ) = 0 p(0,0|x,y)=0 p ( 0 , 0∣ x , y ) = 0 for x ≠ y x\ne y x = y , a guess of 1 is never wrong; it therefore carries information linear in its probability, and it answers all k k k questions about the block at once. The sum, over Alice’s bits Z r Z_r Z r , of the mutual information I ( Z r : G r ) I(Z_r:G_r) I ( Z r : G r ) between Z r Z_r Z r and Bob’s guess G r G_r G r , which information causality bounds by the number of communicated bits, is then at least k 17 [ 1 − ( 1 − 2 − k ) N ] \frac{k}{17}\left[1-(1-2^{-k})^N\right] 17 k [ 1 − ( 1 − 2 − k ) N ] . This exceeds 1 for k = 18 k=18 k = 18 and N = 757 693 N=757\,693 N = 757 693 , and it grows as k ( 1 − e − k ) / 17 k(1-e^{-k})/17 k ( 1 − e − k ) /17 for N = k 2 k N=k2^k N = k 2 k . For a quantum box with p ( 0 , 0 ∣ x , y ) = s δ x y p(0,0|x,y)=s\delta_{xy} p ( 0 , 0∣ x , y ) = s δ x y , Corollary 2 gives s ≤ 1 / N s\le1/N s ≤ 1/ N , and the lower bound obtained from the same protocol is at most k 2 − k ≤ 1 / 2 k2^{-k}\le1/2 k 2 − k ≤ 1/2 . With the level-1 boxes p N V e c p_N^{\mathrm{Vec}} p N Vec of Table 3 , the protocol violates information causality for every N ≥ 1117 N\ge1117 N ≥ 1117 , in agreement with Ref. [18 ] . The violation thus rests on the property established here: zero-error certificates of equality whose rate, 1 / 17 1/17 1/17 for p ⋆ p^\star p ⋆ , does not decrease with N N N .
An explicit local model for $p^\star`
We now write p ⋆ p^\star p ⋆ explicitly as a mixture of deterministic strategies of the three types (i)–(iii) in the proof of Proposition 1. Type (iii) strategies supply the coincidences p ( 0 , 0 ∣ x , x ) p(0,0|x,x) p ( 0 , 0∣ x , x ) , while types (i) and (ii) raise Alice’s and Bob’s marginals to 3 / 17 3/17 3/17 without creating any further coincidence. Let π N = 4 / ( 17 − N ) \pi_N=4/(17-N) π N = 4/ ( 17 − N ) , and mix the following three classes:
Coincidences , with probability N / 17 N/17 N /17 : a type-(iii) strategy with x 0 x_0 x 0 chosen uniformly from [ N ] [N] [ N ] . Alice outputs 0 if and only if x = x 0 x=x_0 x = x 0 , and Bob outputs 0 if and only if y = x 0 y=x_0 y = x 0 .
Extra zeros for Bob , with probability ( 17 − N ) / 34 (17-N)/34 ( 17 − N ) /34 : a type-(i) strategy. Alice always outputs 1, and Bob outputs 0 if and only if y ∈ F B y\in F_B y ∈ F B , where each label is placed in F B F_B F B independently with probability π N \pi_N π N .
Extra zeros for Alice , with probability ( 17 − N ) / 34 (17-N)/34 ( 17 − N ) /34 : a type-(ii) strategy, the mirror image of the previous class. Bob always outputs 1, and Alice outputs 0 if and only if x ∈ F A x\in F_A x ∈ F A , with F A F_A F A chosen in the same way.
The weights are nonnegative and sum to N / 17 + ( 17 − N ) / 17 = 1 N/17+(17-N)/17=1 N /17 + ( 17 − N ) /17 = 1 . Here π N \pi_N π N is not a distribution over labels but the bias of an independent coin tossed for each label; the induced distribution over subsets, Pr ( F B = S ) = π N ∣ S ∣ ( 1 − π N ) N − ∣ S ∣ \Pr(F_B=S)=\pi_N^{|S|}(1-\pi_N)^{N-|S|} Pr ( F B = S ) = π N ∣ S ∣ ( 1 − π N ) N − ∣ S ∣ , is normalized because ∑ S ⊆ [ N ] Pr ( F B = S ) = ( π N + 1 − π N ) N = 1 \sum_{S\subseteq[N]}\Pr(F_B=S)=(\pi_N+1-\pi_N)^N=1 ∑ S ⊆ [ N ] Pr ( F B = S ) = ( π N + 1 − π N ) N = 1 . The only requirement is therefore 0 ≤ π N ≤ 1 0\le\pi_N\le1 0 ≤ π N ≤ 1 , which holds if and only if N ≤ 13 N\le13 N ≤ 13 . Every strategy used lies on F 0 F_0 F 0 , so the mixture does too. It remains to compute the box. Only the first class produces the outcome pair ( 0 , 0 ) (0,0) ( 0 , 0 ) , and it does so exactly when x = y = x 0 x=y=x_0 x = y = x 0 , an event of probability δ x y / N \delta_{xy}/N δ x y / N . Hence
p ( 0 , 0 ∣ x , y ) = N 17 ⋅ δ x y N = δ x y 17 . p(0,0\mid x,y)=\frac{N}{17}\cdot\frac{\delta_{xy}}{N}=\frac{\delta_{xy}}{17}. p ( 0 , 0 ∣ x , y ) = 17 N ⋅ N δ x y = 17 δ x y .
Alice outputs 0 in the first class when x = x 0 x=x_0 x = x 0 (probability 1 / N 1/N 1/ N ), never in the second, and in the third when x ∈ F A x\in F_A x ∈ F A (probability π N \pi_N π N ). Hence
p A ( 0 ∣ x ) = N 17 ⋅ 1 N + 17 − N 34 ⋅ 0 + 17 − N 34 ⋅ 4 17 − N = 1 17 + 2 17 = 3 17 , p_A(0\mid x)=\frac{N}{17}\cdot\frac{1}{N}+\frac{17-N}{34}\cdot0+\frac{17-N}{34}\cdot\frac{4}{17-N}=\frac{1}{17}+\frac{2}{17}=\frac{3}{17}, p A ( 0 ∣ x ) = 17 N ⋅ N 1 + 34 17 − N ⋅ 0 + 34 17 − N ⋅ 17 − N 4 = 17 1 + 17 2 = 17 3 ,
and the same argument with the second and third classes interchanged gives p B ( 0 ∣ y ) = 3 / 17 p_B(0\mid y)=3/17 p B ( 0 ∣ y ) = 3/17 . For binary outcomes these three numbers determine the whole box,
p ( 0 , 1 ∣ x , y ) = p A ( 0 ∣ x ) − p ( 0 , 0 ∣ x , y ) , p ( 1 , 0 ∣ x , y ) = p B ( 0 ∣ y ) − p ( 0 , 0 ∣ x , y ) , p ( 1 , 1 ∣ x , y ) = 1 − p A ( 0 ∣ x ) − p B ( 0 ∣ y ) + p ( 0 , 0 ∣ x , y ) . \begin{aligned}
p(0,1\mid x,y)&=p_A(0\mid x)-p(0,0\mid x,y),\\
p(1,0\mid x,y)&=p_B(0\mid y)-p(0,0\mid x,y),\\
p(1,1\mid x,y)&=1-p_A(0\mid x)-p_B(0\mid y)+p(0,0\mid x,y).
\end{aligned} p ( 0 , 1 ∣ x , y ) p ( 1 , 0 ∣ x , y ) p ( 1 , 1 ∣ x , y ) = p A ( 0 ∣ x ) − p ( 0 , 0 ∣ x , y ) , = p B ( 0 ∣ y ) − p ( 0 , 0 ∣ x , y ) , = 1 − p A ( 0 ∣ x ) − p B ( 0 ∣ y ) + p ( 0 , 0 ∣ x , y ) .
which reproduces Table 2 . The mixture therefore equals p ⋆ p^\star p ⋆ , so p ⋆ p^\star p ⋆ is local for every N ≤ 13 N\le13 N ≤ 13 . The construction breaks down exactly where it must: for N ≥ 14 N\ge14 N ≥ 14 , p ⋆ p^\star p ⋆ violates Eq. (22) , so no local model exists.
Relation to the work of Klauck and de Wolf
The quantum part of our results is closely related to the work of Klauck and de Wolf [32 ] , who adapted the fooling-set method of classical communication complexity [50 , 51 ] to quantum protocols with prior entanglement. This appendix recalls their setting and results, relates their key inequality to Lemma 2 and to the witness of Corollary 2, extends their argument to commuting-operator models and compares the resulting bounds with ours. Table 4 summarizes the comparison.
Table 4. Comparison with Ref. [32 ] for zero-error certification of equality of N = 2 n N=2^n N = 2 n labels. “Guessing” refers to the removal of classical communication in Proposition 4, the classical counterpart of their Lemma 1.
Setting and results
Let f : X × Y → { 0 , 1 } f:X\times Y\to\{0,1\} f : X × Y → { 0 , 1 } be a Boolean function. A 1-fooling set of size N N N is a set of N N N input pairs which, after a relabelling of Bob’s inputs, can be written as { ( x , x ) } x ∈ [ N ] \{(x,x)\}_{x\in[N]} {( x , x ) } x ∈ [ N ] , such that f ( x , x ) = 1 f(x,x)=1 f ( x , x ) = 1 for every x x x and, for x ≠ y x\ne y x = y , f ( x , y ) = 0 f(x,y)=0 f ( x , y ) = 0 or f ( y , x ) = 0 f(y,x)=0 f ( y , x ) = 0 . It is upper triangular if, for some ordering of the labels, f ( x , y ) = 0 f(x,y)=0 f ( x , y ) = 0 whenever x > y x>y x > y . For equality all off-diagonal values vanish, so the diagonal is an upper-triangular 1-fooling set of size N N N . A one-sided-error protocol never outputs 1 on an input with f = 0 f=0 f = 0 , and outputs 1 with probability at least 1 / 2 1/2 1/2 on every input with f = 1 f=1 f = 1 . For equality, such a protocol never certifies equality wrongly and certifies it with probability at least 1 / 2 1/2 1/2 whenever the inputs coincide: it is the one-sided version of our task, in which equality is the only conclusive answer. Klauck and de Wolf denote by Q 1 ∗ ( f ) Q_1^\ast(f) Q 1 ∗ ( f ) the one-sided-error communication complexity with unlimited prior entanglement, in which communication is counted in qubits and may be interactive. Their main result (Theorem 1 of Ref. [32 ] ) states that
Q 1 ∗ ( f ) ≥ 1 2 log 2 N − 1 2 (31) Q_1^\ast(f)\ge\frac{1}{2}\log_2 N-\frac{1}{2} \tag*{(31)} Q 1 ∗ ( f ) ≥ 2 1 log 2 N − 2 1 (31)
whenever f f f has an upper-triangular 1-fooling set of size N N N . For the n n n -bit equality, disjointness and greater-than functions, N = 2 n N=2^n N = 2 n , and Eq. (31) gives n / 2 − 1 / 2 n/2-1/2 n /2 − 1/2 , which supersende coding [66 ] shows to be optimal up to an additive constant. They also prove a bound with constant 1 / 4 1/4 1/4 for arbitrary 1-fooling sets, obtain lower bounds on zero-error (Las Vegas) complexity from Q 0 ∗ ( f ) ≥ max { Q 1 ∗ ( f ) , Q 1 ∗ ( ¬ f ) } Q_0^\ast(f)\ge\max\{Q_1^\ast(f),Q_1^\ast(\neg f)\} Q 0 ∗ ( f ) ≥ max { Q 1 ∗ ( f ) , Q 1 ∗ ( ¬ f )} , and bound nondeterministic quantum communication complexity without shared resources in terms of fooling sets.
The two steps of the proof. The proof of Eq. (31) has two steps. The first removes communication (Lemma 1 of Ref. [32 ] ). Each communicated qubit is teleported [67 ] with an additional EPR pair and two classical bits, and both parties proceed as if every pair of teleportation bits were 00. These bits are uniformly random and independent of the inputs and of the rest of the protocol, so the resulting protocol without communication accepts, in the sense that both parties output 1, with probability exactly 4 − q 4^{-q} 4 − q times the acceptance probability of the original q q q -qubit protocol. Applied to a one-sided-error protocol, it produces a tensor-product box that never accepts on the pairs x > y x>y x > y and accepts each diagonal pair with probability at least 4 − q / 2 4^{-q}/2 4 − q /2 . The second step bounds the diagonal by the following inequality (Claim 1 of Ref. [32 ] ): if w w w is a vector in a bipartite Hilbert space and A x A_x A x , B y B_y B y are effects with ⟨ w , ( A x ⊗ B y ) w ⟩ = 0 \langle w,(A_x\otimes B_y)w\rangle=0 ⟨ w , ( A x ⊗ B y ) w ⟩ = 0 for all x > y x>y x > y , then
∑ x = 1 N ⟨ w , ( A x ⊗ B x ) w ⟩ ≤ ∥ w ∥ 2 . (32) \sum_{x=1}^{N}\langle w,(A_x\otimes B_x)w\rangle\leq\lVert w\rVert^2. \tag*{(32)} x = 1 ∑ N ⟨ w , ( A x ⊗ B x ) w ⟩ ≤ ∥ w ∥ 2 . (32)
Hence N 4 − q / 2 ≤ 1 N4^{-q/2}\leq1 N 4 − q /2 ≤ 1 , which is Eq. (31) .
In the language of § 6 , with acceptance relabelled as outcome 0, Eq. (32) is the face witness (21) for tensor-product boxes, valid on the larger face
F 0 u t = { p : p ( 0 , 0 ∣ x , y ) = 0 whenever x > y } ⊇ F 0 . F_0^{\mathrm{ut}}=\{p:p(0,0|x,y)=0\text{ whenever }x>y\}\supseteq F_0. F 0 ut = { p : p ( 0 , 0∣ x , y ) = 0 whenever x > y } ⊇ F 0 .
The two arguments run in opposite directions. Klauck and de Wolf convert a protocol into a box on this face and apply the inequality, whereas Corollary 2 converts a box on F 0 F_0 F 0 into a one-bit protocol, protocol (a) of § 5.1 , and applies the sum rule.
The inequality for commuting operators. Klauck and de Wolf prove Eq. (32) by induction on N N N , splitting w w w with the support projection of A N ⊗ I A_N\otimes I A N ⊗ I . For tensor-product models it also follows from Lemma 2, applied with the labels in decreasing order to F x = A x F_x=A_x F x = A x and to Alice’s steered operators T y = tr B [ ( I ⊗ B y ) ∣ w ⟩ ⟨ w ∣ ( I ⊗ B y ) ] ≤ tr B ∣ w ⟩ ⟨ w ∣ T_y=\operatorname{tr}_{B}[(I\otimes\sqrt{B_y})|w\rangle\langle w|(I\otimes\sqrt{B_y})]\leq\operatorname{tr}_{B}|w\rangle\langle w| T y = tr B [( I ⊗ B y ) ∣ w ⟩ ⟨ w ∣ ( I ⊗ B y )] ≤ tr B ∣ w ⟩ ⟨ w ∣ : for x > y x>y x > y , tr ( A x T y ) = ⟨ w , ( A x ⊗ B y ) w ⟩ = 0 \operatorname{tr}(A_xT_y)=\langle w,(A_x\otimes B_y)w\rangle=0 tr ( A x T y ) = ⟨ w , ( A x ⊗ B y ) w ⟩ = 0 , and positivity gives A x T y = 0 A_xT_y=0 A x T y = 0 . Both proofs rest on the same principle, that a test certain to fail on a state leaves the state undisturbed. The sequential form of Lemma 2 carries over to commuting-operator models, because the effects it constructs belong to the algebra generated by Alice’s operators.
Proposition 3 (Triangular packing). Let ψ \psi ψ be a vector in a Hilbert space, and let A 1 , … , A N A_1,\ldots,A_N A 1 , … , A N and B 1 , … , B N B_1,\ldots,B_N B 1 , … , B N be effects such that A x B y = B y A x A_xB_y=B_yA_x A x B y = B y A x for all x , y x,y x , y , and ⟨ ψ , A x B y ψ ⟩ = 0 \langle\psi,A_xB_y\psi\rangle=0 ⟨ ψ , A x B y ψ ⟩ = 0 whenever x > y x>y x > y . Then
∑ x = 1 N ⟨ ψ , A x B x ψ ⟩ ≤ ∥ ψ ∥ 2 . (33) \sum_{x=1}^{N}\langle\psi,A_xB_x\psi\rangle\leq\lVert\psi\rVert^2. \tag*{(33)} x = 1 ∑ N ⟨ ψ , A x B x ψ ⟩ ≤ ∥ ψ ∥ 2 . (33) In particular, every binary-outcome box p ∈ C q c ∩ F 0 u t p\in\mathrm{C}_{\mathrm{qc}}\cap F_0^{\mathrm{ut}} p ∈ C qc ∩ F 0 ut satisfies ∑ x p ( 0 , 0 ∣ x , x ) ≤ 1 \sum_xp(0,0|x,x)\leq1 ∑ x p ( 0 , 0∣ x , x ) ≤ 1 , for every N N N .
Proof. Every operator in the norm-closed algebra generated by A 1 , … , A N A_1,\ldots,A_N A 1 , … , A N , such as I − A x \sqrt{I-A_x} I − A x , commutes with every B y B_y B y and with every B y \sqrt{B_y} B y . Put v y = B y ψ v_y=\sqrt{B_y}\psi v y = B y ψ . For x > y x>y x > y , ∥ A x v y ∥ 2 = ⟨ ψ , A x B y ψ ⟩ = 0 \lVert\sqrt{A_x}v_y\rVert^2=\langle\psi,A_xB_y\psi\rangle=0 ∥ A x v y ∥ 2 = ⟨ ψ , A x B y ψ ⟩ = 0 , so A x v y = 0 A_xv_y=0 A x v y = 0 . Apply the Lüders tests A N , A N − 1 , … , A 1 A_N,A_{N-1},\ldots,A_1 A N , A N − 1 , … , A 1 in this order and stop at the first “yes”. With C N = I C_N=I C N = I and C x − 1 = I − A x C x C_{x-1}=\sqrt{I-A_x}C_x C x − 1 = I − A x C x , the outcome “first yes at test x x x ” has effect K x = C x † A x C x K_x=C_x^\dagger A_xC_x K x = C x † A x C x , and, as in the proof of Lemma 2, ∑ x K x = I − C 0 † C 0 ≤ I \sum_xK_x=I-C_0^\dagger C_0\leq I ∑ x K x = I − C 0 † C 0 ≤ I . The tests performed before A y A_y A y are those with x > y x>y x > y ; they annihilate v y v_y v y , so ∑ x ≤ y ⟨ v y , A x v y ⟩ = ⟨ v y , K y v y ⟩ \sum_{x\leq y}\langle v_y,A_xv_y\rangle=\langle v_y,K_yv_y\rangle ∑ x ≤ y ⟨ v y , A x v y ⟩ = ⟨ v y , K y v y ⟩ . Since K y K_y K y commutes with B y B_y B y and 0 ≤ B y ≤ I 0\leq B_y\leq I 0 ≤ B y ≤ I , we have K y 1 / 2 ( I − B y ) K y 1 / 2 ≥ 0 K_y^{1/2}(I-B_y)K_y^{1/2}\geq0 K y 1/2 ( I − B y ) K y 1/2 ≥ 0 , and therefore
⟨ ψ , A y B y ψ ⟩ = ⟨ v y , A y v y ⟩ = ⟨ v y , K y v y ⟩ = ⟨ ψ , K y B y ψ ⟩ ≤ ⟨ ψ , K y ψ ⟩ . \langle\psi,A_yB_y\psi\rangle=\langle v_y,A_yv_y\rangle=\langle v_y,K_yv_y\rangle=\langle\psi,K_yB_y\psi\rangle\leq\langle\psi,K_y\psi\rangle. ⟨ ψ , A y B y ψ ⟩ = ⟨ v y , A y v y ⟩ = ⟨ v y , K y v y ⟩ = ⟨ ψ , K y B y ψ ⟩ ≤ ⟨ ψ , K y ψ ⟩ .
Summing over y y y gives Eq. (33) . For a box in C q c \mathrm{C}_{\mathrm{qc}} C qc , take a unit vector ψ \psi ψ and commuting measurements that realize it, and put A x = A 0 ∣ x A_x=A_0|_x A x = A 0 ∣ x and B y = B 0 ∣ y B_y=B_0|_y B y = B 0 ∣ y .
Tensor-product effects A x ⊗ I A_x\otimes\mathbb{I} A x ⊗ I and I ⊗ B y \mathbb{I}\otimes B_y I ⊗ B y commute, so Proposition 3 contains Eq. (32) . On F 0 F_0 F 0 it gives Corollary 2 for commuting-operator models without the restriction N ≥ 3 N\geq3 N ≥ 3 , which enters Corollary 2 only through Theorem 1. It fails for almost-quantum correlations: the boxes p ∗ p^* p ∗ lie in C A Q ∩ F 0 ⊆ F 0 u t \mathrm{C}_{\mathrm{AQ}}\cap F_0\subseteq F_0^{\mathrm{ut}} C AQ ∩ F 0 ⊆ F 0 ut and violate the bound for every N ≥ 18 N\geq18 N ≥ 18 , and the optimal AQ boxes violate it for every N ≥ 9 N\geq9 N ≥ 9 ; at Level 1 the optimal boxes violate it for every N ≥ 5 N\geq5 N ≥ 5 . The proof breaks where K y K_y K y , which composes several of Alice’s operators, is moved past B y B_y B y ; the AQ condition (1) provides commutation only for single operators acting on ψ \psi ψ . Read as a constraint on correlations, the inequality of Klauck and de Wolf thus holds throughout C q c \mathrm{C}_{\mathrm{qc}} C qc and fails in C A Q \mathrm{C}_{\mathrm{AQ}} C AQ .
Removing classical communication. When the parties communicate classical bits, the first step of the argument needs no teleportation. The following statement is the classical counterpart of Lemma 1 of Ref. [32 ] , combined with Proposition 3.
Proposition 4 (Transcript guessing). Consider a protocol for E Q N \mathrm{EQ}_N EQ N , possibly interactive, in which the parties exchange c c c classical bits in total, share randomness, and either share an entangled state or act on a common Hilbert space with commuting operator algebras. If the protocol never declares equality on an input pair with s ≠ t s\ne t s = t , then
∑ t = 1 N Pr ( G = 1 ∣ t , t ) ≤ 2 c . (34) \sum_{t=1}^{N}\Pr(G=1\mid t,t)\leq2^c. \tag*{(34)} t = 1 ∑ N Pr ( G = 1 ∣ t , t ) ≤ 2 c . (34)
Proof. Shared randomness can be absorbed into the shared state, and padding ensures that every run exchanges exactly c c c bits. Let r ∈ { 0 , 1 } c r\in\{0,1\}^c r ∈ { 0 , 1 } c be uniformly random, shared and independent of everything else. Without communicating, each party runs its part of the protocol on the shared state, using the bits of r r r in place of the messages it would receive and checking whether the messages it would send agree with the corresponding bits of r r r . Alice outputs 0 if all her checks succeed; Bob outputs 0 if all his checks succeed and the run declares equality; otherwise a party outputs 1. Each party’s operations depend only on its input and on the messages it receives. Hence, for every transcript τ \tau τ , the probability that r = τ r=\tau r = τ , that all checks succeed and that the run declares equality equals 2 − c 2^{-c} 2 − c times the probability that a genuine run produces τ \tau τ and declares equality. Summing over τ \tau τ gives a box with p ( 0 , 0 ∣ s , t ) = 2 − c Pr ( G = 1 ∣ s , t ) p(0,0\mid s,t)=2^{-c}\Pr(G=1\mid s,t) p ( 0 , 0 ∣ s , t ) = 2 − c Pr ( G = 1 ∣ s , t ) . Each party’s acceptance effect is built from its own operations alone, so the box is a tensor-product, respectively commuting-operator, box with binary outcomes, and by hypothesis it lies on F 0 F_0 F 0 . Proposition 3 gives 2 − c ∑ t Pr ( G = 1 ∣ t , t ) ≤ 1 2^{-c}\sum_t\Pr(G=1\mid t,t)\leq1 2 − c ∑ t Pr ( G = 1 ∣ t , t ) ≤ 1 .
Comparison of the bounds. For a single bit of one-way communication, Proposition 4 gives ∑ t Pr ( G = 1 ∣ t , t ) ≤ 2 \sum_t\Pr(G=1\mid t,t)\leq2 ∑ t Pr ( G = 1 ∣ t , t ) ≤ 2 and hence η C q c ( N ) ≤ 2 / N \eta_{\mathrm{Cqc}}(N)\leq2/N η Cqc ( N ) ≤ 2/ N . Theorem 1 removes the factor 2, which is the price of guessing the message. It keeps the message instead: since N ≥ 3 N\geq3 N ≥ 3 , a third label shows that the acceptance sectors of the two messages are orthogonal, so the packing for both messages fits into a single copy of Alice’s reduced state, or of ψ \psi ψ , and the resulting value 1 / N 1/N 1/ N is attained with shared randomness. The restriction N ≥ 3 N\geq3 N ≥ 3 is essential: for N = 2 N=2 N = 2 Alice can send her label, the efficiency is 1, and the bound 2 of Eq. (34) is attained. For K K K one-way messages, the same argument with a uniformly random guess of the message gives ∑ t Pr ( G = 1 ∣ t , t ) ≤ K \sum_t\Pr(G=1\mid t,t)\leq K ∑ t Pr ( G = 1 ∣ t , t ) ≤ K and η ≤ K / N \eta\leq K/N η ≤ K / N , whereas Theorem 5 gives ∑ t ≠ u Pr ( G = 1 ∣ t , t ) ≤ K − 1 \sum_{t\ne u}\Pr(G=1\mid t,t)\leq K-1 ∑ t = u Pr ( G = 1 ∣ t , t ) ≤ K − 1 and η ≤ ( K − 1 ) / ( N − 1 ) \eta\leq(K-1)/(N-1) η ≤ ( K − 1 ) / ( N − 1 ) , which is smaller precisely when N > K N>K N > K ; the classical value is ( K − 1 ) / N (K-1)/N ( K − 1 ) / N . For the zero-error cost of n n n -bit equality, a protocol that is conclusive with probability at least 1 / 2 1/2 1/2 on every input pair has ∑ t Pr ( G = 1 ∣ t , t ) ≥ N / 2 \sum_t \Pr(G=1\mid t,t) \ge N/2 ∑ t Pr ( G = 1 ∣ t , t ) ≥ N /2 , so Eq. (34) requires c ≥ n − 1 c \ge n-1 c ≥ n − 1 classical bits, even with interaction, while Klauck and de Wolf obtain n / 2 − 1 / 2 n/2-1/2 n /2 − 1/2 for qubit communication. Corollary 4 determines the one-way cost with classical messages exactly, namely n n n bits in every quantum model, whereas almost-quantum correlations need at most 13. Quantum messages lie outside the scope of this paper: superdense coding halves their cost, and Eq. (31) is the relevant bound there.
The shared-randomness protocol. Klauck and de Wolf also observe that shared randomness trivializes nondeterministic communication complexity: with a shared, uniformly random r ∈ X r \in X r ∈ X , Alice announces whether x = r x=r x = r , and Bob outputs f ( r , y ) f(r,y) f ( r , y ) if she does and 0 otherwise. For equality, this one-bit protocol never accepts an unequal pair and accepts every equal pair with probability 1 / N 1/N 1/ N ; it is the shared-randomness protocol of Corollary 1. Theorem 1 shows that no one-bit protocol assisted by entanglement, or by commuting-operator correlations, does better, whereas almost-quantum correlations do better by an unbounded factor (Theorems 2 and 3).
Scope. The results of Ref. [32 ] apply to every function with a large 1-fooling set, to interactive protocols and to qubit communication, and they also bound nondeterministic quantum communication complexity. Our quantum bounds are restricted to equality and, apart from Proposition 4, to one-way classical messages; within this setting they are exact, and they hold in the commuting-operator model. The post-quantum part of this paper has no counterpart in Ref. [32 ] . The contributions of this paper on the quantum side are therefore the exact one-way values (Theorems 1 and 5 and Corollaries 1, 3 and 4) and the extension of these bounds, together with Propositions 3 and 4, to commuting-operator models. The almost-quantum constructions and optimizations of § 5 and § 8 do not rely on any of these bounds.
ACKNOWLEDGEMENT: JK and BC acknowledge support from University Grants Commission, India (Reference no. 231620167137 and 241620129062, respectively). RKP acknowledges support from the EU (CHISTERA MoDIC) and from the National Research, Development and Innovation Office NKFIH (No. 2023-1.2.1-ERA-NET-2023-00009). MB acknowledges the financial support through the National Quantum Mission (NQM) of the Department of Science and Technology, Government of India.
Use of AI tools. The problem was conceived and all principal results were derived by the authors. A large language model (Claude, Anthropic) was used to assist with editing the text, simplifying the analytic certificates in § 5 and § 8 . ChatGPT (OpenAI) was also used to assist with simplifying the quantum proofs in § 4 . Every derivation and certificate reported here was checked independently in exact arithmetic; no result relies on an assertion of correctness by an AI tool.
References