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.
Correctness of the small-time-aware simulator
Statement
For every promised input of Small-time-aware qubitized simulator, a successful output satisfies the clean-input isometry error bound . It also satisfies the corresponding reference-system trace-distance bound after tracing the work registers.
Facts & Assumptions
Given: The exact normalized block encoding, a rational , and .
Small-time-aware qubitized simulator: the small branch returns identity when ; otherwise it invokes OP4.
Qubitized simulation correctness: on a successful OP4 output, the clean-input isometry error is at most , and the traced output has the same trace-distance bound.
Finite Hermitian matrix dynamics: is defined by the finite spectral functional calculus.
Unitary and differential identities for finite matrix dynamics: and is unitary.
Clean-input isometry error bounds output trace distance: clean-input isometry error bounds the reference-system trace distance after tracing work by .
Qubitization access model: the block-encoding normalization satisfies .
Proof
Given: As in Facts & Assumptions.
If , the algorithm invokes OP4, and [F2] gives the clean-input isometry bound.
Suppose . For a unit vector , the differential identity [F4] and the fundamental theorem of calculus give . Each integrand has norm at most , because preserves norm. The triangle inequality for Riemann sums and continuity yield , using [F7]. Taking the maximum over unit proves the clean-input operator bound for the identity circuit. The work registers are exactly zero, so the same isometry bound holds.
In either branch, the implementation on clean inputs and the target are isometries whose operator-norm difference is at most , by steps 1.1 and 1.2. Apply [F6] with to obtain the reference-system trace-distance conclusion after tracing work.
Depends on
- Small-time-aware qubitized simulator
- Qubitized simulation correctness
- Qubitization access model
- Finite Hermitian matrix dynamics
- Unitary and differential identities for finite matrix dynamics
- The operator norm is submultiplicative and satisfies ||T^*T|| = ||T||^2
- Clean-input isometry error bounds output trace distance
Used by
Dependency tree · two levels
41 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
- András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe, Quantum singular value transformation and beyond, Theorem 58 and Lemma 59 (standard reference, not scraped)
- Andrew M. Childs, Lecture Notes on Quantum Algorithms, Chapter 29 §29.4 (standard reference, not scraped)