Grover's search on N items, M \ge 1 of them marked: start with every amplitude 1/\sqrt N; one round flips the sign of every marked amplitude (one call of the phase oracle, which 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
A search lab runs the following plan, for a fixed k:
- prepare the start state, run k rounds and measure (that costs k oracle calls);
- ask the oracle once more whether the measured item is marked (1 more call);
- if it is not, start again from step 1 with a fresh start state.
Each attempt succeeds with probability p_k, independently of the others, and an experiment that succeeds with probability p > 0 needs 1/p attempts on average. Write cheapest_plan(N, M, K) that returns (k, cost): the number of rounds k in 0, 1, \dots, K with the smallest expected total number of oracle calls, and that expected number. Ties: if several k have a cost within a relative 1e-9 of the smallest (cost <= smallest * (1 + 1e-9)), return the smallest such k. A plan with p_k = 0 never ends and is never the cheapest.
Examples
Input: N = 4, M = 1, K = 3
Output: (1, 2.0)
Explanation: k = 0 costs 1 / 0.25 = 4 calls on average; k = 1 succeeds every time with 2 calls.
Input: N = 16, M = 9, K = 3
Output: (0, 1.7777777777777777)
Explanation: 9 of 16 items are marked: guess, check, repeat. One round would drop p to 0.316.
Input: N = 10**6, M = 1, K = 1000
Output: (583, 690.6174025257172)
Explanation: the success peaks at k = 785, but stopping earlier and retrying is cheaper.
Constraints
- costs are compared with a tolerance of
1e-6
Goals
- Turn a success probability into an expected number of oracle calls when failed runs are repeated
- Find the number of rounds that minimises the expected cost, which is not the one that maximises the success
- See that with most items marked, guessing at once is the cheapest plan