Exact acceptance preservation by the G₂-to-HT compiler
ProvedQMAPerfectCompleteness.Main.HTCompiler.compileVerifier_acceptanceOperatorqma-perfect-completeness-bbe19ef
For every G₂ verifier V, the compiler using Hadamard and Toffoli gates and three shared clean ancillary wires has exactly the same proof-space acceptance operator:
The source proof register is unchanged. Hence the equality preserves acceptance probabilities for every mixed proof, including proofs entangled across any decomposition of that register. It provides the semantic justification for exact gate synthesis after amplification.
Preamble
/- Generated from Solutions.HTPreservation 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_Gates import Definitions.Def_QMAPerfectCompleteness_Main_Cyclic import Definitions.Def_QMAPerfectCompleteness_Main_Compiler import Definitions.Def_QMAPerfectCompleteness_Main_Classes import Definitions.Def_QMAPerfectCompleteness_Proof_BlockEncoding import Definitions.Def_QMAPerfectCompleteness_Proof_CircuitUnitary import Definitions.Def_QMAPerfectCompleteness_Proof_Cyclic import Definitions.Def_QMAPerfectCompleteness_Proof_EuclideanStates import Definitions.Def_QMAPerfectCompleteness_Proof_GateCompilation import Definitions.Def_QMAPerfectCompleteness_Proof_HTCompiler import Definitions.Def_QMAPerfectCompleteness_Proof_HTPreservation import Definitions.Def_QMAPerfectCompleteness_Proof_HadamardToffoli import Definitions.Def_QMAPerfectCompleteness_Proof_RawCircuitEncoding import Definitions.Def_QMAPerfectCompleteness_Proof_RealSimulation import Definitions.Def_QMAPerfectCompleteness_Proof_ReversibleGadgets import Definitions.Def_QMAPerfectCompleteness_Proof_VerifierEncoding open Matrix open scoped Kronecker set_option backward.isDefEq.respectTransparency false namespace QMAPerfectCompleteness.Main.HTCompiler end QMAPerfectCompleteness.Main.HTCompiler section open QMAPerfectCompleteness QMAPerfectCompleteness.Main QMAPerfectCompleteness.Main.HTCompiler open HadamardToffoli ReversibleGadgets
Formal statement
theorem QMAPerfectCompleteness.Main.HTCompiler.compileVerifier_acceptanceOperator (V : Verifier gatesG2) :
(compileVerifier V).acceptanceOperator = V.acceptanceOperator := by sorry
Source
Auxiliary formalization source: commit bbe19efbde567e5c8f7fe21655fd0c4da3573e4d, Solutions/HTPreservation.lean:343–359. Paper context: Sabee Grewal and Dorian Rudolph, QMA has perfect completeness, user-provided main.tex. Auxiliary acceptance-preservation theorem for the exact Hadamard–Toffoli synthesis used in the proof of Theorem 1.1.