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

Question

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

and, additionally,

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

Answer 1

Probably not in general, no. A useful upper bound needs to beat the state-independent bound \begin{equation} \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)| \end{equation}

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, \begin{equation} \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}} \end{equation}

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