In-place permutation gadget: two lookups and a register swap compute
ProvedOPI.permGad_speclean-formalizationquantum-algorithmstwo-fold-opi-construction
Let (controls), (target register), (scratch register, ) and (ancillas) be lists of wires and a flag wire of an -bit register. Assume all these wires are pairwise distinct and . Let be functions taking a control pattern and a register pattern to a bit list. The gadget consists of:
- a function-table lookup ;
- a lookup ;
- a bitwise swap of and (three CNOTs per pair).
Statement. Let be a bit string with flag, ancillas and scratch all . Write and , and assume and . Then
the register is overwritten by , and every other wire, including the scratch, ancillas and flag, keeps its value.
If is a permutation with inverse , the gadget implements it in place with clean scratch. It is used for the in-place field operations of the construction, such as , the linear map , and the multiplications of the gradient preparation.
Preamble
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 : ℕ}
Formal statement
theorem OPI.permGad_spec (cs B Z as : List (Fin N)) (f : Fin N)
(F Finv : List Bool → List Bool → List Bool)
(hnd : (cs ++ B ++ Z ++ as ++ [f]).Nodup) (hBZ : B.length = Z.length)
(hlen : cs.length + B.length ≤ as.length + 2)
(z : Qubits N) (hzf : z f = false) (hz : ∀ a ∈ as, z a = false)
(hZ : ∀ a ∈ Z, z a = false)
(hF : (F (cs.map z) (B.map z)).length = B.length)
(hinv : Finv (cs.map z) (F (cs.map z) (B.map z)) = B.map z) :
revAct (permGad cs B Z as f F Finv) z = writeReg B (F (cs.map z) (B.map z)) z := by sorrySource
Formalization of Theorem 7.4 (algorithmic part), repository https://github.com/sragavan99/lean-prove2me-fills/blob/db81d0d4e3fa008609ed37789a2eb2f6f08ee48d/WorkInProgress/QuantumOPIVariants/OPI/Perm.lean#L228-L329