Quantum computing exploits two phenomena with no classical analog, superposition and entanglement, to perform certain calculations faster than any known classical algorithm, and super-polynomially faster in the case of factoring. The mathematics requires only linear algebra over the complex numbers; the physical interpretation is strange.
Qubits: The Basic Unit
A classical bit is 0 or 1. A qubit can be in any linear combination of both:
|psi> = alpha*|0> + beta*|1>
where alpha and beta are complex numbers satisfying |alpha|^2 + |beta|^2 = 1. The notation |·> (called a ket) comes from Dirac's bra-ket formalism. The basis states are column vectors:
|0> = [1, 0]^T |1> = [0, 1]^T
When we measure the qubit, we get 0 with probability |alpha|^2 and 1 with probability |beta|^2. Measurement is irreversible: it collapses the superposition to a definite outcome. In the standard interpretation, the qubit has no definite value until it is measured.
The Bloch Sphere
Any single-qubit pure state can be written as:
|psi> = cos(theta/2)*|0> + exp(i*phi)*sin(theta/2)*|1>
This parametrization maps every qubit state to a point on a unit sphere, the Bloch sphere. The north pole is |0>, the south pole is |1>, and points on the equator are equal superpositions with different relative phases. Mixed states (statistical mixtures due to decoherence) live inside the sphere, with the maximally mixed state at the center.
Quantum Gates
Quantum gates are unitary matrices: transformations that preserve the norm of the state vector (required so probabilities always sum to 1). Unitarity also means every quantum gate is reversible, unlike many classical logic gates.
Hadamard (H): Creates equal superposition from a basis state.
H = (1/sqrt(2)) * [[1, 1], [1, -1]]
H|0> = (|0> + |1>)/sqrt(2)
H|1> = (|0> - |1>)/sqrt(2)
Pauli-X: The quantum NOT gate. Flips |0> and |1>.
X = [[0, 1], [1, 0]]
Phase gates (S, T): Rotate the phase without changing measurement probabilities in the Z basis.
S = [[1, 0], [0, i]] T = [[1, 0], [0, exp(i*pi/4)]]
Each gate is a rotation of the Bloch sphere; S and T rotate about the Z axis. The Hadamard and T gates together can approximate any single-qubit gate, and adding CNOT (below) gives a universal gate set.
Entanglement and Multi-Qubit Systems
An n-qubit system lives in a 2^n-dimensional complex Hilbert space. Two qubits:
|psi> = a00*|00> + a01*|01> + a10*|10> + a11*|11>
The CNOT gate (Controlled-NOT) acts on two qubits: it flips the second (target) if and only if the first (control) is |1>:
CNOT = [[1,0,0,0],
[0,1,0,0],
[0,0,0,1],
[0,0,1,0]]
Applying H to the first qubit, then CNOT, starting from |00>:
|00> --H--> (|0>+|1>)/sqrt(2) ⊗ |0> --CNOT--> (|00>+|11>)/sqrt(2)
This is a Bell state, a maximally entangled pair. The two measurement outcomes are perfectly correlated regardless of the distance between the qubits, though this cannot be used to send a signal. Bell's theorem (1964) showed that no local hidden variable model can reproduce all such correlations, and experiments have confirmed the quantum prediction. Entanglement is a non-classical resource.
Quantum Interference
Quantum computing's power comes from interference. A quantum algorithm is designed so paths leading to wrong answers cancel (destructive interference) while paths to correct answers reinforce (constructive interference).
Grover's algorithm exploits this geometrically. Starting from a uniform superposition over all N = 2^n states, the algorithm alternately applies an oracle reflection (marking the target state with a phase flip) and an inversion-about-average operation. Each pair of operations rotates the state vector by angle 2*arcsin(1/sqrt(N)) toward the target. After approximately (pi/4)*sqrt(N) iterations, a measurement reveals the target with high probability.
The speedup: O(sqrt(N)) versus O(N) for classical search. For N = 2^100, classical search takes 2^100 steps; Grover's takes about 2^50, still enormous. The speedup is quadratic, not exponential.
Shor's Algorithm: Factoring in Polynomial Time
Peter Shor's 1994 algorithm factors large integers in polynomial time, O((log N)^3), compared to the best known classical algorithm (the general number field sieve), which takes sub-exponential time, roughly exp(c * (log N)^(1/3) * (log log N)^(2/3)). A large fault-tolerant quantum computer running it would break RSA encryption, which relies on factoring being computationally hard.
The central step is finding the period r of the modular exponentiation function f(x) = a^x mod N. Once r is known, the prime factors of N usually follow from a classical greatest-common-divisor computation. Period finding uses quantum phase estimation, which relies on the Quantum Fourier Transform (QFT):
QFT|j> = (1/sqrt(N)) * sum_k exp(2*pi*i*j*k/N) * |k>
The QFT can be implemented in O((log N)^2) quantum gates, versus O(N log N) for the classical FFT. The comparison is not like for like, since the QFT's output amplitudes cannot be read out directly; Shor's algorithm works because only the period is needed.
Complexity Classes and Limitations
Quantum computing does not make all hard problems easy. Current understanding:
- BQP (bounded-error quantum polynomial time) is believed to contain some problems outside classical P, such as factoring
- BQP is widely believed NOT to contain NP-complete problems: quantum computers probably cannot solve satisfiability problems efficiently
- Grover's quadratic speedup is provably optimal for unstructured search; no quantum algorithm can do better
The precise relationship between BQP and NP remains one of the deepest open questions in theoretical computer science.
Decoherence: The Engineering Challenge
Real qubits interact with their environment, causing decoherence: the gradual destruction of superposition as quantum information leaks into the surroundings. Maintaining coherence requires extraordinary isolation: superconducting qubits operate at 10-15 millikelvin (colder than interstellar space), shielded from electromagnetic noise.
Quantum error correction can protect logical qubits using redundancy across many physical qubits. The surface code, for example, encodes one logical qubit in roughly 1000 physical qubits and can correct errors as long as the physical error rate is below a threshold of about 1%. Current leading systems achieve error rates of 0.1-1%, making fault-tolerant quantum computing an engineering challenge rather than a theoretical impossibility.
The path from today's noisy intermediate-scale quantum (NISQ) devices to fault-tolerant machines capable of running Shor's algorithm on cryptographically relevant inputs is likely to take a decade or more of engineering.
Glossary
Complex numbers — An extension of ordinary numbers that includes an imaginary component. Where ordinary numbers live on a line, complex numbers live on a plane, with both a magnitude and a direction. They are essential in quantum mechanics because a qubit's amplitudes carry a phase as well as a magnitude, and phase differences are what produce interference.
Matrix — A rectangular grid of numbers that represents a transformation. When you multiply a matrix by a vector, you get a new vector, the result of applying that transformation. In quantum computing, every gate is a matrix, and applying a gate to a qubit means multiplying that matrix by the vector representing the qubit's current state.
Hilbert space — A mathematical space in which quantum states are represented as vectors. For n qubits, this space has 2ⁿ dimensions, one for each possible combination of 0s and 1s. A two-qubit system needs four dimensions; a ten-qubit system needs 1,024. This exponential growth in the size of the space is part of what gives quantum computers their potential power; interference is the other part.
Polynomial time — A measure of how efficiently an algorithm scales with input size. If an algorithm's running time grows as a polynomial function of the input (e.g., squaring or cubing it), it is considered tractable, feasible even for large inputs. If it grows exponentially (doubling with each extra bit), it quickly becomes impractical. The significance of Shor's algorithm is that it solves integer factoring in polynomial time, whereas the best known classical algorithms take super-polynomial time as the numbers grow larger.
NP-complete — A class of computational problems believed to be hard: no known algorithm solves them efficiently, and a solution for one would solve all of them. Familiar examples include finding the shortest route visiting many cities, or determining whether a logical formula can be satisfied. Contrary to a common misconception, quantum computers are widely believed not to solve NP-complete problems efficiently.