4
$\begingroup$

What does Grover's algorithm output when the desired element is absent from the database? Since there will be no phase inversion, how exactly will the probabilities work?

$\endgroup$
5
$\begingroup$

When it is absent, it will just output one arbitrary state.

As it is not the desired element, you may repeat the search algorithm again (even in the case it was present, you could have measured another computational basis – the algorithm uses probability after all so that's why it may be necessary to repeat) and you will finally conclude that it is not present.

The inversion about average operator changes the amplitudes of the states $\alpha_i$ to $$ - \alpha_i + 2 \langle\alpha\rangle\,, $$ where the last term is the average of the amplitudes. You see in the case of no marking, it has no effect, so all computational bases will have the same probability of being measured.

You can check the explanation in Nielsen and Chuang's book.

$\endgroup$
  • $\begingroup$ Hey, Thank you for your reply! I have one follow question though: How does repeating the algorithm help me in finding out that the element is NOT present? Is there a way to non-randomize the output in case element is absent and conclude that the element is actually absent? $\endgroup$ – Debojyoti Sarkar Jan 25 at 11:26
  • 1
    $\begingroup$ It is just that the Grover's algorithm is probabilistic so if you apply it only once and you have been unlucky in your measurement outcome, just to confirm you can do multiple applications. If all the measurement outcomes do not give you the desired element, you can just say I haven't find it. You have also the possibility to do quantum counting. $\endgroup$ – cnada Jan 25 at 11:39
  • $\begingroup$ Is there a way, other than performing multiple searches, by which we can deterministically say that an element is absent? $\endgroup$ – Debojyoti Sarkar Jan 26 at 10:03
  • 1
    $\begingroup$ Quantum counting. It should give you 0 saying you didn't mark/find any item. $\endgroup$ – cnada Jan 26 at 12:36
  • 1
    $\begingroup$ Quantum counting is a bit different than the quantum search algorithm. We use phase estimation (which can yield one and only output in special cases) to find the number of solutions of a search problem. You can check this Wikipedia link to learn more about it (especially the quantum existence problem): en.wikipedia.org/wiki/Quantum_counting_algorithm. In the case of 0 solutions, your output should be the bitstring 0. In case of another result, you can say it exists. $\endgroup$ – cnada Jan 27 at 13:04

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.