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.

Geometric soundness bound for a history Hamiltonian

Statement

Fix a NO input $x$ and an amplified, input-specific verifier circuit $V_{x}$ with soundness $s \leq 1 / 8$ . Its only unrestricted initial register is the witness: every other work qubit belongs to the zero-initialized set $A$ checked by $H_{i n}$ . In particular, any classical-input scratch registers start at zero and the circuit loads the fixed string $x$ before verification; the output predicate is specialized to $x$ . Let $N = T + 1$ . In the legal-clock history space let $S = \ker (H_{i n} + H_{o u t})$ and $T_{0} = \ker (H_{p r o p})$ . Then for every unit history vector $v \in T_{0}$ , $∥ P_{S} v ∥^{2} \leq 1 - \frac{1}{2 N} .$ Consequently the least eigenvalue of $H_{i n} + H_{o u t} + H_{p r o p}$ on legal clocks is at least $1 / (2 N^{3})$ . The proof allows arbitrary initial ancilla states in $T_{0}$ ; the QMA soundness premise is applied only to the clean-ancilla component.

Facts & Assumptions

Given: The input-specific NO verifier with soundness $s \leq 1 / 8$ , all nonwitness initial wires checked by $H_{i n}$ , its legal-clock history Hamiltonian, and $N = T + 1$ .

[F1]

Propagation kernel and path-Laplacian gap: $T_{0}$ is the image of the linear history map, which preserves norms; in particular its unit vectors are exactly histories of unit initial vectors. The propagation gap is at least $2 / N^{2}$ .

[F2]

Input and output penalties on history states: the squared norm removed by projecting a history onto $S$ is $(p_{b a d} + p_{r e j}) / N$ .

[F3]

QMA promise class with a verifier effect on witnesses: for the fixed NO input $x$ and any witness, acceptance is at most $s$ . By the input-specific initialization hypothesis, this applies to every normalized vector in the zero- $A$ subspace.

[F4]

Parallel QMA amplification remains sound for entangled witnesses: the verifier can be amplified to the stated inverse-polynomially small soundness while preserving polynomial size.

[F5]

Feynman–Kitaev history Hamiltonian: $H_{i n}$ is a sum of ancilla-one projectors restricted to clock time zero, and $H_{o u t}$ is $N$ times the reject projector restricted to clock time $T$ .

Proof

1.1F2F3F4algebra

The amplification supplied by [F4] lets us fix a verifier with NO soundness $s \leq 1 / 8$ . Write a normalized initial computation vector as $ϕ = ϕ_{c} + ϕ_{d}$ , where $ϕ_{c}$ has clean verifier ancillas and $ϕ_{d}$ is orthogonal to that subspace; set $α = ∥ ϕ_{c} ∥$ and $β = ∥ ϕ_{d} ∥$ , so $α^{2} + β^{2} = 1$ and $p_{b a d} = β^{2}$ . Let $K$ be the verifier's accept Kraus map, which is a contraction. By [F3], $∥ K ϕ_{c} ∥ \leq \sqrt{s} α$ ; hence the triangle inequality gives $p_{a c c} = ∥ K ϕ ∥^{2} \leq (\sqrt{s} α + β)^{2}$ . Therefore $p_{b a d} + p_{r e j} = β^{2} + 1 - p_{a c c} \geq 1 - s α^{2} - 2 \sqrt{s} α β .$ The symmetric matrix $(\begin{array}{cc} s & \sqrt{s} \\ \sqrt{s} & 0 \end{array})$ has largest eigenvalue $s / 2 + \sqrt{s + s^{2} / 4}$ ; its Rayleigh quotient at $(α, β)$ bounds the subtracted term. This eigenvalue is increasing for $s \geq 0$ , and at $s = 1 / 8$ it is $(1 + \sqrt{33}) / 16 < 1 / 2$ because $\sqrt{33} < 7$ . Thus $p_{b a d} + p_{r e j} \geq 1 / 2$ .

2.1F1F2F5step 1.1algebra∎

By [F2], every unit $v \in T_{0}$ has $∥ P_{S} v ∥^{2} = 1 - (p_{b a d} + p_{r e j}) / N \leq 1 - 1 / (2 N)$ . Put $c = ∥ P_{S} P_{T_{0}} ∥$ ; then $c^{2} \leq 1 - 1 / (2 N)$ and $1 - c \geq 1 - \sqrt{1 - 1 / (2 N)} \geq 1 / (4 N) .$ For any two orthogonal projections $P, Q$ , the map $v \mapsto (P v, Q v)$ has squared norm operator $P + Q$ . On $ran (P) \oplus ran (Q)$ its block matrix has diagonal $I$ and off-diagonal norm $∥ P Q ∥$ , so $P + Q \leq (1 + ∥ P Q ∥) I$ . Taking $P = P_{S}, Q = P_{T_{0}}$ gives $P_{S^{⊥}} + P_{T_{0}^{⊥}} = 2 I - P_{S} - P_{T_{0}} \geq (1 - c) I .$ By [F5], the input penalty has positive integer eigenvalues on the dirty-ancilla sector at time zero, while the output penalty has eigenvalue $N \geq 1$ on the reject sector at time $T$ ; these clock sectors are orthogonal. Thus $H_{i n} + H_{o u t} \geq P_{S^{⊥}}$ . Also $H_{p r o p} \geq (2 / N^{2}) P_{T_{0}^{⊥}}$ by [F1], and $2 / N^{2} \leq 1$ . The sum is at least $(2 / N^{2}) (1 - c) I \geq 1 / (2 N^{3}) I$ . This proves the ground-energy bound.

Depends on

Used by

Unary clock legality and 5-locality Lemma
5-Local Hamiltonian is QMA-complete Theorem

Dependency tree · two levels

18 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)
Julia Kempe, Alexei Kitaev, and Oded Regev, The Complexity of the Local Hamiltonian Problem (standard reference, not scraped)