quantum gate directory

Qubits: $n$

hermitian

SDK Support

SDK	Name
Qiskit	qiskit.circuit.library.grover_operator ⓘ
PennyLane	pennylane.GroverOperator
Cirq	—
Q#	—
PyQuil	—
Braket	—
BQSKit	—
Qibo	— ⓘ
pytket	— ⓘ
Stim	—
OpenQASM	—

Groups

This gate is contained in the following groups:

• orthogonal

Reference

A fast quantum mechanical algorithm for database search (1996)

The Grover diffuser is the reflection about the uniform superposition $|s\rangle = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1} |x\rangle$ over $n$ qubits ($N = 2^n$):

$$ U_s = 2|s\rangle\langle s| - I = H^{\otimes n} \left( 2|0^n\rangle\langle 0^n| - I \right) H^{\otimes n} $$

Its matrix has $\frac{2}{N} - 1$ on the diagonal and $\frac{2}{N}$ everywhere else.

Inversion about the mean

Acting on a state with amplitudes $a_x$, the diffuser maps each amplitude to $2\bar{a} - a_x$, where $\bar{a}$ is the mean amplitude. An amplitude that a phase oracle has flipped negative lands above the mean after reflection — this is the amplification step of Grover's algorithm.

Properties

• Hermitian, self-inverse, and real: a reflection in every sense.
• The Grover iterate is the diffuser composed with a phase oracle: $G = U_s U_f$. Geometrically, two reflections make a rotation — each iterate rotates the state toward the marked subspace by a fixed angle, giving the $O(\sqrt{N})$ query count.
• Up to the sign convention, $2|0^n\rangle\langle 0^n| - I$ is itself a phase oracle marking $|0^n\rangle$, implemented as a multi-controlled $Z$, so the diffuser costs one MCX conjugated by Hadamards.

Usage

• The amplitude-amplification step in Grover search and its generalizations (amplitude estimation, fixed-point search, quantum walks).