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)?


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.