Gray-code synthesis of a multiplexed Z rotation

If $k=0$, take the one-element mask list containing the empty string. If $k>0$, construct the reflected Gray list recursively by $G_1=(0,1)$ and $G_k=(0G_{k-1},1\mathrm{rev}(G_{k-1}))$ for $k\ge 2$. Induction shows that each $k$-bit string occurs once, consecutive strings differ in one coordinate, and the last string differs from the first in one coordinate; hence for $k>0$ the cycle has $2^k$ single-coordinate transitions. For its masks $p_0,\dots ,p_{2^k-1}$ set $H_{xj}=(-1{)}^{p_j\cdot x}$ and ${\beta }_j=2^{-k}{\sum }_y{H}_{yj}{\theta }_y$. Then ${\sum }_j{H}_{xj}{\beta }_j=2^{-k}{\sum }_y{\theta }_y{\sum }_p(-1{)}^{p\cdot (x\oplus y)}={\theta }_x,$ because the inner sum factors as ${\prod }_{r=1}^k(1+(-1{)}^{x_r\oplus y_r})$, equal to $2^k$ for $x=y$ and $0$ otherwise.

Assume $k>0$. Apply $R_z({\beta }_0)$ and follow the cyclic Gray list, placing one CNOT on the coordinate that changes between consecutive masks and one $R_z({\beta }_j)$ at each mask, including the CNOT that returns from the last mask to the first. There are exactly $2^k$ of each. On a fixed control word $x$, the accumulated target bit flip before the $j$th rotation is $p_j\cdot x$ modulo two by [F5]. By [F2]–[F4], $R_z(t)=\mathrm{diag}(e^{-it\mathrm{/}2},e^{it\mathrm{/}2})$; direct multiplication with [F3] gives $X{R}_z(t)X=R_z(-t)$. Conjugating the target rotation by that parity network therefore gives $R_z((-1{)}^{p_j\cdot x}{\beta }_j)$. The final CNOT restores the parity network, so the full branch operator is the product of these rotations.

Rotations about the same axis satisfy $R_z(a)R_z(b)=R_z(a+b)$ by multiplying their diagonal matrices. Thus on branch $x$ the target operation is $R_z({\sum }_j{H}_{xj}{\beta }_j)=R_z({\theta }_x)$ by step 1.1. This proves the exact block action on every computational basis input and hence, by linearity, on every state. When $k=0$, the definition is the single gate $R_z({\theta }_0)$.