Grover's search looks for marked items among N items numbered 0 to N-1. The state is a row of N real amplitudes, one per item, normalised so that their squares add up to 1, and one round of the search does two things, in this order:
- Mark. A phase oracle multiplies the amplitude of item x by (-1)^{f(x)}, where f(x)=1 for a marked item and 0 otherwise. In plain words: every marked amplitude changes sign, the others stay as they are.
- Invert about the mean. With m the mean of the row after the marking, every amplitude a_i becomes 2m - a_i.
Write grover_step(amps, marked) that applies one round to the list amps and returns the new list (or numpy array). marked lists the indices of the marked items (distinct, possibly none). Any global phase is accepted: [-0.8, 0.6] is the same state as [0.8, -0.6].
Examples
Input: amps = [0.5, 0.5, 0.5, 0.5], marked = [2]
Output: [0.0, 0.0, 1.0, 0.0]
Explanation: marking gives [0.5, 0.5, -0.5, 0.5] with mean 0.25; then 2*0.25 - 0.5 = 0
and 2*0.25 + 0.5 = 1.
Input: amps = [0.3535533905932738] * 8, marked = [5]
Output: [0.17677669529663692, 0.17677669529663692, 0.17677669529663692, 0.17677669529663692,
0.17677669529663692, 0.8838834764831844, 0.17677669529663692, 0.17677669529663692]
Explanation: 0.35355... is 1/sqrt(8). The marked amplitude grows from 0.354 to 0.884.
Input: amps = [0.6, 0.8], marked = [0]
Output: [0.8, -0.6]
Constraints
- numbers are compared with a tolerance of
1e-6
Goals
- Apply a phase oracle to a row of amplitudes by negating the marked entries
- Follow it with the inversion about the mean, in that order
- Watch a marked amplitude grow in one round