Algorithm to decompose a sparse unitary matrix into a Kronecker product of smaller unitary matricies

Question

Given some sparse unitary square matrix $A$ ($dim=2^n$ if it matters), is there an algorithm to decompose $A$ into a Kronecker/tensor product of smaller unitary matrices? In other words: decompose unitary $A$ into $$A=U_1 \otimes U_2 \otimes ... \otimes U_k$$ where each $U_i$ is individually unitary and $\otimes$ denotes the Kronecker product.

I know that in general, the inverse of a Kronecker product is not unique and may not even exist, but if it does, all I would care about is a single tensor decomposition, not an exhaustive list. It wouldn't matter to me what the individual phases are for example.

Edit: I assumed the matrix was a Kronecker product, but in the case that it isn't, is there a way to check?

Edit 2: I found a resource here describing a general outline on how to do the inverse Kronecker product and how to check if it is a Kronecker product in the first place. It looks like the problem can be solved in polynomial time. If however, I demand unitary matrices, is there a similar scheme?

Answer 1

After some thought, I realized the condition of being unitary is essentially irrelevant to the problem. This is because of the mixed-product and inverse identities of the Kronecker product. So given a unitary $A$, we have: $$A^{-1}=A^{\dagger} \implies U_1^{-1}\otimes...\otimes U_k^{-1}=U_1^{\dagger}\otimes...\otimes U_k^{\dagger}$$

$$AA^{\dagger}=AA^{-1}=I=U_1 U_1^{\dagger} \otimes ... \otimes U_k U_k^{\dagger}$$ Where $I$ is the identity matrix.

This last line implies that each individual $U_j U_j^{\dagger}=aI$ for some complex $a$. To make $U_j$ unitary is then just a matter of scaling by a constant.

This means that the inverse Kronecker product for a unitary matrix is automatically unitary up to a constant scaling factor. So to perform this inverse product, one just needs to follow the solution outlined by karahane in the math stackexchange here. A possible followup question would be whether one can get a piece-by-piece unitary nearest Kronecker product approximation. To be self-contained, the academic references for the solution are given below:

Golub G, Van Loan C. Matrix Computations, The John Hopkins University Pres. 1996

Van Loan C., Pitsianis N., Approximation with Kronecker Products, Cornell University, Ithaca, NY, 1992

Genton MG. Separable approximations of space–time covariance matrices. Environmetrics 2007; 18:681–695.