A list of controlled modular shifts adds up to one shift by the controlled sum
ProvedOPI.csList_specWork with classical bit configurations . Let be a register of qubits holding a residue modulo in binary (most significant bit first), with . For , the modular shift maps a -bit string of value to the binary expansion of , and fixes strings of value .
is a reversible circuit built from a list of pairs (control qubit , amount ). For each pair it applies the in-place gadget "if , shift by ", implemented by table lookups with a scratch register ( qubits), ancillas and a flag .
Statement. Assume , , the wires of are pairwise distinct, and no control qubit lies among them. If , and are in , then
and all other wires, including the controls and the scratch, are unchanged.
With the controls being the qubits of a register and amounts , the sum is the value of . The circuit is then the controlled power used in phase estimation inside the gadget.
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 Matrix
variable {n : ℕ}
theorem OPI.csList_spec (p w : ℕ) (hp : 0 < p) (hpw : p ≤ 2 ^ w) (Bl Z as : List (Fin n))
(f : Fin n) (hBl : Bl.length = w) (hZ : Z.length = w) (has : 1 + w ≤ as.length + 2)
(hnd : (Bl ++ Z ++ as ++ [f]).Nodup) :
∀ L : List (Fin n × ℕ), (∀ ck ∈ L, ck.1 ∉ Bl ++ Z ++ as ++ [f]) →
∀ z : Qubits n, (∀ a ∈ Z ++ as ++ [f], z a = false) →
revAct (csList p w Bl Z as f L) z =
writeReg Bl (shiftL p w (L.map fun ck => if z ck.1 then ck.2 else 0).sum (Bl.map z)) z := by sorry