Decomposing dense matrices into dense Pauli tensors

Understand

Decomposing a matrix into a weighted sum of Pauli strings is a common chore of the quantum computer scientist, whom is not easily discouraged by exponential scaling.

• But beware, a naive decomposition can be cubically more expensive than necessary! In this manuscript, we derive a fixed-memory, branchless algorithm to compute the inner product between a 2^N-by-2^N complex matrix and an N-term Pauli tensor in O(2^N) time, by leveraging the Gray code.
• Our scheme permits the embarrassingly parallel decomposition of a matrix into a weighted sum of Pauli strings in O(8^N) time.
• We implement our algorithm in Python, hosted open-source on Github, and benchmark against a recent state-of-the-art method called the &#34;PauliComposer&#34; which has an exponentially growing memory overhead, achieving speedups in the range of 1.5x to 5x for N < 8.