Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Controlled addition of 2e2^e2e to a register by incrementing its top bits

Proved
OPI.incr_top

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

lean-formalizationquantum-algorithmstwo-fold-opi-construction

We work with classical bit configurations z∈{0,1}Nz \in \{0,1\}^Nz∈{0,1}N of NNN wires, on which reversible circuits of X, CNOT and Toffoli gates act. A register is a list of distinct wires g=(g1,…,gn)g = (g_1,\dots,g_n)g=(g1​,…,gn​) read most significant bit first, with value valg(z)=∑kzgk2n−k\mathrm{val}_g(z)=\sum_{k} z_{g_k}2^{n-k}valg​(z)=∑k​zgk​​2n−k. The circuit incr([c],a,r)\mathrm{incr}([c], a, r)incr([c],a,r) increments the register rrr by one modulo 2∣r∣2^{|r|}2∣r∣, controlled on the wire ccc, using the list aaa as ancilla wires for its multi-controlled NOT gates.

Let 0≤e≤n=∣g∣0 \le e \le n = |g|0≤e≤n=∣g∣ and apply the controlled increment only to the top n−en-en−e wires of ggg. Assume n+1≤∣a∣+2n+1 \le |a| + 2n+1≤∣a∣+2 (enough ancillas), that the wires of [c][c][c], ggg, aaa are pairwise distinct, and that all ancillas are 000 in zzz. Writing z′z'z′ for the resulting configuration, the statement says that every wire outside ggg is unchanged (so the control is preserved and the ancillas are returned clean), and

valg(z′)={(valg(z)+2e) mod 2nif zc=1,valg(z)if zc=0.\mathrm{val}_g(z') = \begin{cases} (\mathrm{val}_g(z) + 2^e) \bmod 2^{n} & \text{if } z_c = 1,\\ \mathrm{val}_g(z) & \text{if } z_c = 0.\end{cases}valg​(z′)={(valg​(z)+2e)mod2nvalg​(z)​if zc​=1,if zc​=0.​

This lemma is the single-bit step of the ripple adder addInto (adding one bit of a summand at its correct weight). Through addInto it enters the phase-kickback circuit into the gradient register, and it is also used directly in the in-place multiplications of the gradient-state preparation.

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.incr_top (as gs : List (Fin N)) (c : Fin N) (e : ℕ) (he : e ≤ gs.length)
    (hlen : 1 + gs.length ≤ as.length + 2) (hnd : ([c] ++ gs ++ as).Nodup) (z : Qubits N)
    (hz : ∀ x ∈ as, z x = false) :
    (∀ x, x ∉ gs → revAct (incr [c] as (gs.take (gs.length - e))) z x = z x) ∧
    regVal gs (revAct (incr [c] as (gs.take (gs.length - e))) z) =
      if z c then (regVal gs z + 2 ^ e) % 2 ^ gs.length else regVal gs z := 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#L53-L94

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