# Simultaneous measurements and Bell basis measurements to estimate $\lvert\text{Tr}(\sigma \rho)\rvert^2$ in Huang et al. paper

Theorem 2 of this paper says if one is able to prepare $$\rho^{\otimes k}$$ then it is possible to predict expectation values of all $$n$$-qubit Pauli observables using $$O(n)$$ number of copies of $$\rho$$. It then gives an explicit procedure in Appendix E2, which is composed of two parts: (1) Estimating $$\lvert\text{Tr}(\sigma \rho)\rvert^2$$ and (2) Estimating a sign of $$\lvert\text{Tr}(\sigma \rho)\rvert$$. The paper mentioned that main idea to achieve (1) is to use the fact that $$\sigma \otimes \sigma$$ for any Pauli operator $$\sigma$$ commutes so that one can simultaneously measure them using Bell basis measurements. In Appendix E2 Eq. (E8) shows how to estimate $$\lvert\text{Tr}(\sigma \rho)\rvert^2$$ using the Bell measurement as follows:

1. Perform the Bell measurement on $$\rho \otimes \rho$$; the outcome will be one of the Bell pairs.

2. Every Bell pair is an $$\pm1$$ eigenstate of any single qubit Pauli operator $$\sigma \in \{I,X,Y,Z\}$$, where probability of getting $$\pm1$$ is $$\frac{1}{2}\text{Tr}((I\otimes I \pm \sigma \otimes \sigma)(\rho \otimes \rho))$$. Hence, we have $$\mathbb{E}[\text{Tr}((\sigma \otimes \sigma)S] = Prob(+) - Prob(-) = \lvert \text{Tr}(\sigma \rho)\rvert^2$$ (Eq.(E8)).

3. So, as far as I understand, to obtain $$\lvert\text{Tr}(\sigma \rho)\rvert^2$$, we can perform Bell measurements on many copies of $$\rho \otimes \rho$$, gather results of the outcomes $$S_k$$, and classically calculate the above expectation value.

Then the paper generalized this method to $$n$$-qubit system and proved that only $$O(n)$$ copies of $$\rho \otimes \rho$$ are required in order to estimate $$\lvert\text{Tr}(\sigma \rho)\rvert^2$$ for all $$n$$-qubit Pauli operators $$\sigma$$.

My question is: I understand the protocol but I couldn't immediately see how this procedure is related to the notion of "simultaneous measurement"? Does anyone catch this point?

• if I understand correctly, you want to estimate $\operatorname{tr}(\sigma_i\rho)^2$ with $\sigma_i$ some Pauli matrix, but you want to do it "directly" from measurements of $\rho\otimes\rho$ rather than by estimating $\operatorname{tr}(\sigma_i\rho)$ and square it in post-processing? If so, I think by "simultaneous measurement" they just mean that you're using as input two copies of the same state, and measure the associated output. Think a circuit where two of the inputs are $\rho$
– glS
Commented Jan 23, 2023 at 20:24

Here, "simultaneous measurement" of an observable does not refer to simultaneously in time, but rather the ability to estimate several observables from the same measurement setting acting on $$\rho\otimes \rho$$ (and therefore using only a single copy of $$\rho \otimes \rho$$). Basically, you may estimate both $$|\text{Tr}(\rho P_i)|$$ and $$|\text{Tr}(\rho P_j)|$$ for $$P_i \neq P_j$$ using $$O(1)$$ copies$$^1$$ of $$\rho \otimes \rho$$. However, because estimation involves statistical fluctuations, you can't naively scale this up for an arbitrary number of Pauli observables.

It may make more sense to think of the protocol like this: The paper says you can attempt to estimate $$\lvert\text{Tr}(P \rho)\rvert^2$$ within $$\epsilon$$ error for all $$n$$-qubit Pauli operators $$P$$ using just $$O(1)$$ copies of $$\rho \otimes \rho$$ - instead of , say, $$O(n)$$. But if you do this, there is a decent chance that a few of your estimates are off by more than $$\epsilon$$. So you scale up the number of measurements for each observable by $$\log (4^n)$$ to guarantee that all observables are estimated to $$\epsilon$$ accuracy with high enough probability, recovering the $$O(n)$$ scaling. This is the meaning of the discussion about the "union bound" in Appendix E.2.c.

#### Example of simultaneous measurement with Bell basis

For completeness, I will show how a single Bell measurement configuration may be used on $$\rho \otimes \rho$$ to estimate $$|\text{Tr}(\rho P_i)|$$ "simultaneously". Define the Bell state $$$$|\Phi_{00}\rangle := (|00\rangle + |11\rangle)/\sqrt{2}, \tag{1}$$$$ and then define the rest of a Bell basis according to $$$$|\Phi_{ij}\rangle := (Z^i \otimes X^j)|\Phi_{00}\rangle. \tag{2}$$$$ Measuring $$\rho\otimes \rho$$ in the Bell basis means using a PVM $$\{|\Phi_{ij}\rangle \langle \Phi_{ij}|\, \forall \, i,j\in\{0,1\}\}$$, and observing outcome $$(i,j)$$ with probability $$p_{ij} =\langle \Phi_{ij} |(\rho\otimes \rho)|\Phi_{ij}\rangle$$. We repeat this many times (see footnote 1) to produce an estimate $$\hat{p}_{ij}$$ for the probability distribution $$p_{ij}$$.

Now that we have a way to estimate $$p_{ij}$$, we would like to express each $$|\text{tr}(\rho P_j)|$$ in terms of these probabilities. Since the Pauli operators form a orthonormal basis for Hermitian matrices, we decompose $$\rho \otimes \rho$$ as \begin{align} \rho \otimes \rho &= \sum_{ij} \text{Tr}\left[(\rho \otimes \rho)(P_i \otimes P_j)\right](P_i \otimes P_j) \tag{3} \\&:= \sum_{i}c_{ii}^2 (P_i \otimes P_i) + \sum_{i\neq j} c_{ij}(P_i \otimes P_j), \tag{4} \end{align} where we identify $$c_{ii}^2 = |\text{Tr}(\rho P_i)|^2$$ as the quantities we're looking for. Since $$n=1$$, we can compute by hand the probability of observing each outcome $$(i,j)$$. A useful identity will be \begin{align} |\Phi_{00}\rangle \langle \Phi_{00}| = \frac{1}{4} (I\otimes I + X\otimes X - Y\otimes Y + Z\otimes Z). \tag{5} \end{align} Then, compute: \begin{align} p_{00} &= \text{Tr}\left( |\Phi_{00}\rangle\langle \Phi_{00} | \rho \otimes \rho \right) \tag{6a-c} \\&=\frac{1}{4} \text{Tr}\left[\left( I\otimes I + X\otimes X - Y\otimes Y + Z\otimes Z \right) \left(\sum_{i}c_{ii}^2 (P_i \otimes P_i) + \sum_{i\neq j} c_{ij}(P_i \otimes P_j) \right)\right] \\&= \frac{1}{4} \left(c_{00}^2 + c_{11}^2 - c_{22}^2 + c_{33}^2\right) . \end{align} Similarly, using Eq. (2) and some Pauli conjugation identities, one finds \begin{align} p_{01} &= \text{Tr}\left( (I\otimes X)|\Phi_{00}\rangle\langle \Phi_{00} | (I \otimes X)\rho \otimes \rho \right) \tag{7} \\&= \frac{1}{4}\left(c_{00}^2 + c_{11}^2 + c_{22}^2 - c_{33}^2\right) \tag{8}\\ p_{10} &= \text{Tr}\left( (Z\otimes I)|\Phi_{00}\rangle\langle \Phi_{00} | (Z \otimes I)\rho \otimes \rho \right) \tag{9} \\&= \frac{1}{4}\left(c_{00}^2 - c_{11}^2 + c_{22}^2 + c_{33}^2\right) \tag{12} \\p_{11} &= \text{Tr}\left( (Z\otimes X)|\Phi_{00}\rangle\langle \Phi_{00} | (Z \otimes X)\rho \otimes \rho \right) \tag{10} \\&= \frac{1}{4}\left(c_{00}^2 - c_{11}^2 - c_{22}^2 - c_{33}^2\right) \tag{11}. \end{align} Rearrange these equations to solve for the desired expectation values in terms of $$p_{ij}$$: \begin{align} c_{00}^2 = |\text{Tr}(\rho I)|^2 &= p_{00} + p_{01} + p_{10} + p_{11} = 1 \tag{12}\\ c_{11}^2 = |\text{Tr}(\rho X)|^2 &= p_{00} + p_{01} - p_{10} - p_{11}\tag{13}\\ c_{22}^2 = |\text{Tr}(\rho Y)|^2 &= -p_{00} + p_{01} + p_{10} - p_{11}\tag{14}\\ c_{33}^2 = |\text{Tr}(\rho Z)|^2 &= p_{00} - p_{01} + p_{10} - p_{11} \tag{15}\\ \end{align} Then, just define estimates for the expectation values $$|\text{Tr}(\rho P_i)|:=\hat{c}_{ii}$$ that are computed from $$\hat{p}_{ij}$$ in an analogous manner to the above system. Thus, for $$n=1$$ we see how using the estimated probability distribution $$\{\hat{p}_{ij}\}$$ output by a single measurement setting in the Bell basis , we may output estimates for all $$|\text{Tr}(\rho P_i)|$$.

$$^1$$ Here the $$O(1)$$ includes repeating the measurement to get an estimate of the average and hides terms in $$\epsilon$$ and $$\delta$$ that control the accuracy of this estimate.

I am not sure what you mean with Bell measurement (haven't read the paper in detail).

Maybe this demo can help understand the concept of simultaneous measurement in the Pauli basis. This is a general concept and not specific to classical shadows.

Imagine you want to estimate the expectation values of observables $$[X_0, X_0 Y_1, X_0 Y_1 Z_2]$$ on a quantum computer. You don't need to run three programs executing these expectation values, but rather can re-use the samples you obtained from the last to determine the first two.

More generally, you can sort a large list of observables that you might want to estimate into qubit-wise-commuting groups (fancy way of saying groups with the same non-trivial Pauli operators on each site - and different from commuting as $$X_0 X_1$$ and $$Y_0 Y_1$$ commute but are not qubit-wise-commuting). You can always estimate all of the observables in one group simultaneously (just as we did in the example above).

(Vanilla) classical shadows are doing something similar, but instead of grouping anything they just draw random samples, and then when asked to estimate observables, the sub-pool of samples that match the Pauli word that you are trying to estimate are used. There is no advantage in doing that by the way, this is explained in the demo I linked.

This is only useful if you didn't know which observables you are going to estimate before making the measurement. If you know it a priori you are at best not wasting resources. There are more clever ways of doing this now though (e.g. "derandomized" classical shadow procedure, which is something like a probabilistic way of sampling those operators of the biggest qubit-wise-commuting groups more).