Boolean and Reversible Computation

Bits are two distinguishable physical states; an encoding is the dictionary that gives strings of bits a meaning.

The encoding also fixes how cost is measured, because cost is a function of input length. The number \(N\) has length \(N\) in unary but about \(n=\log_2N\) bits in binary, since \(n\) bits distinguish \(2^n\) values.

So an algorithm taking \(N\) steps is linear in the unary length but exponential, \(N\approx2^n\), in the binary length.

An algorithm must be one finite procedure for all input lengths \(n\); a separate lookup rule for each \(n\) is not allowed.

Work with remainders on division by 2, so that \(1+1=0\). On bits:

• addition is exclusive OR (XOR), written \(a\oplus b\): it is 1 exactly when \(a\ne b\);
• multiplication is AND: \(0\cdot0=0\cdot1=0\) and \(1\cdot1=1\);
• \(1+x\) flips the bit \(x\).

To detect one row \(s=(s_1,\ldots,s_n)\) of a truth table, test each bit and multiply the tests:

A product of bits is 1 only when every factor is 1, so \(\delta_s(x)=1\) when \(x=s\) and \(0\) otherwise. For two bits and \(s=01\): \(\delta_{01}=(1+x)y\).

Existence is not economy. The detector construction can produce up to \(2^n\) terms, hence exponentially many gates.

Sometimes algebra collapses the sum. Parity

equals 1 on \(2^{n-1}\) rows of its truth table, so its detector sum has \(2^{n-1}\) terms; yet the simplified polynomial needs only \(n-1\) XOR gates in a chain.

For most Boolean functions no such simplification exists. Finding the smallest circuit for a given function is the central problem of circuit complexity.

An AND output of 1 identifies the input 11, but an output of 0 could come from 00, 01 or 10. OR, NAND and XOR also send four inputs to two outputs, so each merges inputs and has no inverse.

Whether a step is reversible depends on which wires are kept:

A reversible computer demands more than a one-to-one overall map: every elementary gate must preserve distinctions, with no intermediate wire discarded.

A reset sends a bit holding 0 or 1 to 0. Microscopic physics conserves information, so the lost distinction must go into the environment.

At \(T=300\) K: \(1.38\times10^{-23}\,\mathrm{J/K}\times300\,\mathrm K\times0.693\approx2.9\times10^{-21}\) J per bit, far below the resistive heating of present transistors, but a floor no design can avoid.

• A bit already known to be 0 can be left alone at no minimum cost.
• A biased bit, or one recorded elsewhere, costs less; resetting the record later costs the same again.

Erasure is forced only when a computation merges distinct logical states.

A transformation of \(n\)-bit strings is logically reversible if it is one-to-one, that is, a permutation of the \(2^n\) strings.

Two questions must be kept apart: whether the map can be inverted, and how much heat a particular device dissipates. Reversibility is a property of the map; this book is about the first question.

To compute any \(f:\{0,1\}^n\to\{0,1\}\) without erasure, keep the input and add the answer to an extra target bit \(t\):

With \(t=0\) the target becomes \(f(x)\). Applying \(U_f\) twice,

since a bit added to itself is 0. So \(U_f\) is its own inverse, hence a permutation of all \((n+1)\)-bit strings, for every \(f\).

\(U_f\) does not overwrite \(t\); it XORs \(f(x)\) into it. This map will be the standard model of a function oracle in quantum algorithms.

Compute \(xyz\) with Toffoli gates, a workspace bit \(w=0\) and an output bit \(t=0\):

The answer is in \(t\), but \(w\) still holds \(xy\). Two poor options:

• reset \(w\) to 0: this erases unknown information and pays the Landauer cost;
• leave \(w\): memory fills with a record of the history, one fresh bit per gate in a long computation.

Third option: apply the first Toffoli again. Since \(x,y\) are intact, \(w\) becomes \(xy\oplus xy=0\) and \(t\) is untouched: