A nonreversible function maps multiple inputs to the same output, so its input cannot be uniquely recovered. Quantum gates cannot implement such a mapping directly because quantum operations must be reversible and have a defined adjoint. section 6.2.1
Convert a nonreversible function into a reversible quantum computation by:
- Preserving the original input instead of replacing it with the function value. section 6.2.1
- Adding a separate output bit and computing F(x, y) = (x, y ⊕ f(x)), commonly with y initialized to zero. section 6.7
- Using auxiliary qubits for temporary values and uncomputing them by applying the relevant adjoint operations. section 6.7
Constant function
The transformation |x⟩ → |0⟩ is nonreversible because both possible input states produce the same output. Instead, preserve x and write the result into a separate target bit, making the overall transformation reversible. section 6.2.1
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, including input-output mappings for constant and identity functions. section 6.2.1
