Exact selected block of the certificate unitary
ProvedQMAPerfectCompleteness.Main.BlockProof.exact_block_identityqma-perfect-completeness-bbe19ef
Let V be a G₂ verifier and let (a,b) be a valid certificate. With k the index-register width, the block selected between flag 1 and flag 0 in the unitary U(z,a,b) is (a/2ᵏ)(I−C(z,a/b)). This is the algebraic identity in Lemma 3.6.
The index and verifier-ancilla registers are selected at zero, with incoming flag one and outgoing flag zero. This identifies the consistency residual with the physical rejection amplitude.
Preamble
/- Generated from Solutions.BlockEncoding by authoritative Stage-2 skeleton subtraction.
Original explanatory text, declaration names and scoped commands are retained.
Only selected proof cuts, import rewrites and fact-indexed platform edits are applied. -/
import Definitions.Def_QMAPerfectCompleteness_Main_Compiler
import Definitions.Def_QMAPerfectCompleteness_Main_Cyclic
import Definitions.Def_QMAPerfectCompleteness_Proof_BlockEncoding
import Definitions.Def_QMAPerfectCompleteness_Proof_Cyclic
import Definitions.Def_QMAPerfectCompleteness_Proof_EuclideanStates
/-! Algebraic ingredients of Lemma 3.6. All results in this file are proved from definitions;
no import of the open `exact_block_encoding` statement is used. -/
open Matrix
open scoped Kronecker
namespace QMAPerfectCompleteness.Main.BlockProof
end QMAPerfectCompleteness.Main.BlockProof
section
open QMAPerfectCompleteness QMAPerfectCompleteness.Main QMAPerfectCompleteness.Main.BlockProof
variable {G : GateSet} (V : Verifier G)
Formal statement
theorem QMAPerfectCompleteness.Main.BlockProof.exact_block_identity (V : Verifier gatesG2) (z : V.Proof) (a b : ℕ)
(hvalid : IsValidCertificate V a b) :
(V.zEmbed (indexQubits V) false)ᴴ * V.blockUnitary (indexQubits V) z a b *
V.zEmbed (indexQubits V) true =
((a : ℂ) / (2 : ℂ) ^ indexQubits V) • (1 - V.cyclicOp z ((a : ℝ) / b)) := by sorry
Source
Local source commit bbe19efbde567e5c8f7fe21655fd0c4da3573e4d, Solutions/BlockEncoding.lean:298-325; paper: QMA has perfect completeness, Sabee Grewal and Dorian Rudolph, user-provided main.tex.