Timeline for Efficient way to calculate trace of product of Pauli string and matrix?
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 20 at 18:10 | comment | added | Nichola | some Pauli strings based package would be useful eg : paulistrings.org/dev | |
| May 6 at 19:14 | answer | added | Nichola | timeline score: 0 | |
| Sep 26, 2023 at 18:05 | answer | added | Danylo Y | timeline score: 1 | |
| Sep 26, 2023 at 18:01 | comment | added | Physics Penguin | @DaftWullie yeah, I am using something like that to get the possible $x$ bit strings and, querying in the same way in the Hadamard basis (assuming we have access to it, which is a big assumption, but it'll do for now) gives us the $z$ bit strings. This works for when $M$ is equal to one Pauli string, but if it is a sum of different Pauli strings, then we get a bunch of $x$ and $z$ bit strings that I don't know how to match up appropriately. That's why I've resorted to just calculating the coefficient of each and finding which are nonzero. | |
| Sep 26, 2023 at 8:04 | comment | added | DaftWullie | 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 25, 2023 at 21:01 | comment | added | Norbert Schuch | 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:00 | comment | added | Physics Penguin | 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 20:56 | comment | added | Norbert Schuch | 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:51 | history | edited | Physics Penguin | CC BY-SA 4.0 |
added 27 characters in body
|
| Sep 25, 2023 at 20:49 | history | edited | Physics Penguin | CC BY-SA 4.0 |
added 27 characters in body
|
| Sep 25, 2023 at 20:49 | comment | added | Physics Penguin | 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:47 | history | edited | Physics Penguin | CC BY-SA 4.0 |
added 47 characters in body
|
| Sep 25, 2023 at 19:44 | history | asked | Physics Penguin | CC BY-SA 4.0 |