Posted by s on Friday, April 19, 2013 at 5:15am.
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.) HINT: You may want to review Problems 2, 3, and 5 of Assignment 6.
Now if we run for another m steps, what is the resulting superposition?
What about after yet another m+1 steps?

Quantum Physics  Salmon Kahn, Monday, October 14, 2013 at 10:39pm
This is fairly simple. You just need to remember that Grover's algorithm is cyclical
You start out with an equal superposition for both the y x answers
0 steps: ay = 1/sqrt(K), ax = 1/sqrt(k)
then after m steps, you solve it
@m steps: ay  1, ax = o
Since you started from 0 instead of 1, it takes M+1 steps to get it back to the original position, but it's inverted
@2m+1 steps: ay = 1/sqrt(K), ax = 1/sqrt(k)
Then it takes another m steps to find the answer (but inverted)
@3m+1 steps: ay = 1, ax = 0
and then m+1 steps later, you're back to the initial position.
@4m+2 steps: ay = 1/sqrt(K), ax = 1/sqrt(k)
and the cycle repeats.
@5m+2 steps: ay = 1, ax = 0
@6m+3 steps: ay = 1/sqrt(K), ax = 1/sqrt(k)
Answer This Question
Related Questions
 physics  Suppose we ran m steps of Grover's algorithm on some function f (which...
 Quantum Physics  Suppose we ran m steps of Grover's algorithm on some function ...
 Quantum computers  PROBLEM 5 Suppose we ran m steps of Grover's algorithm on ...
 quantum physics  ass 6 q6:Now, consider the case where N4 elements are marked ...
 Quantum Physics  Suppose we ran m steps of Grover's algorithm on some function ...
 Quantum Physics  Suppose we ran m steps of Grover's algorithm on some function ...
 Math  azmin decided to get some exercise by taking the stairs from the first to...
 Algebra  Yazmin decided to get some exercise by taking the stairs from the ...
 physics  n this problem, we will carry out some steps of the quantum factoring ...
 Quantum Physics  In this problem, we will carry out some steps of the quantum ...
More Related Questions