# Are these gate sets proven to be not universal?

I was reading the paper An introduction to measurement based quantum computation (Josza, 2005) and on page 13 they say the following:

Theorem: Any gate array using gates from the set $$\{CX,R_x(\theta) \text{ all } θ\}$$ or from the set $$\{CX,R_z(\theta) \text{ all } θ\}$$ can be implemented with just two measurement layers.

Remark: Neither of these sets is believed to be universal although it is known that $$CX$$ with all $$y$$-rotations is universal

Has anyone since proved/disproved these two gate sets are not universal?

• I haven't read those papers, specifically citation $[13]$, but when they say $y$-rotations, do they mean $R_x(\theta_1)$ followed by $R_z(\theta_2)$ operation (or the other way around)? Because otherwise, I don't see why rotation around the $Y$-axis is special. I am very curious about that remark! Commented Nov 14, 2023 at 8:47
• @FDGod It's just a normal $R_Y(\theta)$ operation. It's special because controlled-not picks out two special bases: $X$ and $Z$. To see that it's universal, you can prove that $Y$ rotations + controlled-not let you build controlled-$\sqrt{Y}$. In arxiv.org/pdf/quant-ph/0512058.pdf they argue that gate alone is universal. Commented Nov 14, 2023 at 9:10
• @DaftWullie I see. Thank you very much for your comment. Naively, I would have never guessed {Controlled-$\sqrt{Y}$} would be universal. Very interesting! Commented Nov 14, 2023 at 15:50
• I think it is controlled- $\sqrt{R_{Y}}$ and not controlled-$\sqrt{𝑌}$ as pointed out by @DaftWullie. Commented Nov 14, 2023 at 19:44

In fact, it is simple to see that $$CX$$ and $$R_z(\theta)$$ is not universal as both gates map computational basis states to computational basis states, up to a phase. An analogous argument applies to $$CX$$ and $$R_x(\theta)$$ by noting that $$CX$$ also permutes the $$X$$ eigenbasis.
There is another way to see that CNOT+ $$R_Y(\theta)$$ is universal while CNOT+ $$R_X(\theta)$$ or CNOT+ $$R_Z(\theta)$$ is not. The general mathematical result says that one has to satisfy Theorem 3.1 of https://arxiv.org/abs/quant-ph/0205115 for universal gate set with CNOT. Theorem reads - 'CNOT + any single qubit real gate that is basis changing after squaring is universal'.
One can show that only CNOT+ $$R_Y(\theta)$$ satisfies this condition.