Proof of Lemma 3 — one prover message raises by at most
ProvedQStateSearch.entropy_stephaar-random-statesp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1quantum-interactive-proofsquantum-query-complexity
Let be a finite measure, a measurable set with , and a measurable map into (the reply of a padded -bit prover message), so that the sets partition . Put . Then
With , and , this is the step of the proof of Lemma 3 that charges each prover message at most its length in bits: the expected logarithmic inverse mass of the compatible set grows by the entropy of the reply, which is at most .
Formalization Note Terms with are on both sides.
Differences from the source:
- generalization: the Haar measure , the compatible set and the cells → any finite measure , any measurable with , the cells of any measurable reply map ; reason: the paper's case is , ,
- encoding: a -bit reply → ; masses as real numbers; reason: same objects
Preamble
import Mathlib open MeasureTheory
Formal statement
namespace QStateSearch
/-- **Proof of Lemma 3, one-message entropy step.** A padded `b`-bit prover message, given by a
measurable reply map `f` into `Fin (2 ^ b)`, partitions the compatible set `C` into the cells
`C_z = C ∩ f⁻¹{z}`. With `p_z = μ(C_z)/μ(C)`,
`∑_z p_z ln(1/μ(C_z)) = ln(1/μ(C)) + ∑_z p_z ln(1/p_z) ≤ ln(1/μ(C)) + b ln 2`.
Barhoush, *Quantum State Search with Classical Interactive Advice*, arXiv:2610.25657
(held version, sha256 2a16939a…3408), proof of Lemma 3, display after "Let p(z | h) = μ_D(C(hz))/μ_D(C(h))", p.12.
**Formalization Note.** Stated for any finite measure `μ` (the paper's is the Haar measure
`μ_D`) and measurable `C` of positive mass. Masses are `(μ X).toReal`. Lean's `log 0 = 0` is
harmless: every logarithm of a null cell is multiplied by `p_z = 0`. -/
theorem entropy_step {α : Type*} [MeasurableSpace α] (μ : Measure α) [IsFiniteMeasure μ]
(C : Set α) (hC : MeasurableSet C) (hpos : 0 < μ C) (b : ℕ) (f : α → Fin (2 ^ b))
(hf : ∀ z, MeasurableSet (f ⁻¹' {z})) :
∑ z, ((μ (C ∩ f ⁻¹' {z})).toReal / (μ C).toReal) * Real.log (1 / (μ (C ∩ f ⁻¹' {z})).toReal)
= Real.log (1 / (μ C).toReal) +
∑ z, ((μ (C ∩ f ⁻¹' {z})).toReal / (μ C).toReal) *
Real.log (1 / ((μ (C ∩ f ⁻¹' {z})).toReal / (μ C).toReal)) ∧
∑ z, ((μ (C ∩ f ⁻¹' {z})).toReal / (μ C).toReal) * Real.log (1 / (μ (C ∩ f ⁻¹' {z})).toReal)
≤ Real.log (1 / (μ C).toReal) + b * Real.log 2 := by sorry
end QStateSearch
Source
Barhoush, Quantum State Search with Classical Interactive Advice, arXiv:2610.25657 (held version, sha256 2a16939a…3408), proof of Lemma 3, display after the definition of , p.12
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.