Can we write a sum of unitary gates as an equivalent product of unitary gates?

Question

If I did it correctly, in an answer to a question about Bell's states preparation, I found true that:

$$CNOT \space \space (H \otimes I) \space CNOT = ( X \otimes X + Z \otimes I ) \frac{1}{\sqrt{2}}$$

I ask if this is possible in general, i.e. if it's always possible write a sum of unitary gates (normalized with suitable coefficients) as an equivalent product of unitary gates, or if not to what extent this is possible anyway, for instance using non-unitary too.

I'm reading the book Quantum Computer Science and I feel stuck when the author introduces a new unitary gate giving an algebraic definition that is based on the sum of other unitary gates (or not unitary matrices), but then in an actual quantum circuit I'm not allowed to sum gates together. I have to improve my linear algebra skills to tackle questions like this.

Answer 1

Actually, any matrice can be expressed into a sum of Pauli operators. That's because the Pauli matrices are a set of complete bases. For example,

\begin{equation} \begin{bmatrix} a & b \\ c & d \end{bmatrix} = a\frac{I+Z}{2}+d\frac{I-Z}{2}+b\frac{X+iY}{2}+c\frac{X-iY}{2} \end{equation} as \begin{equation} \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix} = \frac{I+Z}{2}, \begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix} = \frac{I-Z}{2}, \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix} = \frac{X+iY}{2}, \begin{bmatrix} 0 & 0 \\ 1 & 0 \end{bmatrix} = \frac{X-iY}{2}. \end{equation}

Therefore, generally, a sum of Pauli operators is not unitary, and cannot be decomposed into a product of elementary unitary gates.

Answer 2

If the sum of unitaries is itself a unitary, then yes, you can always rewrite it as a product of unitaries. This is essentially the content of the concept of universality that says any unitary matrix can be decomposed as a product of elementary gates. Of course, that says nothing about how short/long a sequence of gates it is, or how easy it is to find. For an arbitrary unitary, it's a hard problem.

On the other hand, if you have an arbitrary sum of unitaries, then no, because an arbitrary sum need not be unitary while a product of unitaries can only ever give you a unitary.

For your more general question: an arbitrary sum of unitaries will be some matrix. That matrix has a singular value decomposition $UWV$ where $U$ and $V$ are unitary and $W$ is diagonal. The $U$ and $V$ can always be expressed as a product of unitaries, so the only addition you need is the possibly non-unitary diagonal gate $W$ (whose diagonal elements are the singular values of your target matrix).