1
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

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

Your Answer

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

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