Gray-Path Synthesis of a Two-Level Gate

Input distinct $x,y\in \{0,1{\}}^n$, $n\ge 1$, exact $V\in U(2)$, and for each controlled call a choice between the no-workspace and clean-bit constructions of Multicontrolled Unitaries with and without a Clean Work Bit. If any call selects the clean-bit construction, supply one clean bit initialized to $0$. Output: the chronological elementary-gate list on the $n$ data wires and, if selected, that one clean work wire.

Let $g_0=x,\dots ,g_d=y$ be the path that flips the differing bit positions once in increasing order, where $d$ is the Hamming distance. For $j=0,\dots ,d-2$, swap $g_j$ and $g_{j+1}$ by an $X$ on their differing bit controlled on the other $n-1$ bits matching their common pattern. Apply $V$ to the final pair $g_{d-1},y$ by a one-qubit target gate controlled on their common other bits, reversing the ordered $2\times 2$ block if $g_{d-1}$ has target bit $1$. Undo the swaps in reverse order. Expand every multi-control using its selected construction; implement negative controls by conjugating that control wire with $X$.

Expand the calls by the following procedures. Every list below is chronological; concatenation means execute the left list first. Order control wires and available spare wires by their register positions. All parameter selections are exact mathematical operations: use exact matrix arithmetic, a finite-dimensional unitary eigendecomposition, polar arguments and the Euler parameter selection of One-Qubit Euler Decomposition. The input representation must support these selections and exact zero tests; no finite-precision bit-time claim is made. Fix each selection when its call is first expanded and retain the resulting list for an inverse call.

For one control $c$, target $t$ and matrix $W$, choose $W=e^{i\delta }{R}_z(\alpha )R_y(\theta )R_z(\beta )$ as in One-Qubit Euler Decomposition. Form the three matrices $A=R_z(\alpha )R_y(\theta \mathrm{/}2)$, $B=R_y(-\theta \mathrm{/}2)R_z(-(\alpha +\beta )\mathrm{/}2)$ and $C=R_z((\beta -\alpha )\mathrm{/}2)$. Define $S(c,t;W)$ to be the list $C_t$, ${\mathrm{C}\mathrm{N}\mathrm{O}\mathrm{T}}_{c\to t}$, $B_t$, ${\mathrm{C}\mathrm{N}\mathrm{O}\mathrm{T}}_{c\to t}$, $A_t$, $\mathrm{diag}(1,e^{i\delta }{)}_c$. Each of $A,B,C$ is one arbitrary one-qubit gate, as in Exact Controlled One-Qubit Unitary with Two CNOTs. Define $T(a,b;t)$ by setting $J=((1+i)I+(1-i)X)\mathrm{/}2$ and concatenating $S(b,t;J)$, ${\mathrm{C}\mathrm{N}\mathrm{O}\mathrm{T}}_{a\to b}$, $S(b,t;J^{\ast })$, ${\mathrm{C}\mathrm{N}\mathrm{O}\mathrm{T}}_{a\to b}$, $S(a,t;J)$.

Define the ladder list $L(c_1,\dots ,c_s;t)$ with an ordered supply of at least $\max \{s-2,0\}$ distinct spare wires. For $s=1$ emit one CNOT; for $s=2$ emit $T(c_1,c_2;t)$. For $s\ge 3$, use the first $s-2$ spares $a_1,\dots ,a_{s-2}$. Set $T_1=T(c_1,c_2;a_1)$, $T_j=T(c_{j+1},a_{j-1};a_j)$ for $2\le j\le s-2$, and $H=T(c_s,a_{s-2};t)$. Concatenate $T_1,\dots ,T_{s-2},H,T_{s-2},\dots ,T_1$ and then $T_2,\dots ,T_{s-2},H,T_{s-2},\dots ,T_2$; the latter list is just $H$ when $s=3$. This is the borrowed ladder used in Linear Multicontrolled X with One Borrowed Wire.

Define $D(C;t;z)$ for an ordered nonempty control set $C$ and a distinct borrowed wire $z$. With one or two controls use the corresponding ladder base case and leave $z$ unused. With $r\ge 3$ controls split $C$ into its first $p=\lceil r\mathrm{/}2\rceil$ controls $A$ and the remaining $q=\lfloor r\mathrm{/}2\rfloor$ controls $B$. Let $F=L(A;z)$ use spares from $B\cup \{t\}$, and let $G=L(B\cup \{z\};t)$ use spares from $A$. Emit $F,G,F,G$, using the same parameter choices for repeated lists. The stated spare supplies have at least $p-2$ and $q-1$ wires, respectively.

Define the positive-control no-workspace expansion $N(C;t;W)$ recursively. If $C$ is empty, emit $W_t$. If it has one wire $c$, emit $S(c,t;W)$. Otherwise write $C=A\cup \{b\}$, with $b$ its last control. Choose an orthonormal eigendecomposition $W=R\mathrm{diag}({\lambda }_1,{\lambda }_2)R^{\ast }$ by Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely, choose polar angles ${\lambda }_j=\cos u_j+i\sin u_j$ by Every nonzero complex number has a unique polar form $r(\cos \theta +i\sin \theta )$ with $r>0$ and $-\pi <\theta \le \pi$, and set $Z=R\mathrm{diag}(\cos (u_1\mathrm{/}2)+i\sin (u_1\mathrm{/}2),\cos (u_2\mathrm{/}2)+i\sin (u_2\mathrm{/}2))R^{\ast }$. The addition formulas of The addition formulas for sine and cosine specify these half-angle roots. Emit $S(b,t;Z)$, $D(A;b;t)$, $S(b,t;Z^{\ast })$, $D(A;b;t)$, $N(A;t;Z)$. The last call has one fewer control and uses only its indicated wires.

For the positive-control clean-bit expansion with nonempty $C$ and clean wire $w$, emit $D(C;w;t)$, $S(w,t;W)$, and the reversed adjoint of that same $D$ list. With no controls emit $W_t$ and leave $w$ unused. These are the two constructions analyzed in Multicontrolled Unitaries with and without a Clean Work Bit. For a pattern control, conjugate the selected whole positive-control list by one $X$ on each zero-valued control, ordering each set of these $X$ gates by wire position. Reverse the ordered middle block by using $XVX$ as its single matrix parameter, not by adding target $X$ occurrences.

Use the selected literal elementary gate list for each call without deleting identity gates or cancelling neighboring gates. In the one-control base use the three target matrices and one control phase as four arbitrary one-qubit gates. Use the same choices and reversed adjoint gate lists for the return swaps. Reuse the supplied clean bit sequentially; each selected clean-bit construction returns it to $0$.