$ \newcommand{\bra}[1]{\left< #1 \right|} \newcommand{\ket}[1]{\left| #1 \right>} \newcommand{\bk}[2]{\left< #1 \middle| #2 \right>} \newcommand{\bke}[3]{\left< #1 \middle| #2 \middle| #3 \right>} \newcommand{\mzero}[0]{\begin{bmatrix} 1 \\ 0 \end{bmatrix}} \newcommand{\mone}[0]{\begin{bmatrix} 0 \\ 1 \end{bmatrix}} \newcommand{\ostwo}[0]{\frac{1}{\sqrt{2}}} \newcommand{\mhadamard}[0]{\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}} $
Table of Contents
Introduction
In the previous article, we explored the theory underpinning quantum computation. In this article we delve further and look at quantum gates. These are the nuts and bolts that allow you to build quantum circuits. We explore many of the gates commonly used in quantum computation, and we look at using some of these gates to create various quantum states.
If you haven't already, I recommend reading Part 1 in this series before continuing.
Building Quantum Circuits
In quantum computing, an algorithm is implemented as a quantum circuit that consists of input and output qubits, and gates that alter the quantum states of the qubits. See Figure 1.
There are one-qubit gates and multi-qubit gates. When a measurement is performed on a qubit, its state collapses to one of its basis states: |0⟩ or |1⟩. It can then be thought of as a classical bit. This is signified by the double lines emerging from the Measurement symbol.
Figure 1. Example quantum circuit (quantum entanglement circuit)
Representing Gates as Unitary Matrices
Quantum gates are represented by unitary matrices. A matrix is unitary if its conjugate transpose is also its inverse. That is, U†U = I. In other words, if you multiply a unitary matrix by its conjugate transpose, you end up with the identity matrix. For a revision on conjugate transpose, please refer back to Part 1.
The identity matrix is a diagonal matrix comprised of all zeros apart from a diagonal of 1's, as shown:
$ I_3 = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} $
The subscript next to the '\(I\)' denotes the dimension size.
If you multiply a matrix by an identity matrix, it's a no-op. It's the same as multiplying by 1.
When you multiply a matrix by its inverse, you get the identity matrix.
An important feature of unitary matrices is that when you multiply a matrix by a unitary matrix, the norm is preserved. This means that when a unitary matrix is applied to a quantum state, the sum of the probabilities remains equal to 1, and the state stays on the surface of the Block sphere. The norm is the length of the vector from the center of the sphere.
The dimensions of the matrix representing a gate is equal to 2n × 2n, where n is the number of inputs. For quantum gates, the number of inputs always equals the number of outputs.
The Importance of Gate Reversibility
Unlike gates in classical computing, quantum gates have to be reversible. As Gidney (2016) states, quantum gates must be reversible because quantum mechanics is reversible. While classical computers are able to discard accumulated information during processing, doing so in a quantum computer would count as a measurement; collapsing the quantum state.
To maintain the consistency of a superposition, the sum of all probabilities across all states must equal 1. No information can be lost when applying a gate.
Now, because the matrices representing gates are unitary, they are reversible. If you apply a gate U to a state |ψ⟩, you can undo it by applying U's conjugate transform, which is its inverse, as shown:
$ U^\dagger U \ket{\psi} = \ket{\psi} $
As we learned in the previous section, if you multiply a unitary matrix by its conjugate transform, the result is the identity matrix; effectively leaving the state unchanged.
When we compare quantum gates to classical gates, we see that gates like the classical AND and OR gates aren't as easy to implement in quantum computing. These classical gates are irreversible. They each have two inputs and only one output, which means you can't reconstruct the initial input bits from the output. Information is lost. See Figure 2.
Figure 2. Classical AND & OR gates
To implement quantum AND and OR gates, we need to make them reversible. We can do that using a controlled swap gate. We see how to do that later in the article.
Conversely, classical gates that are already reversible, such as the NOT gate, can be implemented more easily as quantum gates. See Figure 3. It's easy to see that the input to a NOT gate can be inferred from it's output. If the output is 1, the input was 0; if the output is 0, the input was 1.
Figure 3. Classical Not gate
Measuring Qubits
We've learned that a measurement collapses a qubit's state to one of its basis states: |0⟩ or |1⟩, and that quantum gates must be reversible. Since taking a measurement is an irreversible activity, measurements are not technically gates. Though, they are sometimes called Measurement gates.
Measurements are represented by a symbol that features a gauge. See Figure 3. The output of a measurement is a double line indicating a classical bit.
Figure 3. The Measurement circuit symbol
Let's now return to the classical NOT gate and see how it is implemented as a quantum gate.
Negating a Qubit with the Pauli-X Gate
The quantum counterpart of the classical NOT gate is the Pauli-X gate (a.k.a. NOT gate or X gate), whose matrix representation looks like this:
$ X = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} $
Just like a classical NOT gate negates 0 to 1, and 1 to 0, the Pauli-X gate flips the basis states as shown:
$ \begin{align} X \ket{0} &= \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \mzero = \mone = \ket{1} \\ X \ket{1} &= \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \mone = \mzero = \ket{0} \end{align} $
The Pauli-X gate rotates a qubit on the Bloch sphere around the x-axis by π radians (180°).
The Pauli-X gate quantum circuit symbol is shown in Figure 4.
Figure 4. Circuit Symbol for Pauli-X gate
There are two other Pauli gates: the Pauli-Y gate and the Pauli-Z gate. Each performs an antipodal rotation on the Bloch sphere—around the axis specified in the name. We explore them later.
Using the Hadamard Gate to a Create 50/50 Superposition
When starting with a basis state |0⟩ or |1⟩, its common to transform it into an equal probability superposition. That is, to one of the following two states:
$ \begin{align} \ket{+} &= \frac{\ket{0} \color{red}{+} \ket{1}}{\sqrt{2}} \end{align} $
$ \begin{align} \ket{-} &= \frac{\ket{0} \color{red}{-} \ket{1}}{\sqrt{2}} \end{align} $
Notice that the plus and minus symbols correspond to the sign of the amplitude of the |1⟩ state.
|+⟩ and |-⟩ are a common starting point for more complex state manipulations. |+⟩ and |-⟩ give equal probability that the qubit's superposition will collapse to either |0⟩ or |1⟩.
Recall that to calculate the probability of a basis state, we take its coefficient, in this case \(\frac{1}{\sqrt{2}}\), and square its conjugate. Since the number is Real (its imaginary part is 0) we don't need to worry about taking the conjugate. So the probability P(0) is calculated as follows:
$ P(0) = \left \vert \frac{1}{\sqrt{2}} \right \vert^2 = \frac{1}{2} $
and because the sum of the probabilities must equal 1, we can subtract P(0) from 1 to find P(1):
$ P(1) = 1 - P(0) = \frac{1}{2} $
But how do we transform |0⟩ or |1⟩ into |+⟩ or |-⟩? For that we turn to the Hadamard gate (a.k.a., H gate).
The Hadamard gate shows up everywhere in quantum computing because it allows you to transform a qubit's |0⟩ or |1⟩ state into a superposition with equally split probability amplitudes.
The Hadamard gate turns |0⟩ into |+⟩ and |1⟩ into |-⟩, which is just what we need.
The matrix representation of the Hadamard gate is:
$ \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} $
If we apply the Hadamard gate to |0⟩, the result is |+⟩, as shown:
$ H \ket{0} = \ostwo \mhadamard \mzero = \ostwo \begin{bmatrix} 1 \\ 1 \end{bmatrix} = \ostwo \left( \mzero + \mone \right) = \frac{\ket{0} + \ket{1}}{\sqrt{2}} $
Notice how we factor [1, 1]T into [1, 0]T + [0, 1]T. That gives our |0⟩ and |1⟩ basis states.
On the Bloch sphere, |+⟩ and |-⟩ are located on the equator. See figure 5. They reside halfway between the |0⟩ and |1⟩ basis states; having a probability of \(\left \lvert \frac{1}{\sqrt{2}} \right \rvert^2 = \frac{1}{2}\), or 50%.
The Hadamard gate rotates the qubit around the x-axis by π radians (180°) followed by a clockwise rotation around the y-axis by \(\frac{\pi}{2}\) radians (90°). Another way of thinking about it is as a π radians (180°) rotation around the x+z diagonal.
Figure 5. Applying the H operator to |0⟩ on the Bloch sphere
The circuit diagram symbol for the Hadamard gate is shown in Figure 6.
Figure 6. Circuit Symbol for Hadamard gate
Generating Superpositions of all Basis States
We can increase the number of observable states by applying the Hadamard gate to other qubits. Each observable state is composed of a unique set of bits. The set of all these observable states form the basis states. For example \(\ket{00}\) can be split into \(\frac{\ket{00} + \ket{01} + \ket{10} + \ket{11}}{2}\).
Starting with a state of n qubits |0...0n⟩, if we apply the Hadamard gate to each qubit it results in the following state:
$ \ket{\psi} = \frac{\ket{0 \ldots 000} + \ket{0 \ldots 001} + \ldots + \ket{1 \ldots 111}}{\sqrt{2^n}} $
We end up with 2n observable states.
Defining an Operator
A gate can be thought of as function. In quantum mechanics, any function that maps linearly from one value to another value in complex space is called an operator. That's why you sometimes find gates described as operators.
You can tell if a mathematical function is a linear map because it is said to preserve addition and multiplication. That means if you call the function with a argument equal to u + v, then the result would be the same as calling the function twice; once for u and once for v, and summing the result. See the following:
$ f(u + v) = f(u) + f(v) $
Also, if you call the function with an argument of c × u, then the result must equal the same as when calling the function with an argument of u and multiplying the result by c, as shown:
$ f(c \times u) = c \times f(u) $
Stated another way, if the function is a linear map, it doesn't matter whether the function is called before or after the operations of addition and multiplication (Wikipedia).
Using a Controlled Not Gate
Despite its name, the Controlled-Not gate (CNOT) is analogous to the XOR gate (Exclusive OR) in classical computing. In classical computing the XOR operation takes two inputs. If both of the inputs are 1, then the output is 0; otherwise the result is unaffected.
The truth table for a classical XOR gate is as follows:
$ \begin{array}{ccc} A & B & A \oplus B \\ \hline 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{array} $
The quantum CNOT gate has two inputs, and thus two outputs. The target input is negated only if the control input is set to 1. If the control input is 0, the gate has no effect. The control qubit is not changed by the gate.
The CNOT gate's circuit symbol is depicted in Figure 7. (minus the text)
Figure 7. Circuit Symbol for the CNOT gate
TIP: The way I remember which input is which on the CNOT is that the target input looks like a reticle.
The CNOT gate is another name for the Controlled Pauli-X gate. We cover the Pauli gates in Part 3 of the series.
The truth table for the CNOT gate is given below. I've omitted the Dirac notation for states. 0 corresponds to |0⟩ and 1 to |1⟩.
$ \begin{array}{cc|cc} \rlap{In} & & \rlap{Out} & \\ \hline Control & Target & Control & Target \\ \hline 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 \end{array} $
Observe how the Target output column matches the A ⊕ B column of the classical XOR gate.
Since the CNOT gate has two inputs and two outputs, it is represented by a 4 × 4 matrix (2inputCount × 2outputCount), shown below:
$ CNOT = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} $
Let's look at an example of applying a CNOT gate to a |00⟩ state. The first qubit serves as the control; the second, the target.
Recall that the matrix for |00⟩ is [1, 0]T ⊗ [1, 0]T = [1, 0, 0, 0]T.
$ CNOT \ket{00} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} = \ket{00} $
Here the first qubit is 0, which means the second, target, qubit is unchanged.
Look at what happens when we apply a CNOT to a |10⟩ state.
$ CNOT \ket{10} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix} = \ket{11} $
The second qubit is flipped, just as expected.
Converting a Truth Table to a Matrix
As Yanofsky and Mannucci (2008, p. 172) describe, there's a useful technique for converting a truth table to its matrix representation. See figure 8.
You start with enough space to contain your 2inputCount × 2inputCount matrix. Starting at row 0 column 0, you label the columns and rows consecutively in binary, from 00 to 11 for example. You then place a 1 in a cell if the input maps to the output; 0 otherwise. Voilà, you're left with a matrix for your gate.
Figure 8. Converting a truth table to a matrix
Creating Bell States
When we looked at entanglement in Part 1 of this series, we touched upon the Bell state \(\ket{\Phi^+}\). There are three other Bell states, all of which are shown below:
$ \ket{\Phi^\color{red}{+}} = \frac{\ket{00} \color{red}{+} \ket{11}}{\sqrt{2}} $
$ \ket{\Phi^\color{red}{-}} = \frac{\ket{00} \color{red}{-} \ket{11}}{\sqrt{2}} $
$ \ket{\Psi^\color{red}{+}} = \frac{\ket{01} \color{red}{+} \ket{10}}{\sqrt{2}} $
$ \ket{\Psi^\color{red}{-}} = \frac{\ket{01} \color{red}{-} \ket{10}}{\sqrt{2}} $
Each state is a permutation of the + or - operation and the basis states |00⟩ & |11⟩ and |01⟩ & |10⟩
The Bell states are maximally entangled two qubit states. Maximally entangled means that they're entangled and there is a uniform probability distribution. In other words, there is an equal probability across the observable states. For the Bell states the probability is \(\left \vert \ostwo \right \vert^2 = \frac{1}{2}.\)
You use two gates in combination to create a Bell state: a Hadamard gate and a CNOT gate. The circuit diagram for this gate combination is shown in Figure 9.
The output of the Hadamard gate becomes the control input for the CNOT gate.
Figure 9. Applying H Gate and then a CNOT
Let's see how this works algebraically, starting with with a |00⟩ state.
Recall that applying an Hadamard gate to the |0⟩ state places it into the |+⟩ state:
$ H \ket{0} = \frac{\ket{0} + \ket{1}}{\sqrt{2}} $
To begin, we pass the first qubit of the |00⟩ state through a Hadamard gate. The second qubit is unaffected:
$ H \ket{00} = \frac{\ket{0} + \ket{1}}{\sqrt{2}} \otimes \ket{0} $
The two qubits are still separable. We need to apply a CNOT to create entanglement. But before we do, let's use matrices to derive the same result.
$ \begin{align} H \ket{00} &= \left(\ostwo \mhadamard \mzero \right) \otimes \mzero \\[10pt] & = \ostwo \begin{bmatrix} 1 \\ 1 \end{bmatrix} \otimes \mzero = \ostwo \begin{bmatrix} 1 \\ 0 \\ 1 \\ 0 \end{bmatrix} \end{align} $
We see that H|00⟩ can be represented as \(\ostwo \begin{bmatrix} 1, & 0, & 1, & 0, \end{bmatrix}^T\). We can use this matrix result to give us an understanding of what is happening when we apply the CNOT gate:
$ \begin{align} CNOT(H \ket{00}) &= \ostwo \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 1 \\ 0 \end{bmatrix} = \ostwo \begin{bmatrix} 1 \\ 0 \\ 0 \\ 1 \end{bmatrix} \\[10pt] &= \frac{\mzero \otimes \mzero + \mone \otimes \mone}{\sqrt{2}} \\[10pt] &= \frac{\ket{00} + \ket{11}}{\sqrt{2}} \end{align} $
You can see that the multiplier (\(\ostwo\)) is commutative. Moving it to the start of the equation does not change the result.
When applying the CNOT gate, the first qubit becomes the control and the second qubit, the target. When the first bit is 1, the second bit is flipped, giving us the desired state.
To generate the other Bell states, we just start with a different basis state, as listed below:
$ \ket{\Phi^+} = CNOT(H \ket{00}) \\ \ket{\Phi^-} = CNOT(H \ket{10}) \\ \ket{\Psi^+} = CNOT(H \ket{01}) \\ \ket{\Psi^-} = CNOT(H \ket{11}) $
Generating a GHZ State
The Greenberger–Horne–Zeilinger state (GHZ state) is a three or more qubit entangled state.
The GHZ state resembles the \(\ket{\Phi^+}\) state, but while \(\ket{\Phi^+}\) has only two qubits in the same configuration, the GHZ state has three or more. The simplest form of the GHZ state is:
$ \ket{GHZ} = \frac{\ket{000} + \ket{111}}{\sqrt{2}} $
To create a GHZ state, you apply an Hadamard gate to the first qubit, and then a CNOT to every other qubit; using the first qubit as the control.
There are numerous other notable quantum states that you can create using combinations of gates. Figuring out how to create them can be challenging and fun.
TIP: Quirk is a terrific browser-based tool for experimenting with quantum circuits. See Figure 10. It has a drag and drop interface, built-in support for many common gates, and the ability to easily share circuits by URL. Quirk was created by Craig Gidney.
Figure 10. Quirk allows you to visually design and run quantum circuits in your browser.
Conclusion
In this article we looked at some of the most commonly employed quantum gates. We learned that gates are represented as unitary matrices, and of the importance of gate reversibility. We saw how a Measurement is not technically a gate because it isn't reversible. We looked at putting a qubit into superposition with the Hadamard gate, and at entangling qubits with the CNOT gate. Finally, we saw how to create Bell states and the GHZ state using these gates.
In the next part, we continue our exploration of quantum gates. We see how to rotate and swap qubits, and we delve into more advanced controlled gates, which enable you to apply a control qubit to just about any gate. I hope you'll join me.
Thanks for reading and I hope you found this article useful. If so, then I'd appreciate it if you would please rate it and/or leave feedback below.
References
- Yanofsky, Noson S., & Mannucci Mirco A. (2008). Quantum Computing for Computer Scientists
- Anton, H., (2000) Elementary Linear Algebra, 8th Edition, Wiley
- Nielsen, M. & Chuang, I., (2010) Quantum Computation and Quantum Information, 10th edition, Cambridge University Press, Cambridge UK
- Glendinning, Ian. (2005) The Bloch Sphere, accessed on 10 June 2019, retrieved from http://www.vcpc.univie.ac.at/~ian/hotlist/qc/talks/bloch-sphere.pdf
- Dutta, S., If quantum gates are reversible how can they possibly perform irreversible classical AND and OR operations? accessed on 9 June 2019, retrieved from https://quantumcomputing.stackexchange.com/questions/131/if-quantum-gates-are-reversible-how-can-they-possibly-perform-irreversible-class
- Wolf, R., Quantum Computing: Lecture Notes, accessed on 9 June 2019, retrieved from https://homepages.cwi.nl/~rdewolf/qcnotes.pdf
- Wikipedia, Quantum logic gate, accessed on 9 June 2019, retrieved from https://en.wikipedia.org/wiki/Quantum_logic_gate
- Wikipedia, Linear map, accessed on 9 June 2019, retrieved from https://en.wikipedia.org/wiki/Linear_map
- Glendinning, I., (2010) Rotations on the Bloch Sphere, accessed on 9 June 2019, retrieved from http://www.vcpc.univie.ac.at/~ian/hotlist/qc/talks/bloch-sphere-rotations.pdf
- Ramanan, A., Quantum Gates and Circuits: The Crash Course, accessed on 26 June 2019, retrieved from https://blogs.msdn.microsoft.com/uk_faculty_connection/2018/02/26/quantum-gates-and-circuits-the-crash-course/
- Gidney, C., Why do quantum gates have to be reversible?, accessed on 26 June 2019, retrieved from https://physics.stackexchange.com/questions/270266/why-do-quantum-gates-have-to-be-reversible
History
