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 correctly initialized witness histories
Statement
Fix an input-specific verifier circuit with only its witness unrestricted initially and all other work qubits in the checked zero-initialized set . For , use the history map and endpoint penalties of Feynman–Kitaev history Hamiltonian. Write , and let be the span of all full correct-propagation histories for this circuit, identified isometrically with their initial computation vectors. When the padding hypotheses of KKR restriction to correct two-qubit propagation hold, this is the space obtained by that restriction. On , the compressed input term is where is the checked zero-initialized workspace set, and the compressed output term is the transported reject projector . Thus the kernel of consists of histories initialized with zero workspace. If , its least positive eigenvalue is at least ; if , the input term is zero and the restriction is immediate. If bounds the norm of the remaining output term, choose Then the final projection-lemma error is below . For an amplified verifier with YES acceptance at least and NO acceptance at most , the compressed output energy is at most on YES and at least on NO.
Facts & Assumptions
Given: The input-specific verifier and initial-vector identification in the Statement, correctly propagated histories, the input/output penalties, and an amplified verifier with the stated completeness and soundness.
KKR restriction to correct two-qubit propagation identifies its restricted space with full verifier histories under its stated padding hypotheses; no padding is needed for the endpoint calculation here.
Projection lemma for a large penalty: a penalty with gap changes the compressed minimum by at most .
Input and output penalties on history states gives input history energy and output history energy equal to rejection probability.
Feynman–Kitaev history Hamiltonian defines the linear history map , where and , and the endpoint penalties used here.
Proof
By [F4], orthogonal clock sectors give , so is an isometry onto . The clock factors in and select only times and , respectively. Direct multiplication gives and , agreeing with the energy identities of [F3] and requiring no padding. Under the padding hypotheses, [F1] identifies this same image with the preceding KKR restriction space. The input compression has eigenvalues , where counts workspace bits equal to one, so its kernel is exactly the zero-workspace subspace. If , every positive eigenvalue is at least ; if , the input operator is zero on all of .
If , the weighted input penalty has nonzero gap . Apply [F2] with the compressed output term as and this input penalty as ; the chosen inequality makes the correction strictly less than . If , the input penalty is zero, its kernel is all of , and no projection error is incurred. On the restricted kernel, [F3] identifies the least output energy with minimum rejection probability over witness states. Completeness gives energy at most ; soundness gives rejection at least for every clean witness, so the restricted NO minimum is at least .
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
- 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)