Local decomposition of unitary matrices

[chiyosdad]

I know that, given an arbitrary unitary matrix A, it can be written as the product of several "local" unitary matrices Ai -- local in the sense that they only act on a small constant number of vector components, in fact it is sufficient to take 2 as that constant, which is best possible. For example,
$$A=\left(\begin{array}{cccc} a & 0 & b & 0 \\0 & 1 & 0 & 0 \\ <br /> c & 0 & d & 0\\ 0 & 0 & 0 & 1\end{array}\right)$$
is such a local matrix, because it only acts on the basis element e1 and e3. Another way to think of it is that it's only nontrivial over a subspace of dimension 2.

So the picture is that there are these gigantic linear transformations on C^n(n is very large), being built out of smaller transforms which act on small constant-dimension subspaces. So as n grows, the number of local Ai's needed will grow too. I have an upper bound on the number of Ai needed in the decomposition, in terms of n. But that's not what I'm interested in. What I would like to know, is what is the least number of Ai's needed to decompose a specific matrix, or a class of matrices. I know of no machinery that makes this easy, and looking around online for a bit didn't help.

So the question is, if I have a specific unitary matrix, how do I go about calculating the minimum number of Ais needed in the decomposition, and if I have a class of matrices, how do I figure it out. Is there some reading on this subject I can find online?

 

[fresh_42]

To prove lower bounds is generically difficult. You mentioned a specific matrix, which means this could be done more easily depending on the properties of this matrix. E.g. it could just be $1$. In the general case one needs to find a subsystems of values which have to be calculated regardless of these properties and count the steps for those calculations. The bigger this subsystem, the better the lower bound. However, it is not clear what such a subsystem must look like.