2
$\begingroup$

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?

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

1 Answer 1

3
$\begingroup$

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$:

enter image description here

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:

enter image description here

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:

enter image description here


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.

$\endgroup$
2
  • 1
    $\begingroup$ @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. $\endgroup$ Sep 25, 2022 at 21:47
  • $\begingroup$ Amazing work thanks! $\endgroup$
    – Mauricio
    Sep 26, 2022 at 19:46

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.