Pen & paper quantum computing

The math is super easy don't be scared by the Greek letters

They say you need superconducting material, dilution refrigerators, and other advanced lab equipment. But in reality anything a quantum computer can do, you can do at home with only a pen and paper, with enough time on your hands—and ink and sheets.

Before showing how to compute—as in, finding output values from input values—we need to know what we’ll compute with:

• Values that we’ll transform will be qubits.

• Transformation will be done with quantum gates.

Qubits

One qubit

A quantum bit can be in two basis states: one denoted 0, the other denoted 1. In a superposition state it’s neither 0 nor 1; it’s characterized by two values we’ll call α (alpha) and β (beta), and we write the qubit ψ (psi) as

\(|\psi\rangle = \alpha |0\rangle + \beta |1\rangle \)

The funny brackets in ∣ψ​⟩ mean that we’re talking of a quantum state rather than normal numbers. It’s of course more complicated than that but that’s all you need to know at this point.

α and β are numbers that define how likely you are to observe 0 or 1 if you ask, or observe the qubit. Physicists do use the term “observe” and would tell you it amounts to a collapse of the qubit's wave function, a process that turns the qubit from its quantum, superposition state to a more classical state of either 0 or 1.

“So α and β are probabilities?” Kinda, not exactly. They’re called amplitudes. They’re not probabilities in the classical sense of a real number in [0, 1] such that 0.5 means you have a 1/2 chance. They are complex numbers. Not “complex” as in difficult, but numbers of the form a + bi, where a and b are real numbers and i is the imaginary unit. The real numbers (denoted ℝ) are what you obtain if you always set b = 0. The special number i is not a real number, as it’s defined by

\(i^2 = -1\)

To obtain a classical probability from an amplitude α = a + bi, you just compute

\(|\alpha|^2 = a^2 + b^2\)

Here |α| is called the modulus of α. There’s an exponent 2, so we say that we get the actual probability by taking the squared modulus of the amplitude.

For example, if

\(\alpha = 0 + \frac12 i = \frac{i}{2} \)

then the probability of observing 0 is:

\(|\alpha|^2 = \left|\frac{i}{2}\right|^2 = \left({\frac12}\right)^2 = \frac{1}{4}\)

Note that the value squared is 1/2, not i/2, because of the definition of the squared modulus above.

Oh and amplitudes can also be… negative real numbers, such as –0.85. But the squared modulus will turn a negative amplitude back to (positive) classical probabilities.

Two qubits

A pair of two qubits has four basis states: 00, 01, 10, and 11. We can write a two-qubit state as

\(|\psi\rangle = \alpha_{00}|00\rangle + \alpha_{01}|01\rangle + \alpha_{10}|10\rangle + \alpha_{11}|11\rangle\)

You may wonder why we use the “+” sign here. We’re not saying the bit strings are ordinary numbers being added; this is vector addition notation for quantum states. But we won’t really need it in this post. So we’ll use the simpler, standard notation of a vertical list (in math terms, a column vector):

\(|\psi\rangle = \begin{bmatrix} \alpha_{00} \\ \alpha_{01} \\ \alpha_{10} \\ \alpha_{11} \end{bmatrix}\)

Since there are four possible values, there are four amplitudes. And since they describe the probability of observing each of the four states, the sum of their squared moduli must be equal to 1:

\(|\alpha_{00}|^2 + |\alpha_{01}|^2 + |\alpha_{10}|^2 + |\alpha_{11}|^2 = 1 \)

More qubits

Now you get the idea. With three qubits there are be eight possible states 000, 001, 010, …, 110, 111. And more generally with n qubits there are 2ⁿ basis states. Therefore a state of n qubits can be written as

\(|\psi\rangle = \sum_{x \in \{0,1\}^n} \alpha_x |x\rangle\)

Where again all probabilities must sum to 1, because… they’re probabilities:

\(\sum_{x \in \{0,1\}^n} |\alpha_x|^2 = 1 \)

And that’s as far and as abstract as we’ll get about qubits. Now let’s move to the actual computation.

Quantum gates

Like classical logical gates such as AND and OR, which transform Boolean values true and false, quantum gates transform quantum states. Since a quantum state is fully defined by its amplitudes, quantum gates can be seen as a transformation of amplitudes.

Here’s what makes quantum computing SO EASY in principle:

If you see the list of amplitudes as a list of numbers (a vector), then a quantum gate is just a matrix multiplied by this vector. In the exact same way as in high school linear algebra classes.

We’ll see concrete examples for one and two qubits.

Single-qubit gates

In classical logic, the gate NOT transforms 0 to 1 and 1 to 0. In quantum logic, the Pauli-X gate is the quantum equivalent of NOT:

\(X = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\)

We apply the Pauli-X gate to the qubit

\(|\psi\rangle = \alpha |0\rangle + \beta |1\rangle = \begin{bmatrix} \alpha \\ \beta \end{bmatrix}\)

by multiplying the matrix X by its column vector:

\(X|\psi\rangle = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} \alpha \\ \beta \end{bmatrix} = \begin{bmatrix} \beta \\ \alpha \end{bmatrix}\)

we obtain this result because the underlying operations are

\(X(\alpha|0\rangle + \beta|1\rangle) = (0\alpha+1\beta) + (1\alpha + 0\beta) = \beta|0\rangle + \alpha|1\rangle\)

If you’re not familiar with matrix-vector multiplication, it works like this: you multiply one by one the elements of the matrix’s first row with the elements of the vector, and do the same for the second row. Once you see this, you’ll realize that the simplest, and least exciting gate is

\(I = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\)

because it doesn’t change the amplitudes vector. The matrix/gate I is called the identity gate.

And that’s it. Transforming qubits is just matrix–vector multiplication.

The Pauli-X gate is not the most interesting one, but it is one of the simplest. Like amplitudes, the matrix of a quantum gate consists of complex numbers. Thus it may include negative numbers, numbers involving the unit i, etc. For example, the Pauli-Y gate is

\( Y = \begin{bmatrix} 0 & -i \\ i & 0 \end{bmatrix} \)

This gate might look mysterious, but it turns out to have a simple interpretation if you see qubits from a geometrical perspective (for more, ask your favorite LLM about the Bloch sphere and how the Pauli-Y gate “rotates” qubits.)

Two-qubit gates

Remember that a 2-qubit state can be written

\( |\psi\rangle = \alpha_{00}|00\rangle + \alpha_{01}|01\rangle + \alpha_{10}|10\rangle + \alpha_{11}|11\rangle \)

or

\( |\psi\rangle = \begin{bmatrix} \alpha_{00} \\ \alpha_{01} \\ \alpha_{10} \\ \alpha_{11} \end{bmatrix} \)

Like for single qubits, a 2-qubit quantum gate will be a matrix–vector multiplication. But this time the matrix will have four rows and four columns instead of 2×2.

You can directly use a 4×4 matrix, but you may see a 2-qubit transformation as an operation on the first qubit and another operation on the second qubit. Let’s say we want to apply the identity I to the first qubit, and the Pauli-X gate X to the second qubit. You can combine the two one-qubit gates to obtain a two-qubit gate using the operator “⊗”, a kind of multiplication called the tensor product:

\( I \otimes X = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \otimes \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}\)

The tensor product is easier to understand by looking at what it does than by reading a definition involving rows and columns:

\( \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \otimes \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 1 \times \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} & 0 \times \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \\[1em] 0 \times \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} & 1 \times \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \end{bmatrix} = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} \)

If we apply I⊗X to our 2-qubit state we’ll obtain:

\((I \otimes X) \begin{bmatrix} \alpha_{00} \\ \alpha_{01} \\ \alpha_{10} \\ \alpha_{11} \end{bmatrix} = \begin{bmatrix} \alpha_{01} \\ \alpha_{00} \\ \alpha_{11} \\ \alpha_{10} \end{bmatrix}\)

I skip the details of the matrix multiplication because that’s a lot of zeros and ones and alphas and additions and multiplications, but you can check it yourself by hand as an exercise.

Another really cool gate is the controlled-not (CNOT), defined as follows:

\(\operatorname{CNOT} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}\)

In terms of classical logic, CNOT does what it claims: it flips the second qubit when the first bit is 1. But in the more quantum context of entangled qubits it turns out to be more powerful.

Matrix properties & reversibility

You can’t use any matrix as a quantum gate, because you must always end up in a state whose probabilities add up to one—otherwise you’d be in a very strange world. The matrices that preserve this total probability for every input are called unitary matrices, and they have another cool property: they are reversible! This means you can always recover the input from the output. And this is why quantum computing is a form of reversible computing (save for the final observation/measurement, see below.)

Finding the output

I realize I haven’t even told you how to obtain the output of a quantum computation. It’s not the list of amplitudes. An actual quantum computer wouldn’t know the amplitudes, it would observe some of the qubits, yielding values according to the probability distribution defined by the implicit amplitudes. (An observation of a real QC gives only one outcome, and the state collapses accordingly. To estimate the probabilities [though not amplitudes], you’d have run the same circuit many times and build statistics from the observed bit strings.)

How to simulate this with our classical pen-and-paper linear-algebraic “computer”? You’ll need randomness to sample the observed values according to the distribution defined by the amplitudes, which you know.

What’s the catch?

Admittedly, our examples aren’t very impressive, not very quantum-looking yet; we haven’t even talked of the really cool stuff, like the concepts of phase and basis, interference, and entanglement—I’ve expressed quantum gates in terms of the familiar concepts of logic operations, but QC is waaaaay more than that. So why do we bother investing billions in building actually quantum quantum computers when they can be simulated by hand?

It's because an actual quantum computer does much less work, literally exponentially less work. It won’t explicitly compute the 1024 = 2¹⁰ amplitudes of a 10-qubit state. It will just evolve 10 physical qubits whose amplitudes are part of the physical state rather than entries in a list

Now imagine you’re working with 170 qubits (not a crazy number by today’s experimental standards). To simulate such a system classically you’d need to keep a list 2¹⁷⁰ amplitudes, and do even more additions and multiplications to run the circuit. But 2¹⁷⁰ is a lot. It’s more than the number of atoms on Earth. At that point, no amount of pens and paper will save you.