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

Question

I've been trying to perform Grover's algorithm on entangled states, e.g. $|00rangle + |11rangle$. However, the algorithm apparently doesn't seem to amplify the amplitude of the state $|11rangle$ 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?

Martin Vesely · Answer

The problem is that you have only two states in your database. So when you mark state $|00rangle$ 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.

Answered by Martin Vesely on January 16, 2021

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

One Answer

Add your own answers!

Ask a Question