Boolean and Reversible Computation

What does it mean to hand a mathematical problem to a machine that only manipulates zeros and ones? By themselves, bits carry no intrinsic meaning—they are simply two distinguishable states of a physical system. An encoding is the dictionary that assigns meaning to each string of bits. Under a two-bit unsigned binary encoding, the strings \(00\), \(01\), \(10\), and \(11\) represent the integers zero through three; under an eight-bit encoding, the single string \(01000001\) represents either the integer \(65\) in unsigned binary or the capital letter A in the ASCII text standard.

Choosing an encoding is far more than a matter of notation: it directly shapes how we measure computational cost, because an algorithm’s resource use is always evaluated as a function of its input length. To represent a positive integer \(N\) in unary notation—writing \(N\) tally marks on a tape, as in the simple Turing machines of Chapter 1—requires an input of length \(N\). In binary positional notation, by contrast, \(n\) bits can distinguish \(2^n\) values, so the same integer \(N\) requires only about \(\log_2 N\) bits. A procedure that takes \(N\) steps looks fast when measured against an \(N\)-symbol unary string, yet takes exponentially many steps relative to the compact \(\log_2 N\)-bit binary representation.

Once an encoding is fixed, inputs of length \(n\) range over \(2^n\) possible bit strings. Importantly, a genuine algorithm must handle all permitted input lengths \(n\) using one uniform, finite procedure—we are not allowed to smuggle in a newly invented lookup rule for each input size.

Once inputs and outputs are represented in binary, what is the mathematical object a computer actually evaluates? Consider a yes-or-no question about an \(n\)-bit input—for example, whether an \(n\)-bit integer is odd, or whether two bit strings match. Identifying “no” with \(0\) and “yes” with \(1\) turns the task into a Boolean function

\[f:\{0,1\}^n\to\{0,1\},\]

which assigns a single output bit, \(0\) or \(1\), to each of the \(2^n\) possible input strings. What if a calculation produces an \(m\)-bit output, such as the sum of two binary numbers? That multi-bit transformation is simply a list of \(m\) separate Boolean functions \(f_1, f_2, \dots, f_m\), one for each bit of the answer. Understanding single-output Boolean functions therefore suffices to describe any finite computation on bits.

The most direct way to specify a Boolean function \(f\) is to list every possible input string alongside its corresponding output bit. This complete input–output catalog is the truth table of \(f\). For the two-bit operations AND (which outputs \(1\) only when both inputs are \(1\)) and OR (which outputs \(1\) whenever at least one input is \(1\)), the truth tables have four rows:

Does a truth table tell us how to compute \(f\)? It defines what the answer must be for every input, but provides no step-by-step mechanism for calculating it. Moreover, truth tables grow at an explosive rate: an \(n\)-bit function has \(2^n\) rows, so even a \(100\)-bit input would require a table of \(2^{100}\) rows—vastly larger than any physical memory could ever store. To compute functions on many bits, we need a compact rule built from a small set of elementary operations.

Can we systematically turn any truth table into an algebraic formula? We can, provided we work in arithmetic modulo two, where numbers are reduced to their remainder on division by \(2\) so that \(1+1=0\). Addition modulo two is then the exclusive-OR operation (XOR, written \(a\oplus b\)), which outputs \(1\) when its two bit arguments differ and \(0\) when they are equal. Multiplication on \(\{0,1\}\) satisfies \(0\cdot0=0\), \(0\cdot1=0\), and \(1\cdot1=1\), which is exactly logical AND.

Using only addition and multiplication modulo two, we can build an explicit polynomial for any Boolean function \(f\) row by row. For each input string \(s=(s_1,s_2,\dots,s_n)\) in the truth table, we first construct a detector polynomial \(\delta_s(x)\) that evaluates to \(1\) when the input \(x=(x_1,x_2,\dots,x_n)\) equals \(s\), and evaluates to \(0\) on every other input. How do we test whether a single bit \(x_i\) matches \(s_i\)? When \(s_i=1\), the factor \(x_i\) itself equals \(1\) if and only if \(x_i=1\). When \(s_i=0\), the factor \(1+x_i\) flips the bit modulo two, equaling \(1\) if and only if \(x_i=0\). Multiplying these single-bit tests across all \(n\) positions gives the detector for row \(s\):

\[\delta_s(x)=\prod_{i:\,s_i=1}x_i\prod_{i:\,s_i=0}(1+x_i).\]

Because a product of bits equals \(1\) only when every factor is \(1\), \(\delta_s(x)\) is \(1\) for \(x=s\) and \(0\) for all \(x\neq s\). On two bits \((x,y)\), for example, the detector for the row \(s=01\) is \((1+x)y\).

To obtain the polynomial for \(f(x)\), we simply add modulo two the detectors of all rows \(s\) on which \(f(s)=1\):

\[f(x)=\sum_{s:\,f(s)=1}\delta_s(x)\pmod 2.\]

Why does this sum agree with \(f(x)\) on every input? On any specific input \(x\), every detector \(\delta_s(x)\) with \(s\neq x\) evaluates to \(0\), leaving only \(\delta_x(x)=1\). If \(x\) is a row where \(f(x)=1\), its detector is included in the sum, yielding \(1\); if \(f(x)=0\), that detector is absent, yielding \(0\).

Consider two-bit OR, which equals \(1\) on the three rows \(01\), \(10\), and \(11\). Adding their detectors modulo two and expanding gives

\[(1+x)y+x(1+y)+xy=x+y+3xy=x+y+xy\pmod 2,\]

since \(3\equiv1\pmod2\). Check the input \(11\): whereas ordinary integer addition would give \(1+1+1=3\), arithmetic modulo two gives \(1+1+1=1\pmod2\), matching the OR truth table. By expanding the detectors and simplifying modulo two, every Boolean function can be written as a polynomial in its input bits.

How do we turn an algebraic formula such as the OR polynomial \(z=x+y+xy\pmod 2\) into a concrete, step-by-step calculation? We break the formula into elementary two-bit operations: first compute the product \(u=xy\) using an AND operation and the modulo-two sum \(v=x+y\) using an XOR operation, and then combine those two intermediate bits into the final output \(z=u+v\) using a second XOR operation.

This connected arrangement of elementary operations is a Boolean circuit. Each elementary operation is carried out by a logic gate, and each wire routes a bit from an input—or from the output of one gate—to the input of a subsequent gate; in our OR circuit, internal wires carry the intermediate bits \(u\) and \(v\) from the first stage of gates into the final XOR gate. A wire may also supply a fixed constant bit, \(0\) or \(1\), such as the constant \(1\) needed to flip a bit via \(1+x\). Crucially, no wire in a combinational circuit ever loops back to an earlier gate, ensuring that the gates can be evaluated in a definite stage-by-stage order from inputs to output.

The exact same strategy works for any polynomial over the binary field: we multiply variables inside each product term using a cascade of AND gates and add the resulting terms modulo two using a cascade of XOR gates. Because every truth table can be written as a polynomial, it follows immediately that every Boolean function \(f:\{0,1\}^n\to\{0,1\}\) can be computed by a Boolean circuit.

Does this guarantee that every Boolean function has a small circuit? Not at all. Building a polynomial directly from a truth table can produce up to \(2^n\) detector terms, which translates into an exponentially large network of gates. Sometimes algebraic cancellation collapses a huge sum of detectors into a compact circuit—for instance, the \(n\)-bit parity function \(x_1+x_2+\dots+x_n\pmod 2\) equals \(1\) on \(2^{n-1}\) truth-table rows, yet after simplification it requires only \(n-1\) XOR gates. For most Boolean functions, however, no such simplification exists. Showing that every function can be realized by a circuit settles the question of expressiveness; finding the most economical circuit to realize a given function is a central challenge of circuit complexity.

To build circuits for arbitrary Boolean functions, do we really need to manufacture separate hardware gates for AND, XOR, and NOT? Remarkably, a single type of gate is enough. The NAND (“not-AND”) gate outputs the negation of logical AND, written \(\operatorname{NAND}(a,b)=\neg(a\land b)\), where \(a\land b\) denotes the AND of \(a\) and \(b\). Its truth table is the exact opposite of AND: it outputs \(0\) only when both inputs are \(1\) (\(a=b=1\)), and outputs \(1\) on the remaining three input pairs (\(00\), \(01\), and \(10\)).

From NAND alone, we can systematically reconstruct every gate used in polynomial evaluation. First, tying both inputs of a NAND gate to the same bit \(a\) produces logical negation (NOT): since \(a\land a=a\), we have \(\operatorname{NAND}(a,a)=\neg(a\land a)=\neg a\). Second, passing the output of a NAND gate through a NOT gate recovers AND: \(a\land b=\operatorname{NAND}\bigl(\operatorname{NAND}(a,b),\operatorname{NAND}(a,b)\bigr)\). Third, combining four NAND gates yields XOR:

\[t=\operatorname{NAND}(a,b),\quad u=\operatorname{NAND}(a,t),\quad v=\operatorname{NAND}(b,t),\quad a\oplus b=\operatorname{NAND}(u,v).\]

We can verify this four-gate identity directly across all four input pairs. Whenever \(a\) and \(b\) are equal—either \(00\) (where \(t=1\)) or \(11\) (where \(t=0\))—both intermediate wires evaluate to \(u=1\) and \(v=1\), so the final NAND gate outputs \(0\). Whenever \(a\) and \(b\) differ (\(01\) or \(10\)), the first gate gives \(t=1\), causing one of \(u,v\) to be \(0\) and the other to be \(1\), so the final NAND gate outputs \(1\). Because NAND gates can build NOT, AND, and XOR—and can therefore evaluate the polynomial of any Boolean function—the NAND gate is universal for classical computation.

Notice a quiet structural feature that makes these constructions possible: a single wire repeatedly splits so that one bit can feed several gates at once. In our four-NAND circuit for XOR, the inputs \(a\) and \(b\) each branch to two gates, and so does the intermediate wire \(t\). Duplicating a bit across branching wires in this manner is called fan-out. In classical circuits, fan-out is treated as a free wiring operation, since a voltage signal on a wire can easily drive multiple gate inputs—a freedom we will have to re-examine carefully when we move to reversible and quantum circuits.

Now that we can build any Boolean function out of elementary gates, let us ask what happens to the input information as a gate acts. When a two-bit AND gate outputs \(1\), its input is uniquely determined: it must have been \(11\). When the gate outputs \(0\), however, three different input pairs—\(00\), \(01\), and \(10\)—all collapse to that single output value. The same loss of distinction occurs in OR, NAND, and XOR: because each of these gates compresses four possible two-bit inputs into just two possible one-bit outputs, different inputs are forced to merge. Reversibility requires that every allowed output identify a unique input, so an unrestricted two-input, one-output gate has no inverse.

When analyzing whether a calculation is reversible, we must always specify which wires are kept in the final state. A gate that loses information in isolation can form part of a one-to-one step if a copy of an input is preserved elsewhere: for instance, if we use fan-out to retain \(x\) on one wire while computing \(s=x\oplus y\) on a second wire, the combined two-bit output \((x,s)\) is completely reversible because we can recover \(y=x\oplus s\). Conversely, keeping two output bits from two input bits does not automatically make a circuit reversible: computing \(x\land y\) on one wire and \(x\lor y\) on another still merges the inputs \(01\) and \(10\) into the same output pair \((0,1)\).

Even more importantly, a circuit whose overall input–output map is one-to-one is not genuinely reversible if it discards intermediate wires or uses irreversible gates internally along the way. A reversible computer—and, ultimately, a quantum computer—demands a stricter standard: a sequence of elementary steps in which every single gate preserves distinctions across the full state of the registers. Can we still compute arbitrary Boolean functions without ever using AND or NAND as a two-to-one erasure? To see how, we turn next to the physical meaning of information erasure and the mathematical technique for embedding any function into a reversible transformation.

The simplest irreversible operation on a single bit is a reset, which takes a memory cell whose initial value may be \(0\) or \(1\) and forces it into the state \(0\). Why does this logical compression matter to physics? Because the microscopic laws of physics conserve information, compressing two distinguishable physical states of a memory register into a single state cannot simply make the lost distinction vanish; the removed uncertainty must be dumped into the surrounding thermal environment.

In the standard isothermal setting—where a memory register interacts with a thermal reservoir at absolute temperature \(T\)—erasing one equally likely bit without retaining its value elsewhere releases at least

\[Q\geq k_{\mathrm B}T\ln2\]

of heat into the environment on average. This lower bound, discovered by Rolf Landauer in 1961, is Landauer’s principle; here \(T\) is absolute temperature in kelvins and \(k_{\mathrm B}\approx 1.38\times 10^{-23}\text{ J/K}\) is Boltzmann’s constant. At room temperature (\(T=300\text{ K}\)), \(k_{\mathrm B}T\ln2\) is about \(2.9\times 10^{-21}\text{ J}\) per erased bit—tiny compared with the resistive heating of present-day transistors, yet an inescapable physical floor whenever information is destroyed.

Crucially, Landauer’s bound is a thermodynamic price for reducing entropy under stated physical conditions, not an automatic fee charged every time a logic gate acts. A bit already known to be \(0\) can be left untouched at zero minimum cost. If a bit is statistically biased, or if its value is partly or fully correlated with a record kept in another register, less uncertainty is removed and the minimum heat bound is correspondingly smaller—though any physical memory holding that external record will face the same erasure cost if it is later reset.

We will not need a statistical-mechanical derivation of this bound. For our purposes, the essential takeaway is computational: physical erasure is forced only when a calculation merges distinct logical states. If a useful calculation can avoid merging logical states altogether, it avoids forcing information erasure at those steps, even though any imperfect physical device may still dissipate energy for practical engineering reasons.

If a computation never erases information, does it automatically run without producing heat? Not necessarily. We call a transformation logically reversible when it is one-to-one on its allowed states—meaning, on a finite set of \(n\)-bit strings, that it acts as a permutation of all \(2^n\) strings. Because a logically reversible step never merges distinct states, it avoids the minimum heat cost that information erasure forces. Even so, a real physical device implementing that step may still dissipate energy through electrical resistance, friction, imperfect control, or the speed at which it is driven.

Conversely, can a gate that loses logical information—such as a two-input, one-output AND gate or a reset operation—be made reversible simply by operating the hardware slowly and carefully? No. Running an AND gate slowly does not make its output \(0\) reveal whether the input was \(00\), \(01\), or \(10\). Logical reversibility is a mathematical property of the input–output map itself, not of the physical process used to carry it out.

Two questions must therefore be kept cleanly apart: first, whether the mathematical transformation on the state space can be inverted; and second, how much energy a particular physical realization dissipates as heat. Throughout this book, our primary concern is the first question: how to construct computations so that every elementary step can be undone.

How can we evaluate any Boolean function \(f:\{0,1\}^n\to\{0,1\}\) without erasing information, even when \(f\) is a many-to-one operation like AND or OR that merges its inputs? The key is to keep the input register intact and write the answer into an extra target bit \(t\).

Specifically, we adjoin a single target bit \(t\in\{0,1\}\) to the \(n\)-bit input \(x\) and replace \(f\) by the \((n+1)\)-bit transformation

\[U_f:(x,t)\mapsto(x,\,t\oplus f(x)),\]

where the symbol \(\mapsto\) (“maps to”) gives the rule sending each input state to its output state. The input \(x\) passes through unchanged, while the function value \(f(x)\) is added modulo two to the target bit \(t\). Note that \(U_f\) does not overwrite \(t\) with \(f(x)\); rather, it XORs \(f(x)\) into whatever value \(t\) already holds. When we initialize the target bit to \(t=0\), the target register receives \(0\oplus f(x)=f(x)\).

Why is \(U_f\) guaranteed to be reversible for every Boolean function \(f\)? Apply \(U_f\) twice in succession: because the first register still holds \(x\) after the first step, the second application computes the same bit \(f(x)\) and adds it modulo two a second time,

\[U_f\bigl(U_f(x,t)\bigr)=U_f\bigl(x,\,t\oplus f(x)\bigr)=\bigl(x,\,t\oplus f(x)\oplus f(x)\bigr)=(x,t),\]

since adding any bit to itself modulo two gives \(0\). The map \(U_f\) is therefore its own inverse, which proves that it is one-to-one and onto on all \((n+1)\)-bit strings. For the two-bit AND function \(f(x,y)=xy\), this reversible embedding is \((x,y,t)\mapsto(x,y,t\oplus xy)\), which swaps \(110\) with \(111\) and leaves the other six triples unchanged:

Has the AND function itself suddenly become invertible? No: \(f(x,y)=xy\) is unchanged and still merges three input pairs into \(0\). What is invertible is the larger map \(U_f\) on the expanded state space that preserves \((x,y)\) alongside the target. Those retained input bits are not mere bookkeeping—they are the exact information required to make the transformation one-to-one, and the same reversible map \(U_f\) will serve as our standard model of a function oracle in quantum algorithms.

How can an elementary gate make one bit’s update depend on another bit without losing any information? The general principle is to keep the deciding bit unchanged while letting its value select which reversible operation is applied to the other bit. The preserved wire is called the control, and the updated wire is called the target.

On a single target bit, there are only two reversible operations: doing nothing (the identity) and flipping the bit (NOT). Doing nothing when the control \(a\) is \(0\) and flipping the target \(b\) when the control \(a\) is \(1\) defines the controlled-NOT gate, or CNOT:

\[\operatorname{CNOT}:(a,b)\mapsto(a,\,b\oplus a).\]

When the control is \(0\), the target is untouched (\(00\to00\) and \(01\to01\)); when the control is \(1\), the target flips (\(10\to11\) and \(11\to10\)). Notice in particular that when the target is initialized to \(b=0\), CNOT maps \((a,0)\mapsto(a,a)\): this is how a reversible circuit copies a bit (fan-out), using a CNOT gate and a fresh target wire initialized to \(0\).

Applying CNOT twice in succession restores both bits, \((a,\,b\oplus a\oplus a)=(a,b)\), so CNOT is its own inverse. Why does this controlled construction guarantee reversibility in general? Because the control bit \(c\) survives the gate unchanged, we still know after the gate has acted which reversible operation \(g_c\) was applied to the target, and we can simply apply its inverse \(g_c^{-1}\) to undo the step.

Would the gate remain reversible if we applied a reversible update to the target but discarded the control—or kept the control but used an irreversible reset on the target when \(c=1\)? Neither works: without the control bit we would not know whether to flip the target back, and if the conditional action reset the target to \(0\), the inputs \((1,0)\) and \((1,1)\) would both collapse to \((1,0)\). Both a preserved control and a reversible target update for each control value are required.

Can we build every reversible Boolean circuit using only NOT and CNOT gates? No: NOT only adds \(1\) modulo two and CNOT only adds one wire’s value to another modulo two, so any circuit built solely from NOT and CNOT gates produces only linear combinations of the input bits modulo two. In particular, such circuits can never form the degree-two product \(ab\) needed for logical AND. To obtain a reversible multiplication gate, we give the target bit two controls instead of one, defining the three-bit Toffoli (or controlled-controlled-NOT) gate:

\[\operatorname{Toffoli}(a,b,c)=(a,b,c\oplus ab).\]

The Toffoli gate flips its target bit \(c\) only when both controls \(a\) and \(b\) equal \(1\), exchanging \(110\leftrightarrow 111\) and leaving the other six three-bit inputs unchanged. With \(c=0\), the target becomes \(ab\) while both inputs survive. Fixing one control to \(1\) reduces the Toffoli gate to CNOT, and fixing both controls to \(1\) reduces it to NOT. Can Toffoli gates simulate every classical Boolean circuit? Setting the target to \(c=1\) yields \(1\oplus ab=\operatorname{NAND}(a,b)\), and we already know from Section 2.2.2 that NAND alone builds every Boolean function. Any wire that needs to branch to multiple gates can be copied onto a fresh \(0\) wire with CNOT. Thus, replacing each NAND gate in a classical circuit with a Toffoli gate targeting a fresh wire initialized to \(1\) makes any circuit reversible, keeping all inputs and intermediate results in clean workspace. As before, this construction proves universality—that a reversible circuit always exists—without claiming that the naive translation is the most economical.

An alternative three-bit universal gate is the controlled-swap, or Fredkin gate, which keeps its control bit \(a\) intact and swaps its two targets \(b\) and \(c\) whenever \(a=1\). Applied to \((a,b,0)\), its third wire becomes \(ab\); applied to \((a,1,0)\), its target wires become \((\neg a,a)\), providing both NOT and a copy of \(a\). With constant \(0\) and \(1\) wires and clean workspace, Fredkin gates are likewise universal for reversible computation.

In circuit diagrams, time runs from left to right along horizontal wires: a filled dot marks a control that triggers on \(1\), a circled plus (\(\oplus\)) marks an XOR target, a pair of crosses (\(\times\)) marks two swapped targets, and a vertical line connects the wires acted on by a single gate. Both the Toffoli gate and the Fredkin gate are their own inverses.

Toffoli gates allow us to evaluate any Boolean circuit reversibly, but a multi-step calculation inevitably writes intermediate values into temporary wires along the way. What becomes of those temporary bits once we have the final answer? Suppose we want to compute the three-bit AND \(xyz\) using Toffoli gates and two extra bits initialized to \(0\): a temporary workspace bit \(w\) and an output bit \(t\). The first Toffoli gate uses controls \(x,y\) to write \(w=xy\); the second uses controls \(w,z\) to write \(t=wz=xyz\):

\[(x,y,z,0,0)\to(x,y,z,xy,0)\to(x,y,z,xy,xyz).\]

The desired answer \(xyz\) now sits in \(t\), but the workspace bit \(w\) still holds the intermediate product \(xy\). How should we handle \(w\)? Resetting \(w\) unconditionally to \(0\) would erase unknown information and incur the Landauer heat cost. Leaving \(w\) untouched avoids erasure, but clutters the workspace with a permanent record of the computation’s history—and in a long calculation, every gate would consume another fresh workspace bit.

Reversibility provides a clean third option: apply the first Toffoli gate (with controls \(x,y\) and target \(w\)) a second time. Because \(x\) and \(y\) are still intact and the Toffoli gate is its own inverse, this step adds \(xy\) modulo two into \(w\) once more, returning \(w\) to \(xy\oplus xy=0\) without disturbing the answer in \(t\):

\[(x,y,z,xy,xyz)\to(x,y,z,0,xyz).\]

Clearing temporary registers by running intermediate steps backward is called uncomputation. In general, a forward reversible circuit \(A\) starting from \((x,0,0)\) produces the desired answer \(f(x)\) alongside intermediate workspace values \(g(x)\), often called garbage. By adjoining a fresh output register initialized to \(0\), copying \(f(x)\) into it with CNOT gates, and then running the inverse circuit \(A^{-1}\) (applying the gates of \(A\) in reverse order), we restore every workspace wire to \(0\):

\[(x,0,0;0)\to(x,f(x),g(x);0)\to(x,f(x),g(x);f(x))\to(x,0,0;f(x)).\]

At the end, only the input \(x\) and the copied answer \(f(x)\) remain, while the workspace is clean and ready for reuse. Why go to this trouble? Classically, uncomputation recycles memory and avoids the thermodynamic cost of erasure, since removing a redundant copy \(g(x)\) while \(x\) is still present is a one-to-one permutation rather than a many-to-one reset. Quantum computation adds an even deeper reason: if input-dependent garbage \(g(x)\) is left behind in the workspace, it acts as a record of the computation’s history that prevents the quantum interference on which quantum algorithms depend.