Controlled addition of to a register by incrementing its top bits
ProvedOPI.incr_topWe work with classical bit configurations of wires, on which reversible circuits of X, CNOT and Toffoli gates act. A register is a list of distinct wires read most significant bit first, with value . The circuit increments the register by one modulo , controlled on the wire , using the list as ancilla wires for its multi-controlled NOT gates.
Let and apply the controlled increment only to the top wires of . Assume (enough ancillas), that the wires of , , are pairwise distinct, and that all ancillas are in . Writing for the resulting configuration, the statement says that every wire outside is unchanged (so the control is preserved and the ancillas are returned clean), and
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.
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_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