The quantum segment is a realizable segment family
ProvedOPI.W6.IsPR.SegPR.qSegNThe constructed quantum program is represented as a first-order DAG: a list of nodes (gate, measurement, branching, halt, …) referring to each other by position. A segment is a function that, given the index of the continuation node and the start position , returns the list of new nodes placed at positions . A family is realizable () if has a polynomial realizer, i.e. a program of the underlying machine model whose running charge and output size are polynomial in the input size.
is the segment of the whole quantum program, built from natural-number data ( the wire layout, with coordinates, bits per symbol and system wires). It consists of the preparation of a phase-gradient state on wires, followed by repetitions (retry loop) of one trial:
- the preparation segment (repeat-until-success jobs, linear-map circuit with shift tables , phase circuit with table );
- the trial circuit , given as a list of gate fields;
- a zero test on the classical bit , whose accepting branch measures the output wires into the classical slots and halts;
- a reset of all system wires.
Statement. If all fifteen data functions of have polynomial realizers, then is a realizable segment family.
This is the main step showing that the generator emits the quantum part of the program in polynomial time.
import Definitions.Def_TwoFoldOPI_CL_Part05
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Circuit
import Definitions.Def_QAlgorithms_Defs_GradientMethods
import Definitions.Def_QAlgorithms_Defs_OPIOraclePrograms
import Definitions.Def_QAlgorithms_Defs_OPIUniformity
import Definitions.Def_QAlgorithms_Defs_Fourier
import Definitions.Def_TwoFoldOPI_elemBits
import Definitions.Def_TwoFoldOPI_schurSquare
import Definitions.Def_TwoFoldOPI_schurFailureSum
import Definitions.Def_CodingTheory
import Definitions.Def_OAIThreeMachineSched01
import Definitions.Def_CookLevin_Cost
import Definitions.Def_TwoFoldOPI_codeOf
import Definitions.Def_TwoFoldOPI_solves
import Definitions.Def_TwoFoldOPI_Input
import Definitions.Def_TwoFoldOPI_CLSerializableF
open OPI.W6.IsPR
open OAI.ThreeMachine.StackCompiler OPI OPI.Lay OPI.SymEnc
variable {α : Type} [Coding α]
theorem OPI.W6.IsPR.SegPR.qSegN {X : α → ParN} {bg dG dz dst K R Nt kd : α → ℕ} {jobs : α → List (List ℕ × PTab)}
{pivN : α → List ℕ} {TG : α → List (List (PTab × PTab))} {zT : α → PTab} {Cf : α → List (List ℕ)}
{slotN : α → List ℕ} (hX : IsPR X) (hbg : IsPR bg) (hdG : IsPR dG) (hdz : IsPR dz) (hdst : IsPR dst)
(hK : IsPR K) (hR : IsPR R) (hNt : IsPR Nt) (hkd : IsPR kd) (hjobs : IsPR jobs) (hpiv : IsPR pivN)
(hTG : IsPR TG) (hzT : IsPR zT) (hCf : IsPR Cf) (hslot : IsPR slotN) :
SegPR (fun a => Lay.qSegN (X a) (bg a) (dG a) (dz a) (dst a) (K a) (R a) (Nt a) (kd a) (jobs a)
(pivN a) (TG a) (zT a) (Cf a) (slotN a)) := by sorry