Computing expectation value of $|\langle z|C|0^n\rangle|^2$ over Haar random circuit

Question

I am trying to understand the integration on page 4 of this paper. Consider a Haar random circuit $C$ and a fixed basis $z$. Each output probability of a Haar random circuit (given by $|\langle z | C |0^{n} \rangle |^{2}$, for each fixed z) is distributed according to the Porter Thomas distribution, given by \begin{equation} \text{PorterThomas}(x) = 2^{n} e^{-2^{n} x}. \end{equation}

The paper claims that \begin{equation} \mathbb{E}[|\langle z | C |0^{n} \rangle |^{2}] = \int_{0}^{\infty} \frac{x}{2^{n}} x e^{-x} \,dx = \frac{2}{2^{n}}. \end{equation}

However, I do not understand the integration at all. Shouldn't the integration instead be

\begin{equation} \mathbb{E}[|\langle z | C |0^{n} \rangle |^{2}] = \int_{0}^{\infty} x ~2^{n} e^{-2^{n} x} \,dx = \frac{1}{2^{n}}, \end{equation} where I am just using the definition of the expected value and plugging in the pdf for Porter Thomas. However, this gives me a very different answer.

Where are all the extra terms coming from and why is the answer $\frac{2}{2^{n}}$?

Answer 1

The issue that easily leads to confusion is the dual role played by output bitstring probability. It enters the computation of the average in two ways. On one hand, it determines how often one sees different bitstrings. On the other hand, it determines the contribution that each bitstring makes towards the average. In mathematical terms, the output bitstring probability affects both the probability measure of the random variable as well as its value.

To see this, consider the following example procedure that yields $\mathbb{E}[|\langle z | C |0^{n} \rangle |^{2}]$:

1. Run the quantum circuit on a noiseless quantum computer or simulator and obtain the output bitstring $z$.
2. Simulate the quantum circuit on a classical computer to compute the value of the probability $|\langle z | C |0^{n} \rangle |^{2}$.
3. Repeat steps 1 and 2 to obtain the average of probabilities computed in step 2 across many output bistrings sampled in step 1.

In step 1, the output bitstring probability affects the bitstrings you see - you see the more likely bitstrings more often. In step 2, it affects the value you add up in the computation of the average - the more likely bitstrings contribute more towards the average.

We can make this reasoning more rigorous (following section IV C of QS paper supplement). The fact that the distribution of output bitstring probabilities is Porter-Thomas means that the fraction of output bitstrings with probability in $[p, p+dp]$ is:

$$ Pr(p) \, dp \approx 2^n e^{-2^np} dp. $$

Since there are $2^n$ possible output bitstrings, the number of bitstrings with probability in $[p, p+dp]$ is

$$ N(p) \, dp \approx 4^n e^{-2^np} dp. $$

Therefore, the probability that in step 1 above we see a bitstring whose probability lies in $[p, p+dp]$ is

$$ f(p) \, dp \approx p \, 4^n e^{-2^np} dp. $$

Note that $f(p)$ is the probability density function for the output bitstring probability. Therefore, the average output bitstring probability is

$$ \mathbb{E}[|\langle z | C |0^{n} \rangle |^{2}] = \int_0^1 p f(p) dp \approx \int_0^1 p^2 4^n e^{-2^np} dp \approx 2/2^n $$

as expected.

You may object that $f(p)$ defined above is not correctly normalized. This is due to the fact that the exponential formula is an approximate form of the Porter-Thomas distribution which is in fact a Beta distribution

$$ (2^n - 1) (1 - p)^{2^n - 2} \approx 2^n e^{-2^np}. $$

In practice, this approximation is very good for $n$ above a dozen or so.

For completeness, note that if you were running the quantum circuits on a noisy quantum computer the distribution in step 1 would be different and the resulting average would be a number between $1/2^n$ and $2/2^n$ according to the fidelity obtained in the experiment. This is the key idea behind linear cross-entrpy benchmarking.

Answer 2

I was also flummoxed by the apparent puzzle why the value of $\mathbb{E}[\langle z|C|0^n\rangle|^2]$ is $2/2^n$ instead of $1/2^n$, but in my opinion I think the confusion arises from the symbol $\mathbb{E}$ (expectation value) whose meaning is rather ambiguous. Expectation value over what?

Case 1: Fix a bit-string $z$. We ask for the value of $\langle z|C|0^n\rangle|^2$, averaged over unitary $C$ drawn from the Haar measure. Then, $\mathbb{E}[\langle z|C|0^n\rangle|^2]$ is really (note subscript in $\mathbb{E}$): $$ \mathbb{E}_{C}[|\langle z|C|0^n\rangle|^2]=\int_{C \sim \text{Haar($2^n$)}} dC \langle z|C|0^n\rangle \langle 0^n|C^\dagger |z\rangle = \frac{1}{2^n}\langle z|\mathbb{I}|z\rangle =\frac{1}{2^n}. $$ In the second equality I used the well-known result of Haar averaging $\int_{U\sim\text{Haar($2^n$)}} dU UOU^\dagger = \text{Tr}(O) \mathbb{I}/2^n $ where $\mathbb{I}$ is the identity matrix.

Case 2. Adam Zalcman in the previous answer presented the following sampling protocol. At run $i$, the quantum computer chooses a circuit $C_i$ from some distribution (let's say Haar) to implement. We then measure, to obtain a bit-string $z_i$. We keep a (classical) record of what circuit $C_i$ it implemented as well as the measurement outcome $z_i$. We then use a classical computer to compute the number $x_i := |\langle z_i|C_i|0^n\rangle|^2 \in [0,1]$. Then repeat this over $M$ runs, and form the empirical mean: $$ \frac{1}{M} \sum_{i=1}^M |\langle z_i|C_i|0^n\rangle|^2 $$ In the limit of large $M$, what does this converge to?

Well, law of large numbers tells us for $x_i$ i.i.d., $\lim_{M \to \infty} \frac{1}{M}\sum_{i=1}^M x_i = \int dx xp(x)$ where $p(x)$ is the probability density function of $x$.

In our case $x$ is the result of sampling from the joint distribution of the output bit string $z \in \{0,1\}^n$ and circuit $C$.

So the empirical mean converges to, $$ \mathbb{E}_{z,C}[|\langle z|C|0^n\rangle|^2]=\int_{C \sim \text{Haar($2^n$)}} \sum_{z \in \{0,1\}^n} |\langle z|C|0^n\rangle|^4 $$ We swap the integral and sum, and evaluate the integral first using Weingarten calculus. This is (using 2nd moment of Haar random states): $$ \sum_{z \in \{0,1\}^n} \frac{\langle z|^{\otimes 2}(I + S)|z\rangle^{\otimes 2} }{2^n(2^n+1)} $$ where $I$ is the identity on the two-copy Hilbert space $\mathbb{C}^{2^n} \otimes \mathbb{C}^{2^n}$ and $S$ is the swap on the two-copy space. Expectation value within the bit-string states yields 1 for both, so the above evaluates to $$ \sum_{z \in \{0,1\}^n} \frac{2}{2^n(2^n+1)} = \frac{2}{2^n+1} \approx \frac{2}{2^n} $$ So we see the origin of the 2 in the numerator which is the number of elements of the permutation group $S_2$.

So in my humble opinion, the confusion could have been avoided by adding the appropriate subscripts in the expectation value: $\mathbb{E}_C$ vs $\mathbb{E}_{z,C}$, to denote averaging over what.