= Solution
Control all three CNOTs of the <SWAP gate> decomposition by <qubit> 1. This gives, in temporal order,
$$
T_{1,2\to3},\qquad T_{1,3\to2},\qquad T_{1,2\to3}.
$$
When the first <qubit> is 0, all three <Toffoli gates> do nothing. When it is 1, the three lower-wire CNOTs implement <SWAP gate>. The middle panel of the original diagram shows this controlled network.
Only one <Toffoli gate> is actually needed. An equivalent circuit is
$$
\boxed{\operatorname{CNOT}_{3\to2},\qquad T_{1,2\to3},\qquad\operatorname{CNOT}_{3\to2}.}
$$
For input $(c,a,b)$, the first gate forms $a\oplus b$ on wire 2. The second changes wire 3 to $b'=b\oplus c(a\oplus b)$, and the final gate gives wire 2 the value $a'=a\oplus c(a\oplus b)$. For $c=0$ this is $(a,b)$; for $c=1$ it is $(b,a)$. The last panel displays the circuit.
The <Hamming-weight obstruction to Fredkin-only Toffoli synthesis> means that a network of <Fredkin gates> alone cannot implement a <Toffoli gate> on the same three wires: each <Fredkin gate> preserves <Computational basis>[computational-basis] <Hamming weight>, whereas <Toffoli gate> maps $110$ to $111$. The same obstruction holds if fixed ancillary bits must be returned unchanged. Conservative classical computation can use extra encoded wires and input-dependent garbage, but that is not an ancilla-free coherent three-qubit <Toffoli gate> operation. The resources and output encoding would need to be specified before making a different universality claim.
Back to article page
