A reversible operation maps each input to exactly one output, with each output coming from exactly one input. This one-to-one behavior lets the original input be recovered from the result. In quantum programming, classical function evaluation is expressed as a unitary operation whose behavior is specified on basis states. section 6.7 section 6.2.1
For a reversible single-bit function, an in-place transformation can directly map |x⟩ to |f(x)⟩. Identity implements f(x) = x, while an X gate implements f(x) = 1 − x. Constant functions are not reversible in place because they map multiple inputs to the same state. section 6.2 section 6.2.1
Any classical function can instead be embedded in a reversible operation by preserving its input and writing its value into a separate output bit: F(x, y) = (x, y ⊕ f(x)). With y initialized to 0, the result is (x, f(x)); retaining x prevents information loss. For larger Boolean functions, temporary values can occupy auxiliary qubits and must be uncomputed to avoid side effects. section 6.4.1 section 6.7
A practical implementation workflow is:
- Break classical evaluation into primitive logic gates. section 6.7
- Replace each gate with a reversible equivalent, then with quantum gates. section 6.7
- Test every basis-state input against the classically calculated output, checking that inputs remain intact and outputs equal f(x). section 6.3
Self-inverse output accumulation
The standard embedding is its own inverse: applying F(x, y) = (x, y ⊕ f(x)) twice restores (x, y), because f(x) ⊕ f(x) = 0. Independent constraint checks can therefore be uncomputed by rerunning their evaluation; dependent computations require reverse-order uncomputation. section 8.2.2
Table 6.1 Single-bit functions and their reversible two-bit extensions
| Function \(f(x)\) | Extended function \(F(x, y)\) | Extended input | Extended output |
| \(f(x) = 1\) | \(F(x, y) = (x, y \oplus 1)\) | \((0, 0)\) | \((0, 1)\) |
| \((0, 1)\) | \((0, 0)\) | ||
| \((1, 0)\) | \((1, 1)\) | ||
| \((1, 1)\) | \((1, 0)\) | ||
| \(f(x) = x\) | \(F(x, y) = (x, y \oplus x)\) | \((0, 0)\) | \((0, 0)\) |
| \((0, 1)\) | \((0, 1)\) | ||
| \((1, 0)\) | \((1, 1)\) | ||
| \((1, 1)\) | \((1, 0)\) |
Compare single-bit functions with reversible two-bit extensions that preserve the input and accumulate the function value in an output bit. section 6.2.1
