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⟩.
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.)
To determine the resulting superposition after running an additional m+1 steps of Grover's algorithm, we need to understand the behavior of the algorithm and how it evolves the amplitudes of the target state |y⟩ and the other states |x⟩ (where x≠y).
Grover's algorithm consists of three main steps: initialization, oracle, and diffusion.
1. Initialization:
Initially, all states are set to have equal amplitudes, resulting in a uniform superposition:
|ψ⟩ = 1/√K * (|y⟩ + Σ|x⟩)
Here, K represents the total number of elements in the search space.
2. Oracle:
In the oracle step, a phase flip is applied to the marked element |y⟩. This flips the sign of the amplitude of |y⟩:
|ψ'⟩ = 1/√K * (|y⟩ - Σ|x⟩)
The oracle step does not affect the amplitudes of the other states |x⟩.
3. Diffusion:
In the diffusion step, the amplitude of the target state |y⟩ is amplified, while the amplitudes of other states are reduced. This is done by first applying the Hadamard transform to all states, then applying the phase flip operation to the average amplitude of all states, and finally applying the Hadamard transform again:
|ψ''⟩ = 1/√K * (|y⟩ - Σ|x⟩) (After phase flip)
= 2/√K * |y⟩ - 1/√K * Σ|x⟩ (After diffusion)
At this point, after running m steps of Grover's algorithm, the superposition will be:
|ψm⟩ = (2m/K)^0.5 * |y⟩ - √((2m-m)/K) * Σ|x⟩
Now, if we run an additional m+1 steps (total 2m+1 steps from the initial state), the amplitude of the target state |y⟩ will be further amplified, and the amplitude of other states |x⟩ will be further reduced:
|ψ2m+1⟩ = (2m+1/K)^0.5 * |y⟩ - √((2m+1-m)/K) * Σ|x⟩
Therefore, the resulting superposition after running m+1 additional steps is given by:
|y⟩: αy = (2m+1/K)^0.5
|x⟩: αx = - √((2m+1-m)/K)