Exact-support dual solution from a Krawtchouk witness
OpenQuantumLTF.Majority.exact_support_dual_from_krawtchouk_witnessadversary-methodkrawtchouk-polynomialsquantum-query-complexitysection-4
Let . Suppose satisfy the endpoint normalization and complementary-support conditions of the odd-support Krawtchouk construction, their weighted signed cross term is zero, and their binomial energy is at most . Then the rank-one Gram matrices obtained from their intersection Krawtchouk transform form a feasible dual adversary solution for exact supports of size , with objective at most .
The proof combines feasibility of the intersection transform, corrected scalar Parseval, and counting Boolean query strings by their intersection size with a fixed support.
Preamble
import Mathlib import Definitions.Def_QuantumLTF_Majority_AdversaryModel
Formal statement
namespace QuantumLTF.Majority open QAlgorithms theorem exact_support_dual_from_krawtchouk_witness : ∀ n r : ℕ, 3 ≤ r → r ≤ n → ∀ p q : Fin (r+1) → ℝ, p 0 * q 0 = 1/2 → (∀ t : Fin (r+1), 1 ≤ (t : ℕ) → (t : ℕ) < r → (p t = 0 ↔ q t ≠ 0)) → (∑ 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 → ∃ X : Qubits n → Matrix (ExactSupports n r) (ExactSupports n r) ℝ, DualFeasible (fun A : ExactSupports n r => A.1) X ∧ DualCostAtMost X T := by sorry end QuantumLTF.Majority
Source
Krivcenko, Nguyen, de Wolf, arXiv:2609.40331v3, Section 4.2: rank-one Krawtchouk adversary matrices, feasibility, and objective calculation leading to Lemmas 4.1–4.3.