Logarithmic adversary cost for odd exact support size
OpenQuantumLTF.Majority.odd_exact_dual_log_costadversary-methodkrawtchouk-polynomialsquantum-query-complexitysection-4
There is a universal constant such that, for every odd support size , the exact-size Majority learning relation admits a feasible dual adversary solution of objective value at most
This is the odd-cardinality adversary construction obtained from the Krawtchouk polynomial families in Section 4.2. The corrected two-channel Parseval identity controls its diagonal objective.
Preamble
import Mathlib import Definitions.Def_QuantumLTF_Majority_AdversaryModel
Formal statement
namespace QuantumLTF.Majority open QAlgorithms theorem odd_exact_dual_log_cost : ∃ C : ℝ, 0 < C ∧ ∀ n r : ℕ, 3 ≤ r → r ≤ n → Odd r → ∃ X : Qubits n → Matrix (ExactSupports n r) (ExactSupports n r) ℝ, DualFeasible (fun A : ExactSupports n r => A.1) X ∧ DualCostAtMost X (C * Real.log r) := by sorry end QuantumLTF.Majority
Source
Krivcenko, Nguyen, de Wolf, Fast Quantum Algorithms for Learning Linear Threshold Functions, arXiv:2609.40331v3, Sections 4.2–4.3, odd-cardinality Krawtchouk adversary construction and logarithmic objective estimate.