Repeated weighted Hadamard transformations
Anders B Madsen 06 Jan 2022 16:44
Define the weighted Hadamard transformation
(1)\begin{align} H_n = \begin{pmatrix} \frac{\sqrt{n-1}}{\sqrt n} & \frac{1}{\sqrt n}\\ \frac{1}{\sqrt n} & -\frac{\sqrt{n-1}}{\sqrt n} \end{pmatrix}\,. \end{align}
Then $W_n$ can be produced from $\ket{00\ldots 0}$ by a sequence of multiply 0-controlled $H_n, H_{n-1}, \ldots, H_2, H_1$ gates like this:
Note that
(2)\begin{align} H_1 = X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\,. \end{align}
The first gate $H_n$ maps
(3)\begin{align} \ket{00\ldots 0} \longmapsto \left( \frac{\sqrt{n-1}}{\sqrt n}\ket{0} + \frac{1}{\sqrt n}\ket{1}\right)\otimes \ket{00\ldots 0}_{n-1\text{ qubits}}\,. \end{align}
This is mapped by the next gate, the 0-controlled $H_{n-1}$, into the state
(4)\begin{align} \frac 1{\sqrt n}\ket{10\ldots 0} + \frac{\sqrt{n-1}}{\sqrt n}\ket{0}\otimes \left(\frac{\sqrt{n-2}}{\sqrt{n-1}}\ket{0} + \frac{1}{\sqrt{n-1}}\ket{1}\right)\otimes \ket{00\ldots 0}_{n-2\text{ qubits}} = \frac 1{\sqrt n}\ket{10\ldots 0} + \frac 1{\sqrt n}\ket{010\ldots 0} + \frac{\sqrt{n-2}}{\sqrt n}\ket{00\ldots 0}\,. \end{align}
Before the multiply 0-controlled $H_2$ gate, the state is
(5)\begin{align} \frac 1{\sqrt n}\ket{10\ldots 0} + \ldots + \frac 1{\sqrt n}\ket{00\ldots 100} + \frac{\sqrt{2}}{\sqrt n}\ket{00\ldots 000}\,, \end{align}
and after $H_2 = H$ (the standard Hadamard gate), the state is
(6)\begin{align} \frac 1{\sqrt n}\ket{10\ldots 0} + \ldots + \frac 1{\sqrt n}\ket{00\ldots 100} + \frac{1}{\sqrt n}\ket{00\ldots 010} + \frac{1}{\sqrt n}\ket{00\ldots 000}\,. \end{align}
And the final multiply 0-controlled $H_1 = X$ gate, will turn the state into $W_n$.