Grover's search on N items, M of them marked:
- Start with every amplitude equal to 1/\sqrt N.
- One round: every marked amplitude changes sign (the phase oracle multiplies the amplitude of item x by (-1)^{f(x)}, with f(x) = 1 exactly for the marked items); then every amplitude a becomes 2m - a, where m is the mean of all N amplitudes after the sign change.
The rounds treat all marked items alike, and all unmarked items alike. So after any number of rounds, every marked item has the same amplitude a_k and every unmarked item has the same amplitude b_k; the whole list of N numbers is M copies of a_k and N - M copies of b_k. That is good news when N is a trillion.
Write two_amplitudes(N, M, k) that returns the pair (a, b): the amplitude of a marked item and the amplitude of an unmarked item after k rounds. Both are real numbers and may be negative; return them with their signs.
Examples
Input: N = 4, M = 1, k = 1
Output: (1.0, 0.0)
Input: N = 8, M = 1, k = 2
Output: (0.9722718241315025, -0.08838834764831849)
Explanation: the success probability is 0.97227^2 = 0.9453; the 7 unmarked items share the rest.
Input: N = 2, M = 1, k = 5
Output: (0.7071067811865475, -0.7071067811865475)
Constraints
- numbers are compared with a tolerance of
1e-6 - the list of
Namplitudes is far too long to build for the large tests: work with the two numbers
Goals
- Describe Grover's state by one marked and one unmarked amplitude
- Write the mean of N amplitudes from those two numbers and the counts M and N - M
- Run a million-item search with two floats instead of a list