Property of Haar random state

Question

Let $|\psi\rangle$ be a Haar random state and let $|\psi^{\perp}\rangle$ be any state that is perpendicular to $|\psi\rangle$. Let us define

$$p_x = |\langle x| \psi \rangle|^2,$$ and $$q_x = |\langle x| \psi^{\perp} \rangle|^2.$$

For any choice of $x \in \{0, 1\}$, I want to compute the quantity

$$ {\mathbb{E}}[p_x q_x], $$ where the expectation is taken over the choice of the state $|\psi\rangle$. Is this exponentially small?

---

I know that since $p_x, q_x \geq 0,$

$$ {\mathbb{E}}[p_x q_x] \leq {\mathbb{E}}[p_x] \cdot \underset{|\psi\rangle}{\mathsf{max}}|q_x|. $$ Now, $q_x \leq 1$ and ${\mathbb{E}}[p_x] = 2^{-n}.$ Hence, $$ {\mathbb{E}}[p_x q_x] \leq 2^{-n}. $$

But is there a tighter bound?

Answer 1

You can prove a lower bound by exhibiting a good candidate for $\left|\psi^\perp\right\rangle$. Without loss of generality (by unitary invariance of the Haar measure), assume $x=0$. To any state $|\psi\rangle$, we associate: $$\left|\psi^\perp\right\rangle=\frac{|0\rangle-\langle\psi|0\rangle\,|\psi\rangle}{\sqrt{1-|\langle0|\psi\rangle|^2}}$$ Intuitively, we take the state maximizing $p_0q_0$ (that is, $|0\rangle$) and then we orthonormalize it using Gram-Schmidt. We then have: $$\begin{align} \mathbb{E}\left[p_0q_0\right] &= \mathbb{E}\left[|\langle0|\psi\rangle|^2\left(1-|\langle0|\psi\rangle|^2\right)\right]\\ &= \mathbb{E}\left[|\langle0|\psi\rangle|^2\right]-\mathbb{E}\left[|\langle0|\psi\rangle|^4\right]\\ &= \frac{1}{2^n}-\frac{1}{\left(2^n+1\right)2^{n-1}} \end{align}$$ where the rightmost expectation has been computed using this answer.

In particular, assuming an adversarial setting, we have: $$\frac{1}{2^n}-\frac{1}{\left(2^n+1\right)2^{n-1}}\leqslant\mathbb{E}\left[p_xq_x\right]\leqslant\frac{1}{2^n}$$ and thus, $\mathbb{E}\left[p_xq_x\right]\sim\frac{1}{2^n}$. We have even a bit stronger: $$\mathbb{E}\left[p_xq_x\right]=\frac{1}{2^n}+O\left(\frac{1}{4^n}\right)\,.$$ In particular, there is no tighter bound, at least asymptotically speaking. Since we haven't proved that the $\left|\psi^\perp\right\rangle$ is optimal, maybe the lower-bound isn't tight and it's possible to have a better bound inbetween.