Building universal gate set for $SU(d^n)$ from universal gate set for $SU(d)$

Question

Let $G$ be a universal gate set for $SU(d)$. Then the words $\langle G \rangle$ of $G$ form a dense subset of $SU(d)$ with respect to some reasonable norm, and so every element of $SU(d)$ can be approximated arbitrarily well.

What I don't understand is when $G$ also forms a universal gate set for $SU(d^n)$ for all $n \geq 1$. Of course, I'm used to composing quantum gates via the tensor product and $CNOT$s, so I suspect the answer is something like the following, but I'm not sure what the exact statement should be.

Let $G^{\otimes n} = \{g_1 \otimes \cdots \otimes g_n \mid g_i \in G\}$.

Attempt One: If $G$ is universal for $SU(d)$, then $G^{\otimes n}$ is universal for $SU(d^n)$.

However this is not true, because $\langle G^{\otimes n}\rangle$ only contains non-entangling unitaries, which is not dense in $SU(d^n)$. This is why we add an "entangling gate" to our universal gate sets such as the $CNOT$.

Therefore, I suspect the right theorem statement is something like:

Attempt Two: If $G$ is universal for $SU(d)$ and $E$ is a set of "entangling gates", then $G^{\otimes n} \cup E$ is universal for $SU(d^n)$.

However, I am not sure what the right definition of "entangling gate" should be, nor am I sure how to generate the set $E$ from $G$ or $G^{\otimes n}$.

Answer 1

Let $ G $ be a finite set of gates, of size $ |G| $. Let $ <G> $ be the words of $ G $. That is, $ <G> $ is the group generated by $ G $. Suppose that $ <G> $ is dense in $ SU(d) $. Then we say that $ G $ is a universal gate set for $ SU(d) $.

The center of $ SU(d) $ is all $ d $ multiples of the identity by a $ d $th root of unity $ \zeta_d $ (a global phase whose $ d $ power is the identity). Now consider the group $ SU(d^n) $. The center of $ SU(d^n) $ is all $ d^n $ multiples of the identity matrix by a $ d^n $ root of unity $ \zeta_{d^n} $ (a global phase whose $ d^n $ power is the identity).

Consider the set $ G_j:=\{ I \otimes \dots \otimes I \otimes g_i \otimes I \otimes \dots \otimes I: g \in G \} $ of gates from $ G $ but acting only on the $ j $th tensor factor. Define $$ \mathcal{G}:= \cup_{j=1}^n G_j $$ this is a finite set of size $ n|G| $. Recall that the closure of $ <G> $ is $ SU(d) $, that is, $ G $ topologically generates $ SU(d) $. So the closure of $ <G_j> $ in $ SU(d^n) $ is the entire $ j $ tensor factor and thus the closure of $ <\mathcal{G}> $ in $ SU(d^n) $ is the group of all local gates $ \bigotimes_{i=1}^n SU(d) $.

This group is exactly the identity component of the maximal closed subgroup of $ SU(d^n) $ $$ N(\bigotimes_{i=1}^n SU(d) )=\zeta_{d^n} (\bigotimes_{i=1}^n SU(d) \rtimes S_n) $$ described in table 5 row 5 ( $ n \geq 3 $ ) of https://arxiv.org/pdf/math/0605784.pdf (special case $ n = 2 $ given in table 5 row 3). The component group consists of all permutation on $ n $ qudits (the symmetric group $ S_n $) and also a global phase part.

Let $ SWAP_{ij} $ denote the SWAP gate swapping the $ i $ and $ j $ qudits. Then the $ n-1 $ gates $$ \mathcal{S}:=\{SWAP_{i,i+1}: 1 \leq i \leq n-1 \} $$ are consecutive transpositions and so generate all permutations of $ n $ qudits. See for example https://math.stackexchange.com/questions/2286481/symmetric-group-s-n-is-generated-by-consecutive-transpositions

So the the closure of the group generated by $ <\mathcal{G}, \mathcal{S}> $ contains all of $ \bigotimes_{i=1}^n SU(d) \rtimes S_n $ (if $ d $ qudit $ SWAP $ needs to be normalized to determinant $ 1 $ with a global phase it also includes some global phase).

Claim: $ N(\bigotimes_{i=1}^n SU(d)) $ is the only maximal closed subgroup containing the $ n|G|+(n-1) $ gates $ \mathcal{G} \cup \mathcal{S} $.

---

Proof:

Suppose that $ H $ is a maximal closed subgroup of $ SU(d^n) $ containing $ \mathcal{G} \cup \mathcal{S} $. Since $ H $ is a closed subgroup containing $ \mathcal{G} $ then $ H $ must contain all of $ \bigotimes_{i=1}^n SU(d) $. Since $ H $ is a group containing $ \mathcal{S} $ then $ H $ must contain all permutations on $ n $ qudits. Since $ H $ is a maximal closed subgroup of $ SU(d^n) $ it must contain all global phases $ \zeta_{d^n} $ since adding global phases to a closed subgroup always yields another closed subgroup. Since $ N(\bigotimes_{i=1}^n SU(d)) $ is exactly all the local gates plus permutations plus global phase we must have that $ H $ contains all of $ N(\bigotimes_{i=1}^n SU(d)) $. But $ N(\bigotimes_{i=1}^n SU(d)) $ is a maximal closed subgroup. So we conclude $ H= N(\bigotimes_{i=1}^n SU(d)) $. Thus $ N(\bigotimes_{i=1}^n SU(d)) $ is indeed the only maximal closed subgroup of $ SU(d^n) $ containing the gates $ \mathcal{G} \cup \mathcal{S} $.

---

Now let $ E $ be any entangling gate. That is, pick any $ E \not \in N(\bigotimes_{i=1}^n SU(d)) $ (friendliest thing to do is pick something that just entangles 2 qudits, like some qudit $ CNOT $ gate). The the closure of the group generate by the $ n|G|+(n-1)+1 $ many gates $ \mathcal{G} \cup \mathcal{S} \cup \{ E \} $ must be all of $ SU(d^n) $ since the only maximal closed subgroup containing $ \mathcal{G} \cup S $ is $ N(\bigotimes_{i=1}^n SU(d)) $. But $ E $ is not in that group. A closed group not contained in any maximal closed subgroup must be all of $ SU(d^n) $.

Thus the $ n|G|+(n-1)+1 $ many gates $ \mathcal{G} \cup \mathcal{S} \cup \{ E \} $ are a universal gates set for $ SU(d^n) $ consisting of $ n|G| $ many single qubit gates and $ n $ two qubit gates.

Note: The reason we only need 1 entangling gate, for example $ CNOT_{12} $, is because $ \mathcal{S} $ generates all qudit permutations $ \sigma $ and conjugating $ CNOT_{12} $ by a qudit permutation $ \sigma $ yields $ CNOT_{\sigma(1)\sigma(2)} $. Thus we get all $ CNOT_{ij} $ for the price of one! (plus the $ n-1 $ swap gates)

---

Original answer, not as convincing, especially at the end when I try to make an argument about positive dimensional simple subgroups, I don't even know if that part is valid.

Consider the set $$ G^{\otimes n}:=\{ \prod_{i=1}^n g_i: g_i \in G \} $$ this is a finite set of size $ |G|^n $. Recall that the closure of $ <G> $ is $ SU(d) $, that is, $ G $ topologically generates $ SU(d) $. So the closure of $ <G^{\otimes n}> $ in $ SU(d^n) $ is $ \bigotimes_{i=1}^n SU(d) $.

The closed subgroup $ \bigotimes_{i=1}^n SU(d) $ of $ SU(d^n) $ is not maximal. It is contained in two different types of maximal subgroups.

The first type are the maximal subgroups from rows 2&3 of table 5 in https://arxiv.org/abs/math/0605784. These groups are all $ N(SU(d^k) \otimes SU(d^{n-k})) $ for some $ 1 \leq k \leq n-1 $. It is interesting to note that the structure of the component group of the normalizer depends on the value of $ k $, see row 2 column 2 and row 3 column 2, respectively.

The second type is the maximal subgroup in row 5 of table 5. This maximal subgroup is $$ N(\bigotimes_{i=1}^n SU(d) )=\zeta_{d^n} (\bigotimes_{i=1}^n SU(d) \rtimes S_n) $$ Note that in my comment posted beneath the original question I forgot to include the global phase in the normalizer. This isn't especially important for quantum because we don't care about global phase, but it is interesting. For example $ iI \in SU(4) $ clearly normalizes $ SU(2) \otimes SU(2) $, since it is a global phase, but it is a simple and fun exercise to show that $ iI $ lies properly in the normalizer i.e. $ iI \not \in SU(2) \otimes SU(2) $. That is, there is no way to write $ iI=g_1 \otimes g_2 $ for $ g_1,g_2 \in SU(2) $. For more details on this particular case see my question https://math.stackexchange.com/questions/4397313/so-4-mathbbr-and-su-2-otimes-su-2-subgroups-of-su-4 . Also note that the $ \zeta_{d^n} $ global phase is not a direct product because $ \bigotimes_{i=1}^n SU(d) $ already contains a $ \zeta_d $ global phase. So the actual contribution to the component group of the normalizer is a cyclic $ d^{n-1} $. So as recorded in column 2 of row 5 the component group of $ N(\bigotimes_{i=1}^n SU(d) ) $ is a direct product of $ S_n $ with cyclic $ d^{n-1} $.

Note that in both cases above the maximal subgroups containing $ \bigotimes_{i=1}^n SU(d) $ have normalizers which are just generated by global phases and permutations.

Now let $ E $ be a 2 qudit entangling gate. In other words, an element of $ SU(d) $ which is not in $ N(SU(d) \otimes SU(d) ) $ (so not a tensor product or a SWAP gate or a global phase). Let $ E_{ij} $ be the gate in $ SU(d^n) $ that acts as $ E $ on the $ SU(d^2) $ containing $ SU(d)_i \otimes SU(d)_j $ and acts as the identity on the $ n-2 $ other tensor factors. Then let $ \mathcal{E} $ be the finite set of these $ {n}\choose{2} $ many $ E_{ij} $. Then $ \mathcal{E} $ creates entanglement across any partition $ d^{n-k},d^k $ of the $ n $ many local $ SU(d) $ factors. Thus the group generated by $ G^{\otimes n} \cup \mathcal{E} $ cannot be contained in any of the $ N(SU(d^k) \otimes SU(d^{n-k})) $ subgroups. And it certainly is not contained in $ N(\bigotimes_{i=1}^n SU(d) ) $ since that is precisely the group of nonentagling gates and the $ \mathcal{E} $ gates are all entangling.

And $ \bigotimes_{i=1}^n SU(d) $ is already irreducible so it cannot be contained in the reducible subgroups from rows 1 and 4 of table 5.

The group is clearly infinite so cannot be contained in a finite maximal closed subgroup.

Finally any positive dimensional simple subgroup must preserve some either symplectic orthogonal or unitary form but any form preserved by all entangling gates must just coincide with the original unitary form thus the group generated is the whole group $ SU(d^n) $.

So we now have a finite set $ G^{\otimes n} \cup \mathcal{E} $ of size $ |G|^n + $ $ {n}\choose{2} $ which is universal for $ SU(d^n) $.