Module grover 

Grover’s unstructured search algorithm.

Given a black-box oracle that marks a subset of computational-basis states |w⟩ (the “solutions”) out of N = 2^n items, Grover’s algorithm finds a marked item with high probability using only Θ(√(N/M)) oracle queries (M = number of marked items), a quadratic speed-up over the classical Θ(N/M).

The circuit prepares the uniform superposition H^{⊗n}|0⟩, then repeats the Grover iterate G = D · O:

• Oracle O flips the sign of every marked basis amplitude: O|x⟩ = (-1)^{f(x)}|x⟩ where f(x)=1 iff x is marked.
• Diffusion D (inversion about the mean) reflects every amplitude about the average amplitude: D = 2|s⟩⟨s| - I with |s⟩ = H^{⊗n}|0⟩. Acting on an amplitude vector this is a_x ↦ 2·⟨a⟩ - a_x.

The optimal number of iterations is r = round(π/4 · √(N/M) - 1/2), which rotates the state vector to nearly coincide with the equal superposition of marked items. Reading out the register then returns a marked index with probability ≈ 1.

This implementation is state-vector exact: the oracle and diffusion are applied directly to the amplitude array (rather than synthesised from a multi-controlled-Z gate net), which keeps the routine fast and numerically clean while reproducing the textbook amplitude trajectory precisely.

Structs

GroverResult

Outcome of grover_search.

Functions

grover_search

Run Grover’s search and return the most probable basis index.

marked_probability

Total probability mass currently residing on the marked items.

optimal_iterations

Compute the optimal Grover iteration count for n_marked solutions in a space of dim = 2^n_qubits items.