9

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

Frederik vom Ende
  • 4,163
  • 3
  • 12
  • 49
Dylan Thurston
  • 263
  • 1
  • 7

2 Answers2

5

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:

enter image description here

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.

Craig Gidney
  • 44,299
  • 1
  • 41
  • 116
4

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.

Dylan Thurston
  • 263
  • 1
  • 7