Is there a difference between the set of quantum gates that are:

  1. "universal" in the sense that you could calculate anything in BQP with a polynomial number of gates,

  2. "universal" in the sense that you could approximate any arbitrary "gate" (unitary transformation) on a set of qubits?

And if so, what is the proper terminology to distinguish between these? (Or maybe it is exclusively used in only one of the above meanings?)

I believe these are at least different (but maybe the second implies the first). For example, it is my understanding that both of these sets:

  • Toffoli and Hadamard gates

  • CNOT gates plus all single qubit gates

are universal in the first sense, yet the first set cannot make phase shifts gates from the later. So Toffoli and Hadamard gates cannot be universal in the second sense.

Does any set meeting the second sense of universality automatically satisfy the first as well (or can some sets so inefficiently approximate calculations that they are not useful for modelling BQP)?


Yes, approximate-any-quantum-gate implies can-solve-BQP-efficiently.

Even if the cost of approximating gates is very high, you only need to approximate Hadamard, CNOT, and $Z^{1/4}$ operations to some constant fidelity before error correction starts to work. So although you may pay a large constant overhead to get "good enough", once you get there the extra overhead to achieve better and better precision becomes reasonable.

  • $\begingroup$ Is there a standard terminology for "approximate-any-quantum-gate" vs "can-solve-BQP-efficiently" concepts of universality? Also, are Hadamard, CNOT, and Z^1/4 universal, or is that just what is needed for error correcting? $\endgroup$ – PPenguin Apr 9 '17 at 0:02
  • $\begingroup$ @PPenguin I don't know about the terminology, but the gate set I mentioned is universal. $\endgroup$ – Craig Gidney Apr 9 '17 at 0:21
  • $\begingroup$ I found a paper that mentions the two types and calls them "Computational Universality" and "Strict Universality". arxiv.org/abs/quant-ph/0301040 I'm not sure how standard that terminology is, but sounds like reasonable terms. $\endgroup$ – PPenguin Apr 9 '17 at 0:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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