4

Is there any way to check whether a set of gates (for example, take the set comprising of the CNOT gate and the Hadamard gate) is universal for reversible classical computation?

I can think of trial and error methods, like checking whether we can construct a Toffoli gate or a Fredkin gate with our gate set.

But is there a better way --- perhaps a deterministic algorithm --- to check this?

A sufficient condition to check this would be to check whether the gate set is universal for quantum computation. But, there may be gate sets that are universal for reversible classical computation but not universal for quantum computation (for example, the Toffoli gate). How to check these intermediate cases?

BlackHat18
  • 1,527
  • 9
  • 22

1 Answers1

1

You do have to be a little careful on what you mean by "universal." The CCNOT (Toffoli) gate is universal in a stronger sense than the CSWAP (Fredkin) gate is, if only because CSWAP preserves Hamming weight.

If your gate set itself is limited to classically reversible gates (e.g., you exclude Hadamard or Square-Root-of-Not type gates or even Square-Root-of-SWAP type gates), I believe the most recent word on this is Aaronson, Grier, and Schaffer's massive tome "The Classification of Reversible Bit Operations" (arXiv link).

Quoting from the abstract:

Our theorem implies a linear-time algorithm (which we have implemented), that takes as input the truth tables of reversible gates $G$ and $H$, and that decides whether $G$ generates $H$... The theorem says that every set of reversible gates generates either

  • all reversible transformations on $n$-bit strings (as the Toffoli gate does);
  • no transformations;
  • all transformations that preserve Hamming weight (as the Fredkin gate does);
  • all transformations that preserve Hamming weight mod $k$ for some $k$;
  • all affine transformations (as the Controlled-NOT gate does);
  • all affine transformations that preserve Hamming weight mod $2$ or mod $4$, inner products mod $2$, or a combination thereof; or
  • a previous class augmented by a NOT or NOTNOT gate.

I can't speak to the algorithm that they mention in the paper but at least it indicates that there's a linear-time algorithm to check if the truth-table of a particular gate, say the BlackHat gate, and compare it to the truth-table of the CCNOT gate to see if BlackHat generates CCNOT.

Mark Spinelli
  • 15,378
  • 3
  • 26
  • 83