Quantum Computing

Quantum computing is one of those fields where the hype-to-understanding ratio is catastrophically high. Most people have heard that quantum computers are "exponentially faster" and will "break all encryption." Both claims are wrong in ways that matter. The real story is subtler and, I think, more interesting: quantum computers exploit the structure of quantum mechanics — superposition, entanglement, interference — to solve a specific class of problems that classical computers find intractable. Not all problems. Not most problems. But the ones they can solve include factoring large numbers, which happens to be what modern cryptography depends on.

What a Quantum Computer Actually Does

Michael Nielsen, in his video lecture series Quantum Computing for the Determined, takes a refreshingly concrete approach: treat qubits as abstract mathematical objects (vectors in a two-dimensional complex vector space), don't worry about physical implementations, and just learn to manipulate them.¹ A qubit isn't a bit that's "both 0 and 1 at the same time" — that's a metaphor that misleads more than it helps. A qubit is a vector that can be in any superposition of |0⟩ and |1⟩, where the coefficients are complex numbers whose squared magnitudes give measurement probabilities.

The building blocks are gates: the Hadamard gate puts a qubit into equal superposition, the controlled-NOT gate entangles two qubits, and together with arbitrary single-qubit rotations, these form a universal gate set — any quantum computation can be built from them. The insight Nielsen emphasises is that you don't need to understand quantum mechanics to understand quantum computing. It's linear algebra all the way down.

But raw superposition doesn't give you speedup. If you just prepare a superposition of all possible inputs, compute a function on them, and measure, you get a single random output — you've done one computation, not many. The art of quantum algorithm design is arranging interference so that wrong answers cancel out and right answers reinforce. This is enormously difficult in general, which is why there are only a handful of known quantum algorithms that offer genuine speedups.

Shor's Algorithm: Why Factoring Falls

The most famous of those algorithms is Peter Shor's 1994 factoring algorithm, and the reason it works is surprisingly number-theoretic. The core insight: factoring a number n can be reduced to finding the period of the function f(a) = x^a mod n, where x is coprime to n.²

Here's the chain of reasoning. If you can find the period r of that function, then x^r ≡ 1 (mod n), which means (x^(r/2))² - 1 ≡ 0 (mod n). Factor that as (x^(r/2) - 1)(x^(r/2) + 1), and provided r is even and x^(r/2) ≢ -1 (mod n), at least one of those factors shares a nontrivial common divisor with n. You've factored n, and the whole thing reduces to period-finding.²

Classically, finding the period of f(a) = x^a mod n requires evaluating the function for exponentially many values of a. Shor's algorithm does it in polynomial time by exploiting quantum parallelism and the quantum Fourier transform. You prepare a superposition of all possible inputs, compute f in superposition, measure the output register (which collapses the input register to a superposition of values spaced exactly r apart), then apply a quantum Fourier transform that peaks the probability amplitudes at multiples of 1/r. A classical post-processing step extracts r from the measurement.²

What strikes me about Shor's algorithm is how specific the speedup is. It's not that the quantum computer tries all factorizations simultaneously. It's that the mathematical structure of the problem — the periodicity of modular exponentiation — happens to be exactly the kind of structure that quantum Fourier transforms can detect. Change the problem even slightly and the algorithm doesn't apply.

Entanglement Makes Verification Impossibly Hard

The relationship between quantum mechanics and computational complexity runs deeper than individual algorithms. The Spacetime And Information article discusses the MIP* = RE result, which showed that entangled quantum provers can verify problems as hard as the halting problem. But there's a prior result that's worth examining: the work of Vidick and Ito showing that multi-prover interactive proofs remain sound even when provers share quantum entanglement.³

In a classical multi-prover proof, a verifier interrogates several provers who can't communicate. The provers' inability to coordinate means cheating is hard — contradictions emerge quickly. But if provers share entangled particles, they can correlate their answers without communicating. Measurements on entangled particles produce correlated results, and the provers can use this to coordinate strategies that should be impossible.

Vidick and Ito proved that certain proof systems survive this attack. The key idea is geometric: by encoding questions in a high-dimensional space and requiring answers that are consistent along lines through that space, the verifier can catch cheating even when provers use entanglement to correlate responses. The provers can match their answers along any one dimension using entangled measurements, but they can't simultaneously match along all dimensions — the geometry prevents it.³

The result matters for cryptography (interactive proofs underlie many cryptographic protocols), but its deeper significance is for physics. As Dorit Aharonov noted, the paper is the quantum analogue of earlier work that led to the PCP theorem, "no doubt the most important result of complexity in the past 20 years."³ And the road from PCP to MIP* = RE ultimately disproved the Connes embedding conjecture — a problem in pure mathematics refuted by ideas from quantum information. The boundaries between physics, computer science, and mathematics are genuinely dissolving here.

What Quantum Computers Can't Do

It's worth being explicit about the limitations. There's no proof that quantum computers can solve NP-complete problems in polynomial time, and most complexity theorists believe they can't. Scott Aaronson calls this the "No SuperSearch Principle" — an assertion that no physical means, quantum or otherwise, can solve NP-complete problems in polynomial time, analogous in status to the Second Law of Thermodynamics or the impossibility of superluminal signalling. It's not proven, but the consequences of assuming it's true are far more productive than the consequences of doubting it.⁴

The BBBV theorem makes the quantum case concrete: even for a quantum computer searching an abstract, structureless space of 2^n possible solutions, at least ~2^(n/2) steps are required. The intuition is that the single "parallel universe" that found the answer can't shout above all the others — it can only gradually make the others aware of its presence through interference. Grover's algorithm achieves this 2^(n/2) bound, which is a real speedup (taking the square root of the search time), but quadratic, not exponential. For structured problems, the story is more nuanced — the quantum adiabatic algorithm (quantum simulated annealing, essentially) can beat classical annealing on some instances but demonstrably fails on others.⁴

Aaronson's favourite illustration of why physical analogues don't escape these limits is soap bubbles. Dip two glass plates with pegs between them into soapy water, and the bubbles trace out something close to the minimum Steiner tree — an NP-hard optimisation problem. Did Nature just solve an NP-hard problem in polynomial time? No: with more than a few pegs, the soap bubbles get trapped at local optima, sometimes not even achieving a valid tree. Proteins face the same issue — they fold into low-energy configurations, but sometimes get stuck, which is believed to be exactly what happens in prion diseases. Natural selection weeds out proteins that would require solving the Riemann Hypothesis to fold correctly, so the biological "search" is pre-filtered, not general-purpose.⁴

Nielsen frames quantum computing as "nuts and bolts" — linear algebra, gate operations, measurement rules — and this framing is valuable precisely because it strips away the mysticism.¹ Quantum computers aren't magic. They're machines that exploit specific mathematical structure in quantum mechanics, and the ongoing research program is figuring out exactly which problems have the right structure.

The connection to quantum foundations is that the reconstruction program — rebuilding quantum mechanics from information-theoretic axioms — suggests that the power of quantum computing isn't an accident. If quantum mechanics is the simplest possible way to organise probabilistic information under certain constraints, then the computational power that follows from it is likewise minimal and necessary. The universe computes quantumly not because it's exotic, but because there's no simpler way to do what it does.