Post a New Question


posted by .

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 -

    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

First Name:
School Subject:

Related Questions

More Related Questions

Post a New Question