11
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ As you have realized yourself in the answer, the location of the controls is irrelevant. Would it make sense to update the question? $\endgroup$
    – Norbert Schuch
    Commented Aug 8, 2018 at 22:23

4 Answers 4

Reset to default
4
$\begingroup$

Here is the best construction I've found. It uses 8 CNOTs.

8-cnot construction

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ For everyone else reading this, I've confirmed it works. $\endgroup$
    – DaftWullie
    Commented Aug 7, 2018 at 11:05
  • $\begingroup$ 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? $\endgroup$
    – DaftWullie
    Commented Aug 7, 2018 at 11:06
  • $\begingroup$ @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. $\endgroup$
    – Craig Gidney
    Commented Aug 7, 2018 at 11:40
  • $\begingroup$ @DaftWullie I guess you should be able to understand how it works using the ideas of arxiv.org/abs/quant-ph/0303063. $\endgroup$
    – Norbert Schuch
    Commented Aug 7, 2018 at 14:44
  • $\begingroup$ @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). $\endgroup$
    – Norbert Schuch
    Commented Aug 8, 2018 at 22:00
3
$\begingroup$

I believe I've got it down to 9 controlled-not gates: enter image description here

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.

Improve this answer
$\endgroup$
0
3
$\begingroup$

I found this circuit with T-depth 3 using CPFlow (shameless plug). enter image description here

Non-clifford gates (with T-count 1) are $R_Z(\pi/4)$ and $R_X(\pi/4)$. While most of the single-qubit non-Clifford gates in this circuit can probably be removed, circuits with shorter T-depth, T-count or CZ-depth are unlikely to be possible.

Community edit:

Improve this answer
$\endgroup$
4
  • $\begingroup$ Neat solution. It's weird to me to combine the T-depth constraint with a locality constraint, since my intuition is one is mostly-relevant-to-fault-tolerance and the other is mostly-relevant-to-nisq. For fault tolerant circuits T gates are such a huge opportunity cost that the design space opens way up. In that regime I would use ancillae to cut the T count from 7 to 4 and to cut the reaction depth down to 2, or even better switch to distilling CCZ states instead of T states. $\endgroup$
    – Craig Gidney
    Commented Jul 25, 2022 at 16:23
  • $\begingroup$ @CraigGidney the circuit wasn't really meant to be practical, but mostly to illustrate that one can use computer search for such problems. Still, I think 3 is the shortest T depth for the connected case as well. Also, I didn't know that ancilla help reducing T count, because they don't work for CX count in this case. Thanks for the comment! $\endgroup$
    – Nikita Nemkov
    Commented Jul 25, 2022 at 16:43
  • $\begingroup$ Yes, I understand. You can prove 3 is the shortest possible by the fact that if you need 7 T gates and only 3 fit in a layer then you need at least 3 layers. You can see the ancilla-assist thing here: arxiv.org/abs/1709.06648 (figure 3) and here arxiv.org/abs/1212.5069 (figure 1). $\endgroup$
    – Craig Gidney
    Commented Jul 25, 2022 at 16:46
  • $\begingroup$ Note: this circuit has the target on the bottom qubit instead of the middle qubit. $\endgroup$
    – Craig Gidney
    Commented Jul 25, 2022 at 21:31
0
$\begingroup$

If you allow for a relative phase you can get your circuit to 3 $CNOT$s and 4 $U$ gates.

enter image description here

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – DaftWullie
    Commented Jun 22, 2021 at 6:57
  • $\begingroup$ Ok that makes sense $\endgroup$
    – Minh Pham
    Commented Jun 22, 2021 at 11:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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