Fixed-iteration amplitude rotation

What it fills

• Find the item a check accepts

  Given a way to test candidates and nothing else — no order on the domain, no structure to exploit — return one candidate the test accepts, in fewer queries than looking at them all.

When it applies

Grover's paper assumes there is exactly one accepted candidate, and not merely a known number of them — "let there be a unique state, say $S_{\nu}$, that satisfies the condition $C(S_{\nu}) = 1$, whereas for all other states $S$, $C(S) = 0$" — and that the condition is evaluable in unit time. Several accepted candidates is named as an extension and is not carried out here: the paper says the algorithm "can be easily modified" for that case and then cites two other papers for both routes, a degeneracy sweep from Boyer, Brassard, Høyer and Tapp and a random perturbation from Mulmuley, Vazirani and Vazirani. The domain is a register of $n$ bits, $N = 2^{n}$, and no order on it is assumed — "there does not exist any sorting on the database that would aid its selection". Nothing in this paper says what happens when the iteration count is set wrong; it says only that "the precise number of repetitions is important" and points at Boyer, Brassard, Høyer and Tapp for it.

Requires

Every step this method names moves its route along, so there is nothing it needs alongside them.

Example

given  a domain of N = 2^n states S_1 ... S_N, addressed as n-bit strings
       a condition C evaluable on any state S in unit time            (Sec. 2)
       the promise that exactly one state S_nu has C(S_nu) = 1        (Sec. 2)

# no sorting on the domain is assumed -- there is nothing to look the answer
# up in, which is the whole reason the count of queries is the cost

initialize to equal amplitude 1/sqrt(N) in each of the N states  (Sec. 3, step i)

# this distribution costs O(log N) steps, by Walsh-Hadamard on the n bits

repeat O(sqrt(N)) times:                                        (Sec. 3, step ii)
    if C(S) = 1: rotate the phase of S by pi radians; else leave S alone
    apply the diffusion transform D, D_ij = 2/N for i != j,
                                    D_ii = -1 + 2/N

    # D is the inversion about the average: after it, each amplitude sits as
    # far below the mean as it sat above, and as far above as it sat below

sample the resulting state                                      (Sec. 3, step iii)
return the sampled state -- it is S_nu with probability at least 1/2

# the number of repetitions is fixed before the first query, from N alone.
# This paper proves only that SOME M < sqrt(2N) suffices; it says the precise
# count 'is important' and cites Boyer, Brassard, Hoyer and Tapp for it, so no
# exact count is written here

# nor is there anything here about running the loop too long: this paper does
# not discuss it

# the phase rotation must leave no trace of which state was sensed, or the
# paths that reach one final state stop being indistinguishable and stop
# interfering. It is not a classical measurement

# do not read this as covering several accepted candidates. The paper says the
# algorithm can be modified for that and then cites two other papers for both
# ways of doing it, rather than doing either

Cost, as the source states it

The paper states the loop as $O(\sqrt{N})$ repetitions and derives a specific, non-tight bound on it in its own proofs: from the amplitude increment $\Delta k > 1/(2\sqrt{N})$ per round, "there exists a number $M$ less than $\sqrt{2N}$, such that in $M$ repetitions of the loop in step (ii), $k$ will exceed $1/\sqrt{2}$", and $1/\sqrt{2}$ is exactly the threshold at which "the probability of the system being in the desired state ... is $k^{2} = 1/2$". Because $k$ goes past that threshold rather than landing on it, what the paper proves is success "with a probability greater than $1/2$" — and, of the sampling step itself, "a probability of at least $1/2$". Both phrasings are the paper's, in two places, and neither is a certainty. The initial equal superposition costs $O(\log N)$ steps on top. Against it the paper puts a classical floor of $N/2$ examinations to succeed with probability $1/2$, and a quantum floor of $\Omega(\sqrt{N})$ it attributes to Bennett, Bernstein, Brassard and Vazirani, concluding that the algorithm "is within a small constant factor of the fastest possible quantum mechanical algorithm" — sharpened, in a different paper it cites rather than in this one, to "within a few percent".

Implementations

• qiskit-algorithms' `Grover` class, called with a fixed `iterations` integer

  • A fast quantum mechanical algorithm for database search
  • Tight bounds on quantum searching

  `qiskit_algorithms.amplitude_amplifiers.grover.Grover`, in the `qiskit-community/qiskit-algorithms` Python package — installed separately from Qiskit itself via `pip install qiskit-algorithms`, and currently at 0.4.0 on PyPI. The class docstring's own References list this same 1996 paper as [1] — "L. K. Grover (1996), A fast quantum mechanical algorithm for database search" — and the constructor's own References section closes with a second citation, "Boyer et al., Tight bounds on quantum searching", later in that same `__init__` docstring — after several more Args entries and a Raises block beyond the `iterations` paragraph that recommends `Grover.optimal_num_iterations` for the exact power. The `iterations` constructor argument forks exactly along the line this method's own conditions draw: passed a plain `int`, only that one power of the Grover operator is tried; passed `None`, a `list`, an iterator, or a `growth_rate`, the class instead tries a sequence of powers and checks an `is_good_state` callback after each circuit — the several-accepted-candidates and unknown-count extension this method hands to a different citation. Only the fixed single-`int` branch belongs to this method; the adaptive branches are not documented here.

  With `iterations` a plain `int`, the constructor stores it as a one-element list — `elif isinstance(iterations, int): self._iterations = [iterations]` — so inside `amplify`, `max_iterations = len(self._iterations)` is 1 and the run loop executes exactly once regardless of whether the problem supplies an `is_good_state` check: exactly one power of the Grover operator is tried, full stop, which is the fixed-count behaviour this method's own `conditions` field describes. The single circuit is built by `construct_circuit`, composing `problem.state_preparation` — by default in `AmplificationProblem`, "a layer of Hadamard gates" on every qubit, the paper's own equal-amplitude start — with `problem.grover_operator.power(power)`. The oracle enters through `AmplificationProblem.oracle` as the phase flip $S_f$, described as flipping "the phase of the state $|x\rangle$ if $x$ is a hit"; if the problem is not given a `grover_operator` directly, one is built from that oracle and the state preparation by Qiskit's own `grover_operator` function, or the `GroverOperator` class "if you're using a version of Qiskit older than 2.1.0", per the class docstring's own words. When the number of accepted candidates is known, the exact power to fix comes from the static method `Grover.optimal_num_iterations(num_solutions, num_qubits)`: `amplitude = sqrt(num_solutions / 2**num_qubits)`, then `round(arccos(amplitude) / (2 * arcsin(amplitude)))`. Applied to one accepted candidate among $N=8$ states — `optimal_num_iterations(1, 3)` — that formula returns 2.

  No dataset. The input is the caller's own oracle circuit, passed as `AmplificationProblem.oracle`, together with — when the count is fixed rather than searched for — the number of accepted candidates and the qubit count passed to `optimal_num_iterations`.

  `qiskit_algorithms/amplitude_amplifiers/grover.py` and `qiskit_algorithms/amplitude_amplifiers/amplification_problem.py` in https://github.com/qiskit-community/qiskit-algorithms, read at `main`, commit `23187def78`, dated 2026-05-21. Apache-2.0 licensed. The class is `Grover(AmplitudeAmplifier)`; its input is an `AmplificationProblem`, whose constructor takes `oracle`, `state_preparation`, `grover_operator`, `post_processing`, `objective_qubits` and `is_good_state`.

  `GroverResult` reports `iterations` (the powers tried), `top_measurement`, `oracle_evaluation` and `max_probability` from whatever sampler and oracle the caller supplies, so the repository carries no benchmark numbers of its own to quote here — what is checkable is the arithmetic above, that `optimal_num_iterations` turns the paper's "some $M < \sqrt{2N}$" into one concrete integer per $(N, \text{solutions})$ pair rather than a bound the caller still has to search over.

• PennyLane's `GroverOperator` diffusion template, driven for a fixed `num_iterations`

  `pennylane.templates.subroutines.grover.GroverOperator`, in Xanadu's PennyLane (PyPI `pennylane`, currently 0.45.1). The class builds only the diffusion half of a round: its own docstring's worked example constructs the phase-flip oracle separately, as a plain Python function, and composes the two by hand inside a fixed loop, so this artefact matches the diffusion half of this method's two-unitary round and leaves the accepted-candidate oracle to the caller. No paper is cited in the module.

  `compute_decomposition` builds exactly the pattern the class docstring describes — "the operator is implemented with a layer of Hadamards, a layer of $X$, followed by a multi-controlled $Z$ gate, then another layer of $X$ and Hadamards" — as `Hadamard` on every wire but the last, `PauliZ` on the last wire, a `MultiControlledX` with every `control_values` entry 0 (open controls) targeting the last wire, `PauliZ` again, `Hadamard` on every wire but the last again, and a closing `GlobalPhase(numpy.pi)`. The class docstring attributes the pair of `PauliZ` gates on the last wire to the circuit identity "$HXH = Z$", by which "the last $H$ gate converts the multi-controlled $Z$ gate into a multi-controlled $X$ gate" — the textbook picture the docstring draws is a multi-controlled $Z$, and what `compute_decomposition` actually emits is the open-controlled `MultiControlledX` flanked by those two `PauliZ` gates instead. `compute_matrix` gives the same operator in closed form, `2 / dim - np.eye(dim)` for `dim = 2**n_wires` — algebraically $2|s\rangle\langle s| - \mathbb{I}$ with $|s\rangle$ the uniform superposition, since $|s\rangle\langle s|$ has every entry $1/\dim$ — the same matrix as Grover's own $D \equiv -I + 2P$ with $P_{ij} = 1/N$ for every $i, j$, not merely an equivalent one. The class builds no oracle of its own: its worked example constructs one from a Hadamard-Toffoli-Hadamard sandwich on the target wire and drives a fixed number of rounds directly — "We can then implement the entire Grover Search Algorithm for `num_iterations` iterations by alternating calls to the oracle and the diffusion operator" — with `num_iterations` fixed by the caller before the circuit runs, the paper's own schedule.

  No dataset. The worked example's own input is a 3-wire circuit with the accepted candidate $|111\rangle$ marked by a hand-written oracle, not read from any file.

  `pennylane/templates/subroutines/grover.py` in https://github.com/PennyLaneAI/pennylane, read at `main`, commit `a7b66fc43f`, dated 2026-08-14. Apache-2.0 licensed. The class is `GroverOperator(Operation)`, constructed as `GroverOperator(wires, work_wires=())`; `work_wires` only assists the `MultiControlledX` decomposition, and the constructor raises `ValueError("GroverOperator must have at least two wires provided.")` below two wires.

  The docstring's own worked example states the outputs of running it, each marked `# doctest: +SKIP` so they are the published claim rather than a value this record re-executed: `GroverSearch(num_iterations=1)` returns probabilities `[0.0312, 0.0312, 0.0312, 0.0312, 0.0312, 0.0312, 0.0312, 0.7812]`, and `GroverSearch(num_iterations=2)` returns `[0.0078, 0.0078, 0.0078, 0.0078, 0.0078, 0.0078, 0.0078, 0.9453]` — the accepted candidate carrying probability 0.7812 after one round and 0.9453 after two. The same docstring states the fixed schedule separately from the example — "Optimally, the oracle-operator pairing should be repeated $\lceil \pi/4\sqrt{2^{n}} \rceil$ times" — which for $n = 3$ evaluates to 3, one round more than either value the worked example actually runs.

• Cirq's `examples/grover.py`, a fixed one-round search over 2-bit oracles

  `examples/grover.py` in Google Quantum AI's Cirq (PyPI `cirq`, currently 1.7.0), a runnable script rather than a library class. Its own module docstring states the domain it covers and why: "At the moment, only 2-bit sequences (for which one pass through Grover operator is enough) are considered" — the whole example sits inside the one case where a single fixed round already suffices, $N = 4$. The docstring's own "=== REFERENCE ===" line names one external paper, "Coles, Eidenbenz et al. Quantum Algorithm Implementations for Beginners" (arXiv:1804.03719) — a 34-author survey covering twenty different algorithms rather than a paper about Grover's method specifically, so it is not recorded here as this artefact's own citation.

  `make_oracle` builds the phase-flip oracle as a marked-string Toffoli: `X` gates flip every input qubit whose target bit is 0, a `TOFFOLI` targets an ancilla `output_qubit` controlled on both input qubits, and the same `X` gates undo the flip, so the Toffoli fires exactly on the two-bit string `x_bits`. `make_grover_circuit` prepares `output_qubit` in $|-\rangle$ (`X` then `H`) before that oracle runs, turning the Toffoli's bit flip into a relative phase flip on the accepted input string by phase kickback, and starts the two input qubits in an equal superposition with `H.on_each`. After the oracle, the diffusion half is written gate by gate rather than called as a library operator: `H.on_each`, `X.on_each`, `H` on the second input qubit, `CNOT` from the first input qubit to the second, `H` again on the second, `X.on_each`, `H.on_each` — the middle three gates are the two-qubit circuit identity for a controlled-$Z$ ($H \cdot \mathrm{CNOT} \cdot H = CZ$ on the target qubit), and conjugating that $CZ$ by the surrounding `X.on_each` layers moves its $-1$ phase from $|11\rangle$ onto $|00\rangle$, giving $I - 2|00\rangle\langle00|$; sandwiched by the two Hadamard layers this composes to $-D$ rather than $D$, the negative of the paper's own $D = WRW$ factorisation for $n = 2$ — a global phase with no effect on any measurement the circuit produces, and one the file leaves uncorrected: unlike PennyLane's equivalent construction, `examples/grover.py` appends no compensating global-phase gate. The circuit runs through oracle-then-diffusion exactly once, because the module restricts itself to the case where $N = 4$ needs no second round.

  No dataset. `main()` draws the two-bit accepted string `x_bits` at random with `random.randint` on each run and passes it into `make_oracle`.

  `examples/grover.py` in https://github.com/quantumlib/Cirq, read at `main`, commit `f14948c48b`, dated 2026-02-03. Apache-2.0 licensed. `set_io_qubits`, `make_oracle(input_qubits, output_qubit, x_bits)`, `make_grover_circuit(input_qubits, output_qubit, oracle)` and `main()` are module-level functions rather than a class; `main()` runs the built circuit on `cirq.Simulator()`.

  The module docstring carries its own recorded sample run rather than a reported benchmark: `Secret bit sequence: [1, 0]`, ten repetitions all landing on the same bitstring — `Sampled results: Counter({'10': 10})` — and `Found a match: True`. The same docstring's general claim, that the algorithm finds the accepted string "with the probability p >= 2/3", is stated for Grover's algorithm in general and is not a number this specific 2-qubit, 1-round circuit is shown meeting or falling short of anywhere in the file.

What it needs

Nobody has taken this apart yet. That is a gap in this graph, not a claim that the method has no parts.

Other ways to fill the same slot

Different approaches

• Search by state discrimination

  When one query can test a partial guess rather than a whole candidate, the answer is recovered by discriminating quantum states instead of by rotating amplitude. One query turns knowledge of $k$ positions into knowledge of $k + \Theta(\sqrt{k})$ of them, and the measurement that does it is the one that minimises the error — though a stage costs more than that one query, because the guess it produces has to be checked and repaired.

In the Atlas

• Grover unstructured search

  The canonical search primitive, paired with the linear classical baseline it is meant to improve.

Sources

• A fast quantum mechanical algorithm for database search↗Lov K. Grover · 1996theory yes · simulation no · hardware no