Extend odd exact-support dual solutions to all support sizes
OpenQuantumLTF.Majority.odd_exact_family_to_all_sizesadversary-methodquantum-query-complexitysection-4
Assume logarithmic-cost exact-support adversary solutions are available for every odd cardinality at least three. Then, after increasing the universal constant, every exact cardinality admits a feasible solution of cost at most .
For even , apply the paper’s one-coordinate lift to the odd size and restrict back to the original coordinates. The cases have constant cost, which is absorbed because and is bounded below by .
Preamble
import Mathlib import Definitions.Def_QuantumLTF_Majority_AdversaryModel
Formal statement
namespace QuantumLTF.Majority open QAlgorithms theorem odd_exact_family_to_all_sizes : ∀ 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 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) := by sorry end QuantumLTF.Majority
Source
Krivcenko, Nguyen, de Wolf, arXiv:2609.40331v3, Eq. (127) and Sections 4.3 and 4.5.3: one-coordinate lift for even support sizes and constant-size base cases.