2
$\begingroup$

Consider a Haar random quantum state $|\psi \rangle$. I was confused between two facts about $|\psi \rangle$, which appear related:

  1. Consider the output distribution of a particular $n$-qubit $|\psi \rangle$. For a large enough $n$, the probability of what fraction of strings in the output distribution of $|\psi \rangle$ lie between $\frac{1}{2^{n}}$ and $\frac{2}{2^{n}}$ (or between any two numbers)? According to the formulas in the supplement of the Google paper (section IV C, page 9) and this answer, the answer is $$ \int_\frac{1}{2^{n}}^\frac{2}{2^{n}} 2^n e^{-2^np} dp.$$ How to prove this? Also, is this statement true for any Haar-random $|\psi\rangle$, or only with high probability over a particular choice of a Haar-random $|\psi\rangle$? For example, $|\psi\rangle$ could be something trivial like $|0\rangle^{\otimes n}$ and this statement would not hold.

  2. We know that for a particular output string $z \in \{0, 1\}^{n}$, if we define $p_z = |\langle z| \psi \rangle|^{2}$, then the random variable $p_z$ (for a fixed $z$, but for $|\psi\rangle$ chosen uniformly at random from the Haar measure) follows the Porter-Thomas distribution, for every such fixed $z$. The probability density function of the Porter-Thomas distribution is given by \begin{equation} \text{PorterThomas}(p) \sim 2^{n} e^{-2^{n}p}. \end{equation} The same density function also appears inside the integration in the first item. Is this just a coincidence, or are these facts related? The two situations do not seem related (we are interested in a particular $|\psi\rangle$ for the first one and a particular $z$ for the second one) and I do not see an obvious way of going from one to another.

$\endgroup$
2
+150
$\begingroup$

The two facts are connected in that they both arise as a result of rotational invariance of the Haar measure.

We will derive them in the case of large $n$ since this is when the Porter-Thomas distribution takes the exponential form given in the question. Also, this case admits an intuitive proof backed by a geometric picture. For small $n$, Porter-Thomas distribution is a Beta distribution. In this case, the proof turns into a lengthy calculation.

Consider a Haar-random quantum state $|\psi\rangle$ of $n$ qubits. Let $N=2^n$. Commonly, $|\psi\rangle$ is thought of as a complex vector $(a_0+ib_0, a_1+ib_1, \dots, a_{N-1}+ib_{N-1})^T \in \mathbb{C}^{N}$ of unit norm, but we will think of it as a real vector

$$ v = \sqrt{2N}(a_0, b_0, a_1, b_1, \dots, a_{N-1}, b_{N-1})^T\in\mathbb{R}^{2N}. $$

Since $|\psi\rangle$ is drawn from the Haar measure, $v$ is uniformly distributed over a sphere of radius $\sqrt{2N}$ in $\mathbb{R}^{2N}$. We would like to characterize the distribution of the real coordinates $a_j$ and $b_j$.

An easy observation is that all coordinates $a_j$ and $b_j$ have the same distribution. This follows from the fact that Haar measure is unitarily invariant and permutations are unitary matrices. We can say more using the following

Theorem (Diaconis-Freedman). The first $k=o(d)$ coordinates of a point uniformly distributed over the surface of the $d$-sphere of radius $\sqrt{d}$ are independent standard normal variables in the limit of $d\to\infty$.[1]

In our case, permutation invariance means that any $k=o(N)$ coordinates of $v$ are independent standard normal variables, $a_j\sqrt{2N} \sim \mathcal{N}(0, 1)$ and $b_j\sqrt{2N} \sim \mathcal{N}(0, 1)$. Consequently,

$$ 2Np_j = 2N|\langle j|\psi\rangle|^2 = \left(a_j\sqrt{2N}\right)^2 + \left(b_j\sqrt{2N}\right)^2 $$

is the sum of squares of two standard normal variables. In other words, $2Np_j$ is a chi-square random variable with two degrees of freedom which is the same distribution as the exponential distribution with rate parameter $\lambda = \frac{1}{2}$. Thus, the probability density function of $2Np_j$ is $\frac{1}{2}\exp(-\frac{1}{2}p)$, so probability density function of $p_j$ is $N\exp(-Np)$, establishing fact 1 in the question.

Now suppose we independently draw two quantum states $|\psi_1\rangle$ and $|\psi_2\rangle$ from the Haar measure. Fix an output bitstring $j \in \{0, 1\}^n$ and consider the output probabilities $|\langle j|\psi_1\rangle|^2$ and $|\langle j|\psi_2\rangle|^2$. Since $|\psi_1\rangle$ and $|\psi_2\rangle$ have been drawn independently from the Haar measure, the two probabilities are independent from each other. Moreover, by the arguments above both have the same distribution with density function $N\exp(-Np)$, establishing fact 2 in the question.

The key point to explain the symmetry between facts 1 and 2 is the independence of different coordinates of a uniformly distributed point on a sphere. As long as we only have access to a small number $k=o(2^n)$ of output probabilities of a Haar-random quantum state they are all independent and identically distributed random variables with Porter-Thomas distribution. In other words, for any quantum states $|\psi_j\rangle$ chosen independently from the Haar measure and any $k=o(2^n)$ bitstrings $z_i\in\{0, 1\}^n$, also chosen independently, each of the probabilities $|\langle z_i|\psi_j\rangle|^2$ constitutes an independent sample from the same distribution with density function $N\exp(-Np)$. This highlights the very high degree of symmetry of the Haar measure.


The observation that some states with non-zero probability density, such as $|0\rangle^{\otimes n}$, do not exhibit Porter-Thomas output distribution is correct. One might be tempted to dismiss this case as a zero-measure set. However, there is a small, but positive measure set of states in the vicinity of $|0\rangle^{\otimes n}$ that also do not exhibit Porter-Thomas output distribution.

The key point is that typical Haar-random states do. This can probably be made more rigorous by deriving an appropriate concentration inequality, e.g. bounding the probability that the total variation distance between the output distribution of a Haar-random state and the Porter-Thomas distribution exceeds a threshold. However, the following informal argument illustrates the point. One way to think of the process of drawing a Haar-random state is as a long sequence of draws of the real and imaginary parts of each amplitude from (approximate) standard normal distribution: $a_0, b_0, a_1, b_1, \dots$. A quantum state in the vicinity of $|0\rangle^{\otimes n}$ can be thought of as a sequence in which $a_0$ is approximately $1$ and all other numbers are approximately $0$. Probability of obtaining such a result from a sequence of draws from (approximate) standard normal distribution is extremely small, because the dimension of the Hilbert space and thus the length of the sequence is very large.


[1] Persi Diaconis and David Freedman. A dozen de Finetti-style results in search of a theory. Ann. Inst. H. Poincar´e Probab. Statist., 23(2, suppl.), p.397–423, 1987.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks for an excellent answer! $\endgroup$
    – BlackHat18
    Feb 2 at 19:19
  • 1
    $\begingroup$ You're welcome! I'm glad it's helpful! Thank you for asking deep, interesting questions! :-) $\endgroup$ Feb 2 at 19:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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