Compile polynomial-time string functions to uniform quantum circuits
ProvedInfoLossLAR.WorstCase.RegevSketch.polytime_string_to_mqptlar-regev-bridgelatticeslearning-with-errorsquantum-computing
Let be a deterministic polynomial-time string function. There is a uniform quantum polynomial-time multi-output circuit family such that, for any input and any event on finite binary strings closed under appending a suffix,
The family has one output length per input length, so its output may contain a suffix after . This general compilation interface allows deterministic classical algorithms to be used as subroutines in prefix-decoded quantum output problems.
Formalization Note. Polynomial time is the platform's multi-stack Turing-machine predicate; the resulting family is uniform in its fixed Clifford+T gate set. The formal inequality is , which is probability one when circuit well-formedness is used.
Preamble
import Definitions.Def_InfoLossLAR_RegevSketch_DGS set_option autoImplicit false open QAlgorithms.Complexity InfoLossLAR.WorstCase
Formal statement
namespace InfoLossLAR.WorstCase.RegevSketch
theorem polytime_string_to_mqpt (f : Str → Str) (hf : PolyTimeComputable f) :
∃ P : MFamily, IsMQPT P ∧ ∀ w : Str, ∀ event : Str → Prop,
(∀ s t, event s → s <+: t → event t) → event (f w) →
(1 : ℝ) ≤ outputProb P w 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; generic multi-output classical-to-quantum model and encoding closure needed to formalize the finite-dimensional patch, not a verbatim theorem from that source.