Unbounded degree overhead for Alice-conditioned quantum Bell certificates

Technical Summary: Unbounded Degree Overhead for Alice-Conditioned Quantum Bell Certificates

Problem Statement
The paper investigates the computational cost of certifying quantum Bell bounds within the Navascués–Pironio–Acín (NPA) hierarchy when the certificate structure is constrained. Specifically, it examines "Alice-conditioned" hierarchies, where each sum-of-squares (SOS) term in the dual certificate must involve only one of Alice's measurement questions. This structure is relevant for compiled nonlocal games and specific cryptographic soundness proofs (e.g., the "nice-SOS" route). The central question is whether restricting the certificate to this "single-question" structure imposes a bounded overhead in the degree of the SOS decomposition compared to standard, unconstrained certificates. The author focuses on the tilted-CHSH family of Bell functionals, where standard certificates are known to be exact at level two.

Methodology
The author employs a combination of analytic construction, algebraic verification, and numerical optimization within the framework of semidefinite programming (SDP) and operator algebras.

1. Hierarchies and Cones: The study compares two cones of SOS certificates in real Bell-gap space:

   • $D_k$: Standard degree-$k$ certificates (words of total reduced length $\le k$).
   • $O_k$: Alice-conditioned degree-$k$ certificates (Bob words of length $\le k$ in blocks indexed by Alice's question/answer).
     The conversion degree $d_{std}$ and $d_{os}$ are defined as the minimum level required to certify a specific bound $\beta$.

2. Analytic Counterexamples (Unbounded Overhead): To prove that no finite conditioned level contains all standard level-two certificates, the author constructs a family of feasible witnesses using positive functionals on the infinite dihedral group ($\mathbb{Z}_2 * \mathbb{Z}_2$).

   • They utilize a Fejér-weighted trace to construct a positive functional that concentrates mass on specific Bob words.
   • By subtracting a rank-one term corresponding to a deterministic Bob response weighted by $r_k \sim k^{-2}$, they create a witness that violates the positivity constraints of any finite conditioned level $k$ for a specific tilt $\alpha_k$ approaching the local endpoint ($\alpha \to 2$).
   • This construction relies on the Gram matrix of a moving average, where the rank-one subtraction remains positive semidefinite only if the conditioned level is sufficiently high.

3. Exact Certificates on Intervals: Conversely, to identify regimes where the overhead is bounded, the author constructs exact certificates for specific intervals of the tilt parameter $\alpha$.

   • Optimal-Face Reduction: They utilize the optimal strategy of the tilted-CHSH game to identify the kernel of the moment matrices. This reduces the dual certificate search to finding positive semidefinite (PSD) matrices on the kernel's orthogonal complement.
   • Rational-Function Families: For the interval $\alpha \in [13/10, 3/2]$, they parameterize the quantum bound and the strategy kernels using rational functions. They construct a continuous family of certificates where the Gram matrices are degree-20 matrix polynomials.
   • Bernstein Positivity: They verify the positivity of these polynomials over the interval by expanding them into Bernstein bases and checking that all coefficient matrices are strictly PSD.

4. Randomness Certification: The paper translates these Bell-bound separations into device-independent randomness certification. Using a contact criterion involving the concavity of the guessing probability function, they show that a separation in Bell bounds directly implies a separation in certified min-entropy.

Key Contributions and Results

• Unbounded Degree Overhead: The primary result (Theorem 1) proves that for the tilted-CHSH family, no finite level of the Alice-conditioned hierarchy contains all standard level-two certificates. Specifically, as the tilt $\alpha$ approaches the local endpoint ($\alpha \to 2$), the required conditioned level $d_{os}$ grows at least as $\Omega((2-\alpha)^{-1/2})$.

  • For any integer $k$, there exists a tilt $\alpha_k$ such that the standard certificate is exact at level 2 ($d_{std}=2$), but the conditioned certificate requires a level strictly greater than $k$ ($d_{os} > k$).
  • This establishes that the "single-question" restriction can force an unbounded increase in algebraic resources, even when a low-degree standard certificate exists.

• Exact Finite Conversion on Intervals: Despite the unbounded overhead near the endpoint, the author proves (Theorem 2) that on the continuous interval $\alpha \in [13/10, 3/2]$, the overhead is exactly one level.

  • For all $\alpha$ in this range, $d_{std} = 2$ and $d_{os} = 3$.
  • This is demonstrated via an explicit rational-function certificate family verified using Bernstein positivity, proving that the conditioned hierarchy can close exactly at level 3 for this subfamily.

• Separation of Level-One Values: The paper corrects a previous claim regarding level-one equivalence. It proves (Theorem 3.7) that for tilted-CHSH with $\alpha > 0$, the standard level-one value is strictly greater than the Alice-conditioned level-one value ($\omega_{std}^1 > \omega_{os}^1$). This is due to the fact that conditioned blocks at level one implicitly include total-degree-three moments (via the block label) that are absent in the standard level-one truncation.

• Device-Independent Randomness: The author demonstrates (Theorem 3) that the unbounded degree overhead has operational consequences. No finite conditioned level can certify the entire optimal CHSH randomness tradeoff against quantum side information, whereas standard level two can. Specifically, for a sequence of CHSH values $s_k \to 2$, the certified min-entropy using conditioned level $k$ is strictly lower than the quantum optimum, with a deficit exceeding $10^{-3}$ bits for specific points.

• Implications for Compiled Soundness: The results provide a quantitative obstruction for "nice-SOS" inputs in compiled nonlocal game soundness proofs. The degree of the Bob-word factors in an exact nice-SOS certificate for a tilted bound near the endpoint must grow as $\Omega(\epsilon^{-1/2})$, limiting the efficiency of such proofs for arbitrary tilts.

Significance and Claims
The paper claims to separate the "ordinary SOS degree" from the "resources imposed by single-question certificate structure." It demonstrates that structural constraints on certificates, often motivated by cryptographic applications (compiled games), can fundamentally alter the convergence properties of the NPA hierarchy.

• Modesty of Claims: The author explicitly states that they do not claim a failure of compiled protocol security or a finite-key rate failure. The results concern the precision of single-round certification methods and the algebraic degree required for exact certificates.
• Open Problems: The paper acknowledges that while an asymptotic lower bound of $\Omega(\epsilon^{-1/2})$ is proven, an exact upper bound or proof of finite exact closure for every fixed subcritical tilt remains open. The numerical saturation suggests square-root growth, but a rigorous upper bound matching this exponent is not established.
• Correction of Literature: The work refines the understanding of the relationship between standard and conditioned hierarchies, specifically correcting a previous assertion about the equality of level-one values for tilted CHSH and clarifying the distinction between POVM/localizer filtrations and the raw PVM quotient used here.

In summary, the paper establishes that while Alice-conditioned hierarchies can be exact at low levels for specific parameter regimes, they suffer from an unbounded degree overhead near the boundary of the quantum set, preventing them from universally replacing standard hierarchies for exact certification tasks.