3
$\begingroup$

I am trying to understand Grover's algorithm without much of a background in quantum. I believe I understood the main parts to be:

  1. The quantum state is initialized to represent all $n$ possible solutions with equal amplitude/probability;
  2. Using the oracle, the quantum state flips the sign of the amplitude corresponding to the correct solution;
  3. Compute the mean amplitude, and reflect all amplitudes over the mean;
  4. Repeat steps 2 and 3 $O(\sqrt{n})$ times;
  5. Observe the quantum state (at which point it has a high probability to output the correct solution).

First of all, is my (general and non-quantum background) understanding mostly correct?

And secondly, I tried applying this on a simple example, with $n=4$ possible solutions:

  1. Initialize a quantum state with 4 amplitudes of $\frac{1}{2}$ or probabilities of $\frac{1}{4}$;
  2. One of these amplitudes is flipped to $-\frac{1}{2}$;
  3. The mean amplitude is $\frac{1}{4}$, and the flipped amplitudes result in 3 amplitudes of 0 and 1 amplitude of 1;
  4. Steps 2 and 3 are repeated some amount of times, but a circular pattern emerges every three iterations: from amplitudes $(\frac{1}{2}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2})$ to $(0, 0, 0, 1)$ as observed above,to $(-\frac{1}{2}, -\frac{1}{2}, -\frac{1}{2}, \frac{1}{2})$, to $(-\frac{1}{2}, -\frac{1}{2}, -\frac{1}{2}, -\frac{1}{2})$, to $(0, 0, 0, -1)$, to $(\frac{1}{2}, \frac{1}{2}, \frac{1}{2}, -\frac{1}{2})$, and finally back to $(\frac{1}{2}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2})$;
  5. Observing the quantum state is highly likely to output the correct solution, but only if it is done in the above specific $(0, 0, 0, \pm 1)$ states; in the other states it is equally likely to output an incorrect solution.

What am I misunderstanding here? I thought at first that the more iterations meant the closer the probability of a correct solution approaches to 1 (PTAS style if you will), but this is clearly not the case in the above example. Then I thought that there must be a predetermined number of iterations for which the probability of a correct solution is close to 1, but all I could find (that I could understand) was on Wikipedia (paraphrased from the Algorithm section):

Analysis shows that the eventual number of iterations $r(n)$ satisfies $r(n) = O(\sqrt{n})$.

Am I to understand that Grover's algorithm is not a real algorithm in the sense that you could give it an input and find an actual solution, since you don't know the number of iterations you'd need to do? In other words, is Grover's algorithm more of an existential result, i.e. there exists some number of iterations bounded by $O(\sqrt{n})$ for which finding a solution is possible? Or is the fault with me testing it on a (too) small example, for which the result somehow doesn't hold?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

Your understanding is correct. Seeing a circular pattern is indeed what you should expect. However, this does not prevent you from knowing how many repetitions are needed given a certain number of possible states $N = 2^n$ (where $n$ is the number of qubits), and a total number of marked states $M$.

The number of repetitions needed to maximize the amplitude of seeing one of the solution states is given by:

$$r = \left\lfloor \frac{\pi}{4}\sqrt{\frac{N}{M}} \right\rfloor ,$$

so, as long as you know $N$ and $M$ you should be able to find how many times to apply each step. Now, there might be situations in which you want to perform a search but you don't know the number of solutions. In that case, you would need to run another algorithm to first find $M$ (like the quantum counting algorithm), and then run Grover's algorithm.

Now, there are two ways to understand why you see this circular pattern:

  1. By tracking at the probability amplitudes of the statevector after the phase-inversion and inversion-about-the-mean steps.
  2. By plotting the statevector in a plane where the $y$ axis is "marked" state (solutions state) and the $x$ axis is the state orthogonal to the marked state.

The second option is what it is commonly used to find the optimal number of repetitions to get as close as possible to the solution state since it has a nice geometrical interpretation, but requires a little bit of abstract thinking to understand what each axis represents, and how the rotations relate to the algorithm itself. If you are comfortable with this, there is this tool where you can see how if you keep doing phase inversion and inversion about the mean you just rotate around a circle.

If you are still not comfortable with option 2, you can also see this repetition pattern by just looking at each probability amplitude after each step. Here's what is going on in your specific example of 2 qubits with 1 marked element (let's assume $|01\rangle$):

  1. Place qubits in equal superposition:

$$ \begin{aligned} |\psi_1\rangle &= \frac{1}{2}\left(|00\rangle + |01\rangle + |10\rangle + |11\rangle\right) \end{aligned} $$

step1

  1. Apply the oracle to "flip" the probability amplitude of the marked element:

$$ |\psi_2\rangle = \frac{1}{2}\left(|00\rangle - |01\rangle + |10\rangle + |11\rangle\right) $$ step2

  1. Flip all probability amplitudes about the mean given by:

$$ \mu = \frac{1}{N} \sum_{i=0}^N \alpha_i = \frac{1}{4}\left(\frac{1}{2} - \frac{1}{2} + \frac{1}{2} + \frac{1}{2} \right) = \frac{1}{4} $$

enter image description here

This should be the end of the algorithm because your state is the marked state with probability $1$:

$$ \begin{aligned} |\psi_3\rangle &= |01\rangle \end{aligned} $$

step32

But watch what happens if you keep applying the phase-inversion and inversion-about the mean steps. You keep going back and forth between placing the state in superposition and amplifying the final state:

steps

You just keep looping around.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ So in my specific example, $N=4$ and $M=1$, correct? Which by the formula implies Grover's algorithm uses one iteration, which checks out, nice! $\endgroup$ Commented Apr 2 at 14:33
  • $\begingroup$ That is correct. $\endgroup$ Commented Apr 2 at 14:50
4
$\begingroup$

In Grover algorithm you cannot exceed maximal number of iterations allowed which is $(\pi / 4)\sqrt{n}$. If you use more iterations, you would reduce amplitude of marked quantum state again. Then again the amplitude will increase and you would see circular pattern your mentioned. So, number of iterations is known and you should adhere to it.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.