The typically used gate set for quantum computation is composed of the single qubits Cliffords (Paulis, H and S) and the controlled-NOT and/or controlled-Z.

To go beyond Clifford we like to have full single qubit rotations. But if we are being minimal, we just go for T (the fourth root of Z).

This particular form of the gate set pops up everything. Such as IBM’s Quantum Experiment p, for example.

Why these gates, exactly? For example, H does the job of mapping between X and Z. S similarly does the job of mapping between Y and X, but a factor of $-1$ also gets introduced. Why don’t we use a Hadamard-like unitary $(X+Y)/\sqrt{2}$ instead of S? Or why don’t we use the square root of Y instead of H? It would be equivalent mathematically, of course, but it would just seem a bit more consistent as a convention.

And why is our go-to non-Clifford gate the fourth root of Z? Why not the fourth root of X or Y?

What historical conventions led to this particular choice of gate set?

  • 1
    $\begingroup$ Would the answer be the Gottesman-Knill theorem? Stick with gates that allow efficient simulation of a quantum circuit on a classical computer? $\endgroup$
    – Andrew O
    Apr 4 '18 at 2:56
  • $\begingroup$ @AndrewO I guess Gottesman-Knill would explain the strong Clifford bias. But I still don’t get why our standard set of gates are the ones that they are, rather than other more symmetric seeming choices. $\endgroup$ Apr 4 '18 at 5:47

Anyone who has written a paper, and asked themselves whether they could improve the notation, or present the analysis a bit differently to make it more elegant, is familiar with the fact that choices of notation, description, and analysis can be an accident — chosen without deep motivations. There's nothing wrong with it, it just doesn't have a strong justification to be a particular way. In large communities of people more concerned (possibly with reason) with getting things done rather than presenting the cleanest possible picture, this is going to happen all the time.

I think that the ultimate answer to this question is going to be along these lines: it is mostly a historical accident. I doubt that there are any deeply considered reasons for the gate-sets being as they are, any more than there are deeply considered reasons why we talk about the Bell state $\lvert \Phi^+ \rangle = ( \lvert 00 \rangle + \lvert 11 \rangle ) \big/ \sqrt 2$ somewhat more often than the state $\lvert \Psi^- \rangle = ( \lvert 01 \rangle - \lvert 10 \rangle ) \big/ \sqrt 2$.

But we can still consider how the accident came about, and whether there is something we can learn about systematic ways of thinking which might have led us there. I expect that the reasons ultimately come from the cultural priorities of computer scientists, with both deep and superficial biases playing a role in how we describe things.

A digression on Bell states

If you'll bear with me, I'd like to dwell on the example of the two Bell states $\lvert \Phi^+ \rangle$ and $\lvert \Psi^- \rangle$ as an indicative example of how an ultimately arbitrary convention can come about by accident, in part because of biases which do not have deep mathematical roots.

One obvious reason for preferring $\lvert \Phi^+ \rangle$ over $\lvert \Psi^- \rangle$ is that the former is more obviously symmetric. As we add the two components for $\lvert \Phi^+ \rangle$, there is no clear need to defend why we write it as we do. In contrast, we could just as easily define $\lvert \Psi^- \rangle = (\lvert 10 \rangle - \lvert 01 \rangle) \big/ \sqrt 2$ with the opposite sign, which is no better or worse motivated than the choice $\lvert \Psi^- \rangle = (\lvert 01 \rangle - \lvert 10 \rangle) \big/ \sqrt 2$. This makes it feel as though we are making more arbitrary choices when defining $\lvert \Psi^- \rangle$.

Even the choice of basis is somewhat flexible in the case of $\lvert \Phi^+ \rangle$: we can write $\lvert \Phi^+ \rangle := (\lvert ++ \rangle + \lvert -- \rangle)\big/\sqrt 2$ and obtain the same state. But things start going a little worse if you start considering the eigenstates $\lvert \pm i \rangle := (\lvert 0 \rangle \pm i \lvert 1 \rangle)\big/\sqrt 2$ of the $Y$ operator: we have $\lvert \Phi^+ \rangle = (\lvert +i \rangle\lvert -i \rangle + \lvert -i \rangle \lvert +i \rangle)\big/\sqrt 2$. This still looks pretty symmetric, but it becomes clear that our choice of basis plays a non-trivial role in how we define $\lvert \Phi^+ \rangle$.

The joke is on us. The reason why $\lvert \Phi^+ \rangle$ seems "more symmetric" than $\lvert \Psi^- \rangle$ is because $\lvert \Psi^- \rangle$ is literally the least symmetric two-qubit state, and this makes it better motivated than $\lvert \Phi^+\rangle$ instead of less motivated. The $\lvert \Psi^- \rangle$ state is the unique antisymmetric state: the unique state which is the $-1$ eigenvector of the SWAP operation, and therefore implicated in the controlled-SWAP test for qubit state distinguishability, among other things.

  • We can describe $\lvert \Psi^- \rangle$ up to a global phase as $(\lvert \alpha \rangle \lvert \alpha^\perp \rangle - \lvert \alpha^\perp \rangle \lvert \alpha \rangle)\big/\sqrt 2$ for literally any single-qubit state $\lvert \alpha \rangle$ and orthogonal state $\lvert \alpha^\perp \rangle$, meaning that the properties which make it interesting are independent of the choice of basis.
  • Even the global phase which you use to write the state $\lvert \alpha^\perp \rangle$ doesn't affect the definition of $\lvert \Psi^-\rangle$ up to more than a global phase. The same isn't true of $\vert \Phi^+\rangle$: as an exercise for the reader, if $\lvert 1' \rangle = i \lvert 1 \rangle$, then what is $(\lvert 00 \rangle + \lvert 1' 1' \rangle)\big/\sqrt 2$?

Meanwhile, $\lvert \Phi^+ \rangle$ is just one maximally entangled state in the three-dimensional symmetric subspace on two qubits — the subspace of $+1$ eigenvectors of the SWAP operation — and therefore no more distinguished in principle than, say, $\lvert \Phi^- \rangle \propto \lvert 00 \rangle - \lvert 11 \rangle$.

After learning a thing or two about the Bell states, it becomes clear that our interest in $\lvert \Phi^+ \rangle$ in particular is motivated only by a superficial symmetry of notation, and not any truly meaningful mathematical properties. It is certainly a more arbitrary choice than $\lvert \Psi^- \rangle$. The only obvious motivation for preferring $\lvert \Phi^+ \rangle$ are sociological reasons having to do with avoiding minus signs and imaginary units. And the only justifiable reason I can think of for that are cultural: specifically, in order to better accomodate students or computer scientists.

Who ordered CNOT?

You ask why we don't talk more about $(X + Y)\big/\sqrt 2$. To me the more interesting question that you also ask: we do we talk so much about $H = (X + Z)\big/\sqrt 2$, when $\sqrt Y$ does many of the same things? I have seen talks given by experimental optical physicists to students, who even describe performing $\sqrt Y$ on a standard basis state as performing a Hadamard gate: but it was a $\sqrt Y$ gate that was actually more natural for him. The operator $\sqrt Y$ is also more directly related to the Pauli operators, obviously. A serious physicist might consider it curious that we dwell so much on the Hadamard instead.

But there is a bigger elephant in the room — when we talk about CNOT, why are we talking about CNOT, instead of another entangling gate $\mathrm{CZ} = \mathrm{diag}(+1,+1,+1,-1)$ which is symmetric on its tensor factors, or better yet $U = \exp(-i \pi (Z \otimes Z)/2)$ which is more closely related to the natural dynamics of many physical systems? Not to mention a unitary such as $U' = \exp(-i \pi (X \otimes X)/2)$ or other such variants.

The reason, of course, is that we are explicitly interested in computation rather than physics per se. We care about CNOT because how it transforms the standard basis (a basis which is preferred not for mathematical or physical reasons, but for human-centered reasons). The gate $U$ above is slightly mysterious from the point of a computer scientist: it is not obvious on the surface of it what it is for, and worse, it is full of icky complex coefficients. And the gate $U'$ is even worse. By contrast, CNOT is a permutation operator, full of 1s and 0s, permuting the standard basis in a way which is obviously relevant to the computer scientist.

Though I'm making a bit of fun here, in the end this is what we're studying quantum computation for. The physicist can have deeper insights into the ecology of the elementary operations, but what the computer scientist cares about at the end of the day is how primitive things can be composed into comprehensible procedures involving classical data. And that means not caring too much about symmetry on the lower logical levels, so long as they can get what they want out of those lower levels.

We talk about CNOT because it is the gate that we want to spend time thinking about. From a physical perspective gates such as $U$ and $U'$ as above are in many cases the operations we would think about for realising CNOT, but the CNOT is the thing that we care about.

Deep, and not so deep, reasons to prefer the Hadamard gate

I expect that the priorities of computer scientists motivate a lot of our conventions, such as why we talk about $(X + Z)\big/\sqrt 2$, instead of $\sqrt Y \propto (\mathbb 1 - i Y)\big/\sqrt 2$.

The Hadamard operation is already slightly scary to computer scientists who are not already acquainted with quantum information theory. (The way it is used sounds like non-determinism, and it even uses irrational numbers!) But once a computer scientist gets past the initial revulsion, the Hadamard gate does have properties that they can like: at least it only involves real coefficients, it is self-inverse, and you can even describe the eigenbasis of $H$ with just real coefficients.

One way in which the Hadamard often arises is in describing toggling between the standard basis $\lvert 0 \rangle, \lvert 1 \rangle$ and 'the' conjugate basis $\lvert + \rangle, \lvert - \rangle$ (that is to say, the eigenbasis of the $X$ operator, as opposed to the $Y$ operator) — the so-called 'bit' and the 'phase' bases, which are two conjugate bases that you can express using only real coefficients. Of course, $\sqrt Y$ also transforms between these bases, but also introduces a non-trivial transformation if you perform it twice. If you want to think of "toggling between two different bases in which you might store information", the Hadamard gate is better. But — this can only be defensible if you think it is important specifically to have

  • a gate $H$ transforming between the standard basis and the very specific basis of $\lvert + \rangle, \lvert - \rangle$;
  • if you care specifically about $H$ having order $2$.

You might protest and say that it is very natural to consider toggling between the 'bit' and 'phase' bases. But where did we get this notion of two specific bases for 'bit' and 'phase', anyway? The only reason why we single out $\lvert + \rangle, \lvert - \rangle$ as 'the' phase basis, as opposed for instance to $\lvert +i \rangle, \lvert -i \rangle$, is because it can be expressed with only real coefficients in the standard basis. As for preferring an operator with order $2$, to mesh with the notion of toggling, this seems to indicate a particular preference for considering things by 'flips' rather than reversible changes of basis. These priorities smack of the interests of computer science.

Unlike the case between $\lvert \Phi^+ \rangle$ versus $\lvert \Psi^- \rangle$, the computer scientist does have one really good high-level argument for preferring $H$ over $\sqrt Y$: the Hadamard gate is the unitary representation of the boolean Fourier transform (that is, it is the quantum Fourier transform on qubits). This is not very important from a physical perspective, but it is very helpful from a computational perspective, and a very large fraction of theoretical results in quantum computation and communication ultimately rest on this observation. But the boolean Fourier transform already bakes in the asymmetries of computer science, in pre-supposing the importance of the standard basis and in using only real coefficients: an operator such as $(X + Y)\big/\sqrt 2$ would never be considered on these grounds.

Diagonal argument

If you're a computer scientist, once you have Hadamard and CNOT, all that's left is to get those pesky complex phases sorted as an afterthought. These phases are extremely important, of course. But just the way we talk about relative phases reveals a discomfort with the idea. Even describing the standard basis as the 'bit' basis, for storing information, puts a strong emphasis that whatever 'phase' is, it's not the usual way that you would consider storing information. Phases of all sorts are something to be dealt with after the 'real' business of dealing with magnitudes of amplitudes; after confronting the fact that one can store information in more than one basis. We barely talk at all about even purely imaginary relative phases if we can help it.

One can cope with relative phases pretty easily using diagonal operators. These have the advantage of being sparse (with respect to the standard basis...) and of only affecting the relative phase, which is after all the detail which we're trying to address at this stage. Hence $T \propto \sqrt[4]Z$. And once you've done that, why do more? Sure, we could as easily consider arbitrary $X$ rotations (and because of Euler decomposition, we do play some lip-service to these operations) and arbitrary $Y$ rotations, which would motivate $\sqrt[4]X$ and $\sqrt[4]Y$. But these don't actually add anything of interest for the computer scientist, who considers the job done already.

And not a moment too soon — because computer scientists don't really care about precisely what the primitive operations being used are as soon as they can justify move on to something higher-level.


I don't think there is likely to be any very interesting physically-motivated reason why we use a particular gate-set. But it is certainly possible to explore the psychologically-motivated reasons why we do. The above is a speculation in this direction, informed by long experience.

  • $\begingroup$ It seems you are arguing for two things, namely 1) the convention is an 'accident' and 2) the convention is useful for applications in CS. I'm not sure whether you indeed claim both and how this relates to eachother. Perhaps you can high-light this in your summary. $\endgroup$ Apr 4 '18 at 9:33
  • 4
    $\begingroup$ @Discretelizard: I am claiming something a bit subtler: the convention is an accident, because the computer scientist is more concerned with expediency for other purposes than with mathematical symmetry. The physicist and the mathematician both care about symmetries more than the computer scientist does, so what we've ended up with something that looks a little arbitrary. The specific arbitrary thing we've ended up with was itself steered by biases from computer science, but superficial biases rather than meaningful ones. $\endgroup$ Apr 4 '18 at 11:30
  • 7
    $\begingroup$ Indeed, before the arrival of computer scientists, the physicists' preferred maximally entangled state was the singlet state, a.k.a. $|\Psi^-\rangle$. See e.g. all the 20th century papers about Bell's inequalities. $\endgroup$ Apr 4 '18 at 12:55

Your Answer

