Restricting entries of unitary operators to real numbers and universal gate sets

Question

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?

Answer 1

There is A Simple Proof that Toffoli and Hadamard are Quantum Universal 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}}\}$.

Answer 2

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). 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.