Non-unitary matrix decomposition as a sum of unitary matrices

Question

Several quantum algorithms that deals with linear algebra and matrices that are not necessarily unitary circumvent the problem of non-unitary matrices by requiring a decomposition of the non-unitary matrix as a sum of unitary matrices. A widely known example being the LCU method.

I am currently facing the problem of "how should I decompose my non-unitary matrix?". I want to decompose as a sum of unitary matrices (in the best world ever, easy to implement unitary matrices) the following matrix:

$$ A = \begin{pmatrix} 0 & \cdots{} & \cdots{} & \cdots{} & \cdots{} & 0 \\ \vdots{} & & & & & \vdots{}\\ \vdots{} & & & & & \vdots{}\\ 0 & & & & & \vdots{}\\ 1 & 0 & \cdots{} & \cdots{} & \cdots{} & 0 \\ \end{pmatrix} $$ which is obviously non-unitary.

I started by restricting myself to the Pauli matrices (+ identity) because I know that these unitary matrices are easy to implement. I found the following decomposition:

$$ A = \frac{1}{2^{n}} (\mathbb{X} - i \mathbb{Y})^{\otimes n}. $$ The problem with this decomposition is that it is a sum of an exponential (with respect to the number of qubits) number of unitary matrices. From another perspective, there are as much unitary matrices in the decomposition as the size of $A$, so it is linear in the size of $A$. The methods mentioned at the beginning of this question are only efficient when the number of unitary matrices in the decomposition is poly-logarithmic, which is not the case here.

First question: is there any way to find a better decomposition (in terms of number of summed unitary matrices)? Or a proof that shows that it is not possible to do better only with the Pauli matrices?

I voluntarily took a very restricted and simple gate set. I started to think about how introducing a 2-qubit gate like CNOT would affect the decomposition. Obviously, it can only improve the number of unitary matrices summed in the decomposition, but I still cannot figure out if introducing other unitary matrices will help me to reduce the number of unitary matrices summed in the decomposition to something that is logarithmic in the size of $A$ (instead of the linear behaviour I have now).

Second question: do you have any ideas about how modifying the gate set will affect the number of summed unitary matrices in the decomposition?

Answer 1

All tensor products of $n$ Pauli operators $\{I,X,Y,Z\}$ (that is $4^n$ combinations) form an orthogonal basis for the vector space of $2^n \times 2^n$ complex matrices. Hence, for every matrix there is a unique decomposition as a linear combination of tensor products of Pauli unitaries. Same is true if we fix some other unitary basis.

If we not fix the unitary basis, then there are a lot of other options, of course. For example, your matrix $A$ is a linear combination of 2 unitaries: $$ A = \frac{1}{2}\begin{pmatrix} 0 & 0 & 0 & \cdots{} & 1 \\ 0 & 1 & 0 & & \vdots{}\\ 0 & 0 & \ddots & & \vdots{}\\ \vdots{} & & & 1 & 0\\ 1 & \cdots & \cdots{}& 0 & 0 \\ \end{pmatrix} + \frac{1}{2}\begin{pmatrix} 0 & 0 & 0 & \cdots{} & -1 \\ 0 & -1 & 0 & & \vdots{}\\ 0 & 0 & \ddots & & \vdots{}\\ \vdots{} & & & -1 & 0\\ 1 & \cdots & \cdots{}& 0 & 0 \\ \end{pmatrix} $$