Lemma 3.3 — succinct exact description of the diagonal entries
ProvedQMAPerfectCompleteness.Main.diagonal_witnessp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1qmaquantum-complexity
Let be a verifier over with gates , let , , and let be the clock length. For every the number satisfies
Moreover for natural numbers , , each with at most bits. On a YES instance, that is, if some proof is accepted with probability at least , some has .
Unlike the maximum eigenvalue of , the number is therefore an exact quantity with a polynomial-size description, which the prover can send.
Formalization Note The hypothesis is the source's standing assumption for §3.2 (p. 7). It is needed: for and one has , which has bits. The of the source is stated through its explicit bound.
Differences from the source:
- generalization: the fixed verifier of Lemma 3.1 on one input → any verifier over with , 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; nothing else about is used
- encoding: the number → the real part of that matrix entry; reason: is Hermitian, so the entry is real
- encoding: a rational description with numerator and denominator of at most bits → nonnegative natural numbers , with , , and Nat.size bounds on both numbers; reason: Nat.size is binary length, and allowing an unreduced description preserves existence at the stated bound
Preamble
import Definitions.Def_QMAPerfectCompleteness_Main_Cyclic open Matrix
Formal statement
namespace QMAPerfectCompleteness.Main
/-- Lemma 3.3 (p. 7), for a verifier over `𝒢₂` with `g ≥ 1` gates `H ⊗ H`, `h = 2g`: for every `z`,
`0 ≤ Γ_z ≤ 2^ℓ` and `2^{hℓ} Γ_z ∈ ℤ`, and `Γ_z` is a rational whose numerator and denominator have
at most `(h + 1)ℓ` bits. On a YES instance (`λ_max(E) ≥ 2/3`) some `z` has `Γ_z > 2`. -/
theorem diagonal_witness (V : Verifier gatesG2) (hg : 1 ≤ hhCount V) :
(∀ z : V.Proof,
0 ≤ V.gamma z ∧ V.gamma z ≤ 2 ^ ell V.proofQubits ∧
(∃ n : ℤ, (2 : ℝ) ^ (2 * hhCount V * ell V.proofQubits) * V.gamma z = n) ∧
∃ p q : ℕ, 0 < q ∧ V.gamma z = (p : ℝ) / q ∧
p.size ≤ (2 * hhCount V + 1) * ell V.proofQubits ∧
q.size ≤ (2 * hhCount V + 1) * ell V.proofQubits) ∧
(V.AcceptsSomeProof (2 / 3) → ∃ z : V.Proof, 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. 7, Lemma 3.3, with the standing notation of §3.1–3.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.