Theorem 4.1 (companion theorem) — quantum Booleanization
OpenExactLearningSeparation678.Randomized.Supplement.theorem_4_1machine-learningp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationquery-complexity
There are absolute constants such that for every concept class ,
where is the bounded-error quantum query complexity of exactly learning and is the largest bounded-error quantum query complexity of deciding membership of the unknown concept in a subset .
Quantumly, identifying a concept is therefore no harder, up to a constant factor, than the hardest single yes/no question about it.
Formalization Note The constants precede the coordinate set and the class. uses the same quantum query model as , with a Boolean output and success probability at least for every .
Differences from the source:
- encoding: coordinates [N] of C ⊆ {0,1}^N → an arbitrary finite type ι : Type with decidable equality, concepts ι → Bool; reason: a relabeling of [N]; every N, including N = 0, is an instance
- encoding: bounded-error quantum and randomized query complexities Q(C), R(C) → the published quantumExactComplexity (QueryAlg, XOR oracle, any finite workspace) and classicalExactComplexity (randomized decision trees, worst-case query bound), success ≥ 2/3 on every target; reason: the mission’s published models of the source’s Q and R
- encoding: Q(C) = Θ(Q_bool(C)) for every C → a, b > 0 quantified before ι and C with a·Q_bool ≤ Q ≤ b·Q_bool; reason: the source’s Θ is uniform over all classes
Preamble
import Definitions.Def_ExactLearningSeparation678_Randomized_Supplement_Models open Classical set_option autoImplicit false
Formal statement
namespace ExactLearningSeparation678.Randomized.Supplement
open QAlgorithms.Learning
/-- Theorem 4.1 (Quantum Booleanization), p.29: `Q(C) = Θ(Q_bool(C))` uniformly: absolute
`a, b > 0`, fixed before `N` and `C`, with `a · Q_bool(C) ≤ Q(C) ≤ b · Q_bool(C)`. -/
theorem theorem_4_1 : ∃ a b : ℝ, 0 < a ∧ 0 < b ∧
∀ (ι : Type) [Fintype ι] [DecidableEq ι] (C : Finset (ι → Bool)),
a * (Qbool C : ℝ) ≤ (quantumExactComplexity C : ℝ) ∧
(quantumExactComplexity C : ℝ) ≤ b * (Qbool C : ℝ) := by sorry
end ExactLearningSeparation678.Randomized.Supplement
Source
Srinivasan Arunachalam, Amin Shiraz Gilani, Nikhil S. Mande, STOC 2027 submission #678 (October 2026), Theorem 4.1, p.29; Booleanization, p.28; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/678.pdf