Odd-size separated Krawtchouk witness with logarithmic energy
OpenQuantumLTF.Majority.odd_separated_krawtchouk_witnesscorrected-formalizationkrawtchouk-polynomialssection-4
For every odd support size , the degree- root-partition construction supplies lower- and upper-threshold Krawtchouk transforms and . Their same-side distinguishing moments vanish, both mixed moments equal , and the diagonal energy of is at most for a universal constant .
This combines the correctly stated feasibility content of Lemma 4.1 with the objective estimate of Lemmas 4.2–4.3, without discarding the transform-support information needed by the proof.
Preamble
import Mathlib import Definitions.Def_QuantumLTF_Majority_AdversaryModel
Formal statement
namespace QuantumLTF.Majority open QAlgorithms theorem odd_separated_krawtchouk_witness : ∃ C : ℝ, 0 < C ∧ ∀ n r : ℕ, 3 ≤ r → r ≤ n → Odd r → ∃ L U : Fin (r+1) → ℝ, (∀ A B : ExactSupports n r, A ≠ B → (∑ S : Qubits n, if majorityBit A.1 S ≠ majorityBit B.1 S then (2:ℝ)^(-n:ℤ) * L (intersectionIndex A S) * L (intersectionIndex B S) else 0) = 0) ∧ (∀ A B : ExactSupports n r, A ≠ B → (∑ S : Qubits n, if majorityBit A.1 S ≠ majorityBit B.1 S then (2:ℝ)^(-n:ℤ) * U (intersectionIndex A S) * U (intersectionIndex B S) else 0) = 0) ∧ (∀ A B : ExactSupports n r, A ≠ B → (∑ S : Qubits n, if majorityBit A.1 S ≠ majorityBit B.1 S then (2:ℝ)^(-n:ℤ) * L (intersectionIndex A S) * U (intersectionIndex B S) else 0) = 1/2) ∧ (∀ A B : ExactSupports n r, A ≠ B → (∑ S : Qubits n, if majorityBit A.1 S ≠ majorityBit B.1 S then (2:ℝ)^(-n:ℤ) * U (intersectionIndex A S) * L (intersectionIndex B S) else 0) = 1/2) ∧ (∀ A : ExactSupports n r, ∑ S : Qubits n, (2:ℝ)^(-n:ℤ) * (L (intersectionIndex A S) + U (intersectionIndex A S))^2 ≤ C * Real.log r) := by sorry end QuantumLTF.Majority
Source
Krivcenko, Nguyen, de Wolf, arXiv:2609.40331v3, Section 4.2, Lemmas 4.1–4.3 and equations (108)–(116).