Deutsch's Problem (Part 4)

We have seen that the quantum solution to Deutsch’s problem can be done in one step using the quantum computing paradigm, while a conventional computing paradigm requires two steps.  Previously, I have given the quantum circuit and shown HOW the matrix calculations yield the solution, but now I will explore the solution at a high level to help guide some intuition about WHY the quantum solution works (over the next few days).  While Deutsch’s problem does not have practical utility, this type of circuit appears in many other quantum algorithms, so some effort spent on this circuit will pay future dividends. 

Again, here is the circuit for the f(0)=f(1)=0 case:

The two Hadamard gates on the left take two qubits as input and produce a superposition of all possible states as output.  If the two input qubits were both |0>, then we would have had an equal weighting of |00>, |01>, |10>, |11> as output.  This is a very common pattern in quantum computing, and relates to the Fourier transform function (I will discuss this someday).  For now, let’s just view this as a handy way to generate two qubits in all four possible states in equal weighted superposition.

Note that in this circuit, the input is not |00>, but |01>.  The consequence of this difference is that two of the superpositions are negative.  The reason for this will become apparent later.  Next time, we will examine Uf.