QC24 State Preparation Rotation Level Upper Bound

Before any rotation the only nonzero prefix amplitude is the empty-prefix amplitude $1=r_{\mathrm{\varnothing }}$ because the table is normalized.

Consider a computational-basis control word $c_1,\dots ,c_m$. Conjugating each zero-control by $X$ turns the requested pattern into all ones by [F5]. Starting from zero work bits, [F3] first sets $w_1=c_1{c}_2$ and then, successively, $w_{j-1}=w_{j-2}{c}_j$; induction on $j$ shows the final flag is $1$ exactly on the requested control pattern. The controlled operation in [F4] therefore acts only on that branch and changes neither the controls nor the flag. The basis action [F3] shows each Toffoli is its own inverse, and [F5] shows $X$ is its own inverse, so reversing the Toffoli list and undoing the $X$ conjugations restores all work bits to zero. For a leaf phase, the phase gate is diagonal and also leaves the flag's bit value unchanged. For one control the direct controlled block has the same branch action, and for no controls the one-qubit block acts on every branch. The Toffoli and $X$ are basis permutations, the rotations are unitary by [F7], and controlled blocks are unitary by [F4]; the phase gates are unitary by [F10]. The basis calculation extends linearly to superpositions under [F8] and [F9].

Suppose at depth $l$ every prefix $p$ has amplitude $r_p$ on $\mathrm{\mid }p{0}^{n-l}⟩$ under the basis order in [F6]. If $r_p>0$, [F1], [F2], and [F7] split that amplitude into the nonnegative real amplitudes $r_p(r_{p0}\mathrm{/}{r}_p)=r_{p0}$ and $r_p(r_{p1}\mathrm{/}{r}_p)=r_{p1}$ on the two child prefixes. Step 1.2 shows the rotation is confined to the selected prefix branch; distinct length-$l$ prefixes therefore leave each other's amplitudes unchanged. If $r_p=0$, both children have radius zero and the zero branch remains zero without division. Thus induction gives the nonnegative real leaf amplitude $r_x=\mathrm{\mid }{a}_x\mathrm{\mid }$ at every leaf.

Put ${\varphi }_{\ast }=\arg (a_{x_{\ast }})$ for the first nonzero leaf. For every other nonzero leaf, [F10] gives $e^{i(\arg (a_x)-{\varphi }_{\ast })}\mathrm{\mid }{a}_x\mathrm{\mid }=e^{-i{\varphi }_{\ast }}{a}_x$. The reference leaf has unchanged amplitude $\mathrm{\mid }{a}_{x_{\ast }}\mathrm{\mid }=e^{-i{\varphi }_{\ast }}{a}_{x_{\ast }}$, so the same scalar multiplies every nonzero coordinate. A zero relative phase needs no gate. Its flag ladder restores the work bits by step 1.2, and a diagonal phase leaves the flag's bit value unchanged. Zero leaves stay zero. Thus the joint output is $e^{-i{\varphi }_{\ast }}a\otimes \mathrm{\mid }{0}^s⟩$ with the reused workspace zero, and its data ray is exactly $[a]$.

The number of prefixes at depths $0$ through $n-1$ is ${\sum }_{l=0}^{n-1}{2}^l=D-1$, and there are at most $D$ leaf phases. A control of $m\ge 2$ bits uses $2(m-1)$ Toffolis, at most $2m$ $X$ gates for zero-control conjugations, and one controlled one-qubit block; it uses $m-1$ clean work bits. Prefix rotations have $m\le n-1$ controls and leaf phases have $m=n$, so the maximum work count is $\max \{n-1,0\}$; the $m=0,1$ cases use constant resources. Since $m\le n$, each of at most $2D-1$ operations costs $O(n+1)$ gates and serial depth, and step 1.2 shows the same work bits are restored and reused. For $n=0$, both operation lists are empty and the normalized one-entry table has a single ray.