Exact Gray-code synthesis of multiplexed y- and z-axis rotations

For $k>0$, put $m=2^k$ and, for $0\le j<m$, write $j$ as a $k$-bit word and set $p_j=j\oplus \lfloor j\mathrm{/}2\rfloor$. In the arithmetic on these masks, bit $r=0$ is the least significant bit and controls are assigned to wires in reverse display order, as allowed by [F3]. In this proof, a control word $x$ is written in that same least-significant-first order, so it denotes the displayed register word $(x_{k-1},\dots ,x_0)$ and ${\theta }_x$ is the angle assigned to that displayed word; this is only a fixed reindexing of the finite branch set. The map is bijective: from $p_{k-1}=j_{k-1}$ and $p_r=j_{r+1}\oplus j_r$ one recovers the bits $j_r$ in descending order. Consecutive words $p_{j-1},p_j$ differ in exactly one coordinate: incrementing $j-1$ flips its trailing ones and the first zero, so in the Gray word all changed adjacent-bit XORs cancel except the bit at position ${\nu }_2(j)$, where ${\nu }_2(j)$ is the largest $r$ such that $2^r$ divides $j$. Also $p_0=0$ and $p_{m-1}=10\cdots 0$, so the return from $p_{m-1}$ to $p_0$ changes one coordinate. Thus these words give a cyclic Gray traversal of all masks.

Set ${\beta }_j:=2^{-k}{\sum }_{y\in \{0,1{\}}^k}(-1{)}^{p_j\cdot y}{\theta }_y\mathrm{.}$ For each fixed $x$, bijectivity of $j\mapsto p_j$ gives ${\sum }_{j=0}^{m-1}(-1{)}^{p_j\cdot x}{\beta }_j=2^{-k}{\sum }_y{\theta }_y{\sum }_{p\in \{0,1{\}}^k}(-1{)}^{p\cdot (x\oplus y)}={\theta }_x\mathrm{.}$ Indeed, the inner sum factors as ${\prod }_{r=0}^{k-1}(1+(-1{)}^{x_r\oplus y_r})$, equal to $2^k$ when $x=y$ and zero otherwise.

Write ${\delta }_j=p_{j-1}\oplus p_j$ for $1\le j<m$, and ${\delta }_m=p_{m-1}\oplus p_0$ for the return toggle. For a fixed control word $x$, the circuit matrix on the target is $X^{{\delta }_m\cdot x}{R}_a({\beta }_{m-1})X^{{\delta }_{m-1}\cdot x}{R}_a({\beta }_{m-2})\cdots R_a({\beta }_1)X^{{\delta }_1\cdot x}{R}_a({\beta }_0)\mathrm{.}$ The target-flip parity before rotation $j$ is $p_j\cdot x$. Direct multiplication of the matrices in [F1] gives, for both $a=y,z$, $X{R}_a(t)X=R_a(-t)$ and $R_a(s)R_a(t)=R_a(s+t)$. Moving each $X$ factor leftward through the preceding rotations gives angle sign $(-1{)}^{({\delta }_{j+1}\oplus \cdots \oplus {\delta }_m)\cdot x}=(-1{)}^{p_j\cdot x}$ on $R_a({\beta }_j)$, because the cyclic toggle sum is zero and $p_m=p_0=0$. No $X$ remains at the end. The rotations then combine to $R_a({\sum }_j(-1{)}^{p_j\cdot x}{\beta }_j)=R_a({\theta }_x)$ by step 2.1. The circuit consequently agrees with $M_a$ on every control basis subspace, and linearity gives equality on the whole register. It has $m$ rotations and $m$ CNOTs. For $k=0$ the sole term is $R_a({\theta }_{\mathrm{\varnothing }})$ and needs no CNOT.