Theorem 4.5 — learning a hidden Majority support with quantum queries
OpenQuantumLTF.Majority.theorem_4_5linear-threshold-functionsmajoritymembership-queriesquantum-learningquantum-query-complexity
Let . There is a bounded-error quantum algorithm which, for every unknown nonempty set with , identifies exactly using
queries to the coherent Boolean membership oracle for . The same circuit is chosen before the hidden support , and succeeds with probability at least . In particular, the result includes the promise ; the case has constant query complexity.
This is the exponential improvement over the previous upper bound.
Formalization Note The measured output is required to be the exact characteristic vector of . The big- constant is universal and quantified before and .
Preamble
import Mathlib import Definitions.Def_QAlgorithms_Defs_Circuit import Definitions.Def_QuantumLTF_Membership_gates12 import Definitions.Def_QuantumLTF_Majority_oracle
Formal statement
namespace QuantumLTF.Majority
open QAlgorithms QuantumLTF.Membership
/-- **Theorem 4.5 (Upper bound for learning Majority).** For every `2 ≤ k ≤ n`, a bounded-error quantum algorithm identifies every hidden nonempty support `A ⊆ [n]` of size at most `k` using `O(log k)` coherent Majority queries. The circuit is fixed before `A`, and its measured output is the exact characteristic vector of `A`. -/
theorem theorem_4_5 :
∃ 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 ∧
∀ A : Finset (Fin n), A.Nonempty → A.card ≤ k →
probEvent (act (c.unitary fun _ => majorityOracle A) (zeroKet m))
(fun z => ∀ i : Fin n, z (out i) = decide (i ∈ A)) ≥ 2 / 3 := by sorry
end QuantumLTF.MajoritySource
Krivcenko, Nguyen, de Wolf, Fast Quantum Algorithms for Learning Linear Threshold Functions, arXiv:2609.40331v3, Theorem 4.5, p. 49 (PDF p. 50); upper-bound proof in Sections 4.2–4.3