Correctness of the multi-controlled reversible increment modulo
ProvedOPI.incr_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, with value . The circuit is defined recursively: for it first flips controlled on all wires of and of (a multi-controlled NOT built from Toffolis with the ancilla wires ), and then recursively runs .
Statement. Let (controls), (ancillas) and (target) be wire lists with , and suppose the concatenation has no repeated wire. For every configuration whose ancillas are all , the configuration produced by the circuit agrees with on all wires outside , and
The controlled increment is the basic arithmetic gadget of the construction: it is the step of the ripple adder used for phase kickback into the gradient register, and the operation whose powers are tested during the preparation of the phase-gradient state.
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.incr_spec (cs as : List (Fin N)) : ∀ (r : List (Fin N)),
cs.length + r.length ≤ as.length + 2 → (cs ++ r ++ as).Nodup →
∀ z : Qubits N, (∀ x ∈ as, z x = false) →
(∀ x, x ∉ r → revAct (incr cs as r) z x = z x) ∧
regVal r (revAct (incr cs as r) z) =
if (cs.all fun c => z c) then (regVal r z + 1) % 2 ^ r.length else regVal r z := by sorry