Which gate should one add to CNOT in order to have a universal set for Quantum Computing?

Question

I have recently encountered the paper Both Toffoli and Controlled-NOT need little help to do universal quantum computation by Yaoyun Shi.

I'm having trouble understanding the proof of theorem 3.1 There, it's stated that the operator $U$ can be considered a general rotation. In my opinion there's a lot information missing in that statement. I believe the appropriate statement would be that the 2-dimensional operator $S$ is a general 2-dimensional rotation. If so, I am not obtaining the same results for the eigen(values&vectors).

My question arises from studying the proof of Theorem 3.1.

I would like to know how to compute the eigenvalues of an operator defined as: $U:=S\otimes S \cdot CNOT$ where $S$ is an operator whose squared $S^2$ does not preserve the computational basis. In the paper it's said that such matrix $U$ can be, without loss of genererality, a general rotation of angle $\theta$. What does that mean? How does one compute it's eigenvalues? Wouldn't it make more sense that $S=\begin{bmatrix} cos(\theta) & -sin(\theta) \\ sin(\theta) & cos(\theta) \end{bmatrix}$ actually is a general rotation of angle $\theta$?

I would appreciate some help in order to fully understand the theorem and the proof.

---

Cross-posted on physics.SE

Answer 1

I think there's a typo here. I think it's supposed to say that without loss of generality $S$ is a rotation by angle $\theta$ (and hence your proposed parametrisation of $S$ is correct). The most direct evidence I have for this is the eigenvalues of $U$: if $U$ were a rotation by an angle $\theta$, its eigenvalues would be of the form $e^{\pm i\theta}$.

Given this change, how does the calculation proceed? First, verify that the two eigenvectors you're given really are eigenvectors with eigenvalue 1. There are some tricks that help with this. Personally, I rewrote the first eigenvector (for example) as $$ (I\otimes H)(|01\rangle+|10\rangle)/\sqrt{2}. $$ Then I applied $U$ to this, and noted that:

1. if I commute Hadamard through controlled-not, it changes into controlled-phase
2. if I commute Hadamard through $S(\theta)$, I have $S(\theta)H=HS(-\theta)$ because $HYH=-Y$.
3. $S(\theta)\otimes S(-\theta)(|01\rangle+|10\rangle)=(|01\rangle+|10\rangle)$.

So, let's assume we know that two of the eigenvalues of $U$ are 1. What are the others? We can easily calculate that $\text{det}(U)=1$ since $\text{det}(S)=1$. This means that our other two eigenvalues are of the form $e^{\pm i\alpha}$ since this is the only way they can multiply together to give 1. Then we calculate the trace, which is equal to the sum of the eigenvalues: $$ 2+2\cos\alpha=4\cos^4\theta $$ (I just brute-forced this in Mathematica.) This is just the same as $$ 4\cos^2\frac{\alpha}{2}=4\cos^4\theta. $$ Since we're looking for $\pm\alpha$ solutions. Taking the square root leaves us where you need to be.

The second eigenvector: If you look at the second stated eigenvector, it only appears to be a 1-qubit state. So there must be another typo. I believe it should be $$ \sin(\theta)|0\rangle|-\rangle-|1\rangle(\sin(\theta)|+\rangle+2\cos(\theta)|-\rangle) $$

---

Here are the calculations I did in Mathematica. First, define the matrix and verify the first eigenvector (should give all-zeros vector):

rootU = KroneckerProduct[{{Cos[q], -Sin[q]}, {Sin[q], 
      Cos[q]}}, {{Cos[q], -Sin[q]}, {Sin[q], Cos[q]}}].{{1, 0, 0, 
     0}, {0, 1, 0, 0}, {0, 0, 0, 1}, {0, 0, 1, 0}};
U = rootU.rootU;
(U - IdentityMatrix[4]).{1, -1, 1, 1} // FullSimplify

The problem is if you just ask it to solve for the two eigenvectors of +1 eigenvalue, it doesn't know how to pick them within the degenerate subspace. So, we help. Remove the one eigenvector we already know about, so that there is only one eigenvalue of 1:

V = U - {{1, -1, 1, 1}, -{1, -1, 1, 1}, {1, -1, 1, 1}, {1, -1, 1, 1}}/
    4;
-(Sin[q] - 2 Cos[q]) Eigenvectors[V, 1] // FullSimplify

The form of the other two eigenvalues does not seem to drop out nicely, which is why I went the direction I did to reproduce the results of the paper.