The Hadamard test with a controlled acts diagonally on increment eigenvectors
ProvedOPI.hTest_speclean-formalizationquantum-algorithmstwo-fold-opi-construction
Let be a -qubit register inside an -qubit system, a control qubit outside , and as a list of ancilla wires with , where , the wires of and the ancillas are pairwise distinct. Let and . For put on ( read as a number), and let be a vector on the qubits outside that vanishes whenever or some ancilla is .
The Hadamard-test circuit applies to , then the reversible incrementer that adds to modulo when (using the ancillas), then on , then on . With the test phase
the theorem states
The register stays in , and the outcome on has amplitudes .
This is the basic step of the phase-gradient preparation. Measuring reveals information on the bits of the eigen-label without disturbing the label, so different labels never interfere.
Preamble
import Definitions.Def_TwoFoldOPI_CL_Part03
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 {b : ℕ}
variable {N : ℕ}
Formal statement
theorem OPI.hTest_spec (w : Fin b ↪ Fin N) (c : Fin N) (hc : c ∉ Set.range w) (as : List (Fin N))
(e k : ℕ) (he : e ≤ b) (hlen : 1 + b ≤ as.length + 2) (hnd : ([c] ++ List.ofFn w ++ as).Nodup)
(x : ℕ) (ψ : (Outside w → Bool) → ℂ) (hψc : ∀ o, o ⟨c, hc⟩ = true → ψ o = 0)
(hψ : CleanOn w as ψ) :
(Circuit.unitary (hTest w c as e k)).mulVec (withEig w x ψ) =
withEig w x (fun o => (if o ⟨c, hc⟩ then (1 - testPhase b x e k) / 2
else (1 + testPhase b x e k) / 2) * ψ (Function.update o ⟨c, hc⟩ false)) := by sorrySource
Formalization of Theorem 7.4 (algorithmic part), repository https://github.com/sragavan99/lean-prove2me-fills/blob/db81d0d4e3fa008609ed37789a2eb2f6f08ee48d/WorkInProgress/QuantumOPIVariants/OPI/GradPrep.lean#L238-L309