Quantum Computation

In 1981, Richard Feynman made an observation about physics and computation. Simulating a system of $n$ quantum particles on a classical computer requires tracking amplitudes for every possible configuration, and the number of configurations grows exponentially: $n$ particles, $2^n$ amplitudes. Even modest systems overwhelm the fastest machines. Feynman asked: what if the computer itself were quantum mechanical? In 1985, David Deutsch built a computational model around the idea, the quantum Turing machine. Can a computer that runs on quantum mechanics efficiently solve problems no classical computer can?

Three postulates#

Quantum mechanics for computation rests on three postulates. State space: a quantum system with $d$ distinguishable states is described by a unit vector in $C^d$, written as a ket $|\psi ⟩$; the bra $⟨\psi |$ is its conjugate transpose. Evolution: a closed system evolves by unitary transformations, $|\psi ⟩\to U|\psi ⟩$ with $U^{\mathrm{†}}U=I$, so evolution preserves the norm and is deterministic and reversible. Measurement: measuring in the standard basis gives outcome $i$ with probability the squared magnitude of the $i$-th amplitude, and the state collapses to $|i⟩$.

A qubit is the case $d=2$. Gates are unitaries, circuits are sequences of gates, and the goal of quantum algorithm design is to arrange the gates so the right answer has high amplitude when you measure.

A general qubit state is a superposition $\alpha |0⟩+\beta |1⟩$ with $|\alpha {|}^2+|\beta {|}^2=1$. Measurement gives $0$ with probability $|\alpha {|}^2$ and $1$ with probability $|\beta {|}^2$. Two states differing only by a global phase give identical measurement probabilities, so they are the same physical state; the remaining two real parameters place every qubit state on a sphere, the Bloch sphere, with $|0⟩$ at the north pole and $|1⟩$ at the south. Gates are rotations of this sphere. $X$ is the quantum NOT, swapping $|0⟩$ and $|1⟩$. $Z$ flips the sign of $|1⟩$, a phase flip that changes no measurement probability on its own. The Hadamard $H$ sends $|0⟩$ to an equal superposition of both basis states; it is how you enter superposition.

Many qubits and entanglement#

Two qubits live in the tensor product $C^2\otimes C^2=C^4$, with basis $|00⟩,|01⟩,|10⟩,|11⟩$. For $n$ qubits the state is a vector of $2^n$ complex amplitudes: ten qubits, 1024 amplitudes; fifty qubits, over a quadrillion. This is exactly Feynman's observation. A classical computer tracking fifty qubits needs a quadrillion complex numbers. A quantum computer with fifty qubits just has fifty qubits.

Not every multi-qubit state is a product of single-qubit states. Start with $|00⟩$, apply $H$ to the first qubit, then a CNOT, which flips the second qubit exactly when the first is $|1⟩$. The result is the Bell state

$$\frac{|00⟩+|11⟩}{\sqrt{2}}$$

Measure the first qubit and you get $0$ or $1$ with probability one half each, but whatever you get, the second qubit is guaranteed to match. Perfectly correlated, individually random. No assignment of separate states to the two qubits produces this; the state is entangled.

Pause and try: prove the Bell state cannot be factored.

Suppose $\left(\alpha \right|0⟩+\beta |1⟩)\otimes \left(\gamma \right|0⟩+\delta |1⟩)$ equals the Bell state. Multiplying out and matching coefficients: $\alpha \gamma =\frac{1}{\sqrt{2}}$, $\alpha \delta =0$, $\beta \gamma =0$, $\beta \delta =\frac{1}{\sqrt{2}}$. From $\alpha \delta =0$, either $\alpha =0$, which kills $\alpha \gamma$, or $\delta =0$, which kills $\beta \delta$. Either way a required nonzero coefficient is zero. No factorization exists.

In 1935, Einstein, Podolsky, and Rosen argued such correlations suggested quantum mechanics was incomplete, with hidden variables predetermining the outcomes. In 1964, John Bell proved no local hidden variable theory can reproduce all the predictions of quantum mechanics. Entanglement is a physical resource, and quantum algorithms use it.

Circuits and BQP#

Quantum circuits are the standard model, analogous to Boolean circuits: each qubit is a wire, time flows left to right, gates are boxes, CNOT spans two wires, a meter marks measurement. The gate set $H$, $T$, CNOT is universal: any $n$-qubit unitary can be approximated to arbitrary precision from these three, and the Solovay-Kitaev theorem guarantees the approximation is efficient, with gate count growing only polylogarithmically in the inverse precision $1/ϵ$. This grounds the complexity class BQP, bounded-error quantum polynomial time: languages decided by uniform families of polynomial-size quantum circuits with error at most one third on every input. As BPP captures efficient classical randomized computation, BQP captures efficient quantum computation.

One query instead of two#

Applying a gate to a superposition is like evaluating a function on every input at once: put $n$ qubits into uniform superposition and apply a unitary computing $f$, and the output state encodes $f\left(x\right)$ for every $x$ simultaneously. But measuring gives $f\left(x\right)$ for one random $x$, just one evaluation. To extract anything useful, the answers must interfere: wrong answers cancel, right answers reinforce.

Deutsch's algorithm, in its modern form, is the simplest demonstration. Given a black-box $f$ from one bit to one bit, decide whether $f$ is constant, $f\left(0\right)=f\left(1\right)$, or balanced, $f\left(0\right)\ne f\left(1\right)$. Classically you must query twice. Quantumly, prepare two qubits as $|0⟩$ and $|1⟩$, apply $H$ to both, and query the oracle once. With the second register in that particular superposition, the value of $f$ is absorbed into the phase of the first qubit rather than written into the second. This is phase kickback. One more Hadamard on the first qubit makes the phases interfere: constant gives measurement $0$, balanced gives $1$. One query, certainty.

Grover's search#

Suppose $f$ maps $n$-bit strings to a single bit and exactly one input $x^{*}$ gives output one. Find it. Classically there is nothing to do but guess and check, about half of all $2^n$ inputs on average. In 1996, Lov Grover found a quantum algorithm using on the order of $\sqrt{2^n}$ queries, a quadratic speedup, and Bennett, Bernstein, Brassard, and Vazirani proved no quantum algorithm can do better.

Start with all $n$ qubits in uniform superposition: every basis state has amplitude $\frac{1}{\sqrt{2^n}}$, the marked one included. Then alternate two operations. The oracle flips the sign of the marked state's amplitude. The diffusion operator $D=2|\psi ⟩⟨\psi |-I$, where $|\psi ⟩$ is the uniform superposition, reflects the state about that superposition: it sends each amplitude $a$ to twice the mean minus $a$.

Take three qubits, so $2^n=8$ and every amplitude starts at $\frac{1}{\sqrt{8}}\approx 0.354$. The oracle makes the marked amplitude negative, which pulls the mean down slightly. The diffusion reflects every amplitude about that mean: the unmarked ones, just above the mean, drop by half; the marked one, far below it, gets pushed way up. After one iteration the marked amplitude has more than doubled while every other amplitude shrank.

The geometric picture makes this exact. The state lives in the plane spanned by $|x^{*}⟩$ and the uniform superposition over unmarked states, and the initial angle $\theta$ from the unmarked axis satisfies $\sin \theta =\frac{1}{\sqrt{2^n}}$. Each iteration is a rotation by $2\theta$ toward $|x^{*}⟩$, so after $k$ iterations the success probability is ${\sin }^2\left(\right(2k+1\left)\theta \right)$. Setting $(2k+1)\theta \approx \frac{\pi }{2}$ gives $k\approx \frac{\pi }{4}\sqrt{2^n}$. One subtlety: iterate too long and you overshoot, the rotation carries you past the target and the marked amplitude starts falling again. You must stop at the right time.

The BBBV lower bound shows this is optimal. By a hybrid argument, after $t$ queries the algorithm's states on an empty database and on a database with one marked item differ in norm by at most order $\frac{t}{\sqrt{2^n}}$, so distinguishing them takes order $\sqrt{2^n}$ queries. Grover matches the bound. Wherever the best classical approach is brute-force search, Grover cuts the query count to its square root.

Beyond#

Grover gives a quadratic speedup; Shor gave an exponential one. In 1994, Peter Shor showed a quantum computer can factor integers in polynomial time, by reducing factoring to period-finding and solving that with the quantum Fourier transform. Since the best known classical factoring algorithms take sub-exponential time, this would break RSA and related cryptosystems.

Where does BQP sit? It contains P, since classical computation can be simulated quantumly, and it is contained in PSPACE: a classical machine can compute any circuit's output probability in polynomial space by summing over computational paths one at a time rather than storing the exponential state vector. Where BQP falls between those bounds, and whether it extends beyond BPP, is open. There is also QMA, the quantum analogue of NP, where a quantum verifier checks a quantum proof. Feynman noticed that nature tracks exponentially many amplitudes. Grover showed how to use them. The question is how far the advantage goes.

If you remember three things#

1. Three postulates do all the work: states are unit vectors in $C^{2^n}$, evolution is unitary and reversible, and measurement samples by squared amplitude. Algorithms arrange interference so the right answer has high amplitude.
2. Entanglement is real structure, not bookkeeping: the Bell state has perfectly correlated, individually random measurements and provably no factorization, and Bell showed no local hidden variables explain it.
3. Grover's iteration is a rotation by $2\theta$ with $\sin \theta =\frac{1}{\sqrt{2^n}}$, so $\frac{\pi }{4}\sqrt{2^n}$ queries find the needle, that count is provably optimal, and overshooting past it makes things worse.