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}