Quantum Computing

Unit Goals

Introduction

Three things to know up front:

1. A quantum computer can speed up some problems that take exponential time on a classical computer down to linear time.
2. A quantum computer works by manipulating quantum-behaving entities—like atoms, electrons, photons, and neutrinos—letting them behave the way they naturally behave. The problem is that these things are notoriously difficult to control so quantum computers are rather, um, expensive.
3. A quantum computer is not a replacement for a classical computer. Only certain problems can be sped up. You aren’t going to get a better movie-watching or document-editing experience with a quantum computer.

Qubits

Quantum computers work on qubits, which you can think of as having some probability of being 0 and some probability of being 1. (I’m not a fan of that “superposition” word.)

Here is a qubit that has a 64% chance of being 0 and a 36% chance of being 1:

$$ \begin{bmatrix} 0.8 \\ 0.6 \end{bmatrix} $$

Here is a famous qubit, which we call $|0\rangle$; it has a 100% of being 0 and a 0% chance of being 1:

$$ \begin{bmatrix} 1 \\ 0 \end{bmatrix} $$

And here is the famous qubit $|1\rangle$, which has a 0% chance of being 0 and a 100% chance of being 1:

$$ \begin{bmatrix} 0 \\ 1 \end{bmatrix} $$

You will often see the qubit $\left[\begin{smallmatrix}\alpha \\ \beta\end{smallmatrix}\right]$ written in the form $\alpha |0\rangle + \beta |1\rangle$. To see why:

$$ \alpha |0\rangle + \beta |1\rangle = \alpha\begin{bmatrix} 1 \\ 0 \end{bmatrix} + \beta\begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} \alpha \\ 0 \end{bmatrix} + \begin{bmatrix} 0 \\ \beta \end{bmatrix} = \begin{bmatrix} \alpha \\ \beta \end{bmatrix}$$

Technically, the 2-D column vector is not really the qubit itself, but rather the the state of the qubit.

The state space of all possible qubit states comprises all 2-D column vectors whose two elements, $\alpha$ and $\beta$, are complex numbers such that $|\alpha|^2 + |\beta|^2 = 1$.

(That is, the state of a qubit is a normalized vector.)

Measuring a Qubit

So here’s the thing. The qubit has this state $\left[\begin{smallmatrix}\alpha \\ \beta\end{smallmatrix}\right]$ but there is no way for you to ever know $\alpha$ and $\beta$! When you measure the qubit, you get back 0 or 1, and the qubit state becomes $|0\rangle$ or $|1\rangle$, and the values $\alpha$ and $\beta$ are lost forever.

Quantum Gates

Yes, Quantum Computers have gates like classical computers.

List of Quantum Gates at Wikipedia

The NOT Gate

The NOT gate, $X$, transforms $|0\rangle$ to $|1\rangle$ and vice versa. So $X|0\rangle = |1\rangle$ and $X|1\rangle = |0\rangle$. In general, $X$ is defined as:

$$ X (\alpha |0\rangle + \beta |1\rangle) = \beta |0\rangle + \alpha |1\rangle $$ or, equivalently, bc I like the matrix representations better: $$ X \begin{bmatrix}\alpha \\ \beta\end{bmatrix} = \begin{bmatrix}\beta \\ \alpha\end{bmatrix} $$

Makes sense, right? If a qubit was 70% chance of 0 and 30% of 1 then its inverse would be 30% chance of 0 and 70% chance of 1. Well, that’s how it is.

TODO - PICTURE

So you can think of a quantum gate as a box-thing that transforms a qubit into another, or as a function that transforms one vector into another. And did you know, that sometimes, a function from one vector to another can sometimes be represented as matrix multiplication? And qubits is one of those times! Check this out:

$$ X = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$$

It’s true:

$$ X \begin{bmatrix}\alpha \\ \beta\end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix}\alpha \\ \beta\end{bmatrix} = \begin{bmatrix}\beta \\ \alpha\end{bmatrix} $$

Hadamard Gate

Pauli Gates

Phase Shift Gates

Swap Gate

Controlled Gates

Quantum Circuits

Summary