\betaegin{document}

\thetaitle{Decomposition of bipartite and multipartite unitary gates into the product of controlled unitary gates}

\alphauthor{Lin Chen}
\alphaffiliation{Department of Mathematics, Beijing University of Aeronautics and Astronautics, Beijing 100191, P. R. China}
\alphaffiliation{Singapore University of Technology and Design, 20 Dover Drive, Singapore 138682}
\alphauthor{Li Yu}\epsilonmail{liyu@nii.ac.jp}
\alphaffiliation{Singapore University of Technology and Design, 20 Dover Drive, Singapore 138682}
\alphaffiliation{National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan}

\deltaate{\thetaoday}

\piacs{03.65.Ud, 03.67.Lx, 03.67.Mn}

\betaegin{abstract}
We show that any unitary operator on the $d_A\thetaimes d_B$ system ($d_A\gammae 2$) can be decomposed into the product of at most $4d_A-5$ controlled unitary operators. The number can be reduced to $2d_A-1$ when $d_A$ is a power of two. We also prove that three controlled unitaries can implement a bipartite complex permutation operator, and discuss the connection to an analogous result on classical reversible circuits. We further show that any $n$-partite unitary on the space $\muathbb{C}^{d_1}\omegatimes\chidots\omegatimes\muathbb{C}^{d_n}$ is the product of at most $[2\pirod^{n-1}_{j=1}(2d_j-2)-1]$ controlled unitary gates, each of which is controlled from $n-1$ systems. We also decompose any bipartite unitary into the product of a simple type of bipartite gates and some local unitaries. We derive dimension-independent upper bounds for the CNOT-gate cost or entanglement cost of bipartite permutation unitaries (with the help of ancillas of fixed size) as functions of the Schmidt rank of the unitary. It is shown that such costs under a simple protocol are related to the log-rank conjecture in communication complexity theory via the link of nonnegative rank.

\epsilonnd{abstract}

\muaketitle

\sigmaection{introduction}\leftarrowmbdaabel{sec:intro}

The implementation of unitary operations is a key task in quantum information processing. Unitary operators can be implemented by passive linear optical devices \chiite{Reck94}. It is known that any unitary operation on two or more parties can be decomposed into the product of controlled unitary gates \chiite{bry02,blb05}.  Two-qubit controlled unitaries can be implemented with high coherence and dynamical coupling \chiite{cnr14}. Suppose that a bipartite unitary $U$ on systems $A$,$B$ is the product of $k$ bipartite controlled unitaries, interspersed with local unitaries \chiite{note1}. We call the integer $k$ as the \epsilonmph{bipartite depth} of the circuit under the bipartite cut $A$-$B$. The depth, width and total number of basic gates are often quantities of interest in quantum circuit design, where the basic gates refer to some fixed type of two-qubit gates such as the controlled-NOT (CNOT) gate. For implementing the same unitary operation, it is conceivable that there may be a tradeoff between the depth and the total number of basic gates. Nonetheless the bipartite depth does give an upper bound for the total number of basic gates, as discussed in Sec.~\rhoef{sec:elementary} of this paper.  The nonlocal gates need much longer time than local gates to implement, because the systems may be far from each other. Then the bipartite depth is a rough measure of time needed by the circuit. By allowing local unitary freedom in the definition of controlled unitaries (in Sec.~\rhoef{sec:pre}), from now on we will drop the phrase ``interspersed with local unitaries'' from the definition of the bipartite depth.

We define the \epsilonmph{bipartite depth of a given bipartite unitary $U$} as the minimum bipartite depth among all unitary circuits for $U$ that do not use ancillas. Formally, it is
\betaegin{eqnarray}
\leftarrowmbdaabel{eq:cu}
c(U) := \muin\{k | U=U_1U_2\chidots U_k,~~U_i\iotan \chiS\},
\epsilonnd{eqnarray}
where $\chiS$ is the set of bipartite controlled unitaries on the same space that $U$ acts on. Studying the bounds for $c(U)$ and the corresponding decomposition of $U$ is the main problem in this paper. Indeed, it is a special case of the problem of quantum circuit decomposition using \epsilonmph{general} controlled unitaries with the help of local unitaries. It is special in the sense that there are only two systems but the general problem allows many systems. There has been study on decompositions using CNOT or other two-qubit controlled gates, or specific classes of two-qudit controlled gates \chiite{bry02,blb05,bbo06,dw13}. For example, Shende \thetaextit{et al.} \chiite{Shende06} shows that any three-qubit unitary can be written as the product of 20 CNOT gates and some one-qubit unitaries. Another motivation to study the problem is to better understand the structure of nonlocal unitaries and the resources needed to implement them, see the comment just before Section~\rhoef{ssec1}.

We restrict to bipartite controlled gates as the type of nonlocal gates in the definition of bipartite depth for the following reasons. First, it is easy to define, and a smaller class of gates seems not powerful enough. It is hard to find a larger class of easily definable gates that do not include all bipartite gates. The Fourier hierarchy \chiite{Shi2005335} concerns the number of tensor products of Hadamard gates in a circuit that also contains basis-preserving gates. The basis-preserving gates are also called the complex permutation gates, and are discussed later in this paper. They permute among computational-basis states and apply a phase to each state. However the basis-preserving gates are generally nonlocal with respect to a bipartite partition of the qubits. If we modify the definition of Fourier hierarchy and apply it to the bipartite scenario so as to allow some finite set of bipartite gates and arbitrary local gates, then such a set of bipartite gates would have a discrete set of entangling power, which is not desirable for defining a smooth depth measure. Second, the controlled unitaries are analogous to some components in protocols with local operations and classical communication (LOCC). They are a major type of protocols studied in quantum information theory. The LOCC protocols often allow projective measurements on some subsystems. A projective measurement and the subsequent classically controlled unitary operations can be made part of a coherent quantum circuit by rewriting them as a controlled unitary. Thus our measure is analogous to the rounds of classical communications in such protocols.

Generally we consider unitaries acting on $d_A\thetaimes d_B$ dimensional systems. The results of \chiite{bry02,blb05} imply that $c(U)\leftarrowmbdae \muu d_A^4$ when $d_A=d_B$, where $\muu$ is a positive constant, and the type of bipartite controlled gates used are limited to controlled-increment gates. In Theorem \rhoef{thm:u_controlled}, we obtain a tighter bound $c(U)\leftarrowmbdae 4d_A-5$ for arbitrary $d_A,d_B$ at the cost of allowing the use of arbitrary controlled-unitary gates in the decomposition. The same theorem shows that the bound can be further reduced to $2d_A-1$ when $d_A$ is a power of $2$.  We also prove that $c(U)\leftarrowmbdae 3$ when $U$ is a complex permutation matrix in Theorem~\rhoef{thm:u_controlled2}, based on the concept of absolute singularity studied in Lemma \rhoef{le:absolutesingular}. This result is applied to classical reversible circuits \chiite{Shende03,sm14} in Corollary~\rhoef{cr:u_classical}. The above results are based on the sandwich form of bipartite unitaries, constructed in Definition \rhoef{df:sandwich} and Lemma \rhoef{le:2xddecomp}.
We further generalize our observation to multipartite systems based on the generalized sandwich form. We show that any $n$-partite unitary on the space $\muathbb{C}^{d_1}\omegax\chidots\omegax\muathbb{C}^{d_n}$ has a generalized $[2\pirod^{n-1}_{j=1}(2d_j-2)-1]$-sandwich form in Proposition \rhoef{pp:multi_controlled}. We also propose a more efficient generalized sandwich form for $n=4$ in Proposition \rhoef{pp:multi_controlled2}. In Proposition \rhoef{pp:multi_controlled3}, we show that any $n$-partite complex permutation unitary has a generalized $(2^n-1)$-sandwich form composed of controlled-complex-permutation unitaries.

We also discuss the decomposition of any unitary gate using ``standard'' gates proposed in Definition \rhoef{def:ele1}. They effectively only act on two qubits as controlled unitaries, and may be more easily carried out in experiments. We show that any bipartite unitary is the product of $2(d_A-1)^2 \leftarrowmbdafloor \frac{d_B}{2}\rhofloor
+(2d_A-3)(d_B-1) \leftarrowmbdafloor \frac{d_A}{2}\rhofloor$ standard gates interspersed with local unitaries in Proposition \rhoef{pp:elem}. The number reduces to three for $d_A=d_B=2$, which is the smallest number of controlled unitaries needed for the decomposition of two-qubit unitary gates \chiite{vw04}.
In Sec.~\rhoef{sec:Schmidt} we discuss the relationship between the Schmidt rank of the unitary and the number of controlled unitaries needed to decompose it. We give a class of examples where the number of controlled unitaries is upper bounded by a constant, but the Schmidt rank of the target unitary is arbitrarily large.

The rest of the paper is organized as follows. In Sec.~\rhoef{sec:pre} we introduce some definitions and preliminary knowledge. In Sec.~\rhoef{sec:bipartite} we study the decomposition of bipartite unitary operators using controlled unitaries, and comment on the connections with results in the literature. In Sec.~\rhoef{sec:multi} we define the ``controlled-type'' multipartite unitaries and discuss the decomposition of multipartite operators into the product of these gates. We also show that three controlled-permutation matrices are enough to decompose any complex permutation matrix. In Sec.~\rhoef{sec:elementary} we define the standard gates  and discuss the decomposition of bipartite unitaries using these gates and local unitaries. In Sec.~\rhoef{sec:Schmidt} we discuss the relationship between the Schmidt rank of the unitary and the form of the decomposition, and we discuss bipartite permutation unitaries in particular. In Sec.~\rhoef{sec:ancilla} we discuss the use of local ancillas. We conclude in Sec.~\rhoef{sec:con}.

\sigmaection{Preliminaries}\leftarrowmbdaabel{sec:pre}

In this section we introduce the preliminary knowledge used in the paper. Denote the computational-basis states of the bipartite Hilbert space $\chiH=\chiH_A\omegax\chiH_B$ by $\kappaet{i,j},i=1,\chidots,d_A$, $j=1,\chidots,d_B$. Let
$I_A$ and $I_B$ be the identity
operators on the spaces $\chiH_A$ and $\chiH_B$, respectively. Any bipartite unitary gate $U$ acting on $\chiH$ has \epsilonmph{Schmidt rank} (denoted as ${\rhom Sch}(U)$) equal to $n$ if there is an expansion of the form $U=\sigmaum^n_{j=1}A_j \omegax B_j$ where the $d_A\thetaimes d_A$ matrices $A_1,\chidots,A_n$ are linearly independent, and the $d_B\thetaimes d_B$ matrices $B_1,\chidots,B_n$ are also linearly independent. An equivalent definition is in \chiite{Nielsen03,Tyson03}, where it is called the operator-Schmidt rank.
Next, $U$ is a \thetaextit{controlled unitary gate}, if $U$ is
 equivalent to $\sigmaum^{d_A}_{j=1}\piroj{j}\omegax U_j$ or
$\sigmaum^{d_B}_{j=1}V_j \omegax \piroj{j}$ via local unitaries. To be specific, $U$ is a controlled unitary from the $A$ or $B$ side, respectively.
In particular, $U$ is controlled in the computational basis from the $A$ side if $U=\sigmaum^{d_A}_{j=1}\piroj{j}\omegax U_j$. Bipartite unitary gates of Schmidt rank two or three are in fact controlled unitaries \chiite{cy13,cy14,cy14ap}.
We have generalized controlled unitaries to block-controlled unitary gates \chiite{cy14}. We split the space $\chiH_A$ into a direct sum:
$\chiH_A=\omegap^m_{i=1} \chiH_i$, $m>1$, $\deltaim\chiH_i=m_i$, and
$\chiH_i\pierp\chiH_j$ for distinct $i,j=1,\chidots,m$. Then $U$ is
a \thetaextit{block-controlled unitary (BCU) gate controlled from the A
side}, if $U$ is locally equivalent to $\sigmaum^m_{i=1}
\sigmaum^{m_i}_{j,k=1} \kappaetbra{u_{ij}}{u_{ik}}\omegax V_{ijk}$ where
$\{\kappaet{u_{i,1}},\chidots,\kappaet{u_{i,m_i}}\}$ is an orthonormal basis of $\chiH_i$. Note that the $V_{ijk}$ are not necessarily unitary. By definition every controlled unitary with $d_A,d_B\gammae2$ is a BCU. The BCU will be used in the proof of Theorem \rhoef{thm:u_controlled}, as well as in the decomposition of any bipartite unitary into the product of three BCUs in Corollary \rhoef{cr:bcu}.

\sigmaection{Decomposition of bipartite unitary operators}

\leftarrowmbdaabel{sec:bipartite}

It is known \chiite{vw04} that three controlled gates are sufficient and necessary for the decomposition of a general two-qubit unitary, and there is always a decomposition using $3$ CNOT gates and some one-qubit unitaries. For implementing a two-qubit SWAP gate by local unitaries and some number of CNOT gates without the use of ancillas (this condition of no ancillas is implied throughout the paper unless stated otherwise), three CNOT gates are necessary and sufficient \chiite{vw04}. We generalize this fact to the SWAP gates of arbitrary dimension.

\betaegin{lemma}
\leftarrowmbdaabel{le:swap}
Denote the two-qudit SWAP gate acting on $d\thetaimes d$ system as SWAP$_d$. Then
\\
(i)
the product of the SWAP$_d$ gate and any controlled unitary has Schmidt rank $d^2$;
\\
(ii)
For implementing a SWAP$_d$ gate by local unitaries and some number of controlled unitary gates, three controlled unitaries are necessary and sufficient.
\epsilonnd{lemma}
\betaegin{proof}
(i) There are orthonormal bases of $\chiH_A$ and $\chiH_B$ (denoted by $\{\kappaet{i}\}_A$ and $\{\kappaet{j}\}_B$) such that the matrix representation of the SWAP$_d$ gate in such bases has elements of the form $\betaegin{remark}a{i}_A\betaegin{remark}a{j}_B U\kappaet{k}_A \kappaet{l}_B=\deltaelta_{il}\deltaelta_{jk}$. Because the SWAP$_d$ gate effectively performs the physical swap of two systems, which is basis-independent, the above particular matrix representation is invariant under simultaneous unitary similarity transform (simultaneous unitary change of basis) on the two local systems. Then assertion (i) follows from straightforward computation, by writing the matrix for the SWAP$_d$ gate in the form above and assuming one of the local bases is the local controlling basis for the controlled unitary.

(ii) Any controlled unitary on $\chiH$ has Schmidt rank at most $d$. It follows from assertion (i) that the SWAP$_d$ gate is the product of at least three controlled unitaries. It is known that the SWAP$_d$ gate is the product of three controlled unitary gates \chiite{gc13}. So assertion (ii) holds.
This completes the proof.
\epsilonnd{proof}

\sigmamallskip
For the two-qubit SWAP gate, using the general controlled unitaries in its decomposition does not save any controlled unitary compared to using CNOT gates. One might expect that this is the general case, i.e.,  the implementation of a bipartite unitary is the same when we use controlled unitaries or only CNOT gates. However, the two-qubit gate $\epsilonxp(ia\sigma_1\omegax \sigma_1)$ with the Pauli matrix $\sigma_1=\leftarrowmbdaeft(
                   \betaegin{array}{cc}
                     0 & 1 \\
                     1 & 0 \\
                     \epsilonnd{array}
                 \rhoight)$ any $a\nue k\pii/4$, $k\iotan \muathbb{Z}$ cannot be implemented using one CNOT gate and single qubit gates only, since the entangling power of such gate is not equal to that of the CNOT gate.  We will show in Theorem \rhoef{thm:u_controlled} that for the general $d\thetaimes d$ bipartite system that using controlled unitaries might be better than the $d$-dimensional CNOT gates, in the sense that they require fewer such two-qudit gates.
For this purpose we introduce a special decomposition of bipartite unitaries.
\betaegin{definition}
\leftarrowmbdaabel{df:sandwich}
(i) We refer to the \thetaextit{m-sandwich form} of a bipartite unitary $U$, in the sense that $U=U_1U_2\chidots U_m$, where each $U_i$ is a controlled unitary, being controlled in the computational basis on the respective Hilbert space, and the party that does the controlling alternates between A for odd $i$ and B for even $i$.
\\
(ii) We refer to the \thetaextit{m-A form} of a bipartite unitary $U$, in the sense that $U=U_1U_2\chidots U_m$, where any $U_i$ is a controlled unitary controlled from the $A$ side.
\epsilonnd{definition}
Using this definition we present the following result as the first step to our question.

\betaegin{lemma}
\leftarrowmbdaabel{le:2xddecomp}
(i) Any $2\thetaimes d_B$ unitary has a 3-sandwich form;
\\
(ii) Any $2\thetaimes d_B$ unitary has a 3-A form;
\\
(iii) There exists a $2\thetaimes 2$ unitary that cannot be the product of two controlled unitaries.
\epsilonnd{lemma}
\betaegin{proof}
(i) For any $2\thetaimes d_B$ unitary $M$, there are two local unitaries $E,F$ on $\chiH_B$ such that $M=(I_A\omegax E)U(I_A\omegax F)$,
where $U=\sigmaum^1_{i,j=0}\kappaetbra{i}{j}\omegax U_{ij}$ and $U_{00}$ is a $d_B\thetaimes d_B$ diagonal matrix. Since $U$ is unitary, the columns of $U_{10}$ are pairwise orthogonal, and the rows of $U_{01}$ are also pairwise orthogonal. Let $V,W$ be two $d_B\thetaimes d_B$ unitaries such that both $VU_{10}$ and $U_{01}W$ are diagonal matrices with all elements real and non-negative. Let $U_1=\piroj{0}\omegax I_B + \piroj{1}\omegax V$ and $U_2=\piroj{0}\omegax I_B + \piroj{1}\omegax W$ be two controlled unitaries from the $A$ side, we have
\betaegin{eqnarray}
U_3 =U_1 U U_2 =
\leftarrowmbdaeft(
                   \betaegin{array}{cc}
                     U_{00} & U_{01}W \\
                     VU_{10} & VU_{11}W
                   \epsilonnd{array}
                 \rhoight).
\epsilonnd{eqnarray}
Since $U$ is unitary, we have $U_{01}W=VU_{10}$. The matrix $U_3$ is a $2\thetaimes d_B$ bipartite unitary of Schmidt rank at most 3, so it is a controlled unitary from the $B$ side \chiite{cy13,cy14}. We have proved that $U$ is the product of three controlled unitaries $U_1^\deltag, U_3,$ and $U_2^\deltag$. There exist suitable local unitaries $S=I_A\omegax X_B$ and $T=I_A\omegax Y_B$, so that $S U_3 T$ is controlled in the computational basis of $\chiH_B$. Hence $U=(U_1^\deltag S^\deltag) (S U_3 T) (T^\deltag U_2^\deltag)$ is a decomposition with each of the three parts controlled in the computational basis of $\chiH_A$ or $\chiH_B$.  Therefore $M=\leftarrowmbdaeft[(I_A\omegax E) (U_1^\deltag S^\deltag)\rhoight] (S U_3 T) \leftarrowmbdaeft[(T^\deltag U_2^\deltag)  (I_A\omegax F)\rhoight]$ is exactly a 3-sandwich form.  Hence the assertion holds.

(ii) From the proof of (i), we know that any $2\thetaimes d_B$ unitary $U$ has a 3-sandwich form. Let $U=V_1V_2V_3$ where $V_1,V_3$ are controlled unitaries controlled in the computational basis of $\chiH_A$, and $V_2$ is a controlled unitary controlled in the computational basis of $\chiH_B$. Since $V_2$ is controlled in the computational basis of $\chiH_B$, one can write $V_2=\sigmaum^1_{i,j=0} \kappaetbra{i}{j}\omegax V_{ij}$ where all $V_{ij}$ are diagonal matrices. By multiplying $V_2$ with two suitable diagonal controlled unitaries respectively from the left and right side, we can make all entries of $V_{00},V_{01}$ and $V_{10}$ real and non-negative, and the entries of $V_{11}$ real and non-positive. Since $V_2$ is unitary, we have $V_{00}=-V_{11}$ and $V_{01}=V_{10}$. So $V_2$ has Schmidt rank at most two. It is controlled from the $A$ side \chiite{cy13}. The inverse of all diagonal unitary operators taken above are also diagonal, so they can be absorbed by $V_1$ and $V_3$. The latter are still controlled unitaries from the $A$ side in the computational basis. So $U=V_1V_2V_3$ is a 3-A form and the assertion holds.

(iii) The assertion follows from Lemma \rhoef{le:swap},  which shows that the two-qubit SWAP gate is a product of three controlled unitaries, and no fewer.
This completes the proof.
\epsilonnd{proof}

\sigmamallskip
When $d_B=2$ namely the unitary acts on two-qubit states, assertion (ii) has been proved as the statement that any two-qubit unitary has the so-called canonical form \chiite{kbg01,kc01}. It has been shown that any two-qubit unitary does not have Schmidt rank three \chiite{Nielsen03}. For readers' reference, the Schmidt-rank-three multiqubit unitary has been investigated and constructed in \chiite{cy13,cy14ap}.

Now we are in a position to give an upper bound of $c(U)$ and the associated method of decomposing the bipartite unitary $U$.
\betaegin{theorem}\leftarrowmbdaabel{thm:u_controlled}
Let $U$ be a bipartite unitary on the $d_A\thetaimes d_B$ system. Then
\\
(i) $U$ has a $(2^{\leftarrowmbdaceil \leftarrowmbdaog_2 d_A\rhoceil+1}-1)$-sandwich form. Hence
\betaegin{eqnarray}
\leftarrowmbdaabel{eq:upperbound}
c(U) \leftarrowmbdae 2^{\leftarrowmbdaceil \leftarrowmbdaog_2 d_A\rhoceil+1}-1 \leftarrowmbdae 4d_A-5,
\epsilonnd{eqnarray}
for any $d_A\gammae2$. In particular, $c(U)\leftarrowmbdae 2d_A-1$ when $d_A$ is an integer power of $2$.
\\
(ii) If all bipartite unitaries on the $d_A\thetaimes d_B$ system with odd $d_A\gammae3$ have $(2d_A-1)$-sandwich forms, then $U$ has a $(2d_A-1)$-sandwich form for any even $d_A\gammae2$.
\epsilonnd{theorem}
\betaegin{proof}
(i) One can easily show that the second inequality in \epsilonqref{eq:upperbound} holds. In particular its equality holds when $d_A=2^n+1$ with any nonnegative integer $n$. Since the first inequality in \epsilonqref{eq:upperbound} and the last assertion of (i) both follow from the first assertion of (i), it is sufficient to prove the latter. The assertion is trivial if $d_A$ or $d_B=1$, so we assume $d_A,d_B\gammae2$. The proof is by induction over $d_A$. The assertion for $d_A=2$ with any $d_B\gammae 2$ is proven in Lemma~\rhoef{le:2xddecomp}. In the following we prove the assertion for a fixed $d_A\gammae 3$, under the induction hypothesis that the $k\thetaimes d_B$ bipartite unitary with any $2\leftarrowmbdae k\leftarrowmbdae d_A-1$ and $d_B\gammae 2$ has a $g(k)$--sandwich form, where for any positive integer $j$ we define
\betaegin{eqnarray}
\leftarrowmbdaabel{eq:gk}
g(j)=2^{\leftarrowmbdaceil \leftarrowmbdaog_2 j\rhoceil+1}-1.
\epsilonnd{eqnarray}
Let $\chiH_{A_1},\chiH_{A_2}\sigmaue\chiH_A$ be two subspaces spanned by the first $y~(y\leftarrowmbdae \leftarrowmbdafloor d_A/2 \rhofloor)$ and $2y$ computational basis kets, respectively. Let
$V=I_{A_1}\omegax I_B + V'$ be a BCU where $V'$ is a bipartite unitary on the subspace $H=\chiH_{A_1}^\pierp\omegax\chiH_B$. Let
\betaegin{eqnarray}
\leftarrowmbdaabel{eq:w=w'+poxi}
W=W' + I_{{A_2}^\pierp}\omegax I_B
\epsilonnd{eqnarray}
be another BCU, where $W'$ is a bipartite unitary on the subspace $\chiH_{A_2}\omegax\chiH_B$, and $I_{{A_2}^\pierp}$ is the identity operator on the subspace $\chiH_{A_2}^\pierp$. We can find a suitable $V$, such that in the top $yd_B$ rows of the matrix product $UV$, the nonzero entries occur only in the first $2yd_B$ columns. Then we can find a suitable $W$ such that the matrix product
\betaegin{eqnarray}
\leftarrowmbdaabel{eq:x}
X:=UVW=I_{A_1}\omegax I_B + X',
\epsilonnd{eqnarray}
where $X'$ is a unitary acting on $H$. So $X$ is a BCU controlled from the $A$ side, and
\betaegin{eqnarray}
\leftarrowmbdaabel{eq:u=xwdgvdg}
U=XW^\deltag V^\deltag.
\epsilonnd{eqnarray}
By regarding $W'$ as a  $2\thetaimes yd_B$ bipartite unitary and using Lemma \rhoef{le:2xddecomp}, we obtain that $W'$ has a 3-sandwich form. Let
\betaegin{eqnarray}
\leftarrowmbdaabel{eq:w'dag}
(W')^\deltag=CTD,
\epsilonnd{eqnarray}
where $C,D$ are both the direct sum of two unitaries each of order $yd_B$, and
\betaegin{eqnarray}
\leftarrowmbdaabel{eq:t}
T=\sigmaum^{yd_B}_{i=1} W_i \omegax \piroj{i}
\epsilonnd{eqnarray}
with some unitaries $W_i$ of order two. So $C,D$ and $T$ can all be regarded as $2y\thetaimes d_B$ bipartite unitaries on the subspace $\chiH_{A_2}\omegax\chiH_B$. Using \epsilonqref{eq:w=w'+poxi}, \epsilonqref{eq:u=xwdgvdg}, and \epsilonqref{eq:w'dag}, we have
\betaegin{eqnarray}
\leftarrowmbdaabel{eq:xctdv}
U=X(CTD+I_{{A_2}^\pierp}\omegax I_B)V^\deltag=(X \thetailde C)\thetailde T(\thetailde D V^\deltag),
\epsilonnd{eqnarray}
where
\betaegin{eqnarray}
\leftarrowmbdaabel{eq:tildec}
\thetailde C=C+I_{{A_2}^\pierp}\omegax I_B,
\\
\leftarrowmbdaabel{eq:tilded}
\thetailde D=D+I_{{A_2}^\pierp}\omegax I_B,
\\
\leftarrowmbdaabel{eq:tildet}
\thetailde T=T+I_{{A_2}^\pierp}\omegax I_B.
\epsilonnd{eqnarray}
It follows from \epsilonqref{eq:t} that $T$ can be regarded as a controlled unitary on $\chiH_{A_2}\omegax\chiH_B$, controlled from the $B$ side in the computational basis. This fact and \epsilonqref{eq:tildet} imply that $\thetailde{T}$ is a controlled unitary from the $B$ side in the computational basis. Next,
it follows from \epsilonqref{eq:x} and \epsilonqref{eq:tildec} that $X\thetailde C$ is a BCU, i.e.,
\betaegin{eqnarray}
\leftarrowmbdaabel{eq:xtildec}
X\thetailde C=X_1+X_2,
\epsilonnd{eqnarray}
where the bipartite unitaries $X_1$ and $X_2$ act on the subspaces $H^\pierp$ and $H$, respectively. Since $\deltaim \chiH_{A_1}=y$ and $\deltaim \chiH_{A_1}^\pierp=d_A-y$, they are both smaller than $d_A$ for any $y=1,2,\chidots,\leftarrowmbdafloor d_A/2 \rhofloor$. It follows from the induction hypothesis that $X_1$ and $X_2$ have $g(y)$ and $g(d_A-y)$-sandwich forms, respectively. We have two decomposition
\betaegin{eqnarray}
\leftarrowmbdaabel{eq:x1}
X_1=\pirod^{g(y)}_{i=1} X_{1,i},
~~~~
X_2=\pirod^{g(d_A-y)}_{i=1} X_{2,i},
\epsilonnd{eqnarray}
where for any odd and even $i$, the $X_{j,i}$ is a controlled unitary from the $A$ and $B$ side, respectively. Then so is $X_{1,i}+X_{2,i}$, because $X_{1,i}$ and $X_{2,i}$ act on the subspaces $H^\pierp$ and $H$, respectively. It follows from \epsilonqref{eq:gk} and the condition $y\leftarrowmbdae \leftarrowmbdafloor d_A/2 \rhofloor$ that $g(y)\leftarrowmbdae g(d_A-y)$. This inequality, \epsilonqref{eq:xtildec} and \epsilonqref{eq:x1} imply $X\thetailde C=\pirod^{g(y)}_{i=1} (X_{1,i}+X_{2,i})\chidot\pirod^{g(d_A-y)}_{j=g(y)+1} (I_{A_1}\omegax I_B+X_{2,j})$. These facts imply that $X\thetailde C$ has a $g(d_A-y)$-sandwich form. Next using the same argument except that \epsilonqref{eq:tildec} is replaced by \epsilonqref{eq:tilded}, one can show that $\thetailde D V^\deltag$ also has a $g(d_A-y)$-sandwich form. Third it follows from \epsilonqref{eq:gk} that $g(j)$ is odd for any positive integer $j$. Fourth in the paragraph below \epsilonqref{eq:tildet}, we have shown that $\thetailde T$ is a controlled unitary from the $B$ side in the computational basis. Applying these four facts to \epsilonqref{eq:xctdv} implies that the unitary $U$ has an $x$-sandwich form where
\betaegin{eqnarray}
\leftarrowmbdaabel{eq:x2}
x
&&=\muin_{1\leftarrowmbdae y\leftarrowmbdae\leftarrowmbdafloor d_A/2 \rhofloor} \betaig( 2 g(d_A-y) + 1 \betaig)
\nuotag\\
&&= 2 g(\leftarrowmbdaceil d_A/2 \rhoceil) + 1
= g(d_A).
\epsilonnd{eqnarray}
The last two equalities in \epsilonqref{eq:x2} follow from \epsilonqref{eq:gk}, and the fact that $\leftarrowmbdaceil \leftarrowmbdaog_2 d_A \rhoceil = \leftarrowmbdaceil \leftarrowmbdaog_2 (d_A + 1) \rhoceil$ for odd $d_A\gammae3$. So \epsilonqref{eq:x2} is exactly the first assertion of (i).

(ii) The proof is by induction over even $d_A\gammae2$. The assertion for $d_A=2$ with any $d_B\gammae 2$ is proven in Lemma~\rhoef{le:2xddecomp}. In the following we prove the assertion for a fixed even $d_A\gammae 4$, under the induction hypothesis that the $k\thetaimes d_B$ bipartite unitary with any even $k\iotan[2, d_A-1]$ and $d_B\gammae 2$ has a $(2k-1)$--sandwich form. One can verify that the argument from the paragraph below \epsilonqref{eq:gk} to the second sentence below \epsilonqref{eq:xtildec} still applies here. We choose $y=d_A/2$ in the argument. If $y$ is odd (respectively, even), then the condition in (ii) (respectively, the induction hypothesis) implies that $X_1$ and $X_2$ in \epsilonqref{eq:xtildec} both have $(d_A-1)$-sandwich forms, respectively. Hence \epsilonqref{eq:x1} and the subsequent paragraph hold, except that $g(j)$ is replaced by $2j-1$ for any positive integer $j$.
Since $d_A\gammae2$ is even, applying these facts to \epsilonqref{eq:xctdv} implies that the unitary $U$ has an $x$-sandwich form where
\betaegin{eqnarray}
\leftarrowmbdaabel{eq:x=2d-1}
x
=2(d_A-1)+1=2d_A-1.
\epsilonnd{eqnarray}
This completes the proof of assertion (ii).
\epsilonnd{proof}

\sigmamallskip
We do not know whether the condition in Theorem \rhoef{thm:u_controlled} (ii) can be satisfied, and we leave it as an open problem. As a byproduct of the theorem, it follows from \epsilonqref{eq:u=xwdgvdg} that
\betaegin{corollary}
\leftarrowmbdaabel{cr:bcu}
Any bipartite unitary is the product of three BCUs controlled from the $A$, $B$ and $A$ sides, respectively.
\epsilonnd{corollary}
It is known that any two-qubit BCU is a controlled unitary. Hence Lemma \rhoef{le:2xddecomp} (iii) implies that the two-qubit CNOT gate cannot be the product of only two BCUs. In other word, the upper bound three in Corollary \rhoef{cr:bcu} is tight.

The upper bound obtained in Theorem \rhoef{thm:u_controlled} is $4d_A-5$ and it is polynomially smaller than $4d_A^4$ obtained in \chiite{bry02}. Compared to the latter, the implementation of a bipartite unitary by arbitrary controlled unitaries can indeed save quantum resources.   Since the systems $A$ and $B$ are symmetric in the problem, $4d_B-5$ is also an upper bound for the number of controlled gates.  We consider the optimality of the bound $4d_A-5$ under the assumptions that $d_A\leftarrowmbdae d_B$ and that the number of controlled gates is a function of $d_A$ only. By parameter counting, the $4d_A-5$ is already optimal up to a constant factor, because the entire unitary has $d_A^2 d_B^2$ free real parameters in it, and each controlled unitary from the $A$ side and controlled in the computational basis of $\chiH_A$ has $d_A d_B^2$ free real parameters in it, while each controlled gate from the $B$ side has $d_B d_A^2$ free real parameters in it, less than what is in a controlled gate from the $A$ side (so that a larger number of these would be used if they are used instead of controlled gates from the $A$ side).  Note that for two adjacent controlled gates, we have overestimated the number of free parameters, since when they are both controlled from the $A$ side, the change of controlling basis on $\chiH_A$ could be viewed as a change in either of the controlled gates, and generally, a bipartite diagonal gate between two adjacent controlled gates can be absorbed into any of the two adjacent controlled gates.  But such issues only affect the count above by a lower order factor.

We comment on the connection with the results in the literature. Our Lemma~\rhoef{le:2xddecomp}(i) in the special case that $d_B$ is an integer power of $2$ is the same as Theorem 10 of Shende \thetaextit{et al.} \chiite{Shende06} (see also \chiite{pw94}).  Our Theorem~\rhoef{thm:u_controlled}(i) in the case that $d_A$ is an integer power of $2$ can also be derived by recursively applying Theorem 10 of \chiite{Shende06} (the first step of recursion is illustrated in Theorem 11 of \chiite{Shende06}, and note that a gate controlled by multiple qubits belonging to the same party is a controlled gate in our language).  We abbreviate the details here.  Therefore our result can be viewed as a generalization of the results in \chiite{Shende06} to the general dimensions.  Based on our result, it may be possible to decompose any qudit circuit (with dimensions of qudits not required to be all equal) using controlled two-qudit unitaries.  The following Sec.~\rhoef{sec:multi} can be viewed as a step in this direction, but we do not decompose the gates fully there, allowing some gate controlled by multiple qudits. There may be some extensions of the techniques in \chiite{Shende06} to the case of higher dimensional qudits that can help decompose such multiply-controlled gate. There are some papers on decomposition of qudit circuits, such as \chiite{blb05,bbo06,dw13}. It is possible that the methods in those papers may be combined with the results in this paper to give a better upper bound of the number of two-qudit (controlled) gates needed. Apart from the application to circuit decomposition, the other potential application is to help study the nonlocal resource usage in implementing nonlocal unitaries. Here the usage of nonlocal resources is to be optimized, and the local resources such as local unitaries are deemed as cheap. Section~\rhoef{sec:elementary} is a step in this direction, but it only discusses the cost in terms of a particular type of nonlocal gate (whose implementation cost is upper bounded by a constant), and not in terms of the more conventional resources such as entanglement.

\sigmaubsection{Decomposition of complex permutation matrices}\leftarrowmbdaabel{ssec1}

The upper bound in Theorem \rhoef{thm:u_controlled} works for arbitrary bipartite unitaries, and it increases linearly with the dimension. One may expect to have a constant upper bound for some special bipartite unitaries. In this subsection we give such a bound for any \epsilonmph{complex permutation matrix} in Theorem \rhoef{thm:u_controlled2}. It is a unitary matrix with one and only one nonzero element on each row and column. When the nonzero elements have no phases and are equal to one, it becomes the standard permutation matrix. The complex permutation matrix is mathematically known as a special monomial matrix, and has been used to characterize the mutually unbiased bases \chiite{bw09,mb15}. The complex permutation gate is of interest to the study of quantum computation, as it is a somewhat classical part of a quantum circuit; see its use in the definition of the Fourier hierarchy in \chiite{Shi2005335}. The diagonal unitary, which is a special complex permutation matrix, can be efficiently simulated in terms of the Clifford+T basis by the algorithm in \chiite{wbs14}. We define the \epsilonmph{controlled-permutation matrices} to be bipartite controlled unitaries controlled in the computational basis of one system and with the terms on the controlled side being permutation matrices. The \epsilonmph{controlled-complex-permutation matrices} are defined similarly.

To study the decomposition of complex permutation matrices, we present a preliminary lemma, which is actually a form of the Hall's marriage theorem \chiite{Halltheorem}. Suppose $V=\sigmaum^{d_A}_{j,k=1} \kappaetbra{j}{k}\omegax V_{j,k}$ is a bipartite operator on the space $\chiH=\chiH_A\omegax\chiH_B$. We say that $V$ is \epsilonmph{absolutely singular} if there are integers $j_1,\chidots,j_s$ and $k_1,\chidots,k_t$ with $s+t>d_A$, such that $V_{j_a,k_b}=0$. The absolute singularity of $V$ is unchanged up to any product permutation operators on the left- and right-hand sides of $V$ (a product permutation operator is of the form $P_A\omegax Q_B$, where $P_A$ and $Q_B$ are local permutation operators; in what follows we only need $Q_B$ to be an identity matrix). Hence an absolute singular $V$ is locally equivalent to another bipartite operator whose left-upper $sd_B \thetaimes td_B$ submatrix is zero. Evidently an absolutely singular operator is singular, but the converse is not true. We characterize the absolute singularity as follows.
\betaegin{lemma}
\leftarrowmbdaabel{le:absolutesingular}
$V=\sigmaum^{d_A}_{j,k=1} \kappaetbra{j}{k}\omegax V_{j,k}$ is not absolutely singular if and only if there are $d_A$ distinct integers $k_1,\chidots,k_{d_A}$, such that the blocks $V_{1,k_1},\chidots,V_{d_A,k_{d_A}}$ are all nonzero.
\epsilonnd{lemma}
\betaegin{proof}
We first present a matrix-based proof, and then provide a proof of the equivalence of the lemma to Hall's marriage theorem, which is known to have several different proofs.

\thetaextbf{Matrix-based proof.} The ``if'' part follows from the definition of absolute singularity. Let us prove the assertion in the ``only if'' part. Assume $V$ is not absolutely singular. This assumption and the assertion are both unchanged up to any product permutation operators on the left- and right-hand sides of $V$. We will refer to the $d_B\thetaimes d_B$ blocks in $V$ still as $V_{j,k}$ since there is no confusion.
The assertion is trivial for $d_A=1,2$. Next we shall use induction over $d_A$. The induction hypothesis is that the assertion holds when $d_A$ is replaced by $2,\chidots,d_A-1$, and we will prove the assertion for $d_A$.
Since $V$ is not absolutely singular, we may assume that $V_{11}$ is nonzero up to a suitable product permutation operator on the right-hand side of $V$. If the submatrix $X=\sigmaum^{d_A}_{j,k=2} \kappaetbra{j}{k}\omegax V_{j,k}$ is not absolutely singular, then the assertion follows from the induction hypothesis on $X$. Suppose $X$ is absolutely singular. By performing two suitable product permutation operators, respectively, from the left- and right-hand side of $V$, we may assume that $V_{j,k}=0$ where $j=2,\chidots,s$, $k=t+1,\chidots,d_A$, and $d_A\gammae s>t\gammae1$. Since $V$ is not absolutely singular, we have $s=t+1$. Using a suitable product permutation operator on the left-hand side of $V$, we may assume that $V=\leftarrowmbdaeft(
                   \betaegin{array}{cc}
                     V_1 & 0 \\
                     V_2 & V_3 \\
                     \epsilonnd{array}
                 \rhoight)$,
where $V_1$ and $V_3$ are, respectively, $(s-1)d_B\thetaimes (s-1)d_B$ and $(d_A-s+1)d_B\thetaimes (d_A-s+1)d_B$ submatrices. Since $V$ is not absolutely singular, neither are $V_1$ and $V_3$. The hypothesis induction implies that the assertion holds for both $V_1$ and $V_3$.
Hence the assertion holds for $V$.
This completes the proof.

\thetaextbf{Equivalence of the lemma to Hall's marriage theorem.}  We use the combinatorial formulation of Hall's marriage theorem in \chiite{Halltheorem}. It involves some given elements, each of which may be in one or more of some given sets. There is a \epsilonmph{marriage condition} that says the number of distinct elements contained in $k$ sets is at least $k$, for any integer $k\gammae 0$. A \epsilonmph{system of distinct representatives} is a set of distinct elements, each of which is in a different set. Hall's marriage theorem says that a system of distinct representatives exists if and only if the marriage condition is satisfied. Let us now describe the equivalence of the current lemma to the above theorem. Take the sets to be the big rows of $V$ labeled by $j$, and the elements to be the big columns labeled by $k$, and let an element $k$ be in a set $j$ if and only if the $V_{j,k}$ is nonzero. Then the marriage condition corresponds to the definition of absolute singularity, and a system of distinct representatives corresponds to a sequence of $d_A$ distinct big column labels $k_i$ ($i=1,\deltaots,d_A$) such that $V_{i,k_i}$ is nonzero. This establishes the equivalence.
\epsilonnd{proof}

\betaegin{theorem}\leftarrowmbdaabel{thm:u_controlled2}
Any bipartite complex permutation unitary has a $3$-sandwich form, composed of controlled-complex-permutation matrices. In particular, if the unitary is a permutation matrix, the $3$-sandwich form is composed of controlled-permutation matrices.
\epsilonnd{theorem}
\betaegin{proof}
The second claim implies the first claim, since any complex permutation unitary is the product of a permutation matrix and a diagonal unitary, the latter can be absorbed into one of the controlled-permutation matrices in the decomposition of the complex permutation unitary. Therefore it suffices to prove the second claim. Suppose $U$ is a bipartite permutation unitary on the $d_A\thetaimes d_B$ system.

Let $U=\sigmaum^{d_A}_{j,k=1} \kappaetbra{j}{k}\omegax U_{j,k}$. Since it is not absolutely singular, it follows from Lemma \rhoef{le:absolutesingular} that there are $d_A$ distinct integers $k_1,\chidots,k_{d_A}$, such that the blocks $U_{1,k_1},\chidots,U_{d_A,k_{d_A}}$ are all nonzero. There are two controlled-permutation matrices $V=\sigmaum^{d_A}_{j=1} \piroj{j}\omegax V_j$ and $W=\sigmaum^{d_A}_{j=1} \piroj{j}\omegax W_j$ from the A side, such that the first entry of any one of the blocks $V_1U_{1,k_1}W_{k_1},\chidots,V_{d_A}U_{d_A,k_{d_A}}W_{k_{d_A}}$ of $VUW$ is one. If $d_B=2$ then $VUW$ is a controlled-permutation unitary from the B side. So the assertion holds. We use the induction over $d_B\gammae2$.
We have $VUW=X\omegax\piroj{1}+Y$, where $X$ is a permutation matrix on $\chiH_A$, and $Y$ is a permutation matrix on $\chiH_A\omegax\kappaet{1}^{\pierp}$. The induction hypothesis on $Y$ implies that $Y=Y_1Y_2Y_3$, where $Y_1,Y_2$ and $Y_3$ are controlled-permutation matrices from A, B and A side, respectively. Hence
\betaegin{eqnarray}
U&=V^\deltag(I_A\omegax\piroj{1}+Y_1)(X\omegax\piroj{1}+Y_2)\nuotag\\
&\chidot\,(I_A\omegax\piroj{1}+Y_3)W^\deltag,
\epsilonnd{eqnarray}
which is a 3-sandwich form of $U$ composed of controlled-permutation matrices. So we have proved the second claim.
This completes the proof.
\epsilonnd{proof}

\sigmamallskip
It is known that the SWAP$_d$ gate defined in Lemma~\rhoef{le:swap} has a decomposition using three bipartite controlled gates \chiite{gc13}. In agreement with the construction in \chiite{gc13}, Theorem \rhoef{thm:u_controlled2} shows that the three gates can be chosen as controlled-permutation gates in a 3-sandwich form.

The theorem also has implications for classical circuits. Define a \epsilonmph{classical reversible circuit} (\epsilonmph{classical permutation gate}) to be a classical circuit that is a permutation on the allowed set of input data. In the bipartite case, suppose $d_A$ and $d_B$ are the number of possible states on the systems $A$ and $B$, respectively, then we say the circuit acts on a $d_A\thetaimes d_B$ system. For example, when $n_A$ and $n_B$ are the number of bits on the two systems, we have $d_A=2^{n_A}$ and $d_B=2^{n_B}$. From Theorem~\rhoef{thm:u_controlled2}, and noting that in the proof of Theorem~\rhoef{thm:u_controlled2} there is no requirement of coherence in both the target unitary and the controlled unitaries in the decomposition, we have
\betaegin{corollary}\leftarrowmbdaabel{cr:u_classical}
Suppose $T$ is a classical reversible circuit on a $d_A\thetaimes d_B$ bipartite system, then $T$ can be implemented using the product of $3$ bipartite classical controlled-permutation gates.
\epsilonnd{corollary}
Note the classical controlled-permutation gates are controlled in the computational basis, as one would expect.  Corollary~\rhoef{cr:u_classical} is also stated in Sec.~3.15 and Appendix E of \chiite{DeVos10}, where the proof approach is by considering the permutation accomplished by the circuit and directly using the Birkhoff-von Neumann theorem (explained below), which has an integer-arithmetic version that says the following: Any matrix of size $n\thetaimes n$ with non-negative integer entries and with row and column sums equal to $q$ can be decomposed as the sum of $q$ permutation matrices of size $n\thetaimes n$. Such a statement appears in \chiite{Peng06}, and a simple proof is by repeated use of Hall's marriage theorem, each time finding a permutation matrix, which is to be subtracted from the original matrix, and this process terminates when the resulting matrix becomes the zero matrix. The construction of the $3$ classical permutation gates is as follows: arrange the $d_A\thetaimes d_B$ computational-basis states in a rectangular table with $d_A$ rows and $d_B$ columns, and define a matrix $M$ to contain integer elements $M_{ij}$ that indicate how many elements in row $i$ of the table are to be transferred to row $j$ of the table after the permutation gate $T$. The first, second, and third controlled-permutation gates permutes among elements in the same row, column, and row, respectively. Each column of the rectangular table after the first gate contains elements that are to be permuted under the second gate. Each permutation in a column corresponds to one permutation matrix in the decomposition of $M$ as the sum of permutation matrices. The argument above roughly describes the proof in \chiite{DeVos10} for Corollary~\rhoef{cr:u_classical}. In comparison, our matrix-based approach for obtaining the circuit decomposition hints at some connections to the sandwich form of general unitaries of the sort in Lemma~\rhoef{le:2xddecomp} and Theorem~\rhoef{thm:u_controlled}.

\sigmamallskip

\sigmaection{Decomposition of multipartite unitary operators}

\leftarrowmbdaabel{sec:multi}

In this section, we study the decomposition of $n$-partite unitary operators $U$ on the space $\omegax^n_{j=1}\chiH_j$ with $\deltaim\chiH_i=d_i$. We define a \thetaextit{generalized m-sandwich form} of $U$ to be a decomposition of the form $U=U_1U_2\chidots U_m$, where any $U_i$ is a controlled unitary controlled in the computational basis from $n-1$ fixed systems. For example, $U_1$ may be controlled from the systems of $\chiH_1,\chidots,\chiH_{n-1}$, $U_2$ may be controlled from the systems of $\chiH_1,\chidots,\chiH_{n-2},\chiH_n$, etc. The computational basis in $\omegax^n_{j=1}\chiH_j$ consists of the product states $\kappaet{j_1,\chidots,j_n}$ where $j_i=1,\chidots,d_i$ for each $i$. The word ``fixed'' means the choices of controlling parties are fixed for each gate $U_i$.  Such choices are a function of the generalized $m$-sandwich form that we choose. In the results in this section, we always fix such choices. We have

\betaegin{proposition}
\leftarrowmbdaabel{pp:multi_controlled}
Any $n$-partite unitary has a generalized $[2\pirod^{n-1}_{j=1}(2d_j-2)-1]$-sandwich form.
\epsilonnd{proposition}
\betaegin{proof}
Let $f(n)=2\pirod^{n-1}_{j=1}(2d_j-2)-1$. The assertion is trivial  for $n=1$, and follows from Theorem \rhoef{thm:u_controlled} for $n=2$. We use the induction on $n$. Assume that any $(n-1)$-partite unitary has a generalized $f(n-1)$-sandwich form.
Let $U$ be an $n$-partite unitary. By regarding $\chiH_A=\chiH_1$ and $\chiH_B=\omegax^n_{j=2}\chiH_j$ in Theorem \rhoef{thm:u_controlled}, we obtain the $(4d_1-5)$-sandwich form
\betaegin{eqnarray}
\leftarrowmbdaabel{eq:multi_controlled}
U=\pirod^{4d_1-5}_{j=1}U_j,
\epsilonnd{eqnarray}
where $U_j$ is controlled in the computational basis of $\chiH_A$ for odd $j$, and of $\chiH_B$ for even $j$, respectively. In particular, the computational basis in the latter is realized by performing suitable unitaries on $\chiH_B$ that can be absorbed by the $U_j$ with odd $j$. Then
\betaegin{eqnarray}
\leftarrowmbdaabel{eq:multi_controlled2}
U_j=\betaigoplus^{d_1}_{k=1} \piroj{k}\omegax U_{jk},  \,\,\forall \mubox{ odd }j,
\epsilonnd{eqnarray}
where each $U_{jk}$ is a unitary on $\chiH_B$. From the induction assumption, $U_{jk}$ has a generalized $[2\pirod^{n-1}_{j=2}(2d_j-2)-1]$-sandwich form. Then \epsilonqref{eq:multi_controlled2} implies that $U_j$ with any odd $j$ has a generalized $[2\pirod^{n-1}_{j=2}(2d_j-2)-1]$-sandwich form. Since $U_j$ with any even $j$ is a controlled unitary controlled in the computational basis of $\chiH_B$, \epsilonqref{eq:multi_controlled} implies that $U$ has a generalized $m$-sandwich form where
\betaegin{eqnarray}\leftarrowmbdaabel{eq:multi_controlled3}
m
&=&(2d_1-2)[2\pirod^{n-1}_{j=2}(2d_j-2)-1]+2d_1-3
\nuotag\\
&=&f(n).
\epsilonnd{eqnarray}
This completes the proof.
\epsilonnd{proof}

\sigmamallskip
The proof above first divides the systems into two groups of one party and $(n-1)$ parties each. When $n\gammae 4$, there are also other ways of dividing the systems at the first step that may give rise to fewer gates in the generalized sandwich form.  The following result is for the case of $n=4$.

\betaegin{proposition}
\leftarrowmbdaabel{pp:multi_controlled2}
Any unitary on four parties $A,B,C,D$ has a generalized $[4 (d_A d_B - 1)(2 d_A + 2 d_C -5)- 4 d_A +5]$-sandwich form.
\epsilonnd{proposition}
\betaegin{proof}
Let $U$ be a unitary on these four parties. By regarding $\chiH_A$ and $\chiH_B$ in Theorem~\rhoef{thm:u_controlled} as $\chiH_{AB}$ and $\chiH_{CD}$ respectively, we obtain the following sandwich form
\betaegin{eqnarray}
\leftarrowmbdaabel{eq:multi_controlled4}
U=\pirod^{4d_A d_B-5}_{j=1}U_j,
\epsilonnd{eqnarray}
where $U_j$ is controlled in the computational basis of $\chiH_{AB}$ for odd $j$, and in the computational basis of $\chiH_{CD}$ for even $j$, respectively.  Then
\betaegin{eqnarray}
\leftarrowmbdaabel{eq:multi_controlled5}
U_j=\betaigoplus^{d_A d_B}_{k=1} \piroj{k}_{AB}\omegax U_{jk},  \,\,\forall \mubox{ odd }j,
\epsilonnd{eqnarray}
where $\piroj{k}_{AB}$ are projectors onto the computational basis of $\chiH_{AB}$, and each $U_{jk}$ is a unitary on $\chiH_{CD}$. From Theorem~\rhoef{thm:u_controlled}, $U_{jk}$ has a generalized $(4d_C-5)$-sandwich form. Then \epsilonqref{eq:multi_controlled5} implies that $U_j$ with any odd $j$ has a generalized $(4d_C-5)$-sandwich form. Similarly, $U_j$ with any even $j$ has a generalized $(4d_A-5)$-sandwich form. Therefore $U$ is the product of
\betaegin{eqnarray}
\leftarrowmbdaabel{eq:multi_controlled6}
&&(2d_Ad_B-2)(4d_C-5)  + (2d_Ad_B-3)(4d_A-5)\nuotag\\
&=&4 (d_A d_B - 1)(2 d_A + 2 d_C -5)- 4 d_A +5
\epsilonnd{eqnarray}
unitaries that are controlled in the computational basis of $3$ parties. This completes the proof.
\epsilonnd{proof}

\sigmamallskip
To compare the two Propositions above, assume $n=4$ in Proposition~\rhoef{pp:multi_controlled} with the subscripts $1,2,3,4$ replaced by $A,B,C,D$, respectively, and that $d_A\leftarrowmbdae d_B\leftarrowmbdae d_C\leftarrowmbdae d_D$. Then Proposition~\rhoef{pp:multi_controlled} gives that $U$ is the product of $16(d_A-1)(d_B-1)(d_C-1)-1$ unitaries that are controlled from $3$ parties.  Therefore, at least when $d_B << d_C$ and $d_A$ is a large constant (say $d_A\gammae 20$), Proposition~\rhoef{pp:multi_controlled2} gives a smaller number than Proposition~\rhoef{pp:multi_controlled}.

The proofs of the results above imply that, if we could reduce the number of bipartite controlled unitaries in the sandwich form in Theorem \rhoef{thm:u_controlled}, then the number of multipartite controlled unitaries in the generalized sandwich form could also be reduced. In particular, from Theorem.~\rhoef{thm:u_controlled2}, we have
\betaegin{proposition}\leftarrowmbdaabel{pp:multi_controlled3}
Any $n$-partite complex permutation unitary has a generalized $(2n-1)$-sandwich form composed of controlled-complex-permutation unitaries controlled by $n-1$ parties.
\epsilonnd{proposition}
\betaegin{proof}
It suffices to consider permutation unitaries, for the same reason as stated in the proof of Theorem~\rhoef{thm:u_controlled2}. From Theorem~\rhoef{thm:u_controlled2}, the claim holds for $n=2$. The proof is by induction over $n$. The induction hypothesis is that the claim holds when $n$ is replaced by any positive integer less than $n$. Now consider $n\gammae 3$, and take a bipartite cut of the first $n-1$ parties versus the last party. From Theorem~\rhoef{thm:u_controlled2}, the permutation unitary has a $3$-sandwich form, and the first and the last gates in the $3$-sandwich form are a controlled permutation controlled from the first $n-1$ parties. The middle gate in the $3$-sandwich form is a controlled permutation controlled from the last party, so it is of the form $U_1\omegax \kappaetbra{1}{1} + U_2 \kappaetbra{2}{2}$, where the permutation operators $U_1$ and $U_2$ on the first $n-1$ parties can each be decomposed into $2(n-1)-1$ controlled-permutation gates controlled by $n-2$ parties, and the choices of those controlling $n-2$ parties are always the same for the decompositions of $U_1$ and $U_2$, according to the induction hypothesis. Therefore the permutation unitary on $n$ parties has a generalized $(2n-1)$-sandwich form composed of controlled-permutation gates controlled by $n-1$ parties. The case with phases is similar, just adding the word ``complex''. This completes the proof.
\epsilonnd{proof}

The result above has a corresponding statement for classical reversible circuits. In the special case that each party is one bit, it is illustrated by a sample circuit in Fig. 2 of \chiite{DeVos10b} (note the sequence of lines is opposite from that in the proof above).

\sigmamallskip
As mentioned in Sec.~\rhoef{sec:bipartite}, it is possible that the literature results on the decomposition of qudit circuits \chiite{blb05,bbo06,dw13} could be combined with the results in this section to give better upper bounds of the number of two-qudit gates.

\sigmaection{Decomposition using a simple type of gates}

\leftarrowmbdaabel{sec:elementary}

In this section, we apply our result on decomposition using controlled unitaries to the decomposition using more basic type of gates defined below.  One of our motivations is to characterize the nonlocal part of the cost for implementing bipartite unitaries using some measure with a fixed unit, rather than using the number of controlled unitaries which is a measure with its unit dependent on the dimensions.   The cost measure that we use is the number of standard gates defined below, and we do not allow any ancillary systems in the circuit. The case with ancillas will be discussed in Sec.~\rhoef{sec:ancilla}. In the following definitions, $I_X$ stands for the identity operator on system $X$.

\betaegin{definition}\leftarrowmbdaabel{def:ele1}
A standard gate is a unitary acting on the Hilbert space $\chiH_{AB}=\chiH_A\omegax\chiH_B$ of the form $U=U_{AB}=(V_{ab}\omegaplus I_{AB\betaackslash ab})$, where $\chiH_{AB}=\chiH_{ab}\omegaplus \chiH_{AB\betaackslash ab}$, and $\chiH_a\sigmaubseteq \chiH_A$ and $\chiH_b\sigmaubseteq \chiH_B$ are two-dimensional each, and $V_{ab}$ is a Schmidt-rank-2 unitary on the $2\thetaimes 2$ space $\chiH_{ab}=\chiH_a \omegax \chiH_b$. The $V_{ab}$ is called the nontrivial part of $U$.
\epsilonnd{definition}

Note the word ``Schmidt-rank-2'' above can be replaced by ``controlled'', as Schmidt-rank-2 unitaries are controlled unitaries (\chiite{cy13}; also see an alternative proof in \chiite{cy14ap}), and two-qubit unitaries of Schmidt rank greater than 2 must have Schmidt rank 4 \chiite{Nielsen03} and thus cannot be controlled unitaries. The case of $\chiH_{AB}$ being strictly larger than $\chiH_{ab}$ is useful, for example, in the decomposition of the Toffoli gate \chiite{rrg07}, and has been experimentally realized \chiite{Lanyon09}. The definition above can be extended to a more general definition below:

\betaegin{definition}\leftarrowmbdaabel{def:ele2}
A bipartite elementary gate is a unitary acting on the Hilbert space $\chiH_A\omegax\chiH_B=(\chiH_{a}\omegax \chiH_C \omegaplus \chiH_D)\omegax(\chiH_{b}\omegax \chiH_E \omegaplus \chiH_F)$ of the form $U=(V_{ab}\omegax I_{CE}) \omegaplus I_{AB\betaackslash abCE}$, where $\chiH_a$ and $\chiH_b$ are two-dimensional each, and $V_{ab}$ is a Schmidt-rank-2 unitary, and $\chiH_{AB}=\chiH_{AB\betaackslash abCE}\omegaplus\chiH_{abCE}$.
\epsilonnd{definition}

In the following we consider the decomposition of bipartite unitary operators into the product of bipartite standard gates defined in Definition~\rhoef{def:ele1} and arbitrary local gates, with the goal of minimizing the number of nonlocal standard gates. The more general Definition~\rhoef{def:ele2} will not be studied in this paper except that we define some gate cost using it in Definition~\rhoef{def:ele4} and raise some open questions.

We define the following gate-cost measures for a bipartite unitary.
\betaegin{definition}\leftarrowmbdaabel{def:ele4}
Let $\chiH=\chiH_A\omegatimes\chiH_B$ be the complex Hilbert space of a finite-dimensional bipartite quantum system, with $\deltaim\chiH_A=d_A$ and $\deltaim\chiH_B=d_B$. For any given bipartite unitary $U: \chiH\rhoa\chiH$,
\betaegin{eqnarray}
\leftarrowmbdaabel{eq:cu}
c_s(U) &:= \muin\{k | U=U_1U_2\chidots U_k,~~U_i\iotan \chiS_{s}\},\nuotag\\
c_e(U) &:= \muin\{k | U=U_1U_2\chidots U_k,~~U_i\iotan \chiS_{e}\},
\epsilonnd{eqnarray}
where $\chiS_{s}$ (respectively, $\chiS_{e}$) is the set of bipartite unitaries on the same space that are equivalent to the standard (respectively, bipartite elementary) gates under local unitaries.
\epsilonnd{definition}

In the case $d_A=d_B=2$, it is well known that three Schmidt-rank-2 gates are sufficient and necessary for a general two-qubit unitary \chiite{vw04}, as mentioned in Sec.~\rhoef{sec:bipartite}. An example that needs three Schmidt-rank-2 gates is the two-qubit SWAP gate (\chiite{vw04}, also see Lemma~\rhoef{le:swap}).  Our main result for general $d_A\thetaimes d_B$ system is as follows.

\betaegin{proposition}
\leftarrowmbdaabel{pp:elem}
(i) Any bipartite unitary on $d_A\thetaimes d_B$ system is the product of $f(d_A,d_B)$ standard gates interspersed with local unitaries on $\chiH_A$ or $\chiH_B$, where
\betaegin{eqnarray}
\leftarrowmbdaabel{eq:elem1}
f(d_A,d_B)
&=&2(d_A-1)^2 \leftarrowmbdafloor \frac{d_B}{2}\rhofloor
\nuotag\\
&+&(2d_A-3)(d_B-1) \leftarrowmbdafloor \frac{d_A}{2}\rhofloor.
\epsilonnd{eqnarray}

(ii) If the unitary is a controlled unitary controlled from the $A$ side, then
\betaegin{eqnarray}
\leftarrowmbdaabel{eq:elem1b}
f(d_A,d_B)=(d_A-1)\leftarrowmbdafloor\frac{d_B}{2}\rhofloor.
\epsilonnd{eqnarray}

(iii) If the unitary is a complex permutation unitary, then
\betaegin{eqnarray}
\leftarrowmbdaabel{eq:elem1c}
f(d_A,d_B)=2(d_A-1)\leftarrowmbdafloor\frac{d_B}{2}\rhofloor+(d_B-1)\leftarrowmbdafloor\frac{d_A}{2}\rhofloor.
\epsilonnd{eqnarray}
(iv) If the nontrivial part of the standard gates is required to be CNOT, then at most $3(d_A-1)(d_B-1)$ such standard gates
together with local permutation gates can implement any bipartite permutation unitary on $d_A\thetaimes d_B$ space.
\epsilonnd{proposition}

\betaegin{proof}
(i). Let $U$ be the bipartite unitary. Theorem~\rhoef{thm:u_controlled} implies that $U$ has the following sandwich form
\betaegin{eqnarray}
\leftarrowmbdaabel{eq:elem2}
U=\pirod^{4d_A-5}_{j=1}U_j,
\epsilonnd{eqnarray}
where $U_j$ is controlled in the computational basis of $\chiH_A$ for odd $j$, and in the computational basis of $\chiH_B$ for even $j$, respectively.  For all odd $j$, we have
\betaegin{eqnarray}
\leftarrowmbdaabel{eq:elem3}
U_j&=&\betaigoplus^{d_A}_{k=1} \piroj{k}_A\omegax U_{jk},\nuotag\\
&=&\pirod^{d_A}_{k=1} [\piroj{k}_A\omegax U_{jk} \omegaplus (I_A-\piroj{k}_A)\omegax I_B ],\quad
\epsilonnd{eqnarray}
where $\piroj{k}_A$ are projectors onto the computational basis of $\chiH_A$, and each $U_{jk}$ is a unitary on $\chiH_B$.
We can apply a local unitary $U_{jd_B}$ on $\chiH_B$ before performing other steps below. In order to implement $U_j$, the operator that remains to be implemented
is still given by \epsilonqref{eq:elem3} but with $U_{jd_B}$ becoming the identity matrix, and the other operators $U_{jk}$ also  changed but we
still denote the changed matrices as $U_{jk}$, with $1\leftarrowmbdae k\leftarrowmbdae d_A-1$.  The $U_j$ is to be implemented using the product
of $d_A-1$ operators, as shown in the second line of \epsilonqref{eq:elem3}. Then each of the $U_{jk}$ with $1\leftarrowmbdae k\leftarrowmbdae d_A-1$ can be assumed to be a diagonal unitary, because we can apply a suitable local unitary similarity transform on $\chiH_B$ so that $U_{jk}$ is diagonal and $I_B$ is unchanged. By a local diagonal unitary gate on $\chiH_A$ which only applies a phase on $\kappaet{k}_A$, we can set the last diagonal element
of $U_{jk}$ to be $1$, while the $I_B$ corresponding to the basis kets in $\chiH_A$ other than $\kappaet{k}_A$ are unchanged.
Therefore we have
\betaegin{eqnarray}
\leftarrowmbdaabel{eq:elem4}
U_{jk}=\deltaiag(x^{(jk)}_1,x^{(jk)}_2,\deltaots,x^{(jk)}_{d_B-1},1),
\epsilonnd{eqnarray}
where $x^{(jk)}_i$ are complex phases, $i=1,2,\deltaots,d_B-1$. Then we choose $\leftarrowmbdafloor \frac{d_B}{2}\rhofloor$ standard gates as follows:
\betaegin{eqnarray}
\leftarrowmbdaabel{eq:elem5}
V^{(jk)}_r=I_A \omegax I_B + (x^{(jk)}_{2r-1}-1) \piroj{k}_A\omegax\piroj{2r-1}_B  \nuotag\\
+ (x^{(jk)}_{2r}-1) \piroj{k}_A\omegax\piroj{2r}_B, \mubox{ for }\,1\leftarrowmbdae r\leftarrowmbdae\leftarrowmbdafloor \frac{d_B}{2}\rhofloor,
~~~~~
\epsilonnd{eqnarray}
Each gate $V^{(jk)}_r$ applies phases on the two states $\kappaet{k}_A \omegax \kappaet{2r-1}_B$ and $\kappaet{k}_A \omegax \kappaet{2r}_B$, but keeps other computational basis states of $\chiH_{AB}$ unchanged.
It is easy to verify that such a gate has Schmidt rank at most 2 when viewed as a unitary acting on the $2\thetaimes 2$ system with basis $\{\kappaet{k'}_A,\kappaet{k}_A\}\thetaimes\{\kappaet{2r-1}_B,\kappaet{2r}_B\}$, where $k'\nueq k$.
Hence for each $(j,k)$ pair with odd $j$ and $1\leftarrowmbdae k\leftarrowmbdae d_A-1$ , we need $\leftarrowmbdafloor \frac{d_B}{2}\rhofloor$ standard gates to implement the operator $\piroj{k}_A\omegax U_{jk} \omegaplus (I_A-\piroj{k}_A)\omegax I_B $ in the last line of \epsilonqref{eq:elem3}. Therefore, for each odd $j$, $U_j$ needs $(d_A-1) \leftarrowmbdafloor \frac{d_B}{2}\rhofloor$ standard gates to implement, assisted by local unitaries.  Similarly, for each even $j$, $U_j$ needs $(d_B-1) \leftarrowmbdafloor \frac{d_A}{2}\rhofloor$ standard gates to implement, assisted by local unitaries. The assertion then follows by counting the numbers of $U_j$ in \epsilonqref{eq:elem2} in terms of odd and even $j$. This completes the proof of (i).

(ii). The claim follows from the proof of (i) by setting the upper bound for $j$ in \epsilonqref{eq:elem2} to $1$.

(iii). The claim follows from Theorem~\rhoef{thm:u_controlled2} and the result of (ii) applied to the $A$ and $B$ sides.

(iv). From Theorem~\rhoef{thm:u_controlled2} , every bipartite permutation unitary is the product of $3$ controlled-permutation unitaries, controlled from the $A$, $B$ and $A$ side, respectively. Every permutation on $n$ elements is the product of at most $n-1$ transpositions (swap of two elements). Define a controlled-transposition gate to be a bipartite unitary of the form $\kappaetbra{1}{1}_A\omegax I_B + \kappaetbra{2}{2}_A\omegax V_B$, where $V_B=\kappaetbra{j}{k}+\kappaetbra{k}{j}+\sigmaum_{i\nue j,k}\kappaetbra{i}{i}$, for some $j\nue k$ ($\{\kappaet{i}\}$ is the computational basis of $\chiH_B$). For the special case $d_A=2$, up to a local permutation on $\chiH_B$ we can write a controlled-permutation gate from the $A$ side as $\kappaetbra{1}{1}\omegax I_B + \kappaetbra{2}{2}\omegax P_2$, where $P_2$ is a permutation unitary on $\chiH_B$. This controlled-permutation gate can be written as the product of at most $d_B-1$ controlled-transposition gates, which are standard gates with their nontrivial part being the CNOT. For larger $d_A$, up to a local permutation on $\chiH_B$ we can write the controlled-permutation gate as $\kappaetbra{1}{1}\omegax I_B + \sigmaum_j \kappaetbra{j}{j}\omegax P_j$, where $P_j$ are permutation unitaries on $\chiH_B$. Take the subspace span$\{\kappaet{1}_A,\kappaet{j}_A\}$ ($2\leftarrowmbdae j\leftarrowmbdae d_A$) as the $A$ side space in the $d_A=2$ result above; we have that at most $d_B-1$ standard gates with the nontrivial part being CNOT can implement $(I_A-\kappaetbra{j}{j})\omegax I_B + \kappaetbra{j}{j}\omegax P_j$. Repeat this $d_A-1$ times for $j=2,\deltaots,d_A$, a controlled-permutation gate from the $A$ side can be implemented using at most $(d_A-1)(d_B-1)$ such standard gates. The last result is the same for the $B$ side. Hence the claim follows.
\epsilonnd{proof}

\sigmamallskip
It can be verified that in Proposition~\rhoef{pp:elem}(iv), the phrase ``together with local permutation gates'' can be dropped by allowing the nonlocal unitary to be implemented up to local permutations before and after it. Since a permutation gate on $d$-dimensional space requires at most $d-1$ transpositions of the type $\kappaetbra{j}{k}+\kappaetbra{k}{j}+\sigmaum_{i\nue j,k}\kappaetbra{i}{i}$, the four local permutations on $\chiH_A$ or $\chiH_B$ require at most $2d_A+2d_B-4$ local transpositions in total. Therefore the total number of standard gates of the CNOT type and the local transpositions is at most $3(d_A-1)(d_B-1)+2d_A+2d_B-4=3d_A d_B -d_A -d_B - 1$. It could potentially be further reduced by a constant factor, and this is listed as an open problem in the Conclusions.

From \chiite{gc13} and Proposition \rhoef{pp:elem} (ii), the SWAP$_d$ gate has a decomposition using $3(d-1)\leftarrowmbdafloor \frac{d}{2}\rhofloor$ standard gates across the two systems, together with some local unitaries.
On the other hand, if we are not restricted to writing the SWAP$_d$ gate as a product of some gates, but consider the actual cost of implementation, we could also make use of tensor products.
Suppose $d=\pirod_{j=1}^m p_j$, where $m\gammae 1$ is an integer and $p_j$ are primes. Then the SWAP$_d$ gate is the tensor product of the SWAP gates on $p_j\thetaimes p_j$ systems. The SWAP gate on $p_j\thetaimes p_j$ system has a decomposition using $3(p_j-1)\leftarrowmbdafloor \frac{p_j}{2}\rhofloor$ bipartite standard gates, together with some local unitaries. Hence the total implementation cost is $\sigmaum_{j=1}^m 3(p_j-1)\leftarrowmbdafloor \frac{p_j}{2}\rhofloor$ bipartite standard gates, together with some local unitaries.

\sigmaection{The role of Schmidt rank in decomposition of bipartite unitaries}
\leftarrowmbdaabel{sec:Schmidt}

The Schmidt rank of a bipartite unitary $U$ sometimes determines the number of bipartite controlled unitaries needed to decompose $U$, as it is proved in \chiite{cy13,cy14ap} that $c(U)=1$ when ${\rhom Sch}(U)=2$ or $3$. To investigate the relation between $c(U)$ and ${\rhom Sch}(U)$ for general bipartite unitary $U$, we discuss the different cases characterized by how large $r:={\rhom Sch}(U)$ is compared to the dimensions $d_A$ and $d_B$. If $r\gammae \muin\{d_A,d_B\}$, then it follows from Theorem~\rhoef{thm:u_controlled} (applied to the $A$ or $B$ side) that $c(U)\leftarrowmbdae 4r-5$. On the other hand if $r< \muin\{d_A,d_B\}$, then we need to count the number of parameters in $U$. It is equal to $(d_A^2-r+d_B^2)r$, which is smaller than $2d_Ad_B^2$ when $d_A\leftarrowmbdae d_B$. A controlled unitary from the $A$ side contains $d_A d_B^2$ parameters, and noting that there are some redundant parameters when counting consecutive controlled unitaries in a product, theoretically $U$ could be the product of only three controlled unitaries (or even two when $r$ is further restricted to smaller values). But the actual number may be higher. A possible class of candidate examples that \epsilonmph{may} need more than three controlled unitaries is the $U'$ in Example~\rhoef{ex:u_6gates} below.

We now show a class of examples where $c(U)$ is much smaller than ${\rhom Sch}(U)$ (note that a generic permutation matrix already has this property, according to Theorem~\rhoef{thm:u_controlled2}, but our interest here is to show the derived class of examples $U'$ that fit into the requirement $r< \muin\{d_A,d_B\}$ in the previous paragraph).
\betaegin{example}\leftarrowmbdaabel{ex:u_6gates}
{\rhom
Let $V_{CB}$ be a generic unitary on $d\thetaimes d$ system of Schmidt rank $d^2$ with $d>2$, and let $U=V_{CB}\omegax I_D$, where $D$ is of the same size as $B$ and $C$ ($d$ dimensions). Then $U$ is of Schmidt rank $d^2$ across the bipartite cut $CD$-$B$. But there is a decomposition using only $6$ controlled unitaries: first, swap the states of the systems $D$ and $B$, using $3$ controlled gates \chiite{gc13}, then do the $V$ on $CD$, and finally swap the $D$ and $B$ again, using another $3$ controlled gates. The local unitary on $CD$ in the second step could be absorbed into the two controlled unitaries before and after it, thus only $6$ controlled unitaries are needed in total without extra local unitaries. Now consider the unitary $U'=U \omegax I_E\omegax I_F$, where $E$ is one qubit and $F$ is of dimension $2d$. Then $U'$ of Schmidt rank $d^2$ across the $CDE$-$BF$ cut, and $c(U')\leftarrowmbdae 6$, and the Schmidt rank $r=d^2$ satisfies $r< \muin\{d_{CDE},d_{BF}\}$, fitting into the requirement in the first paragraph of this section.
}
\epsilonnd{example}

Speaking about the general dependence of $c(U)$ on ${\rhom Sch}(U)$, the two classes of examples $U$ and $U'$ in Example~\rhoef{ex:u_6gates} show that $c(U)$ is not lower bounded by a function of ${\rhom Sch}(U)$ with maximum or supremum value greater than $6$.  Whether $c(U)$ is upper bounded by a function of ${\rhom Sch}(U)$ is unknown, and this is listed as an open question in Sec. \rhoef{sec:con}.

\sigmaubsection{Nonlocal cost of bipartite permutation operators}\leftarrowmbdaabel{sec:permutation}

We have shown in Theorem~\rhoef{thm:u_controlled2} that every bipartite permutation operator can be implemented by three controlled unitaries, but such controlled unitaries may be hard to implement since they are on $d_A\thetaimes d_B$ space.  A better measure of the nonlocal part of the gate cost (i.e., the nonlocal gate cost) is in terms of the bipartite elementary gates of Definition~\rhoef{def:ele2}. Two results that depend on $d_A$ and $d_B$ are given in Proposition~\rhoef{pp:elem}(iii)(iv), though special classes of the bipartite elementary gates are used therein. In this subsection we study the nonlocal gate cost as a function of the Schmidt rank or dimension of the bipartite permutation unitary.  The obtained upper bounds could be much less than those in Proposition~\rhoef{pp:elem}(iii)(iv) for some classes of permutation unitaries. The result can also be stated in terms of the entanglement cost under local operations and classical communications (LOCC). Hence it provides a significant class of examples that the entanglement cost of a bipartite unitary is upper bounded by a function of Schmidt rank independent of the dimensions. The only known result of this flavor is about Schmidt-rank-$2$ unitaries, which are implementable using one ebit of entanglement under LOCC \chiite{cy13}.
To study the nonlocal gate cost, we first present some definitions and preliminary lemmas.\betaegin{definition}\leftarrowmbdaabel{def:pp}
A partial permutation matrix is a matrix with elements $0$ or $1$ only, with at most one nonzero element on each row and column.  The input (respectively, output) space for such matrix is the complex Hilbert space that is the span of the computational basis states corresponding to the nonzero columns (respectively, rows) of the matrix.
\epsilonnd{definition}

\betaegin{definition}\leftarrowmbdaabel{def:pprank}
The partial-permutation rank of a bipartite operator $U$, denoted ${\rhom ppr}(U)$, is the minimum number of terms $q$ such that
\betaegin{eqnarray}\leftarrowmbdaabel{eq:ppexpansion}
U=\sigmaum_{j=1}^q A_j \omegax B_j,
\epsilonnd{eqnarray}
where $A_j$ and $B_j$ are partial permutation operators on $\chiH_A$ and $\chiH_B$.
\epsilonnd{definition}
The above two definitions imply that if a bipartite operator has a partial-permutation rank, then its entries are non-negative integers. So the partial-permutation rank is not defined for a bipartite operator containing a negative or non-integer entry in its matrix. The partial-permutation rank of the bipartite permutation matrices will be studied in Lemma~\rhoef{le:partial_permutation2}.

\betaegin{lemma}\leftarrowmbdaabel{le:bipartite_CNOT}
Suppose $U$ is a bipartite controlled unitary of the form $P_1\omegax V_1 + P_2 \omegax V_2$, where $P_1$ and $P_2$ are orthogonal projectors on $\chiH_A$, and $V_1$ and $V_2$ are unitaries on $\chiH_B$. With the help of a one-qubit ancilla on each side, $U$ can be implemented using two bipartite CNOT gates and some local unitary gates. The initial and final states of each ancilla qubit are the same.
\epsilonnd{lemma}
\betaegin{proof}
Let $a$ and $b$ denote the qubit ancillas on the $A$ and $B$ side initialized in the state $\kappaet{0}_a$ and $\kappaet{0}_b$, respectively.
The unitary $U$ can be implemented using the ancillas and one CNOT gate with the following sequence of gates: a controlled gate on $\chiH_{Aa}$: $V_{Aa}=P_1 \omegax I_a+ P_2\omegax X_a$, where $X_a=\kappaetbra{0}{1}_a+\kappaetbra{1}{0}_a$ (similar below with subscripts changed), and a CNOT gate on $\chiH_{ab}$: $\mubox{CNOT}_{ab}=\kappaetbra{0}{0}\omegax I_b + \kappaetbra{1}{1}\omegax X_b$, and a controlled gate on $\chiH_{bB}$: $W_{bB}=\kappaetbra{0}{0}\omegax V_1 + \kappaetbra{1}{1}\omegax V_2$, and then $\mubox{CNOT}_{ab}$ again to erase the state on $b$ to $\kappaet{0}_b$, and the $V_{Aa}$ again to erase the state on $a$ to $\kappaet{0}_a$. This implements $U$ without changing the states of $a$ and $b$.
\epsilonnd{proof}

\betaegin{lemma}\leftarrowmbdaabel{le:partial_permutation}
Suppose $U$ is a bipartite permutation unitary of partial-permutation rank $q$. Then the following statements hold:\\
(i) with the help of a one-qubit ancilla on one party and a two-qubit ancilla on the other party, $U$ can be implemented using at most $6q$ bipartite CNOT gates and some local permutation gates.\\
(ii) with the help of a one-qubit ancilla on either party and $3q$ ebits of entanglement, $U$ can be implemented using LOCC.
\epsilonnd{lemma}
\betaegin{proof}
(i) Consider the matrix representation of $U$ in the computational basis of $\chiH_A\omegax \chiH_B$.   Then $U$ can be expanded as $U=\sigmaum_{j=1}^q A_j\omegax B_j$, where $A_j$ and $B_j$ are partial permutation matrices.
Each $A_j$ or $B_j$ has an input space and an output space as defined in Definition~\rhoef{def:pp}. Assume without loss of generality that the two-qubit ancilla is on the $B$ side. Denote the ancilla qubit on the $A$ side as $a$, and the two ancilla qubits on the $B$ side as $b$ and $c$. Let $\{\kappaet{0},\kappaet{1}\}$ (with suitable subscripts $a$,$b$,$c$) be the computational basis of each ancilla qubit. Let the initial state of each of the ancilla qubits be $\kappaet{0}$.

Now let us visualize the computational basis of $\chiH_A\omegax \chiH_B$ as a rectangular table, with the rows labeling the computational basis states of $\chiH_A$, and columns for those of $\chiH_B$.  The input spaces of $A_j\omegax B_j$ ($j=1,\deltaots,q$) correspond to small (disconnected) rectangles in such a table. In other words, the computational basis states in the input space of $A_j\omegax B_j$ take all intersections of some rows and some columns of the table. In the following we abbreviate the word ``disconnected'' since it turns out that the rows and columns in such a ``small rectangle'' need not be consecutive in our argument.

The whole table of size $d_A\thetaimes d_B$ is thus partitioned into $q$ disjoint small rectangles.  The output spaces of $A_j\omegax B_j$ also correspond to small rectangles in the table. Our goal is to move the small rectangles to their respective desired positions, while for each such rectangle, we also hope to do an internal permutation of elements according to the form of $A_j$ and $B_j$.  Such internal permutation of elements is the tensor product of two permutations on a subspace of $\chiH_A$ and a subspace of $\chiH_B$, respectively. But given that there may be some overlap between the input rectangle for one $j$ and the output rectangle for a different $j$, it is hard to do an in-place swap of the rectangles. We avoid this problem by making use of the ancilla qubit $c$, since it effectively supplies two copies of the whole table of size $d_A\thetaimes d_B$, corresponding to the states $\kappaet{0}_c$ and $\kappaet{1}_c$, respectively. The latter copy is called the \epsilonmph{backup copy} below.

For each $j=1,\deltaots,q$, we perform the following procedure which consists of $3$ controlled-permutation gates. Denote by $P$ the rectangle corresponding to the input space of $A_j\omegax B_j$ in the original copy of the table. We first do a controlled-permutation unitary controlled in the computational basis of $\chiH_A$ to swap the elements in $P$ into the place (denoted by $M$) in the backup copy of the table and in the target columns. Then perform a controlled-permutation unitary controlled in the computational basis of $\chiH_B\omegax \chiH_c$ to swap the block $M$ into the desired rows in the backup copy (denote the target rectangle by $Q$). Now the part of $M$ that is not in $Q$ (denoted by $M\betaackslash Q$) is an all-zero block (for any input state of the form $\kappaet{\pisi}_{AB}\omegax \kappaet{0}_c$), but it should have the original contents before these two gates were applied, as it is not the output position for the original $P$. Therefore, we lastly perform a controlled unitary controlled in the computational basis of $\chiH_A$ to swap the partial rectangle $M\betaackslash Q$ and its corresponding part in $P$.  Note that if $M\betaackslash Q$ is an empty set, the last two unitary gates are actually the identity operation. After the $3$ gates, the original probability amplitudes in $M\betaackslash Q$ are unchanged, but the probability amplitudes in $P$ and $Q$ are swapped. Since the original state had zero probability amplitude in $Q$ in the backup copy (note this is still true for $j>1$ according to our procedure here), the state after these $3$ gates has zero probability amplitude in the rectangle $P$ (in the original copy).  The internal permutations required in each rectangular block can be accomplished in the first two of these three controlled-permutation gates.

After performing the (at most) $3q$ controlled-permutation gates, we do a local $X_c$ gate on particle $c$ to swap the states $\kappaet{0}_c$ and $\kappaet{1}_c$. Now the $U$ is implemented and the ancilla qubits are back in their original state. The local gate $X_c$ can be absorbed into the last one of those (at most) $3q$ gates, which is a bipartite controlled-permutation gate controlled in the computational basis of $\chiH_A$. Thus $U$ is implemented using at most $3q$ controlled-permutation unitaries, with the help of the ancilla qubit $c$. Lemma~\rhoef{le:bipartite_CNOT} implies that each of these controlled-permutation gates, which can be written in two terms, can be implemented using two bipartite CNOT gates and some local gates, the latter are local permutation gates in the current case. The two ancilla qubits used are $a$ and $b$, and they can be recycled through these applications of Lemma~\rhoef{le:bipartite_CNOT}, because they start and end in the $\kappaet{0}$ state in each application. Hence at most $6q$ bipartite CNOT gates and some local permutation gates can implement $U$ with the help of the ancilla qubits $a$, $b$ and $c$. This completes the proof of (i).

(ii) The proof is similar to (i), but note that each of the (at most) $3q$ bipartite controlled-permutation gate with two terms can be implemented using 1 ebit of entanglement and LOCC \chiite{ygc10}. Thus we need at most $3q$ ebits in total and also need the ancilla qubit $c$, but do not need the ancillary qubits $a$ and $b$. This completes the proof of (ii).
\epsilonnd{proof}

\sigmamallskip
Next we relate the partial-permutation rank with the Schmidt rank.
\betaegin{lemma}\leftarrowmbdaabel{le:partial_permutation2}
Suppose the bipartite permutation unitary has partial-permutation rank $q$ and Schmidt rank $r$. Then $q\leftarrowmbdae\muin\{d_A^2, d_B^2, d_A r, d_B r, 2^r\}$.
\epsilonnd{lemma}
\betaegin{proof}
Suppose $U$ is the bipartite permutation unitary on the $d_A\thetaimes d_B$ system. The matrix $U$ consists of $d_A^2$ blocks, each of which is a $d_B\thetaimes d_B$ partial permutation matrix. We denote them by $B_{jk}$, so that $U=\sigmaum_{jk} \kappaetbra{j}{k}\omegax B_{jk}$.
Since $\kappaetbra{j}{k}$ is also a partial permutation matrix, we have $q\leftarrowmbdae d_A^2$ and by symmetry $q\leftarrowmbdae d_B^2$.
Since $U$ is a permutation matrix, the nonzero blocks $B_{jk}$ for fixed $j$ are linearly independent. So the number of them is not greater than $r$. It holds for $j=1,2,\deltaots,d_A$. Thus the total number of nonzero $B_{jk}$ is not greater than $d_A r$. Therefore $q\leftarrowmbdae d_A r$. By symmetry of the $A$ and $B$ sides, we have $q\leftarrowmbdae d_B r$.

It remains to prove $q\leftarrowmbdae 2^r$. Suppose $\{F_i\}_{i=1}^r$ is a set of $r$ linearly independent blocks among $B_{jk}$.  All other blocks that are not included in the set $\{F_i\}_{i=1}^r$ are linear combinations of the $F_j$. This last property does not change if we replace $\{F_i\}_{i=1}^r$ by $\{G_i\}_{i=1}^r$. Here each $G_i$ is a linear combination of the $F_j$, and is of the standard form $G_i(t)=\deltaelta_{it}$, $i=1,2,\deltaots,r$, where $G_i(t)$ is the $t$-th matrix element of $G_i$ according to some fixed ordering of the matrix elements, and $\deltaelta_{it}$ is the Kronecker delta function. Note that such orderings of matrix elements must exist but may not be the usual row-first ordering, as it depends on the operators $F_i$. Then any $B_{jk}$ as a linear combination of $G_i$ ($i=1,2,\deltaots,r$) must satisfy that the coefficient for $G_i$ is either $0$ or $1$, since the resulting matrix is a $(0,1)$-matrix which implies that its first $r$ elements (in the ordering above) must be either $0$ or $1$. Thus there are at most $2^r$ choices of the ordered set of coefficients, leading to at most $2^r$ distinct blocks $B_{jk}$. Denote the distinct $B_{jk}$ as $D_l$, $l=1,2,\deltaots,m$. Then $m\leftarrowmbdae 2^r$, and $U=\sigmaum_{l=1}^m \leftarrowmbdaeft(\sigmaum_{(j,k)\iotan S_l}\kappaetbra{j}{k}\rhoight)\omegax D_l$, where $S_l=\{(j,k): B_{jk}=D_l\}$. Since $U$ is a permutation matrix, the operators $\sigmaum_{(j,k)\iotan S_l}\kappaetbra{j}{k}$ are partial permutations, for any $l$. Hence $q\leftarrowmbdae m\leftarrowmbdae 2^r$. This completes the proof.
\epsilonnd{proof}

\sigmamallskip
Lemmas~\rhoef{le:partial_permutation} and \rhoef{le:partial_permutation2} immediately imply

\betaegin{theorem}\leftarrowmbdaabel{thm:u_permutation}
Suppose $U$ is a bipartite permutation unitary of Schmidt rank $r$. With the help of a one-qubit ancilla on one party and a two-qubit ancilla on the other party, $U$ can be implemented using at most $6\muin\{d_A^2, d_B^2, d_A r, d_B r, 2^r\}$ bipartite CNOT gates and some local permutation gates. Alternatively, $U$ can be implemented using LOCC and at most $3\muin\{d_A^2, d_B^2, d_A r, d_B r, 2^r\}$ ebits of entanglement with the help of one ancillary qubit on either party.
\epsilonnd{theorem}

The theorem can also be stated for classical reversible circuits, by making minor changes such as replacing ``qubit'' with ``bit'', and ``local permutation gates'' with ``local reversible gates''.

In Lemma~\rhoef{le:partial_permutation2}, the dimension-independent upper bound $2^r$ may still be improved.
However, the following Example~\rhoef{ex:example1} provides evidence that at least for a class of bipartite permutation matrices, the partial-permutation rank grows fast with $r$ (but is not known to be exponential). The operational meaning of the Schmidt rank $r$ is that its logarithm is an upper bound of how many ebits of entanglement a bipartite unitary can create starting from a product state (possibly with local ancillas). Thus the separation between the partial-permutation rank and the Schmidt rank gives some indication about the separation of the entangling power and the entanglement cost under our protocol in the proof of Lemma~\rhoef{le:partial_permutation}.

Before presenting the example, we first define some versions of ranks for matrices. Let $\rhoank(T)$ denote the usual rank of a matrix $T$.

\betaegin{definition}\leftarrowmbdaabel{def:ranks}
(i). For a matrix $T$ with nonnegative elements, the nonnegative rank \chiite{nonnegativerank} $\rhoank^{+}(T)$ is the minimum number of rank-1 matrices with nonnegative elements that sum to $T$.\\
(ii). For a binary matrix $T$ (binary means the elements are 0 or 1), the binary rank \chiite{xorrank} $\rhoank_N(T)$ is the minimum number of rank-1 binary matrices that sum to $T$.\\
(iii). For a binary matrix $T$, the XOR rank \chiite{xorrank} $\rhoank_X(T)$ (also called modulo-2 rank) is the minimum number of rank-1 binary matrices such that their sum modulo 2 is $T$. It is also equal to the rank over the finite filed $\muathbb{F}_2$, or the number of linearly independent rows (or columns) under arithmetic operations in $\muathbb{F}_2$.
\epsilonnd{definition}
It is apparent that $\rhoank(T)\leftarrowmbdae\rhoank^{+}(T)\leftarrowmbdae\rhoank_N(T)$ and $\rhoank_X(T)\leftarrowmbdae\rhoank_N(T)$ hold for any binary matrix $T$, and according to \chiite{xorrank}, $\rhoank_X(T)$ and $\rhoank(T)$ are generally incomparable.

\betaegin{example}\leftarrowmbdaabel{ex:example1}
{\rhom
Consider bipartite permutation unitaries of the form
\betaegin{eqnarray}\leftarrowmbdaabel{eq:perm_example}
U=\sigmaum_{i=1}^M (\kappaetbra{2i-1}{2i-1} + \kappaetbra{2i}{2i})\omegax  (I_B-C_i) \nuotag\\
+ (\kappaetbra{2i-1}{2i} + \kappaetbra{2i}{2i-1})\omegax  C_i,
\epsilonnd{eqnarray}
where $C_i$ are $d_B\thetaimes d_B$ diagonal partial permutation matrices, $i=1,2,\deltaots,M$. The diagonal part of $U$ is $U_{diag}=\sigmaum_{i=1}^M (\kappaetbra{2i-1}{2i-1} + \kappaetbra{2i}{2i})\omegax  (I_B-C_i)$. It is a partial permutation matrix, but its elements are all diagonal so the implementation is trivial, thus the implementation cost of $U$ in terms of the protocol in the proof of Lemma~\rhoef{le:partial_permutation} is determined by the off-diagonal part of $U$, which is denoted $U_{od}:=\sigmaum_{i=1}^M (\kappaetbra{2i-1}{2i} + \kappaetbra{2i}{2i-1})\omegax  C_i$. Hence ${\rhom ppr}(U_{od})$ is proportional to the nonlocal implementation cost under our protocol.  The diagonal elements of the matrices $C_i$ can be rearranged into a matrix $T$ of size $M\thetaimes d_B$ with elements $T_{jk}=\betaegin{remark}a{k}_B C_j\kappaet{k}_B$. It is known that $\rhoank^{+}(T)\leftarrowmbdae\rhoank_N(T)$. And $\rhoank_N(T)={\rhom ppr}(U_{od})$, since the minimum-term expansion of $U_{od}$ of the form \epsilonqref{eq:ppexpansion} must involve local operators on $\chiH_A$ which are the tensor product of a diagonal partial permutation operator on an $M$-dimensional space and the operator $\kappaetbra{1}{2}+\kappaetbra{2}{1}$ on a two-dimensional space, and the partial permutation operators on $B$ are diagonal. These two types of diagonal partial permutation operators mentioned above correspond to the column and row vectors in an expansion of $T$ in terms of direct products of binary column and row vectors. Therefore $\rhoank^{+}(T)\leftarrowmbdae\rhoank_N(T) = {\rhom ppr}(U_{od})$. On the other hand, $\rhoank(T)\gammae {\rhom Sch}(U_{od})$, since the expansion of $T$ using $\rhoank(T)$ terms which are the direct products of a column vector and a row vector, corresponds to an expansion of $U_{od}$ in terms of tensor-product operators. Therefore, any separation between $\rhoank(T)$ and $\rhoank^{+}(T)$ provides a lower bound for the separation between ${\rhom Sch}(U_{od})$ and ${\rhom ppr}(U_{od})$. By the way, for this $U$ we have $\varepsilonrt{\rhom Sch}(U_{od})-{\rhom Sch}(U)\varepsilonrt \leftarrowmbdae 1$, since the diagonal blocks are $I_B-C_i$, and the Schmidt rank is equal to the number of linear independent $d_B\thetaimes d_B$ blocks in the matrix $U$. The operational meaning of ${\rhom Sch}(U)$ is mentioned before the example.

From \chiite{Kol14}, there is a class of $(0,1)$-matrices $T$ such that the separation between $\rhoank_{\epsilon}(T)$ and of $\rhoank^{+}_{\epsilon}(T)$ is at least quasipolynomial (but not known to be exponential), more precisely, $\leftarrowmbdaog \rhoank^{+}_{\epsilon}(T) \gammae \Omegamega\leftarrowmbdaeft(\leftarrowmbdaog^2 \rhoank_{\epsilon}(T)\rhoight)$ for such $T$.  The subscript $\epsilon$ means the $T$ could be replaced by a matrix that approximates $T$ to accuracy $\epsilon$ for evaluation of the rank, which makes sense in terms of physical implementation. Therefore the separation between ${\rhom Sch}_{\epsilon}(U_{od})$ and ${\rhom ppr}_{\epsilon}(U_{od})$ is at least quasipolynomial for a certain class of permutation matrix $U$, where the subscript $\epsilon$ has the same meaning as above.

It is interesting to note that the problem of the separation of the rank and nonnegative rank is related to the log-rank conjecture  \chiite{LovaszS88} in communication complexity theory (as remarked in \chiite{Kol14}). It is curious that the nonlocal cost for implementing bipartite permutation unitaries (or reversible circuits) under our protocol is related to the communication complexity theory in this unexpected way.
\qed }
\epsilonnd{example}

The lower bound mentioned above is not polynomial. So our protocol in the proof of Lemma~\rhoef{le:partial_permutation} is not efficient for some subclass of bipartite permutation unitaries represented by Eq.~\epsilonqref{eq:perm_example}. There is an alternative method of implementing these unitaries, illustrated in Example~\rhoef{ex:example2} below, by noting that the local gate $\kappaetbra{2i-1}{2i} + \kappaetbra{2i}{2i-1}$ applied twice is the projector on the two-dimensional subspace spanned by $\kappaet{2i-1}$ and $\kappaet{2i}$. Rather than expanding $U_{od}$ using the form \epsilonqref{eq:ppexpansion}, we can write $U$ as the product of some controlled-permutation unitaries controlled in the computational basis of $\chiH_B$, where the controlled operators on $\chiH_A$ are either $I_A$, or a permutation unitary which is the direct sum of an identity operator on a two-dimensional subspace, with another operator which is the tensor product of the identity operator on an $(M-k)$-dimensional space and the operator $\kappaetbra{1}{2}+\kappaetbra{2}{1}$ on a two-dimensional space. Each such controlled-permutation gate can be implemented using two bipartite CNOT gates and some local unitaries with the method in Lemma~\rhoef{le:bipartite_CNOT}. The nontrivial part of these controlled-permutation unitaries could overlap with each other. It corresponds to that in the expansion of $T$ in terms of binary vectors, the operator XOR is to be used instead of the usual ``+'' operator. That is, $T=\omegaplus_j (u_j \omegax v_j)$, where $u_j$ and $v_j$ are binary column and row vectors, respectively, and $\omegaplus$ represents element-wise XOR operation (modulo-2 addition) of two or more matrices. Therefore, the relation between the XOR-rank of binary matrices and the rank of these matrices is relevant for the separation of the implementation cost and the Schmidt rank of $U$. In general, there is no definite inequality relation between the XOR-rank and the rank of a binary matrix \chiite{xorrank}. Thus there may be some cases where this modified protocol is quite efficient, but in the other cases it is not too bad either, since $\rhoank_X(T)\leftarrowmbdae\rhoank_N(T)$ holds for any binary matrix $T$, meaning that it is better than the original protocol.

\betaegin{example}\leftarrowmbdaabel{ex:example2}
{\rhom
Let $U$ be of the form in Eq.~\epsilonqref{eq:perm_example}, where $d_A=6$, $M=d_B=3$, and $C_1=\deltaiag(1,1,0)$, $C_2=\deltaiag(1,0,1)$, $C_3=\deltaiag(0,1,1)$. Let $V=(X\omegaplus X\omegaplus I_2)\omegax \deltaiag(1,1,0) + I_6 \omegax \deltaiag(0,0,1)$, where $X=\kappaetbra{1}{2}+\kappaetbra{2}{1}$, and $I_n$ is the $n\thetaimes n$ identity matrix. Let $W=(I_2\omegaplus X\omegaplus X)\omegax \deltaiag(0,1,1) + I_6 \omegax \deltaiag(1,0,0)$. Then $U=VW$. Each of $V$ and $W$ can be implemented by two bipartite CNOT gates (ignoring local unitary gates; same as below). Hence $U$ can be implemented by four bipartite CNOT gates. In comparison, the protocol in the proof of Lemma~\rhoef{le:partial_permutation}, enhanced by doing nontrivial operations for the off-diagonal part $U_{od}$ only, requires $6$ bipartite CNOT gates (the partial permutation rank of $U_{od}$ is $q=3$, and a reduction by a factor of $3$ applies because the partial permutations are in-place).
The corresponding $T$ matrix is
\betaegin{eqnarray}
T=\leftarrowmbdaeft(\betaegin{array}{ccc}
                     1 & 1 & 0 \\
                     1 & 0 & 1 \\
                     0 & 1 & 1
                   \epsilonnd{array}\rhoight).
\epsilonnd{eqnarray}
It has rank $3$, and XOR rank $2$. This is the simplest example of a binary matrix that has its XOR rank less than the rank.
}
\epsilonnd{example}

\sigmaection{The case with ancillas}
\leftarrowmbdaabel{sec:ancilla}

The use of ancillas of constant size has been seen in the previous section. In this section, we show that the use of ancillas of variable size (sometimes required to be initialized in fixed states) can be useful for reducing the controlled-gate cost $c(U)$ or the number of CNOT gates needed, but sometimes at the cost of modifying the $U$ (e.g., the tensor product $U\omegax I_G$ instead of $U$ itself is used in Proposition~\rhoef{pp:cu_inequality} below).

\betaegin{proposition}\leftarrowmbdaabel{pp:CNOT_with_ancillas}
Any bipartite unitary $U$ on $d_A\thetaimes d_B$ system can be implemented by $4\leftarrowmbdaceil\leftarrowmbdaog_2 \muin\{d_A,d_B\}\rhoceil$ bipartite CNOT gates and some local unitaries, with the help of $\leftarrowmbdaceil\leftarrowmbdaog_2 \muin\{d_A,d_B\}\rhoceil$ ancilla qubits.
\epsilonnd{proposition}
\betaegin{proof}
The circuit for implementing $U$ is as follows: send the state of one system (which is embedded in an integer number of qubits) to the other party using $2\leftarrowmbdaceil\leftarrowmbdaog_2 \muin\{d_A,d_B\}\rhoceil$ CNOT gates, then perform the $U$ locally, and finally send the state of the said system back using the inverse of the first part of the circuit.  The first part of the circuit is a tensor product of many subcircuits each sending one qubit. Each such subcircuit is exactly the one-bit teleportation circuit in \chiite{zlc00}, and requires one ancilla qubit which is initially in a fixed state and finally contains the one-qubit state being transferred. The number of subcircuits in the first part of the whole circuit is $\leftarrowmbdaceil\leftarrowmbdaog_2 \muin\{d_A,d_B\}\rhoceil$, and since final transfer back to the first system reuses the original qubits, no extra ancillas are needed, therefore the total number of ancilla qubits needed is $\leftarrowmbdaceil\leftarrowmbdaog_2 \muin\{d_A,d_B\}\rhoceil$.
\epsilonnd{proof}

Some special classes of bipartite unitaries can be implemented with small amounts of entanglement and classical communication \chiite{ygc10}, which can also be expressed in terms of CNOT gates.  It should be noted that the upper bound $4\leftarrowmbdaceil\leftarrowmbdaog_2 \muin\{d_A,d_B\}\rhoceil$ is not optimal for all dimensions: as mentioned previously, in the case of $d_A=d_B=2$, only $3$ CNOT gates together with local unitaries are needed, without using ancillas. We do not know whether this upper bound is optimal for general unitaries in other dimensions, and this is listed as an open question in the next section.

Somewhat surprisingly, Example~\rhoef{ex:u_6gates} in Sec.~\rhoef{sec:Schmidt} shows the following:
\betaegin{proposition}\leftarrowmbdaabel{pp:cu_inequality}
For any bipartite unitary $U$, $c(U)\gammae c(U\omegax I_G)$, where $G$ is one qubit on the $A$ side. There are examples of $U$ satisfying $c(U)>c(U\omegax I_G)$.
\epsilonnd{proposition}
\betaegin{proof}
The inequality is from observing that any decomposition of $U$ using controlled unitaries can be extended to a decomposition of $U\omegax I_G$ with the same number of controlled unitaries. If $c(U)=c(U\omegax I_G)$ always holds, we may repeatedly use it by adding one qubit on the $A$ side at a time, and get $c(U)=c(U\omegax I_{A'})$, where $A'$ has an integer number of qubits and is of size at least as big as $A$. Then the method in Example~\rhoef{ex:u_6gates} implies that $c(U\omegax I_{A'})\leftarrowmbdae 6$, thus $c(U)\leftarrowmbdae 6$, but this is generally impossible for a generic $U$ simply by parameter counting, see Sec.~\rhoef{sec:bipartite}. Therefore $c(U)=c(U\omegax I_G)$ does not always hold.
\epsilonnd{proof}

\sigmaection{Conclusions}

\leftarrowmbdaabel{sec:con}

We have proposed the sandwich and generalized sandwich forms for the decomposition of bipartite and multipartite unitary operators, respectively. In particular, we have shown that any bipartite unitary on $\muathbb{C}^{d_A}\omegax\muathbb{C}^{d_B}$ has a $(4d_A-5)$-sandwich form, and any $n$-partite unitary on $\muathbb{C}^{d_1}\omegax\chidots\omegax\muathbb{C}^{d_n}$ has a generalized $[2\pirod^{n-1}_{j=1}(2d_j-2)-1]$-sandwich form. The numbers can be further reduced in some special cases. In particular, three controlled unitaries can implement a bipartite complex permutation operator. This last result can be applied to classical reversible circuits. We mentioned some connections between our results and the results in the literature. As an application of the types of decompositions above, we discussed how to express a bipartite unitary as the product of a simple type of bipartite gates and some local unitaries. We also discussed the relationship between the Schmidt rank of the unitary (bipartite permutation unitary in particular) and the complexity of the decomposition, and also discussed the use of local ancillas. To conclude this paper we present a few open questions by requiring that the gates are exactly implemented, and no ancillary space or system is allowed unless stated otherwise.
\betaegin{enumerate}
\iotatem
Let $s(U)$ be the smallest number of controlled unitary gates required in a decomposition of $U$ of the sandwich form. Then $s(U)\gammae c(U)$. Do we have $s(U)=c(U)$? We suspect that this does not hold for some $U$. But does the similar equality $\muax_{U\iotan \chiT_{ab}} s(U)=\muax_{U\iotan \chiT_{ab}} c(U)$ hold, where $\chiT_{ab}$ is the set of all bipartite unitaries $U$ on an $a\thetaimes b$ dimensional space?
\iotatem
Can we obtain some form of decomposition of bipartite unitaries in terms of controlled unitaries, by taking a hint from the decomposition of single-party unitary matrices in \chiite[Corollary 1]{iw14} ? In particular, can we replace $4d_A-5$ by $2d_A-1$ in \epsilonqref{eq:upperbound}?
\iotatem
Let $U$ be a bipartite unitary on the $d_A\thetaimes d_B$ system. Do the following equations hold?
\betaegin{eqnarray}\leftarrowmbdaabel{eq:questions1}
&c(U)=c(U+\piroj{d_A+1}\omegax I_B),\nuotag\\
&c_s(U)=c_s(U+\piroj{d_A+1}\omegax I_B),\\
&c_e(U)=c_e(U+\piroj{d_A+1}\omegax I_B).\nuotag
\epsilonnd{eqnarray}
\iotatem
It is obvious that the following inequalities hold:
\betaegin{eqnarray}\leftarrowmbdaabel{eq:questions2}
c(U^{\omegax n})&\leftarrowmbdae& c(U),\nuotag\\
c_s(U^{\omegax n})&\leftarrowmbdae& n\chidot c_s(U),\\
c_e(U^{\omegax n})&\leftarrowmbdae& n\chidot c_e(U).\nuotag
\epsilonnd{eqnarray}
Here the bipartite unitary $U^{\omegax n}=U_{A_1B_1}\omegax\chidots\omegax U_{A_nB_n}$ acts on the space $\chiH_A\omegax\chiH_B$ where $\chiH_A=\betaigox^n_{i=1}\chiH_{A_i}$ and $\chiH_B=\betaigox^n_{i=1}\chiH_{B_i}$. But do the equalities always hold in the three inequalities above?
\iotatem
As discussed in Sec.~\rhoef{sec:elementary}, a bipartite permutation unitary can be implemented using a certain number of standard gates of the CNOT type and some local transposition gates. What is the minimum number of these gates needed to implement any bipartite permutation unitary on $d_A\thetaimes d_B$ space?  And since the local gates can be regarded as easy to implement, we can also ask the following: What is the minimum number of the first type of gates needed?
\iotatem
For $d_A$ or $d_B$ greater than 2, can an upper bound better than $4\leftarrowmbdaceil\leftarrowmbdaog_2 \muin\{d_A,d_B\}\rhoceil$ be found for the number of CNOT gates (or the bipartite elementary gates defined in Definition~\rhoef{def:ele2}) needed to decompose a bipartite unitary with the help of local ancillas and local unitaries?
\sigmamallskip
\iotatem
Is there a dimension-independent upper bound of $c(U)$ in terms of the Schmidt rank $r$ of a general bipartite unitary $U$? It is known that $c(U)=1$ when $r=2$ or $3$ \chiite{cy13,cy14ap}. See also the discussions in Sec.~\rhoef{sec:Schmidt}, and Theorem~\rhoef{thm:u_permutation} (which is for the permutation unitaries only and requires ancillas of fixed size).
\sigmamallskip
\iotatem
For given integers $m$, $n$ satisfying $m>n\gammae 2$, is there a dimension-independent upper bound (as a function of $m,n$ only) of the number of Schmidt-rank-$n$ bipartite unitaries needed to decompose any Schmidt-rank-$m$ bipartite unitary on the same space?
What about restricting the target unitary to be a controlled unitary in this question?

\epsilonnd{enumerate}

\sigmamallskip
\sigmaection*{Acknowledgments}

We thank Joseph Fitzsimons and Kae Nemoto for helpful discussions.  We also thank Scott Cohen for careful reading of an early version of the paper and pointing out a couple of issues in the presentation. This material is based on research funded in part by the Singapore National Research Foundation under NRF Grant No. NRF-NRFF2013-01, and in part by NICT-A (Japan).

\betaibliographystyle{unsrt}

\betaibliography{channelcontrol}

\epsilonnd{document}