1
$\begingroup$

In Quantum Country's post on the quantum search algorithm, they lay out the search algorithm for the case where there is exactly one solution $| s \rangle$. The key steps are to start in the equal superposition state $|E \rangle$ and then apply a Grover iteration $\pi \sqrt N / 4$ times. The Grover iteration is to reflect about the $|s \rangle$ state and then reflect about the $|E \rangle$ state, resulting in a rotation of the current state $|\psi \rangle$ towards $|s \rangle$.

I am having trouble seeing what we would do differently in the case where we do not assume there is one exact solution. The post recommends starting with thinking about the case where there are exactly two solutions, $|s_1 \rangle$ and $|s_2 \rangle$. It seems to me the exact same algorithm and circuit for rotating around $|s \rangle$ would work. Instead of rotating towards one specific solution in the first step of the Grover iteration, we would rotate towards the plane generated by $|s_1 \rangle$ and $|s_2 \rangle$. But that is okay, since getting our state very close the plane generated by the two solutions would mean we can measure the state and get a solution with high probability.

Is there anything else we must modify in the algorithm for search to handle two possible solutions (or N possible solutions)?

For context, the rotation about $|s \rangle$ looks like this, where $C_s$ is an oracle that flips the working bit if $|x \rangle$ is a solution (image from QC):

Circuit for rotating around solution state

$\endgroup$
1
$\begingroup$

The only thing we need to modify is the number of iterations we do.

The geometric representation of the Grover iteration is a rotation of the system state by an angle $2\Delta$, where $\Delta \approx \sqrt{\frac{M}{N}}$ ($N$ is the size of the search space, and $M$ is the number of solutions, $M \ll N$).

You need to rotate the state by approximately $\frac{\pi}{2}$, which is going to take about $\frac{\pi}{4\Delta} \approx \frac{\pi}{4}\sqrt{\frac{N}{M}}$ iterations. In other words, the more solutions your problem has, the fewer iterations we need to do (which makes sense).

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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