# Is Grover's algorithm only applicable to a pure state?

I've been trying to perform Grover's algorithm on entangled states, e.g. $$|00\rangle + |11\rangle$$. However, the algorithm apparently doesn't seem to amplify the amplitude of the state $$|11\rangle$$ which I have marked. Instead it only applies a net effect of a phase flip, despite applying both oracle and diffusion operator. Is Grover search only applicable to uniform, "pure" states?

• A pure state is any state that can be written in vector form. Hence, the state $|\psi \rangle = |00\rangle + |11 \rangle$ is a pure state, but it is an entangled stated. Whereas the state $|\phi \rangle = |00\rangle + |01\rangle + |10\rangle + |11 \rangle$ is also a pure stat, but it is not an entangled state. It is rather a uniform superposition state. How did you implement the Grover diffuser operator for this state $|\psi \rangle$? Make sure that you implement this diffuser operator, $2|\psi \rangle \langle \psi | - I$, correctly. Nov 8, 2020 at 1:33
• *modulo normalizing factors Nov 8, 2020 at 3:42

## 1 Answer

The problem is that you have only two states in your database. So when you mark state $$|00\rangle$$ its amplitude is $$-1$$ while the other state has amplitued $$1$$ (note that I ignore normalization constants). Hence an average of amplitudes is zero. When you flip the amplitudes around the zero average, the amplitudes still have absoute value $$1$$. As a result, you cannot increase a probability of the marked state.

• Is there any way to solve this problem ? Is the solution simply adding stuff to the database ? Nov 8, 2020 at 12:19
• Say one has an arbitrary entangled state with many terms in the superposition. Is it assumed the algorithm would work then? What if the zero state is not available in this entangled form? E.g. $|1\rangle |2\rangle + |2\rangle |3\rangle + ... |n\rangle |n+1\rangle$. Here there is no zero state and is entangled. I tried implementing this but it only gives some amplitude increase, but also introduces other unwanted states that weren't there before into the state. Nov 8, 2020 at 17:05
• @Jonathcraft: It seems so. But the two records database is rather trivial problem. You do not need Grover algorith. Just based on output of the oracle you can get the solution - 1 for a desired state, 0 for the second one. Nov 9, 2020 at 11:16
• @At2005: It does not depend on which states you have but on its count. As mentioned in my previous comment, two records databses is trivial example and I would not bother with Grover here. Nov 9, 2020 at 11:17