Problem 436522 · hard · Quantum Computing · Level 04 Oracles and Search

The Vault That Answers in Signs

Grover search · phase oracle · Born rule · seeded sampling · verification · query complexity

A vault has N = 2^n possible codes, numbered 0 to N-1, and exactly one opens it: the marked item. You cannot see which. You get a sealed phase oracle oracle(state): give it a state (a list of N amplitudes, normalised so that the sum of |a_i|^2 is 1) and it returns a new list in which the amplitude of the marked item has changed sign. In formula: it multiplies the amplitude of item x by (-1)^{f(x)}, where f(x) = 1 only for the marked item. A state of the wrong length or not normalised raises ValueError.

Every oracle call is expensive, and a real chip lets you measure but never read its amplitudes. Play by those rules, with this exact procedure. Write grover_search(n, oracle, seed):

  1. Create one random generator for the whole search: rng = random.Random(seed).
  2. Search. Start with every amplitude equal to 1/\sqrt N. Run R = \lfloor \frac{\pi}{4}\sqrt N \rfloor rounds (math.floor(math.pi / 4 * math.sqrt(N))). One round: call the oracle on the state, then replace every amplitude a by 2m - a, where m is the mean of the N amplitudes the oracle returned.
  3. Measure once, by the Born rule: outcome i has probability p_i = |a_i|^2. Draw r = rng.random() and pick the first outcome i whose running total p[0] + ... + p[i] is greater than r (if rounding leaves no such i, pick the last outcome with nonzero probability).
  4. Check the outcome with exactly one more oracle call (think about which state to give it). If it is the marked item, return it. Otherwise go back to step 2 with a fresh start state, using the same rng.

The tests call with_box(grover_search, n, seed), which hides the marked item, runs your function and returns {"answer": ..., "calls": ..., "rounds": R, "marked": ...}. A test passes when your answer is the marked item and you used exactly as many oracle calls as the procedure above needs for that seed (so every attempt costs R + 1 calls). Far too many calls raise TooManyCalls. Try it with Run: print(with_box(grover_search, 3, 31)).

Examples

Input:  with_box(grover_search, 2, 1)
Output: correct with 2 oracle calls: one round always finds the code among 4

Input:  with_box(grover_search, 3, 31)
Output: correct with 6 oracle calls: the first measurement (success 94.5%) misses,
        the second attempt finds the code

Input:  with_box(grover_search, 1, 11)
Output: correct with 4 oracle calls: with 2 codes each attempt succeeds only half the time

Constraints

  • 1 <= n <= 10
  • random and math are available; use only the one generator random.Random(seed) for the draws

Goals

  • Run Grover's search against a sealed phase oracle, with the prescribed number of rounds
  • Measure the final state with a reproducible seeded draw
  • Check the measured item with one more oracle call and repeat the whole search when it is wrong
Starting Python…