Alphabeta Math
LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generated
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 A. For T≥1, use the history map and endpoint penalties of Feynman–Kitaev history Hamiltonian. Write V=UT⋯U1, and let Sprop 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 Sprop, the compressed input term is Hin∣Sprop=1T+1∑a∈A∣1⟩⟨1∣a, where A is the checked zero-initialized workspace set, and the compressed output term is the transported reject projector V∗(∣0⟩⟨0∣out⊗I)V. Thus the kernel of Hin∣Sprop consists of histories initialized with zero workspace. If A≠∅, its least positive eigenvalue is at least 1/(T+1); if A=∅, the input term is zero and the restriction is immediate. If Kin bounds the norm of the remaining output term, choose Jin/(T+1)>2Kin+Kin2/ϵin. Then the final projection-lemma error is below ϵin. For an amplified verifier with YES acceptance at least 3/4 and NO acceptance at most 1/4, the compressed output energy is at most 1/4 on YES and at least 3/4 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.

[F1]

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.

[F2]

Projection lemma for a large penalty: a penalty with gap J changes the compressed minimum by at most Kin2/(J−2Kin).

[F3]

Input and output penalties on history states gives input history energy E[Nbad]/(T+1) and output history energy equal to rejection probability.

[F4]

Feynman–Kitaev history Hamiltonian defines the linear history map Rϕ=(T+1)−1/2∑t=0TVtϕ⊗∣ct⟩, where V0=I and Vt=Ut⋯U1, and the endpoint penalties used here.

Proof

1.1F1F3F4algebra

By [F4], orthogonal clock sectors give R∗R=(T+1)−1∑tVt∗Vt=I, so R is an isometry onto Sprop. The clock factors in Hin and Hout select only times 0 and T, respectively. Direct multiplication gives R∗HinR=(T+1)−1∑a∈A∣1⟩⟨1∣a and R∗HoutR=V∗(∣0⟩⟨0∣out⊗I)V, 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 r/(T+1), where r counts workspace bits equal to one, so its kernel is exactly the zero-workspace subspace. If A≠∅, every positive eigenvalue is at least 1/(T+1); if A=∅, the input operator is zero on all of Sprop.

2.1F2F3step 1.1algebra∎

If A≠∅, the weighted input penalty has nonzero gap Jin/(T+1). Apply [F2] with the compressed output term as H1 and this input penalty as H2; the chosen inequality makes the correction strictly less than ϵin. If A=∅, the input penalty is zero, its kernel is all of Sprop, and no projection error is incurred. On the restricted kernel, [F3] identifies the least output energy with minimum rejection probability over witness states. Completeness 3/4 gives energy at most 1/4; soundness 1/4 gives rejection at least 3/4 for every clean witness, so the restricted NO minimum is at least 3/4.

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