Reversible Computation in Quantum Computing

Mastering Reversibility, Ancilla Bits, and Unitary Logic

1. The Necessity of Reversibility

In classical logic, gates like AND are inherently irreversible. Because they compress two input bits into a single output bit, information is physically destroyed. For example, if an AND gate outputs ‘0’, you cannot distinguish if the original inputs were (0,0), (0,1), or (1,0). This “many-to-one” mapping results in information loss that manifests as heat dissipation.

In quantum computing, thermodynamics and the laws of physics require all operations to be Unitary (U^†U = I). This means every quantum gate must be a 1-to-1 (bijective) mapping; no information is ever lost, and the entire computation can be run in reverse to recover the initial state.

2. Ancilla Bits & Uncomputation

Because we cannot erase information, we use Ancilla bits as temporary “scratch space.” However, if these qubits are left in an arbitrary state, they remain entangled with the computation. Uncomputation (running gates in reverse) resets them to |0>, “cleaning” the quantum workspace.

The Toffoli Gate (CCX)

The Toffoli gate is reversible because its mapping is bijective. No two inputs result in the same output.

The Fredkin Gate (CSWAP)

The Fredkin gate is a controlled-swap operation. It swaps the states of the two target qubits (T1 and T2) if and only if the control qubit (C) is in the state |1>. It is conservative, meaning it preserves the Hamming weight (number of 1s) from input to output.

Because it is a universal gate, we can simulate all standard classical logic by fixing certain inputs:

• NOT: Set T1=0, T2=1. Output T2 becomes NOT C.
• AND: Set T2=0. Output T2 becomes C AND T1.
• OR: Set T1=B, T2=1. Output T1 becomes C OR B.

3. Mathematics: Unitary vs. Hermitian

4. Qiskit Verification

from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator

qc = QuantumCircuit(3)
qc.x([0, 1]) # Controls to |1>

# Toffoli is Hermitian (U = U†), so applying it twice cleans the ancilla
qc.ccx(0, 1, 2) # Calculation step
qc.ccx(0, 1, 2) # Uncomputation step

qc.measure_all()
counts = AerSimulator().run(transpile(qc, AerSimulator())).result().get_counts()
print(f"Resulting state: {counts}") # Expect {'011': 1024}
            

Malcolm Low is an Associate Professor at the Singapore Institute of Technology, writing on quantum computing, programming, and applied computing from Singapore.

Website: malcolmlow.com  ·  Singapore

Why must quantum gates be reversible?

Quantum mechanics is fundamentally reversible — the Schrödinger equation preserves information with no loss — so any operation on a quantum state must be representable as a reversible (unitary) transformation.

What is an ancilla bit?

An ancilla bit is an extra qubit added to a circuit, typically initialized to 0, used to make an otherwise irreversible classical operation (like AND or OR) reversible by preserving enough information to undo it.

Can classical logic gates like AND and OR be made quantum?

Not directly, since they destroy information (you can’t recover the inputs from the output alone). They must be converted into reversible equivalents, typically using extra ancilla qubits, such as the Toffoli gate.

What happens to leftover ancilla qubits in a quantum circuit?

They must be “uncomputed” — returned to their original state — before the circuit ends, otherwise they contaminate the interference pattern the algorithm depends on to produce a correct result.