patternMinor
Grover's Algorithm result when the desired element is not present
Viewed 0 times
resultthepresentdesiredalgorithmelementwhennotgrover
Problem
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#103368, answer score: 4
Revisions (0)
No revisions yet.