# 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. Sep 3 at 14:46
• Welcome to QCSE! Interesting question that would probably better fit on TCSSE. Have you see that SE site? Sep 3 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... Sep 3 at 16:05
• Yes, 'bit strings' would be better to say than 'bits' (which aren't usually permuted). Should I repost on the other site, or is there a way to migrate questions? Sep 3 at 16:35
• 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? Sep 3 at 16:48

I've seen claims that a single ancillary bit suffices to make the Toffoli gate universal; is there a good reference for that?

See this blog post: With a single ancilla, you can do an operation that swaps two states in the phase space. This lets you build any permutation, i.e. you get universality. There is the relevant caveat that I'm assuming that if you can do a Toffoli then "obviously" you can do a NOT gate. If you can't do a NOT gate then you need two ON ancillae to allow the Toffoli to act like a NOT.

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

Alternately, there are not very many triply transitive permutation groups, and one could appeal to that.

• I find it interesting that the Aaronson-Grier-Schaeffer paper linked above raises and immediately dismisses this question. In fact this argument was not hard at all, and is a pretty natural answer, and it makes me wonder about the classification of universality classes without their assumption of ancillary bits. It will be more complicated: Eg, the Toffoli gate by itself (no NOT) can't do anything with strings with zero or one '1' bits in them. Sep 3 at 21:43
• 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 Sep 5 at 2:35