  The Pauli matrices are 2-by-2 matrices that are very useful in quantum
computing. They can be used as elementary gates in quantum circuits but also to
decompose any matrix of $\mathbb{C}^{2^n \times 2^n}$ as a linear combination
of tensor products of the Pauli matrices. However, the computational cost of
this decomposition is potentially very expensive since it can be exponential in
$n$. In this paper, we propose an algorithm with a parallel implementation that
optimizes this decomposition using a tree approach to avoid redundancy in the
computation while using a limited memory footprint. We also explain how some
particular matrix structures can be exploited to reduce the number of
operations. We provide numerical experiments to evaluate the sequential and
parallel performance of our decomposition algorithm and we illustrate how this
algorithm can be applied to encode matrices in a quantum memory.
