9
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ 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! $\endgroup$
    – FDGod
    Commented Nov 14, 2023 at 8:47
  • 5
    $\begingroup$ @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. $\endgroup$
    – DaftWullie
    Commented Nov 14, 2023 at 9:10
  • $\begingroup$ @DaftWullie I see. Thank you very much for your comment. Naively, I would have never guessed {Controlled-$\sqrt{Y}$} would be universal. Very interesting! $\endgroup$
    – FDGod
    Commented Nov 14, 2023 at 15:50
  • $\begingroup$ I think it is controlled- $\sqrt{R_{Y}}$ and not controlled-$\sqrt{𝑌}$ as pointed out by @DaftWullie. $\endgroup$
    – R.G.J
    Commented Nov 14, 2023 at 19:44

2 Answers 2

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.