Unbounded degree overhead for Alice-conditioned quantum Bell certificates

The Navascués–Pironio–Acín (NPA) hierarchy is a standard tool for certifying quantum Bell bounds using semidefinite programming (SDP). A variation, the Alice-conditioned hierarchy, organizes the certificate structure such that each sum-of-squares (SOS) term involves only one of Alice's measurement questions. This paper investigates the certification cost—the additional degree required—of this structural restriction compared to the standard NPA hierarchy, particularly for tilted CHSH inequalities.

The author employs a combination of analytic constructions and exact rational verification. By using Fejér-weighted positive functionals on the infinite dihedral group, the paper constructs an explicit family of truncated positive functionals that exceed the quantum bound at every finite Alice-conditioned level, while standard degree-two certificates remain exact. The study also uses optimal-strategy kernels and exact Bernstein matrix positivity to certify exactness on continuous intervals, providing a rigorous separation between standard SOS degree and the resources required by single-question certificate structures.

The study proves that no finite level of the Alice-conditioned NPA hierarchy can contain all standard level-two Bell certificates. Specifically, the required conditioned level grows at least as the square root of the inverse distance to the endpoint tilt. While standard level two is sufficient to certify the optimal CHSH randomness tradeoff, no finite Alice-conditioned level can certify this entire tradeoff. Furthermore, the paper identifies a continuous interval where exactly one extra level is required for Alice-conditioned certification, demonstrating that this unbounded cost coexists with exact finite conversion on specific subfamilies.

These findings highlight a significant limitation in the efficiency of Alice-conditioned hierarchies, which are often used in compiled nonlocal games and cryptographic soundness proofs. By separating ordinary SOS degree from the resources imposed by single-question certificate structures, the paper clarifies the quantitative overhead of these specific proof methods. This has direct implications for device-independent randomness certification, where the precision of single-round methods is constrained by the certificate structure.