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.
Finite-dimensional well-definedness of the filtered γ₂ program
Statement
For the Boolean mismatch masks, if and only if for every x. Whenever finite, the infimum is attained by finite vector families. A minimizing family can be taken in dimension at most for each coordinate i.
Facts & Assumptions
Given: A finite matrix A indexed by D×D and the masks Δ_i on the same finite Boolean input set.
Filtered γ₂ factorization norm for query mismatch masks: γ₂(A|Δ) is the infimum of the maximum row/column sum of squared vector norms over finite factorizations.
Real and complex inner product spaces, with the inner product linear in the first argument: the inner product is positive definite and induces the vector norm.
Dirac Notation Conversion: the Dirac pairing represents the cross-Gram entries used in the factorization.
Every finite-dimensional real or complex inner product space has an orthonormal basis: every finite-dimensional real or complex inner-product space has an orthonormal basis.
Heine-Borel in : with the Euclidean metric a subset of is compact if and only if it is closed and bounded, and the proof by bisection uses no choice principle; the same holds on the real line: closed bounded subsets of positive finite-dimensional real Euclidean spaces are compact.
A continuous real-valued function on a nonempty compact metric space is bounded and attains a greatest and a least value: a continuous real function on a nonempty compact metric space attains its minimum and maximum.
Finite Boolean query problem and error model for adversary bounds: and the finite query domain is nonempty.
Proof
If A_{xx}≠0, the factorization equation at (x,x) has right side zero because every Δ_i(x,x)=0, so A is infeasible. If A has zero diagonal, assign each off-diagonal entry A_{xy} to the least i with x_i≠y_i, forming matrices A^{(i)} supported on Δ_i and satisfying A=Σ_i A^{(i)}. For d=|D|, put u_{x,i}=(\overline{A^{(i)}{x1}},…,\overline{A^{(i)}{xd}}) and v_{y,i}=e_y in C^d; then ⟨u_{x,i}|v_{y,i}⟩D=A^{(i)}{xy}. This is a finite feasible factorization.
For any feasible factorization in finite dimension, take, for each i, the span of the d vectors and d vectors . It has dimension at most ; by [F4] choose an orthonormal basis and map its vectors to their coordinates, padding with zero coordinates in . This preserves every inner product and norm. Thus every feasible candidate has a representation in one fixed finite product of coordinate spaces .
By step 1.1 choose one feasible family and let be its finite cost. Use step 2.1 to represent feasible families in a fixed finite product of copies of , viewed as a positive-dimensional real Euclidean space; by [F7]. The set of coordinate families satisfying the factorization equations and having cost at most is nonempty, closed, and bounded: the equations and cost are continuous, and each vector norm is at most . By [F5] this set is compact. Its continuous cost function attains a minimum by [F6]. Any feasible family with lower cost would also belong to this set, so the minimum equals the global infimum and is attained. Thus every feasible has an attained finite value, while nonzero diagonal is exactly the infeasible case.
Depends on
- Filtered γ₂ factorization norm for query mismatch masks
- Input-mismatch masks and entrywise filtering
- Finite Boolean query problem and error model for adversary bounds
- Real and complex inner product spaces, with the inner product linear in the first argument
- Dirac Notation Conversion
- Every finite-dimensional real or complex inner product space has an orthonormal basis
- Heine-Borel in $\mathbb{R}^n$: with the Euclidean metric a subset of $\mathbb{R}^n$ is compact if and only if it is closed and bounded, and the proof by bisection uses no choice principle; the same holds on the real line
- A continuous real-valued function on a nonempty compact metric space is bounded and attains a greatest and a least value
Used by
Dependency tree · two levels
57 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)