Lemma 4.5 — logarithmic objective value
OpenQuantumLTF.Majority.lemma_4_5adversary-methodsection-4
The bounded-support feasible solution has objective .
Preamble
import Mathlib import Definitions.Def_QuantumLTF_Majority_AdversaryModel
Formal statement
namespace QuantumLTF.Majority open QAlgorithms theorem lemma_4_5 : ∃ C : ℝ, 0<C ∧ ∀ n k : ℕ, 2≤k → k≤n → ∃ X : Qubits n → Matrix (BoundedSupports n k) (BoundedSupports n k) ℝ, DualFeasible (fun A : BoundedSupports n k => A.1) X ∧ DualCostAtMost X (C*Real.log k) := by sorry end QuantumLTF.Majority
Source
Krivcenko, Nguyen, de Wolf, STOC 2027 submission #347, Lemma 4.5, p.47.