9
$\begingroup$

Let $E \in SU(2^k)$ be any entangling gate (for some $k \geq 2)$. Then my question is simply whether or not it is known that $SO(2) \cup \{ E \}$ is universal for $\mathsf{BQP}$?

Clearly it seems that this ought to be true, in light of the standard facts that any entangling gate with arbitrary single-qubit gates is universal, and that "real quantum computation" (computation with gates having only real entries) can also realize universality for $\mathsf{BQP}$.

I am just curious if anyone has seen the result made explicit that $SO(2) \cup \{ E \}$ is universal for any entangling gate $E$, or if this is something I'd have to prove myself?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ It's not a result I've seen. Have you tried looking through the set of papers that cite the universality of Toffoli+H result? If it's been published, it would have to appear in such a list. $\endgroup$
    – DaftWullie
    Commented Sep 19 at 6:43
  • $\begingroup$ I have perused a few of them, as well as those that cite the result by Shi: arxiv.org/abs/quant-ph/0205115. I'll keep looking $\endgroup$
    – Mary_Smith
    Commented Sep 24 at 2:10
  • $\begingroup$ Not sure if this works in general, but I believe the controlled-T gate works. We can apply a normal T-gate by controlling on an auxiliary qubit in the $|1\rangle$-state, and 4 controlled-T gates are equivalent to a CZ gate. I guess for this to work there should be some complex component in $E$ (so $E\not\in SO(2^k)$), I'm unsure of that though. $\endgroup$
    – nippon
    Commented Sep 24 at 6:54
  • $\begingroup$ SO(2) or O(2)? Note that SO(2) does not even contain the Hadamard gate. (This seems especially unclear in the light about your comment on "real quantum computation", so it is not even obvious if E is the Toffoli.) $\endgroup$
    – Norbert Schuch
    Commented Sep 24 at 8:45
  • $\begingroup$ Ah fair point. Though in SO(2) we do have the "Hadamard-like" gate $\frac{1}{\sqrt{2}}\begin{pmatrix} 1 & -1 \\ 1 & 1 \end{pmatrix}$. I think I'd like to restrict to SO(2) specifically. $\endgroup$
    – Mary_Smith
    Commented Sep 24 at 16:24

1 Answer 1

Reset to default
10
$\begingroup$

No. With the conventional notation of the Pauli basis, $SO(2) \cong U(1)$ rotations just constitute rotations around $Y$, i.e., these gates are parameterized by the set $\{e^{i \theta Y} : \theta \in [0, 2\pi)\}$. For ease, let us redefine our basis so that we instead have rotations around the $Z$ axis. One can choose $E$ to be $CZ$, which is entangling. However, it commutes trivially with the above representation of $SO(2)$ rotations. Given that $\langle \{e^{i \theta Z} : \theta \in [0, 2\pi)\}, E \rangle$ is Abelian, it cannot be universal.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Instead of changing to the Z basis, one could also simply consider $e^{i\theta Y\otimes Y}$ as the entangling gate (for a non-nonsuitable $\theta$). $\endgroup$
    – Norbert Schuch
    Commented Sep 29 at 11:14
  • $\begingroup$ True, any entangling gate that respects Abelianity suffices in this argument. I chose CZ purely because it is a conventional gate. $\endgroup$
    – Rohan Mehta
    Commented Sep 29 at 15:45
  • $\begingroup$ The reason for suggesting this is mostly that it avoids having to change to the Z basis, which is potentially suspicious, or rather requires extra care. (After all, the basis change will get us out of SO(2), so one has to be careful that this does not break the argument; if you use $e^{i\theta Y\otimes Y}$, or e.g. instead transform CZ into the Y basis, you don't have this issue. $\endgroup$
    – Norbert Schuch
    Commented Sep 29 at 19:57
  • $\begingroup$ @NorbertSchuch The basis change is synonymous with saying that the copy of SO(2) in SU(2) described by $Y$ axis rotations is unitarily equivalent to the copy of SO(2) described by $Z$ axis rotations. We don't leave SO(2), just change representations. $\endgroup$
    – Rohan Mehta
    Commented Sep 30 at 3:57
  • $\begingroup$ This should probably be a different question, but should we restrict the notion of an entangling gate to be relative to the product states that are possible from the gate set? In that case this C-Z would only ever act as a global phase and not be entangling. $\endgroup$
    – Ethan Davies
    Commented Sep 30 at 9:36

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