Implementing Odd Permutations Without Ancilla Bit

Question

The paper says that

The inversion $\alpha \mapsto \alpha^{-1} $ (where 0 is mapped to 0) can be seen as a permutation on $\mathbb F_{256}$. This permutation is odd, while quantum circuits with NOT, CNOT, and Toffoli gates on n > 3 qubits generate the full alternating group $A_{2n}$ of even permutations. Hence we have to use one ancilla qubit, i.e., nine qubits in total.

Why we restrict the gates only to NOT, CNOT, and Toffoli? As I know they does not generate the universal quantum gate set. Isn't It? For example n-qubit Toffoli is an odd permutation in $S_{2^n}$, but it can be constructed with out ancilla bit as shown in the page.

I think with out ancilla qubit we can construct any permutation in $S_{2^n}$ (in particular we can implement any S-box without ancilla). Am I wrong?

Answer 1

Although the paper is technically wrong to say they need an ancilla qubit, I still think it's the correct choice to use an ancilla qubit. They want an ancilla qubit. It's true that you can bypass the parity barrier by using quantum operations, but doing so has a high cost. Bootstrapping an ancilla qubit will easily consume 5x more T gates than just starting with an ancilla qubit.

Also, keep in mind that, in the context of a large computation laid out on a 2d grid, there are already ancilla qubits everywhere. You need free space to build the magic state factories in. You need free space to enable routing information from one place to another. Your circuit is already filled with ancilla qubits, you're just not drawing them. Using one ancilla qubit, instead of none, is effectively irrelevant when the wider context is considered. Pay the space cost. Save the T gates.

Plus, if you finish faster, you can use less error correction. You can lower the code distance, which saves way more space than one ancilla qubit. For example: