# Implement Fredkin gate with square root of swap

I would like to implement a Fredkin gate based on square root of swap and one-qubit gates. In particular, I was hoping to find the exact gate named "?" in this circuit:

In addition, I want to avoid using C-SQSWAP. Otherwise, the solution would be trivial.

Any ideas?

This is a square root of swap circuit:

You can get a CNOT operation by doing single-qubit rotations between two sqrt swaps. Here's the circuit:

There are standard decompositions of the Fredkin gate into the Toffoli gate and CNOTs, and standard decompositions of the Toffoli gate into CNOTs and single-qubit operations. For example, here is a Fredkin decomposition used by Cirq that only uses CNOTs between adjacent qubits:

Replace all the CNOTs with the CNOT decomposition and voila:

Of course, you would try to cancel as many of the single qubit operations as possible.

Are there better decompositions? Almost definitely. But this is one that's easy to find.

• Two things. Firstly, SUPER-thanks for creating Quirk. Secondly, do you know of a decomposition of the CNOT into only SQSWAPs and Z, S & T gates ? – Alex Mar 26 at 18:22
• I don't think that's possible. All those operations preserve total number of set bits, but CNOT doesn't. – Craig Gidney Mar 26 at 20:27
• Actually, they don't commute, so maybe you can escape the space. – Craig Gidney Mar 27 at 3:34

For other readers who, like me, would otherwise have to go and check this, the Fredkin gate is the same thing as controlled-swap.

Some insight that you can get into the construction comes by focussing only on the elements $$\{|01\rangle,|10\rangle\}$$ on the two target qubits. The square root of swap looks like $$e^{i\pi/4}\left(\begin{array}{cc} 1 & i \\ i & 1 \end{array}\right)/\sqrt{2}$$ on those two elements (at least, that's the definition that I'm taking). Let's all this $$U$$. This reminds me of the beam splitter matrix in the Mach-Zehnder interferometer, which inspired the following construction. We have that $$UU=X\qquad UZUZ=\mathbb{I}.$$ So, what we want is a sequence of V, sqrt-SWAP, V, sqrt-SWAP where V does nothing if the control qubit is in 1 (so we get the sequence $$UU$$), and if the control qubit is 0, does the gate $$\text{diag}(1,1,-1,1)$$ on the target qubits. In other words, $$V$$ is a controlled-controlled-phase up to a couple of bit flips.

I believe the following does the job (but of course depends on what you allow your "?" to be constructed out of):