Normalized counting by support-intersection size
ProvedQuantumLTF.Majority.normalized_intersection_sumadversary-methodboolean-cubecombinatoricssection-4
Let have cardinality . For any real function of the intersection size, averaging uniformly over Boolean query strings gives the binomial distribution:
Indeed, for each fixed , there are choices inside and unrestricted choices outside . This identity converts the dual matrix’s diagonal sum into the weighted Krawtchouk norm.
Preamble
import Mathlib import Definitions.Def_QuantumLTF_Majority_AdversaryModel
Formal statement
namespace QuantumLTF.Majority open QAlgorithms theorem normalized_intersection_sum : ∀ n r : ℕ, r ≤ n → ∀ A : ExactSupports n r, ∀ f : Fin (r+1) → ℝ, (2 : ℝ)^(-n : ℤ) * ∑ S : Qubits n, f (intersectionIndex A S) = (1/(2:ℝ)^r) * ∑ a : Fin (r+1), (r.choose a : ℝ) * f a := by sorry end QuantumLTF.Majority
Source
Elementary Hamming-slice counting used in the diagonal objective calculation of Krivcenko, Nguyen, de Wolf, arXiv:2609.40331v3, Section 4.2.