Uniform acceptance-probability dispatch on encoded lattice dimension
ProvedInfoLossLAR.WorstCase.RegevSketch.gap_dimension_dispatchlar-regev-bridgelatticeslearning-with-errorsquantum-computing
For arbitrary uniform QPT one-bit families and a fixed natural cutoff, there is one uniform QPT one-bit family whose acceptance probability on every encoded GapSVP instance in dimension is exactly the acceptance probability of when is below the cutoff and exactly that of otherwise. The dimension is read from the self-delimiting matrix encoding. The theorem makes no promise about malformed inputs and requires only equality of the measured acceptance probabilities, not equality of full output states.
Preamble
import Definitions.Def_InfoLossLAR_RegevSketch_DGS set_option autoImplicit false open QAlgorithms.Complexity InfoLossLAR.WorstCase
Formal statement
namespace InfoLossLAR.WorstCase.RegevSketch
theorem gap_dimension_dispatch (E A : Family) (hE : IsQPT E) (hA : IsQPT A)
(cutoff : ℕ) :
∃ P : Family, IsQPT P ∧ ∀ n : ℕ, ∀ B : Matrix (Fin (famN n)) (Fin (famN n)) ℤ,
∀ δ : ℚ, acceptProb P (encGapInstance B δ) =
if n < cutoff then acceptProb E (encGapInstance B δ) else acceptProb A (encGapInstance B δ) := by sorry
end InfoLossLAR.WorstCase.RegevSketchSource
Standard uniform circuit composition and reversible classical control, specialized to the self-delimiting encGapInstance encoding in InfoLossLAR_WorstCase_LatticeProblems. This is an explicit machine-model composition obligation needed for the finite-dimensional patch, not a separately numbered claim in Regev.