Eq. (51) and the majority bound — odd batches give error
ProvedDesignTest.eq_51p2o-gran-per-chapterp2o-plan-bookp2o-strengthenedp2o-v1property-testingquantum-informationsample-complexitystate-designs
Let and let be an odd integer with
Let be independent random variables with values in (the error indicators of independent batches) and means . Then the majority vote errs with probability
This is the amplification step that turns the constant-error batch of Theorem 4.11 into a tester with failure probability at a cost of batches.
Formalization Note The indicators live on an arbitrary probability space and are measurable, independent in the sense of Mathlib's iIndepFun, and almost surely -valued.
Differences from the source:
- generalization: B is the smallest odd integer with B ≥ (32/9) log(1/δ_fail) → every odd B with B ≥ (32/9) log(1/δ); reason: the smallest such B is one of them
- generalization: batch error indicators with values in {0, 1} → measurable random variables that are {0, 1}-valued almost surely; reason: everywhere {0,1}-valued indicators are a special case
- encoding: the majority error → Pr[Σ_b X_b ≥ B/2]; reason: for odd B the majority errs exactly when at least B/2 batches err
Preamble
import Mathlib set_option autoImplicit false
Formal statement
namespace DesignTest
open MeasureTheory ProbabilityTheory
/-- **Equation (51) and the majority bound** (amplification). A. Kawachi, Y. Nakata, Y. Takeuchi,
*Testing State and Unitary Designs*, STOC 2027 submission (sha256 e2f0a429…), proof of Theorem 4.5,
eq. (51), p.34, and the following display, p.35; cited in the proof of Theorem 4.11, p.39.
Let `δ ∈ (0, 1/2)` and let `B` be an odd integer with `B ≥ (32/9) log(1/δ)`. If `X_1, …, X_B` are
independent `{0,1}`-valued random variables (the batch error indicators) with means at most `1/8`, the
majority errs with probability `Pr[Σ_b X_b ≥ B/2] ≤ exp(−2B(1/2 − 1/8)²) = exp(−9B/32) ≤ δ`.
**Formalization Note.** The indicators live on an arbitrary probability space; independence is Mathlib's
`iIndepFun`; `{0,1}`-valued is required almost surely. -/
theorem eq_51 (δ : ℝ) (hδ0 : 0 < δ) (hδ1 : δ < 1 / 2) (B : ℕ) (hBodd : Odd B)
(hB : 32 / 9 * Real.log (1 / δ) ≤ (B : ℝ)) {Ω : Type} [MeasurableSpace Ω] (P : Measure Ω)
[IsProbabilityMeasure P] (X : Fin B → Ω → ℝ) (hmeas : ∀ b, Measurable (X b))
(hind : iIndepFun X P) (h01 : ∀ b, ∀ᵐ ω ∂P, X b ω = 0 ∨ X b ω = 1)
(hmean : ∀ b, ∫ ω, X b ω ∂P ≤ 1 / 8) :
P {ω | (B : ℝ) / 2 ≤ ∑ b, X b ω} ≤ ENNReal.ofReal (Real.exp (-(9 * (B : ℝ) / 32))) ∧
Real.exp (-(9 * (B : ℝ) / 32)) ≤ δ := by sorry
end DesignTest
Source
Kawachi–Nakata–Takeuchi, Testing State and Unitary Designs, STOC 2027 submission (sha256 e2f0a429…), proof of Theorem 4.5, eq. (51), p.34, and the display following it, p.35; cited in the proof of Theorem 4.11, p.39
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.