How 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.
Boolean-output filtered γ₂ equals the general adversary value
Statement
For every finite nonconstant partial Boolean function, Here F is the same-output mask, J is all ones, and Δ is the family of input-mismatch masks. The equality is exact for Boolean outputs; no larger-alphabet factor is asserted.
Facts & Assumptions
Given: A finite nonconstant partial Boolean function and its output and mismatch masks.
Filtered γ₂ factorization norm for query mismatch masks: γ₂(J−F|Δ) is the minimum factorization cost for the all-pairs constraints with target J−F.
Finite-dimensional well-definedness of the filtered γ₂ program: this finite factorization program is feasible and attained when its target has zero diagonal.
General adversary matrix and spectral bound: Adv± uses real symmetric matrices supported on opposite-output pairs.
Dual vector formulation of the general adversary bound: Adv± equals the attained minimum vector-certificate cost with right side J−F.
Entrywise products of finite positive semidefinite matrices are positive semidefinite: entrywise products of finite PSD Gram matrices remain PSD.
Proof
For A=J−F, the defining factorization equations for γ₂(A|Δ) are exactly Σ_{i:x_i≠y_i}⟨u_{x,i}|v_{y,i}⟩=1 for opposite outputs and 0 for equal outputs. The target has zero diagonal, so [F2] gives a finite attained value.
The dual-vector theorem [F4] gives the minimum of precisely these equations and the same maximum row/column squared-norm cost. Its single-family form has cost max{C_0,C_1}. Assigning u_{x,i}=w_{x,i} and v_{y,i}=w_{y,i} for every input gives a factorization of identical cost, while the dual-vector proof constructs the single family by taking the row family on D_0 and the column family on D_1, then applying the Boolean output-label code. Therefore the two minima coincide and equal Adv±(f).
In the equivalent cross-output-only formulation, tensoring by the two-code label yields equal-output zeros while preserving cross-output constraints. The associated label Gram matrix is PSD, and [F5] confirms its entrywise product with each original Gram matrix is PSD; thus this equivalent realization remains a valid finite Gram factorization with unchanged vector norms. The Boolean output alphabet makes the label inner product exactly 1 on required cross-output mismatches and 0 on same-output mismatches, so there is no output-size loss factor.
Depends on
- Filtered γ₂ factorization norm for query mismatch masks
- Finite-dimensional well-definedness of the filtered γ₂ program
- General adversary matrix and spectral bound
- Entrywise products of finite positive semidefinite matrices are positive semidefinite
- Finite real semidefinite programs satisfy strong duality under strict feasibility
- Dual vector formulation of the general adversary bound
Used by
Dependency tree · two levels
27 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)