# Expressing a term of an $n$-qubit Hamiltonian in terms of Pauli operators

Consider a $$2^n\times 2^n$$ Hermitian matrix $$M$$ containing up to two non-zero elements, which are $$1$$ (so, either $$M_{ii}=1$$ for some $$i$$, or $$M_{ij}=M_{ji} = 1$$ for some $$i$$ and $$j$$). Each such matrix can be expressed a linear combination of Pauli operators. For example: $$\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} = \frac{1}{2} (XX+YY) \ ,\quad \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} = \frac{1}{4} (1 - Z_1 + Z_2 -Z_1 Z_2) \ .$$

What would be the general expression for such an expansion, for an arbitrary $$n$$ and $$i,j=1\ldots2^n$$?

CLARIFICATION

I'm looking for a solution different from the one which involves taking trace with all the possible Pauli operators. The problem with that solution is that it requires $$O(4^n)$$ operations, since this is the total number of Paulis on $$n$$ qubits.

The motivation for my question, of course, comes from expanding an arbitrary Hermitian $$H$$ in terms of Pauli operators. The number of parameters in such a matrix is $$O(2^n)$$, which sets the lower bound on the solution complexity ⁠— which, I believe, is possible to achieve. One way to do this would be to decompose $$M$$ from my question in $$O(\operatorname{poly}(n))$$ steps. This would allow to expand $$H$$ in $$O(2^n)$$ instead of $$O(4^n)$$ steps, via expressing it in terms of Paulis entry by entry.

• i'm not sure how you're getting 4x4 matrices from products of 2x2 matrices, are you taking the tensor product? and even then in the second expansion you would have miss match of dimesions between $Z_1\otimes Z_2$ and Z_1 – Sam Palmer May 13 '20 at 3:16
• @SamPalmer In the first expression, he's using the tensor product ($X\otimes X+Y\otimes Y$). In the second, because of the subscript notation, multiplication is a reasonable option: $Z_1:=Z\otimes I$. – DaftWullie May 13 '20 at 7:37
• I gave the answer here 2 days ago:quantumcomputing.stackexchange.com/a/11924/2293 – user1271772 May 13 '20 at 10:02
• In which case you're always going to need $O(4^n)$ parameters – DaftWullie May 13 '20 at 14:23
• Ahaha, which is $4^n$. – mavzolej May 13 '20 at 15:02

There's a generalisation that one can make. Let $$x\in\{0,1,2,3\}^n$$ be a string of values. We can define an operator $$\sigma_x$$ to mean "do identity on any qubit $$i$$ where $$x_i=0$$, do $$X$$ on any qubit $$i$$ where $$x_i=1,\ldots$$". Then, because the Pauli matrices form a basis, we can write $$H=\sum_{x\in\{0,1,2,3\}^n}\alpha_x\sigma_x.$$ If $$H$$ is Hermitian (as it should be for a Hamiltonian) then $$\alpha_x$$ is real. If you have $$H$$ in matrix form then you can find the $$\alpha_x$$ via the computation $$\alpha_y=\frac{1}{2^n}\text{Tr}(H\sigma_y).$$
• @DaftWullie, this is indeed a solution. The problem is that if you try to implement it, you would have to do an exponential number of operations, since the total number of Pauli strings on $n$ qubits is $4^n$. I think it should be possible to decompose the matrix from my question in a smaller number of steps. However, I'd also be interested to know the answer for a general Hermitian matrix (I expect the answer to have complexity $O(2^n)$). – mavzolej May 13 '20 at 13:27