Lemma 3.4 — the cyclic history kernel and its soundness
ProvedQMAPerfectCompleteness.Main.cyclic_constrainthistory-statesp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1qmaquantum-complexity
Let and be the operator and vector of Eq. (3).
- On a YES instance, if and , then and
- On a NO instance, that is, if every proof is accepted with probability at most ,
for all , all real , and all complex vectors , normalized or not, with the Euclidean norm.
Clause 2 does not assume : it holds for every claimed value. Together the clauses reduce the distinction between YES and NO instances to an exact kernel condition.
Differences from the source:
- generalization: the fixed verifier of Lemma 3.1 on one input → any verifier over , with YES and NO instances being the conditions at and on that verifier, and without the source's ; reason: the statement specializes to the source's verifier on any input in the promise; no property of is used
- encoding: the number → the real part of the matrix entry ; histories are complex functions on the clock/proof basis, with euclidNorm defined as the square root of the sum of squared absolute values; reason: is Hermitian, so the entry is real, and this is exactly the finite-dimensional Euclidean norm
Preamble
import Definitions.Def_QMAPerfectCompleteness_Main_Cyclic open Matrix
Formal statement
namespace QMAPerfectCompleteness.Main
/-- Lemma 3.4 (p. 8). (i) On a YES instance, if `Γ_z > 2` and `Γ = Γ_z`, then `|Ω_z⟩ ≠ 0` satisfies
`(I - C_{z,Γ})|Ω_z⟩ = 0`. (ii) On a NO instance (`E ⪯ I/3`),
`‖(I - C_{z,Γ})|Ψ⟩‖ ≥ (1/3)‖|Ψ⟩‖` for all `z`, all `Γ ≥ 2` and all `|Ψ⟩`. -/
theorem cyclic_constraint (V : Verifier gatesG2) :
(V.AcceptsSomeProof (2 / 3) → ∀ (z : V.Proof) (Γ : ℝ), 2 < V.gamma z → Γ = V.gamma z →
V.historyVector z ≠ 0 ∧ (1 - V.cyclicOp z Γ) *ᵥ V.historyVector z = 0) ∧
(V.AcceptsAllProofsAtMost (1 / 3) → ∀ (z : V.Proof) (Γ : ℝ), 2 ≤ Γ → ∀ Ψ : History V → ℂ,
(1 / 3) * euclidNorm Ψ ≤ euclidNorm ((1 - V.cyclicOp z Γ) *ᵥ Ψ)) := by sorry
end QMAPerfectCompleteness.Main
Source
Sabee Grewal, Dorian Rudolph, QMA has perfect completeness, STOC 2027 submission #490 (October 2026), p. 8, Lemma 3.4, Eq. (3)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.