A current arriving from the left reaches the light bulb if one of the two gates is closed. Suppose that the two gates are closed when the corresponding switches are on and write 1 for a switch being on, 0 for a switch being off, and 1 or 0 for the bulb being on or off respectively. Then an input of two bits (corresponding to the switch positions) generates an output of one bit (corresponding to the state of the bulb).
In the previous article we gave you a rough idea of the physical processes quantum computers exploit in order to be more powerful than ordinary ones. Or would exploit, if it were possible to build large-scale quantum computers powerful enough to perform useful tasks. While this prospect is still some decades away, people do understand quite a lot of theory of quantum computation. Using the mathematics of quantum mechanics and logic, you can figure out what quantum algorithms can do even if you don't have an actual computer. In this article we look at one such algorithm in more detail: it's a simpler version of the one developed by Deutsch and Jozsa that is discussed in the previous article. You don't need to be familiar with the maths of quantum mechanics, as we'll guide you through the algorithm giving you as much information as you need.
A very important gate
An important fact in ordinary computer science is that any algorithm you might care to dream up can be implemented using a combination of a small collection of logic gates: as the name suggests, these are electrical circuits with gates in them, designed to take only one or two bits as input and produce a new bit as output. An example is the OR gate, shown on the right.
The same is true for quantum computing: a combination of a small number of quantum gates is enough to build any quantum algorithm — that has been proven mathematically. One of the most important ones is called the Hadamard gate, and it can actually be built in reality (see this article for a little more detail). When a Hadamard gate receives a qubit in state 0 as input, it returns a qubit as output that is in a superposition of 0 and 1 — it's both of them simultaneously.
It’s not just any superposition though. As we mentioned in the previous article, when you measure a system in superposition, it collapses and you only observe one of the possible outcomes. If we measure the output of the Hadamard gate after it’s received a qubit that’s a 0, there is a 50:50 chance of seeing a 0 or a 1. Physicists have a special way of writing this superposition:
A qubit in superposition is like a switch being on and off at the same time.
The terms and stand for the qubit being a 0 or a 1 and the symbol indicates that we have a superposition of both possibilities. But why does each term come with a rather than a which corresponds to the probability of observing it?
The answer would take us deeper into the mysteries of quantum mechanics, so let's just say this: in ordinary life, we deal with probabilities, which are always positive numbers. The sum of the probabilities of alternative outcomes (such as seeing a 0 or seeing a 1) is always 1. In quantum mechanics there is a more general concept, called a probability amplitude, which is allowed to be a negative number (in fact, amplitudes are complex numbers). The amplitudes of alternative outcomes don't need to add up to 1, but the sum of their squares does. The coefficients in our expression above are amplitudes, and they satisfy this requirement:
Amplitudes are related to probabilities through squaring: the probability of seeing a particular outcome when you make a measurement is the square of the absolute value of its amplitude. So in our example above, the amplitude corresponds to the probability of as required.
So much for feeding a qubit in state 0 into a Hadamard gate. When a qubit that is in state 1 passes through it, it is also put into a superposition of 0 and 1, but this time the amplitude of is negative:
How does this differ from the state we got from inputting a 0? The squares of the amplitudes are the same in each case, so measuring gives a 50:50 chance of seeing a 0 or a 1 in both cases. The difference lies in how the two states evolve over time and interact with other states or qubits. Probability amplitudes are complex numbers, which contain more information than just a single positive number. In some sense all the mystery of quantum mechanics, the weird phenomena like superposition that don’t chime with our experience of the world, is hidden in that extra information.
The Hadamard gate also gives us a good example of another phenomenon that’s important in quantum computing, called interference. To see how this works, let’s pass a through the Hadamard gate to get the superposition
What happens to this if we pass this through the Hadamard gate again? Luckily, nature has been kind in making the maths needed to work this out quite easy. We can muddle through even without a formal introduction: simply apply the formulae from above, which tell us what the gate does to a and a to the individual components of the superposition. This gives
Multiplying out the brackets it’s easy to see that the terms cancel out, leaving us with
The amplitude of in this expression is which means that if we measure the qubit now we will definitely see a .
Waves can interfere constructively, re-enforcing each other, or destructively, cancelling each other out.
Interference is exactly this cancellation or adding up of terms. There is destructive interference, where the coefficients of a term — in our example — cancel out, so the term disappears. And there is also constructive interference, with coefficients adding up. This is what happened to the term in our example. People often think of this in terms of waves, which can also interfere constructively or destructively (see here for an explanation).
Interference means that starting with and applying the Hadamard gate twice gives you back the initial
You can convince yourself that the analogous thing happens when you start with a
Now let’s return to the algorithm developed by Deutsch and Jozsa, which we used as an example in the previous article. The task to perform was to check whether a function that takes bit-strings of 0s and 1s as input is constant or balanced. Constant means that the function allocates the same value, 0 or 1, to all bit-strings. Balanced means that it allocates a 1 to exactly half of the bit strings and a 0 to the other half.
The simplest possible situation is when the bit-strings that form the input of the function are only one bit long. A constant function would be either:
And a balanced function would be either
If you are working with a classical computer, then a program that finds out whether the function is constant or balanced needs to look up the values of the function twice: once to check its value for and once to check it for There just isn’t a quicker way of finding the answer to your question. What Deutsch and Jozsa showed in 1992 is that there’s a quantum algorithm which can look up the value of the function for both and simultaneously and then tell you whether the function is constant or balanced.
The general idea
The algorithm uses two basic facts. The first fact involves the superposition state
You can change this state into its negative simply by adding to each component, using binary addition, which means that is equal, not to , but to . This gives
We’ll keep this in mind as a potential method for changing signs.
The second fact is the one we already saw above. That a Hadamard gate changes the superposition states
into and respectively.
Now suppose you are dealing with a similar superposition state, but with the signs of the two amplitudes determined by the values of the function . Let’s call this state :
This means that the amplitude of has a negative sign if and a positive one of The same goes for the amplitude of A constant function would therefore give you
and a balanced function
When we apply the Hadamard gate to the state the signs simply pass through the process. A constant function results in either a or a Whichever it is, when we make a measurement, we will definitely see a
A balanced function results in either a or a Whichever it is, when we make a measurement, we will definitely see a
Therefore, if we can produce the state somehow, the Hadamard gate will give us the answer to our question, whether is constant or balanced, with certainty.
Now let’s put all this together and see how the algorithm works. Since it is based on two facts, you might not be surprised that it uses two qubits. First note that to answer the question of whether is constant or balanced, whether we do this classically or using quantum computing, we obviously need to assume that the computer has some method for "looking up", or computing, values of : given an or a it needs to be able to find out what or is. This is something we take as a given, which is why we call this method a black box: we know what it does, but we don’t care how it does it.
We can equally-well assume that we have a black box that works with two pieces of information, an input register and an output register. In the case of classical bits, given an input register set to (which is a or a ) and an output register set to (also a or a ) the black box finds and adds it to giving as the result. The addition here is again binary (and hints towards our first fact above). Our box is just another way of telling us what is, and in terms of answering our question, this doesn’t make a difference: we would still need to use the box twice to decide if the function is constant or balanced.
In the quantum context the registers are qubits and the black box is a quantum gate which transforms the two-bit system made up of and (where and are or ) into and
And here comes the trick. To produce the state we apply the box with input register
and with output register
The input register will be transformed into The transformation involves nothing more than potential sign switches (depending on ) and these will be performed with the help of the output register, which, as fact one above tells us, is capable of performing this task.
Once has been produced in this way (with one use of he black box) we simply use the Hadamard gate to find out whether is constant or balanced.
To show that our box really does the right thing, we make use of the very convenient fact that our two-bit system can be mathematically represented as a product:
which can be rewritten as
To see what the black box does to the term
we simply see what it does to each component of the superposition This gives:
When this is just
But when fact one above tells us that we have
Putting this together (passing the potential sign change through the expression) we have
Similarly, the black box turns the term
Substituting (2) and (3) back into (1) gives
Here is the state we were after!
Deutsch's and Jozsa's algorithm was a breakthrough because it was the first quantum algorithm that was provably better than a classical one: it needed only one shot of looking at the function values (simultaneously for 0 and 1) rather than two. They later generalised the algorithm to work for functions that don't take just 0s and 1s as input, but strings of them (see the previous article). They proved that in this case the quantum algorithm is exponentially faster than its classical counterpart.
That's all very exciting, but is it any use? The problem the Deutsch-Jozsa algorithm solves isn't particularly useful in the real world. What other tasks can quantum perform better than classical ones? And how far away are we from having fully functional quantum computers? To find out, read the following articles:
About this article
Marianne Freiberger is Editor of Plus. She would like to thank Richard Jozsa, Leigh Trapnell Professor of Quantum Physics at the University of Cambridge, for his extremely helpful, very patient and generally invaluable explanations.