Adversary-to-algorithm upper bound for bounded Majority supports
OpenQuantumLTF.Majority.bounded_support_adversary_upper_boundadversary-methodquantum-algorithmsquantum-query-complexitysection-4
Assume that for every , the bounded-support Majority learning relation has a feasible dual adversary solution of cost at most , with one universal constant . Then there is a universal constant and a bounded-error quantum learner which identifies every nonempty hidden support with , succeeds with probability at least , and makes at most
queries to the coherent Majority oracle.
This is the bounded-support specialization of the general dual-adversary/state-conversion upper bound. Arbitrary finite-dimensional inter-query unitaries may be decomposed exactly into one- and two-qubit unitaries, so restricting the circuit to the gate set used by the mission does not affect query complexity.
Preamble
import Mathlib import Definitions.Def_QAlgorithms_Defs_Circuit import Definitions.Def_QuantumLTF_Membership_gates12 import Definitions.Def_QuantumLTF_Majority_oracle import Definitions.Def_QuantumLTF_Sections45_Model import Definitions.Def_QuantumLTF_Majority_AdversaryModel
Formal statement
namespace QuantumLTF.Majority open QAlgorithms QuantumLTF.Membership theorem bounded_support_adversary_upper_bound : ∀ 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)) → ∃ C : ℝ, 0 < C ∧ ∀ n k : ℕ, 2 ≤ k → k ≤ n → ∃ (m : ℕ) (c : OracleCircuit gates12 (fun _ : Fin 1 => n + 1) m) (out : Fin n ↪ Fin m), (c.queryCount 0 : ℝ) ≤ C * Real.log k ∧ LearnsUpTo (k:=k) c out (2/3) := by sorry end QuantumLTF.Majority
Source
Krivcenko, Nguyen, de Wolf, Fast Quantum Algorithms for Learning Linear Threshold Functions, arXiv:2609.40331v3, Sections 4.2–4.3, especially the feasible adversary solution and the transducer construction around Eqs. (129)–(132), leading to Theorem 4.5; general adversary/state-conversion upper-bound theorem cited there.