Grover's algorithm for finding 6/8 states

Question

I'm trying to apply the diffusion operator to this state (normalization factors excluded): $|000\rangle + |001\rangle - |010\rangle - |011\rangle - |100\rangle - |101\rangle - |110\rangle -|111\rangle$

However, I get the resulting state: $|001\rangle+|001\rangle$

This is the opposite of what I want. Is there a solution? I know that my oracle is correct since I can view the phases of $\pi$:

.

And my implementation of the diffusion operator is the same one as for all 3 qubit states - yet I still get a resulting state of:

Answer 1

This is a well known behavior of Grover's algorithm. It is described in "Quantum Computation and Quantum Information" book under section 6.1.4

[...] the number of iterations needed by the search algorithm increases with $M$, for $M ≥ N/2$. Intuitively, this is a silly property for a search algorithm to have: we expect that it should become easier to find a solution to the problem as the number of solutions increases.

You will find also a workaround for this issue:

[...] by adding a single qubit $|q\rangle$ to the search index, doubling the number of items to be searched to $2N$. A new augmented oracle $O'$ is constructed which marks an item only if it is a solution to the search problem and the extra bit is set to zero.

Answer 2

Unfortunately Grover does not work for your setup. I guess your Quantum Circuit looks as follows. To 1) mark the states you want to boost, with a negative phase and 2) apply the Grover Diffusion Operator.

000 : 0.3535533905932739
001 : 0.35355339059327384
010 : -0.35355339059327384
011 : -0.35355339059327384
100 : -0.353553390593274
101 : -0.3535533905932739
110 : -0.35355339059327384
111 : -0.35355339059327384

After having marked the states with a negative phase, the average amplitude will be $\frac{(2/\sqrt{8} - 6/\sqrt{8})}{8} = -0.177$. If you now apply the diffusion operator, you will perform a reflection around that average and receive the following amplitudes:

1. $\left| \psi \right> - 2*(\left| \psi \right> - \left| r \right>) = -0.707$ (for the states with positive amplitude)
2. $-\left| \psi \right> - 2*(-\left| \psi \right> + \left| r \right>) = 0$ (for the states with negative amplitude)

Since $\left| r \right> = \frac{(2/\sqrt{8} - 6/\sqrt{8})}{8} = \lvert \frac{1/\sqrt{8}}{2} \rvert$

That the Grover algorithm seems not to work for cases where you are searching for 6/8 versus searching for 2/8 is not surprising, as I believe that the algorithm was originally invented to search for a single state. In order to boost its amplitude by reflection around the average amplitude of all the states.

I also found versions that can search for more than one particular states, like in https://qiskit.org/textbook/ch-algorithms/grover.html.

What you could do is to re-phrase the problem and search for the states $\left| 000 \right>$ and $\left| 001 \right>$. Then you immediately know the 'location' of the others.

Answer 3

If you recall from the analysis of Grover's algorithm, if the success probability of obtaining an item of interest is $\sin^2(\theta)$ just before a Grover iteration, then just after one iteration of Grover's iterate the probability of obtaining an item of interest goes from $\sin^2(\theta)$ to $\sin^2(3\theta)$.

Now in the case in the question, you mark $6$ out of $8$ items, i.e., you have $6$ items of interest out of the total $8$ elements. So the probability of obtaining an item of interest on measurement is $\sin^2(\theta) = \frac{6}{8} = \frac{3}{4}.$ So we get $\theta = \sin^{-1}{\sqrt{\frac{3}{4}}} = \frac{\pi}{3}$ in radians. Then after one iteration of Grover's algorithm, the success probability of obtaining an item of interest becomes $\sin^2(3\cdot \frac{\pi}{3}) = 0$. In such a scenario, if you measure the state obtained after one iteration of Grover's iterate, you would not see any item of interest. Notice that this is exactly as remarked in the question. After one iteration, you see none of the $6$ elements that you have marked.