A CNOT gate cannot be constructed only with a SQRT SWAP gate, arguing within an ancilla system

Question

When I looked at the construction of a $\mathsf{CNOT}$ gate out of a $\sqrt{\mathsf{SWAP}}$ (https://arxiv.org/abs/quant-ph/0209035), I could see that $\sigma_X$ and and $\sigma_Z$ gates were used. It made sense for me, that additional 1-qubit gates are needed to do this, but I could not think of a simple argument explaining this fact. When the system starts in the state $|00\rangle$, it is obvious, because the $\sqrt{\mathsf{SWAP}}$ gate acts here equivalent the identity. But what if I can choose the starting state, for example $|0101\rangle$ and also allow an ancilla system.

Here my thoughts, which were not very helpful for me:

I realized I can use the states $|01\rangle$ and $|10\rangle$ as a mapping, so that the $\sqrt{\mathsf{SWAP}}$ gate acts similar to a $H$ gate.

$|0_L\rangle \mapsto |10\rangle$

$|1_L\rangle \mapsto |01\rangle$

since

$ |10\rangle \xrightarrow{\sqrt{\mathsf{SWAP}}} \frac12\big[(1-i)|01\rangle + (1+i)|10\rangle\big] \equiv |01\rangle + i |10\rangle $ $ |01\rangle \xrightarrow{\sqrt{\mathsf{SWAP}}} \frac12\big[(1+i)|01\rangle + (1-i)|10\rangle\big] \equiv i |01\rangle + |10\rangle $

I thought about proofing that in a different base, the $\sqrt{\mathsf{SWAP}}$ is isomorphic in behavior to the $H$ gate (which I am not even sure), but this argument brought me nowhere, and seemed too complicated for such a simple question. Especially, allowing an ancilla system made arguing harder for me.

Maybe someone has some simple idea of reasoning, which can be applied to a bigger set of gate construction problems.

Answer 1

The reason you need an additional gate to make a $\text{CNOT}$ is that swap-style operations preserve the number of 1 bits, but $\text{CNOT}$s don't.

Swap-style operations may phase the no-1s state $|00\rangle$ and the all-1s state $|11\rangle$, but they won't mix those states with other states. The only states they mix between are the two single-1 states: $|01\rangle$ and $|10\rangle$. By contrast, a $\text{CNOT}$ can change the number of 1 bits: $\text{CNOT} \cdot|10\rangle = |11\rangle$.

The $\sqrt{\text{SWAP}}$ gate, and the $\text{iSwap}$ gate, both have this preserve-number-of-1s property. Without some other gate, you just won't be able to mix or transition between parts of the superposition that have different numbers of bits set. So you just won't be able to perform a $\text{CNOT}$.

It's true that, when you can't implement arbitrary unitaries, it may be possible to switch to a different information encoding and perform universal quantum computation within the encoding. I'm not sure of the $\sqrt{\text{SWAP}}$ gate can do that or not. The $\text{iSwap}$ definitely can't, because it's in the Clifford group.