6
$\begingroup$

In the Qiskit tutorial on Grover's algorithm it is stated that with a 2 qubit algorithm the chance of measuring the "right" state is already 100%.

But I thought that the algorithm would amplify the 'right' amplitude around 9 times and respectively the probability around 3 times.

Is this depending on the variation of grovers algorithm used? Where does the 100% suddenly came from, if other multi-qubit states do not get to 100%?

Edit: I want to work with the Quantum Reinforcement Learning Paper of Dong et al. There they propose to use some sort of grovers algorithm to make use of the probability amplification of a 2 qubit system. This would need a slower approach to 100% as far as I understand. There would be no point in their proposal, if it reaches 100% after just 1 iteration.

$\endgroup$

1 Answer 1

6
$\begingroup$

Good question! Short answer: No. It is true for search problems with only one solution but does not hold for search problems with more than one solution. For the long answer, I will need to define some terms (I'll try to use most of the same notation as in the Qiskit tutorial).

Suppose we wish to search through $N$ elements, and that the search problem has exactly $M$ solutions, with $1 \leq M \leq N$. As you know, the Grover iteration can be regarded as a rotation in the two-dimensional space $\mathbb{C}^N$ spanned by the starting vector $|s\rangle$ and the state consisting of a uniform superposition of solutions to the search problem, $|\omega\rangle$. Following Qiskit's naming convention, we will also introduce the state $|s'\rangle$, which is in the span of these two vectors, and perpendicular to $|\omega\rangle$. We can define these normalized states as,

$$|s'\rangle \equiv \frac{1}{\sqrt{N-M}}\sum_{x\neq\omega}|x\rangle$$ $$|w\rangle \equiv \frac{1}{\sqrt{M}} \sum_{x=\omega}|x\rangle,$$ and can therefore express the initial state $|s\rangle$ as, $$|s\rangle = \sqrt{\frac{N-M}{N}}|s'\rangle+\sqrt{\frac{M}{N}}|\omega\rangle.$$

Let $\sin{\theta} = \sqrt{M/N}$, so that $|s\rangle = \cos{\theta}|s'\rangle + \sin{\theta}|\omega\rangle$. The action of a single Grover iteration, $G$, is to rotate the state vector by $2\theta$ towards $|\omega\rangle$. Based on the initial state, $|s\rangle$, taking the system to $|\omega\rangle$ requires rotating through $\arccos{\sqrt{M/N}}$ radians.

For Qiskit's two-qubit example, we set $N=4$ and $M=1$. This tells us that $\sin{\theta} = 1/2$, so $\theta = \pi/6$, and,

$$|s\rangle = \cos{(\pi/6)}|s'\rangle + \sin{(\pi/6)}|\omega\rangle.$$

From above, we know a single Grover iteration will rotate the state vector by $2\theta = \pi/3$:

$$G|s\rangle = \cos{(\pi/2)}|s'\rangle + \sin{(\pi/2)}|\omega\rangle = |\omega\rangle.$$

So, in this special case, only exactly one iteration is required to perfectly obtain $\omega$. However, this is not the case for all values $M/N$. For example, when $M/N << 1$ we have $\theta \approx \sin{\theta} \approx \sqrt{M/N}$, and thus the angular error of the final state can be as high as (but no greater than) $\theta \approx \sqrt{M/N}$, giving a probability of error as high as (but no greater than) $M/N$. Depending on the value $M/N$ and whether $M$ is known in advance, alternate approaches to and various adaptations of Grover's algorithm are also used. When $M/N \geq 1/2$, we see that the angle $\theta$ gets smaller as $M$ varies from $N/2$ to $N$. As a result, the number of iterations needed by the search algorithm increases with $M$. When $M/N$ is this large, error probability can be as high as (by no greater than) one-half. Here, quantum search offers little significant advantage over a classical one. When $M$ is not known in advance, there are a number of different approaches. One clever procedure exploits the fact that the Grover iteration is periodic, and combines Grover iterations with an application of the quantum Fourier transform to learn the value of $M$ with enough accuracy to still ensure a high probability of success. Nielson and Chuang Section 6.1 and Mermim Chapter 4 are great for more on this topic.

Hope that helps!

$\endgroup$
2
  • $\begingroup$ Thank you for this detailed answer. Just to be 100% sure I understood this correctly (since it it so counter-intuitive): The error probability is $\theta \approx \sqrt{M/N}$, where $N$ is the total number of elements in the search space. This means that the error probability is lower the more elements there are in the search space. This sounds really weird - shouldn't it be less likely that the right element is found, the more elements there are in total? $\endgroup$
    – avf
    Jul 9, 2021 at 17:37
  • 1
    $\begingroup$ @avf I see where your confusion is. Each Grover iteration rotates the state vector by $2\theta$. The larger $N$ is, the smaller $\theta$ is, and therefore the higher the probability is that an integral number of iterations will bring the state vector to exactly the goal state: $\text{iteration precision} \propto 1/\sqrt{N}$. However, the number of iterations required scales with the number of elements in the search space: $\text{num iterations} \propto \sqrt{N}$. $\endgroup$
    – ryanhill1
    Jul 9, 2021 at 18:58

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.