A search chip holds n qubits, so it can point at N = 2^n items, numbered 0 to N-1. Some of them are marked (their indices are listed in marked). Grover's search runs like this:
- Start in the uniform state: every one of the N amplitudes equals 1/\sqrt{N}.
- One round first applies the phase oracle, which multiplies the amplitude of item x by (-1)^{f(x)} with f(x)=1 exactly for the marked items (every marked amplitude changes sign), and then inverts about the mean: with m the mean of all N amplitudes after the marking, each amplitude a becomes 2m - a.
- After k rounds the chip is measured. By the Born rule it shows item x with probability |a_x|^2, so the success probability p_k is the sum of |a_x|^2 over the marked items.
Write success_curve(n, marked, K) that returns the list [p_0, p_1, \dots, p_K]: the success probability after 0, 1, \dots, K rounds (p_0 is measured on the starting state, before any round).
Press Run with plot(range(13), success_curve(5, [7], 12), kind="stem") to see the probability climb, peak and fall back.
Examples
Input: n = 2, marked = [3], K = 3
Output: [0.25, 1.0, 0.25, 0.25]
Explanation: with 4 items one round finds the marked one for sure; more rounds spoil it.
Input: n = 4, marked = [9], K = 6
Output: [0.0625, 0.47265625, 0.908447265625, 0.9613189697265625, 0.5817041397094727,
0.1254916787147522, 0.020380768924951553]
Input: n = 1, marked = [1], K = 3
Output: [0.5, 0.5, 0.5, 0.5]
Explanation: with two items and one marked, a round never changes the odds.
Constraints
- probabilities are compared with a tolerance of
1e-6 - if
markedis empty the success probability is 0 after every round
Goals
- Start Grover's search from the uniform state on N = 2^n items
- Repeat the round of marking and inverting about the mean
- Record the probability of measuring a marked item after every round