Quantum Computing: From First Principles to Interpretability

This is a notebook, not a finished essay. I’m learning quantum computing from first principles and writing up each part as I go. My two main texts are Thomas Wong’s Introduction to Classical and Quantum Computing and Nielsen and Chuang’s Quantum Computation and Quantum Information.

1. Why?

Why start with classical computing?

People sometimes say we’re in the vacuum tube era of quantum computing. Classical computers went through the same stage:

Computers in the 1940s were room-sized machines built from thousands of parts that could fail. Today we rarely think about the billions of transistors in a laptop. Quantum computers are still at the early stage: researchers are working out how to build large, reliable computations from noisy physical qubits. Classical computing already answered many of the same engineering questions, so it’s the natural place to start.

2. Mathematical foundations

Bits and states

A coin has two states, heads or tails. Two coins have four (HH, HT, TH, TT), and $n$ coins have $2^n$. Any two-state system (a coin, a switch, a transistor) can be labelled 0 and 1, a bit: the smallest unit of classical information. Everything else, numbers in binary and text in ASCII or Unicode, is built from strings of bits.

The key fact: $n$ bits can be in any one of $2^n$ states, but only one at a time.

Logic gates and universality

Gates transform bits, and a truth table fully describes a gate:

There are 16 possible two-bit gates and 256 three-bit gates, but we don’t need them all. A universal gate set can build any truth table. {NOT, AND, OR} is universal, and so is NAND alone: tie its inputs together to get NOT ($\overline{AA} = \overline{A}$), and NOT a NAND to get AND. Gates combine into circuits. Built from AND, OR and XOR gates, a full adder takes 5 gates, so a ripple-carry adder for two $n$-bit numbers takes $5n$; more generally, addition needs $O(n)$ elementary operations. Boolean algebra (such as De Morgan’s law $\overline{AB} = \overline{A} + \overline{B}$) shrinks circuits further.

Whiteboard notes: adders and Boolean algebra

Reversible gates

A gate is reversible if its output always tells you its input. That needs as many outputs as inputs, and no output repeated. NOT is reversible. AND isn’t: an output of 0 could have come from 00, 01 or 10, so information is lost.

The Toffoli gate fixes this. It keeps its inputs and XORs the AND into a third bit: $(A, B, C) \mapsto (A, B, AB \oplus C)$. With $C = 0$ it computes AND, with $C = 1$ it computes NAND, so (with extra ancilla bits) it’s universal for classical reversible computation. It flips $C$ only when $A = B = 1$, hence its other name, controlled-controlled-NOT. The same trick makes any function reversible: $(A, B, C) \mapsto (A, B, f(A,B) \oplus C)$.

Whiteboard notes: reversible gates and the Toffoli gate

Error correction

Bits flip by accident. In a 2003 Belgian election, one candidate gained exactly $4096 = 2^{12}$ votes, suspected to be a cosmic-ray particle flipping a single bit. The fix is redundancy: encode one logical bit in several physical bits.

With the three-bit repetition code, $0 \mapsto 000$ and $1 \mapsto 111$, and a single flip is corrected by majority vote. Better still, two parity checks ($b_1 \oplus b_2$, $b_2 \oplus b_3$) pinpoint which bit flipped without revealing the encoded value. The code fails only if two or three bits flip, with probability $3p^2(1-p) + p^3$, which beats an unprotected bit whenever $p < \tfrac12$.

Whiteboard notes: repetition codes and parity checks

Complexity: what’s possible, and what’s efficient

Algorithms are compared by how their cost grows with input size $n$, using Big-O notation: $O(n)$ and $O(n^2)$ are polynomial and usually tractable, while $O(2^n)$ is exponential and quickly isn’t.

Some problems can’t be solved at all. Turing proved the halting problem (will this program ever stop?) is undecidable: any supposed solver $H$ can be fed a program built to do the opposite of whatever $H$ predicts about it.

Solvable problems are grouped into complexity classes. A class describes the resources needed to solve a whole family of problems as the input grows, not a category of individual algorithms:

• P: solvable in polynomial time.
• NP: answers can be checked in polynomial time. Whether P = NP is a million-dollar open problem.
• BPP: solvable in polynomial time with randomness and a small error probability.
• BQP: solvable in polynomial time by a quantum computer.

None of these inclusions is known to be strict, and there’s no known efficient quantum algorithm for NP-complete problems.

The thread, in one table

3. From classical bits to quantum bits

Superposition, informally

Meet Schrödinger’s cat, a thought experiment by Erwin Schrödinger. Put a healthy, sleepy cat in a box with a radioactive atom that may or may not decay by the end of the experiment. The atom can’t hurt the cat, but if it decays it triggers a Geiger counter wired to an alarm clock that rudely wakes the cat.

The thought experiment asks what happens when a microscopic quantum event is linked to a macroscopic outcome. It’s often summarised as “the cat is both asleep and awake until someone looks”, which is memorable but misleading. Schrödinger meant it to show the tension between quantum mechanics and our everyday intuition about large objects, not to describe what quantum theory literally says about cats.

It helps to separate three ideas that are easy to blur together:

• Classical uncertainty: the system is in one definite state; you just don’t know which. A coin under a cup is like this.
• Quantum superposition: the state is a combination of basis states with amplitudes, and those amplitudes can interfere. That’s not a statement about our ignorance, and an isolated system can stay in superposition while it evolves.
• Decoherence: interactions with the environment make interference between the alternatives effectively impossible to observe.

Measurement produces an outcome with probabilities set by the quantum state and by which measurement is performed. Measuring can disturb the state, but it doesn’t wipe out every superposition: what happens depends on what you measure. How definite outcomes arise from quantum evolution is still a foundational question, and it’s part of why Schrödinger and Einstein found the theory so uncomfortable.

The double-slit experiment makes interference concrete. Fire electrons one at a time at a barrier with two narrow slits. Each electron arrives at the screen as a single dot. But after many electrons, the dots build up an interference pattern: the amplitudes for the two paths combine, adding in some places and cancelling in others. If the setup makes which-path information available, through any measurement or interaction that records the slit, not a person watching, the pattern disappears and you get two bands. When the paths stay coherent and indistinguishable, they interfere.

This is also the first glimpse of a theme that runs through the rest of the notebook: a single measurement gives one outcome, and the quantum state shows up in the statistics of many repeated measurements.

Why does superposition help computation?

This was the big question I had after reading about superposition. Imagine searching for one specific cat among 1,000.

A classical computer checks cats one by one, and in the worst case checks all 1,000.

A quantum computer can prepare a superposition that includes all 1,000 candidates at once. But it can’t just look at all of them and report the right one. Measuring immediately gives one random candidate, which is probably wrong.

The secret is interference. Each candidate carries an amplitude, a number related to its probability of being measured. Unlike probabilities, amplitudes can be negative (or complex), so they can cancel out, like waves.

1. Prepare a superposition where every candidate has the same amplitude, so all are equally likely.
2. Interfere. Apply carefully designed operations that mark the target (in Grover’s algorithm, by flipping the sign of its amplitude) and then make amplitudes interfere so the target’s grows and the others shrink. Repeat.
3. Measure. The target is now very likely to come out.

It’s a bit like tuning a radio: you’re not listening to every station separately, you’re shaping the signal so the one you want comes through clearly. It’s not a perfect analogy, but it gives the intuition.

Qubits

A qubit is like a classical bit in one way: it has two basis states, 0 and 1. In Dirac or bra-ket notation, we write them as kets:

We can picture them as the north and south poles of a sphere of radius 1, the Bloch sphere. Following the physics convention, the $x$-axis points out of the page, the $y$-axis points to the side and the $z$-axis points up. Then $|0\rangle$ sits at $(x, y, z) = (0, 0, 1)$ and $|1\rangle$ at $(0, 0, -1)$.

A classical bit can only be at one pole or the other. A qubit can be in a superposition of $|0\rangle$ and $|1\rangle$, for example equal parts of each:

Both coefficients are $1/\sqrt{2}$, so this state is halfway between the poles, on the equator. It sits where the Bloch sphere meets the $+x$-axis, at $(1, 0, 0)$.

Every point on the equator is equal parts $|0\rangle$ and $|1\rangle$. What distinguishes them is the relative phase between the two terms. A phase of $-1$ moves the state to the $-x$-axis, and the complex phases $i = \sqrt{-1}$ and $-i$ move it to the $\pm y$-axis. This is the first place complex numbers show up in quantum computing.

In Qiskit, each state is a one-qubit circuit (which starts in $|0\rangle$) followed by a couple of gates. For example, $|i\rangle$:

from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector
from qiskit.visualization import plot_bloch_multivector

qc = QuantumCircuit(1)  # one qubit, initialised to |0>
qc.h(0)                 # Hadamard: |0> -> |+>, onto the equator
qc.s(0)                 # S: phase of +i on |1>, rotates |+> to |i>
state = Statevector.from_instruction(qc)

plot_bloch_multivector(state)

Swapping s for z gives $|-\rangle$, sdg gives $|-i\rangle$, and an x gate on its own gives $|1\rangle$:

The full notebook from the cohort session, with exercises on gate identities like $X^2 = I$, $S^2 = Z$ and $HXH = Z$, is on Colab.

These four are just the points where the axes cross the equator. Other complex phases reach every other point on the equator, and superpositions aren’t limited to the equator either. A qubit can be at any point on the Bloch sphere. That continuous space of states, together with interference, is what the rest of this notebook builds on.

Coming next

Planned

The title promises a path to interpretability, and this first entry only gets as far as a single qubit. Here’s the plan for the next entries:

Main texts: Thomas G. Wong, Introduction to Classical and Quantum Computing, Rooted Grove, 2022 (free PDF from the author); Michael A. Nielsen and Isaac L. Chuang, Quantum Computation and Quantum Information, 10th anniversary edition, Cambridge University Press, 2010. Cohort notebook: Chapter 2, part 1 on Colab.