# Average output state of random quantum circuits

Let $$|\psi\rangle = C_1 |0^{n}\rangle$$ be a quantum state, such that $$C_1$$ is a Haar random unitary circuit. Consider a density matrix $$\rho$$ as follows

$$$$\rho_1 = \mathbb{E}[|\psi\rangle\langle \psi|],$$$$ where the expectation is taken over the circuits.

Now, consider another family of states $$|\phi\rangle = C_2 |0^{n}\rangle$$, where $$|\phi\rangle$$ is a sufficiently deep random quantum circuit, comprising of layers of local one and two qubit random unitaries drawn from the Haar measure, such that the output distribution of $$C_2$$ when measured in the standard basis is a Porter-Thomas distribution. In other words, it is a type of circuit used in the Google quantum supremacy experiment. Let $$$$\rho_2 = \mathbb{E}[|\phi\rangle\langle \phi|],$$$$ where the expectation is taken over all circuits of type $$C_2$$.

I am trying to show that $$$$\rho_1 = \frac{\mathbb{I}}{{2^{n}}},$$$$ and that the trace distance of $$\rho_1$$ and $$\rho_2$$ is very small.

That $$\rho_1$$ is the maximally mixed state is qualitatively easy to see --- $$\rho_1$$ is essentially a uniform distribution over all possible quantum states. But I could not do this mathematically.

## Calculating $$\rho_1$$

Let $$N=2^n$$ denote the dimension of the Hilbert space where $$|\psi\rangle$$ lives. For $$i=0,\dots,N-1$$, let $$V_i$$ be any unitary that maps $$|i\rangle$$ to $$|0\rangle$$. The action of $$V_i$$ on other computational basis states $$|j\rangle$$ with $$j\ne i$$ is irrelevant. Exploiting the invariance of the Haar measure to absorb $$V_i$$ into the integration variable $$C_1$$, we have

\begin{align} \rho_1 &= \mathbb{E}[|\psi\rangle\langle\psi|] \\ &=\int C_1|0\rangle\langle0|C_1^\dagger dC_1 \\ &=\frac{1}{N}\sum_{i=0}^{N-1}\int C_1|0\rangle\langle 0|C_1^\dagger dC_1 \\ &=\frac{1}{N}\sum_{i=0}^{N-1}\int C_1V_i|i\rangle\langle i|V_i^\dagger C_1^\dagger dC_1 \\ &=\frac{1}{N}\sum_{i=0}^{N-1}\int C_1|i\rangle\langle i|C_1^\dagger dC_1 \\ &=\frac{1}{N}\int C_1\left(\sum_{i=0}^{N-1}|i\rangle\langle i|\right)C_1^\dagger dC_1 \\ &=\frac{1}{N}\int C_1\mathbb{I}C_1^\dagger dC_1 \\ &=\frac{\mathbb{I}}{N}\int dC_1 \\ &=\frac{\mathbb{I}}{N} \\ \end{align}

where we also assumed that the measure is normalized.

## Comparing $$\rho_1$$ and $$\rho_2$$

In order to quantify how close $$\rho_2$$ is to $$\rho_1=\frac{\mathbb{I}}{N}$$, we first need to have some idea of how close the distribution of $$C_2$$ is to the Haar measure. Comparing measures is hard in general, but in this case, at least if you are willing to use fidelity instead of trace distance, the problem can be simplified to the calculation of just the first moment. Namely, the fidelity of $$\rho_1$$ and $$\rho_2$$ is

$$F(\rho_1, \rho_2) = \left(\mathrm{tr}\sqrt{\rho_2^{1/2}\rho_1\rho_2^{1/2}}\right)^2 = \frac{\left(\mathrm{tr}\sqrt{\rho_2}\right)^2}{N} = \frac{\left(\mathrm{tr}\sqrt{\mathbb{E}[|\phi\rangle\langle\phi|]}\right)^2}{N} \\ = \frac{1}{N}\left[\mathrm{tr}\sqrt{\int C_2|0\rangle\langle 0|C_2^\dagger dC_2}\right]^2$$

so the fidelity depends only on the first moment of the distribution of $$C_2$$. Evaluating it depends on the details of the circuits. As pointed out by @BlackHat18 in the comments, in the particular case when $$C_2$$ is discrete and a $$1$$-design, we have

$$\mathbb{E}[|\phi\rangle\langle\phi|] = \frac{1}{|C_2|}\sum_{C_2}C_2|0\rangle\langle 0|C_2^\dagger = \int C_1|0\rangle\langle0|C_1^\dagger dC_1 = \frac{\mathbb{I}}{N}$$

and so $$F(\rho_1, \rho_2) = 1$$. In this case, the trace distance between $$\rho_1$$ and $$\rho_2$$ is zero. In the more general case, this paper might offer more insight and ideas.

• If the distribution of $C_2$ is an exact $1$-design, is it sufficient to say that $\int C_2|0\rangle\langle 0|C_2^\dagger dC_2 = \mathbb{I}/2^{n}$? Sep 5, 2021 at 14:53
• Yes, because if $C_2$ is an exact $1$-design then $$\int C_2|0\rangle\langle 0|C_2^\dagger dC_2 = \int C_1|0\rangle\langle 0|C_1^\dagger dC_1=\mathbb{I}/2^n$$ where the first equality follows from the definition of $1$-design and the second from the calculation above. Note that the integral with respect to $C_2$ is really a sum due to discrete nature of $C_2$. Sep 5, 2021 at 15:20
• Thanks! At what depth do random circuits composed of local Haar-random one or two qubit gates (like the circuit in the Google experiment) become (exact or approximate) 1 designs? Sep 5, 2021 at 15:25
• This is the question answered in the paper I linked to at the end. The exact answer will depend on the details of the circuits (e.g. connectivity and gateset), but generally the output becomes a $1$-design much earlier than it becomes a good approximation of the Haar measure (which in particular implies agreement with the Haar measure of all moments, not just the first). I also recommend numerical experiments :-) Sep 5, 2021 at 15:36
• One more naive question. In the Google experiment, the authors claimed that they experimentally saw the Porter-Thomas distribution at $\sqrt{n}$ depth. Does this imply that their architecture was at least a $\text{poly}(n)$ design? If not, did they, independently, assert anything about whether their circuit was some design? Sep 8, 2021 at 18:34