Are relative phase Toffoli gates universal for reversible circuits?

Question

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?

Answer 1

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.