9

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?

Peter LeFanu Lumsdaine
  • 103
  • 3
Ethan Davies
  • 768
  • 1
  • 8

2 Answers2

7

I think the authors haven't tried to prove it, hence the formulation.

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.

Markus Heinrich
  • 5,652
  • 11
  • 22
1

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.

R.G.J
  • 271
  • 1
  • 7