Multicontrolled Unitaries with and without a Clean Work Bit

By [F2], choose an orthonormal eigenbasis of $U$. For a unit eigenvector $v$ of eigenvalue $\lambda$, $1=\mathrm{\parallel }Uv\mathrm{\parallel }=\mathrm{\mid }\lambda \mathrm{\mid }$, so [F3] writes $\lambda =\cos t+i\sin t$. Set $\mu =\cos (t\mathrm{/}2)+i\sin (t\mathrm{/}2)$. The double-angle identities give ${\mu }^2=\lambda$, and hence $\mathrm{\mid }\mu {\mathrm{\mid }}^2=\mathrm{\mid }\lambda \mathrm{\mid }=1$. Putting these unit-modulus roots on the diagonal in that eigenbasis and conjugating back gives a unitary $V$ with $V^2=U$.

For the clean-bit branch, let $w$ start at $0$. An $m$-controlled $X$ into $w$, using the data target as the returned borrowed wire, changes $w$ to the AND of the controls. Apply $C(U)$ controlled by $w$ and reverse the same $X$ circuit. On each computational-basis input this applies $U$ exactly on the all-one control branch by [F5] and restores $w=0$ by [F4]; linearity gives the same exact operator on superpositions. The two $X$ calls and one controlled-$U$ call cost $O(m)$ in the model [F6] by [A1].

For the lower bound, make an undirected graph with one vertex for every circuit wire, including controls, target, and any workspace, and one edge for each two-qubit gate joining its two wires. If some control were disconnected from the target, the full circuit factors across the graph components. Choose the same data-independent auxiliary state for both test inputs (for the dirty contract a fixed product state is permitted). Even if that auxiliary state has correlations between components, a unitary on the disconnected component cannot change the reduced state of the target component: taking the partial trace cancels that unitary with its adjoint. The target reduced state would therefore be unchanged when that control alone is toggled. Since nonscalar unitary $U$ has two orthogonal eigenvectors $u,v$ with distinct eigenvalues $\lambda ,\mu$, the state $\psi =(u+v)\mathrm{/}\sqrt{2}$ obeys $U\psi =(\lambda u+\mu v)\mathrm{/}\sqrt{2}$, which is not a scalar multiple of $\psi$. Set all other controls to $1$ and the target to $\psi$; toggling the disconnected control changes the required target ray from $[\psi ]$ to $[U\psi ]$, a contradiction. Thus the target component contains all $m$ controls and has at least $m+1$ vertices. A connected component on at least $m+1$ vertices has at least $m$ edges, so at least $m$ two-qubit gates are needed.

For $m\ge 2$, write $A$ for the AND of the first $m-1$ control bits and $b$ for the last control. In chronological order [F7], the recursive controlled-$V$ construction applies $V$ to the target under $b$, toggles $b$ by an $(m-1)$-controlled $X$ under the first controls, applies $V^{\ast }$ under the changed $b$, toggles $b$ back, then applies $V$ under the first controls. On a basis branch the exponent of $V$ on the target is $b-(b\oplus A)+A$: it is $0$ when $A=0$, $0$ when $(A,b)=(1,0)$, and $2$ when $(A,b)=(1,1)$. Thus the ideal branch matrices are $I,I,V^2=U$, exactly the required $C^m(U)$ action by [F5]. Implementing the two controlled-$X$ calls with the data target as borrowed wire, and the final recursive controlled-$V$ call with the restored $b$ as borrowed wire, yields $q_m\le q_{m-1}+2x_{m-1}+O(1)$, where $x_r$ is the borrowed-bit controlled-$X$ cost. By [F8]–[F9], $x_1=1$; [A1] gives $x_r=O(r)$ for $r\ge 2$, so summing the recurrence from the constant one-control base [F1] gives $q_m=O(m^2)$ in the gate model [F6]. Every borrowed-wire call is the required controlled operation tensored with identity, so using the data target as its borrowed wire is valid even when it is entangled with the controls. The recursive call uses only its own controls and target; the restored $b$ is available but is not needed as an extra wire.

The lower bound is linear and the no-work upper bound is quadratic, so no quadratic optimality claim follows. The no-workspace recursion and clean-bit compute/apply/uncompute construction prove the two upper bounds, with exact work-bit return supplied by [A1].