How to decompose a unitary transform into two-level unitary matrices?

Question

I'm struggling to understand the process of how to decompose a unitary transform into two-level unitary matrices. I've been trying to understand the process as detailed in arXiv:1210.7366, but I don't get where those 2x2 matrices in the individual two-level matrices are coming from, or what P actually is. If anyone could walk me through a numerical example of decomposing for example, a 4x4 matrix into two-level unitary matrices, that'd be greatly appreciated!

Answer 1

The basic idea is to multiply $U$ on the left with $2\times 2$ unitaries until the identity is obtained. This method provides a sequence of gates $U_k$ such that $U_1\cdots U_n U=I$, which then gives you the decomposition of $U$ in terms of $2\times2$ unitaries: $U=U_1^\dagger \cdots U_n^\dagger$.

For example, suppose you start with $$U=\begin{pmatrix}1/2&\frac{1}{2\sqrt3}&\sqrt{2/3}\\-1/2&\sqrt3/2&0\\1/\sqrt2&1/\sqrt6&-1/\sqrt3\end{pmatrix}.$$ We start by finding a matrix which only mixes first and third row of $U$, with the goal of annihilating the $(3,1)$ element. In general, a matrix $U_1$ mixing only first and third column of $U$ has the form $$\begin{pmatrix}* & 0 & * \\ 0 &1&0\\ *&0&*\end{pmatrix}.$$ To send $U_{31}$ to zero essentially amounts to finding parameters $a,b$ such that $aU_{11}+b U_{31}=0$, which gives $a=-b U_{31}/U_{11}$ (the case $U_{11}=0$ can be handled separately). You then put the resulting $a,b$ in the third row of $U_1$, and then adjust the rest of the parameters in $U_1$ in order to make it into a unitary. This results in the following $U_1$: $$U_1=\begin{pmatrix} 1/\sqrt3 & 0 & \sqrt{2/3}\\ 0 & 1 & 0\\ -\sqrt{2/3} & 0 & 1/\sqrt3 \end{pmatrix}.$$ Then, $$U_1 U = \begin{pmatrix}\sqrt3/2 & 1/2 & 0 \\ -1/2 & \sqrt3/2 & 0 \\ 0 & 0 & -1\end{pmatrix}.$$ In this case we were lucky in that we obtained two zeros in one step, but this is only due to this particular choice of $U$. You now need to find some $U_2$ which only mixes the first two rows of $U$, that is, a matrix with the structure $$\begin{pmatrix}* & * & 0 \\ * &*&0\\ 0&0&1\end{pmatrix}.$$ To send to zero the $(2,1)$ element of $U_1 U$ we can use (again, focus on coefficients that send to zero the elements in the first column of $U_1U$, and put them in the second row of $U_2$, then filling out the rest to make $U_2$ unitary): $$U_2=\begin{pmatrix}-\sqrt3/2 & 1/2 & 0 \\ 1/2 & \sqrt3/2 & 0 \\ 0 & 0 & 1\end{pmatrix},$$ so that finally $$U_2U_1 U=\begin{pmatrix}-1&0&0\\0&1&0\\0&0&-1\end{pmatrix}.$$ Notice how some of the signs in the resulting matrix are wrong. This is because I didn't put much care in the signs of the matrices $U_i$. Following the more accurate prescription given in the paper (note how they also include the determinants in the expressions, and take care of the cases with complex numbers) you will always obtain the identity at the end.

Finally, it might be interesting to note that this is essentially the LU decomposition applied to the special case of a unitary matrix.

Answer 2

Their approach is more advanced than the simple one, described in the book "Quantum Computation and Quantum Information" by M. Nielsen and I. Chuang, section 4.5.1. It's better to understand it first. Basically we are just making zeros under diagonal step by step, where each step is the multiplication by some two-level unitary. Hence there are only $d(d-1)/2$ steps needed.

In the linked paper, $P$ is just a permutation of $d$ numbers $\{1,2,..,d\}$ represented as a tuple $(j_1, j_2, .. ,j_d)$. For a fixed $P$ we can take two consecutive numbers $j_k,j_{k+1}$ from the tuple $P$ by picking $k$ from the set $\{1,2,..,d-1\}$.