At a high level, this question can be phrased quite simply: which sets of gates are universal for quantum computation?
In quantum computation, there are many notions of universality that we can adopt. One of the most standard and useful definitions is what we may call "approximate universality", wherein a set of quantum gates \( \mathcal{G} \) is said to be universal if for any unitary \( U \) and error \( \epsilon \), there exists a circuit
over \( \mathcal{G} \) that realizes a unitary \( U_{\epsilon} \) such that \( \lVert U - U_{\epsilon} \rVert_{sup} < \epsilon. \) Note that here, importantly, we characterize the "closeness" of two unitaries in operator norm. Though there remain interesting open questions regarding criterion for the realization of approximate universality in quantum gatesets,
a good deal is also known. For example, it is known that if \( \mathcal{G} \) is approximately universal for all single-qubit unitaries, and \( \mathcal{G} \) contains any entangling gate, then \( \mathcal{G} \) is approximately universal at large.
However, there is an argument to be made that approximate universality, while very natural and useful to reason about, is in fact too strong a notion of universality. In particular, whenever a quantum circuit is implemented to solve a given computational task, the solution given is not inherently due to the unitary realized by the circuit, but is rather due to the statistical distribution realized at the end of the circuit.
This observation suggests that even if a given gateset \( \mathcal{G} \) cannot approximate an arbitrary unitary \( U \) to arbitrary precision, so long as it can realize a unitary \( U_\epsilon \) whose output distribution is within arbitrary statistical distance to the output distribution of \( U \), then \( \mathcal{G} \) still ought to be considered universal, at least for computational tasks. Appropriately, we refer to this notion of universality as "computational universality."
A nice example of a computationally universal (but not approximately universal) gateset (due to Shi), is \( \{ \text{CNOT}, V \} \), where \( V \) is any real single-qubit gate which does not preserve the computational basis when squared (essentially so long as \( V \) is not a Hadamard gate).
We naturally ask then, which sets of gates are computationally universal for quantum computing? And more precisely, how might the emergence of computational universality in quantum gatesets be mathematically characterized?