94
Part Three · A · Foundations of quantum information

Reversible computing and Landauer's principle

Is information physical? In 1961 Rolf Landauer, at IBM, argued that it must be: erasing one bit of information, resetting a memory to zero whatever it held, must release at least kBTln⁡2k_BT\ln2 of heat into the surroundings. At room temperature that is three zeptojoules, absurdly small. In 2012 a team in Lyon trapped a single glass bead in a double-well made of laser light, erased the bit it represented, and measured the heat. It approached Landauer’s limit. Information has a thermodynamic price.

On the plate: Szilard’s one-molecule engine, which seems to turn information into work.

Szilard’s engine

In 1929 Leo Szilard imagined a box holding one gas molecule. Slide in a partition; note which side the molecule is on; attach a piston on that side and let the molecule push it out, extracting kBTln⁡2k_BT\ln2 of work from the surrounding heat bath. Repeat forever, and you would have a perpetual-motion machine of the second kind, violating the second law of thermodynamics (Chapter 18). . Something must cost at least as much as it gains.

Erasure pays the bill

Charles Bennett showed in 1982 where the cost lies. Measuring which side the molecule is on can be done reversibly at no cost. But the memory now holds a bit, and to run the next cycle it must be reset. Erasing it maps two possible states to one, reducing the memory’s entropy by kBln⁡2k_B\ln2; the second law then demands at least that much entropy, kBTln⁡2k_BT\ln2 of heat, be dumped into the environment:

Qerase≥kBTln⁡2Q_{\text{erase}} \ge k_BT\ln2

At 300 K that is 2.87×10−212.87\times10^{-21} J, or 0.018 eV. Set the temperature to 300 K. In 2012 Antoine Bérut and colleagues measured the heat from erasing the state of a 2 µm bead in a double optical trap: as the erasure was done more slowly, the heat approached kBTln⁡2k_BT\ln2. Established

Reversible logic

Ordinary gates erase information: an AND gate with output 0 does not reveal which of three inputs produced it. A reversible gate maps inputs to outputs one to one, so in principle it can run with no minimum heat. The Toffoli gate (controlled-controlled-NOT) flips its third bit if the first two are both 1. It is universal for reversible computation: setting the third input to 0 makes its third output the AND of the first two, with the inputs kept. Choose inputs: .

Uncomputation

Reversible circuits leave behind garbage: the extra bits needed to keep everything invertible. Bennett’s trick, in 1973: compute the answer, copy it to a fresh register with CNOT gates, then run the whole computation backwards, returning the garbage to zeros. The cost is about twice the gates and no erasure. This matters enormously in quantum computing. Leftover garbage would be entangled with the answer and destroy interference (Chapter 52), so every quantum oracle in Shor’s and Grover’s algorithms (Chapters 114–115) is built with uncomputation. Established

What you now have

Szilard’s engine and why it does not break the second law, Landauer’s principle and its 2012 confirmation, reversible gates and the Toffoli gate, and Bennett’s uncomputation, the tool behind every quantum oracle.

· · ·

Three questions to carry with you.

What step in Szilard’s engine costs work?tap
Erasing the memory of which side the molecule was on.
Why is the Toffoli gate important?tap
It is universal for reversible classical computation and can compute AND without erasing inputs.
Why must quantum algorithms uncompute garbage?tap
Garbage entangled with the answer would destroy the interference the algorithm relies on.

And one to work out. What is the Landauer limit kBTln⁡2k_BT\ln2 at body temperature, 310 K, in zeptojoules (10−2110^{-21} J)?

Q =zJ

Sources: L. Szilard, Z. Phys. 53, 840 (1929). R. Landauer, IBM J. Res. Dev. 5, 183 (1961). C. H. Bennett, IBM J. Res. Dev. 17, 525 (1973); Int. J. Theor. Phys. 21, 905 (1982). A. Bérut et al., Nature 483, 187 (2012). T. Toffoli, MIT report MIT/LCS/TM-151 (1980). Checked by code: k_BT ln 2 = 2.87×10⁻²¹ J (0.018 eV) at 300 K, 2.97×10⁻²¹ J at 310 K; Toffoli truth table with Book.QSim.

Next · Chapter 95
Shannon information theory and coding

How far can you compress a genome?

Turn the page