2
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$ – KAJ226 Nov 8 '20 at 1:33
  • $\begingroup$ *modulo normalizing factors $\endgroup$ – Mark S Nov 8 '20 at 3:42
2
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Is there any way to solve this problem ? Is the solution simply adding stuff to the database ? $\endgroup$ – BrockenDuck Nov 8 '20 at 12:19
  • $\begingroup$ 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. $\endgroup$ – At2005 Nov 8 '20 at 17:05
  • $\begingroup$ @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. $\endgroup$ – Martin Vesely Nov 9 '20 at 11:16
  • $\begingroup$ @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. $\endgroup$ – Martin Vesely Nov 9 '20 at 11:17

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.