Polynomial-time uniformity of the executable cyclic compiler
ProvedQMAPerfectCompleteness.Main.CyclicRecipe.uniformOnVerifierCodesqma-perfect-completeness-bbe19ef
The executable G₂ coherent-certificate compiler preserves polynomial-time uniform generation on valid verifier codes: composing it with any polynomial-time generator of valid G₂ verifier encodings again gives a polynomial-time string function.
This is the runtime interface needed for the forward class reduction, with validity required on every generated input.
Preamble
/- Generated from Solutions.CyclicUniformity 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 Mathlib.Tactic.DeriveFintype import Definitions.Def_QMAPerfectCompleteness_Main_Classes import Definitions.Def_QAlgorithms_ClassicalStringComputability import Definitions.Def_QMAPerfectCompleteness_Main_Compiler import Definitions.Def_QMAPerfectCompleteness_Main_Cyclic import Init.Data.BitVec.Bitblast import Definitions.Def_QMAPerfectCompleteness_Main_BlockEncoding import Mathlib.Tactic.NormNum import Mathlib.Tactic.Linarith import Definitions.Def_QMAPerfectCompleteness_Main_Gates import Definitions.Def_QMAPerfectCompleteness_Proof_BinaryComposition import Definitions.Def_QMAPerfectCompleteness_Proof_BlockClockCoordinates import Definitions.Def_QMAPerfectCompleteness_Proof_BlockCompiler import Definitions.Def_QMAPerfectCompleteness_Proof_BlockCoordinates import Definitions.Def_QMAPerfectCompleteness_Proof_BlockEncoding import Definitions.Def_QMAPerfectCompleteness_Proof_BlockImplements import Definitions.Def_QMAPerfectCompleteness_Proof_BlockLogicalActions import Definitions.Def_QMAPerfectCompleteness_Proof_BlockLogicalSelect import Definitions.Def_QMAPerfectCompleteness_Proof_BlockProgramPlacement import Definitions.Def_QMAPerfectCompleteness_Proof_BlockStateCoordinates import Definitions.Def_QMAPerfectCompleteness_Proof_BlockTaggedActions import Definitions.Def_QMAPerfectCompleteness_Proof_BlockVerifierCoordinates import Definitions.Def_QMAPerfectCompleteness_Proof_BooleanCircuits import Definitions.Def_QMAPerfectCompleteness_Proof_BooleanFraming import Definitions.Def_QMAPerfectCompleteness_Proof_BoundedWriterTM import Definitions.Def_QMAPerfectCompleteness_Proof_CertificateBlockCompilerCorrectness import Definitions.Def_QMAPerfectCompleteness_Proof_CertificateBlockCorrectness import Definitions.Def_QMAPerfectCompleteness_Proof_CertificateClosingActions import Definitions.Def_QMAPerfectCompleteness_Proof_CertificateClosingCircuit import Definitions.Def_QMAPerfectCompleteness_Proof_CertificateCoordinates import Definitions.Def_QMAPerfectCompleteness_Proof_CertificateEtaTransport import Definitions.Def_QMAPerfectCompleteness_Proof_CertificateHadamardCoordinates import Definitions.Def_QMAPerfectCompleteness_Proof_CertificateHistoryCoordinates import Definitions.Def_QMAPerfectCompleteness_Proof_CertificateHistoryPrograms import Definitions.Def_QMAPerfectCompleteness_Proof_CertificateInitialization import Definitions.Def_QMAPerfectCompleteness_Proof_CertificateLogicalSelect import Definitions.Def_QMAPerfectCompleteness_Proof_CertificateMasterHistory import Definitions.Def_QMAPerfectCompleteness_Proof_CertificateMasterLayout import Definitions.Def_QMAPerfectCompleteness_Proof_CertificateMasterReadout import Definitions.Def_QMAPerfectCompleteness_Proof_CertificateMixture import Definitions.Def_QMAPerfectCompleteness_Proof_CertificateOldPrograms import Definitions.Def_QMAPerfectCompleteness_Proof_CertificatePostCorrectness import Definitions.Def_QMAPerfectCompleteness_Proof_CertificatePreparation import Definitions.Def_QMAPerfectCompleteness_Proof_CertificateQuantumTransports import Definitions.Def_QMAPerfectCompleteness_Proof_CertificateRangeCircuit import Definitions.Def_QMAPerfectCompleteness_Proof_CertificateReadout import Definitions.Def_QMAPerfectCompleteness_Proof_CertificateStageActions import Definitions.Def_QMAPerfectCompleteness_Proof_CertificateThresholdLayout import Definitions.Def_QMAPerfectCompleteness_Proof_CertificateValidity import Definitions.Def_QMAPerfectCompleteness_Proof_CertificateValidityCircuit import Definitions.Def_QMAPerfectCompleteness_Proof_CertificateValidityPreparation import Definitions.Def_QMAPerfectCompleteness_Proof_CertificateVerifierCoordinates import Definitions.Def_QMAPerfectCompleteness_Proof_CertificateVerifierLayout import Definitions.Def_QMAPerfectCompleteness_Proof_CircuitExprTM import Definitions.Def_QMAPerfectCompleteness_Proof_CircuitProvisionalWriter import Definitions.Def_QMAPerfectCompleteness_Proof_CircuitRecipe import Definitions.Def_QMAPerfectCompleteness_Proof_CircuitUnitary import Definitions.Def_QMAPerfectCompleteness_Proof_ClassTransport import Definitions.Def_QMAPerfectCompleteness_Proof_ClearStacksTM import Definitions.Def_QMAPerfectCompleteness_Proof_ClockCircuits import Definitions.Def_QMAPerfectCompleteness_Proof_CoherentAcceptance import Definitions.Def_QMAPerfectCompleteness_Proof_CoherentCertificate import Definitions.Def_QMAPerfectCompleteness_Proof_CoherentReadout import Definitions.Def_QMAPerfectCompleteness_Proof_ComparisonCircuits import Definitions.Def_QMAPerfectCompleteness_Proof_ConcreteUniformity import Definitions.Def_QMAPerfectCompleteness_Proof_ConditionalWriterTM import Definitions.Def_QMAPerfectCompleteness_Proof_ControlCircuits import Definitions.Def_QMAPerfectCompleteness_Proof_CountedWriterLoops import Definitions.Def_QMAPerfectCompleteness_Proof_Cyclic import Definitions.Def_QMAPerfectCompleteness_Proof_CyclicClockMetadata import Definitions.Def_QMAPerfectCompleteness_Proof_CyclicClockPrefixTM import Definitions.Def_QMAPerfectCompleteness_Proof_CyclicFullMetadata import Definitions.Def_QMAPerfectCompleteness_Proof_CyclicIndexMetadataCorrectness import Definitions.Def_QMAPerfectCompleteness_Proof_CyclicIndexMetadataIO import Definitions.Def_QMAPerfectCompleteness_Proof_CyclicIndexMetadataTM import Definitions.Def_QMAPerfectCompleteness_Proof_CyclicMetadataTM import Definitions.Def_QMAPerfectCompleteness_Proof_CyclicProvisionalCode import Definitions.Def_QMAPerfectCompleteness_Proof_CyclicRawCompiler import Definitions.Def_QMAPerfectCompleteness_Proof_CyclicRawCorrectness import Definitions.Def_QMAPerfectCompleteness_Proof_CyclicRawLayout import Definitions.Def_QMAPerfectCompleteness_Proof_CyclicRecipe import Definitions.Def_QMAPerfectCompleteness_Proof_CyclicRecipeRealization import Definitions.Def_QMAPerfectCompleteness_Proof_CyclicVerifier import Definitions.Def_QMAPerfectCompleteness_Proof_Dyadic import Definitions.Def_QMAPerfectCompleteness_Proof_DyadicCompiler import Definitions.Def_QMAPerfectCompleteness_Proof_DyadicEncoding import Definitions.Def_QMAPerfectCompleteness_Proof_DyadicPreservation import Definitions.Def_QMAPerfectCompleteness_Proof_DynamicBlockCompiler import Definitions.Def_QMAPerfectCompleteness_Proof_DynamicRangeLayout import Definitions.Def_QMAPerfectCompleteness_Proof_EqualityCircuits import Definitions.Def_QMAPerfectCompleteness_Proof_EuclideanStates import Definitions.Def_QMAPerfectCompleteness_Proof_FinitePlanCompilerTM import Definitions.Def_QMAPerfectCompleteness_Proof_GateCompilation import Definitions.Def_QMAPerfectCompleteness_Proof_HTCompiler import Definitions.Def_QMAPerfectCompleteness_Proof_HTCompilerTM import Definitions.Def_QMAPerfectCompleteness_Proof_HTEncoding import Definitions.Def_QMAPerfectCompleteness_Proof_HTPreservation import Definitions.Def_QMAPerfectCompleteness_Proof_HadamardToffoli import Definitions.Def_QMAPerfectCompleteness_Proof_IndexHadamards import Definitions.Def_QMAPerfectCompleteness_Proof_InstructionBuffersTM import Definitions.Def_QMAPerfectCompleteness_Proof_PointwiseSetup import Definitions.Def_QMAPerfectCompleteness_Proof_PolyTimeComposition import Definitions.Def_QMAPerfectCompleteness_Proof_RawArithmeticGadgets import Definitions.Def_QMAPerfectCompleteness_Proof_RawCertificateGadgets import Definitions.Def_QMAPerfectCompleteness_Proof_RawCircuitEncoding import Definitions.Def_QMAPerfectCompleteness_Proof_RawControlGadgets import Definitions.Def_QMAPerfectCompleteness_Proof_RawG2Gadgets import Definitions.Def_QMAPerfectCompleteness_Proof_RawThresholdGadgets import Definitions.Def_QMAPerfectCompleteness_Proof_RealSimulation import Definitions.Def_QMAPerfectCompleteness_Proof_RecipeCompositeWriters import Definitions.Def_QMAPerfectCompleteness_Proof_RecipeGadgets import Definitions.Def_QMAPerfectCompleteness_Proof_RecipeLeafWriter import Definitions.Def_QMAPerfectCompleteness_Proof_RecipeNormalization import Definitions.Def_QMAPerfectCompleteness_Proof_RecipeSerializerContinuation import Definitions.Def_QMAPerfectCompleteness_Proof_RecipeSerializerSetup import Definitions.Def_QMAPerfectCompleteness_Proof_RecipeSerializerTM import Definitions.Def_QMAPerfectCompleteness_Proof_RecipeVerifierContext import Definitions.Def_QMAPerfectCompleteness_Proof_RecipeWriterContext import Definitions.Def_QMAPerfectCompleteness_Proof_RecountGatesCorrectness import Definitions.Def_QMAPerfectCompleteness_Proof_RecountGatesTM import Definitions.Def_QMAPerfectCompleteness_Proof_RegisterCopies import Definitions.Def_QMAPerfectCompleteness_Proof_Repetition import Definitions.Def_QMAPerfectCompleteness_Proof_RepetitionCircuit import Definitions.Def_QMAPerfectCompleteness_Proof_RepetitionEncoding import Definitions.Def_QMAPerfectCompleteness_Proof_ReversibleGadgets import Definitions.Def_QMAPerfectCompleteness_Proof_SourceBuffersTM import Definitions.Def_QMAPerfectCompleteness_Proof_SourceInstructionMapper import Definitions.Def_QMAPerfectCompleteness_Proof_SourceWriter import Definitions.Def_QMAPerfectCompleteness_Proof_SourceWriterBounds import Definitions.Def_QMAPerfectCompleteness_Proof_SourceWriterTM import Definitions.Def_QMAPerfectCompleteness_Proof_StackEmbedding import Definitions.Def_QMAPerfectCompleteness_Proof_StackTransfers import Definitions.Def_QMAPerfectCompleteness_Proof_StreamWriterTM import Definitions.Def_QMAPerfectCompleteness_Proof_StructuredStackCode import Definitions.Def_QMAPerfectCompleteness_Proof_ThresholdLayout import Definitions.Def_QMAPerfectCompleteness_Proof_ThresholdPreparation import Definitions.Def_QMAPerfectCompleteness_Proof_UnaryDispatch import Definitions.Def_QMAPerfectCompleteness_Proof_UnaryEvaluator import Definitions.Def_QMAPerfectCompleteness_Proof_UnaryFieldCode import Definitions.Def_QMAPerfectCompleteness_Proof_UnaryMetadataArithmetic import Definitions.Def_QMAPerfectCompleteness_Proof_UnaryNextPowerCorrectness import Definitions.Def_QMAPerfectCompleteness_Proof_UnaryNextPowerPhases import Definitions.Def_QMAPerfectCompleteness_Proof_UnaryNextPowerTM import Definitions.Def_QMAPerfectCompleteness_Proof_UnaryStackOps import Definitions.Def_QMAPerfectCompleteness_Proof_VariableAddition import Definitions.Def_QMAPerfectCompleteness_Proof_VariableComparison import Definitions.Def_QMAPerfectCompleteness_Proof_VariableEquality import Definitions.Def_QMAPerfectCompleteness_Proof_VariableHistoryEquality import Definitions.Def_QMAPerfectCompleteness_Proof_VerifierAnalysis import Definitions.Def_QMAPerfectCompleteness_Proof_VerifierEncoding /- Namespace registrations retained from original proof-only imports. -/ namespace QMAPerfectCompleteness.Main.Certificate end QMAPerfectCompleteness.Main.Certificate namespace QMAPerfectCompleteness.Main.DiagonalProof end QMAPerfectCompleteness.Main.DiagonalProof namespace QMAPerfectCompleteness.Main.BlockComposition end QMAPerfectCompleteness.Main.BlockComposition namespace QMAPerfectCompleteness.Main.BlockTransport end QMAPerfectCompleteness.Main.BlockTransport namespace QMAPerfectCompleteness.Main.BlockHistoryCoordinates end QMAPerfectCompleteness.Main.BlockHistoryCoordinates namespace QMAPerfectCompleteness.Main.BlockHadamardCoordinates end QMAPerfectCompleteness.Main.BlockHadamardCoordinates namespace QMAPerfectCompleteness.Main.CoordinateFibers end QMAPerfectCompleteness.Main.CoordinateFibers namespace QMAPerfectCompleteness.Main.CertificateClaimBits end QMAPerfectCompleteness.Main.CertificateClaimBits namespace QMAPerfectCompleteness.Main.CertificateReadoutEffect end QMAPerfectCompleteness.Main.CertificateReadoutEffect namespace QMAPerfectCompleteness.Main.CertificateVerifierEffect end QMAPerfectCompleteness.Main.CertificateVerifierEffect namespace QMAPerfectCompleteness.Uniformity.Expansion end QMAPerfectCompleteness.Uniformity.Expansion namespace QMAPerfectCompleteness.Uniformity.UnaryNatArithmetic end QMAPerfectCompleteness.Uniformity.UnaryNatArithmetic /-! The paper's actual coherent-certificate circuit has a closed finite-machine polynomial code generator. Metadata, bounded recipe evaluation, source traversal and gate recounting are all witnessed by literal finite TM2 programs. -/ set_option backward.isDefEq.respectTransparency false set_option maxHeartbeats 1800000 namespace QMAPerfectCompleteness.Main.CyclicRecipe end QMAPerfectCompleteness.Main.CyclicRecipe section open QMAPerfectCompleteness QMAPerfectCompleteness.Main QMAPerfectCompleteness.Main.CyclicRecipe open CircuitRecipe open ClassTransport open QAlgorithms.Complexity (PolyTimeComputable)
Formal statement
theorem QMAPerfectCompleteness.Main.CyclicRecipe.uniformOnVerifierCodes :
UniformOnVerifierCodes gatesG2 executableCompile := by sorry
Source
Local source commit bbe19efbde567e5c8f7fe21655fd0c4da3573e4d, Solutions/CyclicUniformity.lean:16-38; paper: QMA has perfect completeness, Sabee Grewal and Dorian Rudolph, user-provided main.tex.