The positive branch only copies the original input once before running the sampler
ProvedMIPRE.Introspection.ZeroIndexSampler.atZero_timeBound_posA statement of the module MIPRE.Background.Introspection.PauliSamplerZero of the MIP* = RE formalization (commit 70cbf1c of vidick/MIPRE-formalization). A zero-dimensional sampler at the exceptional index. The branch inspects the index in place. At zero it returns the empty answer without copying the query or reading the underlying sampler description.
The positive branch only copies the original input once before running the sampler.
Formal statement. In Lean, with the scope shown:
open MIPRE
open MIPRE.Introspection
open MIPRE.Introspection.ZeroIndexSampler
open MIPRE.Cost MIPRE.Cost.Prog MIPRE.Cost.PolyTimeFun MIPRE.CL
theorem MIPRE.Introspection.ZeroIndexSampler.atZero_timeBound_pos {ℓ n B k : ℕ} (S : CL.Sampler ℓ) (hn : n ≠ 0)
(h : S.TimeBoundAt n B k) :
(atZero S).TimeBoundAt n (B + esize n + 5) (max k 1)
Formalization Note MIPRE.Introspection.ZeroIndexSampler.atZero_timeBound_pos is declared in MIPRE/Background/Introspection/PauliSamplerZero.lean, lines 134–151. The binders, hypotheses and conclusion are exactly those of the Lean statement above; the uploaded statement elaborates to the same type as the declaration in the repository. The definitions it mentions are those of the published definition bundles of the module's import closure.
import Mathlib.Algebra.Algebra.Basic import Mathlib.Algebra.BigOperators.Fin import Mathlib.Algebra.BigOperators.Group.Finset.Basic import Mathlib.Algebra.BigOperators.Ring.Finset import Mathlib.Algebra.CharP.Algebra import Mathlib.Algebra.CharP.Two import Mathlib.Algebra.Field.ZMod import Mathlib.Algebra.Module.Basic import Mathlib.Algebra.MonoidAlgebra.Basic import Mathlib.Algebra.MvPolynomial.CommRing import Mathlib.Algebra.MvPolynomial.Degrees import Mathlib.Algebra.MvPolynomial.SchwartzZippel import Mathlib.Algebra.Order.BigOperators.Group.Finset import Mathlib.Algebra.Polynomial.Degree.Lemmas import Mathlib.Algebra.Polynomial.Degree.SmallDegree import Mathlib.Algebra.Polynomial.Div import Mathlib.Algebra.Polynomial.Eval.Defs import Mathlib.Algebra.Polynomial.Eval.Degree import Mathlib.Algebra.Polynomial.FieldDivision import Mathlib.Algebra.Polynomial.Monic import Mathlib.Algebra.Polynomial.Roots import Mathlib.Algebra.Polynomial.SpecificDegree import Mathlib.Algebra.Squarefree.Basic import Mathlib.Algebra.Star.Basic import Mathlib.Algebra.Star.Module import Mathlib.Analysis.CStarAlgebra.CStarMatrix import Mathlib.Analysis.CStarAlgebra.Classes import Mathlib.Analysis.Complex.Basic import Mathlib.Analysis.Complex.Order import Mathlib.Analysis.Matrix.Order import Mathlib.Analysis.Matrix.PosDef import Mathlib.Analysis.RCLike.Basic import Mathlib.Computability.Primrec.List import Mathlib.Data.Complex.Basic import Mathlib.Data.ENat.Lattice import Mathlib.Data.Fin.Tuple.Basic import Mathlib.Data.Finset.Image import Mathlib.Data.Finset.Sum import Mathlib.Data.Fintype.BigOperators import Mathlib.Data.Fintype.Option import Mathlib.Data.Fintype.Pi import Mathlib.Data.Fintype.Prod import Mathlib.Data.Fintype.Sum import Mathlib.Data.List.Basic import Mathlib.Data.List.GetD import Mathlib.Data.List.OfFn import Mathlib.Data.List.Rotate import Mathlib.Data.Matrix.Basic import Mathlib.Data.Matrix.Mul import Mathlib.Data.Nat.Bits import Mathlib.Data.Nat.Factorization.Basic import Mathlib.Data.Nat.Notation import Mathlib.Data.Nat.Size import Mathlib.Data.Rat.Cast.Order import Mathlib.Data.Real.Basic import Mathlib.Data.Set.Basic import Mathlib.Data.ZMod.Basic import Mathlib.FieldTheory.Finite.Basic import Mathlib.FieldTheory.Finite.Extension import Mathlib.FieldTheory.Finite.GaloisField import Mathlib.FieldTheory.Finite.Trace import Mathlib.FieldTheory.Galois.NormalBasis import Mathlib.FieldTheory.IsAlgClosed.AlgebraicClosure import Mathlib.FieldTheory.KummerExtension import Mathlib.FieldTheory.Minpoly.Finite import Mathlib.LinearAlgebra.Basis.Defs import Mathlib.LinearAlgebra.BilinearForm.Orthogonal import Mathlib.LinearAlgebra.FiniteDimensional.Lemmas import Mathlib.LinearAlgebra.LinearIndependent.Lemmas import Mathlib.LinearAlgebra.Matrix.Circulant import Mathlib.LinearAlgebra.Matrix.ConjTranspose import Mathlib.LinearAlgebra.Matrix.DotProduct import Mathlib.LinearAlgebra.Matrix.Kronecker import Mathlib.LinearAlgebra.Matrix.Notation import Mathlib.LinearAlgebra.Matrix.ToLin import Mathlib.LinearAlgebra.Pi import Mathlib.Logic.Denumerable import Mathlib.Logic.Equiv.Fin.Basic import Mathlib.Logic.Function.Iterate import Mathlib.Order.Fin.Basic import Mathlib.RingTheory.AdjoinRoot import Mathlib.RingTheory.Coprime.Lemmas import Mathlib.RingTheory.Polynomial.Content import Mathlib.RingTheory.Polynomial.Cyclotomic.Factorization import Mathlib.RingTheory.RootsOfUnity.PrimitiveRoots import Mathlib.RingTheory.Trace.Basic import Mathlib.Tactic.Abel import Mathlib.Tactic.DeriveFintype import Mathlib.Tactic.Linarith import Mathlib.Tactic.Module import Mathlib.Tactic.Ring import Definitions.Def_MIPRE_Foundations_Games import Definitions.Def_MIPRE_Foundations_Distances import Definitions.Def_MIPRE_Background_LIDT_Game import Definitions.Def_MIPRE_Foundations_CL_Register import Definitions.Def_MIPRE_Foundations_CL_Canonical import Definitions.Def_MIPRE_Background_LIDT_CLGame import Definitions.Def_MIPRE_Foundations_CL_Basic import Definitions.Def_MIPRE_Foundations_Cost_Basic_B import Definitions.Def_MIPRE_Foundations_Cost_Encoding_B import Definitions.Def_MIPRE_Foundations_SAT_Circuit import Definitions.Def_MIPRE_Foundations_SAT_Cnf import Definitions.Def_MIPRE_Foundations_Cost_PolyTime import Definitions.Def_MIPRE_Foundations_CL_Closure_B import Definitions.Def_MIPRE_Foundations_CL_Sampler import Definitions.Def_MIPRE_Foundations_Verifier import Definitions.Def_MIPRE_Foundations_SAT_Succinct import Definitions.Def_MIPRE_Foundations_SAT_Decoupled import Definitions.Def_MIPRE_Foundations_Cost_Closure import Definitions.Def_MIPRE_Foundations_Cost_Loops_B import Definitions.Def_MIPRE_Foundations_Cost_Fold import Definitions.Def_MIPRE_Foundations_Cost_Unary import Definitions.Def_MIPRE_Foundations_Cost_Numeric_B import Definitions.Def_MIPRE_Foundations_LowDegree_Encoding import Definitions.Def_MIPRE_Foundations_SAT_Pcp import Definitions.Def_MIPRE_Foundations_GameTransport import Definitions.Def_MIPRE_Foundations_GameDouble import Definitions.Def_MIPRE_Foundations_POVMValue import Definitions.Def_MIPRE_Foundations_PVM import Definitions.Def_MIPRE_Foundations_PVM_B import Definitions.Def_MIPRE_Foundations_LowDegree_SchwartzZippel import Definitions.Def_MIPRE_Foundations_LowDegree_Anticomm import Definitions.Def_MIPRE_Foundations_GameAdapt import Definitions.Def_MIPRE_Foundations_RegisterReindex import Definitions.Def_MIPRE_Foundations_RegisterReindex_B import Definitions.Def_MIPRE_Foundations_CL_Embedding import Definitions.Def_MIPRE_Foundations_CL_Graph import Definitions.Def_MIPRE_Foundations_CL_Detyping import Definitions.Def_MIPRE_Foundations_CL_DetypingLaw import Definitions.Def_MIPRE_Foundations_SampledGame import Definitions.Def_MIPRE_Foundations_CL_DetypingGame import Definitions.Def_MIPRE_Foundations_GapCompression import Definitions.Def_MIPRE_Foundations_Cost_Codable_B import Definitions.Def_MIPRE_Foundations_Halting_Descriptions import Definitions.Def_MIPRE_Foundations_CL_Downsize import Definitions.Def_MIPRE_Foundations_CL_TypedSampler import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryRepresentation import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryPolynomial import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryConstants import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryPower import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryTrace import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryQuotient import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryNormalize import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryDivision import Definitions.Def_MIPRE_Foundations_Cost_Binary import Definitions.Def_MIPRE_Foundations_SAT_Formula import Definitions.Def_MIPRE_Foundations_SAT_FmlLib import Definitions.Def_MIPRE_Foundations_SAT_Flatten import Definitions.Def_MIPRE_Foundations_Cost_Reader import Definitions.Def_MIPRE_Foundations_SAT_FmlProg import Definitions.Def_MIPRE_Foundations_SAT_ArrayProg import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryLinear import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryElimination import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryBasisProg import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryEchelon import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryEchelon_B import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryBasis import Definitions.Def_MIPRE_Foundations_LowDegree_BinarySolve import Definitions.Def_MIPRE_Foundations_LowDegree_BinarySolve_B import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryMatrixSolve import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryMatrixSolve_B import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryMatrixInverse import Definitions.Def_MIPRE_Foundations_LowDegree_SelfDualize import Definitions.Def_MIPRE_Foundations_LowDegree_BinarySquareRoot import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryCirculant import Definitions.Def_MIPRE_Foundations_Cost_Iterates import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryCirculantProg import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryCirculantProg_B import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryKernel import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryGroupAlgebra import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryGroupAlgebra_B import Definitions.Def_MIPRE_Foundations_LowDegree_FiniteReducedComponents import Definitions.Def_MIPRE_Foundations_LowDegree_IdempotentSplit import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryComponents import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryComponents_B import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryComponentsProg import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryComponentsProg_B import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryQuotientFrobenius import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryQuotientComponents import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryQuotientFactors import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryGCD import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryFactorization import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryCyclotomicSeed import Definitions.Def_MIPRE_Foundations_LowDegree_BinarySubstitution import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryNonresidueLoop import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryNonresidueCorrectness import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryQuotientOrbit import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryTraceBits import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryOrbitPolynomial import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryOrbitDescent import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryQuotientPolynomial import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryQuotientTranslation import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryCoprimeDegree import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryComposedSumPolynomial import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryComposedSumProg import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryOddPrimeProgram import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryPrimePowerTrace import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryArtinSchreier import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryArtinSchreierProg import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryArtinSchreierTower import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryArtinSchreierLoop import Definitions.Def_MIPRE_Foundations_LowDegree_UnaryDegreeArithmetic import Definitions.Def_MIPRE_Foundations_LowDegree_UnaryPrimality import Definitions.Def_MIPRE_Foundations_LowDegree_UnaryPrimePower import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryDegreeFactors import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryDegreeDecomposition import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryPrimePowerDispatch import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryIrreducibleAssembly import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryIrreducibleConstructor import Definitions.Def_MIPRE_Foundations_LowDegree_Shoup import Definitions.Def_MIPRE_Foundations_LowDegree_ShoupCoefficients import Definitions.Def_MIPRE_Foundations_SAT_QuotientField import Definitions.Def_MIPRE_Foundations_SAT_FieldTrace import Definitions.Def_MIPRE_Foundations_SAT_FieldTrace_B import Definitions.Def_MIPRE_Foundations_SAT_FieldCoordinates import Definitions.Def_MIPRE_Foundations_Cost_BinaryArithmetic import Definitions.Def_MIPRE_Foundations_Introspection_SeedSelectorProg import Definitions.Def_MIPRE_Foundations_SAT_TraceGram import Definitions.Def_MIPRE_Foundations_LowDegree_SelfDual import Definitions.Def_MIPRE_Foundations_LowDegree_NormalBasis import Definitions.Def_MIPRE_Foundations_SAT_NormalGram import Definitions.Def_MIPRE_Foundations_SAT_FrobeniusAction import Definitions.Def_MIPRE_Foundations_SAT_NormalElement import Definitions.Def_MIPRE_Foundations_SAT_FrobeniusMatrix import Definitions.Def_MIPRE_Foundations_SAT_FrobeniusActionProg import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryFold import Definitions.Def_MIPRE_Foundations_SAT_NormalElementProg import Definitions.Def_MIPRE_Foundations_SAT_NormalElementProg_B import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryInverse import Definitions.Def_MIPRE_Foundations_Introspection_LineRepresentativeProg import Definitions.Def_MIPRE_Foundations_Cost_BinaryCompare import Definitions.Def_MIPRE_Foundations_Introspection_SeededLineProg import Definitions.Def_MIPRE_Foundations_Cost_TreeBits import Definitions.Def_MIPRE_Foundations_CL_DetypingProgFinite import Definitions.Def_MIPRE_Foundations_CL_DetypingProgParse import Definitions.Def_MIPRE_Foundations_SAT_BasisTransport import Definitions.Def_MIPRE_Foundations_SAT_EffectiveSelfDual import Definitions.Def_MIPRE_Foundations_SAT_EffectiveNormalBasis import Definitions.Def_MIPRE_Foundations_Introspection_BasisProg import Definitions.Def_MIPRE_Foundations_Introspection_BinaryBlockProg import Definitions.Def_MIPRE_Foundations_Introspection_BinaryBlockProg_B import Definitions.Def_MIPRE_Background_LIDT_Adapter_Geometry import Definitions.Def_MIPRE_Foundations_CL_DetypingQueries import Definitions.Def_MIPRE_Foundations_CL_DetypingProgBits import Definitions.Def_MIPRE_Foundations_CL_DetypingProgCall import Definitions.Def_MIPRE_Foundations_CL_DetypingProgRoute import Definitions.Def_MIPRE_Foundations_Cost_Machine_B import Definitions.Def_MIPRE_Foundations_Cost_MachineData_B import Definitions.Def_MIPRE_Foundations_Cost_Interpreter_B import Definitions.Def_MIPRE_Foundations_Cost_MachineBound_B import Definitions.Def_MIPRE_Foundations_Cost_Toolkit_B import Definitions.Def_MIPRE_Foundations_Cost_Universal_B import Definitions.Def_MIPRE_Foundations_Introspection_PauliStageProg import Definitions.Def_MIPRE_Foundations_Introspection_PauliStageProg_B import Definitions.Def_MIPRE_Foundations_Halting_Lists_B import Definitions.Def_MIPRE_Foundations_Cost_Growth import Definitions.Def_MIPRE_Foundations_Halting_Arith import Definitions.Def_MIPRE_Foundations_Halting_Arith_B import Definitions.Def_MIPRE_Foundations_Repeat_Prims import Definitions.Def_MIPRE_Foundations_CL_Repeat import Definitions.Def_MIPRE_Foundations_Repeat_Bits import Definitions.Def_MIPRE_Foundations_VerifierValue import Definitions.Def_MIPRE_Foundations_Pipeline_Budget import Definitions.Def_MIPRE_Foundations_CL_DetypingProgQueries import Definitions.Def_MIPRE_Foundations_CL_DetypingProgSampler import Definitions.Def_MIPRE_Foundations_CL_DetypingProgCost import Definitions.Def_MIPRE_Foundations_CL_DetypingDeciderRoute import Definitions.Def_MIPRE_Foundations_CL_DetypingDeciderProg import Definitions.Def_MIPRE_Foundations_CL_DetypingClock import Definitions.Def_MIPRE_Foundations_Pipeline_Introspection import Definitions.Def_MIPRE_Foundations_Halting_PolyBounded import Definitions.Def_MIPRE_Foundations_Introspection_ClockArithmetic import Definitions.Def_MIPRE_Foundations_Introspection_ParserBits import Definitions.Def_MIPRE_Foundations_Introspection_ParserAnswers import Definitions.Def_MIPRE_Foundations_Introspection_DynamicParserSlice import Definitions.Def_MIPRE_Foundations_Introspection_DynamicParser import Definitions.Def_MIPRE_Foundations_Introspection_SourceCompilerParams import Definitions.Def_MIPRE_Foundations_Introspection_PauliSamplerParams import Definitions.Def_MIPRE_Foundations_Introspection_Clock import Definitions.Def_MIPRE_Foundations_Introspection_ClockCost import Definitions.Def_MIPRE_Foundations_Introspection_ClockSimulation import Definitions.Def_MIPRE_Foundations_Introspection_ClockCompiler import Definitions.Def_MIPRE_Foundations_Introspection_ClockSimulationCost import Definitions.Def_MIPRE_Foundations_Introspection_SourceCompilerParamsCost import Definitions.Def_MIPRE_Foundations_Introspection_PauliSamplerParamsCost import Definitions.Def_MIPRE_LCS_Basic import Definitions.Def_MIPRE_LCS_Common import Definitions.Def_MIPRE_LCS_Measurement import Definitions.Def_MIPRE_LCS_Observable import Definitions.Def_MIPRE_LCS_Strategy_ObservableToProjector import Definitions.Def_MIPRE_LCS_NonlocalGame import Definitions.Def_MIPRE_LCS_Pauli import Definitions.Def_MIPRE_LCS_MagicSquare_Strategy import Definitions.Def_MIPRE_LCS_MagicSquare_Game import Definitions.Def_MIPRE_Background_QLD_Game import Definitions.Def_MIPRE_Background_QLD_CLPresentation import Definitions.Def_MIPRE_Background_QLD_CLBinary import Definitions.Def_MIPRE_Background_QLD_CLExplicitSeed import Definitions.Def_MIPRE_Background_QLD_PauliStagePrograms import Definitions.Def_MIPRE_Background_QLD_TypeEncoding import Definitions.Def_MIPRE_Background_QLD_BinaryBlocks import Definitions.Def_MIPRE_Foundations_Introspection_PauliRowsProg import Definitions.Def_MIPRE_Foundations_Introspection_Types import Definitions.Def_MIPRE_Foundations_Introspection_TypeGraph import Definitions.Def_MIPRE_Foundations_Introspection_TypedPresentation import Definitions.Def_MIPRE_Foundations_Introspection_PauliFactorProg import Definitions.Def_MIPRE_Background_QLD_SamplerQueryProgram import Definitions.Def_MIPRE_Background_QLD_PauliFactorPrograms import Definitions.Def_MIPRE_Background_Introspection_PauliSampler import Definitions.Def_MIPRE_Background_Introspection_PauliSamplerCost import Definitions.Def_MIPRE_Foundations_Introspection_SamplerProgram import Definitions.Def_MIPRE_Foundations_Introspection_Sampler import Definitions.Def_MIPRE_Foundations_Introspection_SamplerCost import Definitions.Def_MIPRE_Background_Introspection_PauliSamplerExtension import Definitions.Def_MIPRE_Background_Introspection_PauliSamplerZero open MIPRE open MIPRE.Introspection open MIPRE.Introspection.ZeroIndexSampler open MIPRE.Cost MIPRE.Cost.Prog MIPRE.Cost.PolyTimeFun MIPRE.CL
theorem MIPRE.Introspection.ZeroIndexSampler.atZero_timeBound_pos {ℓ n B k : ℕ} (S : CL.Sampler ℓ) (hn : n ≠ 0)
(h : S.TimeBoundAt n B k) :
(atZero S).TimeBoundAt n (B + esize n + 5) (max k 1) := by sorry