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


1 Answer 1


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, 2017 at 0:02
  • $\begingroup$ @PPenguin I don't know about the terminology, but the gate set I mentioned is universal. $\endgroup$ Apr 9, 2017 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, 2017 at 0:27

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.