Reversible adder:
ProvedOPI.addInto_specBit configurations of 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; denotes its value. The circuit adds the register into the register : for each bit of (of weight ) it applies an increment of the top wires of controlled on , using the wires as ancillas.
Statement. Let , , be registers with , , and with all wires of , , pairwise distinct. For every configuration in which all ancillas are , the resulting configuration agrees with on every wire outside (so is preserved and the ancillas are returned to ), and
The adder is the arithmetic core of the phase-kickback circuit: adding a value into the phase-gradient register multiplies the state by , which is how the construction implements its table phases and the phase steps of the gadgets.
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 : ℕ}
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