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

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!

• what do you mean by "two level unitary"? Oct 21, 2019 at 17:36
• This is how it's defined in the PDF I linked above: "Recall that a two-level d×d unitary matrix is a unitary matrix obtained from the d×d identity matrix I_d by changing a 2×2 principal submatrix. It is well known that every d×d unitary matrix can be decomposed into the product of no more than d(d−1)/2 two-level unitary matrices." Oct 21, 2019 at 18:10
• what's the difference between this and the classical Reck et al. 1994 method to decompose unitaries as sequence of 2x2 ones?
– glS
Oct 21, 2019 at 22:31

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.

• Hi, thanks for the very detailed reply, I really appreciate it! If I could ask you a couple of followup questions, that'd be awesome. 1. Solving the parameter equation, is this just taking educated guesses at the values of a and b until we have a pair that fit, since we only have a single equation with 2 parameters? 2. In the paper I linked, in page 2, in the Step 1 section, it says that det(U_1) = u_bar; how is that calculated when we need u_bar to make U_1 in the first place? Oct 22, 2019 at 1:15
• @Yuerno 1) more than educated guesses, you are solving equations like $a U_{11}+ b U_{31}=0$ for $a,b$, whose solution can always be written down explicitly. 2) I think that's an additional freedom in the way the $U_k$ are chosen. You just need the final matrix to have a fixed identity, so you can tune the intermediate determinants as long as the overall one is correct
– glS
Oct 22, 2019 at 17:50

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

• Thanks for the reply! Would you be able to explain how these approaches are calculating the values of the principal submatrices? I think I'm just missing some linear algebra background here. Like for example, in the PDF I linked, how the entries of the bottom right square of U1 are calculated? Oct 21, 2019 at 22:23