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.
KKR restriction to legal unary clocks
Statement
For clock qubits let and Its kernel is and every illegal computational-basis clock word has eigenvalue at least one. Let be the sum of the remaining weighted KKR terms, with , and let be the soundness gap allocated before this restriction. Any integer makes the projection-lemma error strictly less than . The clock penalty is 2-local even though it has summands.
Facts & Assumptions
Given: unary clock qubits, the remaining KKR Hamiltonian , a polynomial norm bound , and inverse-polynomial .
Projection lemma for a large penalty: a penalty with gap outside a zero space changes the compressed least eigenvalue by at most when .
Feynman–Kitaev history Hamiltonian: legal unary words are and each two-qubit clock projector is a 2-local term.
Proof
The sum is diagonal in the computational clock basis. It has eigenvalue equal to the number of pairs with bit and bit . This number is zero exactly when no zero precedes a one, which is equivalent to a word ; every other word has at least one such pair and hence eigenvalue at least one. Thus its zero space and gap are as stated.
Apply [F1] with , and . The spectral penalty on is at least , while it vanishes on . The chosen strict bound gives , and so the correction . For polynomial resource bounds, choose specifically , using a supplied rational norm bound . This is strictly above the threshold and at most . If and are polynomially bounded and their encodings have polynomial length, this choice has polynomial magnitude and bit length, and the term list has polynomial size; no size bound is claimed for arbitrary larger admissible integers.
Depends on
Used by
Dependency tree · two levels
7 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
- Julia Kempe, Alexei Kitaev, and Oded Regev, The Complexity of the Local Hamiltonian Problem (standard reference, not scraped)
- Dorit Aharonov and Tomer Naveh, Quantum NP: A Survey (standard reference, not scraped)