Abstract
We show that any unitary operator on the $d_A\times d_B$ system ($d_A\ge 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 $\mathbb{C}^{d_1}\otimes\cdots\otimes\mathbb{C}^{d_n}$ is the product of at most $[2\prod^{n-1}_{j=1}(2d_j-2)-1]$ controlled unitary gates, each of which is controlled from $n-1$ systems. The number can be further reduced for $n=4$. The decomposition using not many controlled unitaries is suitable for optical implementation. We also decompose any bipartite unitary into the product of a simple type of bipartite gates and some local unitaries. We give a dimension-independent upper bound for the CNOT-gate cost or entanglement cost of bipartite permutation unitaries in terms of a function of the Schmidt rank of the unitary, and we find that the problem of improving the bound is related to the log-rank conjecture in communication complexity theory via the link of nonnegative rank.

This publication has 17 references indexed in Scilit: