Uniform repeated quantum circuits with classical input preparation and output encoding
ProvedInfoLossLAR.WorstCase.RegevSearch.uniform_raw_repetitionsFix a uniform polynomial-time family of multi-output quantum circuits. A polynomial-time classical program computes a binary query from the input. A second program produces one slot per desired repetition, and a third encodes a list of measured binary words as a single word.
There exists one uniform polynomial-time quantum circuit family that realizes these programs and repetitions. On a fixed input, initialize one disjoint copy per slot with the computed query. Write for the single-copy Born weight of a full computational basis outcome and for its designated output word. For every event on the final word, its probability equals the sum over all tuples of basis outcomes of their product weights, restricted to tuples for which the encoded list of the , padded on the right with zeros to the output width, belongs to the event. With zero slots the encoder receives the empty list. The number of slots and the length and content of the query may vary among inputs of the same length.
import Definitions.Def_InfoLossLAR_RegevSketch_DGS import Definitions.Def_InfoLossLAR_FirstBridgeBundle_02 set_option autoImplicit false open QAlgorithms.Complexity InfoLossLAR.WorstCase open OAI.MetricKMedian.Binary.Automatic open scoped BigOperators Classical
namespace InfoLossLAR.WorstCase.RegevSearch
theorem uniform_raw_repetitions (H : MFamily) (hH : IsMQPT H)
(query slots : Str → Str) (encode : List Str → Str)
(hq : Poly query) (hs : Poly slots) (he : Poly encode) :
∃ G : MFamily, IsMQPT G ∧ ∀ (input q : Str) (copies : ℕ),
query input = q → (slots input).length = copies → ∀ observe : Str → Prop,
let raw (y : Bits (q.length + (H.anc q.length + 1))) :=
List.ofFn (fun j => y (H.outW q.length j))
let mass (y : Bits (q.length + (H.anc q.length + 1))) :=
‖runLayered (H.circ q.length) (basisInput (toBits q)) y‖ ^ 2
outputProb G input observe =
∑ ys : Fin copies → Bits (q.length + (H.anc q.length + 1)),
(∏ i, mass (ys i)) *
(let result := encode (List.ofFn (fun i => raw (ys i)))
if observe (result ++ List.replicate (G.outLen input.length - result.length) false)
then 1 else 0) := by
sorry
end InfoLossLAR.WorstCase.RegevSearch