Uniform quantum evaluation of a polynomial-time encoded request and response
ProvedInfoLossLAR.WorstCase.RegevSearch.PaddedDecoder.native_requestlar-regev-bridgelatticesquantum-computing
Let be a uniform polynomial-time quantum family. Given polynomial-time classical functions and , one uniform quantum family accepts a word , runs on the variable-length request , and returns an encoding with prefix for the measured response . For every pair of events on output words, if a failure on every padded response implies that the response of is bad, the probability of failure is bounded by the bad-response probability of on . The construction is independent of both events.
Preamble
import Definitions.Def_InfoLossLAR_LoadedBatchBundle_05 import Definitions.Def_InfoLossLAR_RegevSketch_DGS open QAlgorithms.Complexity InfoLossLAR.WorstCase OAI.MetricKMedian.Binary.Automatic open scoped Classical
Formal statement
theorem InfoLossLAR.WorstCase.RegevSearch.PaddedDecoder.native_request (T : MFamily) (hT : IsMQPT T) (q : Str → Str) (hq : Poly q) (f : Str × Str → Str) (hf : Poly f) :
∃ C : MFamily, IsMQPT C ∧ ∀ (w : Str) (fail bad : Str → Prop),
(∀ o tail, fail (f (w,o) ++ tail) → bad o) →
outputProb C w fail ≤ outputProb T (q w) bad := by sorry
Source
Auxiliary lemma for the coherent shared-pool Fourier sampler, used to run its BDD family on a framed request at the actual request length. https://prove2.me/theorems/23174e03-6b1d-4113-b6b9-4dab17fa850a