<p>In addition to the paper Martin pointed you to, there was an earlier paper by Terry Rudolph and Lov Grover showing that a 2 rebit gate is universal for quantum computing (see <a href="http://arxiv.org/abs/quant-ph/0210187" rel="noreferrer">quant-ph/0210187</a>). The gate has all real enteries, and in case you are unaware rebits are qubits where the amplitudes are restricted to real numbers. This may be the source of the claim. The gate in question described in the paper is a controlled Y rotation. </p>

<p>It is worth noting that such a controlled-Y gate can be created from Y-rotations and controlled-Z gates as follows: $G(\theta) = Y_2(\frac{\theta}{2}) CZ_{12} Y_2(\frac{\theta}{2}) CZ_{12}$. Note that a Y-rotation is exactly the type of rotation described in your question, while controlled-Z gates has entries only +1 and -1.</p>

CC BY-SA 3.0
2011-05-22T15:47:45.700Z
2011-05-22T15:47:45.700Z
Joe Fitzsimons
<p>There is <a href="http://arxiv.org/abs/quant-ph/0301040" rel="noreferrer">A Simple Proof that Toffoli and Hadamard are Quantum Universal</a> by Dorit Aharonov which first shows how complex amplitudes can be simulated by real amplitudes over a larger Hilbert space with one more qubit. </p>

<p>"This is done by adding one extra qubit
to the circuit, the state of which indicates whether
the system’s state is in the real or imaginary part of
the Hilbert space, and replacing each complex gate
$U$ operating on $k$ qubits by its <em>real version</em>, denoted
$\tilde{U}$, which operates on the same $k$ qubits plus the
extra qubit. $\tilde{U}$ is defined by:</p>

<p>$\tilde{U}|i\rangle |0\rangle = [Re(U)|i\rangle]|0\rangle + [Im(U)|i\rangle]|1\rangle$<br>
$\tilde{U}|i\rangle |1\rangle = -[Im(U)|i\rangle]|0\rangle + [Re(U)|i\rangle]|1\rangle$"<br></p>

<p>Secondly, she proofs the universality of the {Hadamard,Toffoli} gate set, which has only real amplitudes $\{0,1,\pm\frac{1}{\sqrt{2}}\}$.</p>

CC BY-SA 3.0
2011-05-20T00:44:50.627Z
Thanks Martin! However, it seems to me that Aharonov's technique for replacing complex unitaries with real unitaries is not the same way that Adleman/BV considered (for I can find no evidence that they thought this way). But Aharanov's result is interesting and very nice.
Henry Yuen
CC BY-SA 3.0
2011-05-22T18:07:16.540Z
I am fairly sure that Adleman/BV used a construction that doubled the number of qubits rather than just adding one, but that worked similarly.
Peter Shor 
CC BY-SA 3.0
2011-05-22T18:26:42.897Z
@Peter: Rudolph and Grover's construction works that way, using two rebits to encode a single qubit: quant-ph/0210187.
Joe Fitzsimons
CC BY-SA 3.0
2011-05-19T08:46:40.497Z
2011-05-19T08:57:04.143Z
2011-05-19T08:57:04.143Z
Martin Schwarz
<p>In Bernstein and Vazirani's seminal paper "Quantum Complexity Theory", they show that a $d$-dimensional unitary transformation can be efficiently approximated by a product of what they call "near-trivial rotations" and "near-trivial phase shifts". </p>

<p>"Near-trivial rotations" are $d$-dimensional unitary matrices that act as the identity on all but 2 dimensions, but act as a rotation in the plane spanned by those two dimensions (i.e. has a 2x2 submatrix of the form:</p>

<p>$
 \begin{pmatrix}
  \cos{\theta} &amp; -\sin{\theta} \\
  \sin{\theta} &amp; \cos{\theta} \\
 \end{pmatrix}
$</p>

<p>for some $\theta$).</p>

<p>"Near-trivial phase shifts" are $d$-dimensional unitary matrices that act as the identity on all but 1 dimension, but apply a factor of $e^{i\theta}$ for some $\theta$ to that one dimension.</p>

<p>Furthermore, they show that only one rotation angle is needed (for both the rotation and phase shift unitaries), given that the angle is an irrational multiple of $2\pi$ (BV set the angle to $2\pi\sum_{j=1}^{\infty}{2^{-2^j}}$. </p>

<p>Subsequent papers on quantum complexity theory (like that by Adleman et al or Fortnow and Rogers) claim that the B-V result implies that universal quantum computation can be accomplished with unitary operators whose entries are in $\mathbb{R}$. </p>

<p>How does this follow? I can understand that a product of near-trivial rotation matrices will give you a unitary matrix with real entries, but what about the phase shift matrices?</p>

<p>That is: if you are only able perform near-trivial rotations, and phase shift matrices where the entries of the matrix are either $0,\pm 1$, can we efficiently approximate all other phase shift matrices? </p>

<p>I suspect that this implication is not immediately obvious, and the proper proof for it would resemble the proof that Deutsch's Toffoli-like gate is universal - or am I missing something very obvious?</p>

<quantum-computing><linear-algebra><universal-computation>
Restricting entries of unitary operators to real numbers and universal gate sets
Henry Yuen
# Restricting entries of unitary operators to real numbers and universal gate sets

(Asked by: username_0 on 2011-05-19)

In Bernstein and Vazirani's seminal paper "Quantum Complexity Theory", they show that a $d$-dimensional unitary transformation can be efficiently approximated by a product of what they call "near-trivial rotations" and "near-trivial phase shifts".

"Near-trivial rotations" are $d$-dimensional unitary matrices that act as the identity on all but 2 dimensions, but act as a rotation in the plane spanned by those two dimensions (i.e. has a 2x2 submatrix of the form:

$
\begin{pmatrix}
\cos{\theta} & -\sin{\theta} \\
\sin{\theta} & \cos{\theta} \\
\end{pmatrix}
$

for some $\theta$).

"Near-trivial phase shifts" are $d$-dimensional unitary matrices that act as the identity on all but 1 dimension, but apply a factor of $e^{i\theta}$ for some $\theta$ to that one dimension.

Furthermore, they show that only one rotation angle is needed (for both the rotation and phase shift unitaries), given that the angle is an irrational multiple of $2\pi$ (BV set the angle to $2\pi\sum\_{j=1}^{\infty}{2^{-2^j}}$.

Subsequent papers on quantum complexity theory (like that by Adleman et al or Fortnow and Rogers) claim that the B-V result implies that universal quantum computation can be accomplished with unitary operators whose entries are in $\mathbb{R}$.

How does this follow? I can understand that a product of near-trivial rotation matrices will give you a unitary matrix with real entries, but what about the phase shift matrices?

That is: if you are only able perform near-trivial rotations, and phase shift matrices where the entries of the matrix are either $0,\pm 1$, can we efficiently approximate all other phase shift matrices?

I suspect that this implication is not immediately obvious, and the proper proof for it would resemble the proof that Deutsch's Toffoli-like gate is universal - or am I missing something very obvious?

**Tags:** quantum-computing, linear-algebra, universal-computation


---

## 2 answers

### Answer by username_2 on 2011-05-19. Score: 15 | Accepted answer

There is [A Simple Proof that Toffoli and Hadamard are Quantum Universal](http://arxiv.org/abs/quant-ph/0301040) by Dorit Aharonov which first shows how complex amplitudes can be simulated by real amplitudes over a larger Hilbert space with one more qubit.

"This is done by adding one extra qubit
to the circuit, the state of which indicates whether
the system’s state is in the real or imaginary part of
the Hilbert space, and replacing each complex gate
$U$ operating on $k$ qubits by its *real version*, denoted
$\tilde{U}$, which operates on the same $k$ qubits plus the
extra qubit. $\tilde{U}$ is defined by:

$\tilde{U}|i\rangle |0\rangle = [Re(U)|i\rangle]|0\rangle + [Im(U)|i\rangle]|1\rangle$  
$\tilde{U}|i\rangle |1\rangle = -[Im(U)|i\rangle]|0\rangle + [Re(U)|i\rangle]|1\rangle$"

Secondly, she proofs the universality of the {Hadamard,Toffoli} gate set, which has only real amplitudes $\{0,1,\pm\frac{1}{\sqrt{2}}\}$.

> **Comments:**
> **username_0**: Thanks Martin! However, it seems to me that Aharonov's technique for replacing complex unitaries with real unitaries is not the same way that Adleman/BV considered (for I can find no evidence that they thought this way). But Aharanov's result is interesting and very nice.  
> **username_3**: I am fairly sure that Adleman/BV used a construction that doubled the number of qubits rather than just adding one, but that worked similarly.  
> **username_1**: @Peter: Rudolph and Grover's construction works that way, using two rebits to encode a single qubit: quant-ph/0210187.  

---

### Answer by username_1 on 2011-05-22. Score: 10

In addition to the paper Martin pointed you to, there was an earlier paper by Terry Rudolph and Lov Grover showing that a 2 rebit gate is universal for quantum computing (see [quant-ph/0210187](http://arxiv.org/abs/quant-ph/0210187)). The gate has all real enteries, and in case you are unaware rebits are qubits where the amplitudes are restricted to real numbers. This may be the source of the claim. The gate in question described in the paper is a controlled Y rotation.

It is worth noting that such a controlled-Y gate can be created from Y-rotations and controlled-Z gates as follows: $G(\theta) = Y\_2(\frac{\theta}{2}) CZ\_{12} Y\_2(\frac{\theta}{2}) CZ\_{12}$. Note that a Y-rotation is exactly the type of rotation described in your question, while controlled-Z gates has entries only +1 and -1.


---

