Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
Consider two Haar random $n$ qubit unitaries, $U_1$ and $U_2$. Consider the quantum state
$$|\psi\rangle = (U_1 \otimes U_2) |0^{2n}\rangle. $$
Let $p_x = |\langle x| \psi \rangle|^{2}$, for $x \in \{0, 1\}^{2n}$. Does the probability distribution $p$ anti-concentrate (anticoncentration is as defined in equation $1$ here)?
I believe so (caveat: this is not something I've every thought about before).
I'm going to rewrite the $p_x$ from your question as $p_{xy}$. So, we have $$ p_{xy}=|\langle x|U_1|0^n\rangle|^2\ |\langle y|U_2|0^n\rangle|^2 $$ Note that this is two independent probabilities $p_x$ and $p_y$.
Now, the probability that $p_{xy}>\alpha'$, which we write as $\mathbb{P}(p_{xy}>\alpha')$ certainly satisfies $$ \mathbb{P}(p_{xy}>\alpha')>\mathbb{P}(p_{x}>\sqrt{\alpha'})^2 $$ because if both the independent probabilities $p_x$ and $p_y$ are bigger than $\sqrt{\alpha'}$, the probability of the produce being larger than $\alpha$ (which includes some events not counted in the independent case) is certainly larger.
Now, from the paper you cite (theorem 5, $\epsilon=0$), we know $$ \mathcal{P}\left((p_x>\frac{\alpha}{N}\right))\geq\frac{(1-\alpha)^2}{2} $$ So, equate $$ \sqrt{\alpha'}=\frac{\alpha}{N} $$ and follow through to find the constant $\beta'$ such that $$ \mathbb{P}(p_{xy}>\alpha')>\beta', $$ the definition of being anti-concentrated.
