Deutsch's Problem (Part 5)

Today, we will explore the oracle Uf.  Yesterday, we saw that the first two Hadamard gates produce two qubits that equally weight all four binary states in superposition (two of them with negative coefficients).  I am now going to drop the normalization constant to keep the equations a bit simpler.  So,  we can describe the input to the oracle as the state

|00>-|01>+|10>-|11> .

The oracle has two qubit inputs, |x> and |y>, and two qubit outputs, |x> and |y+f(x)>, where f(x) is one of the four secret mappings we previously discussed.  Given the input from the output of the two Hadamards, we can write the oracle output as the sum of these four factors:

Adding the above four terms together and simplifying yields

And tomorrow, we will see what happens when we put this through the final Hadamard gate.

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.

Deutsch's Problem (Part 3)

Here is the quantum circuit that solves Deutsch’s problem with one step, as opposed to the two steps required with a conventional computer.  Uf is the oracle.  All four combinations are illustrated.

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.

Deutsch's Problem (Part 1)

Physicist David Deutsch made significant contributions to the foundations of quantum computing.  He defined an extension to the Turing Machine model of computing based on the expanded capabilities of quantum computing, yielding a Quantum Turing Machine model and its implication for computational complexity (which is still a hot topic these days).  He also defined the quantum circuit model that we use to describe quantum algorithms.

Deutsch is interested in quantum computing because of what it tells us about the foundations of quantum mechanics and of physical reality itself.  He is a strong proponent of Hugh Everett’s Many-Worlds Interpretation of quantum mechanics, and asserts that quantum computations take place in parallel universes.

In 1985, Deutsch published the paper Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer that, among other fundamental ideas, described the first quantum computing algorithm, now known as Deutsch’s problem.  The algorithm was subsequently simplified in 1998 by Cleve, Ekert, Macchiavello, and Mosca in the paper Quantum Algorithms Revisited.

Deutsch’s Problem does not have practical utility, but it was the first (and is probably the simplest) demonstration that quantum computers are more powerful than classical computers.  Next time, I will describe the algorithm.