7
Quantum Gates and Circuits

Quantum gates and circuits are a natural extension of both classical gates and circuits. They are also another way of thinking about the mathematics that describes sending qubits from Alice to Bob.

I commute by train. Often the train I am on is stationary, with another train also at a standstill just inches away from my window. One train will move slowly. Sometimes it is impossible to tell whether it is my train or the other one that is moving without turning to look out of the window on the opposite side. We could be inching forward, or the train moving in the opposite direction could be inching forward. Both scenarios fit. The same analysis applies to Bob’s measurements. We can either think of Bob as rotating his measuring apparatus, or we can think of Bob as keeping his apparatus in the same direction as Alice, but somehow the qubit gets rotated on the trip from Alice to Bob. When Alice and Bob are far apart, it often makes sense to think of Bob’s apparatus as being rotated. But we are going to send qubits to ourselves. We could think of our apparatus rotating during the travel time, but it is more natural to think of the apparatus as fixed and the qubit as being rotated. We think of the rotation as happening between the time it is sent and the time it is measured. Sending the qubits through a quantum gate performs this rotation. Previously we said that choosing directions to measure our qubits correspond to choosing an orthogonal matrix. Now we think of the directions we are measuring as being fixed and the orthogonal matrix as corresponding to a gate that the qubits pass through. Before we look at examples, we will introduce some new names for our basis kets.

Qubits

Since we are going to think of our measuring device as being fixed, we need to use only one ordered basis for both sending and receiving qubits. The natural basis to choose is the standard one . Earlier we denoted this as . But we also associated the first vector in the ordered basis to the bit 0 and the second vector to 1. Now that we are solely going to use this basis it makes sense to give our kets new names that reflect how they relate to bits. We let denote and denote

In general a qubit will have the form , where . When we measure it, either the state jumps to and we read 0, or the state jumps to and we read 1. The first occurs with probability , the second with probability .

Usually we have a system with more than one qubit, which means that we have to form tensor products. For a system with two qubits the underlying ordered basis is

This can be written as . As we noted before, we often suppress the tensor product symbols, and so we write the product even more succinctly as . Finally, we make the convention that we let denote , giving the representation that is short and easy to read.

How does this connect to gates? This is what we will consider next. We start by reexamining the CNOT gate.

The CNOT Gate

As we saw, the classical CNOT gate takes two input bits and gives two output bits. It’s defined by the table:

We extend this to qubits in the natural way—replacing 0 by , and 1 by . The table becomes:

This can be written more succinctly using our compact notation for tensor products.

The table tells us what happens to the basis vectors. We then extend to linear combinations of the basis vectors in the obvious way.

It just flips the probability amplitudes of and .

We keep using the diagram we used previously for the CNOT gate, but we must be careful about how we interpret it. For classical bits, the bit entering the top wire on the left, leaves the top wire on the right unchanged. This is still true for qubits if the top qubit is either or , but it is not true for other qubits.

For example, we take as the top qubit and for the bottom one.

The input is . This is sent by the CNOT gate to .

This state, as we recognize from the EPR experiment, is an entangled state. Consequently, we cannot assign individual states to the top and bottom wires on the right side. We draw the diagram in the following way.

The wires represent our electrons or photons. These are separate objects and can be far apart. We will often talk about the top qubit and the bottom qubit and think of them as being far apart. But, remember, if they are entangled, a measurement on one will affect the state of the other.

This example illustrates how we will often use this gate. We can input two unentangled qubits and use the gate to entangle them.

Quantum Gates

Notice that the CNOT gate permutes the basis vectors. Permuting the basis vectors in an ordered orthonormal basis gives another ordered orthonormal basis, and we know that associated with any of these bases is an orthogonal matrix. Consequently, the matrix corresponding to the CNOT gate is orthogonal. In fact, all of the reversible gates that we introduced in the last chapter permute basis vectors. They all correspond to orthogonal matrices. This gives us the definition of quantum gates. They are just operations that can be described by orthogonal matrices.

Just as for classical computation, we want to assemble a small collection of simple gates that we can connect together to form circuits. We start by looking at the simplest gates, those that act on just one qubit.

Quantum Gates Acting on One Qubit

In classical, reversible computation there are only two possible boolean operators that act on one bit: the identity that leaves the bit unchanged, and NOT, which flips the values of 0 and 1. For qubits there are infinitely many possible gates!

We begin by looking at the two quantum gates that correspond to the classical identity and that both leave the qubits and unchanged. Then we will look at the two quantum gates corresponding to flipping the qubits and . These four gates are named after Wolfgang Pauli and are called the Pauli transformations.

The Gates I and Z

The gate I is just the identity matrix

We will see how I acts on an arbitrary qubit .

Unsurprisingly, I acts as the identity and leaves qubits totally unchanged.

The gate Z is defined by the matrix

Again, let’s see how Z acts on an arbitrary qubit .

So, Z leaves the probability amplitude of unchanged, but it changes the sign of the probability amplitude of . But let’s look at what Z does a little more carefully.

First, we will look at how it acts on the basis vectors. We have and . But recall that a state vector is equivalent to that state vector multiplied by , so is equivalent to ; consequently, Z preserves both of the basis vectors, but it is not the identity. If we apply Z to the qubit , we obtain

and, as we showed earlier, is distinguishable from, not equivalent to, .

Even though the transformation Z preserves both the basis vectors, it changes every other qubit! This operation of changing the sign of a probability amplitude is sometimes called changing the relative phase of the qubit.

The Gates X and Y

The gates X and Y are given by:*

They both correspond to NOT in that they interchange and . The gate X just flips, while Y flips and changes the relative phase.

The Hadamard Gate

The last and most important gate that acts on one bit is the Hadamard gate, H. It is defined by

This gate is often used to put the standard basis vectors into superpositions:

In diagrams, gates that act on one qubit are denoted by a square with the appropriate letter drawn in the center. For example, the Hadamard gate acting on one bit is denoted by the following.

We have named five quantum gates that act on just one qubit. Of course, there are infinitely more. Any rotation will give us an orthogonal matrix, and there are infinitely many of these, all of which can be considered as gates.

Are There Universal Quantum Gates?

In classical computing, we found that every boolean function could be given by a circuit that used only Fredkin gates, telling us that the Fredkin gate is universal. We also saw that NAND, along with fan-out, was universal. Are there universal quantum gates?

In the classical case, there are only finitely many boolean functions with a given number of variables. There are just two boolean functions of one variable. There are four of two variables. In general, there are possible functions with n variables. Things are very different with quantum gates. As we have seen there are infinitely many possible gates that can act on just one qubit. If we take a finite number of gates and connect them in a finite number of ways, we will end up with a finite number of circuits. So, it is just not possible to have a finite number of gates generate an infinite number of circuits.

The short answer to the question of whether or not there is a finite set of quantum gates that is universal is just “no.” However, even though it is impossible to have a finite number of quantum gates that will generate every other possible quantum circuit, people have shown there is a finite collection of gates that can be used to approximate every possible circuit, but we will not go into this. All of the circuits that we need can be constructed from the gates that we have introduced; five that act on just one qubit, and one, the CNOT gate, that acts on two qubits.

No Cloning Theorem

We first came across the fan-out operation when we were looking at classical circuits. One input wire is connected to two output wires. The input signal is split into two identical copies.

We then looked at reversible gates. For these, if you have two outputs, then you must also have two inputs. We could get the fan-out operation by using an ancilla bit—taking the second input always to be 0. One way of doing this is with the CNOT gate.

, , so , if is either or . Unfortunately, if is not or , we don’t end up with two copies. We saw this when we input into the gate. It resulted in an entangled state, not two copies of the left qubit. We can use to copy classical bits, but not general qubits.

The term fan-out is restricted to classical computing. We use the word cloning for the analogous idea in quantum computing. Cloning is like fan-out, but for qubits. We want to make copies not just of classical bits but also of qubits. We want a gate that inputs a general qubit and a fixed second input (an ancilla bit) and outputs two copies of . A diagram of our desired gate follows.

The question of cloning becomes the question of whether or not the gate G can exist. We will show that it cannot, showing that it is impossible to clone general qubits. We do this by supposing that there is such a gate and then showing that two contradictory consequences follow logically from this assumption. Since our argument is logically sound and contradictions should not occur, we conclude that our initial assumption that G existed was false. Here’s the argument.

If G exists, we know that its cloning property gives:

1. .

2. .

3. .

These three statements can be restated to give:

1. .

2. .

3. .

The gate G, like all matrix operators, must be linear, which means that

Replacing and using statements (1) and (2) gives

But statement (3) says that

However,

So we have shown that if G exists then two things that are not equal must be equal. This is a contradiction. The only logical conclusion is that G cannot exist, and it is impossible to construct a gate that clones general qubits. The argument we have given used for the ancilla bit. There is nothing special about this. Exactly the same argument can be used whatever value is chosen for this bit.

The inability to clone a qubit has many important consequences. We want to be able to back up files and send copies of files to other people. Copying is ubiquitous. Our everyday computers are based on von Neumann architecture, which is heavily based on the ability to copy. When we run a program we are always copying bits from one place to another. In quantum computing this is not possible for general qubits. So, if programmable quantum computers are designed they will not be based on our current architecture.

At first, the fact that we cannot clone qubits seems like a serious drawback, but there are a couple of important comments that need to be made.

Often we want to prevent copying. We want to secure our data—we don’t want our communications to be tapped. Here, as we saw with Eve, the fact that we cannot clone qubits can be used to our advantage, preventing unwanted copies from being made.

The second comment is so important it deserves its own section.

Quantum Computation versus Classical Computation

The qubits and correspond to the bits 0 and 1. If we run our quantum CNOT gate just using the qubits and , and not any superpositions, then the computation is exactly the same as running a classical CNOT gate with 0 and 1. The same is true of the quantum version of the Fredkin gate. Since the classical Fredkin gate is universal and the quantum Fredkin gate using just and is equivalent to the classical gate, we can see that a quantum circuit can calculate anything that can be calculated by a classical circuit. The no-cloning property may seem worrisome, but it doesn’t restrict us from doing classical computations in any way.

This is a deep result. It shows that if we compare classical and quantum computation, we shouldn’t think of them as different types of computation. Quantum computation includes all of classical computation. It is the more general form of computation. The qubit is the basic unit of computation, not the bit.

Now that we have seen some basic gates, we will start to connect them together to form circuits.

The Bell Circuit

We call the following quantum circuit the Bell circuit.

To see what it does, we will input the four pairs of qubits that form the standard basis. We start with . The first qubit is acted on by the Hadamard gate’s changing it to , so the system of two qubits has state

at this stage. We now apply the CNOT gate. This flips to , giving the final state .

We can represent the situation by the following picture.

We will summarize this by

Convince yourself that

Each of these outputs is entangled. Since the inputs form an orthonormal basis for , the outputs must also form an orthonormal basis. This basis, consisting of four entangled kets, is called the Bell basis.

Recall that the way to tell whether a square matrix A is orthogonal is by calculating , where is the transpose matrix obtained from A by interchanging the rows and columns. If we get the identity matrix I, then the matrix is orthogonal and the columns of the matrix give us an orthonormal basis. If we don’t get the identity, then the matrix is not orthogonal. We have defined our gates to be orthogonal, so they all have this property. In fact, all the gates we have introduced in this chapter, with the one exception of the Pauli matrix Y, also have the property that when you take the transpose matrix you end up with exactly the same matrix you started with.** Consequently, for all of these gates, . This tells us that if we apply the gate twice in a row we end up with an output that is unchanged from the input. The second time we apply the gate, it undoes what we did when we applied it the first time.

We will see a couple of uses of the Bell circuit in a moment, but first we make use of the fact that the Hadamard gate and the CNOT gate are their own inverses. Consider the following circuit:

If we send a pair of qubits through the circuit, the first thing that happens is that the Hadamard gate is applied, and then we apply the CNOT gate. This action is immediately undone by the second application of the CNOT gate. Finally, the second application of the Hadamard gate undoes the action done by the initial Hadamard gate. The result is that the circuit doesn’t change anything. The qubits output are identical to the qubits that entered. The second half of the circuit reverses what the first half does.

This means that the following circuit, which we will call the reverse Bell circuit, reverses the action of the Bell circuit.

In particular, we know what happens if we input vectors from the Bell basis. It is going to give us vectors in the standard basis.

If we input , it will output .

Now that we have the basic properties of the Bell circuit, we will see how it can be applied to do some very interesting things. We look at superdense coding and quantum teleportation.

Superdense Coding

The initial setup for both superdense coding and quantum teleportation is the same. Two electrons have the entangled spin state . One of the electrons is given to Alice and the other to Bob. They then travel far apart, both being careful not to make any measurement of their respective electron, preserving the entangled state.

In superdense coding, Alice wants to send Bob two classical bits of information, that is, one out of the following possibilities: 00, 01, 10, 11. She is going to do this by sending Bob one qubit—her electron. We will outline the exact procedure in a moment, but first we will analyze the problem to see what we want to do.

Initially, it seems as though the solution should be easy. Alice is going to send Bob a qubit . There are infinitely many choices for the qubit, anything that satisfies will do. Surely, it must be easy to construct a way of transmitting two bits of information—one out of four possibilities—if you are allowed to send something that can be one of an infinite number of things. The problem is, of course, that Bob can never know what the qubit is. He can get information only by measuring. He will measure the spin in the standard basis and get either or . If Alice sends him , he will get with probability and with probability . If he gets , he knows nothing about , except for the fact that it is nonzero. Bob can get at most one bit of information from each qubit. In order to get two bits of information he will have to extract one bit from the particle that Alice is sending him, but he must also extract one bit from the particle in his possession.

Alice and Bob initially have one electron each. Eventually Bob is going to have both electrons and is going to measure their spins. Bob will have some quantum circuit with two wires exiting. If Alice wants to send 00, we need to arrange things so that just before Bob starts measuring, the top electron is in state and the bottom electron is in state , that is, the pair of electrons is in the unentangled state just before Bob measures their spins. Similarly, if Alice wants to send 01, we want the pair of electrons to be in the state just before Bob makes his measurements. The final state should be if Alice wants to send 10, and if Alice wants to send 11.

The final observation is that Bob must do the same thing to every pair of electrons that he receives. He cannot do different things depending on what Alice is trying to send, because he doesn’t know what she is trying to send. That’s the whole point!

The idea behind the method is that Alice will act on her electron in one of four ways. Each way will result in the state of the qubits being one of the basis vectors in the Bell basis. Bob will then run the pair of qubits through the reverse Bell circuit to get the correct unentangled state.

Alice has four quantum circuits, one for each of the two-bit choices. Each circuit uses Pauli gates. The circuits are given below.

We will look at what happens to the qubits in each case. Initially, Alice’s and Bob’s qubits are entangled. They are in state which we will write as

When Alice sends her electron through the appropriate circuit, her kets change. Note that Alice’s circuits do not affect Bob’s electron in any way. We will do the calculation in each case.

If Alice wants to send 00, then she does nothing. The resultant state for the qubits remains as state .

If Alice wants to send 01, she applies X. This interchanges her and her . The new state will be , which we can write as .

If Alice wants to send 10, she applies Z. This interchanges leaves alone but changes her to . The new state will be which we can write as .

If Alice wants to send 11, she applies Y. The qubits end in the entangled state .

Notice that these resultant states are exactly what she wants. Each is a distinct Bell basis vector. Now she sends Bob her electron. When Bob has her electron, he can use a circuit that inputs both the qubit that Alice has sent and the one that has always been in his possession. He uses the reverse Bell circuit.

If Alice is sending 00, when Bob receives the qubits they will be in state . He sends this through the reverse Bell circuit. This changes the state to . This is unentangled. The top bit is as is the bottom bit. Bob now measures the qubits. He gets 00.

If Alice is sending 01, when Bob receives the qubits they will be in state He sends this through the reverse Bell circuit. This changes the state to .This is unentangled. The top bit is and the bottom bit is . Bob now measures the qubits. He gets 01. The other cases are similar. In each case Bob ends up with the two bits that Alice wants to send to him.

Quantum Teleportation

As in superdense coding, Alice and Bob are far apart. They each have one electron. The electrons share the entangled state . Alice also has another electron. It is in state . Alice has no idea what the probability amplitudes a and b are, but she and Bob want to change Bob’s electron so that it has state . They want to teleport the state of Alice’s electron to Bob’s. To do this, we will see that Alice needs to send Bob two classical bits, but notice that there are infinitely many possibilities for the initial state of her electron. It’s impressive that we can send one of an infinite number of possibilities using only two classical bits. It is also interesting that Alice starts with a qubit and Bob ends up with it, but neither of them can ever know exactly what it is. To learn about it, they have to make a measurement. When they measure, they just get either or

We can deduce a few things about how the process will work. Bob is going to end up with an electron in the unentangled state . At the start, Bob and Alice’s electrons share an entangled state. To disentangle the state someone has to make a measurement. Clearly, it cannot be Bob. If Bob makes a measurement he will end up with an electron in state of either or , not the required , so we know Alice will be making a measurement. We also have to get the third electron’s state involved. Alice will have to do something to entangle the state of this electron with the state of her other electron, which is currently entangled with Bob’s. The obvious way of doing this is to send the two qubits that she controls through a CNOT gate. That will be the first step. The second step will be to apply the Hadamard gate to the top qubit. So, in fact, Alice is going to put the two qubits that she controls through a reverse Bell circuit. The situation is depicted as follows, where Alice’s qubits are shown above Bob’s qubit. The second and third rows depict the entangled qubits.

We have three qubits, the initial state that describes the three electrons is

which we can write as

Alice is going to act on her qubits, so we write the state emphasizing these.

Alice is going to apply the reverse Bell circuit. We will analyze this in two steps, first by applying the CNOT gate to the first two qubits and then the Hadamard gate to the top bit. Applying the CNOT gate gives:

Alice now is going to act on the first qubit, so we write the state emphasizing this.

We now apply the Hadamard gate to the first qubit. This changes to

and to .

This results in the state

This can be slightly simplified to give

Alice now measures her two electrons in the standard basis. She will get one of , , , , each with probability 1/4.

If she gets , Bob’s qubit will jump to state .

Alice and Bob want Bob’s qubit to be in the state . It is almost there, but not quite. To sort things out, Alice has to let Bob know which of the four possible situations he is in. She sends Bob two classical bits of information, 00, 01, 10, or 11, corresponding to the results of her measurements, to let him know. These bits of information can be sent in any way, by text, for example.

If Bob receives 00, he knows that his qubit is in the correct form and so does nothing.

If Bob receives 01, he knows that his qubit is . He applies the gate X to it.

If Bob receives 10, he knows that his qubit is . He applies the gate Z to it.

If Bob receives 11, he knows that his qubit is . He applies the gate Y to it.

In every case Bob’s qubit ends in state , the original state of the qubit that Alice wanted to teleport.

It is important to note that there is only one qubit in state at any point during the process. Initially, Alice has it. At the end Bob has it, but as the no cloning theorem tells us, we can’t copy, so only one of them can have it at a time.

It is also interesting to observe that when Alice sends her qubits through her circuit Bob’s qubit instantaneously jumps to one of the four states. He has to wait for Alice to send him the two classical bits before he can determine which of the four qubits correspond to Alice’s original qubit. It is the fact that the two bits have to be sent by some conventional transportation method that prevents instantaneous transmission of information.

Quantum teleportation and superdense coding are sometimes described as being inverse operations. For superdense coding, Alice sends Bob one qubit to convey two classical bits of information. For quantum teleportation, Alice sends Bob two classical bits of information to teleport one qubit. For superdense coding, Alice encodes using the Pauli transformations, and Bob decodes using the reverse Bell circuit. For quantum teleportation, Alice encodes using the reverse Bell circuit, and Bob decodes using the Pauli transformations.

Quantum teleportation is actually being performed, usually using entangled photons rather than entangled electrons, where it can be done over substantial distances. As I write this, it has been announced that a Chinese team has teleported a qubit from Earth to a satellite in low Earth orbit. These experiments are often mentioned on news broadcasts, mainly because of the word “teleportation,” which conjures up images of Star Trek. Unfortunately, quantum teleportation is not something that is readily explained in a brief sound bite, and though many people have heard the term, not many understand exactly what it is that is being teleported.

Quantum teleportation gives a way of transporting a qubit from one place to another without actually transporting the particle that represents the qubit. It is used in various ways to correct errors. This is extremely important for quantum computations. Qubits have a tendency to interact with the environment and get corrupted. We will not study error correction in detail but will only look at a simple example.

Error Correction

I was a student before the advent of CDs. We listened to vinyl records. To play a record we went through an elaborate ritual. First, the record was gently slid from its sleeve, care being taken to hold it by its edges and not get any fingerprints on the surface. Then the record was placed on the turntable. The next step was to clean it of any dust. This often involved an antistatic spray and a special cleaning brush. Finally you lined up the stylus and carefully lowered it to the record.

Even with all these precautions, there were often clicks and pops caused by unseen dust or some minute imperfection. If you accidently scratched it, you would get a pop thirty three times per minute, which made the music unlistenable. Then CDs came. Gone were the pops. You could even scratch the surface and it still played perfectly. It seemed incredible.

Vinyl records have no error correction built in. If you damage them, you cannot recover the original sound. CDs, on the other hand, incorporate error correction. If there is some small imperfection, the digital error-correcting code can often calculate what has gone wrong and correct it.

Encoding digital information involves two essential ideas. The first is to eliminate redundancy to compress the information as much as possible—to make the message as short as possible. A good example of this is making a ZIP file of a document. (Some people don’t like CDs because they think the music has been compressed too much, losing the warmth you get from vinyl.) The second important idea is to add some redundancy back in, but to make it useful redundancy. You want to add in some additional information that will help correct errors.

Nowadays, practically all transmissions of digital information use some form of error-correcting code. There are so many ways that a message can be slightly corrupted, and given a slightly corrupted message, you want to be able to correct it.

Error correction is essential for transmissions involving qubits. We are using photons and electrons to encode them. These particles can interact with the rest of the universe and unwanted interactions may change the states of some qubits.

In this section we will look at the most basic classical error-correcting code and then show how it can be modified for sending qubits.

The Repetition Code

A simple error-correcting code is just to repeat the symbol that we want to send. The simplest case is to repeat it three times. If Alice wants to send 0, she sends 000. If she wants to send 1, she sends 111. If Bob keeps getting sequences of three 0s and three 1s, he assumes that all is well. If he receives something else, say 101, he knows that an error has occurred; the string should have been 000 or 111. If the string that Alice sent was 000, then two errors must have occurred. If the string was 111, then only one error has occurred. If errors are fairly unlikely, it is more probable that one error, rather than two errors, have occurred, so Bob assumes that the least number of errors have occurred and consequently replaces 101 with 111.

There are eight possibilities of three-bit strings that Bob could receive. Four of them are 000, 001, 010, and 100. Bob decodes all of these as 000. The other four three-bit strings are 111, 110, 101, and 011. Bob decodes these as 111. If the chance of error is very small, then this repetition code corrects many errors and reduces the overall error rate. This is fairly straightforward, but we will analyze what Bob does in a way that generalizes for qubits. The problem with qubits is that to read them, we have to measure them, and that can make them jump to a new state. We need a new way of determining what Bob should do. He is going to perform parity tests.

Now, suppose Bob receives the three bits . We will do some computations to show which, if any, of the bits should be changed. Bob computes and .

The first sum checks the parity of the first two bits—that is, it checks whether they are the same digit or not. The second sum performs a parity check on the first and third digits.

If all three bits equal 0, or all equal 1, then he will get 0 for both sums. If not all of the bits are equal, then two will be equal and the third will differ. It will be this third symbol that needs to be flipped from 0 to 1, or from 1 to 0.

If then and .

If then and

This means that Bob can look at the pair of bits and .

If he gets 00 then there is nothing to correct, so he does nothing.

If he gets 01, he flips .

If he gets 10, he flips .

If he gets 11, he flips .

We look at how these error-correcting ideas can be modified for qubits. But before we do we make one important observation. It might seem trivial, but it is what makes the quantum bit-flip correction code work.

Suppose Bob receives a string and there is an error in the first bit. This means that he has received either 011 or 100. After Bob does the parity tests, he will get 11 for both strings and will know that there is an error in the first bit. The key observation is that the parity tests tell us where the error is. They do not tell us whether it is a 0 that needs to be flipped to a 1, or a 1 that needs to be flipped to a 0.

Quantum Bit-Flip Correction

Alice wants to send the qubit to Bob. There are various types of errors that can occur, but we will restrict our attention to bits getting flipped. In this case, gets changed to .

Alice would like to send three copies of her qubit. This, of course, is not possible. The no cloning theorem tells us that she cannot make copies. But she can perform what is essentially a classical fan-out and replace with and with . This is done with two CNOT gates. This is shown in the circuit below.

She starts with three qubits, the one she wants to encode and two ancilla bits that are both , so the initial state is The first CNOT gate changes it to . The second gives us the required state .

Alice then sends the three qubits to Bob. But the channel is noisy, and there is the possibility of a qubit being flipped. Bob might receive the correct qubits , or he might receive one of the following incorrect versions, , or , which correspond to the error occurring in the first, second, and third qubit, respectively. He wants both to detect the error and to correct it. But notice that he cannot make any measurements on this entangled state. If he does, the state immediately becomes unentangled and he just gets three qubits that are some combination of s and s—the values of and are lost, with no way of recovering them.

It is amazing that Bob can determine which bit is flipped, correct it, and yet never make a measurement on the three qubits that Alice sent him! But he can. He uses the parity check idea that we used for classical bits.

He adds an additional two qubits in which to perform the parity checks. The circuit is given below. It uses four CNOT gates. The two on the fourth wire are used to do the parity calculation; the two on the fifth wire do the calculation. The standard first reaction on seeing this circuit is to assume that we end up with five qubits that are hopelessly entangled. But I’ve drawn the picture that shows that the bottom two qubits are not entangled with the top three. Can that really be the case?

Let us suppose that Bob receives The key observation is that if there is an error, then there will be an error in both and , and it will occur in exactly the same place. When we apply the parity checks, both strings give the same results.

To illustrate what is going on, let’s look at Bob’s circuit, ignoring the fifth wire for the moment. The input for the first four qubits is

The two CNOT gates attached to the fourth wire perform the parity check on the first two digits. But , so the four qubits at the right of the circuit will be in one of two states. They will be in state

if .

They will be in state

In both cases, the fourth qubit is not entangled with the top three.

A similar argument applies to the fifth qubit. It is not entangled with the others. It is if , and is if .

Since the bottom two qubits are not entangled with the top three, Bob can make measurements on the bottom two qubits, and it will leave the top three unchanged. This is what he does:

If he gets 00, then there is nothing to correct, so he does nothing.

If he gets 01, he flips the third qubit using by installing an X gate on the third wire.

If he gets 10, he flips the second qubit using by installing an X gate on the second wire.

If he gets 11, he flips the first qubit using by installing an X gate on the first wire.

The result is that the bit-flip error is corrected and the qubits are now back in the state that Alice sent.

In this chapter we introduced the idea of quantum gates and circuits. We have seen some surprising things we can do with just a few quantum gates. We have also seen that quantum computation includes all of classical computation. This doesn’t mean that we will be using quantum computers to perform classical computations, but it does tell us that quantum computation is the more fundamental form of computation.

The next topic that we look at concerns whether we can use quantum circuits to perform calculations faster than can be done with classical circuits. How do we measure the speed of a computation? Are quantum computers always faster than classical ones? These are some of the questions we look at in the next chapter.

CNOT
Input	Output