7
$\begingroup$

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

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ 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. $\endgroup$
    – Mark Spinelli
    Sep 3, 2021 at 14:46
  • $\begingroup$ Welcome to QCSE! Interesting question that would probably better fit on TCSSE. Have you see that SE site? $\endgroup$
    – Adam Zalcman
    Sep 3, 2021 at 16:03
  • $\begingroup$ 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... $\endgroup$
    – Adam Zalcman
    Sep 3, 2021 at 16:05
  • 1
    $\begingroup$ @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? $\endgroup$
    – Dylan Thurston
    Sep 3, 2021 at 16:36
  • 2
    $\begingroup$ 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? $\endgroup$
    – Mark Spinelli
    Sep 3, 2021 at 16:48

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Dylan Thurston
    Sep 3, 2021 at 21:43
  • $\begingroup$ 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 $\endgroup$
    – Dylan Thurston
    Sep 5, 2021 at 2:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.