Correctness of the reversible table-lookup circuit
ProvedOPI.lookup_specLet (address), (data) and (ancillas) be lists of wires and a flag wire in an -bit register. Assume the wires of are pairwise distinct and . A table is a list of rows of bit lists, and every pattern is assumed to have length .
The circuit handles the rows in order. For each row it flips iff holds (X gates on the zero positions of , a multi-controlled NOT into , and the X gates again). It then XORs into with CNOTs controlled by , and finally flips back.
Statement. For every bit string with and all ancillas , the circuit maps to
i.e. the configuration obtained from by XOR-ing into , in table order, the data of every row whose pattern equals the current address . All other wires (address, ancillas, flag) are unchanged.
Lookups are the basic reversible primitive behind the function tables, the in-place permutation gadgets, the table phases and the repeat-until-success membership tests of the construction.
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.lookup_spec (xs ys as : List (Fin N)) (f : Fin N)
(hlen : xs.length ≤ as.length + 2) (hnd : (xs ++ ys ++ as ++ [f]).Nodup) :
∀ (T : List (List Bool × List Bool)), (∀ e ∈ T, e.1.length = xs.length) →
∀ z : Qubits N, z f = false → (∀ a ∈ as, z a = false) →
revAct (lookup xs ys as f T) z = xorAll ys T (xs.map z) z := by sorry