It is my understanding that, given a quantum computer with $n$ qubits and a way to apply $m$ single- and 2-qubit gates, quantum supremacy experiments

  1. Initialize the $n$ qubits into the all-zero's ket $|000\cdots\rangle$
  2. Generate a random unitary $U$ of $m$ gates
  3. Apply the quantum gate $U$ to these qubits, e.g. produce the state $|\Psi\rangle=U|000\cdots\rangle$
  4. Measure $|\Psi\rangle$ to produce an $n$-bit classical string
  5. Measure some property the sampled string, such as a cross-entropy, and determine if quantum supremacy is achieved based on the sampled string, as compared to, say, the uniform distribution.

This can be repeated multiple times.

  • Would a claim of quantum supremacy require applying the same random unitary $U$ each time, for each sample? Or is there a different pseudo-random $U$ for each sample?

I think I'm reading that $U$ is broken up into a set of pseudo-random single-qubit gates, followed by a set of 2-qubit gates. Are either or both of these fixed, or do they change for each sample?

  • 2
    $\begingroup$ are you referring to a specific class of quantum supremacy experiments here (e.g. to IQP circuits)? Generally speaking, these kinds of experiments want to show "quantum supremacy" by solving sampling problems which are provably efficiently unsolvable classically. The thing with sampling problems is that, in principle, a single sample is sufficient to "achieve quantum supremacy". But how do you certify that that single sample was drawn according to the correct "hard" probability distribution? So what people do is to collect some statistics, compute some properties of it, and verify that ... $\endgroup$ – glS Sep 22 '19 at 22:00
  • 1
    $\begingroup$ ... they are what they should be if the distribution they are sampling from is indeed the correct one. So when can you say that "quantum supremacy is achieved" then? That's a tricky question, and at the end of the day it boils down to having collected enough evidence to convince the majority of people that everything is working as intended. $\endgroup$ – glS Sep 22 '19 at 22:07
  • 3
    $\begingroup$ Not going into detail of any particular supremacy scheme, just from a statistical viewpoint it should be clear that you need to apply the same random unitary $U$ each time in order for your samples to capture the properties of some probability distribution $p_U$. If you switched unitaries, then you would effectively draw a single sample from the distributions $p_{U_1}, p_{U_2}, p_{U_3}, \dots$ and all these might be hard to sample from but a single sample will most likely not be enough to establish that $\endgroup$ – Marsl Sep 23 '19 at 11:29
  • 1
    $\begingroup$ In case you are confused by the need for a random unitary, it needs to be random in order to avoid that the classical sampler trying to reproduce the right prob. distribution can adapt to the particular unitary. Basically, if I wanted build a classical sampling algorithm that solves the problem for any unitary you hand over to me (or a description of the circuit), then the randomness assures that my sampler has to be "general-purpose", I have to design it such that it works well for any instance! $\endgroup$ – Marsl Sep 23 '19 at 11:36
  • 1
    $\begingroup$ as I understand, that is it. In particular, if you are referring to the leaked Google paper( which you can read here docdroid.net/h9oBikj/… ). I havent read it in full, since its not official, but from what I have read, I understand they used XEB. Whether we accept this or not, is a different question given that XEB is not provably a valid verification method. $\endgroup$ – Marsl Sep 24 '19 at 17:51

Generally speaking, to prove quantum supremacy, you don't need to sample several times from the same unitary/circuit/output probability distribution. If you extract even a single sample from the output probability distribution of a circuit which you know is extremely hard to simulate classically, then you already achieved something that you couldn't do (efficiently) classically.

This is because these are sampling problems. Such problems are not about estimating some property of some output probability distribution, but rather simply about the sampling itself.

The caveat in this is that, in practice, just observing one output state from a given circuit wouldn't look all that great an achievement. In other words, one needs to gather enough "circumstantial evidence" to manage to convince most people that the claim is solid and legit. This often includes actually retrieving some statistical features of the distribution, which allows checking that the distribution was indeed the intended one. It is, however, important to realise that the problem is not that of computing such features, but rather only that of sampling from the underlying probability distribution.

In conclusion, to more directly address some of the points raised: one unitary sampled once is, in principle, enough. But one wants to gather enough evidence to make the claim as solid as possible, and for this it is useful to do things like estimating properties of the experimental output distribution.

| improve this answer | |
  • $\begingroup$ In my opinion, while this is completely true, I would like to stress how important the certification of the experiment actually is. I mean, anyone could claim they built a quantum device running BosonSampling, RCS or whatever supremacy scheme you want. But then, we wouldn't outright announce supremacy being achieved. D-Wave has claimed their devices were doing something quantum for years, still many are not sold. Even the google paper only provides evidence (in form of XEB) for actually having sampled from the right distribution. $\endgroup$ – Marsl Oct 1 '19 at 17:48
  • $\begingroup$ @Marsl sure, I didn't mean to downplay the importance of certification in this context. But it is important to understand in my opinion that the certification is not what gives the "quantum supremacy". Rather, it is what gives you confidence that the experiment that achieves quantum supremacy is working as intended. In a world in which these sorts of experiments are an every-day occurrence, you probably wouldn't feel the need to certify your experiment, because you would have previously amassed a sufficient amount of confidence in your devices. $\endgroup$ – glS Oct 1 '19 at 18:00
  • $\begingroup$ I am entirely on your side. To me it just looks like, the supremacy schemes are already there in a variety of flavors and a lot of work has been put into making the conjectures they are based on as well established as possible. On the other hand, on the certification side, we are in still in lack of reliable methods that are necessary as long as we are just at the brink of building our first ever so noisy devices. $\endgroup$ – Marsl Oct 1 '19 at 18:22

In the Sycamore paper linked in the comments, in the description of FIG. 4, the authors state:

  • ...For each $n$, each instance is sampled with $N_s$ between 0.5 M and 2.5 M... For $m=20$, obtaining 1M samples on the quantum processor takes 200 seconds, while an equal fidelity classical sampling would take 10,000 years on 1M cores, and verifying the fidelity would take millions of years.

Thus, it is clear that the authors of the Sycamore paper repeatedly apply the same unitary each time.

Thinking about it now this makes sense, you would need to sample more than once to be able to accurately estimate the fidelity of your samples.

| improve this answer | |
  • $\begingroup$ Yeah, I guess it's like 1M "shots" in 200 seconds. I asked the same question here before I noticed your post. $\endgroup$ – Sanchayan Dutta Sep 28 '19 at 15:45

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.