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:

enter image description here

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:

sqrt swap

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:

Fredkin from sqrt swap

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.

| improve this answer | |
  • $\begingroup$ 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 ? $\endgroup$ – Alex Mar 26 '19 at 18:22
  • $\begingroup$ I don't think that's possible. All those operations preserve total number of set bits, but CNOT doesn't. $\endgroup$ – Craig Gidney Mar 26 '19 at 20:27
  • $\begingroup$ Actually, they don't commute, so maybe you can escape the space. $\endgroup$ – Craig Gidney Mar 27 '19 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): enter image description here

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.