Corrected rank-one feasibility lemma from separated moments
ProvedQuantumLTF.Majority.rank_one_dual_of_separated_momentsadversary-methodcorrected-formalizationsection-4
Let and be the lower- and upper-threshold components of the intersection transform. Assume that, on every pair of distinct supports and after restricting to distinguishing queries, the two same-side moments vanish and each of the two mixed moments equals . Then the rank-one Gram family generated by is dual feasible.
This is the faithful algebraic interface for the feasibility calculation in Lemma 4.1: equations (108)–(111) establish precisely these four moment identities from the degree and root-partition properties of the chosen polynomials.
Preamble
import Mathlib import Definitions.Def_QuantumLTF_Majority_AdversaryModel
Formal statement
namespace QuantumLTF.Majority open QAlgorithms theorem rank_one_dual_of_separated_moments : ∀ n 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) → let W := fun a => L a + U a; 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); DualFeasible (fun A : ExactSupports n r => A.1) X := by sorry end QuantumLTF.Majority
Source
Krivcenko, Nguyen, de Wolf, arXiv:2609.40331v3, Section 4.2.1, Lemma 4.1, especially equations (108)–(111).