Algorithms such as Deutsch–Jozsa and Grover often begin with an oracle . But a Boolean function can erase information: AND maps four inputs to one output bit. How can such a function be part of a unitary circuit? The answer is to keep the input and XOR the result into a separate target. A further step, uncomputation, removes temporary results without measuring them.
Let be a deterministic Boolean function. We use computational-basis strings, XOR , and the gates , controlled-NOT and Toffoli. The Toffoli gate maps to , leaving both control bits unchanged. These gates permute computational-basis states and are therefore unitary.
Why the oracle is reversible
Definition 9.3.1
(Bit oracle)
For a Boolean function , the bit oracle is the operator on input qubits and one target qubit defined on computational-basis states by
For any , even a many-to-one function, applying (1) twice returns every basis state to itself: . It is a permutation and hence unitary. It does not map to alone. If two distinct inputs have the same output, that proposed map would send orthogonal input states to the same state, even if the output were padded back to qubits, and could not be unitary.
Proposition 9.3.2
(The bit oracle is unitary and kicks back a phase)
For every Boolean function , is unitary with . With ,
Proof
(A permutation, and an eigenvector of the target flip)
The map is its own inverse, hence a permutation of basis states, so is a permutation matrix and unitary. For (2), expand . If this is ; if it is .
By linearity the phase applies to each branch of a superposition. This is phase kickback, not a measurement of all values of .
Constructing the oracle from a Boolean circuit
Suppose a classical acyclic circuit for has AND or NOT gates in topological order and one designated output wire. Inputs and earlier gate outputs may be used as controls repeatedly. Reserve one clean work bit per gate, initially zero. To write an AND of two distinct earlier wires into its fresh work bit, use Toffoli. If its two inputs are the same wire, use controlled-NOT instead, since . To write NOT into a fresh work bit, use controlled-NOT from followed by on the work bit. In both cases the controls are unchanged and the new bit is the desired gate value.
Theorem 9.3.3
(Oracle from a classical circuit with clean workspace)
Let a classical acyclic circuit with AND or NOT gates compute . Then there is a circuit of at most gates from and work bits such that, for every ,
so it realizes whenever the work bits start clean, and returns them clean.
Proof
(Compute, copy, uncompute)
After all gates are evaluated, a reversible circuit has the action
where stores all gate values; the designated output is one of these values or an input wire. The same circuit acts linearly on superpositions. The circuit acts only on the input and work registers; the separate target is a spectator during and . Now use a controlled-NOT from the output wire to , and run by reversing the gate order. This gives, for every basis input ,
The target is not touched by , so its copied output remains. Equation (4) extends by linearity to arbitrary superpositions, and realizes (1) on the clean-workspace subspace. The uncomputation is not erasure by measurement: it is the inverse of a known reversible computation.
Each classical AND or NOT gate uses at most two of the listed reversible gates to compute its value. Thus the construction uses at most gates for , at most for , one output controlled-NOT, and clean work bits: at most listed gates.
This is an upper bound in a gate set that treats Toffoli as one gate; a different elementary quantum gate set requires its own decomposition. It also assumes the classical circuit is supplied. The mere existence of as a permutation does not make an arbitrary a cheap oracle.
Proof X-ray
Where each step of compute, copy, uncompute is used
Running immediately after would remove both the workspace and the computed answer, because . The non-obvious move is the single controlled-NOT in the middle: it acts on the target, which neither nor touches, so it records on a register that survives the uncompute. Two hypotheses are used. First, the work register starts at , so that produces exactly and undoes it. Second, every gate of leaves its controls unchanged, so the output wire still holds when the copy happens. Linearity then extends the basis-state computation to superpositions. If the work register is not clean, (3) fails, as the counterexample below shows.
Worked AND example
Worked example 9.3.4
(AND with one work bit)
For , one work bit suffices. With , use Toffoli on , controlled-NOT from to , then Toffoli on again. The transformation is
For the target flips; for the other three basis inputs it does not. If , the induced phase map is diagonal with a minus sign only on , and the work bit returns to . That sign is observable as a relative phase when the input contains another branch; on alone it is global.
Worked example 9.3.5
(NAND with two work bits)
Take with gates. Write into by Toffoli on . Then write NOT into : controlled-NOT from to , followed by on . Copy into by controlled-NOT, then run the three gates in reverse order. For : , , so is unchanged, and . For : , , so flips, and . Uncomputation restores in both cases. The circuit uses gates, within the bound .
Worked example 9.3.6
(An edge case: both AND inputs are the same wire)
For , the Toffoli rule would need two distinct controls, so use controlled-NOT instead. Write into the work bit by controlled-NOT from to , copy into by controlled-NOT, and undo the first step. Then , which is with a clean work bit.
Common mistakes
Counterexample mode
A dirty work register breaks the oracle
Plausible claim: the compute-copy-uncompute circuit realizes whatever the work bit holds. For the AND circuit, take and input (that is, , ). The first Toffoli leaves ; the controlled-NOT from to makes ; the second Toffoli returns . The output is , although requires . The dirty work bit returns to one, but its value has incorrectly influenced the target. The guarantee (4) requires the work register to start at .
Common mistake
(Discarding the workspace is not uncomputing it)
Apply controlled-NOT to ; the result is . Tracing out the second qubit leaves on the first, not . Measuring the first in the basis now yields only with probability , instead of one. This simple copy is analogous to input-dependent garbage : discarding an entangled work register can remove coherence and change a later interference calculation.
Common mistake
(Reusing a wire as a control does not clone a state)
Using one wire as a control multiple times does not clone an arbitrary unknown quantum state. Controlled-NOT copies a computational-basis bit into a clean target, but on a superposition it can entangle the registers, as the previous example shows.
Practice with solutions
Quick check
(Why is unitary even when ?)
Look at what happens to the input register.
Solution · Answer
The pair retains , and the XOR is its own inverse; (1) is a basis permutation.
Quick check
(For the AND example, what happens to ?)
Track the work bit and the target through the three gates.
Solution · Answer
The target flips to , giving : the first Toffoli sets , the controlled-NOT sets , and the second Toffoli resets .
Quick check
(Why must the gates of be applied in reverse order, even though , controlled-NOT and Toffoli are each self-inverse?)
Recall .
Solution · Answer
For a product of gates, the inverse reverses the order of the factors; self-inversion of each factor does not make the factors commute.
Quick check
(Does the gate bound imply that every Boolean function has a polynomial-size oracle in ?)
Ask what is.
Solution · Answer
No. The bound is conditional on a supplied circuit of size ; itself may be exponential in .