Construction for Theorem 7.4, part 2: decoders, trials, state preparation, serialization
DefinitionTwoFoldOPI_CL_Part02lean-formalizationquantum-algorithmstwo-fold-opi-construction
Definitions underlying the formal construction behind the algorithmic part of Theorem 7.4, part 2 (imports part 1). It contains the real decoder layout and the full decoder circuit, the trial loop (zero test, readout, retries), the subtraction circuit, the repeat-until-success state-preparation stages and their jobs, the preparation layout, and the first part of the polynomial-time realizer framework: first-order program nodes, the depth-first serializer, and polynomial realizers with their arithmetic and list combinators.
The bundle contains only definitions together with the structural lemmas these definitions require.
Definition code
import Definitions.Def_TwoFoldOPI_CL_Part01
import Mathlib
import Definitions.Def_OAIThreeMachineSched01
import Definitions.Def_CookLevin_Cost
set_option maxHeartbeats 400000
set_option linter.all false
-- ===== OPI.BfacL =====
section
/-!
# Nested factorized states
`bfacL L g = h₁ ⊗_{w₁} (h₂ ⊗_{w₂} ⋯ g)` for a list `L` of (register, state) pairs. Commutation,
support and norm lemmas.
-/
namespace OPI
open QAlgorithms
variable {n : ℕ}
/-- A state on a register. -/
structure Res (n : ℕ) where
k : ℕ
w : Fin k ↪ Fin n
h : Qubits k → ℂ
/-- Nested factorized states. -/
noncomputable def bfacL : List (Res n) → (Qubits n → ℂ) → Qubits n → ℂ
| [], g => g
| r :: L, g => bfac r.w r.h (bfacL L g)
/-- Two registers are disjoint. -/
def Res.Disj (r r' : Res n) : Prop := ∀ i j, r.w i ≠ r'.w j
end OPI
namespace OPI
open QAlgorithms
variable {n : ℕ}
end OPI
namespace OPI
open QAlgorithms
variable {n : ℕ}
/-- Clear all registers of a list. -/
noncomputable def clrL (L : List (Res n)) (y : Qubits n) : Qubits n := L.foldr (fun r y => clrE r.w y) y
end OPI
namespace OPI
open QAlgorithms
variable {n : ℕ}
end OPI
end
-- ===== OPI.RWires =====
section
/-!
# Wires of reversible circuits
`WiresIn P L`: every gate of `L` touches only wires satisfying `P`. Such circuits commute with
factorized states on registers outside `P` (`revCirc_bfac`). Wire bounds for the builders
`mcx`, `flipZeros`, `eqFlip`, `cxOut`, `lookup`, `lookupF`, `swapRegs`, `permGad`.
-/
namespace OPI
open QAlgorithms
variable {N : ℕ}
/-- Wires of a reversible gate. -/
def RGate.wires : RGate N → List (Fin N)
| .x q => [q]
| .cx c t => [c, t]
| .ccx a b t => [a, b, t]
/-- All gates touch only wires satisfying `P`. -/
def WiresIn (P : Fin N → Prop) (L : List (RGate N)) : Prop := ∀ g ∈ L, ∀ q ∈ g.wires, P q
/-! ## Builders -/
/-! ## Commutation with factorized states -/
section Comm
variable {k : ℕ} (w : Fin k ↪ Fin N)
end Comm
end OPI
end
-- ===== OPI.DecReal =====
section
/-!
# The real decoder: `QFT_q` gadgets with `|u_p⟩` resources
The ideal decoder `allOps` uses exact `Q_q` on the symbol registers. The real one uses the
`QFT_q` gadgets `Q i c` (`QQ`), which consume `|u_p⟩` resources in their `B` registers. With all
resources prepared (`RSL`), the real decoder is within `2 m ε` of the ideal one.
-/
namespace OPI
namespace SymEnc
open QAlgorithms TwoFoldOPI Matrix
variable (F : AvgCaseTI.FieldPres) {n b t m : ℕ}
/-- The resources of a `QFT_q` gadget. -/
noncomputable def resQ (Q : QQ n b F t) : List (Res n) :=
Q.Gs.map fun G => ⟨Fq.w F, G.bE, fvec F.p (Fq.w F) 0⟩
/-- Constrained wires of a `QFT_q` gadget. -/
def cWire (Q : QQ n b F t) (q : Fin n) : Prop :=
q ∈ Q.ZR ++ Q.asR ++ [Q.fR] ∨
∃ G ∈ Q.Gs, q ∈ Set.range G.bE ∨ q ∈ Set.range G.cE ∨ q ∈ G.acc ∨ q ∈ G.cl
/-- Scratch wires of the `E` and `P_β` gadgets of a coordinate. -/
def epWire {reg : Fin m × Bool × Fin (bitsPerSymbol F) ↪ Fin n} {i : Fin m} (W : CoordWires F reg i)
(q : Fin n) : Prop :=
q = W.aE ∨ q = W.fE ∨ q ∈ W.ZE ∨ q ∈ W.asE ∨ q = W.fP ∨ q ∈ W.ZP ∨ q ∈ W.asP
/-- **Layout of the real decoder.** -/
structure RealDec (reg : Fin m × Bool × Fin (bitsPerSymbol F) ↪ Fin n) (b t : ℕ) where
W : ∀ i, CoordWires F reg i
Q : Fin m → Bool → QQ n b F t
hQX : ∀ i c, (Q i c).X = bReg reg i c
hres : ∀ i c i' c', (i, c) ≠ (i', c') → ∀ r ∈ resQ F (Q i c), ∀ r' ∈ resQ F (Q i' c'), r.Disj r'
hcw : ∀ i c q, cWire F (Q i c) q → (∀ p, reg p ≠ q) ∧
∀ i' c', (i, c) ≠ (i', c') → ∀ r ∈ resQ F (Q i' c'), q ∉ Set.range r.w
hep : ∀ i i' c', ∀ r ∈ resQ F (Q i' c'), ∀ q, epWire F (W i) q → q ∉ Set.range r.w
variable {F}
variable {reg : Fin m × Bool × Fin (bitsPerSymbol F) ↪ Fin n} (D : RealDec F reg b t)
/-- The resources of all gadgets. -/
def RealDec.isRes (r : Res n) : Prop := ∃ i c, r ∈ resQ F (D.Q i c)
/-! ## Commutation of the exact gadgets with resources -/
/-- Circuits commuting with a factor. -/
def CommRes {k : ℕ} (w : Fin k ↪ Fin n) (C : Circuit htcxGateSet n) : Prop :=
∀ h g, (Circuit.unitary C).mulVec (bfac w h g) = bfac w h ((Circuit.unitary C).mulVec g)
variable {D}
/-! ## Supports of resource-dressed symbol states -/
variable (D) in
/-- Resources of gadgets other than `(i, c)`. -/
def OtherRes (i : Fin m) (c : Bool) (L : List (Res n)) : Prop :=
∀ r ∈ L, ∃ i' c', (i, c) ≠ (i', c') ∧ r ∈ resQ F (D.Q i' c')
/-! ## One coordinate of the real decoder -/
variable (D) in
/-- Resources of a coordinate. -/
noncomputable def resC (i : Fin m) : List (Res n) := resQ F (D.Q i false) ++ resQ F (D.Q i true)
variable (D) in
/-- The real operator of a coordinate. -/
noncomputable def actC (i : Fin m) (β : F.F) : Mat n :=
QQ.U (D.Q i true) * QQ.U (D.Q i false) *
Circuit.unitary (eGad (reg := reg) i (D.W i).ZE (D.W i).asE (D.W i).aE (D.W i).fE) *
Circuit.unitary (revCirc (pGad reg (elemBits F) i (D.W i).ZP (D.W i).asP (D.W i).fP (fun x => β - x)))
variable (F b t) in
/-- Error of one `QFT_q` gadget. -/
noncomputable def epsQ : ℝ := (F.f.natDegree : ℝ) * (2 * Real.pi / 2 ^ b + 2 * (F.p / Real.sqrt (2 ^ t)))
lemma resQ_pairwise (Q : QQ n b F t) : (resQ F Q).Pairwise Res.Disj := by
unfold resQ
rw [List.pairwise_map]
refine Q.hpair.imp (fun {G G'} h => ?_)
intro i j e
exact h.2.1 i (Or.inr (Or.inl ⟨j, e.symm⟩))
/-! ## Normalization of the product states -/
/-! ## All coordinates -/
variable (D) in
/-- The real operators of the coordinates in a list, head applied last. -/
noncomputable def actOps (β : Fin m → F.F) : List (Fin m) → Mat n
| [] => 1
| i :: is => actC D i (β i) * actOps β is
/-! ## Decoding probability of the real decoder -/
variable (D) in
/-- All resources. -/
noncomputable def RSall (g : Qubits n → ℂ) : Qubits n → ℂ := bfacL ((List.finRange m).flatMap (resC D)) g
end SymEnc
end OPI
end
-- ===== OPI.TrialCore =====
section
/-!
# The trial of the A-domain Regev reduction, on the register level
The register `R` (embedding `wR`) holds an encoding `enc d` of `d`; the decoder's output register is
read by `out` (a function of the configuration that ignores `R`). The subtraction `R ⊖= O` is a
permutation `σ` that acts only on `R`:
`σ z = setE wR z (sub (z ∘ wR) (out z))`, with `sub (enc d) o = enc 0 ↔ o = d`.
Then, for `Ψ = Σ_d |enc d⟩_R ⊗ φ_d`, the `R = 0` part of `σ Ψ` is `|enc 0⟩_R ⊗ Σ_d P_{out = d} φ_d`.
With `φ_d = U ψ_d` (a decoder `U` acting off `R`) and `U†` afterwards, this is `|enc 0⟩ ⊗ vAcc`.
-/
namespace OPI
open QAlgorithms Matrix
variable {n k : ℕ} {δ : Type*} [DecidableEq δ]
/-- Restriction to configurations whose register `w` holds `y0`. -/
def projReg (w : Fin k ↪ Fin n) (y0 : Qubits k) (f : Qubits n → ℂ) : Qubits n → ℂ :=
fun z => if z ∘ w = y0 then f z else 0
/-- The delta function of a register value. -/
def delta (y0 : Qubits k) : Qubits k → ℂ := fun y => if y = y0 then 1 else 0
section Sub
variable (wR : Fin k ↪ Fin n) (enc : δ → Qubits k) (d0 : δ) (out : Qubits n → δ)
(sub : Qubits k → δ → Qubits k) (subInv : Qubits k → δ → Qubits k)
(hout : ∀ z y, out (setE wR z y) = out z)
(hinv1 : ∀ y o, subInv (sub y o) o = y) (hinv2 : ∀ y o, sub (subInv y o) o = y)
(hzero : ∀ d o, sub (enc d) o = enc d0 ↔ o = d)
/-- The subtraction permutation. -/
noncomputable def subEquiv : Qubits n ≃ Qubits n where
toFun z := setE wR z (sub (z ∘ wR) (out z))
invFun z := setE wR z (subInv (z ∘ wR) (out z))
left_inv z := by
simp only [setE_comp, hout]
rw [hinv1, setE_setE, setE_comp_self]
right_inv z := by
simp only [setE_comp, hout]
rw [hinv2, setE_setE, setE_comp_self]
end Sub
/-! ## Operators acting off the register -/
section Off
variable (wR : Fin k ↪ Fin n)
/-- `U` acts off the register `wR`: it commutes with factorization and with register tests. -/
def OffReg (U : Mat n) : Prop :=
(∀ (h : Qubits k → ℂ) (g : Qubits n → ℂ), U.mulVec (bfac wR h g) = bfac wR h (U.mulVec g)) ∧
∀ (y0 : Qubits k) (f : Qubits n → ℂ), U.mulVec (projReg wR y0 f) = projReg wR y0 (U.mulVec f)
end Off
/-! ## The trial core -/
section Core
variable (wR : Fin k ↪ Fin n) (enc : δ → Qubits k) (d0 : δ) (out : Qubits n → δ)
(sub : Qubits k → δ → Qubits k) (subInv : Qubits k → δ → Qubits k)
(hout : ∀ z y, out (setE wR z y) = out z)
(hinv1 : ∀ y o, subInv (sub y o) o = y) (hinv2 : ∀ y o, sub (subInv y o) o = y)
(hzero : ∀ d o, sub (enc d) o = enc d0 ↔ o = d)
end Core
end OPI
end
-- ===== OPI.OffRegOps =====
section
/-!
# Operators acting off a register
`OffReg w` (commutation with `w`-factorizations and `w`-restrictions) for permutations of
reversible gate lists that avoid `w`, diagonal operators that ignore `w`, and their adjoints. Wire
bounds for the arithmetic builders `incr`, `addInto`, `rdList`, `tauList`, `csList`.
-/
namespace OPI
open QAlgorithms Matrix
variable {N : ℕ}
/-! ## Wire bounds -/
/-! ## `OffReg` closure -/
section Off
variable {k : ℕ} (w : Fin k ↪ Fin N)
end Off
/-! ## Two-sided `OffReg` -/
section Two
variable {n : ℕ} {k : ℕ} (w : Fin k ↪ Fin n)
/-- `U` and `U†` act off `w`. -/
def OffReg2 (U : Mat n) : Prop := OffReg w U ∧ OffReg w Uᴴ
/-- The wires of a `QFT_p` gadget's system unitary. -/
def QG.sysWire {b p ww t : ℕ} (G : QG n b p ww t) (q : Fin n) : Prop :=
q ∈ Set.range G.aE ∨ q ∈ Set.range G.bE ∨ q ∈ Set.range G.cE ∨ q ∈ G.top ∨ q = G.lh ∨
q ∈ G.lrest ∨ q ∈ G.Z ∨ q ∈ G.as ∨ q = G.f
/-- The wires of a `QFT_q` gadget's system unitary. -/
def QQ.sysWire {F : AvgCaseTI.FieldPres} {b t : ℕ} (Q : QQ n b F t) (q : Fin n) : Prop :=
q ∈ Set.range Q.X ∨ q ∈ Q.ZR ∨ q ∈ Q.asR ∨ q = Q.fR ∨ ∃ G ∈ Q.Gs, G.sysWire q
end Two
end OPI
end
-- ===== OPI.Trial =====
section
/-!
# The trial on the program level: readout, the flag test, retries
* `copyCirc`: the Boolean circuit that outputs designated memory slots.
* `measAll`: measure a list of qubits into memory slots; followed by `halt`, its law is
`Σ_z [event (output z)] |f z|²`.
-/
namespace OPI
open QAlgorithms QAlgorithms.OPI Matrix
variable {N c out : ℕ}
/-! ## Output circuits -/
/-- Output memory slot `slot j` as output bit `j`. -/
def copyCirc (slot : Fin out → Fin c) : BoolCircuit c out where
gates := []
outputs j := slot j
lemma copyCirc_wf (slot : Fin out → Fin c) : (copyCirc slot).WellFormed := by
refine ⟨fun k => k.elim0, fun j => ?_⟩
simp [copyCirc]
/-! ## Measuring a register -/
/-- Measure each qubit into its memory slot. -/
def measAll : List (Fin N × Fin c) → Prog N c out → Prog N c out
| [], P => P
| (q, d) :: L, P => .measure q d fun _ => measAll L P
/-- The memory after the measurements of `L` on configuration `z`. -/
def writeMem : List (Fin N × Fin c) → Qubits N → (Fin c → Bool) → Fin c → Bool
| [], _, mem => mem
| (q, d) :: L, z, mem => writeMem L z (Function.update mem d (z q))
/-- The readout list: output bit `j` is the measurement of qubit `qOf j` into slot `slot j`. -/
def readList (qOf : Fin out → Fin N) (slot : Fin out → Fin c) : List (Fin N × Fin c) :=
List.ofFn fun j => (qOf j, slot j)
/-! ## Retries -/
/-- `k` trials, then `fail`; `T P` is a trial that continues with `P` on rejection. -/
def retry (T : Prog N c out → Prog N c out) : ℕ → Prog N c out
| 0 => .fail
| k + 1 => T (retry T k)
/-! ## Measurements on the system part of the layout -/
/-! ## Resetting the whole system register -/
/-- All system wires of the layout `n + b`. -/
def sysWires (n b : ℕ) : List (Fin (n + b)) := (List.finRange n).map (Fin.castAdd b)
/-- The all-zero system state. -/
def sysZero (n : ℕ) : Qubits n → ℂ := fun z => if z = fun _ => false then 1 else 0
variable {n b : ℕ}
/-! ## The zero test -/
/-- Measure the wires `qs` one by one; on the first `1` continue with `Rj`, and if all are `0`
continue with `A`. -/
def zeroTest (dz : Fin c) : List (Fin N) → Prog N c out → Prog N c out → Prog N c out
| [], A, _ => A
| q :: qs, A, Rj => .measure q dz fun β => if β then Rj else zeroTest dz qs A Rj
/-- Restriction to configurations where the wires `qs` are `0`. -/
def zeroPart (qs : List (Fin n)) (φ : Qubits n → ℂ) : Qubits n → ℂ :=
fun z => if ∀ a ∈ qs, z a = false then φ z else 0
/-! ## The gradient register is normalized -/
/-! ## The trial middle: decoder, subtraction, inverse decoder, zero test -/
section Middle
variable {k : ℕ} {δ : Type*} [DecidableEq δ]
(wR : Fin k ↪ Fin n) (enc : δ → Qubits k) (d0 : δ) (out' : Qubits n → δ)
(sub : Qubits k → δ → Qubits k) (subInv : Qubits k → δ → Qubits k)
(hout : ∀ z y, out' (setE wR z y) = out' z)
(hinv1 : ∀ y o, subInv (sub y o) o = y) (hinv2 : ∀ y o, sub (subInv y o) o = y)
(hzero : ∀ d o, sub (enc d) o = enc d0 ↔ o = d) (henc0 : enc d0 = fun _ => false)
end Middle
/-! ## Numerics of the retry loop -/
/-! ## The trial loop -/
/-- One trial: the preparation `pre`, the middle circuit, and the zero test with readout on
acceptance and reset-and-continue on rejection. -/
def trialStep (pre : Prog (n + b) c out → Prog (n + b) c out) (C : Circuit htcxGateSet (n + b))
(dz : Fin c) (Rw : List (Fin n)) (Acc : Prog (n + b) c out) (P : Prog (n + b) c out) :
Prog (n + b) c out :=
pre ((circSeg C).prog (zeroTest dz (Rw.map (Fin.castAdd b)) Acc (resets (sysWires n b) P)))
section Loop
variable {k : ℕ} {δ : Type*} [DecidableEq δ]
(wR : Fin k ↪ Fin n) (enc : δ → Qubits k) (d0 : δ) (out' : Qubits n → δ)
(sub : Qubits k → δ → Qubits k) (subInv : Qubits k → δ → Qubits k)
(hout : ∀ z y, out' (setE wR z y) = out' z)
(hinv1 : ∀ y o, subInv (sub y o) o = y) (hinv2 : ∀ y o, sub (subInv y o) o = y)
(hzero : ∀ d o, sub (enc d) o = enc d0 ↔ o = d) (henc0 : enc d0 = fun _ => false)
end Loop
end OPI
end
-- ===== OPI.CatComm =====
section
/-!
# Catalysed operators commute with states on registers they avoid
If `C` implements `U` on clean states (`Cat cl C U`) and the gates of `C` avoid the register `w`,
then `U (h ⊗_w g) = h ⊗_w (U g)` (for `g`, `h ⊗_w g` clean).
-/
namespace OPI
open QAlgorithms Matrix
variable {n b k : ℕ}
end OPI
namespace OPI
open QAlgorithms Matrix
variable {n : ℕ}
/-- The clean subspace. -/
def cleanSub (cl : List (Fin n)) : Submodule ℂ (Qubits n → ℂ) where
carrier := {ψ | ∀ x, ψ x ≠ 0 → ∀ a ∈ cl, x a = false}
add_mem' := by
intro f g hf hg x hx
by_cases h : f x = 0
· exact hg x (by simpa [h] using hx)
· exact hf x h
zero_mem' := by intro x hx; simp at hx
smul_mem' := by
intro c f hf x hx
exact hf x (fun h => hx (by simp [h]))
end OPI
end
-- ===== OPI.DecFull =====
section
/-!
# The full decoder: `Cat`, `PresClean`, `OffReg`
The decoder circuit applies, coordinate by coordinate, `P_β`, `E`, `QFT_q` on `S_i` and on `T_i`,
and finally the compiled classical decoder. All `QFT_q` gadgets share their clean scratch `clQ`.
-/
namespace OPI
open QAlgorithms Matrix
variable {N : ℕ}
/-! ## Wires of compiled straight-line programs -/
namespace SymEnc
open TwoFoldOPI
variable {F : AvgCaseTI.FieldPres} {n b t m : ℕ}
{reg : Fin m × Bool × Fin (bitsPerSymbol F) ↪ Fin n}
/-- Wires of the `E` and `P_β` gadgets of a coordinate (including its symbol registers). -/
def epAll {i : Fin m} (W : CoordWires F reg i) (q : Fin n) : Prop :=
epWire F W q ∨ q ∈ List.ofFn (bReg reg i false) ∨ q ∈ List.ofFn (bReg reg i true)
/-- **The full decoder layout.** -/
structure DecFull (F : AvgCaseTI.FieldPres) (reg : Fin m × Bool × Fin (bitsPerSymbol F) ↪ Fin n)
(b t k k2 kR : ℕ) where
D : RealDec F reg b t
C : ClsLay reg (elemBits F) (decodeElem F) (Fq.decode_elemBits F) k k2
clQ : List (Fin n)
hclQ : ∀ i c, (D.Q i c).cl = clQ
wR : Fin kR ↪ Fin n
hep : ∀ i q, epAll (D.W i) q → q ∉ clQ ∧ q ∉ Set.range wR
hqR : ∀ i c q, (D.Q i c).sysWire q → q ∉ Set.range wR
hcls : ∀ q, ((∃ x < nIds m k k2, q ∈ C.rs x) ∨ q ∈ C.as ∨ q = C.f0) → q ∉ clQ ∧ q ∉ Set.range wR
variable {k k2 kR : ℕ} (X : DecFull F reg b t k k2 kR)
/-- The circuit of one coordinate. -/
noncomputable def DecFull.cCirc (i : Fin m) (β : F.F) : Circuit htcxGateSet (n + b) :=
relocCirc sysEmb (revCirc (pGad reg (elemBits F) i (X.D.W i).ZP (X.D.W i).asP (X.D.W i).fP
(fun x => β - x))) ++
relocCirc sysEmb (eGad (reg := reg) i (X.D.W i).ZE (X.D.W i).asE (X.D.W i).aE (X.D.W i).fE) ++
(X.D.Q i false).circ ++ (X.D.Q i true).circ
/-- The circuits of a list of coordinates, head last. -/
noncomputable def DecFull.dCirc (β : Fin m → F.F) : List (Fin m) → Circuit htcxGateSet (n + b)
| [] => []
| i :: is => DecFull.dCirc β is ++ X.cCirc i (β i)
/-- The full decoder circuit. -/
noncomputable def DecFull.circ (β : Fin m → F.F) (bD : Fin k → Fin m → F.F) (bW : Fin k2 → Fin m → F.F) :
Circuit htcxGateSet (n + b) :=
X.dCirc β (List.finRange m) ++ relocCirc sysEmb (revCirc (clsGates X.C bD bW))
/-- The system unitary of the decoder. -/
noncomputable def DecFull.U (β : Fin m → F.F) (bD : Fin k → Fin m → F.F) (bW : Fin k2 → Fin m → F.F) :
Mat n :=
Circuit.unitary (revCirc (clsGates X.C bD bW)) * actOps X.D β (List.finRange m)
end SymEnc
end OPI
end
-- ===== OPI.RSub =====
section
/-!
# The register `R` and the subtraction `R ⊖= O`
`R` holds a word `d ∈ K^m`, block `i` (bits `fPF (i, ·)`) encoding `d_i` by `elemBits`.
The subtraction acts blockwise: a valid block `y_i` becomes `y_i − o_i`; invalid blocks are kept.
-/
namespace OPI
namespace SymEnc
open QAlgorithms TwoFoldOPI
variable (F : AvgCaseTI.FieldPres) (m : ℕ)
set_option hygiene false in
local notation "L" => bitsPerSymbol F
/-- Block `i` of a register of `m` symbols. -/
def blk (y : Qubits (m * L)) (i : Fin m) : Qubits L := fun j => y (finProdFinEquiv (i, j))
/-- Assemble blocks. -/
def unblk (v : Fin m → Qubits L) : Qubits (m * L) := fun x =>
v (finProdFinEquiv.symm x).1 (finProdFinEquiv.symm x).2
/-- The encoding of a word. -/
noncomputable def encW (d : Fin m → F.F) : Qubits (m * L) := unblk F m fun i => elemBits F (d i)
open Classical in
/-- Blockwise shift by `±o` on valid blocks. -/
noncomputable def shiftW (s : F.F) (y : Qubits (m * L)) (o : Fin m → F.F) : Qubits (m * L) :=
unblk F m fun i => if Fq.Valid F (blk F m y i) then elemBits F (decodeElem F (blk F m y i) + s * o i)
else blk F m y i
/-! ## The subtraction circuit -/
/-- Bits as a symbol register value. -/
def toQ (bs : List Bool) : Qubits L := fun j => bs.getD j false
open Classical in
/-- Shift an encoded symbol by `s · dec c`. -/
noncomputable def fShift (s : F.F) (c B : List Bool) : List Bool :=
if Fq.Valid F (toQ F B) then List.ofFn (elemBits F (decodeElem F (toQ F B) + s * decodeElem F (toQ F c)))
else B
variable {F m} {n : ℕ}
/-- The subtraction gadget of coordinate `i`. -/
noncomputable def subGad (Os : List (Fin n)) (Ri : Fin L ↪ Fin n) (Z as : List (Fin n)) (f : Fin n) :
List (RGate n) :=
permGad Os (List.ofFn Ri) Z as f (fShift F (-1)) (fShift F 1)
/-! ## All coordinates -/
section All
variable (Rr : Fin m → (Fin L ↪ Fin n))
(hRd : ∀ i i' j j', Rr i j = Rr i' j' → i = i' ∧ j = j')
/-- The register `R` as one embedding. -/
def wRof : Fin (m * L) ↪ Fin n :=
⟨fun x => Rr (finProdFinEquiv.symm x).1 (finProdFinEquiv.symm x).2, fun x x' h => by
obtain ⟨h1, h2⟩ := hRd _ _ _ _ h
exact finProdFinEquiv.symm.injective (Prod.ext h1 h2)⟩
/-- The decoded output word. -/
noncomputable def outOf (Os : Fin m → List (Fin n)) (z : Qubits n) : Fin m → F.F :=
fun i => decodeElem F (toQ F ((Os i).map z))
/-- The subtraction circuit. -/
noncomputable def subAll (Rr : Fin m → (Fin L ↪ Fin n)) (Os : Fin m → List (Fin n)) (Z as : List (Fin n))
(f : Fin n) (is : List (Fin m)) : List (RGate n) :=
is.flatMap fun i => subGad (F := F) (Os i) (Rr i) Z as f
variable (Os : Fin m → List (Fin n)) (Z as : List (Fin n)) (f : Fin n)
variable (hnd : ∀ i, (Os i ++ List.ofFn (Rr i) ++ Z ++ as ++ [f]).Nodup) (hZ : L = Z.length)
(hlen : ∀ i, (Os i).length + L ≤ as.length + 2)
(hOs : ∀ i i' j, ∀ q ∈ Os i', Rr i j ≠ q)
(hsc : ∀ i j, Rr i j ≠ f ∧ (∀ q ∈ Z, Rr i j ≠ q) ∧ ∀ q ∈ as, Rr i j ≠ q)
end All
/-! ## Reversible circuits agreeing with a permutation on clean configurations -/
end SymEnc
end OPI
end
-- ===== OPI.PrepR =====
section
/-!
# Preparing `Σ_{d ∈ D} |d⟩` in the register `R`
`G` is a basis of `D` in reduced row-echelon form with pivots `piv` (`G j (piv j') = [j = j']`).
After the pivot symbols of `R` hold a uniformly random `a ∈ K^k` (repeat-until-success), the shifts
`R_i += G_{j i} · R_{piv j}` (non-pivot `i`) produce `R = a G`.
-/
namespace OPI
namespace SymEnc
open QAlgorithms TwoFoldOPI
variable {F : AvgCaseTI.FieldPres} {n : ℕ}
set_option hygiene false in
local notation "L" => bitsPerSymbol F
/-- The shift gadget `R_i += s · dec (c)`. -/
noncomputable def shGad (s : F.F) (Os : List (Fin n)) (Ri : Fin L ↪ Fin n) (Z as : List (Fin n)) (f : Fin n) :
List (RGate n) :=
permGad Os (List.ofFn Ri) Z as f (fShift F s) (fShift F (-s))
/-! ## The linear map `R_i += Σ_j G_{j i} R_{piv j}` -/
section Lin
variable {m kd : ℕ} (G : Fin kd → Fin m → F.F) (piv : Fin kd → Fin m)
(Rr : Fin m → (Fin L ↪ Fin n)) (hRd : ∀ i i' j j', Rr i j = Rr i' j' → i = i' ∧ j = j')
(Z as : List (Fin n)) (f : Fin n)
/-- The shift of one pair `(j, i)`. -/
noncomputable def linGad (p : Fin kd × Fin m) : List (RGate n) :=
shGad (G p.1 p.2) (List.ofFn (Rr (piv p.1))) (Rr p.2) Z as f
/-- Effect of a list of shifts on a word. -/
noncomputable def linWord (ps : List (Fin kd × Fin m)) (v : Fin m → F.F) : Fin m → F.F :=
ps.foldl (fun v p => Function.update v p.2 (v p.2 + G p.1 p.2 * v (piv p.1))) v
variable (hnd : ∀ p : Fin kd × Fin m, (∀ j', piv j' ≠ p.2) → (List.ofFn (Rr (piv p.1)) ++ List.ofFn (Rr p.2) ++ Z ++ as ++ [f]).Nodup)
(hZ : L = Z.length) (hlen : L + L ≤ as.length + 2)
(hsc : ∀ i j, Rr i j ≠ f ∧ (∀ q ∈ Z, Rr i j ≠ q) ∧ ∀ q ∈ as, Rr i j ≠ q)
open Classical in
/-- The shift pairs: every row `j`, every non-pivot column `i`. -/
noncomputable def linPairs : List (Fin kd × Fin m) :=
(List.finRange kd).flatMap fun j =>
((List.finRange m).filter fun i => ∀ j', piv j' ≠ i).map fun i => (j, i)
end Lin
end SymEnc
end OPI
end
-- ===== OPI.Prep =====
section
/-!
# Preparation laws
`PreLaw pre f f' w e`: running `pre P` from `f` yields at least `w · K − e` whenever `P` yields at
least `K` from `f'`. Composition, circuits, repeat-until-success, scaling, perturbation.
-/
namespace OPI
open QAlgorithms Matrix
variable {N c out : ℕ} (event : Option (Fin out → Bool) → Prop)
/-- A preparation law. -/
def PreLaw (pre : Prog N c out → Prog N c out) (f f' : Qubits N → ℂ) (w e : ℝ) : Prop :=
∀ P K, (∀ mem, K ≤ lawP P event f' mem) → ∀ mem, w * K - e ≤ lawP (pre P) event f mem
variable {event}
end OPI
namespace OPI
open QAlgorithms
variable {N c out : ℕ} {event : Option (Fin out → Bool) → Prop}
end OPI
end
-- ===== OPI.PrepState =====
section
/-!
# States of the preparation
* `rusOut_eq_bfac`: a repeat-until-success output is a factorized state on its register;
* `perm_bfac_delta`: a permutation that moves basis words of a register moves factorized states;
* `bfac_sum_delta`: a factor on a register is the sum of its basis words.
-/
namespace OPI
open QAlgorithms
variable {N : ℕ}
/-! ## The uniform pivot state -/
namespace SymEnc
open TwoFoldOPI
variable {F : AvgCaseTI.FieldPres} {n m kd : ℕ}
set_option hygiene false in
local notation "L" => bitsPerSymbol F
variable (Rr : Fin m → (Fin L ↪ Fin n)) (hRd : ∀ i i' j j', Rr i j = Rr i' j' → i = i' ∧ j = j')
(piv : Fin kd → Fin m) (hpivi : Function.Injective piv)
open Classical in
/-- The word with pivot values `a` and zeros elsewhere. -/
noncomputable def vPiv (a : Fin kd → F.F) : Fin m → F.F :=
fun i => if h : ∃ j, piv j = i then a (Classical.choose h) else 0
/-- The pivot registers with a factor `h` each. -/
noncomputable def pivRes (h : Qubits L → ℂ) : List (Res n) :=
(List.finRange kd).map fun j => (⟨L, Rr (piv j), h⟩ : Res n)
/-! ## The linear map on basis words -/
section LinBasis
variable (G : Fin kd → Fin m → F.F) (hpiv : ∀ j j', G j (piv j') = if j = j' then 1 else 0)
(Z as : List (Fin n)) (f : Fin n)
(hnd : ∀ p : Fin kd × Fin m, (∀ j', piv j' ≠ p.2) → (List.ofFn (Rr (piv p.1)) ++ List.ofFn (Rr p.2) ++ Z ++ as ++ [f]).Nodup)
(hZ : L = Z.length) (hlen : L + L ≤ as.length + 2)
(hsc : ∀ i j, Rr i j ≠ f ∧ (∀ q ∈ Z, Rr i j ≠ q) ∧ ∀ q ∈ as, Rr i j ≠ q)
/-- Clean scratch. -/
def scrClean (z : Qubits n) : Prop := z f = false ∧ (∀ q ∈ as, z q = false) ∧ ∀ q ∈ Z, z q = false
/-- The linear-map circuit. -/
noncomputable def linCirc : List (RGate n) := (linPairs piv).flatMap (linGad G piv Rr Z as f)
end LinBasis
end SymEnc
end OPI
end
-- ===== OPI.PrepPhase =====
section
/-!
# The phase `Z^d` on `(R_i, S_i)`
The table `(r, s) ↦ ⌊2^b · tr(r s)/p⌋` on `L + L` bits, with kickback into the gradient register, is
within `2π/2^b` of `ψ(r s) = ω_p^{tr(r s)}` on encoded symbols.
-/
namespace OPI
namespace SymEnc
open QAlgorithms TwoFoldOPI
variable (F : AvgCaseTI.FieldPres) (b : ℕ)
set_option hygiene false in
local notation "L" => bitsPerSymbol F
/-- The phase table of one coordinate. -/
noncomputable def zTab : List (List Bool × List Bool) :=
funTable (L + L) fun pat =>
natBits b (2 ^ b * (Fq.tr F (decodeElem F (toQ F (pat.take L)) * decodeElem F (toQ F (pat.drop L)))).val / F.p)
end SymEnc
end OPI
namespace OPI
open QAlgorithms Matrix
variable {n : ℕ}
end OPI
end
-- ===== OPI.PrepChain =====
section
/-!
# Chains of repeat-until-success stages
`rusChain js` runs one repeat-until-success stage per job (register, membership test); on a state
clean on all job registers and the shared flag/ancillas it prepares `bfacL (js.map res) f`.
-/
namespace OPI
open QAlgorithms
variable {n b c out : ℕ} {event : Option (Fin out → Bool) → Prop}
/-- A repeat-until-success job. -/
structure RJob (n : ℕ) where
k : ℕ
w : Fin k ↪ Fin n
memT : List Bool → Bool
/-- The factor a job prepares. -/
noncomputable def RJob.res (j : RJob n) : Res n :=
⟨j.k, j.w, fun v => if j.memT (List.ofFn v) then ((Real.sqrt 2 : ℂ))⁻¹ ^ j.k else 0⟩
/-- The chain of stages, head first. -/
noncomputable def rusChain (fl f0 : Fin n) (as : List (Fin n)) (dst : Fin c) (R : ℕ) :
List (RJob n) → Prog (n + b) c out → Prog (n + b) c out
| [], P => P
| j :: js, P => rusProg (List.ofFn (j.w.trans (sysEmb (b := b)))) (Fin.castAdd b fl) (Fin.castAdd b f0)
(as.map (Fin.castAdd b)) j.memT dst R (rusChain fl f0 as dst R js P)
/-- The weight of a chain. -/
noncomputable def RJob.wt (j : RJob n) (R : ℕ) : ℝ :=
∑ t ∈ Finset.range R, rusFail (List.ofFn (j.w.trans (sysEmb (b := b)))) j.memT ^ t
end OPI
end
-- ===== OPI.PrepJ =====
section
/-!
# Symbol registers prepared factor by factor are `J`-states
If each `S_i` carries a factor `h_i` supported on encodings and everything else is `0`, the state is
`J (⊗_i (h_i ∘ enc) ⊗ δ₀)`.
-/
namespace OPI
namespace SymEnc
open QAlgorithms TwoFoldOPI
variable {F : AvgCaseTI.FieldPres} {n m : ℕ} (reg : Fin m × Bool × Fin (bitsPerSymbol F) ↪ Fin n)
/-- Factors on the `S` registers. -/
noncomputable def sRes (h : Fin m → Qubits (bitsPerSymbol F) → ℂ) : List (Res n) :=
(List.finRange m).map fun i => (⟨bitsPerSymbol F, bReg reg i false, h i⟩ : Res n)
/-- The product state of `S`-factors and `T = 0`. -/
noncomputable def sProd (h : Fin m → Qubits (bitsPerSymbol F) → ℂ) : Fin m → F.F × F.F → ℂ :=
fun i w => if w.2 = 0 then h i (elemBits F w.1) else 0
end SymEnc
end OPI
end
-- ===== OPI.PrepZ =====
section
/-!
# The ideal phase on the prepared state
`Dideal_d z = Π_i ψ(d_i · dec(z_{S_i}))` maps `J (⊗ aState ⊗ δ₀)` to `J (⊗ Z^{d_i} aState ⊗ δ₀)`;
it commutes with factors on other registers.
-/
namespace OPI
namespace SymEnc
open QAlgorithms TwoFoldOPI CoordSym
variable {F : AvgCaseTI.FieldPres} {n m : ℕ} (reg : Fin m × Bool × Fin (bitsPerSymbol F) ↪ Fin n)
/-- The ideal phase of a word `d` on the `S` registers. -/
noncomputable def phS (d : Fin m → F.F) (z : Qubits n) : ℂ :=
∏ i, Fq.ψ F (d i * decodeElem F (z ∘ bReg reg i false))
/-- The unphased pair states. -/
noncomputable def gA (β : Fin m → F.F) : Fin m → F.F × F.F → ℂ :=
fun i => withZero F (aState F (β i))
/-! ## The phase on `R ⊗ S` -/
section RS
set_option hygiene false in
local notation "L" => bitsPerSymbol F
variable (Rr : Fin m → (Fin L ↪ Fin n)) (hRd : ∀ i i' j j', Rr i j = Rr i' j' → i = i' ∧ j = j')
/-- The ideal phase `Π_i ψ(dec R_i · dec S_i)`. -/
noncomputable def phRS (z : Qubits n) : ℂ :=
∏ i, Fq.ψ F (decodeElem F (z ∘ Rr i) * decodeElem F (z ∘ bReg reg i false))
/-- The real phase of the table circuits. -/
noncomputable def phReal (b : ℕ) {N' : ℕ} (scr : List (Fin N')) (z : Qubits n) : ℂ :=
∏ i, kickPhase b (tableNat scr (zTab F b) (List.ofFn (z ∘ Rr i) ++ List.ofFn (z ∘ bReg reg i false)))
/-! ## The phase circuit -/
variable {b : ℕ} (scr as : List (Fin n)) (f : Fin n)
/-- The table-phase gates of one coordinate. -/
noncomputable def tpg (i : Fin m) : List (RGate (n + b)) :=
tablePhaseGates (List.ofFn (Rr i) ++ List.ofFn (bReg reg i false)) scr as f (zTab F b)
/-- The phase circuit for a list of coordinates. -/
noncomputable def phCirc : List (Fin m) → Circuit htcxGateSet (n + b)
| [] => []
| i :: is => phCirc is ++ revCirc (tpg reg Rr (b := b) scr as f i)
variable (hsl : scr.length = b) (hbl : 1 + b ≤ as.length + 2) (hxl : L + L ≤ as.length + 2)
(hnd : ∀ i, (List.ofFn (Rr i) ++ List.ofFn (bReg reg i false) ++ scr ++ as ++ [f]).Nodup)
end RS
end SymEnc
end OPI
end
-- ===== OPI.PrepJobs =====
section
/-!
# The repeat-until-success jobs of the preparation and their factors
Up to explicit scalars, the factors are `aState β_i` on `S_i` (via `elemBits`), `|u_p⟩` on the
resource registers, and the uniform valid symbol on the pivot registers.
-/
namespace OPI
open QAlgorithms TwoFoldOPI
variable {n : ℕ}
/-- Scale the factors of a list. -/
def Res.scale (c : Res n → ℂ) (r : Res n) : Res n := ⟨r.k, r.w, fun v => c r * r.h v⟩
end OPI
namespace OPI
namespace SymEnc
open QAlgorithms TwoFoldOPI CoordSym
variable {F : AvgCaseTI.FieldPres} {n m : ℕ}
set_option hygiene false in
local notation "L" => bitsPerSymbol F
open Classical in
/-- The repeat-until-success job of `S_i`: valid and `≠ β_i`. -/
noncomputable def sJob (reg : Fin m × Bool × Fin L ↪ Fin n) (β : Fin m → F.F) (i : Fin m) : RJob n :=
⟨L, bReg reg i false, fun bits => decide (Fq.Valid F (toQ F bits) ∧ decodeElem F (toQ F bits) ≠ β i)⟩
open Classical in
/-- The unnormalized `aState` factor on encodings. -/
noncomputable def hA (β : Fin m → F.F) (i : Fin m) (v : Qubits L) : ℂ :=
if Fq.Valid F v then aState F (β i) (decodeElem F v) else 0
/-- The scalar of the `S` jobs. -/
noncomputable def cS (F : AvgCaseTI.FieldPres) : ℂ :=
((Real.sqrt 2 : ℂ))⁻¹ ^ bitsPerSymbol F * (Real.sqrt ((Fintype.card F.F : ℝ) - 1) : ℂ)
open Classical in
/-- The repeat-until-success job of a resource register: value `< p`. -/
noncomputable def rJob (F : AvgCaseTI.FieldPres) (r : Res n) : RJob n :=
⟨r.k, r.w, fun bits => decide (bitsVal bits < F.p)⟩
/-- The scalar of a resource job. -/
noncomputable def cR (F : AvgCaseTI.FieldPres) (k : ℕ) : ℂ :=
((Real.sqrt 2 : ℂ))⁻¹ ^ k * (Real.sqrt F.p : ℂ)
end SymEnc
end OPI
end
-- ===== OPI.PrepAll =====
section
/-!
# The state after the repeat-until-success stages
The jobs run pivots, then resources, then `S`; the state is, up to an explicit scalar,
`Σ_a |vPiv a⟩_R ⊗ RSall (J (⊗ gA β))`.
-/
namespace OPI
open QAlgorithms TwoFoldOPI
variable {n : ℕ}
/-- `g` vanishes unless wire `q` is clear. -/
def OffW (g : Qubits n → ℂ) (q : Fin n) : Prop := ∀ z, g z ≠ 0 → z q = false
namespace SymEnc
variable {F : AvgCaseTI.FieldPres} {m kd : ℕ}
set_option hygiene false in
local notation "L" => bitsPerSymbol F
open Classical in
/-- The repeat-until-success job of a pivot register: valid. -/
noncomputable def pJob (Rr : Fin m → (Fin L ↪ Fin n)) (piv : Fin kd → Fin m) (j : Fin kd) : RJob n :=
⟨L, Rr (piv j), fun bits => decide (Fq.Valid F (toQ F bits))⟩
section RusState
variable {b t : ℕ} {reg : Fin m × Bool × Fin L ↪ Fin n} (D : RealDec F reg b t)
/-- All resource factors. -/
noncomputable def resAll : List (Res n) := (List.finRange m).flatMap (resC D)
/-- All jobs: pivots, then resources, then `S`. -/
noncomputable def allJobs (Rr : Fin m → (Fin L ↪ Fin n)) (piv : Fin kd → Fin m) (β : Fin m → F.F) :
List (RJob n) :=
(List.finRange kd).map (pJob Rr piv) ++ (resAll D).map (rJob F) ++ (List.finRange m).map (sJob reg β)
/-- The scalar of all jobs. -/
noncomputable def cAll (kd : ℕ) : ℂ :=
(((Real.sqrt 2 : ℂ))⁻¹ ^ L) ^ kd * ((resAll D).map fun r => cR F r.k).prod * cS F ^ m
end RusState
end SymEnc
end OPI
end
-- ===== OPI.PrepStages =====
section
/-!
# The linear-map and phase stages of the preparation, and the reindexing onto `D`
-/
namespace OPI
open QAlgorithms TwoFoldOPI
variable {n b : ℕ}
/-- Splitting the layout `n + b`. -/
def splitNB : Qubits n × Qubits b ≃ Qubits (n + b) :=
(Equiv.sumArrowEquivProdArrow (Fin n) (Fin b) Bool).symm.trans
(Equiv.arrowCongr finSumFinEquiv (Equiv.refl Bool))
namespace SymEnc
variable {F : AvgCaseTI.FieldPres} {m kd : ℕ}
set_option hygiene false in
local notation "L" => bitsPerSymbol F
section Stages
variable {t : ℕ} {reg : Fin m × Bool × Fin L ↪ Fin n} (D : RealDec F reg b t)
(Rr : Fin m → (Fin L ↪ Fin n)) (hRd : ∀ i i' j j', Rr i j = Rr i' j' → i = i' ∧ j = j')
(piv : Fin kd → Fin m) (hpivi : Function.Injective piv)
/-- `g` vanishes unless the listed wires are clear. -/
def OffL (g : Qubits n → ℂ) (qs : List (Fin n)) : Prop := ∀ q ∈ qs, OffW g q
/-- The unphased inner state. -/
noncomputable def Y0 (β : Fin m → F.F) : Qubits n → ℂ := RSall D (J reg (elemBits F) (prodF (gA β)))
end Stages
end SymEnc
end OPI
end
-- ===== OPI.PrepNorm =====
section
/-!
# Normalization facts for the prepared state, and the reindexing onto `D`
-/
namespace OPI
open QAlgorithms TwoFoldOPI
variable {n : ℕ}
namespace SymEnc
variable {F : AvgCaseTI.FieldPres} {m kd b t : ℕ}
set_option hygiene false in
local notation "L" => bitsPerSymbol F
section Norm
variable {reg : Fin m × Bool × Fin L ↪ Fin n} (D : RealDec F reg b t)
lemma resAll_pairwise : (resAll D).Pairwise Res.Disj := by
unfold resAll
rw [List.pairwise_flatMap]
refine ⟨fun i _ => ?_, ?_⟩
· unfold resC
rw [List.pairwise_append]
exact ⟨resQ_pairwise _, resQ_pairwise _, fun r hr r' hr' =>
D.hres i false i true (by simp) r hr r' hr'⟩
· refine (List.nodup_finRange m).pairwise_of_forall_ne (fun i _ i' _ hii r hr r' hr' => ?_)
simp only [resC, List.mem_append] at hr hr'
rcases hr with hr | hr <;> rcases hr' with hr' | hr' <;>
exact D.hres _ _ _ _ (by simp [hii]) r hr r' hr'
end Norm
end SymEnc
end OPI
end
-- ===== OPI.PrepLaw =====
section
/-!
# The full preparation law
From `|0⟩ ⊗ grad` the preparation (repeat-until-success stages, the linear map `R ↦ R G`, the table
phase) reaches, with weight `W · |cAll|² |D|` and phase error `2 m (2π / 2^b)` times that weight,
`Σ_{d ∈ D} |d⟩_R ⊗ ψ_d ⊗ grad` with `ψ_d = |D|^{-1/2} RSall (J (⊗ g0 β d))`.
-/
namespace OPI
open QAlgorithms TwoFoldOPI
variable {n b : ℕ}
namespace SymEnc
variable {F : AvgCaseTI.FieldPres} {m t : ℕ}
set_option hygiene false in
local notation "L" => bitsPerSymbol F
/-- **The layout of the preparation.** -/
structure PrepLay {reg : Fin m × Bool × Fin L ↪ Fin n} (D : RealDec F reg b t) (kd : ℕ) where
Rr : Fin m → (Fin L ↪ Fin n)
hRd : ∀ i i' j j', Rr i j = Rr i' j' → i = i' ∧ j = j'
piv : Fin kd → Fin m
hpivi : Function.Injective piv
G : Fin kd → Fin m → F.F
hpiv : ∀ j j', G j (piv j') = if j = j' then 1 else 0
fl : Fin n
f0 : Fin n
asR : List (Fin n)
Z : List (Fin n)
asL : List (Fin n)
fL : Fin n
scr : List (Fin n)
asP : List (Fin n)
fP : Fin n
hRreg : ∀ i j p, reg p ≠ Rr i j
hRres : ∀ r ∈ resAll D, ∀ i j, Rr i j ∉ Set.range r.w
hjob : ∀ β, ∀ j ∈ allJobs D Rr piv β, (List.ofFn j.w ++ [fl] ++ asR ++ [f0]).Nodup ∧ j.k ≤ asR.length + 2
hjpair : ∀ β, ((allJobs D Rr piv β).map RJob.res).Pairwise Res.Disj
hndL : ∀ p : Fin kd × Fin m, (∀ j', piv j' ≠ p.2) → (List.ofFn (Rr (piv p.1)) ++ List.ofFn (Rr p.2) ++ Z ++ asL ++ [fL]).Nodup
hZ : L = Z.length
hlenL : L + L ≤ asL.length + 2
hscL : ∀ i j, Rr i j ≠ fL ∧ (∀ q ∈ Z, Rr i j ≠ q) ∧ ∀ q ∈ asL, Rr i j ≠ q
hLoff : ∀ q ∈ fL :: asL ++ Z, (∀ p, reg p ≠ q) ∧ ∀ r ∈ resAll D, q ∉ Set.range r.w
hsl : scr.length = b
hscr : scr.Nodup
hbl : 1 + b ≤ asP.length + 2
hxl : L + L ≤ asP.length + 2
hndP : ∀ i, (List.ofFn (Rr i) ++ List.ofFn (bReg reg i false) ++ scr ++ asP ++ [fP]).Nodup
hPoff : ∀ q ∈ scr ++ asP ++ [fP], (∀ p, reg p ≠ q) ∧ (∀ r ∈ resAll D, q ∉ Set.range r.w) ∧ ∀ i j, Rr i j ≠ q
variable {reg : Fin m × Bool × Fin L ↪ Fin n} {D : RealDec F reg b t} {kd : ℕ}
/-- The preparation program. -/
noncomputable def PrepLay.pre {c out : ℕ} (X : PrepLay D kd) (β : Fin m → F.F) (dst : Fin c) (R : ℕ)
(P : Prog (n + b) c out) : Prog (n + b) c out :=
rusChain X.fl X.f0 X.asR dst R (allJobs D X.Rr X.piv β)
((circSeg (relocCirc sysEmb (revCirc (linCirc X.Rr X.piv X.G X.Z X.asL X.fL)))).prog
((circSeg (phCirc reg X.Rr (b := b) X.scr X.asP X.fP (List.finRange m))).prog P))
/-- The weight of the repeat-until-success stages. -/
noncomputable def PrepLay.W (X : PrepLay D kd) (β : Fin m → F.F) (R : ℕ) : ℝ :=
((allJobs D X.Rr X.piv β).map fun j => RJob.wt (b := b) j R).prod
/-- The normalized target states. -/
noncomputable def psiN (D : RealDec F reg b t) (Ds : Finset (Fin m → F.F)) (β d : Fin m → F.F) : Qubits n → ℂ :=
((Real.sqrt Ds.card)⁻¹ : ℂ) • RSall D (J reg (elemBits F) (prodF (g0 (F := F) β d)))
end SymEnc
end OPI
end
-- ===== OPI.SerI =====
section
/-!
# First-order nodes for the serializer
Every node code of `programNodeTable` has the form `serializeWords (tag :: fields ++ rs)`, where
`rs` are the table indices of the children. A node is therefore represented by the first-order
triple `(tag, fields, children)` (`INode`), and the memoized traversal `trav` is computed by the
uniform traversal `travI` on such triples.
-/
namespace OPI
open QAlgorithms QAlgorithms.OPI QAlgorithms.Complexity
/-- A first-order node: tag, fields, children (DAG indices). -/
abbrev INode := ℕ × List ℕ × List ℕ
/-- The code of a node whose children have table indices `rs`. -/
def codeI (nd : INode) (rs : List ℕ) : Str := serializeWords (nd.1 :: (nd.2.1 ++ rs))
/-- The node read at a missing index. -/
def failI : INode := (1, [], [])
lemma serializeWords_append (a b : List ℕ) :
serializeWords (a ++ b) = serializeWords a ++ serializeWords b := by
simp [serializeWords]
lemma serializeWords_cons (k : ℕ) (a : List ℕ) :
serializeWords (k :: a) = encNat k ++ serializeWords a := by
simp [serializeWords]
@[simp] lemma serializeWords_nil : serializeWords [] = [] := rfl
/-- The uniform memoized traversal. -/
def travI (dag : List INode) (i : ℕ) (memo : ℕ → Option ℕ) (T : List Str) : TravRes :=
match memo i with
| some k => (k, T, memo)
| none =>
let nd := dag[i]?.getD failI
let r : List ℕ × List Str × (ℕ → Option ℕ) := nd.2.2.foldl (fun acc j =>
if j < i then
let t := travI dag j acc.2.2 acc.2.1
(acc.1 ++ [t.1], t.2.1, t.2.2)
else
let u := internProgramNode failCode acc.2.1
(acc.1 ++ [u.1], u.2, acc.2.2)) ([], T, memo)
let res := internProgramNode (codeI nd r.1) r.2.1
(res.1, res.2, Function.update r.2.2 i (some res.1))
termination_by i
decreasing_by all_goals assumption
section ToI
variable {N c out : ℕ}
open Classical in
/-- The first-order form of a node. -/
noncomputable def toI : Node N c out → INode
| .halt D _ => (0, [D.gates.length] ++ D.gates.flatMap (fun g => [Learning.boolOpCode g.op, g.a, g.b]) ++
List.ofFn D.outputs, [])
| .fail => (1, [], [])
| .gate g j => (2, (if g.gate = Gate.ofMatrix1 hadamard then 0
else if g.gate = Gate.ofMatrix1 gateT then 1 else 2) :: List.ofFn (fun i => (g.wires i).val), [j])
| .measure q dst j0 j1 => (4, [q.val, dst.val], [j0, j1])
| .prepare q j => (5, [q.val], [j])
| .coin dst j0 j1 => (6, [dst.val], [j0, j1])
| .setBit dst b j => (7, [dst.val, if b then 1 else 0], [j])
| .boolean op dst x y j => (8, [Learning.boolOpCode op, dst.val, x.val, y.val], [j])
| .branch src j0 j1 => (9, [src.val], [j0, j1])
end ToI
end OPI
end
-- ===== OPI.DFS =====
section
/-!
# The memoized traversal as an explicit-stack machine
`stepM` performs one step of a depth-first traversal with an explicit stack of frames
`(node, next child position, child results)`, a memo list and the code table. Iterating it
`fuelM dag root` times from the initial state computes `travI dag root`.
-/
namespace OPI
open QAlgorithms QAlgorithms.OPI QAlgorithms.Complexity
abbrev Frame := ℕ × ℕ × List ℕ
abbrev MState := List Frame × List (Option ℕ) × List Str × ℕ
/-- Hand a child result to the parent frame. -/
def deliver (k : ℕ) : List Frame → List Frame
| [] => []
| (i, ph, rs) :: S => (i, ph, rs ++ [k]) :: S
/-- The memo list as a function. -/
def mf (memo : List (Option ℕ)) (j : ℕ) : Option ℕ := memo.getD j none
/-- One step of the traversal. -/
def stepM (dag : List INode) : MState → MState
| ([], s) => ([], s)
| ((i, ph, rs) :: S, memo, T, res) =>
match (if ph = 0 then mf memo i else none) with
| some k => (deliver k S, memo, T, k)
| none =>
match (dag.getD i failI).2.2[ph]? with
| some j =>
if j < i then ((j, 0, []) :: (i, ph + 1, rs) :: S, memo, T, res)
else ((i, ph + 1, rs ++ [(internProgramNode failCode T).1]) :: S, memo,
(internProgramNode failCode T).2, res)
| none =>
((deliver (internProgramNode (codeI (dag.getD i failI) rs) T).1 S),
memo.set i (some (internProgramNode (codeI (dag.getD i failI) rs) T).1),
(internProgramNode (codeI (dag.getD i failI) rs) T).2,
(internProgramNode (codeI (dag.getD i failI) rs) T).1)
/-- The number of unset memo entries. -/
def nones (memo : List (Option ℕ)) : ℕ := memo.count none
lemma mf_set (memo : List (Option ℕ)) (i : ℕ) (v : Option ℕ) (hi : i < memo.length) :
mf (memo.set i v) = Function.update (mf memo) i v := by
funext j
unfold mf
by_cases h : j = i
· subst h; simp [List.getD_eq_getElem?_getD, hi]
· rw [Function.update_of_ne h]
simp only [List.getD_eq_getElem?_getD, List.getElem?_set, Ne.symm h, if_false]
lemma nones_set (k : ℕ) : ∀ (memo : List (Option ℕ)) (i : ℕ), i < memo.length →
mf memo i = none → nones (memo.set i (some k)) + 1 = nones memo := by
intro memo
induction memo with
| nil => intro i hi; simp at hi
| cons x xs ih =>
intro i hi hn
cases i with
| zero =>
have hx : x = none := by simpa [mf] using hn
subst hx
simp [nones, List.count_cons]
| succ i =>
have := ih i (by simpa using hi) (by simpa [mf] using hn)
simp only [nones, List.set_cons_succ, List.count_cons] at this ⊢
omega
/-- The memoized traversal only changes the memo at indices `≤ i`. -/
lemma travI_memo_of_gt (dag : List INode) (i : ℕ) :
∀ memo T l, i < l → (travI dag i memo T).2.2 l = memo l := by
induction i using Nat.strong_induction_on with
| _ i IH =>
intro memo T l hl
rw [travI]
cases hm : memo i with
| some k => rfl
| none =>
simp only
rw [Function.update_of_ne (by omega)]
generalize (dag[i]?.getD failI).2.2 = cs
suffices h : ∀ (cs : List ℕ) (acc : List ℕ × List Str × (ℕ → Option ℕ)), acc.2.2 l = memo l →
(cs.foldl (fun acc j => if j < i then
((acc.1 ++ [(travI dag j acc.2.2 acc.2.1).1], (travI dag j acc.2.2 acc.2.1).2.1,
(travI dag j acc.2.2 acc.2.1).2.2))
else (acc.1 ++ [(internProgramNode failCode acc.2.1).1], (internProgramNode failCode acc.2.1).2,
acc.2.2)) acc).2.2 l = memo l from h cs _ rfl
intro cs
induction cs with
| nil => intro acc h; exact h
| cons j cs ih =>
intro acc h
rw [List.foldl_cons]
apply ih
split
· rename_i hj; simp only; rw [IH j hj _ _ l (by omega)]; exact h
· exact h
section Run
variable (dag : List INode) (W : ℕ) (hW : ∀ nd ∈ dag, 2 * nd.2.2.length ≤ W)
include hW
lemma children_le (i : ℕ) : 2 * (dag.getD i failI).2.2.length ≤ W := by
rw [List.getD_eq_getElem?_getD]
cases h : dag[i]? with
| none => simp [failI]
| some nd => exact hW nd (List.mem_of_getElem? h)
/-- **One node.** -/
theorem run_node (i : ℕ) : ∀ (S : List Frame) (memo : List (Option ℕ)) (T : List Str) (res : ℕ),
i < memo.length →
∃ n memo', memo'.length = memo.length ∧ mf memo' = (travI dag i (mf memo) T).2.2 ∧
(stepM dag)^[n] ((i, 0, []) :: S, memo, T, res) =
(deliver (travI dag i (mf memo) T).1 S, memo', (travI dag i (mf memo) T).2.1,
(travI dag i (mf memo) T).1) ∧
n + (W + 2) * nones memo' ≤ (W + 2) * nones memo + 1 := by
induction i using Nat.strong_induction_on with
| _ i IH =>
intro S memo T res hi
cases hm : mf memo i with
| some k =>
refine ⟨1, memo, rfl, ?_, ?_, by omega⟩
· rw [travI, hm]
· rw [travI, hm]
simp only [Function.iterate_one, stepM, if_pos, hm]
| none =>
-- the children loop
have loop : ∀ (cs : List ℕ) (ph : ℕ) (rs : List ℕ) (memo : List (Option ℕ)) (T : List Str) (res : ℕ),
memo.length > i → mf memo i = none → (dag.getD i failI).2.2.drop ph = cs →
∃ n memo' res', memo'.length = memo.length ∧ mf memo' i = none ∧
let r := cs.foldl (fun acc j => if j < i then
((acc.1 ++ [(travI dag j acc.2.2 acc.2.1).1], (travI dag j acc.2.2 acc.2.1).2.1,
(travI dag j acc.2.2 acc.2.1).2.2))
else (acc.1 ++ [(internProgramNode failCode acc.2.1).1], (internProgramNode failCode acc.2.1).2,
acc.2.2)) (rs, T, mf memo)
mf memo' = r.2.2 ∧
(stepM dag)^[n] ((i, ph, rs) :: S, memo, T, res) =
((i, ph + cs.length, r.1) :: S, memo', r.2.1, res') ∧
n + (W + 2) * nones memo' ≤ (W + 2) * nones memo + 2 * cs.length := by
intro cs
induction cs with
| nil =>
intro ph rs memo T res hl hmi _
exact ⟨0, memo, res, rfl, hmi, rfl, by simp, by simp⟩
| cons j cs ih =>
intro ph rs memo T res hl hmi hd
have hj : (dag.getD i failI).2.2[ph]? = some j := by
rw [← List.head?_drop, hd]; rfl
have hd' : (dag.getD i failI).2.2.drop (ph + 1) = cs := by
rw [← List.drop_drop, hd]; rfl
have hcheck : (if ph = 0 then mf memo i else none) = none := by split <;> simp [hmi]
by_cases hji : j < i
· -- push the child, run it, continue
have s1 : stepM dag ((i, ph, rs) :: S, memo, T, res) =
((j, 0, []) :: (i, ph + 1, rs) :: S, memo, T, res) := by
simp only [stepM, hcheck, hj, hji, if_true]
obtain ⟨n1, memo1, hl1, hmf1, hrun1, hb1⟩ := IH j hji ((i, ph + 1, rs) :: S) memo T res (by omega)
have hmi1 : mf memo1 i = none := by
rw [hmf1, travI_memo_of_gt dag j _ _ i hji]; exact hmi
obtain ⟨n2, memo2, res2, hl2, hmi2, hmf2, hrun2, hb2⟩ :=
ih (ph + 1) (rs ++ [(travI dag j (mf memo) T).1]) memo1 (travI dag j (mf memo) T).2.1
(travI dag j (mf memo) T).1 (by omega) hmi1 hd'
refine ⟨n2 + n1 + 1, memo2, res2, by omega, hmi2, ?_, ?_, ?_⟩
· rw [hmf2, hmf1, List.foldl_cons]; simp only [hji, if_true]
· rw [Function.iterate_add_apply, Function.iterate_add_apply, Function.iterate_one, s1, hrun1]
simp only [deliver]
rw [hrun2, hmf1]
simp only [List.foldl_cons, hji, if_true, List.length_cons]
rw [show ph + 1 + cs.length = ph + (cs.length + 1) by omega]
· simp only [List.length_cons]; omega
· -- a child that is not earlier: intern the failure code
have s1 : stepM dag ((i, ph, rs) :: S, memo, T, res) =
((i, ph + 1, rs ++ [(internProgramNode failCode T).1]) :: S, memo,
(internProgramNode failCode T).2, res) := by
simp only [stepM, hcheck, hj, hji, if_false]
obtain ⟨n2, memo2, res2, hl2, hmi2, hmf2, hrun2, hb2⟩ :=
ih (ph + 1) (rs ++ [(internProgramNode failCode T).1]) memo (internProgramNode failCode T).2
res hl hmi hd'
refine ⟨n2 + 1, memo2, res2, hl2, hmi2, ?_, ?_, ?_⟩
· rw [hmf2, List.foldl_cons]; simp only [hji, if_false]
· rw [Function.iterate_add_apply, Function.iterate_one, s1, hrun2]
simp only [List.foldl_cons, hji, if_false, List.length_cons]
rw [show ph + 1 + cs.length = ph + (cs.length + 1) by omega]
· simp only [List.length_cons]; omega
obtain ⟨n1, memo1, res1, hl1, hmi1, hmf1, hrun1, hb1⟩ :=
loop (dag.getD i failI).2.2 0 [] memo T res hi hm (by simp)
set r := (dag.getD i failI).2.2.foldl (fun acc j => if j < i then
((acc.1 ++ [(travI dag j acc.2.2 acc.2.1).1], (travI dag j acc.2.2 acc.2.1).2.1,
(travI dag j acc.2.2 acc.2.1).2.2))
else (acc.1 ++ [(internProgramNode failCode acc.2.1).1], (internProgramNode failCode acc.2.1).2,
acc.2.2)) ([], T, mf memo) with hr
have htrav : travI dag i (mf memo) T =
((internProgramNode (codeI (dag.getD i failI) r.1) r.2.1).1,
(internProgramNode (codeI (dag.getD i failI) r.1) r.2.1).2,
Function.update r.2.2 i (some (internProgramNode (codeI (dag.getD i failI) r.1) r.2.1).1)) := by
rw [travI, hm, hr, List.getD_eq_getElem?_getD]
have hnone : (dag.getD i failI).2.2[0 + (dag.getD i failI).2.2.length]? = none := by simp
have s2 : stepM dag ((i, 0 + (dag.getD i failI).2.2.length, r.1) :: S, memo1, r.2.1, res1) =
(deliver (internProgramNode (codeI (dag.getD i failI) r.1) r.2.1).1 S,
memo1.set i (some (internProgramNode (codeI (dag.getD i failI) r.1) r.2.1).1),
(internProgramNode (codeI (dag.getD i failI) r.1) r.2.1).2,
(internProgramNode (codeI (dag.getD i failI) r.1) r.2.1).1) := by
have hc : (if 0 + (dag.getD i failI).2.2.length = 0 then mf memo1 i else none) = none := by
split <;> simp [hmi1]
simp only [stepM, hc, hnone]
have hcw := children_le dag W hW i
have hns := nones_set (internProgramNode (codeI (dag.getD i failI) r.1) r.2.1).1 memo1 i
(by omega) hmi1
refine ⟨1 + n1, memo1.set i (some (internProgramNode (codeI (dag.getD i failI) r.1) r.2.1).1),
by simp [hl1], ?_, ?_, ?_⟩
· rw [mf_set _ _ _ (by omega), htrav, hmf1]
· rw [Function.iterate_add_apply, hrun1, Function.iterate_one, s2, htrav]
· have : (W + 2) * nones memo1 = (W + 2) * nones (memo1.set i
(some (internProgramNode (codeI (dag.getD i failI) r.1) r.2.1).1)) + (W + 2) := by
rw [← hns]; ring
omega
end Run
/-- The step bound for a DAG. -/
def wM (dag : List INode) : ℕ := 2 * (dag.flatMap (fun nd => nd.2.2)).length
lemma wM_spec (dag : List INode) : ∀ nd ∈ dag, 2 * nd.2.2.length ≤ wM dag := by
intro nd hnd
unfold wM
have : nd.2.2.length ≤ (dag.flatMap (fun nd => nd.2.2)).length := by
rw [List.length_flatMap]
exact List.le_sum_of_mem (List.mem_map.mpr ⟨nd, hnd, rfl⟩)
omega
/-- The fuel of the machine. -/
def fuelM (dag : List INode) (root : ℕ) : ℕ := (wM dag + 2) * (root + 1) + 1
/-- The initial state. -/
def initM (root : ℕ) : MState := ([(root, 0, [])], List.replicate (root + 1) none, [], 0)
lemma stepM_nil (dag : List INode) (s : List (Option ℕ) × List Str × ℕ) (n : ℕ) :
(stepM dag)^[n] ([], s) = ([], s) := by
induction n with
| zero => rfl
| succ n ih => rw [Function.iterate_succ_apply', ih]; rfl
/-- **The machine computes the traversal.** -/
theorem run_root (dag : List INode) (root : ℕ) :
((stepM dag)^[fuelM dag root] (initM root)).2.2.1 = (travI dag root (fun _ => none) []).2.1 ∧
((stepM dag)^[fuelM dag root] (initM root)).2.2.2 = (travI dag root (fun _ => none) []).1 := by
have hmf : mf (List.replicate (root + 1) none) = fun _ => none := by
funext j; unfold mf; rw [List.getD_eq_getElem?_getD]
cases h : (List.replicate (root + 1) (none : Option ℕ))[j]? with
| none => rfl
| some v => simp only [List.getElem?_replicate] at h; split at h <;> simp_all
obtain ⟨n, memo', hl, hmf', hrun, hb⟩ := run_node dag (wM dag) (wM_spec dag) root [] (List.replicate (root + 1) none) [] 0 (by simp)
rw [hmf] at hrun
have hnn : nones (List.replicate (root + 1) (none : Option ℕ)) = root + 1 := by
simp [nones, List.count_replicate]
have hle : n ≤ fuelM dag root := by
unfold fuelM; rw [hnn] at hb
have : 0 ≤ (wM dag + 2) * nones memo' := Nat.zero_le _
omega
obtain ⟨d, hd⟩ := Nat.exists_eq_add_of_le hle
unfold initM
rw [hd, Nat.add_comm, Function.iterate_add_apply, hrun]
simp [deliver, stepM_nil]
end OPI
end
-- ===== OPI.PR =====
section
/-!
# Polynomial realizers
An OAI `Realizer` bundled with a monotone polynomial bound on its charge and on the volume of
its output (both as functions of the input volume). The combinators compute the bounds, so a
generator assembled from them is polynomial by construction.
-/
namespace OPI.W6
open OAI.ThreeMachine.StackCompiler
/-- Monotone functions with a polynomial upper bound. -/
def Poly (T : ℕ → ℕ) : Prop := Monotone T ∧ ∃ c d : ℕ, ∀ n, T n ≤ c * (n + 1) ^ d
namespace Poly
lemma const (k : ℕ) : Poly (fun _ => k) :=
⟨fun _ _ _ => le_rfl, k, 0, fun n => by simp⟩
lemma id : Poly (fun n => n) :=
⟨fun _ _ h => h, 1, 1, fun n => by simp⟩
lemma add {T S : ℕ → ℕ} (hT : Poly T) (hS : Poly S) : Poly (fun n => T n + S n) := by
obtain ⟨mT, c, d, h⟩ := hT
obtain ⟨mS, c', d', h'⟩ := hS
refine ⟨fun a b hab => Nat.add_le_add (mT hab) (mS hab), c + c', d + d', fun n => ?_⟩
have e1 : (n + 1) ^ d ≤ (n + 1) ^ (d + d') := Nat.pow_le_pow_right (by omega) (by omega)
have e2 : (n + 1) ^ d' ≤ (n + 1) ^ (d + d') := Nat.pow_le_pow_right (by omega) (by omega)
calc T n + S n ≤ c * (n + 1) ^ d + c' * (n + 1) ^ d' := Nat.add_le_add (h n) (h' n)
_ ≤ c * (n + 1) ^ (d + d') + c' * (n + 1) ^ (d + d') :=
Nat.add_le_add (Nat.mul_le_mul_left _ e1) (Nat.mul_le_mul_left _ e2)
_ = (c + c') * (n + 1) ^ (d + d') := by ring
lemma mul {T S : ℕ → ℕ} (hT : Poly T) (hS : Poly S) : Poly (fun n => T n * S n) := by
obtain ⟨mT, c, d, h⟩ := hT
obtain ⟨mS, c', d', h'⟩ := hS
refine ⟨fun a b hab => Nat.mul_le_mul (mT hab) (mS hab), c * c', d + d', fun n => ?_⟩
calc T n * S n ≤ (c * (n + 1) ^ d) * (c' * (n + 1) ^ d') := Nat.mul_le_mul (h n) (h' n)
_ = c * c' * (n + 1) ^ (d + d') := by ring
lemma comp {T S : ℕ → ℕ} (hT : Poly T) (hS : Poly S) : Poly (fun n => S (T n)) := by
obtain ⟨mT, c, d, h⟩ := hT
obtain ⟨mS, c', d', h'⟩ := hS
refine ⟨fun a b hab => mS (mT hab), c' * (c + 1) ^ d', d * d', fun n => ?_⟩
have h1 : T n + 1 ≤ (c + 1) * (n + 1) ^ d := by
have := h n
have : 1 ≤ (n + 1) ^ d := Nat.one_le_pow _ _ (by omega)
nlinarith
calc S (T n) ≤ c' * (T n + 1) ^ d' := h' _
_ ≤ c' * ((c + 1) * (n + 1) ^ d) ^ d' := Nat.mul_le_mul_left _ (Nat.pow_le_pow_left h1 _)
_ = c' * (c + 1) ^ d' * (n + 1) ^ (d * d') := by rw [mul_pow, ← pow_mul]; ring
lemma smul (k : ℕ) {T : ℕ → ℕ} (hT : Poly T) : Poly (fun n => k * T n) :=
(const k).mul hT
lemma succ {T : ℕ → ℕ} (hT : Poly T) : Poly (fun n => T n + 1) := hT.add (const 1)
lemma mono {T : ℕ → ℕ} (hT : Poly T) {a b : ℕ} (h : a ≤ b) : T a ≤ T b := hT.1 h
end Poly
variable {α β γ δ ε : Type} [Coding α] [Coding β] [Coding γ] [Coding δ] [Coding ε]
/-- A realizer with a polynomial bound on its charge and on its output volume. -/
structure PR (f : α → β) where
R : Realizer f
T : ℕ → ℕ
poly : Poly T
time_le : ∀ x, R.time x ≤ T (volume x)
vol_le : ∀ x, volume (f x) ≤ T (volume x)
namespace PR
variable {f : α → β} {g : β → γ}
def congr {f' : α → β} (P : PR f) (h : ∀ x, f x = f' x) : PR f' :=
⟨P.R.congr h, P.T, P.poly, fun x => by rw [Realizer.time_congr]; exact P.time_le x,
fun x => by rw [← h]; exact P.vol_le x⟩
def id : PR (fun x : α => x) :=
⟨Realizer.id, fun n => n + 2, Poly.id.add (Poly.const 2), fun x => by simp, fun x => by omega⟩
def fst : PR (Prod.fst : α × β → α) :=
⟨Realizer.fst, fun n => n + 2, Poly.id.add (Poly.const 2), fun x => by simp,
fun x => by rcases x with ⟨a, b⟩; simp only [volume_pair]; omega⟩
def snd : PR (Prod.snd : α × β → β) :=
⟨Realizer.snd, fun n => n + 2, Poly.id.add (Poly.const 2), fun x => by simp,
fun x => by rcases x with ⟨a, b⟩; simp only [volume_pair]; omega⟩
def reinterpret (f : α → β) (h : ∀ x, enc (f x) = enc x) : PR f :=
⟨Realizer.reinterpret f h, fun n => n + 2, Poly.id.add (Poly.const 2), fun x => by simp,
fun x => by simp only [volume, h]; omega⟩
def const (b : β) : PR (fun _ : α => b) :=
⟨Realizer.constant b, fun n => (2 * volume b + 1) * (20 * n + (50 * volume b + 50)),
Poly.smul _ ((Poly.smul 20 Poly.id).add (Poly.const _)),
fun x => by
change (2 * volume b + 1) * (20 * volume x + 50 * volume b + 50) ≤ _
rw [Nat.add_assoc],
fun x => by nlinarith⟩
def comp (P : PR f) (Q : PR g) : PR (fun x => g (f x)) :=
⟨P.R.comp Q.R, fun n => P.T n + Q.T (P.T n) + 10 * (P.T n + 1),
(P.poly.add (P.poly.comp Q.poly)).add (Poly.smul 10 P.poly.succ),
fun x => by
rw [Realizer.time_comp]
have h1 := P.time_le x
have h2 := P.vol_le x
have h3 := Q.time_le (f x)
have h4 := Q.poly.mono h2
omega,
fun x => (Q.vol_le (f x)).trans (Q.poly.mono (P.vol_le x)) |>.trans (by omega)⟩
def pair {g : α → γ} (P : PR f) (Q : PR g) : PR (fun x => (f x, g x)) :=
⟨P.R.pair Q.R, fun n => P.T n + Q.T n + 20 * (n + P.T n + Q.T n + 1),
(P.poly.add Q.poly).add (Poly.smul 20 (((Poly.id.add P.poly).add Q.poly).succ)),
fun x => by
rw [Realizer.time_pair]
have := P.time_le x; have := Q.time_le x; have := P.vol_le x; have := Q.vol_le x
omega,
fun x => by
simp only [volume_pair]
have := P.vol_le x; have := Q.vol_le x
omega⟩
def nil : PR (fun _ : α => ([] : List β)) := (const ([] : List β)).congr (fun _ => rfl)
def cons : PR (fun x : α × List α => x.1 :: x.2) := reinterpret _ (fun _ => rfl)
/-! ### Folds -/
lemma foldTime_le' {F : α × β → β} (R : Realizer F) (T V : ℕ) :
∀ (xs : List α) (b : β),
(∀ k, volume ((xs.take k).foldl (fun b a => F (a, b)) b) ≤ V) →
(∀ a ∈ xs, ∀ k, R.time (a, (xs.take k).foldl (fun b a => F (a, b)) b) ≤ T) →
Realizer.foldTime R b xs ≤ xs.length * (T + 20 * (volume xs + 2 * V + 1)) + 1
| [], b, _, _ => by simp [Realizer.foldTime]
| a :: xs, b, hV, hT => by
have ih := foldTime_le' R T V xs (F (a, b))
(fun k => by simpa using hV (k + 1))
(fun a' ha' k => by simpa using hT a' (List.mem_cons_of_mem _ ha') (k + 1))
have h0 := hV 0
have h1 := hV 1
have ht := hT a (List.mem_cons_self) 0
simp only [List.take_zero, List.foldl_nil, List.take_succ_cons, List.foldl_cons] at h0 h1 ht
simp only [Realizer.foldTime, List.length_cons, volume_cons] at ih ⊢
have hx : xs.length * (T + 20 * (volume xs + 2 * V + 1)) ≤
xs.length * (T + 20 * (volume a + volume xs + 1 + 2 * V + 1)) :=
Nat.mul_le_mul_left _ (by omega)
nlinarith
/-- Folds, given a polynomial bound `G` on all intermediate accumulators. -/
def fold {F : α × β → β} (P : PR F) (G : ℕ → ℕ) (hG : Poly G)
(hacc : ∀ (xs : List α) (b : β) k,
volume ((xs.take k).foldl (fun b a => F (a, b)) b) ≤ G (volume (xs, b))) :
PR (fun x : List α × β => x.1.foldl (fun b a => F (a, b)) x.2) :=
⟨P.R.fold, fun n => 2 * n + 6 + (n * (P.T (n + G n + 1) + 20 * (n + 2 * G n + 1)) + 1) + G n,
((((Poly.smul 2 Poly.id).add (Poly.const 6)).add
((Poly.id.mul ((((Poly.id.add hG).succ).comp P.poly).add
(Poly.smul 20 ((Poly.id.add (Poly.smul 2 hG)).succ)))).succ)).add hG),
fun x => by
rcases x with ⟨xs, b⟩
rw [Realizer.time_fold]
have hl : xs.length ≤ volume (xs, b) := by
have : xs.length ≤ volume xs := by
clear hacc; induction xs with
| nil => simp
| cons a xs ih => simp only [List.length_cons, volume_cons]; have := volume_pos a; omega
simp only [volume_pair]; omega
have hxs : volume xs ≤ volume (xs, b) := by simp only [volume_pair]; omega
have key := foldTime_le' P.R (P.T (volume (xs, b) + G (volume (xs, b)) + 1)) (G (volume (xs, b)))
xs b (fun k => hacc xs b k)
(fun a ha k => by
refine (P.time_le _).trans (P.poly.mono ?_)
have hva : volume a ≤ volume xs := by
obtain ⟨l1, l2, rfl⟩ := List.append_of_mem ha
clear hacc hl hxs ha; induction l1 with
| nil => simp only [List.nil_append, volume_cons]; omega
| cons c l1 ih => simp only [List.cons_append, volume_cons]; omega
have := hacc xs b k
simp only [volume_pair] at this hxs ⊢; omega)
generalize volume (xs, b) = n at *
have e1 : xs.length * (P.T (n + G n + 1) + 20 * (volume xs + 2 * G n + 1)) ≤
n * (P.T (n + G n + 1) + 20 * (n + 2 * G n + 1)) :=
Nat.mul_le_mul hl (by omega)
simp only at key ⊢
omega,
fun x => by
rcases x with ⟨xs, b⟩
have := hacc xs b xs.length
rw [List.take_length] at this
simp only
omega⟩
/-- Accumulator bound for folds whose step adds at most `c (|a| + 1)` to the volume. -/
lemma hacc_add {F : α × β → β} (c : ℕ) (h : ∀ a b, volume (F (a, b)) ≤ volume b + c * (volume a + 1)) :
∀ (xs : List α) (b : β) k,
volume ((xs.take k).foldl (fun b a => F (a, b)) b) ≤ (fun n => n + c * n) (volume (xs, b)) := by
have key : ∀ (xs : List α) (b : β) k,
volume ((xs.take k).foldl (fun b a => F (a, b)) b) + 1 ≤ volume b + c * volume xs + 1 := by
intro xs
induction xs with
| nil => intro b k; simp
| cons a xs ih =>
intro b k
cases k with
| zero =>
simp only [List.take_zero, List.foldl_nil, volume_cons]
have : 0 ≤ c * (volume a + volume xs + 1) := Nat.zero_le _
omega
| succ k =>
simp only [List.take_succ_cons, List.foldl_cons, volume_cons]
have h1 := ih (F (a, b)) k
have h2 := h a b
have e : c * (volume a + volume xs + 1) = c * (volume a + 1) + c * volume xs := by ring
rw [e]; omega
intro xs b k
have h1 := key xs b k
simp only [volume_pair]
have e : c * (volume xs + volume b + 1) = c * volume xs + c * (volume b + 1) := by ring
rw [e]; omega
/-- Iteration, given a polynomial bound on all iterates. -/
def iterate {f : α → α} (P : PR f) (G : ℕ → ℕ) (hG : Poly G)
(hacc : ∀ (m : ℕ) (a : α) j, j ≤ m → volume (f^[j] a) ≤ G (volume (m, a))) :
PR (fun x : ℕ × α => f^[x.1] x.2) :=
⟨P.R.iterate, fun n => 10000 * ((n + 1) * (P.T (G n) + G n + n + 1)) + G n,
((Poly.smul 10000 (Poly.id.succ.mul ((((hG.comp P.poly).add hG).add Poly.id).succ))).add hG),
fun x => by
rcases x with ⟨m, a⟩
have hm : m ≤ volume (m, a) := by simp only [volume_pair, volume_nat]; omega
have := Realizer.time_iterate_le P.R m a (P.T (G (volume (m, a)))) (G (volume (m, a)))
(fun j hj => (P.time_le _).trans (P.poly.mono (hacc m a j hj.le)))
(fun j hj => hacc m a j hj)
have e : (m + 1) * (P.T (G (volume (m, a))) + G (volume (m, a)) + m + 1) ≤
(volume (m, a) + 1) * (P.T (G (volume (m, a))) + G (volume (m, a)) + volume (m, a) + 1) :=
Nat.mul_le_mul (by omega) (by omega)
rw [Nat.mul_assoc] at this
show _ ≤ 10000 * ((volume (m, a) + 1) * _) + _
omega,
fun x => by
rcases x with ⟨m, a⟩
have := hacc m a m le_rfl
simp only
omega⟩
/-! ### Volume facts -/
lemma length_le_volume (xs : List α) : xs.length ≤ volume xs := by
induction xs with
| nil => simp
| cons a xs ih => simp only [List.length_cons, volume_cons]; have := volume_pos a; omega
lemma volume_lt_of_mem {a : α} {xs : List α} (h : a ∈ xs) : volume a < volume xs := by
induction xs with
| nil => simp at h
| cons b xs ih =>
simp only [volume_cons]
rcases List.mem_cons.mp h with rfl | h
· omega
· have := ih h; omega
/-! ### Choice -/
def choose {g : α → β} (P : PR f) (Q : PR g) : PR (fun x : Bool × α => if x.1 then f x.2 else g x.2) :=
⟨P.R.choose Q.R, fun n => (n + 2 + P.T n + 10 * (n + 1)) + (n + 2 + Q.T n + 10 * (n + 1)) +
30 * (n + P.T n + Q.T n + 1),
(((Poly.id.add (Poly.const 2)).add P.poly).add (Poly.smul 10 Poly.id.succ)).add
(((Poly.id.add (Poly.const 2)).add Q.poly).add (Poly.smul 10 Poly.id.succ)) |>.add
(Poly.smul 30 ((Poly.id.add P.poly).add Q.poly).succ),
fun x => by
rcases x with ⟨c, a⟩
rw [Realizer.time_choose, Realizer.time_comp, Realizer.time_comp]
simp only [Realizer.time_snd, volume_pair]
have h1 := P.time_le a; have h2 := Q.time_le a; have h3 := P.vol_le a; have h4 := Q.vol_le a
have hc := volume_bool c
have m1 := P.poly.mono (show volume a ≤ volume c + volume a + 1 by omega)
have m2 := Q.poly.mono (show volume a ≤ volume c + volume a + 1 by omega)
omega,
fun x => by
rcases x with ⟨c, a⟩
simp only [volume_pair]
have h3 := P.vol_le a; have h4 := Q.vol_le a
have m1 := P.poly.mono (show volume a ≤ volume c + volume a + 1 by omega)
have m2 := Q.poly.mono (show volume a ≤ volume c + volume a + 1 by omega)
split_ifs <;> omega⟩
def ite {p : α → Bool} {g : α → β} (Pp : PR p) (P : PR f) (Q : PR g) :
PR (fun x => if p x then f x else g x) :=
((Pp.pair id).comp (P.choose Q)).congr (fun _ => rfl)
/-! ### Map -/
def map {f : α × γ → β} (P : PR f) : PR (fun x : List α × γ => x.1.map (fun a => f (a, x.2))) :=
⟨(Uniform.map (P.R.uniform Unit)).specialize (),
fun n => 30000 * ((n + 1) * (P.T n + n + n + (n * (P.T n + 1) + 1) + 1)) + (n * (P.T n + 1) + 1),
(Poly.smul 30000 (Poly.id.succ.mul
((((P.poly.add Poly.id).add Poly.id).add (Poly.id.mul P.poly.succ).succ).succ))).add
(Poly.id.mul P.poly.succ).succ,
fun x => by
rcases x with ⟨xs, e⟩
have hb : ∀ a ∈ xs, volume (a, e) ≤ volume (xs, e) := fun a ha => by
have := volume_lt_of_mem ha; simp only [volume_pair]; omega
have hT : ∀ a ∈ xs, (P.R.uniform Unit).time () (a, e) ≤ P.T (volume (xs, e)) := fun a ha => by
rw [Uniform.time_uniform]; exact (P.time_le _).trans (P.poly.mono (hb a ha))
have hm := Uniform.time_map (P.R.uniform Unit) () xs e _ hT
have hv := volume_list_le (xs.map (fun a => f (a, e))) (P.T (volume (xs, e))) (fun b hb' => by
obtain ⟨a, ha, rfl⟩ := List.mem_map.mp hb'
exact (P.vol_le _).trans (P.poly.mono (hb a ha)))
have hl := length_le_volume xs
simp only [List.length_map] at hv
have hm' : ((Uniform.map (P.R.uniform Unit)).specialize ()).time (xs, e) ≤ _ := hm
clear hm
generalize hn : volume (xs, e) = n at *
have hxe : volume xs + volume e + 1 = n := by rw [← hn, volume_pair]
have e1 : 30000 * (xs.length + 1) * (P.T n + volume xs + volume e +
volume (xs.map (fun a => f (a, e))) + 1) ≤
30000 * ((n + 1) * (P.T n + n + n + (n * (P.T n + 1) + 1) + 1)) := by
rw [Nat.mul_assoc]
refine Nat.mul_le_mul_left _ (Nat.mul_le_mul (by omega) ?_)
have : xs.length * (P.T n + 1) ≤ n * (P.T n + 1) := Nat.mul_le_mul_right _ (by omega)
omega
omega,
fun x => by
rcases x with ⟨xs, e⟩
have hb : ∀ a ∈ xs, volume (a, e) ≤ volume (xs, e) := fun a ha => by
have := volume_lt_of_mem ha; simp only [volume_pair]; omega
have hv := volume_list_le (xs.map (fun a => f (a, e))) (P.T (volume (xs, e))) (fun b hb' => by
obtain ⟨a, ha, rfl⟩ := List.mem_map.mp hb'
exact (P.vol_le _).trans (P.poly.mono (hb a ha)))
have hl := length_le_volume xs
simp only [List.length_map] at hv
have : xs.length * (P.T (volume (xs, e)) + 1) ≤ volume (xs, e) * (P.T (volume (xs, e)) + 1) :=
Nat.mul_le_mul_right _ (by simp only [volume_pair]; omega)
simp only
omega⟩
/-! ### List primitives -/
def revOnto : PR (fun x : List α × List α => x.1.foldl (fun b a => a :: b) x.2) :=
((cons : PR (fun x : α × List α => x.1 :: x.2)).fold (fun n => n + 1 * n)
(Poly.id.add (Poly.smul 1 Poly.id))
(hacc_add (F := fun x : α × List α => x.1 :: x.2) 1 (fun a b => by simp only [volume_cons]; omega))).congr (fun _ => rfl)
def reverse : PR (fun xs : List α => xs.reverse) :=
((id.pair (nil : PR (fun _ : List α => ([] : List α)))).comp revOnto).congr
(fun xs => by simp only [Realizer.fold_cons_eq, List.append_nil])
def append : PR (fun x : List α × List α => x.1 ++ x.2) :=
(((fst.comp reverse).pair snd).comp revOnto).congr
(fun x => by simp only [Realizer.fold_cons_eq, List.reverse_reverse])
lemma volume_revOnto (xs ys : List α) :
volume (xs.foldl (fun b a => a :: b) ys) + 1 = volume xs + volume ys := by
rw [Realizer.fold_cons_eq, volume_append, volume_reverse]
def flatten : PR (fun xs : List (List α) => xs.flatten) :=
((((id.pair nil).comp (revOnto.fold (fun n => n + 1 * n) (Poly.id.add (Poly.smul 1 Poly.id))
(hacc_add (F := fun x : List α × List α => x.1.foldl (fun b a => a :: b) x.2) 1 (fun zs acc => by
have := volume_revOnto zs acc; dsimp only; omega)))).comp reverse).congr
(fun xs => by
simp only
rw [show (fun (b : List α) (a : List α) => a.foldl (fun b a => a :: b) b) =
(fun ys zs => zs.foldl (fun ys a => a :: ys) ys) from rfl]
rw [Uniform.flatten_fold_eq (I := Unit) (α := fun _ => α) () xs [], List.append_nil,
List.reverse_reverse]))
def flatMap {f : α × γ → List β} (P : PR f) :
PR (fun x : List α × γ => x.1.flatMap (fun a => f (a, x.2))) :=
(P.map.comp flatten).congr (fun x => by simp [List.flatMap])
def length : PR (fun xs : List α => xs.length) :=
((id.pair (const 0)).comp
((⟨Realizer.snd.comp Realizer.succ, fun n => (n + 2) + 200 * (n + 1) + 10 * (n + 1),
((Poly.id.add (Poly.const 2)).add (Poly.smul 200 Poly.id.succ)).add (Poly.smul 10 Poly.id.succ),
fun x => by
rcases x with ⟨a, k⟩
rw [Realizer.time_comp]
simp only [Realizer.time_snd, volume_pair, volume_nat]
have := Realizer.time_succ_le k
omega,
fun x => by rcases x with ⟨a, k⟩; simp only [volume_pair, volume_nat]; omega⟩ :
PR (fun x : α × ℕ => x.2 + 1)).fold (fun n => n + 2 * n) (Poly.id.add (Poly.smul 2 Poly.id))
(hacc_add (F := fun x : α × ℕ => x.2 + 1) 2 (fun a k => by simp only [volume_nat]; omega)))).congr (fun xs => by
simp only
have : ∀ (ys : List α) (k : ℕ), ys.foldl (fun b _ => b + 1) k = k + ys.length := by
intro ys; induction ys with
| nil => simp
| cons a ys ih => intro k; simp [ih]; omega
rw [this]; simp)
end PR
end OPI.W6
end
-- ===== OPI.PRArith =====
section
/-!
# Polynomial realizers: arithmetic, Booleans, and the Cook–Levin bridge
-/
namespace OPI.W6
open OAI.ThreeMachine.StackCompiler
variable {α β γ : Type} [Coding α] [Coding β] [Coding γ]
namespace PR
/-- Quadratic-time binary operations on unary numbers. -/
def ofQuad {f : ℕ × ℕ → β} (R : Realizer f) (C : ℕ) (ht : ∀ a b, R.time (a, b) ≤ C * (a + b + 1) ^ 2)
(hv : ∀ a b, volume (f (a, b)) ≤ 2 * (a + b) + 3) : PR f :=
⟨R, fun n => C * (n * n) + n, (Poly.smul C (Poly.id.mul Poly.id)).add Poly.id,
fun x => by
rcases x with ⟨a, b⟩
have h := ht a b
simp only [volume_pair, volume_nat]
have : (a + b + 1) ^ 2 ≤ (2 * a + 1 + (2 * b + 1) + 1) * (2 * a + 1 + (2 * b + 1) + 1) := by
rw [sq]; exact Nat.mul_le_mul (by omega) (by omega)
have := Nat.mul_le_mul_left C this
omega,
fun x => by
rcases x with ⟨a, b⟩
have := hv a b
simp only [volume_pair, volume_nat]
omega⟩
def add : PR (fun x : ℕ × ℕ => x.1 + x.2) :=
ofQuad Realizer.add _ Realizer.time_add_le (fun a b => by simp only [volume_nat]; omega)
def sub : PR (fun x : ℕ × ℕ => x.1 - x.2) :=
ofQuad Realizer.sub _ Realizer.time_sub_le (fun a b => by simp only [volume_nat]; omega)
def le : PR (fun x : ℕ × ℕ => decide (x.1 ≤ x.2)) :=
ofQuad Realizer.le _ Realizer.time_le_le (fun a b => by have := volume_bool (decide (a ≤ b)); dsimp only; omega)
def eqNat : PR (fun x : ℕ × ℕ => decide (x.1 = x.2)) :=
ofQuad Realizer.eqNat _ Realizer.time_eqNat_le (fun a b => by have := volume_bool (decide (a = b)); dsimp only; omega)
def succ : PR (fun n : ℕ => n + 1) :=
⟨Realizer.succ, fun n => 200 * (n + 1), Poly.smul 200 Poly.id.succ,
fun x => by have := Realizer.time_succ_le x; simp only [volume_nat]; omega,
fun x => by simp only [volume_nat]; omega⟩
def not : PR (fun b : Bool => !b) :=
⟨Realizer.not, fun _ => 10000, Poly.const _, fun x => Realizer.time_not_le x,
fun x => by have := volume_bool (!x); omega⟩
def and : PR (fun x : Bool × Bool => x.1 && x.2) :=
⟨Realizer.and, fun _ => 10000, Poly.const _, fun x => Realizer.time_and_le x,
fun x => by have := volume_bool (x.1 && x.2); omega⟩
def or : PR (fun x : Bool × Bool => x.1 || x.2) :=
⟨Realizer.or, fun _ => 10000, Poly.const _, fun x => Realizer.time_or_le x,
fun x => by have := volume_bool (x.1 || x.2); omega⟩
def isZero : PR (fun n : ℕ => decide (n = 0)) :=
((id.pair (const 0)).comp eqNat).congr (fun _ => rfl)
/-- Multiplication by repeated addition. -/
def mul : PR (fun x : ℕ × ℕ => x.1 * x.2) :=
(((fst.pair (snd.pair (const 0))).comp
((fst.pair ((snd.pair fst).comp add) : PR (fun y : ℕ × ℕ => (y.1, y.2 + y.1))).iterate
(fun n => 4 * (n * n) + 4 * n + 4)
(((Poly.smul 4 (Poly.id.mul Poly.id)).add (Poly.smul 4 Poly.id)).add (Poly.const 4))
(fun m a j hj => by
rcases a with ⟨b, c⟩
have e : ∀ j, (fun y : ℕ × ℕ => (y.1, y.2 + y.1))^[j] (b, c) = (b, c + j * b) := by
intro j; induction j with
| zero => simp
| succ j ih => rw [Function.iterate_succ_apply', ih]; simp only [Prod.mk.injEq, true_and]; ring
rw [e]
simp only [volume_pair, volume_nat]
have : j * b ≤ m * b := Nat.mul_le_mul_right _ hj
have : m * b ≤ (2 * m + 1 + (2 * b + 1 + (2 * c + 1) + 1) + 1) *
(2 * m + 1 + (2 * b + 1 + (2 * c + 1) + 1) + 1) := Nat.mul_le_mul (by omega) (by omega)
omega))).comp snd).congr (fun x => by
rcases x with ⟨a, b⟩
have e : ∀ j, (fun y : ℕ × ℕ => (y.1, y.2 + y.1))^[j] (b, 0) = (b, j * b) := by
intro j; induction j with
| zero => simp
| succ j ih => rw [Function.iterate_succ_apply', ih]; simp only [Prod.mk.injEq, true_and]; ring
simp only [e])
end PR
/-! ### The bridge to Cook–Levin machines -/
lemma volume_bools_le (x : List Bool) : volume x ≤ 4 * x.length + 1 := by
induction x with
| nil => simp
| cons b x ih => simp only [volume_cons, List.length_cons]; have := volume_bool b; omega
end OPI.W6
end
-- ===== OPI.PRList =====
section
/-!
# Polynomial realizers: list operations
-/
namespace OPI.W6
open OAI.ThreeMachine.StackCompiler
variable {α β γ : Type} [Coding α] [Coding β] [Coding γ]
namespace PR
/-- Accumulator bound for folds carrying a frozen part of volume `inv b`. -/
lemma hacc_env {F : α × β → β} (c : ℕ) (inv : β → ℕ) (hinv : ∀ a b, inv (F (a, b)) = inv b)
(hle : ∀ b, inv b ≤ volume b)
(h : ∀ a b, volume (F (a, b)) ≤ volume b + c * (volume a + 1) + inv b) :
∀ (xs : List α) (b : β) k,
volume ((xs.take k).foldl (fun b a => F (a, b)) b) ≤
(fun n => n + c * n + n * n) (volume (xs, b)) := by
have key : ∀ (xs : List α) (b : β) k,
volume ((xs.take k).foldl (fun b a => F (a, b)) b) + 1 ≤
volume b + c * volume xs + xs.length * inv b + 1 ∧
inv ((xs.take k).foldl (fun b a => F (a, b)) b) = inv b := by
intro xs
induction xs with
| nil => intro b k; simp
| cons a xs ih =>
intro b k
cases k with
| zero =>
simp only [List.take_zero, List.foldl_nil, volume_cons, List.length_cons]
refine ⟨?_, by simp⟩
have : 0 ≤ c * (volume a + volume xs + 1) := Nat.zero_le _
have : 0 ≤ (xs.length + 1) * inv b := Nat.zero_le _
omega
| succ k =>
simp only [List.take_succ_cons, List.foldl_cons, volume_cons, List.length_cons]
obtain ⟨h1, h1'⟩ := ih (F (a, b)) k
have h2 := h a b
rw [hinv] at h1 h1'
refine ⟨?_, h1'⟩
have e : c * (volume a + volume xs + 1) = c * (volume a + 1) + c * volume xs := by ring
have e' : (xs.length + 1) * inv b = xs.length * inv b + inv b := by ring
rw [e, e']; omega
intro xs b k
have h1 := (key xs b k).1
have hl := length_le_volume xs
have hi := hle b
simp only [volume_pair]
have e1 : xs.length * inv b ≤ (volume xs + volume b + 1) * (volume xs + volume b + 1) :=
Nat.mul_le_mul (by omega) (by omega)
have e : c * (volume xs + volume b + 1) = c * volume xs + c * (volume b + 1) := by ring
rw [e]; omega
/-! ### Basic list access -/
def tail : PR (fun xs : List α => xs.tail) :=
⟨(Uniform.tail (I := Unit) (α := fun _ => α)).specialize (), fun n => n + 2,
Poly.id.add (Poly.const 2), fun x => le_rfl,
fun x => by cases x <;> simp only [List.tail_nil, List.tail_cons, volume_cons] <;> omega⟩
def head? : PR (fun xs : List α => xs.head?) :=
⟨(Uniform.head? (I := Unit) (α := fun _ => α)).specialize (), fun n => 10000 * (n + 1) + (n + 2),
(Poly.smul 10000 Poly.id.succ).add (Poly.id.add (Poly.const 2)),
fun x => (Uniform.time_head?_le (I := Unit) (α := fun _ => α) () x).trans (by omega),
fun x => by cases x <;> simp only [List.head?_nil, List.head?_cons, volume_none, volume_some,
volume_cons] <;> omega⟩
def drop : PR (fun x : List α × ℕ => x.1.drop x.2) :=
((snd.pair fst).comp (tail.iterate (fun n => n) Poly.id (fun m xs j _ => by
have : ∀ j (xs : List α), volume ((fun xs : List α => xs.tail)^[j] xs) ≤ volume xs := by
intro j; induction j with
| zero => intro xs; simp
| succ j ih => intro xs; rw [Function.iterate_succ_apply]; refine (ih _).trans ?_
cases xs <;> simp only [List.tail_nil, List.tail_cons, volume_cons] <;> omega
have := this j xs
simp only [volume_pair]; omega))).congr (fun x => by
simp only
have h : ∀ (n : ℕ) (xs : List α), (fun xs : List α => xs.tail)^[n] xs = xs.drop n := by
intro n; induction n with
| zero => intro xs; rfl
| succ n ih => intro xs; rw [Function.iterate_succ_apply, ih, List.drop_tail]
rw [h])
def getElem? : PR (fun x : List α × ℕ => x.1[x.2]?) :=
(drop.comp head?).congr (fun x => by simp only [List.head?_drop])
def optGetD : PR (fun x : Option α × α => x.1.getD x.2) :=
⟨(Uniform.getD (I := Unit) (α := fun _ => α)).specialize (), fun n => 10000 * (n + 1) + n,
(Poly.smul 10000 Poly.id.succ).add Poly.id,
fun x => by
rcases x with ⟨o, a⟩
have := Uniform.time_getD_le (I := Unit) (α := fun _ => α) () o a
exact this.trans (by simp only [volume_pair]; omega),
fun x => by
rcases x with ⟨o, a⟩
cases o <;> simp only [Option.getD_none, Option.getD_some, volume_pair, volume_none, volume_some] <;>
omega⟩
def listGetD : PR (fun x : (List α × ℕ) × α => x.1.1.getD x.1.2 x.2) :=
(((fst.comp getElem?).pair snd).comp optGetD).congr (fun x => by
simp only [List.getD_eq_getElem?_getD])
def isCons : PR (fun xs : List α => !xs.isEmpty) :=
⟨(Uniform.isCons (I := Unit) (α := fun _ => α)).specialize (), fun n => 10000 * (n + 1) + 3,
(Poly.smul 10000 Poly.id.succ).add (Poly.const 3),
fun x => (Realizer.time_test_le (α := List α) (fun xs => !xs.isEmpty)
(by intro xs; cases xs <;> rfl) x).trans (by omega),
fun x => by have := volume_bool (!x.isEmpty); omega⟩
def isSome : PR (fun o : Option α => o.isSome) :=
⟨(Uniform.optionIsSome (I := Unit) (α := fun _ => α)).specialize (), fun n => 10000 * (n + 1) + 3,
(Poly.smul 10000 Poly.id.succ).add (Poly.const 3),
fun x => (Realizer.time_test_le (α := Option α) (fun o => o.isSome)
(by intro o; cases o <;> rfl) x).trans (by omega),
fun x => by have := volume_bool x.isSome; omega⟩
/-- Head with a default. -/
def headD : PR (fun x : List α × α => x.1.headD x.2) :=
(((fst.comp head?).pair snd).comp optGetD).congr (fun x => by cases x.1 <;> rfl)
/-! ### Folds with environments -/
/-- `any` with an environment. -/
def any {p : α × γ → Bool} (P : PR p) : PR (fun x : List α × γ => x.1.any (fun a => p (a, x.2))) :=
(((fst.pair (snd.pair (const false))).comp
((((snd.comp fst).pair (((snd.comp snd).pair ((fst.pair (snd.comp fst)).comp P)).comp or)) :
PR (fun y : α × (γ × Bool) => (y.2.1, y.2.2 || p (y.1, y.2.1)))).fold
(fun n => n + 2 * n + n * n) ((Poly.id.add (Poly.smul 2 Poly.id)).add (Poly.id.mul Poly.id))
(hacc_env (F := fun y : α × (γ × Bool) => (y.2.1, y.2.2 || p (y.1, y.2.1))) 2 (fun _ => 0)
(fun _ _ => rfl) (fun _ => Nat.zero_le _)
(fun a b => by
rcases b with ⟨e, c⟩
have := volume_bool c; have := volume_bool (c || p (a, e))
have := volume_pos c; have := volume_pos a
simp only [volume_pair]; omega)))).comp snd).congr (fun x => by
simp only
rw [Uniform.any_fold_eq (I := Unit) (α := fun _ => α) (γ := fun _ => γ) (fun _ => p) () x.1 x.2 false]
simp)
/-- The step of `setL`. -/
def setStep : PR (fun y : α × (α × ℕ × ℕ × List α) =>
(y.2.1, y.2.2.1, y.2.2.2.1 + 1, (if y.2.2.2.1 = y.2.2.1 then y.2.1 else y.1) :: y.2.2.2.2)) :=
let vP : PR (fun y : α × (α × ℕ × ℕ × List α) => y.2.1) := snd.comp fst
let iP : PR (fun y : α × (α × ℕ × ℕ × List α) => y.2.2.1) := (snd.comp snd).comp fst
let cP : PR (fun y : α × (α × ℕ × ℕ × List α) => y.2.2.2.1) := ((snd.comp snd).comp snd).comp fst
let accP : PR (fun y : α × (α × ℕ × ℕ × List α) => y.2.2.2.2) := ((snd.comp snd).comp snd).comp snd
let chP := (((cP.pair iP).comp eqNat).pair (vP.pair fst)).comp (choose fst snd)
(vP.pair (iP.pair ((cP.comp succ).pair ((chP.pair accP).comp cons)))).congr (fun y => by
simp only [decide_eq_true_eq])
/-- `List.set`. -/
def setL : PR (fun x : (List α × ℕ) × α => x.1.1.set x.1.2 x.2) :=
let init : PR (fun x : (List α × ℕ) × α => (x.1.1, (x.2, x.1.2, 0, ([] : List α)))) :=
(fst.comp fst).pair (snd.pair ((fst.comp snd).pair ((const 0).pair nil)))
let body := setStep.fold
(fun n => n + 3 * n + n * n) ((Poly.id.add (Poly.smul 3 Poly.id)).add (Poly.id.mul Poly.id))
(hacc_env (F := fun y : α × (α × ℕ × ℕ × List α) =>
(y.2.1, y.2.2.1, y.2.2.2.1 + 1, (if y.2.2.2.1 = y.2.2.1 then y.2.1 else y.1) :: y.2.2.2.2))
3 (fun b => volume b.1) (fun _ _ => rfl)
(fun b => by rcases b with ⟨v, r⟩; simp only [volume_pair]; omega)
(fun a b => by
rcases b with ⟨v, i, c, acc⟩
simp only [volume_pair, volume_cons, volume_nat]
split_ifs <;> omega))
let fin : PR (fun y : α × ℕ × ℕ × List α => y.2.2.2.reverse) := ((snd.comp snd).comp snd).comp reverse
((init.comp body).comp fin).congr (fun x => by
rcases x with ⟨⟨xs, i⟩, v⟩
simp only
have key : ∀ (xs acc : List α) (c : ℕ), xs.foldl (fun b a =>
(b.1, b.2.1, b.2.2.1 + 1, (if b.2.2.1 = b.2.1 then b.1 else a) :: b.2.2.2)) (v, i, c, acc) =
(v, i, c + xs.length, (xs.mapIdx (fun k a => if c + k = i then v else a)).reverse ++ acc) := by
intro xs; induction xs with
| nil => intro acc c; simp
| cons a xs ih =>
intro acc c
rw [List.foldl_cons, ih]
simp only [List.length_cons, List.mapIdx_cons, List.reverse_cons, List.append_assoc,
List.singleton_append, Nat.add_zero, Prod.mk.injEq, true_and]
refine ⟨by omega, ?_⟩
congr 2
refine List.mapIdx_eq_mapIdx_iff.mpr (fun k hk => ?_)
simp only [show c + 1 + k = c + (k + 1) by omega]
rw [key]
simp only [Nat.zero_add, List.append_nil, List.reverse_reverse]
refine List.ext_getElem (by simp) (fun k h1 h2 => ?_)
rw [List.getElem_mapIdx, List.getElem_set]
by_cases h : k = i
· subst h; simp
· simp only [Nat.zero_add, h, if_false, Ne.symm h])
lemma iter_rep (a : α) : ∀ (j : ℕ) (acc : List α),
(fun y : α × List α => (y.1, y.1 :: y.2))^[j] (a, acc) = (a, List.replicate j a ++ acc) := by
intro j; induction j with
| zero => intro acc; simp
| succ j ih => intro acc; rw [Function.iterate_succ_apply', ih]; simp only [List.replicate_succ, List.cons_append]
lemma volume_rep_append (a : α) (acc : List α) : ∀ j,
volume (List.replicate j a ++ acc) = volume acc + j * (volume a + 1) := by
intro j; induction j with
| zero => simp
| succ j ih => simp only [List.replicate_succ, List.cons_append, volume_cons, ih]; ring
/-- `List.replicate`. -/
def replicate : PR (fun x : ℕ × α => List.replicate x.1 x.2) :=
let step : PR (fun y : α × List α => (y.1, y.1 :: y.2)) := fst.pair cons
let it := step.iterate (fun n => n + n * n) (Poly.id.add (Poly.id.mul Poly.id)) (fun m b j hj => by
rcases b with ⟨a, acc⟩
rw [iter_rep]
simp only [volume_pair, volume_nat, volume_rep_append]
have : j * (volume a + 1) ≤ (2 * m + 1 + (volume a + volume acc + 1) + 1) *
(2 * m + 1 + (volume a + volume acc + 1) + 1) := Nat.mul_le_mul (by omega) (by omega)
omega)
let init : PR (fun x : ℕ × α => (x.1, (x.2, ([] : List α)))) := fst.pair (snd.pair nil)
((init.comp it).comp snd).congr (fun x => by
rcases x with ⟨n, a⟩
simp only [iter_rep, List.append_nil])
end PR
end OPI.W6
end
-- ===== OPI.PRStr =====
section
/-!
# Polynomial realizers: bit strings, interning, node codes
-/
namespace OPI.W6
open OAI.ThreeMachine.StackCompiler QAlgorithms QAlgorithms.OPI QAlgorithms.Complexity
namespace PR
def beqBool : PR (fun p : Bool × Bool => p.1 == p.2) :=
((and.pair (((fst.comp not).pair (snd.comp not)).comp and)).comp or).congr (fun p => by
rcases p with ⟨a, b⟩; cases a <;> cases b <;> rfl)
/-- The step of string comparison. -/
def beqF (b : List Bool × Bool) (a : Bool) : List Bool × Bool :=
(b.1.tail, b.2 && (!b.1.isEmpty && (b.1.headD false == a)))
def beqStep : PR (fun y : Bool × (List Bool × Bool) => beqF y.2 y.1) :=
let ysP : PR (fun y : Bool × (List Bool × Bool) => y.2.1) := snd.comp fst
let hdP : PR (fun y : Bool × (List Bool × Bool) => y.2.1.headD false == y.1) :=
(((ysP.pair (const false)).comp headD).pair fst).comp beqBool
let okP : PR (fun y : Bool × (List Bool × Bool) => y.2.2 && (!y.2.1.isEmpty && (y.2.1.headD false == y.1))) :=
((snd.comp snd).pair (((ysP.comp isCons).pair hdP).comp and)).comp and
((ysP.comp tail).pair okP).congr (fun _ => rfl)
lemma beq_fold (xs : List Bool) : ∀ (ys : List Bool) (ok : Bool),
xs.foldl beqF (ys, ok) = (ys.drop xs.length, ok && decide (xs = ys.take xs.length)) := by
induction xs with
| nil => intro ys ok; simp
| cons x xs ih =>
intro ys ok
rw [List.foldl_cons, ih]
cases ys with
| nil =>
simp only [beqF, List.tail_nil, List.isEmpty_nil, Bool.not_true, Bool.false_and, Bool.and_false,
List.drop_nil, List.take_nil, List.length_cons]
simp
| cons y ys =>
simp only [beqF, List.tail_cons, List.isEmpty_cons, Bool.not_false, List.headD_cons, Bool.true_and,
List.length_cons, List.drop_succ_cons, List.take_succ_cons]
rw [Bool.and_assoc]
congr 2
by_cases hxy : x = y
· subst hxy; simp
· have : (y == x) = false := by simpa using Ne.symm hxy
rw [this]; simp [hxy]
/-- Equality of bit strings. -/
def beqStr : PR (fun x : List Bool × List Bool => decide (x.1 = x.2)) :=
let r : PR (fun x : List Bool × List Bool => x.1.foldl beqF (x.2, true)) :=
((fst.pair (snd.pair (const true))).comp
(beqStep.fold (fun n => n + 3 * n) (Poly.id.add (Poly.smul 3 Poly.id))
(hacc_add (F := fun y : Bool × (List Bool × Bool) => beqF y.2 y.1) 3 (fun a b => by
rcases b with ⟨ys, ok⟩
have := volume_bool ok
have := volume_bool (ok && (!ys.isEmpty && (ys.headD false == a)))
have : volume ys.tail ≤ volume ys := by
cases ys <;> simp only [List.tail_nil, List.tail_cons, volume_cons] <;> omega
simp only [beqF, volume_pair]; omega)))).congr (fun _ => rfl)
let fin : PR (fun r : List Bool × Bool => r.2 && r.1.isEmpty) :=
((snd.pair ((fst.comp isCons).comp not)).comp and).congr (fun r => by simp only [Bool.not_not])
(r.comp fin).congr (fun x => by
rcases x with ⟨xs, ys⟩
simp only [beq_fold, Bool.true_and]
by_cases h : xs = ys
· subst h; simp
· have : ¬ (xs = ys.take xs.length ∧ ys.drop xs.length = []) := by
rintro ⟨h1, h2⟩
apply h
rw [← List.take_append_drop xs.length ys, h2, List.append_nil, ← h1]
rw [decide_eq_false h]
cases h1 : decide (xs = List.take xs.length ys)
· rfl
· have e1 : xs = ys.take xs.length := of_decide_eq_true h1
have e2 : ys.drop xs.length ≠ [] := fun e => this ⟨e1, e⟩
rw [Bool.true_and]
cases h2 : ys.drop xs.length with
| nil => exact absurd h2 e2
| cons _ _ => rfl)
/-- The step of the search for a string in a table. -/
def idxF (b : List Bool × Bool × ℕ) (a : List Bool) : List Bool × Bool × ℕ :=
(b.1, b.2.1 || decide (a = b.1), if b.2.1 || decide (a = b.1) then b.2.2 else b.2.2 + 1)
def idxStep : PR (fun y : List Bool × (List Bool × Bool × ℕ) => idxF y.2 y.1) :=
let fP : PR (fun y : List Bool × (List Bool × Bool × ℕ) => y.2.2.1 || decide (y.1 = y.2.1)) :=
(((snd.comp snd).comp fst).pair ((fst.pair (snd.comp fst)).comp beqStr)).comp or
let iP : PR (fun y : List Bool × (List Bool × Bool × ℕ) => y.2.2.2) := (snd.comp snd).comp snd
((snd.comp fst).pair (fP.pair ((fP.pair (iP.pair (iP.comp succ))).comp (choose fst snd)))).congr
(fun _ => rfl)
lemma idx_true (x : List Bool) : ∀ (T : List (List Bool)) (i : ℕ), T.foldl idxF (x, true, i) = (x, true, i) := by
intro T; induction T with
| nil => intro i; rfl
| cons t T ih => intro i; rw [List.foldl_cons]; exact ih i
lemma idx_fold (x : List Bool) : ∀ (T : List (List Bool)) (i : ℕ),
T.foldl idxF (x, false, i) = (x, decide (x ∈ T), i + T.idxOf x) := by
intro T
induction T with
| nil => intro i; simp
| cons t T ih =>
intro i
rw [List.foldl_cons]
by_cases h : t = x
· subst h
rw [show idxF (t, false, i) t = (t, true, i) by simp [idxF], idx_true]
simp [List.idxOf_cons_self]
· rw [show idxF (x, false, i) t = (x, false, i + 1) by simp [idxF, h], ih (i + 1),
List.idxOf_cons_ne _ h]
simp only [List.mem_cons, Ne.symm h, false_or, Prod.mk.injEq, true_and]
omega
/-- Interning a code. -/
def intern : PR (fun x : List Bool × List (List Bool) => internProgramNode x.1 x.2) :=
let r : PR (fun x : List Bool × List (List Bool) => x.2.foldl idxF (x.1, false, 0)) :=
((snd.pair (fst.pair ((const false).pair (const 0)))).comp
(idxStep.fold (fun n => n + 4 * n) (Poly.id.add (Poly.smul 4 Poly.id))
(hacc_add (F := fun y : List Bool × (List Bool × Bool × ℕ) => idxF y.2 y.1) 4 (fun a b => by
rcases b with ⟨x, f, i⟩
have := volume_bool f; have := volume_bool (f || decide (a = x)); have := volume_pos a
simp only [idxF, volume_pair, volume_nat]; split_ifs <;> omega)))).congr (fun _ => rfl)
-- context (r, x)
let ctx : PR (fun x : List Bool × List (List Bool) => (x.2.foldl idxF (x.1, false, 0), x)) := r.pair id
let idxP : PR (fun c : (List Bool × Bool × ℕ) × (List Bool × List (List Bool)) => c.1.2.2) :=
fst.comp (snd.comp snd)
let memP : PR (fun c : (List Bool × Bool × ℕ) × (List Bool × List (List Bool)) => c.1.2.1) :=
fst.comp (snd.comp fst)
let TP : PR (fun c : (List Bool × Bool × ℕ) × (List Bool × List (List Bool)) => c.2.2) := snd.comp snd
let appP : PR (fun c : (List Bool × Bool × ℕ) × (List Bool × List (List Bool)) => c.2.2 ++ [c.2.1]) :=
(TP.pair (((snd.comp fst).pair nil).comp cons)).comp append
(ctx.comp (idxP.pair ((memP.pair (TP.pair appP)).comp (choose fst snd)))).congr (fun x => by
rcases x with ⟨c, T⟩
simp only [idx_fold, Nat.zero_add]
unfold internProgramNode
by_cases hc : c ∈ T
· simp [hc]
· simp [hc, List.idxOf_eq_length hc])
def encNatP : PR (fun k : ℕ => encNat k) :=
(((((id.pair (const true)).comp replicate).pair (const [false])).comp append)).congr (fun k => rfl)
def serWords : PR (fun w : List ℕ => serializeWords w) :=
((id.pair (const ())).comp ((fst.comp encNatP : PR (fun y : ℕ × Unit => encNat y.1)).flatMap)).congr
(fun w => by simp [serializeWords, List.flatMap])
def codeIP : PR (fun x : INode × List ℕ => codeI x.1 x.2) :=
((((fst.comp fst).pair ((((fst.comp snd).comp fst).pair snd).comp append)).comp cons).comp
serWords).congr (fun x => rfl)
end PR
end OPI.W6
end
Source
Formalization of Theorem 7.4 (algorithmic part), repository https://github.com/sragavan99/lean-prove2me-fills/blob/db81d0d4e3fa008609ed37789a2eb2f6f08ee48d/Definitions/Def_TwoFoldOPI_CL_Part02.lean