MakarovSuites
English
EnglishDeutschРусскийУкраїнськаFrançaisEspañolItalianoPolski
Contact & licences

Math

Grover's search

Explore amplitude amplification in an unstructured search. A phase oracle changes the sign of the marked amplitude without changing probabilities in the computational basis. The diffusion step turns relative phase into a higher success probability. Too many iterations reduce that probability again.

By Mykhailo Makarov

Grover's search — Actual application image
Actual application image

What happens

The phase oracle marks a candidate by changing its relative phase. Measuring immediately in the computational basis gives the same probabilities as before the oracle; this does not make relative phase unobservable in every measurement basis. Interference in the diffusion step converts the phase mark into amplitude amplification.
One Grover iteration consists of the oracle and diffusion. The success probability oscillates rather than converging: stop near the first maximum, then compare with later iterations. The query count scales with the square root of the search-space size for a single marked item; constructing the oracle and preparing data also have costs. The module shows an ideal state-vector simulation, exact rational amplitudes for its selected sizes, and reproducible sampled measurement counts.

Equations used in the module
Equations
sin θ = 1/√N;  after k turns the marked amplitude is sin((2k+1)θ) and the chance is its square
one turn = one oracle call (a minus sign on the marked amplitude) + one reflection about the mean:  a -> 2·mean − a
optimal number of turns k* = floor(π/4·√N) = 3, 6, 12, 25 for N = 16, 64, 256, 1024;  a blind search averages (N + 1)/2 = 8.5, 32.5, 128.5, 512.5
for N = 4^m the amplitude is an exact FRACTION, by the integer recursion u(k+1) = (2q² − 4)·u(k) − q⁴·u(k−1) with q = 2^(n/2), sin((2k+1)θ) = u(k)/q^(2k+1)
sixteen items:  1/4, 11/16, 61/64, 251/256 (k* = 3), 781/1024, 1451/4096, −2339/16384 (k = 6, chance 0.0204 - worse than the 0.0625 it started at), … , 2269261/67108864 (k = 12)
sixty-four items after six turns:  133988401/134217728 = 0.99829138070344925, which the register reproduces to the last bit
measured against counted:  2000 runs at k* give 1913, 1994, 2000, 2000 hits for N = 16, 64, 256, 1024 - each inside three sigma of the exact chance

Related experiments

Back to catalogue
Gates, phase and what a basis is for — Actual application image

Math

Gates, phase and what a basis is for

Four small circuits with one turnable phase in them, read in the Z, X or Y basis. The phase is a real, located property of the state - the Bloch vector walks the equator with it - and in the wrong basis it is completely invisible: over a whole turn the largest change in any outcome probability is 1e-16. Put a second Hadamard at the end and the same phase decides the answer with certainty. That is interference, and it is the whole difference between a quantum computer and a coin.

Teleportation, and what the two classical bits are for — Actual application image

Math

Teleportation, and what the two classical bits are for

Alice's station holds a message qubit and half of a shared pair; Bob's holds the other half. Walk the protocol step by step - CNOT, H, measurement - and send the two bits down an ordinary channel. Stop them before they arrive and try to guess them; then pick Bob's correction and compare what he holds with the message. Until the bits arrive Bob's qubit is I/2 whatever was sent, and after measuring Alice keeps no copy.

One question, asked once — Actual application image

Math

One question, asked once

A black box computes f from n bits to one bit, and you may only ask it about inputs. To be certain whether f is constant or balanced can take half the table plus one call. Hadamard everything, ask ONCE with the answer as a sign, Hadamard everything again, and the all-zeros outcome settles it. The truth table here is clickable, so the promise can be broken by hand: for any table at all the answer comes up with probability (1 - 2k/N)². And when the table happens to be f(x) = s·x, the one call returns s itself.