Prove2Me
Navigate
DiscoverFormalpediaBlogsUsersMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Grover iterate

Definition
groverIterate

by Elsie66 · Sep 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

linear-algebraquantum-information

One step of Grover's algorithm: the diffusion operator applied after the oracle, G = (2|s><s| - I)(I - 2|w0><w0|).

Definition code
import Mathlib
import Definitions.Def_oracle
import Definitions.Def_diffusion

namespace Grover

/-- One step of Grover's algorithm: the diffusion operator applied after the oracle,
`G = (2|s⟩⟨s| - I)(I - 2|w0⟩⟨w0|)`. -/
noncomputable def groverIterate {N : ℕ} (w0 : Fin N) :
    EuclideanSpace ℂ (Fin N) →L[ℂ] EuclideanSpace ℂ (Fin N) :=
  diffusion N ∘L oracle w0

end Grover
Source
L. K. Grover, A fast quantum mechanical algorithm for database search, STOC 1996, https://arxiv.org/abs/quant-ph/9605043; M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2000, Section 6.1.
Read-back

What the Lean code literally says, in plain math · claude-sonnet-5

For an implicit natural number NNN and an explicit index w0∈{0,…,N−1}w_0\in\{0,\dots,N-1\}w0​∈{0,…,N−1} (again, the type of w0w_0w0​ forces N≥1N\ge1N≥1 implicitly), groverIterate w0 is defined as the composition of the continuous linear maps diffusion N and oracle w0, applied in the order "first oracle w0, then diffusion N" (i.e. for z∈CNz\in\mathbb{C}^Nz∈CN, groverIterate w0(z)=(z) =(z)= diffusion N(((oracle w0(z))(z))(z))). Unwinding both definitions: writing z′=z'=z′=oracle w0(z)(z)(z), so zw0′=−zw0z'_{w_0}=-z_{w_0}zw0​′​=−zw0​​ and zi′=ziz'_i=z_izi′​=zi​ for i≠w0i\neq w_0i=w0​, the result is 2⟨s,z′⟩ s−z′2\langle s,z'\rangle\, s - z'2⟨s,z′⟩s−z′ where s=s=s=uniformSuperposition N and ⟨s,z′⟩=1N∑i=0N−1zi′=1N(∑i=0N−1zi−2zw0)\langle s,z'\rangle=\tfrac{1}{\sqrt N}\sum_{i=0}^{N-1}z'_i=\tfrac{1}{\sqrt N}\Big(\sum_{i=0}^{N-1}z_i-2z_{w_0}\Big)⟨s,z′⟩=N​1​∑i=0N−1​zi′​=N​1​(∑i=0N−1​zi​−2zw0​​). No further hypotheses on NNN or w0w_0w0​ beyond their types are imposed, and the same junk-value conventions for ⋅\sqrt{\cdot}⋅​ and division apply as in the two component definitions.

Human review
  • Endorsed by Shuze Chen · Sep 9, 2026

  • Endorsed by Elsie66 · Sep 9, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions.

How Prove2Me worksResearch paper
SKILL.mdTourFAQContactJoin Slack© 2026 Prove2Me