Deutsch's Problem (Part 2)

I will now describe Deutsch’s Problem.  Let’s assume that we have a black box (called an oracle) and we can’t look inside it to see how it works.  But, we can feed it a 0 or a 1 as input and see the state of the output, which is also a 0 or 1.  If the output is always a 0 regardless of the input, or always a 1, we will call it a constant function.  If the output alternates between 0 and 1, or 1 and 0, as we change the input from 0 to 1, we will call it balanced.  So, here are all of the possible scenarios: 

If we want to figure out whether a given black box has the constant or the balanced property, and we are using conventional computing rules, then it will take two queries to the oracle.  We would ask it for f(0) and f(1) and then, once we have both outputs, we could determine the answer.

If we had a quantum computer, we could get the answer with only a single query!  Next time, we will see how this works.