  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 "PauliComposer" which has an exponentially
growing memory overhead, achieving speedups in the range of 1.5x to 5x for N <
8. Note that our scheme does not leverage sparsity, diagonality, Hermitivity or
other properties of the input matrix which might otherwise enable optimised
treatment in other methods. As such, our algorithm is well-suited to
decomposition of dense, arbitrary, complex matrices which are expected dense in
the Pauli basis, or for which the decomposed Pauli tensors are a priori
unknown.
