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.
First-order query and gate cost
Statement
For the term-list input in Term-list Hamiltonian access, let be a finite time code in its expression language, let be rational, and let be a certified rational satisfying . Supply a certified rational upper bound and put and . When , suppose each term call at the exact signed code is supported and declared, directly or through separately declared inverse or time-reversed access, with at most named queries and gate occurrences. Let and be the separately declared query and gate costs of uniform circuit composition and generation. For , the algorithm First-order term-list simulator uses at most queries and gates. Its exact term product has error at most . If, when , implemented calls are unitary and their total operator-norm error over all calls is at most , the returned unitary is within of . When , the algorithm returns the identity with no term calls. Coefficient, description-bit, ancilla, and classical-generation resources remain separate coordinates.
Facts & Assumptions
Given: A finite term-list input, finite time code in its expression language, rational , certified rational , certified rational upper bound , the resulting integer , and the declared costs for calls at when .
First-order term-list simulator returns the identity with no term calls when ; otherwise it makes exactly repetitions of term calls, where and .
First-order commutator error bounds the exact product-formula error by .
Term-list Hamiltonian access records per-call query and gate costs, implementation errors, and composition/generation overhead as separate charges.
The operator norm is submultiplicative and satisfies ||T^*T|| = ||T||^2 gives submultiplicativity.
The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv|| defines the operator norm as the maximum over unit vectors.
Proof
If , the algorithm returns the identity and the exact evolution is also the identity. Otherwise . Since bounds the commutator sum, [F2] gives exact product error at most .
Replace the exact term calls one at a time by their supplied unitary implementations. For unitaries, the definition [F5] and submultiplicativity [F4] show that left and right multiplication preserve operator norm. Thus a telescoping expansion of the two products bounds the operator-norm change by the sum of the individual call errors. The input certificate in [F1] makes this total at most . The triangle inequality with step 1.1 gives total error at most .
For , each of the term circuits occurs once in each of repetitions, so their query and gate totals are and . For there are no term calls, and hence zero term-call query and gate costs. Adding the separately declared composition/generation overhead gives the stated bounds in either branch; the other resource coordinates are charged separately by [F3].
Depends on
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
19 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 (standard reference, not scraped)
- Ronald de Wolf, Quantum Computing: Lecture Notes (standard reference, not scraped)