Exact Two-Level Elimination of a Unitary

Input: an exact-arithmetic representation of $U\in U(N)$, $N\ge 1$, supporting addition, multiplication, conjugation, nonnegative square roots, exact zero tests, and exact division by nonzero positive real scalars. Output: a finite ordered factorization into two-level unitaries and a diagonal unitary. This is an exact algebraic procedure; no claim of a bit-time algorithm for arbitrary real input is made.

Initialize $M:=U$ and an empty chronological list. For each column $j=0,\dots ,N-2$, and for $r=N-1,N-2,\dots ,j+1$, set $a=M_{r-1,j}$ and $b=M_{r,j}$. If $b=0$, do nothing. Otherwise set $h=\sqrt{\mathrm{\mid }a{\mathrm{\mid }}^2+\mathrm{\mid }b{\mathrm{\mid }}^2}>0$ and left-multiply rows $(r-1,r)$ by $G=\frac{1}{h}\left(\begin{array}{cc}\bar{a}& \bar{b}\\ -b& a\end{array}\right),$ recording this two-level unitary in the order applied. Let the resulting matrix be $D$. Return the factorization $U=G_1^{\ast }\cdots G_s^{\ast }D$. In chronological circuit order, apply $D$ first and then $G_s^{\ast },\dots ,G_1^{\ast }$.