Classical Logic on a Quantum Computer

Here is a plot twist worthy of a good novel: the whole synthesis module of this course — embedding irreversible Boolean functions into bijections, compiling them down to Toffoli and CNOT networks, counting ancillas — was secretly quantum-compiler training. When a quantum algorithm needs to evaluate a classical function f (and almost all of them do: Grover needs "is this the marked item?", Shor needs modular arithmetic), it cannot call a classical subroutine — every step must be a unitary, and the previous lesson showed unitaries cannot be irreversible. The escape route is exactly the one you already know: make f reversible first. This lesson shows how any Boolean function rides into the quantum world on the back of that trick.

The standard oracle

Let f : \{0,1\}^n \to \{0,1\}^m be any Boolean function. The standard oracle for f is the unitary U_f acting on an n-qubit input register and an m-qubit answer register by

U_f\,|x\rangle|y\rangle \;=\; |x\rangle\,|y \oplus f(x)\rangle.

Look closely — you have met this map before. It is precisely the reversible XOR embedding from the gates module: keep the input, XOR the answer into a second register. On bit-strings it is a bijection (a permutation of the 2^{n+m} basis states), so as a matrix it is a permutation matrix, so it is unitary. Two immediate properties, both inherited from the classical story:

the input survives: |x\rangle comes out unchanged, which is what makes the map invertible even when f destroys information;
U_f is its own inverse: U_f\,U_f\,|x\rangle|y\rangle = |x\rangle|y \oplus f(x) \oplus f(x)\rangle = |x\rangle|y\rangle, because XOR-ing the same value twice cancels. Running the oracle again uncomputes it.

Building U_f: your synthesis toolbox, verbatim

An oracle is not an oracle in the mystical sense — someone has to build it out of gates. And the recipe is the one you already own. Take any classical circuit for f (AND, OR, NOT gates), replace each irreversible gate by its reversible embedding — AND becomes a Toffoli writing into a fresh ancilla, XOR and fan-out become CNOTs, NOT stays NOT — and you have a reversible network computing x \mapsto (x,\, f(x),\, \text{junk}). Every gate in that network is a permutation matrix, so the whole network is one big unitary. That is U_f, gate for gate. (The junk register is a real problem — it is the subject of the next lesson — but the construction itself is pure reversible synthesis.)

The Toffoli is the load-bearing beam of this bridge. It is classically universal for reversible logic — every Boolean function can be built from it — and it is a legal quantum gate. One gate with a foot on each shore: whatever classical logic can express, the Toffoli carries into the quantum circuit model unchanged. With \{\text{Toffoli}, \text{CNOT}, X\} you can build U_f for every f.

Worked example: f(x_1, x_2) = x_1 \wedge x_2

For AND, the synthesis is a one-liner: a single Toffoli with the two inputs as controls and the answer qubit as target implements

U_f\,|x_1 x_2\rangle|y\rangle = |x_1 x_2\rangle\,|y \oplus (x_1 \wedge x_2)\rangle.

Superposed trace. Now prepare the input register in the equal superposition of all four inputs (two Hadamards on |00\rangle) with the ancilla at |0\rangle, and apply the same single Toffoli. Unitaries are linear, so it acts on each branch simultaneously:

\tfrac{1}{2}\big(|00\rangle + |01\rangle + |10\rangle + |11\rangle\big)|0\rangle \;\xrightarrow{\;U_f\;}\; \tfrac{1}{2}\big(|00\rangle|0\rangle + |01\rangle|0\rangle + |10\rangle|0\rangle + |11\rangle|1\rangle\big).

One application of the oracle, and the output state contains f(x) evaluated against all four inputs — for n input qubits, all 2^n of them. This is quantum parallelism.

The honest caveat

One paragraph of cold water, because this is where popular accounts go off the rails. The state above encodes all 2^n values of f, but a measurement returns one of the branches, uniformly at random: a single pair (x, f(x)) — something a classical computer produces with one evaluation and a random-number generator. Quantum parallelism pays only when you don't measure straight away, and instead use interference to make the branches vote — cancelling amplitudes for wrong answers, reinforcing them for right ones, as in the oracle algorithms you have seen. The oracle is the engine of every quantum speed-up, but it is the interference afterwards, not the parallel evaluation itself, that does the magic.

for any Boolean f : \{0,1\}^n \to \{0,1\}^m, the unitary U_f|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle — the reversible XOR embedding, run as a quantum gate;
it is a permutation matrix, self-inverse (U_f^2 = I), and leaves the input register unchanged;
it is built by reversible synthesis: \{\text{Toffoli}, \text{CNOT}, X\} suffices for every f;
applied to a superposition it evaluates f on all 2^n inputs in one application — but measurement yields only one random (x, f(x)); the advantage comes from interference afterwards.

A tempting "simpler" oracle would be |x\rangle|y\rangle \mapsto |x\rangle|f(x)\rangle — overwrite the answer register. But overwriting is erasure: the old value of y vanishes, two different inputs |x\rangle|0\rangle and |x\rangle|1\rangle collide on the same output, and the map has a repeated column — not a unitary. The XOR is the cheapest bijection that carries f's answer: it costs nothing when y = 0 (then y \oplus f(x) = f(x), the value you wanted) and it keeps every state recoverable. There is a delightful bonus, too: set the answer qubit to \tfrac{1}{\sqrt2}(|0\rangle - |1\rangle) and the XOR turns into a phase, (-1)^{f(x)}, on the input register — the "phase kickback" that powers Deutsch–Jozsa and Grover. The humble reversible-computing XOR trick, promoted to a quantum superpower.

The sentence "a quantum computer evaluates f on all 2^n inputs at once" is true — and the sentence people hear, "so it can hand you all 2^n answers", is false. The circuit model gives you one measurement at the end, and it samples one branch. If quantum computers really delivered all values of f, they could brute-force every problem in exponential time instantly — and they cannot. Every real algorithm must funnel that parallel state through interference until the answer it wants dominates the amplitudes. When you read "tries all possibilities simultaneously" in a news story, the missing half of the sentence is: and then throws almost all of that work away unless interference is arranged with extreme care.