Grover's search on N items, M of them marked, starts with every amplitude equal to 1/\sqrt N. One round flips the sign of every marked amplitude (the phase oracle multiplies the amplitude of item x by (-1)^{f(x)}, with f(x) = 1 exactly for the marked items) and then replaces every amplitude a by 2m - a, where m is the mean of all N amplitudes after the flip. The success probability p_k is the chance that measuring after k rounds shows a marked item.
Simulating this needs a list of N amplitudes, which is hopeless for N = 2^{40}. Fortunately there is an exact formula. With the angle
(in Python math.asin(math.sqrt(M / N)), in radians), the success probability after k rounds is
Write closed_form(N, M, ks) that returns the list of p_k for every k in the list ks, in the same order. The formula holds for every N \ge 1, not only for powers of two.
The formula agrees with a step-by-step simulation on a list: for N = 32 and M = 1 both give about [0.03125, 0.25830078125, 0.60242462158203, 0.89693653583527] for k = 0, 1, 2, 3. Press Run with plot(range(60), closed_form(1000, 1, range(60))) to see the probability rise and fall.
Examples
Input: N = 4, M = 1, ks = [0, 1, 2]
Output: [0.25, 1.0, 0.25]
Input: N = 2**40, M = 1, ks = [0, 823549]
Output: [9.094947017729282e-13, 0.9999999999999014]
Explanation: a trillion items; about 823 thousand rounds make the marked one almost certain.
Input: N = 16, M = 9, ks = [0, 1, 2]
Output: [0.5625, 0.31640625, 0.793212890625]
Constraints
- probabilities are compared with a tolerance of
1e-6
Goals
- Evaluate the closed form sin^2((2k+1) theta) for Grover's success probability
- Handle search spaces far too large to simulate
- Treat the edge cases with no marked item and with every item marked