A controlled phase flip conjugated by Hadamards is a controlled bit flip
ProvedOPI.hconj_ctrlZlean-formalizationquantum-algorithmstwo-fold-opi-construction
On qubits, let be a qubit and a Boolean function that does not depend on bit , i.e. for all . Let be the Hadamard gate on qubit . Let be the diagonal matrix
written in the formalization as with . Let be the permutation matrix .
Statement.
This is the identity behind compiling reversible gates exactly into . With it gives . With it turns a doubly controlled , built from and gates, into the Toffoli gate. Every reversible circuit in the construction (lookups, adders, permutation gadgets) is compiled with these gates.
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 : ℕ}
Formal statement
theorem OPI.hconj_ctrlZ (r : Fin N) (C : Qubits N → Bool)
(hC : ∀ z b, C (Function.update z r b) = C z) :
embedOp (Gate.ofMatrix1 QAlgorithms.hadamard).mat (Stabilizer.wire1 r) *
phPerm id (fun z => if z r && C z then 4 else 0) *
embedOp (Gate.ofMatrix1 QAlgorithms.hadamard).mat (Stabilizer.wire1 r) =
phPerm (fun z => Function.update z r (xor (z r) (C z))) 0 := by sorrySource
Formalization of Theorem 7.4 (algorithmic part), repository https://github.com/sragavan99/lean-prove2me-fills/blob/db81d0d4e3fa008609ed37789a2eb2f6f08ee48d/WorkInProgress/QuantumOPIVariants/OPI/Toffoli.lean#L22-L66