Part I. Mental Model · Chapter 2
Classical Information, Gates, Circuits, and Reversibility
Every gate you will ever draw in a quantum circuit is reversible, and that rule was learned from classical computing first. This chapter rebuilds the classical baseline — bits, gates, truth tables, circuits — and shows exactly what it costs to make an ordinary operation like AND invertible.
In this chapter 7 sections
Reader question. How can an irreversible classical function be embedded in a reversible circuit without losing the result or corrupting later interference?
Keep the input, write the function into an ancilla with an XOR-style reversible map, use the result, and uncompute temporary workspace; reversibility preserves distinguishable basis states and makes garbage management part of the algorithm.
- This chapter does not claim that classical computers must be programmed reversibly in ordinary use.
- It does not yet prove unitarity for arbitrary quantum states; Chapter 12 supplies that formalism.
Information erased by AND
Use a truth table to show why the naive map is many-to-one.
Classical digital computing is built from stable states and transformations. A bit stores one of two values. A register stores a tuple of bits. A logic gate maps input bits to output bits, and a circuit composes gates into a larger transformation. None of this is exotic, and that is the point: quantum computing keeps this skeleton and changes what the wires and gates are allowed to do.
The bridge to quantum computing is reversibility. Many ordinary classical gates discard information. An AND gate maps three different input pairs to the output 0, so once you see a 0 on the output wire you cannot say which input produced it. Information that is discarded cannot be recovered from the output alone.
Closed-system quantum operations are reversible; full stop, no exceptions for convenience. That does not prevent a quantum computer from evaluating ordinary functions. It means irreversible functions must be embedded into reversible transformations that preserve enough structure to be inverted, and the embedding is a design decision you make consciously, not a detail the compiler hides.
Evidence boundary. Irreversible logical operations can be embedded into reversible computations by retaining inputs and workspace. [Charles H. Bennett] [Michael A. Nielsen]
An embedding that keeps every branch distinct
Construct (x,y,z)→(x,y,z⊕xy) with Toffoli.
A classical Boolean gate computes a function . The gate is reversible when the function is one-to-one over the relevant state space: every output corresponds to exactly one input. Equal numbers of input and output wires are a necessary start, and a one-to-one map finishes the job.
NOT is the trivial example. It sends 0 to 1 and 1 to 0; applying it a second time recovers the input. AND fails the test:
Three inputs collapse into one output, so no inverse exists. The standard repair keeps the inputs and writes the result into an extra target bit:
When starts at 0, the final bit comes out holding , while and remain available on their own wires. Nothing was thrown away, so the map can be inverted; apply it again and the target returns to its original value.
Evidence boundary. Quantum gates act reversibly on closed-system pure-state evolution. [Michael A. Nielsen] [John Preskill]
Compute, use, reverse
Trace workspace creation and uncomputation.
Evidence boundary. Uncomputation removes temporary information that would otherwise remain correlated with the result. [Charles H. Bennett] [John Preskill]
Notation contract: Classical bits x,y,z∈{0,1}; ⊕ denotes XOR; circuit wire order must be declared; Toffoli controls precede target.
Garbage becomes quantum dependency
Show how leftover workspace can block interference.
If you write software, reversibility is close to lossless state transformation: a reversible gate behaves like a pure function whose output carries enough information to reconstruct its input. Everyday code works nothing like this. We overwrite variables, branch, allocate, log, and discard; all irreversible, all invisible because the hardware absorbs the cost.
Quantum programming removes the hiding place. You track which information persists, which wires are temporary workspace, and which transformation is invertible at every step. The discipline shows up again in oracles, phase kickback, error correction, and circuit cost estimates, which is why the book places it here, before any quantum notation. A quantum gate is a matrix that preserves valid state length; a reversible classical gate is the same instinct wearing older clothes.
A reversible-circuit design checklist
Specify ancillas, outputs, cleanup, and gate cost.
Reversible AND circuit and truth-table verifier
| Field | Reader-visible record |
|---|---|
| Format | OpenQASM-compatible circuit, eight-row truth table, and simulator test |
| Verification | Verifier proves the mapping is bijective, checks every basis input, and asserts all workspace returns to zero after uncomputation. |
| Availability | Source-embedded acceptance record; no separate download is claimed |
{
"artifact": "Reversible AND circuit and truth-table verifier",
"format": "OpenQASM-compatible circuit, eight-row truth table, and simulator test",
"acceptance_test": "Verifier proves the mapping is bijective, checks every basis input, and asserts all workspace returns to zero after uncomputation.",
"publication_state": "source-embedded contract and worked fixture"
}Scope boundary
- This chapter does not claim that classical computers must be programmed reversibly in ordinary use.
- It does not yet prove unitarity for arbitrary quantum states; Chapter 12 supplies that formalism.
Depth commitment. One irreversible counterexample, one Toffoli embedding, one cleanup trace, and an executable exercise.
Practice problem
Design a reversible circuit for OR using ancillas, then uncompute every temporary bit after copying the answer to an output wire.
- Deliverable
- A circuit, complete truth table, and final-wire state for all inputs.
- Pass condition
- The test executes all basis inputs, confirms OR on the output, preserves inputs, and returns all scratch wires to zero.
Verification record
Expected solution form. Gate-by-gate construction plus exhaustive truth-table test.
Model answer. Initialize ancilla t and output y to zero. Apply CNOT(a,y), CNOT(b,y), Toffoli(a,b,t), and CNOT(t,y); y now equals a xor b xor ab, which is OR. Apply Toffoli(a,b,t) again to return t to zero. The full mapping is bijective because every gate is self-inverse.
Model result and check. A classical reversible simulator independently asserts bijection, correctness, and clean ancillas.
Acceptance test. The test executes all basis inputs, confirms OR on the output, preserves inputs, and returns all scratch wires to zero.
Provenance
Sources and review
- Charles H. Bennett. Logical reversibility of computation. IBM Journal of Research and Development. 1973primary paper
- Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press. 2010textbook
- John Preskill. Lecture Notes for Physics 219: Quantum Computation. California Institute of Technology. 2018graduate lecture notes
The load-bearing claims in the chapter are mapped inline to this registered source set. A citation supports only the bounded claim beside it.