Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Register layout for an injective classical string program

Definition
InfoLossLAR_ReversibleStringInjection

by BoomShaKaLaaaKa · Nov 21, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexityquantum-computing

The circuit uses registers for the original string, its padded image, and workspaces for a forward program and a proposed inverse. The forward oracle writes the output into a fresh register. Exchanging the roles of the two data registers in the inverse oracle provides a circuit for restoring the original register to zero. The layout also specifies the canonical computational basis states at the input and output.

Definition code
import Definitions.Def_InfoLossLAR_LoadedBatchBundle_01
import Definitions.Def_InfoLossLAR_RegevSearch_PhysicalFourierReadout
import Definitions.Def_QAlgorithms_Defs_Measurement
import Definitions.Def_ShorAlgorithms_QFT_Circuit

set_option autoImplicit false
set_option backward.isDefEq.respectTransparency false

section

noncomputable section

namespace InfoLossLAR.WorstCase.NativeWordLayout

open QAlgorithms QAlgorithms.Complexity FiniteGateTransport

open TM2Boolean TM2Boolean.PolyProgramCircuit CodeGenerator

open OAI.MetricKMedian.Binary OAI.MetricKMedian.Binary.Automatic

open Integration9_9.TM2PolynomialBudget

variable {f : Str → Str} (P : PolyProgram id id f) (p : Polynomial ℕ)

def width (n : ℕ) : ℕ := n+((compiled P n).ops.length+1)

end InfoLossLAR.WorstCase.NativeWordLayout

end

end

section

noncomputable section

namespace InfoLossLAR.WorstCase.NativeWordCoherent

open QAlgorithms QAlgorithms.Complexity FiniteGateTransport

open scoped BigOperators

/-- Append arbitrary data/reference wires; original instruction addresses
remain fixed and every CNOT control/target remains distinct. -/
def extendInstr (k : ℕ) {W : ℕ} : Instr W → Instr (W+k)
  | .h i => .h (i.castAdd k)
  | .s i => .s (i.castAdd k)
  | .t i => .t (i.castAdd k)
  | .x i => .x (i.castAdd k)
  | .cnot i j h => .cnot (i.castAdd k) (j.castAdd k) (by intro he;exact h (Fin.castAdd_inj.mp he))

def extendCircuit (k : ℕ) {W : ℕ} (gates : Layered W) : Layered (W+k) :=
  gates.map (List.map (extendInstr k))

end InfoLossLAR.WorstCase.NativeWordCoherent

end

end

section

noncomputable section

namespace InfoLossLAR.WorstCase.CoherentClassicalOracle

open QAlgorithms QAlgorithms.Complexity CoherentComputeUncompute NativeWordCoherent NativeWordLayout

open TM2Boolean TM2Boolean.PolyProgramCircuit

open OAI.MetricKMedian.Binary

open scoped BigOperators

variable {f : Str → Str} (P : PolyProgram id id f)

def controls (n : ℕ) (i : Fin (capacity P n)) : Fin (width P n) := outputWire P n i (some true)

def base (n : ℕ) : Layered (width P n) := PolyProgramCircuit.circuit P n

def fullCircuit (n : ℕ) : Layered (width P n+capacity P n) :=
  extendCircuit (capacity P n) (base P n)++CoherentXorCopy.circuit (controls P n)++
    extendCircuit (capacity P n) (inverseCircuit (base P n))

end InfoLossLAR.WorstCase.CoherentClassicalOracle

end

end

section

noncomputable section

namespace InfoLossLAR.WorstCase.CoherentClassicalOracle

open QAlgorithms QAlgorithms.Complexity CoherentComputeUncompute NativeWordCoherent NativeWordLayout

open TM2Boolean TM2Boolean.PolyProgramCircuit

open OAI.MetricKMedian.Binary

variable {f : Str → Str} (P : PolyProgram id id f)

def paddedOutput (word : Str) : Str :=
  List.ofFn (fun i : Fin (capacity P word.length) => wordExtension (f word) i.val)

end InfoLossLAR.WorstCase.CoherentClassicalOracle

end

end

section

namespace InfoLossLAR.WorstCase.CoherentInjection

open QAlgorithms.Complexity FiniteGateTransport

/-- Physical order: padded original input, forward output, forward machine
workspace, inverse machine workspace. Both machine workspaces are retained. -/
def width (x y a b : ℕ) := x+y+a+b

def forwardWires (n x y a b : ℕ) (hn : n ≤ x) : Fin (n+a+y) ↪ Fin (width x y a b) where
  toFun i :=
    if h : i.val<n then ⟨i.val,by unfold width;omega⟩
    else if h' : i.val<n+a then ⟨x+y+(i.val-n),by unfold width;omega⟩
    else ⟨x+(i.val-(n+a)),by unfold width;omega⟩
  inj' := by
    intro i j he
    have hv := congrArg Fin.val he
    simp only at hv
    split_ifs at hv <;> simp_all only <;> apply Fin.ext <;> omega

def backwardWires (x y a b : ℕ) : Fin (y+b+x) ↪ Fin (width x y a b) where
  toFun i :=
    if h : i.val<y then ⟨x+i.val,by unfold width;omega⟩
    else if h' : i.val<y+b then ⟨x+y+a+(i.val-y),by unfold width;omega⟩
    else ⟨i.val-(y+b),by unfold width;omega⟩
  inj' := by
    intro i j he
    have hv := congrArg Fin.val he
    simp only at hv
    split_ifs at hv <;> simp_all only <;> apply Fin.ext <;> omega

def dataBits {x y a b : ℕ} (old : Bits x) (fresh : Bits y) : Bits (width x y a b) :=
  fun i => if hx : i.val<x then old ⟨i.val,hx⟩
    else if hy : i.val<x+y then fresh ⟨i.val-x,by omega⟩ else false

end InfoLossLAR.WorstCase.CoherentInjection

end

section

noncomputable section

namespace InfoLossLAR.WorstCase.CoherentInjection

open QAlgorithms QAlgorithms.Complexity CoherentComputeUncompute FiniteGateTransport

open TM2Boolean TM2Boolean.PolyProgramCircuit

open OAI.MetricKMedian.Binary

open scoped BigOperators

variable {f g : Str → Str} (P : PolyProgram id id f) (Q : PolyProgram id id g)

abbrev outputSize (n : ℕ) := capacity P n

abbrev originalSize (n : ℕ) := capacity Q (outputSize P n)

abbrev forwardWork (n : ℕ) := (compiled P n).ops.length+1

abbrev backwardWork (n : ℕ) := (compiled Q (outputSize P n)).ops.length+1

abbrev totalWidth (n : ℕ) := width (originalSize P Q n) (outputSize P n) (forwardWork P n) (backwardWork P Q n)

def firstWires (n : ℕ) : Fin (NativeWordLayout.width P n+capacity P n) ↪ Fin (totalWidth P Q n) :=
  forwardWires n (originalSize P Q n) (outputSize P n) (forwardWork P n) (backwardWork P Q n)
    (by simp only [originalSize,outputSize,capacity]; omega)

def secondWires (n : ℕ) : Fin (NativeWordLayout.width Q (outputSize P n)+capacity Q (outputSize P n)) ↪ Fin (totalWidth P Q n) :=
  backwardWires (originalSize P Q n) (outputSize P n) (forwardWork P n) (backwardWork P Q n)

def firstCircuit (n : ℕ) : Layered (totalWidth P Q n) :=
  relocateCircuit (firstWires P Q n) (CoherentClassicalOracle.fullCircuit P n)

def secondCircuit (n : ℕ) : Layered (totalWidth P Q n) :=
  relocateCircuit (secondWires P Q n) (CoherentClassicalOracle.fullCircuit Q (outputSize P n))

def circuit (n : ℕ) : Layered (totalWidth P Q n) := firstCircuit P Q n++secondCircuit P Q n

end InfoLossLAR.WorstCase.CoherentInjection

end

end

section

noncomputable section

namespace InfoLossLAR.WorstCase.CoherentInjection

open QAlgorithms QAlgorithms.Complexity CoherentComputeUncompute FiniteGateTransport

open TM2Boolean TM2Boolean.PolyProgramCircuit

open OAI.MetricKMedian.Binary

open scoped BigOperators

variable {f g : Str → Str} (P : PolyProgram id id f) (Q : PolyProgram id id g)

def inputBitsAt (n : ℕ) (word : Str) : Bits (totalWidth P Q n) :=
  dataBits (fun i => wordExtension word i.val) (fun _ => false)

def finalBitsAt (n : ℕ) (word : Str) : Bits (totalWidth P Q n) :=
  dataBits (fun _ => false) (fun i => wordExtension (f word) i.val)

variable {I : Type*} [Fintype I]

end InfoLossLAR.WorstCase.CoherentInjection

end

end
Source
Register layout used by the reversible machine stage of https://prove2.me/theorems/d106aba4-0ad7-4239-9c6b-4a9dc8c9ebc4

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me