Independent query postprocessing with a product failure bound
ProvedInfoLossLAR.WorstCase.RegevSearch.ShortProbeCircuit.compiledlar-regev-bridgelatticesquantum-computing
Let be a measured quantum circuit family and let be a finite list of requests determined by a classical input . Suppose a uniform quantum family emits a framed transcript whose readouts have the product Born law of independent executions of on these requests. For any deterministic polynomial-time function of and the list of readouts, there is a uniform measured family with the following guarantee.
Fix distinct positions in and an event on an individual readout. If the presence of any readout in prevents the output of from lying in a loss event , even after appending arbitrary padding, then
The bound allows arbitrary additional requests outside the chosen positions.
Preamble
import Definitions.Def_InfoLossLAR_LoadedBatchBundle_05 import Definitions.Def_InfoLossLAR_RegevSearch open QAlgorithms.Complexity InfoLossLAR.WorstCase open OAI.MetricKMedian.Binary.Automatic open scoped BigOperators Classical
Formal statement
namespace InfoLossLAR.WorstCase.RegevSearch.ShortProbeCircuit
theorem compiled (A : MFamily) (qs : Str → List Str) (finish : Str × List Str → Str)
(hf : Poly finish) (ht :
∃ F : MFamily, IsMQPT F ∧ ∀ w : Str,
let requests := qs w
let width (i : Fin requests.length) :=
(requests.get i).length + (A.anc (requests.get i).length + 1)
∃ padding : ((i : Fin requests.length) → Bits (width i)) → Str,
∀ event : Str → Prop, outputProb F w event =
∑ xs : (i : Fin requests.length) → Bits (width i),
let outs := List.ofFn (fun i => List.ofFn fun j =>
xs i (A.outW (requests.get i).length j))
if event (padding xs ++ (encS w ++ encL encS outs).reverse)
then ∏ i, ‖runLayered (A.circ (requests.get i).length)
(basisInput (toBits (requests.get i))) (xs i)‖^2 else 0) :
∃ T : MFamily, IsMQPT T ∧ ∀ w : Str, ∀ n : ℕ,
∀ pick : Fin n ↪ Fin (qs w).length,
∀ (ok loss : Str → Prop),
(∀ os tail, (∃ o ∈ os, ok o) → ¬loss (finish (w,os) ++ tail)) →
outputProb T w loss ≤
∏ j, outputProb A ((qs w).get (pick j)) (fun o => ¬ok o) := by sorry
end InfoLossLAR.WorstCase.RegevSearch.ShortProbeCircuitSource
Derivation for InfoLossLAR.WorstCase.RegevSearch.search_to_dual_candidate_lists, Independent query postprocessing with a product failure bound. https://prove2.me/theorems/98258395-a948-48ad-91ba-ef2767f47f76