Quantum Koan: High Probability
A novice approached the master asking for a code review of his implementation of Grover’s search. The master examined the code and found that the algorithm terminated after applying a certain number of iterations and measuring the qubits to obtain the answer. The measurement was preceded by a comment: “This produces a solution to the search problem with high probability”.
That evening at dinner the novice was served a separate bowl with a note: “This food is not poisoned with high probability”.
Upon seeing this the novice was enlightened.
Had the novice implemented Deutsch–Jozsa,
They would not have gone to bed hungry.
Randomized algorithms are like that,
No matter quantum or classical.
This pseudo-koan has been inspired by The Codeless Code – a collection of short metaphoric stories about software development.
If you need more insight in the nuances of Grover’s algorithm, try to implement it in the Grover’s algorithm quantum kata.