Is there a difference between the set of quantum gates that are:universal in the sense that you could calculate anything in BQP with a polynomial number of gates,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 gatesCNOT gates plus all single qubit gatesare 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)?
universality of quantum gates
complexity theory;quantum computing
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.