Exact Noise Thresholds of Parity Proofs: Sub-Proof Roots under Independent Bit Flips

Source abstract

A parity proof of the Kochen-Specker theorem is a set of observables arranged in contexts of commuting observables whose products are ±I with an odd number of minus signs along a dependency. We study the exact noise threshold of such a proof at the maximally mixed state when every observable outcome is flipped independently with probability η/2 (model F). Contexts may have different sizes s c. We prove that for every parity proof η * F ≥ max T (1-x T) (the inequality of Cabello and of Trandafir, Lisone ǩ and Cabello applied to sub-proofs), where T runs over sub-proofs, k T ≥ 1 is the least number of contexts of T that a noncontextual assignment must violate, and x T ∈ (0, 1) is the root of ∑︁ c∈T x sc = |T |-2k T (1-x T := 1 if |T | ≤ 2k T). Under a symmetrisation condition (condition L, automatic for Pauli proofs with minimal contexts), and with s c the row weights of the incidence matrix, equality holds when the space K of dependencies is one-dimensional and, by a block reduction to a coset of a short code, whenever the contexts fall into at most dim K +1 nonzero incidence classes, and for direct sums of such proofs. With the theorem of Barahona and Grötschel on cycle polytopes of binary matroids the equality extends to every proof whose matroid of incidence classes has no minor F * 7 , R 10 or M * (K 5)-in particular to every proof with dim K ≤ 3 or with at most dim K + 2 incidence classes. Beyond this range the equality can fail for abstract proofs with condition L: for the simplex proof [7, 3] (dim K = 4, class matroid F * 7) η * F = 1-5-1/4 > max T (1-x T) = 1-3-1/4. For Pauli proofs whose class matroid has one of these minors it is open; a search with exact rational certificates at max T (1-x T) ± 10-10 over 360 abstract proofs with dim K = 2, 3, 4 found no discrepancy, including the 19 proofs with an F * 7 minor. The variant with a single root taken over the whole proof is false. Examples with mixed sizes give exact thresholds such as η * F = 0.1011287750. .. (4x 5 + x 4 = 3) for a four-qubit Mermin star. For uniform mixing we relate the equal-size value 2k min /m to the robustness measure of Trandafir, Lisone ǩ and Cabello and treat a qudit Mermin-Peres square. The methods are standard (parity and cycle polytopes, linear programming with exact certificates); what is new is the exact form of the thresholds, the reduction for overlapping dependencies, its link to cycle polytopes, and the certified values.