Random subset parities: two distinct strings agree on parities with probability
ProvedBBPSSW.Distill.random_parity_agreebbpsswentanglement-distillationp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-information
Let be -bit strings, and choose subsets independently and uniformly at random. Then
This is the fact behind BXOR tests: each test reveals the parity of a random subset of the unknown error string, so about (number of candidates) tests single it out.
Differences from the source:
- encoding: probability over r independent random subsets → the number of agreeing r-tuples of subsets divided by the number (2^n)^r of all r-tuples; reason: uniform independent subsets; bits in ZMod 2
Preamble
import Mathlib
Formal statement
namespace BBPSSW.Distill
/-- **Random subset parities separate distinct strings.**
Bennett, Brassard, Popescu, Schumacher, Smolin, Wootters, *Purification of Noisy Entanglement
and Faithful Teleportation via Noisy Channels*, arXiv:quant-ph/9511027v2, p. 3 (unnumbered bullet): "For any two distinct n-bit strings the probability that they
agree on the parities of r independent random subsets of their bits is ≤ 2^−r [10]."
Let `x ≠ y` be `n`-bit strings. Choose `r` subsets `S₁, …, S_r ⊆ {1, …, n}` independently and
uniformly at random (all `(2^n)^r` tuples equally likely). The probability that
`∑_{i ∈ S_j} x_i = ∑_{i ∈ S_j} y_i (mod 2)` for every `j` is at most `2^{−r}`.
**Formalization Note.** Bits are `ZMod 2`; the probability is the number of agreeing tuples
`(S_j)_{j < r}` divided by the number `(2^n)^r` of all tuples. -/
theorem random_parity_agree (n r : ℕ) (x y : Fin n → ZMod 2) (hxy : x ≠ y) :
((Finset.univ.filter fun S : Fin r → Finset (Fin n) =>
∀ j, ∑ i ∈ S j, x i = ∑ i ∈ S j, y i).card : ℝ) /
(Fintype.card (Fin r → Finset (Fin n)) : ℝ) ≤ (1 / 2 : ℝ) ^ r := by sorry
end BBPSSW.Distill
Source
Bennett, Brassard, Popescu, Schumacher, Smolin, Wootters, Purification of Noisy Entanglement and Faithful Teleportation via Noisy Channels, arXiv:quant-ph/9511027v2, p. 3, unnumbered bullet ("For any two distinct n-bit strings …")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.