Are 20 repetitions of Sycamore's one- and 2-qubit gates sufficient to produce a uniformly random state?

Question

In the answer to this question about random circuits, James Wootton states:

One way to see how well we [fully explore the Hilbert space] is to focus on just randomly producing $n$ qubit states. These should be picked uniformly from all possible states, and not be biased towards the tiny set of states that it is easy for us to produce or write down. This can be done by running a random circuits of sufficient circuit depth. The number of gates for this thought to be efficient (i.e. polynomial in $n$), though I'm not sure if this is proven or is just a widely held conjecture. (Emphasis added).

The Google Sycamore team ran a cycle of $m=20$ repetitions of random single- and 2-qubit gates on $n=53$ qubits.

Can there be a claim that Sycamore was able to prepare a state drawn uniformly at random from the Hilbert space of dimension $2^{53}$? That is, with the gate sets of Sycamore, are we getting far enough away from the $|000\cdots 0\rangle$ initial state to be uniformly random?

Certainly a simple counting argument is sufficient to show that there are many states in the Hilbert space that would never be achieved, or are even $\epsilon$-close to being acheived, by only $20$ repetitions of the Sycamore gate-set; however, can we say that the states that could be achieved by $20$ such repetitions are uniformly distributed within the Hilbert space?

I suspect the answer is most assuredly "yes", the Sycamore repetition is sufficient to uniformly explore the entirety of the Hilbert space, much as only $7$ dovetail shuffles are sufficient to randomly shuffle a deck of cards. However, in the setting of a Hilbert space, can this conjecture be placed on any theoretical footing?

Note that I think this question is independent of the claim of supremacy. Even if the circuit wasn't deep enough to fully and uniformly explore all corners of the Hilbert space, it may be difficult/impossible for a classical computer to compute any such state produced by Sycamore.

Answer 1

In fact, you would need an astronomical circuit depth in order to get close to a uniformly random state, or even close to a randomly chosen probability distribution on the $2^{53}$ outputs.

As a first estimate, consider how many different distributions you need in order to be within 1/8 of the total variation distance of any distribution on $N$ outputs. There is special formula that the TVD ball of radius $r$, in the space of these distributions, has volume $r^{N-1}\binom{2N-2}{N-1}$ times the volume of the entire simplex of distributions. Recall also the elementary inequality $\binom{2N-2}{N-1} < 4^{N-1}$. Therefore, to get within a TVD distance of $\frac18$ of even half of the space of measures on the simplex, you need at least $2^{N-2}$ examples. Recall also that $N = 2^n$ is exponential in the number of qubits. The result is a doubly exponential lower bound for the number of needed circuits.

On the other side, technically speaking there are infinitely many random circuits of any given depth, because a 2-qubit gate has continuous parameters. However, there is some finite set of gates that comes close to all of the 2-qubit gates. Skipping over some calculation, the end result is that unitary operators that you can make with circuits of depth $d$ acting on $n$ qubits is well-approximated by $2^{\mathrm{poly}(n,d)}$ distinct examples, which is only singly exponential with a polynomial exponent, rather than doubly exponential.

However, if circuits of any reasonable size don't produce a randomly chosen distribution, small circuits might still produce states or distributions with the same features as one that is actually randomly chosen. For many natural types of features, such as the spectrum of probabilities of the individual outcomes, that is exactly what happens. The approximate $t$-design property is a related standard, and is much weaker than actually achieving a uniformly random distribution on outputs or anything close to it.