# How universal is the Toffoli gate for classical reversible computing?

It is easy to see that no finite set of classical reversible gates can be strictly universal (without ancilla) for classical reversible computation: for any reversible gate on $$n$$ bits, in its action on $$n+1$$ bits it induces an even permutation, and so cannot achieve an arbitrary permutation of the set $$\{0,1\}^{n+1}$$ in any combination.

With sufficiently many ancillary bits, the Toffoli gate can achieve arbitrary permutations; this is described many places, starting with Toffoli's original paper. (The standard construction as he describes it uses $$n-3$$ ancillary bits for computations on $$n$$ bits.)

But how close can you get? Specifically, for, say, the Toffoli gate plus NOT gates (or equivalently arbitrary 3-bit gates), can you achieve an arbitrary even permutation of $$\{0,1\}^n$$ for any $$n > 3$$?

Related, I've seen claims that a single ancillary bit suffices to make the Toffoli gate universal; is there a good reference for that? (That is a weaker result, of course.)

(I'm asking about classical reversibility, so maybe the question should be redirected. This sign-of-permutation argument explains why any proof of strict quantum universality needs to use a non-permutation matrix in bootstrapping from operations on a finite set of qubits to general circuits.)

• It may not be helpful, but have you seen this classification of reversible gates? The Fredkin gate (CSWAP) doesn't change the Hamming weight of the inputs. Commented Sep 3, 2021 at 14:46
• Welcome to QCSE! Interesting question that would probably better fit on TCSSE. Have you see that SE site? Commented Sep 3, 2021 at 16:03
• BTW, the action of the 2-bit gate that swaps its inputs induces a transposition on three bits, which is an odd permutation. I suppose you might be meaning the action of an $n$-bit gate on the set $\{0, 1\}^{n+1}$ of $n+1$ bit strings (rather than on the bits) which is indeed always even... Commented Sep 3, 2021 at 16:05
• @MarkS, thank you for the reference, it looks very interesting. To get on-topic for this SE, is there a similar 'types of universality' theorem for quantum gates? Commented Sep 3, 2021 at 16:36
• No! Not as far as I know. I think that's a very rich question, that Aaronson, Grier, and Schaeffer leave as their top "Open Problem" in section 10 of their paper. For example, the (infamous or famous) Gottesman-Knill theorem immediately gives that $\{ \text H,\text S, \text{CNOT} \}$ is not likely to be universal. Must there be a "hierarchy" of sub-universal gates? Factoring is not likely to be $\text{BQP-complete}$, but it's still in $\text{BQP}$ - what does that imply about the gates used in Shor's algorithm? Commented Sep 3, 2021 at 16:48

It turns out Toffoli + NOT is universal for alternating permutations of bit-strings for $$n \ge 4$$. The construction of a $$\mathrm{C}^n\mathrm{NOT}$$ gate with one borrowed bit (starting in unknown state, and returning there) generates a permutation that is a pair of flips on any 2-d face of the hypercube $$\{0,1\}^n$$. This strictly contains the group $$IGL(\mathbb{F}^n)$$, affine linear transformations of the hypercube (also the group generated by 2-bit operations), so in particular is triply transitive. For $$n=4$$, GAP assures me that it contains a 3-cycle, and is therefore the entire alternating group for any $$n\ge 4$$.
• This result also appears in various places in the literature. One general result that implies it is Selinger's result letting you bootstrap size $n+1$ reversible circuits from size $n$ ones: arxiv.org/abs/1604.02549v3 Commented Sep 5, 2021 at 2:35