Exact finite unitary synthesis from cosine-sine recursion

For $n=1$, use the single gate $U$ itself. For $n=2$, [F4] gives an exact circuit with at most three CNOTs and no ancillas. For $n=0$, the only unitary channel on $\mathbb{C}$ is the identity, represented by the empty circuit. These establish the base cases.

Let $n\ge 3$ and split the ordered register into its first wire and the remaining $n-1$ wires. Apply [F1] to write $U=LWR,$ where $L=L_0\oplus L_1$ and $R=R_0\oplus R_1$ are block-diagonal unitaries on that split and $W=\left(\begin{array}{cc}C& -S\\ S& C\end{array}\right)\mathrm{.}$ For each computational word $x$ of the lower register, let $c_x,s_x$ be the corresponding diagonal entries of $C,S$. Since $c_x,s_x\ge 0$ and $c_x^2+s_x^2=1$, the unit complex number $c_x+i{s}_x$ has modulus one; by [F5] write it as $e^{i{\eta }_x}$ and put ${\theta }_x=2{\eta }_x$. Its real and imaginary parts show $c_x=\cos ({\theta }_x\mathrm{/}2)$ and $s_x=\sin ({\theta }_x\mathrm{/}2)$, so $W$ is a multiplexed $R_y$ rotation on the first wire, controlled by the lower word $x$.

Apply [F2] separately to $L_0\oplus L_1$ and $R_0\oplus R_1$. Each side factor becomes two unitaries on the lower $n-1$ wires, with one intervening $D\oplus D^{\ast }$ factor. In the ordered computational coordinates of the lower register, write the diagonal entries of each factor as $d_x=e^{i{\eta }_x}$; the eigenbasis change is in the outer $V,W$ factors by [F2]. The two-dimensional block on the first wire at lower word $x$ is $\mathrm{diag}(d_x,d_x^{\ast })=R_z(-2{\eta }_x)$. Thus each intervening factor is a multiplexed $R_z$ rotation controlled by the lower register. The two such factors and the central $R_y$ factor have finite exact circuits by [F3]; the wire permutation that places the first wire as target is only a relabeling of the specified ordered local gate embeddings in [F6], so no extra wire or approximation is introduced.

By induction, each of the four lower-register unitaries from step 1.3 has a finite exact circuit with no ancillas on its $n-1$ wires. Place those circuits in the product order of [F6] together with the three multiplexor circuits from step 1.3. The resulting finite $n$-wire circuit denotes $LWR=U$ exactly; all recursive factors act on existing wires, so no ancilla is added. Since every construction uses finitely many exact gate matrices, the union of the finitely many recursive gate alphabets and the three multiplexor constructs is finite, so it is an instance-specific gate alphabet.