Sign outOpen workspaceSign in

SlotLayer 0

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.

Takes

A check evaluable in superposition on any candidate, the size of the domain it ranges over, and the promise that fixes the schedule — Grover assumes exactly one accepted candidate; a method may instead require the check to answer about partial commitments rather than whole candidates.

Returns

One accepted candidate, with the number of queries spent and the probability the answer is right — or the report, at a stated confidence, that the domain holds none.

Find the item a check acceptsFixed-iteration amplitude rotationSearch by state discriminationFixed-iteration amplitude rotation — click the name to read about itGrover searchSearch by state discrimination — click the name to read about itSearch by state discriminationMarking oracle over a domain — you start hereA marked item, with its query bill — you finish here

Drag to pan. Pinch, or hold ctrl and scroll, to zoom. Arrow keys pan, plus and minus zoom, zero resets the view.

From Marking oracle over a domain to A marked item, with its query bill

A circle is an object you are holding. Each line between the two ends is one recorded way through this slot; where a way is built from smaller slots, those are its own lines. Circles are named on hover, and each one is a link.

Nothing drawn here has a recorded way through it that this figure leaves shut. See it on the map

Why this is a layer

What the methods differ in is what the check is allowed to be asked, and that is what decides whether the search is fast at all. Grover's check answers about a whole candidate, so the query bill is set by the domain size: O(N)O(\sqrt{N}) over N=2nN = 2^{n} strings. Ambainis and Montanaro's check answers about a partial commitment — a subset of the positions, not the whole candidate — a subset SS of the positions and a guess for those positions — and that single change carries the same recovery from O(2n/2)O(2^{n/2}) queries to O(nlog⁡n)O(\sqrt{n}\log n), an exponential difference. It is bought twice over, at the oracle and again at the technique, and the authors are explicit about the second half: their algorithm "rests neither on amplitude amplification nor on a quantum walk". A richer query is what makes a different technique worth reaching for. So a claim that a problem "reduces to unstructured search" has said nothing until it says what one query is worth. This is the same shape as the slot below it — `success-amplification`'s methods also differ in what they additionally require, a lower bound on aa or a per-branch stopping flag — and it is deliberately a slot of its own rather than that one: amplification is handed the preparation unitary AA and asked to make its good branch reliable, and a search is handed an oracle and has to build AA itself.

2 methods recorded

  • Fixed-iteration amplitude rotation

    Start from equal amplitude on every candidate, and alternate two operations — flip the sign of the accepted candidate, then reflect every amplitude about their average. Each round moves a fixed amount of amplitude onto the accepted candidate, so the number of rounds is computed from the domain size before the first query rather than discovered while running.

  • 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 kk positions into knowledge of k+Θ(k)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.

No recorded route avoids this step.

Nothing in this graph needs this as a step, so it is where a reading starts.

No record in the Atlas covers this yet. The catalogue is circuits and primitives; this part of the literature is not in it.