# Relating upper bound on the total variation distance with a bound on a Pauli observable

Consider an $$n$$ qubit state $$|\psi\rangle$$. Let us say we have the following upper bound on the total variation distance between the distribution generated by measuring $$|\psi\rangle$$ in the standard basis and the uniform distribution.

$$\sum_{x \in \{0, 1\}^{n}} \left||\langle x | \psi \rangle|^{2} - \frac{1}{2^{n}} \right| \leq a,$$

$$\left||\langle x | \psi \rangle|^{2} - \frac{1}{2^{n}} \right| \leq \frac{a}{2^{n}},$$

for every $$x$$.

Now, let us consider a Pauli observable $$O$$ as follows:

$$O = \sum_{\sigma_i\in\{I, X, Y, Z\}^{\otimes n}} w_{\sigma_i} \sigma_i.$$

Does an upper bound on the total variation distance imply an upper bound on the following quantity?

$$\left|\langle \psi|O |\psi \rangle - \frac{\text{Tr}(O)}{2^{n}} \right|?$$

My intuition is that a change of basis seems to be at the heart of the question -- we are changing from the standard basis to the Pauli basis. How does the total variation distance change with this change of basis?

Probably not in general, no. A useful upper bound needs to beat the state-independent bound $$$$\left| \langle \psi | O | \psi\rangle - \frac{1}{2^n} \text{Tr}(O) \right| \leq \lVert O \rVert_\infty + \frac{1}{2^n}|\text{Tr}(O)|$$$$
By counterexample, we can consider the state $$|\psi\rangle = H^{\otimes n}|0^n\rangle$$ which satisfies the tightest form of your requirement with $$a=0$$ i.e. $$D(\text{diag}(|\psi\rangle \langle \psi|), \mathbb{I}/2^n) = 0$$ where $$D(p, q)$$ denotes total variation distance between two (classical) distributions. But choosing $$O = w_{X^{\otimes n}} X^{\otimes n}$$, we can saturate the naive bound given above, $$$$\left| \langle \psi | O | \psi\rangle - \frac{1}{2^n} \text{Tr}(O) \right| = \lVert O \rVert_\infty + \frac{1}{2^n}|\text{Tr}(O)| = w_{X^{\otimes n}}$$$$
meaning $$a$$ doesn't play a meaningful role in bounding this quantity in this case, or any case involving this choice of $$|\psi\rangle$$ and traceless observables composed from $$X$$ and $$I$$.