A classical function maps classical inputs to classical outputs. In quantum programming, it specifies the computation to reproduce with a unitary operation: encode classical variables in qubit arrays, then arrange quantum gates so each input basis state carries the function value in its result. This translation is reversible computing, a step between a problem’s classical formulation and a quantum algorithm that uses it. section 6.0 section 6.7
A function is reversible when every input has one output and every output comes from one input. For one-bit functions, identity f(x)=x and negation f(x)=1−x are reversible, while constant-zero and constant-one functions are not: both inputs yield the same output. Direct in-place evaluation, |x⟩ → |f(x)⟩, therefore works only for reversible functions. Identity needs no gate; negation uses X. section 6.2 section 6.2.1
Figure 6.5 The single-bit function can be reversible, like \(f(x) = x\), or not, like \(f(x) = 1\). Adding an extra bit to the input and output allows us to define the extended function \(F(x, y)\) to be reversible regardless of whether the original single-bit function was reversible.
Compare a reversible single-bit function with a nonreversible one and see why adding an output bit makes a reversible extension possible. section 6.2.1
Use a separate output bit to implement any classical function reversibly: F(x,y)=(x,y⊕f(x)). With y initialized to 0, the operation produces (x,f(x)); the input remains available, and XOR makes the full mapping reversible even when f is not. Auxiliary qubits can hold temporary values, but their changes must be uncomputed to avoid unwanted side effects. section 6.2.1 section 6.7
A practical implementation path is:
- Write the classical evaluation as primitive logic gates. section 6.7
- Replace each logic gate with a reversible equivalent, then with quantum gates. section 6.7
- Specify behavior on every computational-basis input; linearity then determines behavior on superpositions. section 6.7
- Uncompute temporary and altered input state when the surrounding algorithm requires clean qubits. section 6.7
Testing a single-bit implementation
For every classical input x, calculate f(x), prepare |x⟩|0⟩, and apply the reversible operation. The expected state is |x⟩|f(x)⟩. A Qiskit statevector test can flip the output according to the expected classical value and undo input preparation; a final |00⟩ state confirms both the output and preserved input are correct. section 6.3 section 6.3.1
Classical functions also define quantum oracles. An oracle is a unitary operation that implements a problem-specific function while leaving a quantum algorithm generic. In Grover search, a Boolean function marks the desired inputs: the task is to find x₀ such that f(x₀)=1. Marking and phase oracles encode these function values in different quantum forms. section 7.1 section 7.4
The reversible extension is its own inverse: applying F(x,y)=(x,y⊕f(x)) twice restores (x,y), since f(x)⊕f(x)=0. Independent constraint checks can therefore sometimes be uncomputed by rerunning the same code. When one computed function depends on another’s result, uncomputation must instead reverse the computation order. section 8.2.2
