Joint bounded-support vector witness with logarithmic energy
OpenQuantumLTF.Majority.bounded_support_vector_moment_witnesscorrected-formalizationkrawtchouk-polynomialssection-4
For every promise , the coupled vector-polynomial construction of Section 4.3 provides vectors for all support sizes simultaneously. Their distinguishing Gram moments satisfy every dual adversary constraint, including cross-size pairs, and their maximum diagonal energy is bounded by .
Unlike an assembly of independent exact-size solutions, this theorem retains the correction coordinates that enforce the cross-size constraints in equations (121)–(124).
Preamble
import Mathlib import Definitions.Def_QuantumLTF_Majority_AdversaryModel
Formal statement
namespace QuantumLTF.Majority open QAlgorithms theorem bounded_support_vector_moment_witness : ∃ C : ℝ, 0 < C ∧ ∀ n k : ℕ, 2 ≤ k → k ≤ n → ∃ d : ℕ, ∃ W : ℕ → ℕ → Fin d → ℝ, (∀ A B : BoundedSupports n k, A ≠ B → (∑ S : Qubits n, if majorityBit A.1 S ≠ majorityBit B.1 S then (2:ℝ)^(-n:ℤ) * ∑ j : Fin d, W A.1.card ((A.1.filter fun i => S i).card) j * W B.1.card ((B.1.filter fun i => S i).card) j else 0) = 1) ∧ (∀ A : BoundedSupports n k, ∑ S : Qubits n, (2:ℝ)^(-n:ℤ) * ∑ j : Fin d, (W A.1.card ((A.1.filter fun i => S i).card) j)^2 ≤ C * Real.log k) := by sorry end QuantumLTF.Majority
Source
Krivcenko, Nguyen, de Wolf, arXiv:2609.40331v3, Section 4.3, Lemmas 4.4–4.5 and equations (117)–(126).