7
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

I think the rough, imprecise answer is "yes, $20$ cycles of the one- and 2-qubit gates of Sycamore is sufficient to be able to generate a (Haar measure)-random element of the Hilbert space of dimension $2^{53}$."

For example, the diameter (longest shortest path) between any two qubits on Sycamore is $12\lt 20$, thus any two qubits should have a chance to interact at least once.

More importantly, a recent lecture from O'Donnell notes that Harrow and Mehrabran prove Google's conjecture that a circuit on a two-dimensional lattice of depth $O(\sqrt{n})$ is sufficient to scramble and generate a random state. FIG. 2 of Harrow and Mehrabran look closer to the $\mathrm{EFGH}$ tiles used in the "easier" pattern on Sycamore - certainly the supremacy tiles $\mathrm{ABCDCDAB}$ should be even more scrambling.

If $20$ was not sufficient, then I think that would only make the cross-entropies higher. However, I'm not sure whether this is necessary for the central claim of supremacy. It may be impossible to model the beating/scrambling of an egg for 2 seconds to a high-enough accuracy, although clearly such an egg is not likely to be fully homogenized.

$\endgroup$

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.