Problem 438443 · medium · Quantum Computing · Level 04 Oracles and Search

Stirred Too Long

Grover iteration · overshooting · periodic sequences · search over k

Grover's search on N items, M of them marked: start with every amplitude 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, with m the mean after the flip. After k rounds, a measurement shows a marked item with probability

p_k = \sin^2\big((2k+1)\,\theta\big), \qquad \theta = \arcsin\sqrt{M/N}

(in Python math.asin(math.sqrt(M / N)), radians). Rounds are not free, and running too many is as bad as running too few: past its peak the probability falls again. A technician who loses count wants to know how much slack there is.

When fewer than half of the items are marked, p_k first rises. The first peak is the smallest k \ge 0 with p_{k+1} < p_k. Write first_drop(N, M, t) that returns the smallest k after the first peak (so k is larger than the peak) with p_k < t.

Press Run with plot(range(8), [math.sin((2 * k + 1) * math.asin(math.sqrt(1 / 16))) ** 2 for k in range(8)], kind="stem") to see a peak and the fall after it.

Examples

Input:  N = 8, M = 1, t = 0.5
Output: 3
Explanation: p is about [0.125, 0.781, 0.945, 0.330, ...]; the first peak is k = 2 and
p_3 = 0.330 is already below 0.5. The early k = 0 does not count: it is before the peak.

Input:  N = 16, M = 1, t = 0.9
Output: 4
Explanation: p is about [0.063, 0.473, 0.908, 0.961, 0.582, ...]; the peak is k = 3.

Input:  N = 2**24, M = 1, t = 0.5
Output: 4825
Explanation: the peak is at k = 3216; the success stays above one half for a long while after it.

Constraints

  • 1 <= M and 2 * M < N (fewer than half of the items are marked)
  • M / N < t <= 1, which guarantees that the answer exists
  • the answer is at most about math.pi / 2 * math.sqrt(N / M), so a loop over k is fast enough

Goals

  • Locate the first peak of Grover's success probability
  • Measure how far past the peak the search can run before the success falls below a threshold
Starting Python…