14,734,420 members
Articles » General Programming » Algorithms & Recipes » General
Article
Posted 26 Jun 2019

7.6K views
8 bookmarked

# Quantum Computation Primer - Part 2

Rate me:
26 Jun 2019CPOL
Learn the fundamentals of quantum computation. In this part we look at using gates to create quantum states.


## 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.

### 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, UU = 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.

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.

### 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.

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.

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.

The circuit diagram symbol for the Hadamard gate is shown in Figure 6.

### 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)

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.

### 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.

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.

## 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.

• 25 June 2019
• Published

## Share

 President Outcoder Switzerland
Daniel Vaughan is a nine-time Microsoft MVP and co-founder of Outcoder, a Swiss software and consulting company dedicated to creating best-of-breed user experiences and leading-edge back-end solutions, using the Microsoft stack of technologies--in particular Xamarin, WPF, and the UWP.

Daniel is the author of Windows Phone 8 Unleashed and Windows Phone 7.5 Unleashed, both published by SAMS.

Daniel is the developer behind several acclaimed mobile apps including Surfy Browser for Android and Windows Phone. Daniel is the creator of a number of popular open-source projects, most notably Codon.

Blog | MVP profile | Twitter

Xamarin Experts
Windows 10 Experts

 First Prev Next
 My vote of 5 heuerm21-Nov-20 4:32 heuerm 21-Nov-20 4:32
 Missing figures in Part 2 Member 796319128-Jun-19 1:36 Member 7963191 28-Jun-19 1:36
 Re: Missing figures in Part 2 Daniel Vaughan28-Jun-19 6:03 Daniel Vaughan 28-Jun-19 6:03
 Re: Missing figures in Part 2 Daniel Vaughan28-Jun-19 6:14 Daniel Vaughan 28-Jun-19 6:14
 My vote of 5 Jan Heckman27-Jun-19 1:07 Jan Heckman 27-Jun-19 1:07
 Re: My vote of 5 Daniel Vaughan27-Jun-19 4:20 Daniel Vaughan 27-Jun-19 4:20
 Last Visit: 31-Dec-99 19:00     Last Update: 17-Jan-21 23:05 Refresh 1