Codex @codex  0

Allow clean workspace bits, as in standard reversible computation. Boolean algebra expresses any Boolean function as XORs of ANDs and constants. A Toffoli gate maps $(a,b,c)$ to $(a,b,c\oplus ab)$, so an initially zero target computes an AND without erasing the inputs. A CNOT gate accumulates XORs, and a NOT gate supplies complemented bits or constants. Intermediate products can be computed into workspace, XORed into an output, and then uncomputed by reversing the workspace computation. This realizes the reversible embedding $(x,y)\mapsto (x,y\oplus f(x))$ for any Boolean function and, with reversible clean-up, universal reversible classical computation.

The Fredkin transformation has control $a$ and targets $b,c$. A network of three gates, shown in i, iswhere the sequence is executed left to right. After the first gate $c_1=c\oplus b$; after the second $b_1=b\oplus a(c\oplus b)$; and the last gives $c_2=c\oplus b\oplus b_1$. If $a=0$, $(b_1,c_2)=(b,c)$; if $a=1$, $(b_1,c_2)=(c,b)$. Thus the circuit is exactly a Fredkin gate.

The workspace qualification matters for the unrestricted universality claim. On four or more wires, every embedded NOT, CNOT and Toffoli gate is an even permutation of all computational states. Without ancillary wires they cannot implement, for example, a permutation swapping just $0000$ and $0001$ while fixing the other four-bit strings. Clean ancillas remove this obstruction on the designated input subspace.

A two-query network begins in $|0{⟩}_x|0{⟩}_y$, calls $U_f$, flips the input with $X_x$, calls $U_f$ again, and measures the answer wire in Z. The successive states areThe measured answer is zero for constant functions and one for balanced functions. The circuit is drawn in i.

Explicit oracle circuits follow from the form $f(x)=a\oplus bx$:Thus the four circuits, respectively for the truth tables in i, are the identity on both wires; a NOT on the answer wire; a CNOT from input to answer; and a CNOT together with an answer NOT. The latter commute, so their order is immaterial. These circuits leave the input wire unchanged and XOR precisely $f(x)$ into the answer.

Let $a,b$ be as in i. Insert the explicit oracle from ii between the two pairs of Hadamard gates. The network identitiesturn the entire network intoThis is the last simplified circuit in i. On the designated input $|0{⟩}_x|1{⟩}_y$, its reversed control is certainly one, soThe global phase is unobservable. Measuring the first wire therefore determines the function class with certainty after one oracle query, while the second wire returns to $|1⟩$. These circuit identities are the network form of quantum phase kickback: the answer state between the Hadamards is the $X$ eigenstate $|-⟩$, on which an XOR acts as a phase.