LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedjudge pass (gpt-6-luna)

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 correct one-qubit propagation

Statement

Fix $L \geq 2$ and let $T_{2}$ be the number of controlled- $Z$ gates. Pad the verifier to $T = (T_{2} + 1) L - 1$ steps, with controlled- $Z$ gates exactly at times $t = l L$ for $1 \leq l \leq T_{2}$ and exactly $L$ clock configurations in each block $[l L, (l + 1) L - 1]$ . Every other $U_{t}$ is one-qubit. For each one-qubit gate time $t$ , define the KKR local propagation term by $H_{p r o p, t} = \frac{1}{2} (I \otimes ∣ 10 ⟩ ⟨ 10 ∣_{C_{t} C_{t + 1}} + I \otimes ∣ 10 ⟩ ⟨ 10 ∣_{C_{t - 1} C_{t}} - U_{t} \otimes ∣ 1 ⟩ ⟨ 0 ∣_{C_{t}} - U_{t}^{*} \otimes ∣ 0 ⟩ ⟨ 1 ∣_{C_{t}})$ for $1 < t < T$ . When $T \geq 2$ , use the endpoint terms $H_{p r o p, 1} = \frac{1}{2} (I \otimes ∣ 10 ⟩ ⟨ 10 ∣_{C_{1} C_{2}} + I \otimes ∣ 0 ⟩ ⟨ 0 ∣_{C_{1}} - U_{1} \otimes ∣ 1 ⟩ ⟨ 0 ∣_{C_{1}} - U_{1}^{*} \otimes ∣ 0 ⟩ ⟨ 1 ∣_{C_{1}}),$ $H_{p r o p, T} = \frac{1}{2} (I \otimes ∣ 1 ⟩ ⟨ 1 ∣_{C_{T}} + I \otimes ∣ 10 ⟩ ⟨ 10 ∣_{C_{T - 1} C_{T}} - U_{T} \otimes ∣ 1 ⟩ ⟨ 0 ∣_{C_{T}} - U_{T}^{*} \otimes ∣ 0 ⟩ ⟨ 1 ∣_{C_{T}}) .$ For $T = 1$ (necessarily $T_{2} = 0, L = 2$ ), use only $H_{p r o p, 1} = \frac{1}{2} (I \otimes I_{C_{1}} - U_{1} \otimes ∣ 1 ⟩ ⟨ 0 ∣_{C_{1}} - U_{1}^{*} \otimes ∣ 0 ⟩ ⟨ 1 ∣_{C_{1}})$ . Each summand is at most 2-local. Put $H_{p r o p 1} = \sum_{t : U_{t} is one-qubit} H_{p r o p, t}$ . On the legal clock space it is a direct sum of half-weight path Laplacians, and its kernel $S_{p r o p 1}$ is spanned by block histories $∣ η_{l, i} ⟩ = L^{- 1 / 2} \sum_{t = l L}^{(l + 1) L - 1} U_{t} \dots U_{1} ∣ i ⟩ \otimes ∣ c_{t} ⟩,$ where $i$ ranges over a computational basis of the work register and $l$ over the blocks. The nonzero gap is at least $g_{1} = 1 - \cos (π / L) \geq 2 / L^{2}$ . If the remaining weighted terms have norm at most $K_{1}$ , choose $J_{1} g_{1} > 2 K_{1} + K_{1}^{2} / ϵ_{1}$ ; the projection lemma then incurs additive error below $ϵ_{1}$ when restricting to $S_{p r o p 1}$ .

Facts & Assumptions

Given: The legal unary clock, a padded circuit with one-qubit gates except at the designated block boundaries, and $K_{1}$ bounding the norm of all remaining weighted terms.

[F1]

KKR restriction to legal unary clocks: the clock penalty has already restricted the analysis to legal unary clock words.

[F2]

Propagation kernel and path-Laplacian gap: a half-weight path on $L$ consecutive configurations has gap $1 - \cos (π / L) \geq 2 / L^{2}$ .

[F3]

Projection lemma for a large penalty: a penalty with spectral gap $J$ changes the compressed minimum by at most $K_{1}^{2} / (J - 2 K_{1})$ .

Proof

1.1F1F2givenalgebra

Within one block, conjugate each clock-time sector by its accumulated one-qubit circuit prefix. Every propagation edge becomes $\frac{1}{2} (∣ t ⟩ - ∣ t - 1 ⟩) (⟨ t ∣ - ⟨ t - 1 ∣)$ tensor identity. No edge in $H_{p r o p 1}$ connects distinct blocks because the separating edge is the designated two-qubit gate. Therefore the operator is a direct sum, over blocks and work basis labels, of half-weight path Laplacians on $L$ vertices. Their common kernel is the constant vector on each block, which after undoing the conjugation gives the displayed $∣ η_{l, i} ⟩$ basis; [F2] gives the minimum nonzero gap $g_{1}$ .

2.1F3step 1.1algebra∎

The weighted penalty $J_{1} H_{p r o p 1}$ has zero space $S_{p r o p 1}$ and least positive eigenvalue at least $J_{1} g_{1}$ . Apply [F3] with the remaining Hermitian sum as $H_{1}$ and this penalty as $H_{2}$ . Since $J_{1} g_{1} > 2 K_{1} + K_{1}^{2} / ϵ_{1}$ , the error is strictly less than $ϵ_{1}$ . For polynomial $K_{1}$ , $L$ and $1 / ϵ_{1}$ , a polynomial integer $J_{1}$ satisfies this inequality.

Depends on

Used by

KKR restriction to correct two-qubit propagation Lemma
2-Local Hamiltonian is QMA-complete Theorem

Dependency tree · two levels

6 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)
Ronald de Wolf, Quantum Computing: Lecture Notes (standard reference, not scraped)