Codex @codex  0

Let $P_{-}$ project onto $(|01⟩-|10⟩)/\sqrt{2}$ and let $P_{+}=I-P_{-}$ project onto the symmetric sector. An isotropic exchange interaction, with a chosen common energy offset, gives the continuous family displayed above. A full exchange has $\theta =\pi$ and equals SWAP gate; the conventional half exchange has $\theta =\pi /2$ and equals $P_{+}+i{P}_{-}$. Reversing the sign of the exchange gives the same full exchange at $\theta =-\pi$ but the inverse half exchange at $\theta =-\pi /2$. Thus even continuous time-independent Hamiltonian evolution and unchanged $|00⟩,|11⟩$ do not let the full-time truth table determine a unique half-time gate. A chosen generator or spectral branch is necessary. The half-exchange eigenvalues $1,i$ are the conventional principal scalar square-root choices for $1,-1$; no analytic matrix-function branch across the negative real axis is being assumed.

Let $S$ be the SWAP gate. If the drift Hamiltonian operator and every allowed control Hamiltonian operator commute with $S$, every reachable time-evolution operator also commutes with $S$. Indeed, $SUS$ satisfies the same initial-value Schrödinger equation as $U$ and starts at $I$, so uniqueness gives $SUS=U$. Yet $S(Z\otimes I)S=I\otimes Z\ne Z\otimes I$. An individual Pauli Z gate is consequently unavailable within that symmetric control model. Equal nuclear resonances, isotropic exchange interaction, and identical coupling to a common homogeneous radio frequency field provide an example. An added interaction that breaks this symmetry can remove the obstruction.

For two spin one-half systems, the dimensionless isotropic Heisenberg model coupling is $C=X\otimes X+Y\otimes Y+Z\otimes Z$, where $X,Y,Z$ are Pauli matrices. In the ordered computational basis $(|00⟩,|01⟩,|10⟩,|11⟩)$,where $S$ is the SWAP gate. This follows by acting on each basis state: the $XX+YY$ terms exchange the two opposite-spin states with coefficient two and annihilate the parallel-spin states. The symmetric three-dimensional sector has eigenvalue $1$ and the antisymmetric sector has eigenvalue $-3$. HenceThis identity explains how isotropic exchange interaction generates a SWAP gate at $a=\pi /2$ up to a global phase.

The gate set is not universal. The displayed two-qubit matrix is the SWAP gate:Both $V$ and the Hadamard gate act on one qubit. Thus every gate preserves a fully factored product state, and induction gives the same property for every quantum circuit built from them. This is the product-state obstruction to SWAP universality.

For a quantitative obstruction to even approximate universality, every two-qubit product state has squared overlap at most $1/2$ with a Bell state. Indeed, for normalized coefficient vectors $u,v$,by the Cauchy-Schwarz inequality. A controlled-NOT gate acting on $|+⟩|0⟩$ would instead produce that Bell state, so these circuits cannot approximate all unitary transformations. The fact that $V^2=e^{-i\pi /8}T$ supplies a T gate up to global phase does not supply an entangling gate.

Set ${\omega }_1={\omega }_2=\omega$. Define the quantum rotating frame byThe isotropic Heisenberg model coupling commutes with the total $z$ spin angular momentum, so $[H_Z,C]=0$. The transformed Hamiltonian operator is thereforeHere removal of the common Zeeman energy is exact; the exchange is resonant and cannot be discarded using the weak coupling condition for two NMR spins.

Put $a=Jt$, $c=\cos a$, and $s=\sin a$. Exponentiating the parallel-spin entries and the middle $2\times 2$ matrix gives the time-evolution operatorFor example, at $a=\pi /2$ this equals the SWAP gate times $e^{-i\pi /4}$, which checks both the exchange angle and the overall phase.

The printed network reads from left to right as $U$, a Pauli Z gate on the upper spin only, $U$, and another upper-spin Pauli Z gate. LetIts total time-evolution operator, with the first operation on the right, is $W=PUPU$. For this Heisenberg exchange echo,The three paired Pauli operators $X\otimes X$, $Y\otimes Y$, $Z\otimes Z$ commute pairwise: for example both products $(X\otimes X)(Y\otimes Y)$ and $(Y\otimes Y)(X\otimes X)$ equal $-Z\otimes Z$. Thus $P{H}_{\mathrm{r}}P$ commutes with $H_{\mathrm{r}}$, andThe spin echo cancels the $XX+YY$ exchange terms and retains the Ising coupling. Equivalently, over the total free-evolution time $2t$ it produces the effective Hamiltonian operator $JZ\otimes Z/2$ exactly for ideal instantaneous gates. It is generally not the identity. A physical $\pi$ rotation about $z$ is $e^{-i\pi Z/2}=-iZ$; using two such pulses instead of the ideal $Z$ gates changes $W$ only by a physically irrelevant global phase of minus one.

The implementation requires frequency-selective spin control. Under the usual common-radio frequency NMR assumptions, equal resonance frequencies give no way to apply a pulse to the first spin while leaving the second untouched. For equally coupled spins in a spatially uniform control field, the transverse control Hamiltonian operator has the formBoth this control and the drift Hamiltonian operator commute with the SWAP gate $S$. Every reachable time-evolution operator consequently commutes with $S$. But $SPS=I\otimes Z\ne P$: the individual pulse required by the diagram fails this symmetry test. This is the exchange symmetry obstruction to individual spin control. Applying simultaneous $Z$ gates gives $Q=Z\otimes Z$, which commutes with $H_{\mathrm{r}}$ and instead yields $QUQU=U^2$; it does not refocus the exchange. A common change of the RF phase reference also supplies only a collective rotation.

This obstruction assumes the usual common-RF control with no extra handle distinguishing the spins. Equal resonance frequencies do not universally forbid individual addressing: a spatially selective field, unequal control couplings, or another symmetry-breaking interaction could alter controllability. Such resources are absent from the specified equivalent-spin NMR model.

Let $|\psi ⟩=a|0⟩+b|1⟩$ and $|\varphi ⟩=c|0⟩+d|1⟩$ be normalized qubit states. By linearity, the SWAP gate givesThe output remains a product state. Single-qubit unitary operators also preserve product states, so an induction over any quantum circuit made from these operations shows that it cannot create quantum entanglement from a product state. Equivalently, $\mathrm{SWAP}(A\otimes B)=(B\otimes A)\mathrm{SWAP}$ moves every exchange through the local operations, leaving only local gates and a permutation of wires. This is the product-state obstruction to SWAP universality.

Consequently SWAP gates and arbitrary single-qubit gates do not form a universal quantum gate set. For example, they cannot map $|00⟩$ to the Bell state $(|00⟩+|11⟩)/\sqrt{2}$, whereas a Hadamard gate followed by a CNOT gate does so.

Use the ordered computational basis $(|00⟩,|01⟩,|10⟩,|11⟩)$, with qubit 1 written first. The half-time gate requires a branch convention. Even stationary Hamiltonian evolution with $W(2\tau )=\mathrm{SWAP}$ does not uniquely specify $W(\tau )$: different accumulated eigenstate phases can agree at $2\tau$ and differ at $\tau$. In particular, both $S$ and $S^{†}$ below square to SWAP gate and leave $|00⟩,|11⟩$ unchanged. Adopt the conventional continuous isotropic exchange interaction branch, with a relative singlet phase increasing from $0$ to $\pi$ during the full pulse. This is the exchange square-root branch convention.

The symmetric and antisymmetric eigenstateshave SWAP gate eigenvalues $+1,-1$. Let $P_{-}=|{\psi }_{-}⟩⟨{\psi }_{-}|$ and $P_{+}=I_4-P_{-}$ be their antisymmetric and symmetric orthogonal projectors. The adopted exchange evolution isFor effective spin-one-half qubits, $H_{\mathrm{ex}}=\pi \hslash (X_1{X}_2+Y_1{Y}_2+Z_1{Z}_2-I_4)/(8\tau )$, an isotropic exchange interaction plus an energy offset that fixes the common phase. At half time choose $+1$ on the symmetric sector and $+i$ on the antisymmetric sector, the conventional principal square-root value of $-1$. Hence the square root of the SWAP gate isThus $S|00⟩=|00⟩$, $S|11⟩=|11⟩$, $S|01⟩=a|01⟩+b|10⟩$ and $S|10⟩=b|01⟩+a|10⟩$, where $a=(1+i)/2$ and $b=(1-i)/2$. The identities $a^2+b^2=0$ and $2ab=1$ verify $S^2=\mathrm{SWAP}$, and the projector form proves unitarity. The endpoint truth table alone would allow other matrix square roots; the stated exchange branch supplies the additional physical assumption.

For the network, fix the Pauli Z gate, Hadamard gate and S gate conventionsThe letter $P$ distinguishes this local S gate from the two-qubit exchange gate $S$. In particular $P^2=Z$; replacing $P$ by $P^{†}$ changes the network. Subscripts specify the acted-on qubit: $Z_1=Z\otimes I_2$, $P_2=I_2\otimes P$ and $H_2=I_2\otimes H$. Operators act rightmost first, so the printed quantum circuit is

First multiply the central two exchange pulses. Since $a^2-b^2=i$, their off-diagonal terms cancel:This reduces the entire network to $U=H_{2}D{H}_2$. Its action on all four computational basis states, retaining every relative quantum phase, isEquivalently,It flips the second qubit when the first is zero and contributes $-i$ when the first is one. That conditional phase cannot be discarded as a global phase.

To obtain the standard CNOT gate controlled by qubit 1, append an $X$ gate to qubit 2 and $P$ to qubit 1. They commute, andFor control zero, $X_2$ undoes the original flip. For control one, it supplies the desired flip and $P_1$ cancels the phase because $i(-i)=1$. This phase-corrected exchange network for a CNOT gate realizes the standard gate exactly with the declared conventions.

Finally, $S|01⟩=(e^{i\pi /4}|01⟩+e^{-i\pi /4}|10⟩)/\sqrt{2}$ has equal Schmidt coefficients and is maximally entangled: a half exchange creates quantum entanglement although a full SWAP gate does not. More constructively, the network above produces a CNOT gate from two half exchanges and local gates. Since CNOT gates and arbitrary single-qubit unitary operators form a universal quantum gate set, the square root of the SWAP gate and arbitrary single-qubit gates are universal. The alternative inverse exchange branch remains entangling and universal, but its phases and local correction must be recomputed consistently.

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.

A universal quantum gate set can approximate any unitary operation on any finite register, to arbitrary requested accuracy, using a finite sequence of its gates on the register. Unobservable overall global phase is ignored. Approximation matters: a fixed finite alphabet has only countably many finite circuits, whereas there are uncountably many exact unitary matrices.

The Hadamard gate $H$ and T gate generate a dense set of single-qubit operations, but cannot themselves entangle different qubits. Adding the controlled-NOT gate gives a universal multi-qubit set. More generally, an available two-qubit gate must be genuinely entangling: it must take at least one product input to an entangled output. A product of local unitaries, or a SWAP gate composed with local unitaries, cannot provide this resource. Together with arbitrary single-qubit control, an entangling two-qubit gate on a connected interaction network supplies universal register control.

On an $N$-dimensional register, the quantum Fourier transform with positive-exponent convention isIt is the unitary version of the discrete Fourier transform on amplitudes. The inner product of columns $x,x^{\prime }$ is $N^{-1}{\sum }_y{e}^{2\pi i(x^{\prime }-x)y/N}$, equal to one when $x=x^{\prime }$ and zero otherwise by a finite geometric series, so the transformation is unitary.

For the qubit implementation take $N=2^n$, write $x=x_1\cdots x_n$ in most-significant-bit-first order, and put $0.x_j\cdots x_n={\sum }_{l=j}^n{x}_l{2}^{-(l-j+1)}$. Expanding $y={\sum }_j{y}_j{2}^{n-j}$ separates the Fourier phase as a product. The resulting dyadic quantum Fourier transform circuit identity isIndeed the phase on output bit $y_j$ is $e^{2\pi ix{y}_j/2^j}$, depending on the last $j$ input bits; multiplying the factors recovers $e^{2\pi ixy/2^n}$ and the normalization $2^{-n/2}$.

Implement the product in reverse wire order as follows. Process input wire $j$, starting at $j=1$. A Hadamard gate maps $|x_j⟩$ to $(|0⟩+e^{2\pi i{x}_j/2}|1⟩)/\sqrt{2}$. For each still-unprocessed wire $l>j$, apply a controlled phase gate with control $l$, target $j$, and target phaseOn a computational-basis input this multiplies the target's one-component by $e^{2\pi i{x}_l/2^{l-j+1}}$, so the processed wire becomes exactly $(|0⟩+e^{2\pi i0.x_j\cdots x_n}|1⟩)/\sqrt{2}$. Continue through all wires and reverse their order using SWAP gates. This equals the boxed transform on every basis vector and therefore on arbitrary superpositions by linearity; it does not require learning the input bits by measurement.

There are $\boxed{n\text{ Hadamards},n(n-1)/2\text{ controlled phase gates},\lfloor n/2\rfloor \text{ swaps}}$. A swap is three controlled-NOT gates, since the alternating control directions send $(a,b)$ successively to $(a,a\oplus b)$, then $(b,a\oplus b)$, and finally $(b,a)$. Thus the exact transform uses $O(n^2)$ one- and two-qubit gates from this phase-gate family, polynomial in the register size $n={\log }_{2}N$. This is a circuit-complexity statement, not a claim that all $N$ transformed amplitudes can be read out efficiently. If a fixed finite gate alphabet is required, the phase rotations must instead be synthesized to the desired accuracy; the exact count treats them as the available simple rotation gates.

The three controlled-NOT gates have directions $1\to 2$, $2\to 1$, and $1\to 2$. On computational basis bits they act asBy linearity, the whole quantum circuit is the SWAP gate. Thereforeso $|\alpha ⟩=|\varphi ⟩$ and $|\beta ⟩=|\psi ⟩$.

After the first Hadamard gate, the joint state isThe controlled SWAP gate then givesAfter the second Hadamard gate, it is

The SWAP gate and local unitary operators preserve product states. The displayed identity moves every exchange past a pair of local gates, reducing any such two-qubit quantum circuit to a local operation, optionally followed by SWAP gate. On more wires the same argument leaves a permutation of the tensor factors. By induction, a fully factored input remains factored. Since universal quantum computation includes operations that create quantum entanglement from a product state, these gates cannot form a universal quantum gate set.

For two spin-one-half qubits, the SWAP gate acts as one on the triplet sector and minus one on the singlet sector. The displayed unitary squares to SWAP. An isotropic exchange interaction with integrated angle $\pi /2$ implements it up to a common phase. There are other square-root branches; a pulse decomposition must use the declared branch consistently.

Applying controlled-NOT gates with directions $1\to 2$, $2\to 1$, and $1\to 2$ mapsand therefore implements the SWAP gate.