Uniform quantum dispatch by encoded lattice dimension
ProvedInfoLossLAR.WorstCase.RegevSketch.sivp_dimension_dispatchlar-regev-bridgelatticeslearning-with-errorsquantum-computing
Let and be uniform multi-output quantum polynomial-time circuit families, and fix a dimension cutoff . There exists a uniform multi-output quantum polynomial-time family with the following property. For every , integer matrix , and event on binary output strings that remains true under appending any suffix,
The guarantee applies to all integer matrices, including singular ones, and to all prefix-monotone events. It isolates the input-dimension dispatch and circuit-composition obligation for multi-output solvers; output strings from different branches may have different lengths.
Formalization Note. The input is the self-delimiting platform matrix encoding; uniformity and the Born-rule probabilities use the existing interface.
Preamble
import Definitions.Def_InfoLossLAR_RegevSketch_DGS set_option autoImplicit false open QAlgorithms.Complexity open InfoLossLAR.WorstCase
Formal statement
namespace InfoLossLAR.WorstCase.RegevSketch
theorem sivp_dimension_dispatch (A E : MFamily) (hA : IsMQPT A) (hE : IsMQPT E)
(cutoff : ℕ) : ∃ P : MFamily, IsMQPT P ∧
∀ n, ∀ B : Matrix (Fin n) (Fin n) ℤ, ∀ event : Str → Prop,
(∀ s t, event s → s <+: t → event t) →
(if n < cutoff then outputProb E (encMat encI B) event
else outputProb A (encMat encI B) event) ≤
outputProb P (encMat encI B) event
:= by sorry
end InfoLossLAR.WorstCase.RegevSketch
Source
Chen Qian, Information Loss Is All You Need: TC⁰ Pseudorandomness from Worst-Case Lattices, arXiv:2611.05136, Appendix I.1, pp. 132–133. Explicit circuit-composition and encoding closure obligation for the finite-dimension patch, not a theorem claimed verbatim in the paper.