Khanh Giang

In the previous article, we looked at why quantum computers are needed and the importance of their ability to be ‘reversible’. Here, we will discover how to create such a “reversible computer” and the logic gates that govern these calculations. In fact, it’s worth pointing out that you are already familiar with the concept of a logic gate (perhaps without realising it), as almost all complex operations that computers are able to do, such as displaying photos, playing music, or playing games, are just the results of hundreds of thousands of these logic gate calculations performed simultaneously.

Formally, a logic gate is an electrical circuit that has one or more binary inputs and one single output, the relationship between which is based on a certain “logic” such as ‘and’, ‘or’, ‘nor’. They are often constructed using diodes and transistors (hence the need to pack more transistors into as tiny a space as possible as discussed in the previous article), but can also be constructed using vacuum tubes, fluids, optics, and many other methods. To begin, let’s look at a few basic gates.

Classical gates: Reversible

The most “boring” gate on paper is the identity gate, whose job is to return the same input. Of course, this gate is reversible, since if the output is 1 the input must also be 1, and hence it’s also a quantum logic gate!

To better understand these gates, let’s look at their truth table (or result table). For the identity gate it’s just:

INPUT	OUTPUT
0	0
1	1

A diagram can also be used to keep track of what happens, and for the identity gate the diagram is just:

Similarly, the other 1-bit gate – the NOT gate is also a reversible quantum gate, whose effect is to reverse the input, like flipping the light switch from on to off or off to on:

INPUT	OUTPUT
0	1
1	0

The symbol for this gate is , and the result of the gates can be show through the below diagram:

For example, the upper path is 0 – NOT Gate, which gives the result of 1.

Classical gates: Irreversible

The two 1-bit logic gates seen above are both reversible, so how do 2-bit logic gates compare? A potentially familiar and somewhat more interesting example is the AND gate, which asks the question: are both A and B in state 1? Remembering that 0 means no and 1 means yes, the truth table is as follows:

INPUT A	INPUT B	OUTPUT Q
0	0	0
0	1	0
1	0	0
1	1	1

Now we encounter our first reversibility problem: Let’s say we have the output Q = 1, then using the truth table above we know the inputs must have been A = 1 and B = 1. But, if we have the output Q = 0, we cannot know whether we had A = 0, B = 0, or A = 1, B = 0, or A = 0, B=1. This process isn’t reversible – given the output we cannot trace back to the input.

A sensible suggestion is to add another bit of data (we call this the “ancillary” bit), to store the solution. To understand how this bit may help, let’s look at a rather strange gate first, the CONTROLLED NOT gate, also called the C-NOT.

The C-NOT is a two qubit gate, whereby one qubit is “controlled” by the other. Let’s first look at the gate diagram:

The black dot on the top line is the CONTROL and the at the bottom line is the NOT gate we have seen above. We can think of the C-NOT gate as though the CONTROL gate is asking “Do you have the key? (ie. are you equal to 1?)” with 1 meaning yes and 0 corresponding to no. Only with the key (a value of 1) is the NOT gate activated, thereby reversing anything that passes through.

Let’s now look again at the two bit system A = 0, B = 1. The A bit is on the top line, so it goes in and meets the CONTROL gate. Since A = 0 (and thus it doesn’t have the key), the CONTROL gate doesn’t do anything and lets both qubits pass through unaltered. The outputs are thus A = 0, B = 1 and thus the input remains unchanged. Similarly, A = 0, B = 0 is also unchanged, the output is still A = 0, B = 0.

Now, if the two bits are A = 1, B = 1, the situation is more interesting. Now, when the qubit A passes through the CONTROL gate, it has the key to make the NOT gate on the bottom line rise up and come into play. As we know, the effect of the NOT gate is to reverse the input (of B only), so our input B = 1 will become B = 0. So the output here is A = 1, B = 0. The truth table below summarises this:

INPUT		OUTPUT
A	B	A	B
0	0	0	0
0	1	0	1
1	0	1	1
1	1	1	0

(The rows in italics emphasise when the output is the same as the input)

A quick check shows that the C-NOT gate is indeed reversible, and thus can be used to construct other more complex quantum gates. (It also helps to realise that there is one output for every input, and one input only for every output, a situation we call 1-to-1 mapping. In fact, for a gate to be reversible, it has to be a 1-to-1 mapping.) Now we are ready to tackle the reversible AND gate – also known as the Toffoli gate.

The diagram for the Toffoli gate is as follows:

Immediately we notice the similarity with the C-NOT gate above: it’s just the C-NOT but with one more CONTROL gate (which is why it’s also called the CCNOT, controlled-controlled-NOT gate!). Just as before, the CONTROL gates still ask “Are you equal to 1?”, but this time, the NOT gate on the bottom line will only be activated when, you guessed it, both A and B are equal to 1. In our analogy, this is as if we need 2 keys to activate the NOT gate totem on the bottom line.

Another important thing to note is that we now have three lines to our logic gate, which means we require 3 inputs, A, B and C.

Let’s look at two examples where the first one has the input A = 1, B = 0, C = 0. Bit A has the key, but bit B does not, so the NOT gate on the third line is not activated, and so bit C passes through unchanged. For the second example with A = 1, B = 1, C = 0: since both bit A and B have the key, they activate the NOT gate and so bit C is reversed into C = 1.

The truth table of the Toffoli gate is as follows:

INPUT			OUTPUT
A	B	C	A	B	C
0	0	0	0	0	0
0	0	1	0	0	1
0	1	0	0	1	0
0	1	1	0	1	1
1	0	0	1	0	0
1	0	1	1	0	1
1	1	0	1	1	1
1	1	1	1	1	0

Whilst at first it may look a little scary, if we look a little closer, we can see that most of the output is the same as the input, except for the last two cases where the bit C is flipped. Since this is clearly a 1-to-1 mapping (for 3 bits with 2 possible values, there are 2³ = 8 cases and all of them are represented in the input and the output table), it is indeed a reversible gate. 

Universal Gates

The Toffoli gate is such a complex gate, that it begs the question: how many gates do we need to realise all the quantum gates needed in a quantum computer? It would be a serious problem if we need hundreds of complex gates like this – the physical space on a processing chip isn’t enough to include too many different gates! 

The logic gate able to perform every calculation without the need to use any other type of gate is called a “universal gate”. For classical computers, the NAND (Not AND), the NOR (Not OR) gate, and the Toffoli gate are all universal gates. For quantum computers, the set of the Hadamard gate, the phase rotation gate and C-NOT gate are universal: we only need these three gates to create all other logic gates. (In fact, there are many sets of universal quantum gates, for example the Deutsch gate is a single-gate universal quantum set.)

We’ve already seen the C-NOT gate so let’s look at the phase rotation gates. As mentioned in the previous article, a qubit is in a general state of a(0) + b(1), where a and b are complex numbers. We purposefully glossed over the details, simply stating that the probability of obtaining state 0 is a², but in fact rather than squaring the value, we are taking the modulus of the complex number a (obtained by multiplying the complex number with its conjugate). This ensures that the probability is always positive and real (imagine the horror of a probability of i² = -1).

Now, the complex numbers have a really interesting property: there are many numbers that have the same “modulus” or “absolute squared” value, unlike in the real numbers where we only have 2 (the positive and negative square roots). Imagine the complex plane with one axis (the y-axis) describing the imaginary part and one axis (the x-axis) describing the real part as shown below:

Drawing a circle centred at the origin with radius 1, we have drawn all points that have absolute squared value equal to 1 (i.e. probability 1). We can then categorise each point uniquely by the angle a line from the origin to our point makes with the real axis (the angle “phi” in the diagram). The value of a point on the line will therefore be equal to cos phi + i sin phi = e^{i phi}. So, all points on the circle will have the same probability (here equal to 1), and differ only by a phase e^{i phi}. As far as we are concerned, these phase differences have no physical meaning, because in the end all we can measure (i.e. have an effect on the real world) is the probability, which is unchanged when multiplied by a different phase.

The purpose of a phase rotation gate is as its name suggests: it keeps the state 0 the same, and adds a phase to state 1. This might not seem helpful here, but in a complex system where we need to keep track of the phase, for example in an optical system where the phase of light can decide whether effects like interference will occur, it is of great importance.

INPUT	OUTPUT
0	0
1	ei phi 1
…	…

The Hadamard gate is a little more difficult to explain, but in short it maps the state 0 to (0 + 1)/sqrt(2) and 1 to (0 – 1)/sqrt(2).  Imagine a sphere (which we call the Bloch sphere) with (0) and (1) on the poles (the z axis). Every combination of (0) and (1) is on the sphere surface. The two states (0 + 1)/sqrt(2) and (0 – 1)/sqrt(2) are “in the exact middle” of our (0) and (1) state: they lie on the poles of the x axis. Therefore, the Hadamard state can be thought of as mapping states on the z axis onto the x axis.

Why the Hadamard gate is important was already shown above: it can create superposition (a combination of 0’s and 1’s) from a pure state (a single 0 or 1). Qubits that have known values are no different from classical bits – only by applying a Hadamard gate can they be returned to a “powerful state” and benefit from the superposition. 

A truth table in the classical sense can no longer be made for these two gates, as both their input and output aren’t really binary values, but quantum states. Nevertheless, a rough “truth table” can still help to summarise the information:

INPUT	OUTPUT
0	(0 + 1)/sqrt(2)
1	(0 – 1)/sqrt(2)
…	…

Using these 3 gates (C-NOT, phase rotation and Hadamard), we can construct all quantum gates. We have established above that these gates are all reversible, so why aren’t our quantum computers a fully reversible machine? Well, it turns out there are a few fundamental gates needed for quantum computing which are irreversible: the setting gate (initialisation) that sets the initial bit value, and the readout gate (which gives the output). It is hopefully quite obvious why the former is irreversible: we don’t know what state to return our bit to. And the readout gate is not reversible for the same reason that if we open Schrödinger’s box and find the cat dead, closing the box won’t revive it. In fact this issue is just one of the many interesting things about quantum measurement, which we will be exploring in the next article (COMING SOON), along with some limits and applications of the quantum computer. See you there!