Alphabeta MathHow statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
General adversary bound characterizes Boolean quantum query complexity
Statement
For every finite partial Boolean function f:D→{0,1}, bounded-error quantum query complexity at error at most 1/3 satisfies For nonconstant f, the lower coefficient is and the reflection evaluator gives an upper bound below . For constant f both quantities are zero.
Facts & Assumptions
Given: A finite partial Boolean function with the standard XOR query model.
General adversary spectral lower bound for quantum queries: Q_ε(f)≥(1/2−√(ε(1−ε)))Adv±(f).
Boolean-output filtered γ₂ equals the general adversary value: for nonconstant finite partial Boolean functions, the Boolean filtered factorization value is exactly Adv±.
Dual reflection evaluator query complexity: a supplied balanced dual certificate of cost A≥1 gives an evaluator using fewer than 2048A queries.
Quantum query complexity: the general query-cost coordinate is the worst-case number of designated oracle calls, excluding nonoracle gates.
Dual vector formulation of the general adversary bound: for nonconstant f the certificate minimum equals Adv± and is attained.
Nonconstant Boolean functions have adversary value at least one: nonconstant f has Adv±≥1.
Finite Boolean query problem and error model for adversary bounds: is the least worst-case standard XOR query count for success probability at least on every promised input.
General adversary matrix and spectral bound: for constant f, Adv±(f) is defined to be zero.
Dual reflection evaluator has bounded-error correctness: for every supplied finite dual certificate with class costs at most A≥1, the reflection evaluator outputs f(x) with probability at least 2/3 on every promised input x.
Proof
If f is nonconstant, apply [F1] with ε=1/3 to obtain Q_{1/3}(f)≥(1/2−√2/3)Adv±(f), whose coefficient is positive.
Still assuming f is nonconstant, [F2] identifies the Boolean filtered factorization value with Adv±(f). By [F5] the dual certificate optimum is attained with cost A=Adv±(f); reciprocal rescaling balances C_0,C_1 without increasing their maximum. By [F6], A≥1. For this certificate and bound A, [F9] gives success probability at least 2/3 on every promised input, while [F3] bounds the same evaluator's query count by fewer than 2048A. It therefore qualifies in the minimization [F7], giving Q_{1/3}(f)<2048Adv±(f).
If f is constant, the algorithm that outputs its fixed value without queries computes it exactly, so Q_{1/3}(f)=0 by [F7]. By [F8], Adv±(f)=0 as well. Combining this case with steps 1.1–1.2 proves the claimed uniform constant-factor bounds at error at most 1/3. Nonoracle gates are excluded from query cost by [F4].
Depends on
- General adversary spectral lower bound for quantum queries
- Boolean-output filtered γ₂ equals the general adversary value
- Dual reflection evaluator query complexity
- Dual reflection evaluator has bounded-error correctness
- Finite Boolean query problem and error model for adversary bounds
- Quantum query complexity
- Dual vector formulation of the general adversary bound
- Nonconstant Boolean functions have adversary value at least one
- General adversary matrix and spectral bound
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
45 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- Andrew M. Childs, Lecture Notes on Quantum Algorithms (17 April 2025) (standard reference, not scraped)
- Troy Lee, Rajat Mittal, Ben Reichardt, Robert Špalek, and Mario Szegedy, Quantum Query Complexity of State Conversion, arXiv:1011.3020 (standard reference, not scraped)
- Ben W. Reichardt, Span programs and quantum query complexity: The general adversary bound is nearly tight for every Boolean function, 2009 (standard reference, not scraped)