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


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.

  • $\begingroup$ 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 $\endgroup$
    – Sam Palmer
    May 13, 2020 at 3:16
  • 1
    $\begingroup$ @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$. $\endgroup$
    – DaftWullie
    May 13, 2020 at 7:37
  • $\begingroup$ I gave the answer here 2 days ago:quantumcomputing.stackexchange.com/a/11924/2293 $\endgroup$ May 13, 2020 at 10:02
  • 1
    $\begingroup$ In which case you're always going to need $O(4^n)$ parameters $\endgroup$
    – DaftWullie
    May 13, 2020 at 14:23
  • 1
    $\begingroup$ Ahaha, which is $4^n$. $\endgroup$
    – mavzolej
    May 13, 2020 at 15:02

1 Answer 1


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

  • $\begingroup$ quantumcomputing.stackexchange.com/a/11924/2293 $\endgroup$ May 13, 2020 at 10:02
  • $\begingroup$ @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)$). $\endgroup$
    – mavzolej
    May 13, 2020 at 13:27
  • $\begingroup$ @DaftWullie, please see an update to my question. $\endgroup$
    – mavzolej
    May 13, 2020 at 13:43
  • 1
    $\begingroup$ I think that your general case would need an exponential number of elements to describe it anyway. If you know the elements to be on either of the diagonals you can cheat by limiting to only X&Y or I&Z Paulis (for anti- or normal diagonal). There are some other 'cheats' you might be able to use, but for the general case it would not be so easy I think $\endgroup$
    – JSdJ
    May 13, 2020 at 14:18

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.