Linear recursion preserves polynomial-time realizability
ProvedOPI.W6.IsPR.linreclean-formalizationquantum-algorithmstwo-fold-opi-construction
A function between encodable types is polynomially realizable () if it has a realizer in the stack-machine model used for the Cook–Levin packaging, whose running time (charge) and output size are both bounded by a monotone polynomial in the size ("volume") of the input.
Suppose satisfies the linear recursion
where the following hold:
- , , , and are polynomially realizable;
- the measure decreases: whenever is not a base case;
- does not increase size: ;
- for some polynomial bound : and .
Then is polynomially realizable.
This is the general tool used to show that the recursive circuit builders (multi-controlled NOT ladders, lookups, zips, and similar) have polynomial realizers. That is a step in proving that the program generator of the algorithm runs in polynomial time.
Preamble
import Definitions.Def_TwoFoldOPI_CL_Part03
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
variable {α β γ δ : Type} [Coding α] [Coding β] [Coding γ] [Coding δ]
Formal statement
theorem OPI.W6.IsPR.linrec {f : α → β} {μ : α → ℕ} {isBase : α → Bool} {base : α → β} {next : α → α}
{wrap : α → β → β} (hμ : IsPR μ) (hb : IsPR isBase) (hbase : IsPR base) (hnext : IsPR next)
(hwrap : IsPR (fun p : α × β => wrap p.1 p.2))
(hdec : ∀ x, isBase x = false → μ (next x) < μ x) (hnv : ∀ x, volume (next x) ≤ volume x)
(D : ℕ → ℕ) (hD : Poly D) (hbv : ∀ x, volume (base x) ≤ D (volume x))
(hwv : ∀ x r, volume (wrap x r) ≤ volume r + D (volume x))
(hf : ∀ x, f x = if isBase x then base x else wrap x (f (next x))) : IsPR f := by sorrySource
Formalization of Theorem 7.4 (algorithmic part), repository https://github.com/sragavan99/lean-prove2me-fills/blob/db81d0d4e3fa008609ed37789a2eb2f6f08ee48d/WorkInProgress/QuantumOPIVariants/OPI/LinRec.lean#L57-L102