Is there an efficient algorithm for decomposing an arbitrary Hamiltonian into Pauli strings?

Question

Basically the title. If I have a $2^N\times 2^N$ Hamiltonian $H$ of random numbers (we can take the Hamiltonian as normalized if we want) and $N$ is an integer, is there an efficient way of writing $$ H = \sum_{i}{\beta_iP_i} $$ where $\beta_i \in \mathbb{C}$ and $P_i$ is a Pauli string and the sum ranges over all such possible tensor product combinations of the Pauli group, $\{I,X,Y,Z\}$. Apologies if my notation is non-standard; let me know if any clarification is needed.

Also, I say efficient because I am aware of such solutions as this and this, but these seem to become exponentially hard in $N$.

Answer 1

For example see the one proposed recently in https://arxiv.org/abs/2401.16378. In my tests, I could decompose random $N=11$-qubit Hamiltonian in about $ \sim 150$ minutes.

Answer 2

Your output size is $4^n$ numbers, so you're certainly not going to do better than $\Omega(4^n)$ complexity. At least, not without some sort of sparsity guarantee and some way to compute those big terms analogous to the sparse fast fourier transform.

Anyways, it turns out that you can get all $4^n$ numbers by interpreting your matrix as a vector and simulating applying the same quantum circuit you would apply to measure in the Bell basis. This takes $O(4^n)$ space and $O(n 4^n)$ time:

In more classical computing terms: take your matrix of coefficients, permute each column so that the entry at offset $j$ in column $k$ ends up at offset $j \oplus k$ in column $k$, then apply the classical Hadamard transform to each column (or maybe each row? I can never keep that straight). The matrix now contains the Pauli term coefficients.