4
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Not sure about a deterministic algorithm to check this but since any reversible Boolean function $f: \{ 0,1 \}^{n} \rightarrow \{ 0,1 \}^{n}$ is a permutation of the $n$-bits, your gate set needs to be able to generate the unitaries corresponding to at least pairwise swaps or something equivalent (so that you can compose them to generate all possible permutations). $\endgroup$
    – keisuke.akira
    Jul 1, 2021 at 10:28
  • $\begingroup$ As any universal quantum computer is able to implement any classical algorithm, it is enough to check if the gates set is universal for a quantum computer. Of course, such set does not have to be the smallest one. $\endgroup$
    – Martin Vesely
    Jul 1, 2021 at 21:12
  • 1
    $\begingroup$ @MartinVesely I am more interested in intermediate cases, when the gate set is universal for reversible classical computation but not quantum computation. $\endgroup$
    – BlackHat18
    Jul 2, 2021 at 4:40
  • $\begingroup$ @keisuke.akira It gets hard to check this if your gate set has imaginary entries. For example, consider the problem of trying to determine whether the set {CNOT, Hadamard, S} is universal for reversible classical computation. I think it is not, but the S gate makes checking it hard. $\endgroup$
    – BlackHat18
    Jul 2, 2021 at 4:43
  • 1
    $\begingroup$ My approach would be to check what is the group generated by your gate set (if it's not a group because it lacks an inverse then it's already not universal). If it has the permutation group as a subgroup, it's universal. Otherwise, it's not. $\endgroup$
    – Mateus Araújo
    Jul 2, 2021 at 9:46

0

Reset to default

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.