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.
Reversibility is a classical idea that quantum hardware makes mandatory. Learning to embed irreversible logic into reversible circuits is the first real circuit-design skill this book asks of you, and it pays off long before any quantum device enters the picture.
By the end of this chapter you will be able to take any small Boolean function, say whether it can be undone, and — when it cannot — rebuild it as a reversible transformation that keeps enough information around to run backward.
Core concepts: bits and registers, gates and truth tables, reversible computation, embedding, uncomputation.
Bits, gates, and circuits
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.
What reversible means, precisely
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.
Worked example: building a reversible AND
Start from the irreversible truth table:
Now add a target bit initialized to 0 and carry the inputs through:
This is the Toffoli pattern: flip the target exactly when both controls are 1. The output column contains the AND result, and the full map — all three wires in, all three out — is one-to-one, which you can confirm by checking that no two complete input rows produce the same complete output row. If is allowed to be 1 as well, the same rule stays reversible: it is its own inverse.
The general lesson matters more than the example. Quantum circuits often carry extra wires and extra information because the legal transformations must preserve enough structure to be undone. When you see a quantum circuit with "workspace" qubits, you are looking at the same move this truth table just made.
Where the intuition fails
The first trap is asking whether a quantum computer can perform AND, OR, or a database lookup as if those operations could be dropped straight into a quantum circuit. The better question is: what reversible operation implements the same useful relation while preserving valid quantum evolution? The answer is usually an embedding like the one above, and the extra wires are part of the price.
The second trap is ignoring cleanup. Reversible computation creates temporary workspace, and in a quantum machine that workspace can end up entangled with the answer or holding leftover history. Left in place, it ruins the interference the algorithm depends on. Well-built quantum algorithms therefore compute, extract what they need — often a phase — and then uncompute: run the embedding backward to return the workspace to a clean state. Uncomputation is not an optimization. It is part of the algorithm.
The engineering view
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.
What this buys you in diligence
When a team claims it can accelerate a workflow, ask which part of the workflow becomes a reversible quantum transformation. Data loading, objective functions, constraint checks, and lookup procedures are not free: each must be represented as a circuit or a hardware-native operation, with extra wires, extra gates, and an uncomputation cost. A claim that never mentions this overhead is describing the algorithm's marketing diagram, not its resource estimate.
Reversibility is also where real software value hides. Tools that synthesize efficient reversible circuits, shrink temporary workspace, or automate uncomputation directly lower the resource estimates that decide whether an application is feasible. A credible improvement there is worth more than a new demo on an old benchmark.
Exercise
Embed one function. Choose a two-input irreversible Boolean function — NAND and OR are both good choices — and embed it into a reversible three-bit or four-bit transformation, the way the worked example embeds AND.
- Submit: the complete truth table of your reversible transformation, with the original function's output marked on the target wire.
- Check: verify that no two complete input rows map to the same complete output row. If two do, the map is not one-to-one and cannot be inverted.
- Repair: if your construction discards an input or cannot be undone, rebuild it using the Toffoli pattern — carry every input through on its own wire and write the answer into an extra target.
Check your understanding
Without notes: take a small classical truth table, construct a reversible version of it, and explain what extra information the reversible version preserves and why.
A passing answer names the original irreversible function, shows the embedding, and states in one sentence why quantum gates force this discipline. An answer that treats quantum gates as arbitrary classical functions, or that ignores where the AND result physically lives, does not pass yet.
Oral defense: explain to a colleague why a quantum computer can evaluate any classical function, but only after the function is re-expressed as a reversible circuit — and why the extra wires are a feature, not waste.
If you get stuck
If reversibility still feels like an arbitrary rule imposed for elegance, return to Chapter 1 (Computation Is Physical). The requirement comes from the physics of closed-system evolution, not from notation, and the physical framing there is what makes the embedding construction here feel inevitable rather than fussy.