# Are relative phase Toffoli gates universal for reversible circuits?

Let us define a new three qubit gate as:

$$\begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{bmatrix}.$$

This gate almost coincides with the Toffoli gate, except that it has a minus sign for the state $$|101\rangle$$. This gate has the advantage that it can be built using just 3 CNOTs (instead of 6) plus single qubit rotations. I cannot figure out if this gate is also universal for reversible circuits as the Toffoli. Could I get a Toffoli gate from this gate?

• What other gates are allowed? Clearly it's not universal on its own since it can't create superpositions. Sep 25, 2022 at 17:55
• @CraigGidney only that gate. Universal in the same sense of Toffoli being universal for reversible circuits. Sep 25, 2022 at 18:38

You can decompose the Toffoli into this gate if you have an ancilla qubit.

First, note that the gate is equivalent to $$CCX \cdot \overline{C}CZ$$:

Note that the order of the $$CCX$$ and the $$\overline{C}CZ$$ doesn't matter, since they disagree on a control.

Knowing this decomposition, and using a $$|0\rangle$$ ancilla, it's not too hard to find a way to ensure the phase operations cancel out or have their controls unsatisfied:

This ancilla may bother you. Although, note that in Aaronson et al's classification of reversible gates, they did allow ancilla qubits in $$|0\rangle$$ and $$|1\rangle$$ as long as they were restored to their original state by the end of the circuit.

It is possible to fix the fact that the ancilla needs to be in a specific state. You can modify the construction so that it works with any ancilla, no matter its value:

# Impossibility without ancilla

There are two relevant parities here: permutation parity and phase parity. The permutation parity of an operation is the number of state swaps needed to implement the operation ignoring phase. The phase parity of an operation is whether an even or odd number of states have their amplitude negated by the operation.

When there are no ancilla qubits, the gate you described has odd permutation parity and odd phase parity. Therefore the gate you described can only be used to implement operations whose permutation and phase parity are the same.

When there are no ancilla qubits, the Toffoli operation has odd permutation parity but even phase parity. It has disagreeing permutation and phase parity. Therefore the Toffoli cannot be decomposed into your gate when their are no ancilla qubits.

This proof breaks when there are ancilla qubits because all the parities become even, due to everything happening in the subspace where the ancilla is 0 and also in the subspace where the ancilla is 1.

• @Mauricio I improved the decomposition to use 3 instead of 5, and gave a variant with 4 that doesn't require a specific ancilla state. Sep 25, 2022 at 21:47
• Amazing work thanks! Sep 26, 2022 at 19:46