Assemble exact-cardinality dual solutions for the bounded-support promise
OpenQuantumLTF.Majority.assemble_exact_support_dualsadversary-methodquantum-query-complexitysection-4
Suppose that, uniformly for every cardinality , the exact-size Majority relation has a feasible dual solution of cost at most . Then the full bounded-support relation has a feasible dual solution of cost at most for a universal constant .
The construction is the Section 4.3 direct-sum/auxiliary-component assembly. Its cross-cardinality components enforce the adversary constraints between supports of different sizes without summing the costs over all .
Preamble
import Mathlib import Definitions.Def_QuantumLTF_Majority_AdversaryModel
Formal statement
namespace QuantumLTF.Majority open QAlgorithms theorem assemble_exact_support_duals : ∀ C₀ : ℝ, 0 < C₀ → (∀ n k r : ℕ, 2 ≤ k → k ≤ n → 1 ≤ r → r ≤ k → ∃ X : Qubits n → Matrix (ExactSupports n r) (ExactSupports n r) ℝ, DualFeasible (fun A : ExactSupports n r => A.1) X ∧ DualCostAtMost X (C₀ * Real.log k)) → ∃ 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, arXiv:2609.40331v3, Sections 4.3–4.3.1, bounded-support adversary vectors and their auxiliary component, leading to Lemma 4.5.