Deutsch – Jozsa algorithm
In the video, we required absolute certainty of both the classical and the quantum computation. If you have already tried k inputs, and have found the same output for all of your tries, what is then the probability that the function actually is constant?
Pconstant(k) = 1 – 2-(k-1)