Universal sets of gates for SU(3)?

Question

In quantum computing we are often interested in cases where group of special unitary operators, G, for some d-dimensional system gives either the whole group SU(d) exactly or even just an approximation provided by a dense cover of SU(d).

A group of finite order, such as the Clifford group for a d-dimensional system C(d), will not give a dense cover. A group of infinite order will not give a dense cover if the group is Abelian. However, my rough intuition is that an infinite number of gates and basis changing operations of the Clifford group should suffice to provide a dense cover.

Formally, my question is:

I have a group G that is a subgroup of SU(d). G has infinite order and C(d) is a subgroup of G. Do all such G provide a dense cover of SU(d).

Note that I am particular interested in the case when d>2.

---

I take the Clifford group to be as defined here: http://arxiv.org/abs/quant-ph/9802007

This post has been migrated from (A51.SE)

Comments

Can you formulate a mathematical definition of the Clifford group? I found it difficult to extract from the paper without reading it in detail

This post has been migrated from (A51.SE)

---

@Squark: for $N\geqslant 2$ arbitrary, consider the subgroup $G \subseteq \mathbf U(N)$ generated by an operator $X$ which "shifts" the standard basis vectors on $\mathbb C^N$ cyclically, an operator $Z = \mathrm{diag}(1, \omega, \omega^2, \ldots, \omega^{N-1})$ for $\omega = \exp(2\pi i/N)$, and an operator $Y = \mathrm e^{\pi i (N-1)(N+1)/N} ZX$. (The scalar in front of $Y$ is up for negotiation for $N > 2$; for $N = 2$ the matrices $X,Y,Z$ will be the usual Pauli spin matrices.) Then the Clifford group is the set of operators in $\mathbf U(N)$ which preserves $G$ under conjugation.

This post has been migrated from (A51.SE)

Answer 1

I believe the answer to original question is probably yes, but unfortunately, I can't say that definitively. I can help answer Peter's extended question, however.

In math/0001038, by Nebe, Rains, and Sloane, they show that the Clifford group is a maximal finite subgroup of U(2^n). Solovay has also shown this in unpublished work that "uses essentially the classification of finite simple groups." The Nebe et al. paper also shows that the qudit Clifford group is a maximal finite subgroup for prime p, also using the classification of finite groups. This means that the Clifford group plus any gate is an infinite group, which makes one of the assumptions of the original question redundant.

Now, both Rains and Solovay told me that the next step, showing that an infinite group containing the Clifford group is universal, is relatively straightforward. However, I don't know how that step actually works. And more importantly for the original question, I don't know if they were only considering the qubit case or also the qudit case.

Actually, I might add that I don't understand the Nebe, Rains, and Sloane proof either, but would like to.

This post has been migrated from (A51.SE)

Answer 2

It's not clear to me whether you're asking about SU(3) or SU(3$^{n}$) acting on a tensor product of qudits. I'll assume you're asking about SU(3). It's not clear to me (despite what I said in a previous version of my answer) that the statement for SU(3) implies the statement for SU(3$^n$).

As long as the set of gates doesn't lie in a subgroup of SU(3), it will generate a dense cover of SU(3). So you need to check whether any of the infinite subgroups of SU(3) contains the Clifford group. I am fairly sure they don't, but I can't say for sure. Here is a math overflow question giving all the Lie subgroups of SU(3).

This post has been migrated from (A51.SE)

Comments

@PeterShor: Regarding your update, doesn't the statement for $SU(3^n)$ follow from http://pra.aps.org/abstract/PRA/v66/i2/e022317 ?

This post has been migrated from (A51.SE)

---

In case it is not clear what I meant by the above comment, I mean that the paper can be taken as the following statement: the Lie algebra generated by the generators of the Lie algebra $su(D)$ for $N$ qudits plus any two-body operators connecting pairs of subsystems is exactly $su(D^N)$. Since you have all local generators already for $su(3)$ (by assumption), conjugating one of these (say $X_D$) by an entangling Clifford gate with which it does not commute (say SUM) gives you a suitable cross term in the relevant Lie algebra (which then becomes $su(D^N)$).

This post has been migrated from (A51.SE)

---

@Joe: what I meant was, if you take the Clifford group for SU(3$^n$) and add a single gate (possibly an entangling gate) that gives you an infinite group, it's not clear that you generate a dense subgroup. I don't think you can use the link above because if you just have the Clifford group for a single copy of SU(3), you don't know that you have generators for $su$(3) in the Lie algebra.

This post has been migrated from (A51.SE)

---

@PeterShor: Sorry, I took your update to mean that you were now doubting about whether given gates that provide dense cover over SU(3) plus the Clifford group corresponding to local system dimension 3 you get dense cover over SU($3^N$). My point was that you do. However if you are talking about the Clifford group corresponding to local dimension $3^N$, then I agree that it does not seem to easily follow. I think the fact that SU(N) does not denote the dimensionality of the local systems and hence which Clifford group we are talking about is leading to confusion.

This post has been migrated from (A51.SE)

---

Some question troubles me in relation with that: for odd dimension the Clifford group isomorphic with $SL(2,Z_d)$, but, e.g., both $SL(2,Z_3)$ and $SL(2,Z_5)$ are isomorphic with some finite subgroups of $SU(2)$ - see Wolf, Spaces of constant curvature. Why we may be so sure, that Clifford group may not be in some infinite subgroup of $SU(d)$?

This post has been migrated from (A51.SE)

---

Ah, I see. I'll delete my answer. From the context of the notes I linked to it sounded like the theorem applied in arbitrary dimensions, not just the case where $d=2$. However, upon digging up the source that appears not to be the case. Thanks for pointing out the error.

This post has been migrated from (A51.SE)

---

Ultimately, I will be interested in $SU(3^{n})$. However, because this is entailed by universality in $SU(3)$ + the Clifford group, this is how I phrased the question to keep it simple. I also had a quick look at the reference Joe provided and could only see results for $d=2$.

This post has been migrated from (A51.SE)

Answer 3

This is not a complete answer, but perhaps it goes some way towards answering the question.

Since $G$ has infinite order but $C(d)$ is not, then $G$ necessarily contains a non-Clifford group gate. However $G$ has $C(d)$ as a subgroup. But for $d=2$ the Clifford group plus any other gate not in the Clifford group is approximately universal (see e.g. Theorem 1 here). Therefore all such $G$ provide dense cover on $SU(2^n)$.

For the case where $d>2$ it seems like it may be possible to prove that you still get dense cover along the following lines (using the notation of the paper linked to in the question):

1. As all gates in $G$ are unitary, all of their eigenvalues are roots of unity, which for simplicity I will parameterize by real angles $0 \leq \theta_i < 2\pi$.
2. As $G$ has infinite order, either $G$ contains gates for which at least one value $\theta_k$ is an irrational multiple of $\pi$ or contains an arbitrarily good approximation to such an irrational multiple of $\pi$. Let us designate one such gate $g$.
3. Then there exists an $n$ such that $g^n$ is arbitrarily close to, but not equal to the identity.
4. Since $g^n$ is unitary it can be written as $\exp(-iH)$.
5. Since the Pauli group as defined in quant-ph/9802007 forms a basis for $d \times d$ matrices, you can write $H = \sum_{j,k = 0}^{d-1}\alpha_{jk} X_d^j Z_d^k$, where $\alpha_{jk} \in \mathbb{C}$ and $|\alpha_{jk}|\leq \epsilon$ for any $\epsilon > 0$ (by [3]), with at least one such $\alpha_{ab}$ not equal to zero.
6. We can then choose $C$ an element from the Clifford group which maps $X_d^j Z_d^k$ to $Z_d$ under conjugation. Thus $C g^n C^\dagger = \exp(-iCHC^\dagger) = \exp(-i(\alpha_{ab}Z_d + \sum_{(j, k) \neq (a,b)} \alpha'_{jk} X_d^j Z_d^k))$, where $\alpha'$ is just a permutation of $\alpha$ and $\alpha_{ab} = \alpha'_{01}$.
7. Note that $Z_d$ satisfies $Z_d (X_d^u Z_d^v) = \omega^{u} (X_d^u Z_d^v) Z_d$. Let us define $g_\ell = Z_d^{-\ell} C g^n C^\dagger Z_d^{\ell} = \exp(-i(\alpha_{ab}Z_d + \sum_{(j, k) \neq (a,b)} \omega^{j\ell} \alpha'_{jk} X_d^j Z_d^k))$.
8. By the Baker-Cambel-Hausdorff theorem, since all $\alpha$ have been made arbitrarily close to the identity, we can evaluate the product of $g' = g_1 \times ... \times g_d$ to first order as $\exp(-i(d\times(\sum_{k} \alpha_{0k} Z^k) + (\sum_{\ell = 1}^d \omega^d)\times\sum_{j \neq 0}\sum_k \alpha_{jk}X_d^j Z_d^k))$. Summing over all routes of unity, for $d>1$ yields $g' = \exp(-i(d\times(\sum_{k\neq b} \alpha_{0k} Z^k))$. This is basically a decoupling sequence which decouples the non-diagonal elements.
9. As only diagonal matrices remain in the exponential, $g'$ must be diagonal. Further due to the restrictions on $\alpha'$ it necessarily has eigenvalues which are non-zero but proportional to $\epsilon$.
10. By varying $\epsilon$ and repeating the above process it should be possible to generate $d$ linearly independent gates: $g'_1 ... g'_d$, such that their product results in a diagonal gate with with irrational and incommensurate phases or an arbitrarily close approximation to one.
11. By the reference given in Mark Howard's answer this, together with the Clifford group, should suffice for approximate universality.

This post has been migrated from (A51.SE)

Comments

Why isn't this complete? If you flesh out the details in your vague steps (step 10 in particular), it seems like it might work.

This post has been migrated from (A51.SE)

---

@PeterShor: For exactly that reason: I haven't fleshed out all of the steps. I think it should work, but I acknowledge it is not rigorous. I'll see if I can flesh out 10.

This post has been migrated from (A51.SE)

---

Nice. This seems like a good approach.

This post has been migrated from (A51.SE)

---

I'm giving the bounty to this answer because I think the chances are that a proof along these lines will answer the question. The other answers are very useful as well.

This post has been migrated from (A51.SE)

---

@PeterShor: Thanks! I was feeling a bit guilty that my first answer was incorrect.

This post has been migrated from (A51.SE)

Answer 4

I think the following paper may contain the relevant constructions for proving qudit universality

http://dx.doi.org/10.1088/0305-4470/39/11/010

In particular, the comment at the end of section $4$ says that Controlled-phase $CZ$, Fourier transform $F$, and a diagonal gate $D$ with irrational and incommensurate phases gives approximate universality. (This is a sufficient condition on $D$ but I'm pretty sure it is not a necessary condition.)

If your $G$ is of the correct form (and diagonal gates would seem a natural choice) then the result applies

An alternative approach would be to create the ancilla states required for implementation of the qudit Toffoli, or directly using $G$ along with Cliffords to implement the Toffoli. It's hard to say whether this is possible without knowing more about $G$.

This post has been migrated from (A51.SE)

Comments

Welcome to the site, Mark!

This post has been migrated from (A51.SE)

---

Hi Mark. Thanks for your answer. Though I am interested in the most general case, I am particularly interested in a case where I know I have an infinite number of gates because it is generated by a gate with phases that are irrational multiples of $\pi$. However, the "irrational" gate is not diagonal in the computational basis, and so I can't apply the results you cite.

This post has been migrated from (A51.SE)