Lemma 4.6 — norm of the lower-bound adversary matrix
OpenQuantumLTF.Majority.lemma_4_6adversary-methodmatrix-normssection-4
For the adversary matrix of Eq. (128) on the -subsets of a known -element universe, .
Preamble
import Mathlib import Definitions.Def_QAlgorithms_Defs_Circuit import Definitions.Def_QuantumLTF_Majority_AdversaryModel
Formal statement
namespace QuantumLTF.Majority
open QAlgorithms
theorem lemma_4_6 : ∀ {n m : ℕ} (U : Finset (Fin n)), U.card=2*m → specNorm (fun A B : {A : Finset (Fin n) // A⊆U ∧ A.card=m} => (lowerAdversary U A B : ℂ)) = ∑ s ∈ Finset.Icc 1 m, (1:ℝ)/s := by sorry
end QuantumLTF.MajoritySource
Krivcenko, Nguyen, de Wolf, STOC 2027 submission #347, Lemma 4.6, p.49 (PDF p.50).