Linear Multicontrolled X with One Borrowed Wire

An exact Toffoli has constant cost. Let $V=\frac{1}{2}((1+i)I+(1-i)X)$. The orthogonal projectors $(I+X)\mathrm{/}2,(I-X)\mathrm{/}2$ show $V$ is unitary and $V^2=X$. With controls $a,b$, apply chronologically $C_b(V)$ to the target, ${\mathrm{C}\mathrm{N}\mathrm{O}\mathrm{T}}_{a\to b}$, $C_b(V^{\ast })$, ${\mathrm{C}\mathrm{N}\mathrm{O}\mathrm{T}}_{a\to b}$, and $C_a(V)$. The bit $b$ returns, and the target exponent is $b-(b\oplus a)+a=2ab$, so its action is $X^{ab}$. By [F1] the three controlled gates and two CNOTs cost at most eight CNOTs and twelve one-qubit gates. No relative phase is discarded.

First construct an $s$-controlled $X$ with $s-2$ borrowed wires, for $s\ge 3$. Call the controls $c_1,\dots ,c_s$, the borrowed bits $a_1,\dots ,a_{s-2}$, and the target $t$. Let $T_1$ toggle $a_1$ under $c_1,c_2$; for $2\le j\le s-2$, let $T_j$ toggle $a_j$ under $c_{j+1},a_{j-1}$. Let $Q$ toggle $t$ under $c_s,a_{s-2}$. Apply the list $T_1,\dots ,T_{s-2},Q,T_{s-2},\dots ,T_1$, followed by $T_2,\dots ,T_{s-2},Q,T_{s-2},\dots ,T_2$; for $s=3$ the second list is just $Q$. Each list restores every borrowed bit, since $Q$ changes only $t$ and the compute list is reversed afterward.

Let $u_j,v_j$ be the values of $a_j$ immediately before $Q$ in the first and second lists. Both lists begin with the same borrowed values. We have $u_1=a_1\oplus c_1{c}_2$, $v_1=a_1$ and, for $j\ge 2$, $u_j=a_j\oplus c_{j+1}{u}_{j-1}$, $v_j=a_j\oplus c_{j+1}{v}_{j-1}$. Thus $u_j\oplus v_j={\prod }_{h=1}^{j+1}{c}_h$ by induction. The two target toggles add to $c_s(u_{s-2}\oplus v_{s-2})={\prod }_{h=1}^s{c}_h$. Controls and borrowed bits are unchanged. The two lists contain $(2s-3)+(2s-5)=4s-8$ exact Toffolis. For $s=2$ use one Toffoli; for $s=1$ use one CNOT. This auxiliary construction therefore costs $O(s)$ and uses at most $\max \{s-2,0\}$ borrowed wires.

For $r\ge 3$, partition the controls into $A,B$ of sizes $p=\lceil r\mathrm{/}2\rceil$, $q=\lfloor r\mathrm{/}2\rfloor$, and call the extra wire $z$. Put $a={\prod }_{j\in A}{c}_j$, $b={\prod }_{j\in B}{c}_j$. Apply an $A$-controlled $X$ into $z$, a $(B\cup \{z\})$-controlled $X$ into $t$, and repeat these two calls in that order. The first kind can borrow from $B\cup \{t\}$ because $q+1\ge p-2$; the second can borrow from $A$ because $p\ge q-1$. Step 3.1 restores these temporary borrowed wires after each call, for their actual arbitrary values at that call. No wire beyond the original $r+2$ is used.

The four ideal calls send $z$ to $z\oplus a$ and back, while toggling $t$ by $b(z\oplus a)\oplus bz=ab$. Thus their action is precisely $C^r(X)$ with $z$ and every control returned. The two calls of each kind cost $O(p)+O(q+1)=O(r)$. For $r=1,2$, use [F2] or step 1.1 and leave $z$ untouched. Equality on every basis word extends by [F6] to $C^r(X)\otimes I_z$; tensoring with an external identity also proves the entangled-input claim and the return condition [F3].