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?


2 Answers 2


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}}\}$.

  • $\begingroup$ 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. $\endgroup$
    – Henry Yuen
    Commented May 20, 2011 at 0:44
  • 1
    $\begingroup$ 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. $\endgroup$ Commented May 22, 2011 at 18:07
  • $\begingroup$ @Peter: Rudolph and Grover's construction works that way, using two rebits to encode a single qubit: quant-ph/0210187. $\endgroup$ Commented May 22, 2011 at 18:26

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.


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.