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.
Unary clock legality and 5-locality
Statement
For the unary clock , the penalty has kernel exactly the legal-clock subspace and every illegal clock basis word has penalty at least . With the local windows specified in Feynman–Kitaev history Hamiltonian, every propagation summand is supported on at most two computation qubits and three clock qubits; input, output and clock summands are at most two-local. For any , a weight makes the projection-lemma error strictly less than , where bounds the sum of all other weighted terms. Such a weight can be chosen polynomially bounded when both and are polynomially bounded; the formula does not assert polynomial size for smaller gaps.
Facts & Assumptions
Given: , the unary-clock history terms, a polynomial bound , and an inverse-polynomial positive gap when a polynomial penalty weight is required.
Feynman–Kitaev history Hamiltonian: propagation windows have at most three clock bits and each verifier gate touches at most two work qubits.
Projection lemma for a large penalty: a penalty changes the least eigenvalue of a Hermitian operator of norm by at most when .
Geometric soundness bound for a history Hamiltonian: the legal-clock Hamiltonian has an inverse-polynomial soundness gap before illegal clocks are penalized.
Proof
A binary word has no adjacent occurrence of exactly when its bits are nonincreasing from left to right: if a zero occurred before a later one, the first subsequent transition from zero to one would be adjacent; conversely a word has no such transition. Thus the common zero space of all adjacent projectors is spanned by the legal unary words. On a basis word, is diagonal with eigenvalue the number of forbidden adjacent pairs, so every illegal word has eigenvalue at least one.
The stated propagation windows contain three clock bits and at most two work bits; each input/output term couples one clock and one work bit, and each clock penalty couples two clock bits, proving the support bounds from [F1]. Let be the legal-clock subspace. Then vanishes on and is at least on . Applying [F2] with , gives additive error at most . For polynomial resources choose the integer . It strictly exceeds the threshold and is at most , hence is polynomially bounded when and are. The resulting error is strictly below , preserving a positive gap at that scale.
Depends on
Used by
Dependency tree · two levels
11 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
- Dorit Aharonov and Tomer Naveh, Quantum NP: A Survey (standard reference, not scraped)
- Andrew M. Childs, Lecture Notes on Quantum Algorithms (standard reference, not scraped)