Diagonal cost of the exact-support Krawtchouk dual matrix
ProvedQuantumLTF.Majority.exact_support_krawtchouk_costadversary-methodcombinatoricskrawtchouk-polynomialssection-4
Fix an exact support of size , and form the rank-one dual matrices from the intersection transform . If the signed coefficient cross term vanishes and the coefficient energy is at most , then the diagonal dual objective is at most .
Indeed, among the Boolean query strings, exactly have intersection size with . Consequently the diagonal sum reduces to the weighted scalar Krawtchouk norm, which corrected Parseval identifies with the coefficient energy.
Preamble
import Mathlib import Definitions.Def_QuantumLTF_Majority_AdversaryModel
Formal statement
namespace QuantumLTF.Majority open QAlgorithms theorem exact_support_krawtchouk_cost : ∀ n r : ℕ, r ≤ n → ∀ p q : Fin (r+1) → ℝ, (∑ t : Fin (r+1), (r.choose t : ℝ) * ((-1 : ℝ) ^ (t : ℕ) * p t * q t)) = 0 → ∀ T : ℝ, (∑ t : Fin (r+1), (r.choose t : ℝ) * (p t^2 + q t^2)) ≤ T → let W := intersectionTransform r p q; let X : Qubits n → Matrix (ExactSupports n r) (ExactSupports n r) ℝ := fun S A B => (2:ℝ)^(-n:ℤ) * W (intersectionIndex A S) * W (intersectionIndex B S); DualCostAtMost X T := by sorry end QuantumLTF.Majority
Source
Krivcenko, Nguyen, de Wolf, arXiv:2609.40331v3, Section 4.2, diagonal objective calculation for the rank-one exact-support adversary matrices; corrected scalar Parseval plus Hamming-slice counting.