A tree-approach Pauli decomposition algorithm with application to quantum computing

Understand

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.