Lemma 3.7 — a valid certificate with
ProvedQMAPerfectCompleteness.Main.valid_certificatep2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1qmaquantum-complexity
On a YES instance there is a valid certificate with
Here and are fixed from and before the certificate is chosen, and validity means are positive integers representable by bits with and . The equality is exact, in the reals. This supplies the classical part of the honest prover's proof. The prover need not compute it efficiently.
Differences from the source:
- generalization: the fixed verifier of Lemma 3.1 on one input, with → any verifier over , with no lower bound on , a YES instance being a verifier that accepts some proof with probability at least ; reason: the statement specializes to the source's verifier on any YES input, and the bounds used hold for as well
- encoding: the scalar → the real part of that matrix entry; reason: is Hermitian, so its diagonal entry is real
Preamble
import Definitions.Def_QMAPerfectCompleteness_Main_BlockEncoding
Formal statement
namespace QMAPerfectCompleteness.Main
/-- Lemma 3.7 (p. 11): on a YES instance there is a valid certificate with `a/b = Γ_z > 2`. -/
theorem valid_certificate (V : Verifier gatesG2) (hyes : V.AcceptsSomeProof (2 / 3)) :
∃ (z : V.Proof) (a b : ℕ), IsValidCertificate V a b ∧
(a : ℝ) / b = V.gamma z ∧ 2 < V.gamma z := by sorry
end QMAPerfectCompleteness.Main
Source
Sabee Grewal, Dorian Rudolph, QMA has perfect completeness, STOC 2027 submission #490 (October 2026), p. 11, Lemma 3.7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.