11

Within the theory of quantum gates, a common pair of single-qubit phase gates are the $P(\pi/2)=S$ and $P(\pi/4)=T$ gates, with

$$S= \begin{bmatrix} 1 & 0 \\ 0 & i \end{bmatrix},\:T = \begin{bmatrix} 1 & 0 \\ 0 & e^{i \frac{\pi}{4}} \end{bmatrix}.$$

We have, for example, $T^4=S^2=Z$.

See this Wikipedia article.

Within the theory of presentations of $\mathrm{PSL}(2, \mathbb Z)$ (the modular group), we have the two generators, $S$ and $T$, with:

$$S : z\mapsto -\frac1z,\:T : z\mapsto z+1.$$

We have, for example, $S^2=(ST)^3=I$

See this Wikipedia article.

But, in matrix form, these generators do not look like those above:

$$S = \begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix}, \: T = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}.$$

Are the $S$ and $T$ labels used in quantum computation just coincidentally the same as those used to describe generators of the modular group? Or is there some deeper relation that I'm not immediately seeing? What is the origin of $S$ and $T$ gates used in quantum computation?

Mark Spinelli
  • 11,947
  • 2
  • 19
  • 65
  • 2
    Thanks... I can agree that there is a relation and the folks working on these back in the day certainly might have had something in mind, but my knowledge of group theory is not strong enough to follow. Just naively, as matrices $S$ in group-theory land looks like $-iY$ in quantum-computing land, while $T$ in group-theory land is not even unitary. Plus they obey different relations (e.g. we have in group-theory land that $S^2=(ST)^3=I$, but this is not so with quantum gates AFAICT.) – Mark Spinelli Jun 14 '21 at 14:01
  • 6
    I think this is merely a coincidence of notation. I think that the more interesting aspects of $S$, $T$, (and if you also throw in $H$) is that they generate a so-called $\mathcal{S}$-arithmetic subgroup of the projective unitary group. The astonishing property of this such subgroups is not only that they generate a topologically dense subgroup (which enables universal quantum computation) but that short approximating words exist which means that you can always approximate (up to $\epsilon$) an element of $PU(2)$ with a word of length $O(\log(1/\epsilon)$ in the generators $H, S,$ and $T$. – Condo Jun 14 '21 at 15:12
  • @MarkS yea I think I misread the question, I was just showing that the equivalence of matrix representation and "algebraic representation" for the projective matrices, which has nothing to do with the unitaries using in QC. – glS Jun 14 '21 at 16:09
  • 1
    You should only look at the group relations not about unitarity in the modular group's defining representation. The more relevant representation for the modular group is the one that comes secondarily through putting a Conformal Field Theory on a torus. – AHusain Jun 14 '21 at 18:12
  • @Condo, can you explain further? I read your statement as a single-qubit corollary of the Solovay-Kitaev theorem. – Mark Spinelli Jun 16 '21 at 01:27
  • 1
    @MarkS it is in fact a strengthening of Solovay-Kitaev because the exponent $c$ in $O(\log^c(1/\epsilon))$ (from Solovay-Kitaev) is equal to $1$ for such gate sets. – Condo Jun 16 '21 at 13:53
  • 1
    For more information, I would recommend reading https://arxiv.org/pdf/1704.02106.pdf or this hand written letter by Peter Sarnak to Scott Aaronson and Andy Pollington https://publications.ias.edu/sites/default/files/Letter%20-%20golden%20gates%20march_0.pdf – Condo Jun 16 '21 at 13:56
  • 1
    that letter from Sarnak is awesome! – Mark Spinelli Jun 16 '21 at 15:19
  • I should also mention the talk given by Sarnak back in 2015 at IQC https://www.youtube.com/watch?v=oeBFeHkUapg&t=2488s – Condo Jun 16 '21 at 16:23
  • 1
    I guess that the start of some of the notation was here: https://arxiv.org/abs/quant-ph/9503016. This contains a lot of the proofs about universality of the gate model (but not the finite gate set part), and they're using a lot of different letters for all sorts of different gates. Their use of $S$ was as a general phase gate (i.e. not a fixed phase), and so things may have evolved from there. If so, the relation is just coincidental. That said, their use of $T$ is completely different! – DaftWullie Jun 17 '21 at 07:09

1 Answers1

4

I believe Neilsen and Chuang were the first to use this particular notation. Previous work had referred to $S$ and $T$ as $\sigma_z^{1/2}$ and $\sigma_z^{1/4}$, respectively (Boykin et al. 1999). The use of $S$ may have been inspired by Deutsch's "S-matrix" (Deutsch 1989), though this was really a root-of-NOT gate. The use of $T$ may have been inspired by the transformation "T" matrix of a universal beam splitter (DiVincenzo 1989), which is equivalent to the modern $T$ matrix, up to a global phase, for certain parameter values.

Brian R. La Cour
  • 506
  • 4
  • 7