Decomposition of an unitary operator by simple operators

Question

For quantum computation, it's well known that any unitary operator can be approximated with an arbitrary accuracy by simple operators, for example to approximate an unitary operator on n qubits by no more than $e^n$ universal gates.

What's puzzling me is that: Can we decompose an unitary operator into no more than $e^n$ (or with a similar complexity) simple unitary operators, i.e., as a tensor product of simple unitary operators? Here I am not talking about 'approximation' but a precise 'decomposition'. Also the simple operators need not to be from a finite set as in the universal gate case, we can use any simple operators (for example any 2-level unitary operator).

So I want to have $U=U_1U_2....U_k$, where $U_{i}=I\otimes I \otimes I ...\otimes O_{i1,i2}..\otimes I$. $I$ is the identical operator on a single qubit and $O_{i1,i2}$ is an arbitrary two-level operator on qubit $i1,i2$. Can such kind of decomposition possible? What's the complexity of it, i.e., $k \sim O(e^n)$? Thanks a lot.

Answer 1

Yes, such a kind of exact decomposition is always possible. This is shown in Barenco et al., Elementary gates for quantum computation (Sec. 8, pg. 27 in the arXiv preprint), based on work by Reck et al. (which gives a corresponding decomposition where each elementary operation is the identity except for a $2\times 2$ submatrix). The construction given requires $O(n^34^n)$ two-qubit gates.

(This is the same answer as to the cross-post https://physics.stackexchange.com/questions/201770).

Answer 2

The possibility of what you want to do would imply, at the very least, that every unitary operator on $k$ systems can be written as a "simple tensor", i.e. that we could write $U = U_1 \otimes \cdots \otimes U_k$ some unitary operators $U_1, \dots, U_k$.

This, however, is not the case. For example, consider $U \in \Bbb C^{2 \times 2} \otimes \Bbb C^{2 \times 2}$ to be defined by $$ U(e_i \otimes e_j) = e_j \otimes e_i $$ In particular, we have $$ U = \left[ \begin{array}{cc|cc} 1&0&0&0\\ 0&0&1&0\\ \hline 0&1&0&0\\ 0&0&0&1 \end{array} \right] $$ Note that there are no unitary matrices $U_1,U_2$ such that $U = U_1 \otimes U_2$, since the blocks are not all multiples of the same $2 \times 2$ matrix.