Chapter 19 The physics of computation
11 minute read
19.1Boolean logic and the silicon transistor
Across four billion years of evolution, living nervous systems distilled the regularities of nature into mathematics and logic. In the middle of the 20th century, humanity reversed that ancient arrow of abstraction. Engineers took the formal rules of deduction and etched them back into inanimate crystal. Refined beach sand learned to execute autonomous reason.
The bridge between human thought and electrical hardware began with two insights separated by nearly a century. In 1854, George Boole showed that Aristotelian logic works as an algebra over two values, truth (1) and falsehood (0). In 1937, 83 years later, a 21-year-old graduate student at the Massachusetts Institute of Technology named Claude Shannon studied telephone switches. In his master's thesis, Shannon proved that Boole's algebra maps directly onto circuits of open and closed relays.
Two switches wired in series pass current only if both close at once, executing logical conjunction, the and operation. Two switches wired in parallel pass current whenever either switch closes, executing logical disjunction, the or operation. An inverting relay opens when energized and turns a signal into its opposite, executing logical negation.
Engineers do not even need all three operations to build a universal mind. The single combined operation known as not-and, defined by , is functionally complete by itself. Every Boolean truth table of any number of inputs and outputs can be built solely by wiring not-and gates together. Binary addition, multiplication, and the entire control unit of a universal Turing machine all reduce to this single primitive switch.
Early digital computers built from mechanical relays or vacuum tubes proved the principle, yet they hit a brutal material limit. Vacuum tubes burned tens of kilowatts, radiated blistering heat, and snapped their fragile filaments every few hours. To pack billions of switches onto a fingernail of matter without moving parts, physicists turned to the quantum mechanics of solids. John Bardeen and Walter Brattain invented the point-contact transistor in 1947, and William Shockley followed with the junction transistor in 1948. By 1959, Mohamed Atalla and Dawon Kahng had created the metal-oxide-semiconductor field-effect transistor.
The physical secret of modern computing lies in the periodic crystal lattice of elemental silicon, atomic number 14. Roughly 50 sextillion silicon atoms pack into every cubic centimeter of crystal. There, the discrete outer electron orbitals described in Chapter 7 overlap across neighboring nuclei. By Felix Bloch's theorem, an electron moving through this periodic crystal potential travels as a plane wave modulated by the repeating rhythm of the atomic lattice.
This quantum overlap splits the sharp atomic energy levels into continuous energy bands separated by a forbidden energy gap. In pure silicon at room temperature (300 kelvins), a lower valence band sits full of bound electrons that lock the tetrahedral crystal together. Above that band lies an empty conduction band, separated by a forbidden gap of 1.12 electronvolts. Electrons in a full band have no empty quantum states into which they can accelerate. Pure silicon therefore acts as an electrical insulator unless thermal motion kicks a stray electron across the gap.
Engineers turn this inert crystal into a programmable medium through substitutional doping. They replace a few silicon atoms per million with impurity atoms from neighboring columns of the periodic table. Pentavalent atoms such as phosphorus or arsenic carry five valence electrons instead of four. Each impurity atom donates its fifth electron into the conduction band, creating a negatively conducting or n-type semiconductor. Conversely, trivalent boron atoms carry only three valence electrons and leave an empty quantum vacancy in the valence bonds. Neighboring electrons hop into that vacancy like cars advancing into an empty parking space. The moving vacancy acts as a mobile positive charge, or hole, creating a positively conducting or p-type semiconductor.
An n-channel field-effect transistor brings both varieties together into a microscopic electrostatic valve. Two n-type regions, called the source and the drain, sit embedded inside a p-type silicon body. Above the narrow channel between source and drain rests an oxide insulator only a few atomic layers thick, capped by a metal gate electrode.
When the gate-to-source voltage stays below a threshold value, depleted barrier zones block current between source and drain save for a tiny subthreshold trickle. In this non-conducting state, the switch holds a logical 0. When a positive voltage above threshold charges the gate, its electric field penetrates the thin oxide insulator. That vertical field pushes positive holes away and pulls a thin inversion layer of mobile electrons underneath the oxide. Instantly, a conducting n-type channel bridges source and drain. The switch flips to logical 1 with a saturation current governed by William Shockley's square-law equation:
In this law, the drain current grows with the electron mobility, the oxide capacitance per unit area, the channel width-to-length ratio, and the square of the voltage excess above threshold. Wiring an n-channel transistor in series with a complementary p-channel partner yields complementary metal-oxide-semiconductor logic. In this paired design, one transistor always blocks the path from power to ground while the gate rests in state 0 or 1. A resting gate draws almost zero static power and spends capacitive energy only during the brief picoseconds when switching states.
19.2The thermodynamic cost of erasing a bit
As photolithography shrank silicon transistors toward gate pitches of 2 nanometers, a deep question of physics moved to the factory floor. What is the minimum price in energy that nature charges to perform a single logical step?
For decades after Claude Shannon linked information to Ludwig Boltzmann's entropy formula, physicists gave the wrong answer. Pioneers including John von Neumann and Leon Brillouin assumed that every logic gate must dissipate at least a fixed quantum of thermal heat per operation. They reasoned that reading or flipping a bit requires overpowering thermal noise in the surrounding bath. This question was tied to a riddle that had troubled physics since 1867. That year, James Clerk Maxwell imagined a microscopic being guarding a trapdoor between two chambers of gas. By letting fast molecules into one chamber and slow molecules into the other, Maxwell's demon created a temperature difference out of warmth. It appeared to violate the second law of thermodynamics without doing work.
In 1961, the IBM physicist Rolf Landauer overturned the consensus with a sharp physical insight. Logical computation itself has zero fundamental thermodynamic cost. A physical process that transforms information in a one-to-one, reversible manner need not dissipate any heat at all. Instead, the thermodynamic tax falls strictly on logically irreversible information erasure, the act of mapping two logical states onto one.
We can prove Landauer's principle directly from statistical mechanics. Imagine a microscopic particle inside a symmetric double-well potential in contact with a heat bath at a fixed absolute temperature. The left well stores 0 and the right well stores 1. Before erasure, the bit holds either value with equal probability of one-half. Its initial Gibbs-Shannon entropy equals Boltzmann's constant multiplied by the natural logarithm of two.
Suppose we now run a reset operation that pushes the particle into the left well from either starting state. After the reset finishes, the particle sits in the left well with 100% certainty. Its informational entropy drops to zero, decreasing the entropy of the memory bit by Boltzmann's constant times the natural logarithm of two.
Yet the microscopic laws of physics forbid volume in phase space from vanishing. By Joseph Liouville's theorem in classical mechanics and unitary evolution in quantum mechanics, dynamical trajectories are strictly one-to-one. Compressing two logical histories into one physical state forces the surrounding heat bath to expand its phase-space volume. By the second law of thermodynamics, the bath entropy must rise by at least the entropy lost by the bit. That expansion dumps a mandatory minimum quantity of heat into the environment:
At room temperature (300 kelvins), this Landauer bound equals roughly 2.87 zeptojoules, or 0.018 electronvolts, per erased bit. Landauer's insight, extended by Charles Bennett in 1982, finally solved the riddle of Maxwell's demon. The demon can measure and sort gas molecules without generating heat so long as its memory notebook has blank pages. Once its finite memory fills up, the demon must erase old records to log new molecules. That erasure releases at least the Landauer minimum of heat per bit into the gas, paying back the exact entropy the demon saved.
This theorem also sets the ultimate thermodynamic floor below which no irreversible computer chip can ever drop. Conventional gates such as the logical and gate are irreversible funnels. An and gate takes two input bits spanning four possible configurations (00, 01, 10, 11) and emits only one output bit (0 or 1). Because no observer can reconstruct the two inputs from the single output, information is destroyed at every gate.
Between 1973 and 1982, Charles Bennett, Edward Fredkin, and Tommaso Toffoli showed how to avoid this loss entirely. Any irreversible calculation can be rewritten as a reversible circuit using three-input, three-output invertible gates such as the universal Toffoli gate. In a Toffoli gate, the first two bits pass through unchanged while their conjunction flips the third bit via addition modulo two: .
Applying the Toffoli gate a second time restores the original three bits unchanged. Because the gate is a one-to-one permutation on all eight three-bit states, it never erases a bit. A reversible computer runs a cascade of Toffoli gates forward to compute an answer and copies that answer to an output register. It then runs the circuit in reverse to uncompute all scratchpad bits back to their initial zeros. Switched slowly enough to avoid resistive friction, a reversible computer can calculate with heat dissipation approaching zero.
19.3Quantum superposition and factoring
Reversible logic gates point toward an even deeper physical synthesis. In Chapter 6, we saw that every isolated quantum system evolves in time via a unitary operator that preserves inner products and total probability. Because every unitary transformation is strictly invertible, quantum mechanics is already a native reversible computer.
In 1982, Richard Feynman noted a stark mismatch between classical computers and the quantum matter they try to simulate. As we saw in Chapter 5, describing the entangled state of 300 spin-half electrons requires tracking complex amplitudes, exceeding all the protons in the observable universe. Feynman proposed turning this obstacle into an engine by building computers out of quantum systems themselves. Three years later, David Deutsch formalized Feynman's vision as the universal quantum circuit model.
While a classical bit must choose between 0 and 1, a quantum bit, or qubit, spans a continuous complex space. It is a unit vector in a two-dimensional complex Hilbert space spanned by two orthogonal basis states:
The squared magnitudes of the two complex amplitudes sum to 1, tracing the surface of a three-dimensional sphere called the Bloch sphere. When we combine multiple qubits into a register, their joint state inhabits a tensor-product space whose dimension doubles with every added qubit.
By the Solovay-Kitaev theorem, two single-qubit gates and one two-qubit gate suffice to approximate any unitary transformation on that vast space to arbitrary precision. The single-qubit Hadamard gate splits a basis state into an equal superposition of 0 and 1, while the eighth-turn phase gate rotates the relative complex phase between them. Combined with the two-qubit controlled-not gate, which flips a target qubit whenever its control qubit holds a 1, these operations weave multi-particle entanglement across the register. Applying a layer of Hadamard gates in parallel to an all-zero register places the machine into an equal superposition of all binary numbers in one step.
Popular accounts often claim that a quantum computer evaluates a function on all inputs at once and simply reads out the solution. The Born rule of quantum measurement rules out that naive story. If we compute a function across an equal superposition and immediately measure the register, the wave function collapses at random to a single branch. We receive a useless random guess with exponentially tiny probability.
Real quantum speedups rely instead on wave interference in Hilbert space. Because quantum amplitudes carry complex phases, computational paths that reach the same state can either add together or cancel out. A quantum algorithm works like a precision interferometer. It steers wrong computational paths into destructive interference so their amplitudes cancel to zero. Simultaneously, it guides the true solution paths into constructive interference so their amplitudes reinforce near certainty before measurement.
In 1996, Lov Grover used this geometry to search an unsorted database of items. Grover's algorithm alternates a phase-flip oracle that marks the target state with a reflection across the mean amplitude. Each cycle rotates the state vector in a two-dimensional plane toward the target by an angle proportional to the inverse square root of the database size. After a number of steps proportional to the square root of the database size, the state aligns with the hidden item. That rotation beats the classical linear search limit by a quadratic factor.
Two years earlier, in 1994, Peter Shor discovered an exponential quantum speedup for integer factoring. Modern public-key cryptography relies on the difficulty of factoring a large composite integer into its two secret prime factors. By classical number theory, factoring a composite number reduces to finding the repeating period of modular exponentiation. That period is the smallest positive power that leaves a remainder of 1 when divided by the composite number. On a classical computer, the fastest known method takes sub-exponential time that grows rapidly with the number of digits.
Shor's algorithm evaluates the modular exponential function in superposition and applies the quantum Fourier transform to the input register. This quantum transform requires a number of gates proportional only to the square of the number of bits. Across the superposition, destructive interference wipes out almost every frequency that does not match the hidden rhythm of the modular sequence. Constructive interference leaves sharp resonant peaks at the integers closest to multiples of the ratio between the register size and the unknown period. Measuring such a peak and applying continued fractions reveals the period and factors the integer in cubic polynomial time.
To run such deep circuits in real hardware, engineers must overcome environmental decoherence. Stray thermal photons and magnetic fluctuations constantly corrupt fragile quantum phases, while the quantum no-cloning theorem forbids copying an unknown qubit state onto backup qubits. Yet Peter Shor, Andrew Steane, and Alexei Kitaev proved that entanglement itself can shield quantum information. In Kitaev's surface code, a single logical qubit is stored non-locally across a two-dimensional grid of entangled physical qubits. The hardware repeatedly measures four-qubit parity checks around local squares of the lattice. Those measurements reveal where bit flips or phase flips have occurred without ever measuring or collapsing the encoded logical qubit. Once physical gate errors drop below a threshold near 1%, a quantum computer can correct errors faster than noise creates them. Yet whether a processor flips silicon transistors or entangles superconducting qubits, physical switches alone do not make a mind. To turn hardware into intelligence, computer science had to discover how networks learn directly from data.