Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Reversible adder: g←g+x mod 2∣g∣g \leftarrow g + x \bmod 2^{|g|}g←g+xmod2∣g∣

Proved
OPI.addInto_spec

by sragavan · Nov 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

lean-formalizationquantum-algorithmstwo-fold-opi-construction

Bit configurations z∈{0,1}Nz\in\{0,1\}^Nz∈{0,1}N of NNN wires are acted on by reversible circuits of X, CNOT and Toffoli gates. A register is a list of distinct wires read most significant bit first; valr(z)\mathrm{val}_r(z)valr​(z) denotes its value. The circuit addInto(a,g,x)\mathrm{addInto}(a, g, x)addInto(a,g,x) adds the register xxx into the register ggg: for each bit xkx_kxk​ of xxx (of weight 2ek2^{e_k}2ek​) it applies an increment of the top ∣g∣−ek|g| - e_k∣g∣−ek​ wires of ggg controlled on xkx_kxk​, using the wires aaa as ancillas.

Statement. Let xxx, ggg, aaa be registers with ∣x∣≤∣g∣|x| \le |g|∣x∣≤∣g∣, ∣g∣+1≤∣a∣+2|g| + 1 \le |a| + 2∣g∣+1≤∣a∣+2, and with all wires of xxx, ggg, aaa pairwise distinct. For every configuration zzz in which all ancillas are 000, the resulting configuration z′=addInto(a,g,x)(z)z' = \mathrm{addInto}(a,g,x)(z)z′=addInto(a,g,x)(z) agrees with zzz on every wire outside ggg (so xxx is preserved and the ancillas are returned to 000), and

valg(z′)=(valg(z)+valx(z)) mod 2∣g∣.\mathrm{val}_g(z') = \big(\mathrm{val}_g(z) + \mathrm{val}_x(z)\big) \bmod 2^{|g|}.valg​(z′)=(valg​(z)+valx​(z))mod2∣g∣.

The adder is the arithmetic core of the phase-kickback circuit: adding a value vvv into the phase-gradient register ∣Gb⟩|G_b\rangle∣Gb​⟩ multiplies the state by e2πiv/2be^{2\pi i v/2^b}e2πiv/2b, which is how the construction implements its table phases and the phase steps of the QFTq\mathrm{QFT}_qQFTq​ gadgets.

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 : ℕ}
Formal statement
theorem OPI.addInto_spec (as gs : List (Fin N)) : ∀ xs : List (Fin N),
    xs.length ≤ gs.length → 1 + gs.length ≤ as.length + 2 → (xs ++ gs ++ as).Nodup →
    ∀ z : Qubits N, (∀ x ∈ as, z x = false) →
      (∀ x, x ∉ gs → revAct (addInto as gs xs) z x = z x) ∧
      regVal gs (revAct (addInto as gs xs) z) = (regVal gs z + regVal xs z) % 2 ^ gs.length := by sorry
Source
Formalization of Theorem 7.4 (algorithmic part), repository https://github.com/sragavan99/lean-prove2me-fills/blob/db81d0d4e3fa008609ed37789a2eb2f6f08ee48d/WorkInProgress/QuantumOPIVariants/OPI/Adder.lean#L96-L141

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