# Minimum number of CNOTs for Toffoli with non-adjacent controls

I want to decompose a Toffoli gate into CNOTs and arbitrary single-qubit gates. I want to minimize the number of CNOTs. I have a locality constraint: because the Toffoli is occurring in a linear array, the two controls are not adjacent to each other (so no CNOTs directly between the controls).

What is the minimum number of CNOTs required to perform this task? What is an example of a circuit which achieves this minimum?

To be specific, this is the layout I have in mind:

1 ---@---
|
2 ---X---
|
3 ---@---


Each control is adjacent to the target, but the controls are not adjacent to each other.

• As you have realized yourself in the answer, the location of the controls is irrelevant. Would it make sense to update the question? Aug 8 '18 at 22:23

I believe I've got it down to 9 controlled-not gates: What I did was I used a set of three cNots in the place of Swap to move the two controls next to each other to achieve the last part of the standard Toffoli circuit (see here). This used 12 cNots.

However, the final $T$ and $H$ gates on the target qubit I propagated through one of these swaps. This let me cancel two controlled-Nots.

Then, in the final SWAP, I chose the first of the controlled-nots to be controlled from the middle qubit. I replaced it with a controlled-phase and two Hadamards. The leading Hadamard cancelled. The controlled-phase gate commutes with the preceding controlled gates controlled off the middle qubit, and phase gates on the middle qubit and bottom qubits. These operations bring that controlled phase up to a controlled-not from the first inserted swap. Hence, we can combine these two gates as a controlled-$iY$, controlled off the bottom qubit. But this can be written as a single cNot with some $S$ gates.

I've made no attempt at an optimality proof, but I'm already pretty pleased to have got it this small.

Here is the best construction I've found. It uses 8 CNOTs. I verified this circuit in Quirk using the channel-state duality and a known-good inverse.

The target is the middle qubit. None of the CNOTs go directly from top to bottom or bottom to top. You can switch which qubit is the the target by simply switching which line the Hadamards are on.

• For everyone else reading this, I've confirmed it works. Aug 7 '18 at 11:05
• Can you give any insight as to how you constructed this? Is it a set of manipulations from the standard circuit, or did you get it by some independent method? Aug 7 '18 at 11:06
• @DaftWullie Instead of trying to make a Toffoli, I focused on a CCZ because it's more symmetric but the same problem. I knew that a CCZ made out of CNOT+T needed the CNOTs to form a classical identity circuit. I knew one way to decompose an 1->3 CNOT is to do 1->2+2->3 twice. Two identical CNOTs is an identity, so I started with two 1->3 gates. Then I decomposed them both into the 1->2->3 * 2 form. Then I checked if the classical parity combinations needed for the various T gates were present, and... well, they were. In other words, I tried a random idea based on a vague hunch and got lucky. Aug 7 '18 at 11:40
• @DaftWullie I guess you should be able to understand how it works using the ideas of arxiv.org/abs/quant-ph/0303063. Aug 7 '18 at 14:44
• @CraigGidney Have checked for solutions following the scheme of the paper above. My code found 4 solutions with 8 CNOTs, so (within this scheme) the above solution is unique up to reflections. Also, there were no solutions with 7 or less CNOTs. Of course, this doesn't mean there aren't solutions which use non-diagonal single-qubit gates (or I made a programming error). Aug 8 '18 at 22:00

If you allow for a relative phase you can get your circuit to 3 $$CNOT$$s and 4 $$U$$ gates. • You've missed a key factor in the question - you can only perform gates between nearest neighbours. So your controlled-not gates between $q_0$ and $q_2$ are not allowed. Jun 22 at 6:57
• Ok that makes sense Jun 22 at 11:32