Decomposition of bipartite and multipartite unitary gates into the product of controlled unitary gates

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 ...\otimes {\mathbb{C}}^{d_n}$ is the product of at most $[2{\prod }_{j=1}^{n-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$. 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.

References in corpus (4)

• Synthesis of Quantum Logic Circuits
• Efficient Toffoli Gates Using Qudits
• All unitaries having operator Schmidt rank 2 are controlled unitaries
• On the Schmidt-rank-three bipartite and multipartite unitary operator

Cited by in corpus (6)

• Trade-off relation among genuine three-qubit nonlocalities in four-qubit systems
• Classification of Schmidt-rank-two multipartite unitary gates by singular number
• Constructing three-qubit unitary gates in terms of Schmidt rank and CNOT gates
• The detection power of real entanglement witnesses under local unitary equivalence
• Synthesis and upper bound of Schmidt rank of the bipartite controlled-unitary gates
• Mutually unbiased bases containing a complex Hadamard matrix of Schmidt rank three