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$.

  • $\begingroup$ Certainly, this seems impossible unless there is some additional structure imposed on $H$. Asking for $H$ in the Pauli string basis, given an $H$ in the standard basis requires matrix multiplication, which is why you will always be polynomial in the dimension of the matrix (i.e. exponential in $N$). $\endgroup$
    – Condo
    Oct 3, 2022 at 19:28
  • $\begingroup$ @Condo While it is true that it is exponentially hard -- just specifying H already requires an exponential number of parameters, it does not require matrix multiplication (at least not in the sense of multiplying two $2^N\times 2^N$ matrices). $\endgroup$ Oct 3, 2022 at 22:03
  • $\begingroup$ The most efficient way (if $H$ is just a full matrix) is to vectorize $H$ (which makes it a $4^N$-component vector) and then apply a basis transformation to the Pauli basis on each of the $4$-dimensional blocks; this can be achieved as a sequence of multiplication of a $4\times 4^{N-1}$ matrix with a $4\times 4$ matrix. $\endgroup$ Oct 3, 2022 at 22:04
  • $\begingroup$ @NorbertSchuch Ah yes, I completely mistyped what I meant. What I was trying to say was that the change of basis transformation requires matrix multiplication. $\endgroup$
    – Condo
    Oct 5, 2022 at 20:51


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.