# Approximation of an unitary operator by simple operators

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.

• What is your precise notion of "simple operator" and how do you define the "accuracy" of the approximation? Commented Aug 21, 2015 at 16:35
• For me, 'simple' means the operator will not work on more than 2 qubits just as the universal gates of quantum circuit model. 'Accuracy' means the distance between the target operator $U$ and the approximated version of it $U'$ is small enough w.r.t. matrix norm. Here I am not interested in an approximation, but a perfect decomposition, i.e., I want $U=U'=U_{1} U_{2}....U_{k}$, where $U_{i}$ is simple and $k~O(e^{n})$ for $U(2^n)$. I hope this can make my problem clear.
– XXDD
Commented Aug 21, 2015 at 16:41
• Since the tensor product enlarges the space an operator acts on, I don't understand the question - for an $n$-qubit space, only the tensor product of exactly $n/2$ 2-qubit operator (all on different qubits) will give an operator on $n$-qubit space. I suppose you are seeking for a different decomposition than that into the tensor product of "at most $\mathrm{e}^n$ simply operators". Commented Aug 21, 2015 at 16:44
• Sorry I made a mistake. I mean every simple operator looks like $U_{i}=I \otimes I \otimes...\otimes O_{i1,i2} ...\otimes I$, where $I$ is the identical operator on a single qubit and $O_{i1,i2}$ is a two-level operator on qubit $i1,i2$. So each operator $U_i$ is simple, or local, and the target operator $U$ can be regarded as a successive implementation of all the $U_i$s. Thanks.
– XXDD
Commented Aug 21, 2015 at 16:50
• Ah, that makes more sense! I don't know the answer, but you should edit this clarification into your question to make it more accessible! Commented Aug 21, 2015 at 16:53

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.
• Wow: that's a staggering and unexpected complexity ($O(n^34^n)$) given the $O(n^2)$ complexity of the $R Z B^2$ algorithm. Commented May 31, 2016 at 0:17
• @WetSavannaAnimalakaRodVance ??? RZB$^2$?? Commented May 31, 2016 at 8:14
• Sorry if that was a little obtuse: $RZB^2$ is Reck, Zeilinger, Bernstein, Bertani - the Reck et al algorithm you referenced. Commented May 31, 2016 at 9:23