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.
Input-mismatch masks and entrywise filtering
Definition
For a finite Boolean query problem (N,D,f), all matrices below are indexed by the same fixed ordering of D. For i∈[N], define the input-mismatch matrix For same-size matrices define the entrywise product . Define the same-output mask and the all-ones matrix . Thus is the opposite-output mask.
Facts & Assumptions
Given: A finite Boolean query problem (N,D,f) with its fixed input ordering.
Finite Boolean query problem and error model for adversary bounds: every row/column label is an element of the same finite D⊆{0,1}^N with output f(x).
Proof
For every i∈[N], set (Δ_i){xy}=1 when x_i≠y_i and 0 otherwise; then Δ_i is a real symmetric Boolean matrix indexed by D×D. Define (A∘B){xy}=A_{xy}B_{xy} for matrices with the same row and column labels.
Set F_{xy}=1[f(x)=f(y)] and J_{xy}=1 for all x,y∈D. If x=y, every Δ_i(x,x)=0; if x≠y, then x and y differ in at least one coordinate, so at least one Δ_i(x,y)=1. Hence J−F is supported exactly on pairs with opposite outputs, and every diagonal entry is excluded by every query mask.
Depends on
Used by
- Filtered γ₂ factorization norm for query mismatch masks Definition
- General adversary matrix and spectral bound Definition
- Nonnegative-weight adversary bound Definition
- Dual adversary certificate for OR_N Example
- Finite-dimensional well-definedness of the filtered γ₂ program Lemma
- Finite, attained general adversary value for nonconstant Boolean functions Lemma
- Input-distribution certificates upper-bound the nonnegative adversary value Lemma
- Nonconstant Boolean functions have adversary value at least one Lemma
- One oracle call changes adversary progress by at most filtered spectral norm Lemma
- The four-bit Ambainis function separates nonnegative and signed adversary bounds Proposition
- Dual vector formulation of the general adversary bound Theorem
- Nonnegative and signed adversary bounds compose from below Theorem
Dependency tree · two levels
5 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)