Table-driven phase by lookup and kickback into a phase gradient
ProvedOPI.tablePhase_catThe qubits are split into system qubits and a -qubit gradient register, which holds the phase-gradient state . Let be a lookup table, a list of pairs (input pattern, output pattern), and let , , , be system wires: input register, scratch register, ancillas and flag. For a system configuration , is the number that a table lookup on input writes into the initially clean register , read in binary. The circuit looks up into , adds into the gradient register, and looks up again.
Statement. Assume all keys of have length , , , , and are pairwise distinct. Then the compiled circuit satisfies with
That is, for every system vector that vanishes unless , , are ,
The gradient state acts as a catalyst: it is returned unchanged.
Table phases implement the multiplication phase in the gadget, rounded to bits, and the phase in the 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 Matrix
variable {N : ℕ}
variable {n b : ℕ}
theorem OPI.tablePhase_cat (xs scr as : List (Fin n)) (f : Fin n)
(T : List (List Bool × List Bool)) (hT : ∀ e ∈ T, e.1.length = xs.length)
(hxl : xs.length ≤ as.length + 2) (hsl : scr.length ≤ b) (hbl : 1 + b ≤ as.length + 2)
(hnd : (xs ++ scr ++ as ++ [f]).Nodup) :
Cat (b := b) (scr ++ as ++ [f]) (revCirc (tablePhaseGates xs scr as f T))
(Matrix.diagonal fun x => kickPhase b
(tableNat (scr.map (Fin.castAdd b)) T (xs.map x))) := by sorry