PROBLEM 5
Suppose we ran m steps of Grover's algorithm on some function f (which has one marked element y) and the resulting superposition was exactly |y⟩.
PROBLEM 5A (4 points possible)
If we run for m+1 additional steps (i.e. total of 2m+1 steps from the initial state), what is the resulting superposition? Note that you can describe the superposition by specifying two numbers, αy and αx for x≠y. You may use K to denote the total number of elements. (K should be uppercase.) HINT: You may want to review Problems 2, 3, and 5 of Assignment 6.
To find the resulting superposition after running m+1 additional steps of Grover's algorithm (total of 2m+1 steps from the initial state), we can follow these steps:
1. Recall that after m steps of Grover's algorithm, the amplitude of the marked element y (denoted as αy) becomes -αy, and the amplitudes of all other elements x (where x≠y) remain the same.
2. Therefore, after m steps, the resulting superposition can be described as:
|ψ⟩ = αy|y⟩ + ∑(x≠y)αx|x⟩
3. Now, running for m+1 additional steps means another iteration of the Grover's algorithm will be performed.
4. In each iteration, the amplitude αy is negated, and the amplitudes of all other elements x (where x≠y) undergo a reflection around the average amplitude.
5. After the additional m+1 steps, the resulting superposition can be expressed as:
|ψ'⟩ = -αy|y⟩ + ∑(x≠y)'αx'|x'⟩
6. We use primes to denote the new amplitudes after the additional m+1 steps.
7. To find the new amplitudes, we need to determine the reflection around the average amplitude for the elements other than y.
8. Let's calculate the average amplitude:
avg = (αy + ∑(x≠y)αx) / K
9. In each iteration of the algorithm, the amplitudes are reflected around the average amplitude.
10. Therefore, after the reflection, the new amplitude αx' for x≠y can be calculated as follows:
αx' = 2 * avg - αx
11. Plugging in the previous equation for avg, we get:
αx' = 2 * ((αy + ∑(x≠y)αx) / K) - αx
12. Finally, we substitute αx' and αy' back into the superposition expression:
|ψ'⟩ = -αy|y⟩ + ∑(x≠y){2 * ((αy + ∑(x≠y)αx) / K) - αx}|x'⟩
Note that the values of αy and αx depend on the specific function f and the number of iterations m. So to obtain the exact numerical values, further information about the function and the number of iterations is needed.