Correctness of compiling straight-line programs to reversible lookup circuits
ProvedOPI.compile_speclean-formalizationquantum-algorithmstwo-fold-opi-construction
A straight-line program over a value type is a list of instructions acting on environments . Running it () applies the updates in order. Values carry a fixed-length binary encoding with a left inverse. Each identifier has a register of qubits. The compiler turns each instruction into one table lookup that XORs into the destination register, using ancillas and a flag .
Hypotheses.
- Layout up to : for the registers have length , have no repeated wires, are pairwise disjoint, and avoid and .
- Well-formedness (relative to the set of identifiers defined initially): every source is defined, , and the sources of an instruction are distinct; every destination is fresh, , and written by only one instruction.
- Every source register list fits the lookup ancillas: .
- In the input configuration , holds for every ; all destination registers are ; and are .
Statement. After the compiled reversible circuit,
and every wire outside the destination registers is unchanged. In particular, sources and scratch are restored.
This is how the classical relinearization decoder (Gauss–Jordan elimination over , written as a straight-line program) becomes a reversible circuit inside the quantum decoder.
Preamble
import Definitions.Def_TwoFoldOPI_CL_Part01
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
open QAlgorithms
variable {n : ℕ} {V : Type}
Formal statement
theorem OPI.compile_spec (E : Enc V) (reg : ℕ → List (Fin n)) (as : List (Fin n)) (f : Fin n) (N : ℕ)
(hlay : Layout E reg as f N) :
∀ (Is : List (KIns V)) (S : ℕ → Prop) (ρ : ℕ → V) (z : Qubits n), PWF N S Is →
(∀ i, S i → i < N) → (∀ I ∈ Is, I.dst < N) →
(∀ I ∈ Is, I.src.length * E.L ≤ as.length + 2) →
Encodes E reg S ρ z → (∀ I ∈ Is, ∀ a ∈ reg I.dst, z a = false) →
(∀ a ∈ as ++ [f], z a = false) →
Encodes E reg (fun i => S i ∨ ∃ I ∈ Is, I.dst = i) (kRun Is ρ) (revAct (compile E reg as f Is) z) ∧
(∀ a, (∀ I ∈ Is, a ∉ reg I.dst) → revAct (compile E reg as f Is) z a = z a) := by sorrySource
Formalization of Theorem 7.4 (algorithmic part), repository https://github.com/sragavan99/lean-prove2me-fills/blob/db81d0d4e3fa008609ed37789a2eb2f6f08ee48d/WorkInProgress/QuantumOPIVariants/OPI/SSA.lean#L105-L190