Phase kickback from any reversible circuit that adds a value into the phase-gradient register
ProvedOPI.kick_of_eqlean-formalizationquantum-algorithmstwo-fold-opi-construction
Let be a -qubit register inside an -qubit system, and let be the phase-gradient state on . Let be a list of reversible gates (X, CNOT, Toffoli), compiled into a Clifford+T circuit . Let cl be a list of wires outside (clean ancillas), and let assign a natural number to every configuration of the qubits outside . Assume:
- for every basis configuration with all wires of
clequal to , maps to the configuration obtained by adding to the value of modulo , leaving every other wire unchanged; - is a vector on the qubits outside that vanishes on configurations where some wire of
clis .
Then
The gradient register is unchanged, and each branch acquires the phase . This turns arithmetic circuits (adders, table lookups) into phase gates. In the algorithm it implements the phases and the phases inside the QFT gadgets, using the gradient register as a catalyst.
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 b : ℕ}
Formal statement
theorem OPI.kick_of_eq (w : Fin b ↪ Fin N) (L : List (RGate N)) (cl : List (Fin N))
(hcl : ∀ a ∈ cl, a ∉ Set.range w) (v : (Outside w → Bool) → ℕ)
(hL : ∀ z, Clean cl z → revAct L z = kickEquiv w v z)
(ψ : (Outside w → Bool) → ℂ) (hψ : CleanOn w cl ψ) :
(Circuit.unitary (revCirc L)).mulVec (withGrad w ψ) =
withGrad w (fun o => kickPhase b (v o) * ψ o) := by sorrySource
Formalization of Theorem 7.4 (algorithmic part), repository https://github.com/sragavan99/lean-prove2me-fills/blob/db81d0d4e3fa008609ed37789a2eb2f6f08ee48d/WorkInProgress/QuantumOPIVariants/OPI/KickGen.lean#L14-L60