# Efficient way to calculate trace of product of Pauli string and matrix?

Basically the title, but more formally: is there a way to efficiently calculate the trace of the product of a Pauli string $$P$$ and a $$2^n \times 2^n$$ matrix $$M$$? That is, is there a way to calculate in polynomial time (or better) the quantity $$\text{Tr}{(PM)},$$ where $$P$$ is an $$n$$-qubit Pauli string and $$M$$ is an arbitrary matrix of dimension $$2^n \times 2^n$$. Assume we have query access to the matrix $$M$$ in the computational basis. That is, we can ask for any row and our query access model returns the values of all nonzero entries and the column indices (or equivalently we can query the column). Recall, an $$n$$-qubit Pauli string is a tensor product of Pauli matrices: $$P = \sigma^{(1)}_i \otimes...\otimes \sigma^{(n)}_i,$$ where $$\sigma^{(j)}_i$$ is a Pauli matrix that acts on qubit $$j$$ and $$i \in \{1, 2, 3, 4\}$$ for the four Pauli matrices.

I am interested in this general case for an arbitrary matrix $$M$$, but I am also interested in a specific instance of the problem where we have some information on the structure of $$M$$, namely that

1. $$M$$ is promised to be the sum of $$k$$ distinct Pauli strings (assume the coefficients on the terms are 1 for now)
2. $$P$$ may or may not be one of the Pauli strings; if it isn't, the trace should come out to 0

Thus, the goal is essentially to find out which Pauli strings are in the sum comprising $$M$$. This is akin to the process of decomposing a matrix into the Pauli basis by calculating all $$4^n$$ possible coefficients, but through some pre-processing, we are assuming that we have reduced the number of possible Pauli strings to $$k^2$$ and we are trying to find out which $$k$$ of these $$k^2$$ terms have non-zero coefficients.

• Sure, I edited it to reflect that we have query access in the computational basis and what this means. And yes, the bound on the number of nonzero entries is $k$ since the sum of $k$ Pauli matrices, each of which is 1-sparse, will be $k$-sparse. For now, let's assume that $k$ is a constant, $k = O(1)$. At some point I would expand it to $k = \text{poly}(n)$ but I am assuming constant for now. Sep 25, 2023 at 20:49
• Sounds like there should be some smart way to do it, if k is sufficiently small. Is there a specific motivation? Sep 25, 2023 at 20:56
• The motivation is to decompose an arbitrary matrix (say, of dense classical data) into the Pauli basis, but I am starting with this promise problem to see if I can find a way to do this in sub-exponential time. I am assuming that the dense case is still going to be exponential, but if I can get it to be "less" exponential than the naïve algorithm, that'd be a minor success. By "naïve" I mean by finding all $4^n$ coefficients as $\alpha_i = \text{Tr}{(P_iM)}$, which has to be done for all possible Pauli strings. Obviously this does not scale well in $n$. Sep 25, 2023 at 21:00
• A start would be to consider only I and Z, and then only I and X, and then two Paulis. If you can't get it to work there, there's little chances for the general scheme. Sep 25, 2023 at 21:01
• I suppose if you were to look along a single row (0000..0 is easiest), the non-zero elements tell you quite a lot about the involved Pauli strings: if $x$ is the bit string representing the position, then everywhere $x_i=0$ is either $I$ or $Z$, while everywhere $x_i=1$ is either $X$ or $Y$. Resolving which might be harder. Is it enough to compare the coefficients $n$ (linearly independent) rows? Sep 26, 2023 at 8:04

Any Pauli string has exactly one non-zero element in each row and column. Moreover, if you switch between $$I$$ and $$Z$$, and between $$X$$ and $$Y$$ in a Pauli string then the pattern of zeros will be the same. I'll call it a type of a Pauli string. Also note that non-zero elements patterns never intersect for different Pauli string types.

The position of non-zero element tells you what type a Pauli string has. For example, in $$I\otimes X \otimes X \otimes I \otimes I$$ the 0-based index of the unique non-zero element in the first column is $$(01100)_2$$. The Pauli string $$Z\otimes Y \otimes X \otimes I \otimes Z$$ has the same pattern of zeros.

So, by looking at indices (in binary notation) of non-zero elements in the first column of $$M$$ you immediately know what types of Pauli strings are in the decomposition of $$M$$. And you immediately know how matrix $$M$$ decomposes into a sum $$\sum_t M_t$$, where $$M_t$$ is a weighted sum of Pauli strings of the same type $$t$$.

Thus, the problem reduces to finding a decomposition of $$M_t$$ into an exact weighted sum of Pauli strings of type $$t$$.

There are $$2^n$$ Pauli strings in each type. And matrix $$M_t$$ has $$2^n$$ non-zero elements. In essence, we have a system of linear equations here. There is no way to solve it fast in general. But if we know that $$k$$ is small and coefficients are restricted, then we can try some specific methods, I guess. Though, it still looks like a knapsack problem.

One can try to solve it just for the type $$I\otimes I \otimes \dots \otimes I$$. In this case $$M_t$$ is a diagonal matrix and we have to find its decomposition into a weighted sum of $$Z^{b_1}\otimes Z^{b_2} \otimes \dots \otimes Z^{b_n}$$ where $$b_i$$ are bits.

Update

Actually, it might be solvable. I'll explain just for the case where $$M_t$$ is diagonal. Let's take first $$m$$ bits and group strings $$Z^{b_1}\otimes Z^{b_2} \otimes \dots \otimes Z^{b_{m}} \otimes Z^{c_{m+1}} \otimes \dots \otimes Z^{c_{n}}$$ together, where $$b_i$$ are fixed and $$c_j$$ vary (so there are $$2^m$$ groups).

A linear combination of matrices in a group is some matrix $$Z^{b_1}\otimes Z^{b_2} \otimes \dots \otimes Z^{b_{m}} \otimes D_{b_1\dots b_m}$$ where $$D_{b_1\dots b_m}$$ can be any diagonal matrix of size $$2^{n-m} \times 2^{n-m}$$. It's true for each group.

What we want to achieve is to decompose $$M_t$$ into "groups" at first. That is, to find decomposition $$M_t = \sum_{b_1\dots b_m} Z^{b_1}\otimes Z^{b_2} \otimes \dots \otimes Z^{b_{m}} \otimes D_{b_1\dots b_m},$$ for some $$D_{b_1\dots b_m}$$. Note that if $$k$$ is small ($$k<2^m$$), then some groups will not be present in the decomposition, i.e. $$D_{b_1\dots b_m}=0$$.

Now, consider the first element on the diagonal in $$D_{b_1\dots b_m}$$. In $$Z^{b_1}\otimes Z^{b_2} \otimes \dots \otimes Z^{b_{m}} \otimes D_{b_1\dots b_m}$$ it will appear on positions with indices $$x2^{n-m}$$, $$x=0,\dots,2^{m}-1$$, with some $$\pm$$ sign. Same is true for each combination $$b_1\dots b_m$$.

Thus, if we consider elements of $$M_t$$ on those positions $$x2^{n-m}$$, we get a system of linear equations for those $$2^m$$ first elements of $$D_{b_1\dots b_m}$$. Which we just solve. If in the solution the first element of $$D_{b_1\dots b_m}$$ is not zero, then some Pauli strings in $$M_t$$ decomposition must be in this group. If it's zero, then the group is either missing, or has at least two Pauli strings which are parts of $$M_t$$. This already gives us a lot of information.

To refine and compose it we can do the same for the second, third, and other elements of each $$D_{b_1\dots b_m}$$. Or try a different split of qubits into two parts. It seems we only need a small number of runs.