I had a confusion about shallow depth Haar random quantum circuits. In this paper, in Section B (related works), it is mentioned that Haar random quantum circuits form approximate $2$-designs only after $\mathcal{O}\left(n^{1/D}\right)$ depth, where $D$ is the spatial dimension (proved here).

What does this mean for the output distribution of Haar random quantum circuits that have constant and logarithmic depth? For every fixed string $z \in \{0, 1\}^{n}$, does every output probability $|\langle z| U |0^{n} \rangle|^{2}$ approximately follow a Porter-Thomas distribution, even for a shallow depth Haar-random $U$?

If so, what extra mileage does the $2$-design property give us?


First of all, that does not imply anything for shorter (constant/logarithmic) depths. Moreover, the 2-design property does not imply that the outcome distribution is the same as for Haar-random unitaries, but only the first and second moment is.

In the mentioned paper, they consider anti-concentration of the outcome distribution. To show this feature, a distribution does not need to be the one induced by Haar-random unitaries. In fact, any 2-design will result in anti-concentration, and even sufficiently strong approximations of 2-designs.

  • $\begingroup$ I am a bit confused here. Is a "random unitary circuit" different from a "Haar random unitary circuit"? And is is true that the outcome distribution of a shallow depth (constant or logarithmic) random unitary circuit, of the type Google considered, follows a Porter-Thomas distribution (ie, the outcome distribution of a Haar random circuit)? If the outcome distribution is the same as that of a Haar random circuit, doesn't it automatically follow that the first and second moments are also the same, and hence, constant and logarithmic depths form 2 designs? $\endgroup$ – BlackHat18 Feb 22 at 9:36
  • 1
    $\begingroup$ Strictly speaking a "Haar-random unitary circuit" consists of a single multi-qubit Haar-random unitary. Nobody can do this. "Random quantum circuits" (Dalzell et al.) are composed of other random quantum gates. For instance, we can take 2-local Haar-random unitaries of a certain depth. This converges quickly to the multi-qubit Haar measure with depth, however, we are often only interested in the moments. This is strictly weaker and formalised by approximate designs. Harrow-Mehraban showed that geometrically local circuits form approximate t-designs in depth $\mathrm{poly}(t)n^{1/D}$. $\endgroup$ – Markus Heinrich Feb 22 at 10:01
  • $\begingroup$ Thanks! It's a lot clearer now. A question: what did the Google experiment do then? Did they consider an architecture of certain depth that gives a unitary 2-design and a Porter-Thomas output distribution? If so, what was the depth and can this same architecture give a unitary 2 design and a Porter Thomas output distribution for constant and logarithmic depths? $\endgroup$ – BlackHat18 Feb 22 at 10:13
  • $\begingroup$ @BlackHat18 Your first comment was too much to answer in one response :) The output distribution of constant-depth quantum circuits should not be close to Porter-Thomas, nor does the circuit give a 2-design. AFAIK, the hardness of the Google experiment is in fact more complicated. Sure, if they increase the depth, they will probably get approximate unitary designs, but only in linear depth! In logarithmic depth, it is likely that their gate set results in anti-concentration. But to get a PT distribution, they have to go way beyond that (at least that's my guess). Why is PT so important? $\endgroup$ – Markus Heinrich Feb 22 at 10:34
  • $\begingroup$ @BlackHat18 Maybe keep in mind that the PT distribution, 2-designs and anti-concentration are a priori completely independent concepts. They just happen to appear in the context of quantum supremacy. There are implications between these notions, but that doesn't mean that they are connected on a fundamental level. $\endgroup$ – Markus Heinrich Feb 22 at 10:38

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.