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.
Operator-norm error bounds a basis-outcome probability change
Statement
Let be a nonzero finite-dimensional complex inner-product space with a finite orthonormal basis . Let be unit, let be unitary, and let satisfy . If and are the computational-basis measurement probabilities after applying and to , respectively, then for every ,
Facts & Assumptions
Given: The space, orthonormal basis, unit vector, two unitary maps, and operator-norm bound in the Statement.
The measurement law for a finite continuous-time walk: for a unit vector , the probability of basis outcome is .
Bessel's inequality for a finite orthonormal list and Parseval's identity for an orthonormal basis: for one unit vector , .
The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv|| defines as the maximum of over unit on a nonzero finite-dimensional domain; The operator norm is 0 on the zero domain and otherwise equals the largest singular value, attained at a right-singular vector proves that this maximum exists and is attained.
Linear isometries, and orthogonal or unitary operators on finite-dimensional inner product spaces: a unitary is a linear isometry and preserves every vector norm.
Cauchy-Schwarz with its equality case, the triangle inequality for , the parallelogram law and polarisation: the Euclidean norm on satisfies the triangle inequality. Under the coordinates this gives for complex numbers.
Proof
Put . Since is unit, [F3] and the operator-norm hypothesis give .
Fix and put and . By [F2] applied to , . By [F4], and are unit; [F2] then gives and .
The triangle inequality [F5]–[F6] implies the reverse triangle inequality . Factoring the difference of squares and using step 2.1 gives . By [F1], the left side is . Since was arbitrary, the claimed bound holds for every basis outcome.
Depends on
- The measurement law for a finite continuous-time walk
- Bessel's inequality for a finite orthonormal list and Parseval's identity for an orthonormal basis
- The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||
- The operator norm is 0 on the zero domain and otherwise equals the largest singular value, attained at a right-singular vector
- Linear isometries, and orthogonal or unitary operators on finite-dimensional inner product spaces
- Real and imaginary parts, complex conjugation, and modulus
- Cauchy-Schwarz $\lvert\langle x,y\rangle\rvert \le \lVert x\rVert_2\lVert y\rVert_2$ with its equality case, the triangle inequality for $\lVert\cdot\rVert_2$, the parallelogram law and polarisation
Used by
Dependency tree · two levels
38 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, Chapter 17 §17.1 (standard reference, not scraped)
- Ronald de Wolf, Quantum Computing: Lecture Notes, Chapter 9 §9.1 (standard reference, not scraped)