In a recent post we discussed Google’s claim of achieving “quantum supremacy” and my reasons to think that these claims will not stand. (See also this comment for necessary requirements from a quantum supremacy experiment.) This debate gives a good opportunity to discuss some conceptual issues regarding sampling, probability distributions, statistics, and computational complexity. This time we will discuss chaotic behavior vs. robust experimental outcomes.
On unrelated matter, I just heard Shachar Lovett’s very beautiful TCS+ lecture on the sunflower conjecture (see this post on the Alweiss, Lovett, Wu, and Zhang’s breakthrough). You can see the lecture and many others on the TCS+ you tube channel.
Slide 30 from my August, ’19 CERN lecture: predictions of near-term experiments. (Here is the full powerpoint presentation.) In this post we mainly discuss point b) about chaotic behavior. See also my paper: The argument against quantum computers.
Consider an experiment aimed for establishing quantum supremacy: your quantum computer produced a sample which is a 0-1 string of length from a certain distribution . The research assumption is that is close enough to a fixed distribution ( accounts for the computing process and the noise) which is very hard to be demonstrated on a classical computer. By looking at a large number of samples you can perform a statistical test on the samples to verify that they were (approximately) sampled from , or at least that they were sampled from a probability distribution that is very hard to be computed on a classical computer!
But, is it possible that all the distributions ‘s are very different? Namely that each sample is taken from a completely different distribution? More formally, is it possible that under a correct modeling of the device for two different samples and , has a very small correlation with ? In this case we say that the experiment outcomes are not robust and that the situation is chaotic.
Here are a couple of questions that I propose to think about:
- How do we test robustness?
- Do the supremacy experiments require that the experiment is robust?
- If, after many samples, you reach a probability distribution that require exponential time on a classical computer should you worry about the question whether the experiment is robust?
- Do the 10,000,000 samples for the Google 53-qubit experiment represent a robust sampling experiment?