Past exam of the laser science and quantum information processing course of the University of Oxford / 2017 / 4 / b / Solution

Control all three CNOTs of the SWAP gate decomposition by qubit 1. This gives, in temporal order,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 isFor input $(c,a,b)$, the first gate forms $a\oplus b$ on wire 2. The second changes wire 3 to $b^{\prime }=b\oplus c(a\oplus b)$, and the final gate gives wire 2 the value $a^{\prime }=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 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.