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 matrix and spectral bound
Definition
For a nonconstant finite Boolean query problem define Negative entries are allowed. The denominator is positive and the maximum is finite and attained by Finite, attained general adversary value for nonconstant Boolean functions. For constant f set . The nonnegative adversary value is the same maximum with the additional constraint for all x,y; it is also set to zero for constant f.
Facts & Assumptions
Given: A finite Boolean query problem with mismatch masks and same-output matrix F.
Input-mismatch masks and entrywise filtering: F_{xy}=1 on equal-output pairs and Δ_i(x,y)=1 on coordinate mismatches.
The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||: ||A|| is the induced Euclidean operator norm.
Finite, attained general adversary value for nonconstant Boolean functions: for nonconstant f every nonzero admissible Γ has positive denominator and the finite optimum is attained.
Proof
Call Γ admissible when it is a nonzero real symmetric D×D matrix with Γ∘F=0. Define d(Γ)=max_{i∈[N]}||Γ∘Δ_i|| and set Adv±(f)=sup_Γ ||Γ||/d(Γ) for nonconstant f; for constant f set Adv±(f)=0.
By [F3], d(Γ)>0 for every nonzero admissible Γ and the supremum is a finite attained maximum when f is nonconstant. The entries of Γ need not be nonnegative; negative entries are permitted by this feasible set. Restricting to Γ≥0 entrywise gives the separate nonnegative adversary value, which is a smaller feasible set.
Depends on
Used by
- A nonnegative-only adversary estimate need not capture the general bound Counterexample
- Nonnegative-weight adversary bound Definition
- Dual adversary certificate for OR_N Example
- Adversary progress at initial and bounded-error final states Lemma
- Nonconstant Boolean functions have adversary value at least one Lemma
- One oracle call changes adversary progress by at most filtered spectral norm Lemma
- Signed weights extend the nonnegative adversary certificate Proposition
- The four-bit Ambainis function separates nonnegative and signed adversary bounds Proposition
- Boolean-output filtered γ₂ equals the general adversary value Theorem
- Dual vector formulation of the general adversary bound Theorem
- General adversary bound characterizes Boolean quantum query complexity Theorem
- General adversary spectral lower bound for quantum queries Theorem
- Nonnegative and signed adversary bounds compose from below Theorem
Dependency tree · two levels
8 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)
- Ronald de Wolf, Quantum Computing: Lecture Notes, arXiv:1907.09415v6 (standard reference, not scraped)