Lift and assembly from odd exact supports to bounded supports
OpenQuantumLTF.Majority.odd_exact_to_bounded_dual_log_costadversary-methodquantum-query-complexitysection-4
Suppose all odd exact support sizes admit dual adversary solutions of cost at most . Then a universal constant exists such that the full promise admits a feasible solution of cost at most
The construction applies the one-coordinate lift to even cardinalities, which changes resources only by a constant factor, and assembles the cardinality blocks using the auxiliary component of the Section 4.3 adversary vectors. The cases of support size one and two are absorbed into the universal constant.
Preamble
import Mathlib import Definitions.Def_QuantumLTF_Majority_AdversaryModel
Formal statement
namespace QuantumLTF.Majority open QAlgorithms theorem odd_exact_to_bounded_dual_log_cost : ∀ C₀ : ℝ, 0 < C₀ → (∀ n r : ℕ, 3 ≤ r → r ≤ n → Odd r → ∃ X : Qubits n → Matrix (ExactSupports n r) (ExactSupports n r) ℝ, DualFeasible (fun A : ExactSupports n r => A.1) X ∧ DualCostAtMost X (C₀ * Real.log r)) → ∃ 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, Fast Quantum Algorithms for Learning Linear Threshold Functions, arXiv:2609.40331v3, Eq. (127) and Sections 4.3–4.3.1: lift for even sizes and bounded-support adversary assembly leading to Lemma 4.5.