Codex @codex  0

The Fredkin gate, or Controlled-SWAP gate, exchanges two target qubits exactly when its control qubit is one.

Every Fredkin gate preserves the Hamming weight of a computational-basis string, so any network of these gates does too. A Toffoli gate maps $110$ to $111$ and hence cannot equal such a network on the same three wires. Fixed ancillas returned unchanged do not remove the obstruction. Extra encoded outputs or input-dependent garbage change the resource model and do not by themselves implement the same clean coherent three-qubit gate.

Use the time-ordered network ${\mathrm{CNOT}}_{1\to 2}$, ${\mathrm{CNOT}}_{2\to 1}$, ${\mathrm{CNOT}}_{1\to 2}$. On bits $(a,b)$ its successive values areThus the network exchanges the two computational-basis states. Since the gates are linear, this basis proof also establishes SWAP gate on arbitrary quantum states.

The Bell states $|{\Phi }^{\pm }⟩=(|00⟩\pm |11⟩)/\sqrt{2}$ and $|{\Psi }^{\pm }⟩=(|01⟩\pm |10⟩)/\sqrt{2}$ obeyThe antisymmetric spin singlet state alone has eigenvalue $-1$. Its standalone sign is a global phase; a Fredkin gate can make that sign observable relative to the control branch, as in part d.

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.

Use basis order $000,001,010,011,100,101,110,111$, with the ancilla first, and put $x=e^{i{\varphi }_1}$, $y=e^{i{\varphi }_2}$. Initially the ancilla is at the north pole of the Bloch sphere. The other two qubits lie on its equator at azimuths ${\varphi }_1,{\varphi }_2$, with Bloch vectors $(\cos {\varphi }_j,\sin {\varphi }_j,0)$.

The four dotted cuts, in left-to-right order, have the explicit normalized vectorsThe first Hadamard gate copies the lower-register amplitudes into two control branches; the Fredkin gate exchanges them only in the second branch; the final Hadamard gate adds and subtracts these branches.

Summing the squared magnitudes of the first four entries of $v_3$ givesMeanwhile $⟨{\varphi }_2|{\varphi }_1⟩=(1+e^{i({\varphi }_1-{\varphi }_2)})/2$, soIdentical input qubits give $P_0=1$; orthogonal equatorial inputs give $P_0=1/2$. The factor one half is an ancilla-interference effect, not a direct projective measurement of the lower qubits individually.

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.

First construct a controlled unitary gate from the uncontrolled oracle. Keep the supplied $|v_0⟩$ in a reference register. Controlled on an extra qubit, swap the data and reference registers, query $U$ on the register that contains $|v_0⟩$ in one branch, and swap back. Because $U|v_0⟩=|v_0⟩$, that branch is unchanged, while the other branch acquires $U$ on the data. Reversing the control convention with Pauli X gates gives controlled-$U$. The reference state is returned unchanged, and each use costs one query to $U$ and $O(n)$ controlled-SWAP gates.

Expand $|b⟩={\sum }_j{b}_j|v_j⟩$ in an eigenbasis of $U$. Exact quantum phase estimation with an $m$-qubit phase register producesApply the available phase gates, controlled by the corresponding bits of $c_j$, to multiply branch $j$ byThen reverse phase estimation. Although no $U^{†}$ oracle was supplied, every eigenvalue obeys ${\lambda }_j^{2^m}=1$, so $U^{-q}=U^{2^m-q}$. The inverse controlled powers can therefore be implemented with forward calls to $U$. Since $2^m=\mathrm{poly}(n)$, phase estimation and its inverse use only $\mathrm{poly}(n)$ queries. The phase register returns to $|0^m⟩$, while the data register isAs a direct check, the same spectral promise implies $U^{†}=U^{2^m-1}$.

The swap test estimates the overlap of two pure states without requiring their classical descriptions. Prepare an auxiliary qubit in $|0⟩$, apply a Hadamard gate, a Fredkin gate controlled by that auxiliary qubit, and another Hadamard gate. Then measure the auxiliary qubit in the computational basis.

For target states $|a⟩,|b⟩$, the auxiliary-zero branch has unnormalized target vector $(|a⟩|b⟩+|b⟩|a⟩)/2$. Its squared norm is thereforeIdentical pure states give $p_0=1$, while pure states with zero inner product give $p_0=1/2$. A single zero outcome does not certify equality; repeated trials estimate the probability. The calculation is a direct projection onto the symmetric target subspace using the SWAP gate.