# Decidability/algorithm for checking universality of a quantum gate set

Given a finite set of quantum gates $\mathcal{G} = \{G_1, \dots, G_n\}$, is it decidable (in computation theoretic sense) whether $\mathcal{G}$ is a universal gate set? On one hand, "almost all" gate sets are universal, on the other, non-universal gate sets are still not well understood (in particular, of course, it is not known whether every non-universal gate set is classically simulatable), so I imagine giving an explicit algorithm for checking universality could be nontrivial.

• Can you clarify the question? Joe's answer assumes you have a fixed number of qubits and all gates act on those, but for universality, we often assume gates can act on any subset of qubits. E.g., CNOT + all one-qubit gates are not universal if the one-qubit gates can only act on the first qubit, and CNOT is only from qubit 1 to qubit 2. In the latter case, we might want to extrapolate to many qubits to get universality. In that case, I think the anwer may be unknown. – Daniel Gottesman Jan 23 '12 at 15:30
• @DanielGottesman: I agree about the limitations of my answer. Indeed, I believe it is undecidable in the latter case as follows: Take a cellular automata on an infinite lattice of qubits and use it to encode the halting problem (call this update unitary $U_1$). Then take a second lattice with a universal QCA (with update unitary $U_2$). We can define a new unitary $CU_2 = |0\rangle\langle0|_H\otimes I + |1\rangle\langle1|\otimes U_2$, where the subscript $H$ denotes a qubit which is set to $|1\rangle$ iff the first cellular automata halts. – Joe Fitzsimons Jan 31 '12 at 6:19
• Thus the gate $CU_2 \times U_1$ is universal if and only if the first Turing machine halts, and is hence undecidable. – Joe Fitzsimons Jan 31 '12 at 6:22

• I meant you should consider $[\ldots[H_k,H_j],H_l],\ldots]$, but not only pairs, e.g. see my own paper arxiv.org/abs/quant-ph/0010071 – Alex 'qubeat' Jan 21 '12 at 12:35