The gadget circuit maps to
ProvedOPI.eCirc_speclean-formalizationquantum-algorithmstwo-fold-opi-construction
On qubits consider two registers , of equal length, a control qubit , a flag , a scratch list with , and ancillas with . All these wires are pairwise distinct. The circuit is
where the controlled swap and the zero test are reversible circuits of X/CNOT/Toffoli gates using , and as workspace. Let denote the permutation of basis configurations exchanging the contents of and .
Statement. Let be a state (any complex function on ) such that every configuration with has , all zero, not all zero, and , , all zero. Then
In ket notation, for , with all workspace returned clean. This is the gadget of Appendix A.3; the symbol-level form eGad_J is derived from it.
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 Matrix
variable {N : ℕ}
variable (S T Z as : List (Fin N)) (a f : Fin N)
variable (hnd : ([a] ++ (S ++ T) ++ Z ++ as ++ [f]).Nodup) (hST : S.length = T.length)
(hZ : (S ++ T).length = Z.length) (hlen : 1 + (S ++ T).length ≤ as.length + 2)
include hnd hST hZ hlen
Formal statement
theorem OPI.eCirc_spec (g : Qubits N → ℂ)
(hg : ∀ z, g z ≠ 0 → z a = false ∧ T.map z = List.replicate T.length false ∧
S.map z ≠ List.replicate S.length false ∧ EClean Z as f z) :
(Circuit.unitary (eCirc S T Z as a f)).mulVec g =
((Real.sqrt 2 : ℂ))⁻¹ • (g - g ∘ swapST S T) := by sorrySource
Formalization of Theorem 7.4 (algorithmic part), repository https://github.com/sragavan99/lean-prove2me-fills/blob/db81d0d4e3fa008609ed37789a2eb2f6f08ee48d/WorkInProgress/QuantumOPIVariants/OPI/EGad.lean#L192-L298