# How does successfully sampling from a random quantum circuit invalidate the Extended Church-Turing Thesis?

According to these lecture notes from Berkeley, the Extended Church-Turing Thesis (ECT) asserts that:

...any "reasonable" model of computation can be efficiently simulated on a standard model such as a Turing Machine or a Random Access Machine or a cellular automaton. (Emphasis added).

Google is claiming that, by preparing and sampling from a highly-entangled random state in a Hilbert space of dimension $$2^{53}$$, they are marching towards quantum supremacy. As intimated by, for example, Aaronson here, a successful demonstration of sampling from a large-enough Hilbert space with a high-enough fidelity will indeed invalidate the Extended Church-Turing Thesis.

There seems to be at least two challenges to this claim.

1. Random circuit sampling (even from a Hilbert space of high-enough dimension) does not constitute a demonstration of quantum supremacy, because random circuit sampling does not correspond to "classic" applications of quantum computing (such as Shor's algorithm), or does not appear to be a "computation" in the sense of an action performed by a computer.

2. Even granting that random circuit sampling does constitute a demonstration of quantum supremacy, it's not clear that the Efficient Church-Turing Thesis requires any physical instantiation of a hypothetical quantum device, and the "reasonable" model of computation only needs to be a purely platonic description of different complexity classes. Thus the ECT is only invalidated if one were to prove, e.g., that $$\mathrm{BQP}\ne\mathrm{BPP}$$ or something similar.

My question: Why can we say that the ECT falls with a successful demonstration of random circuit sampling from a large enough Hilbert space?

That is, what are the rejoinders to the above positions? Are there other potential faults in the logic connecting random circuit sampling to the negation of the ECT?

• In the supremacy FAQ blog post, 1. Aaronson does assert that the random circuit sampling problem is classically intractable (to the best of our knowledge), although the experiment is not par excellence, unlike Shor's algorithm. 2. Yes, the ECT is falsified (again, to the best of our knowledge). This question seems to be right up @GregKuperberg's alley; let's hope for an answer from him! – Sanchayan Dutta Oct 30 '19 at 19:58
• – Sanchayan Dutta Oct 30 '19 at 20:14
• It's a good question, nonetheless. The more pressing confusion for most people would be that it's not obvious how random sampling is a computation in the Church Turing thesis sense (i.e., the objection @R.. raised). I guess we should make a Q&A thread on that. – Sanchayan Dutta Oct 30 '19 at 20:39
• @SanchayanDutta For 1, I believe that RCS is #P-hard (here: arxiv.org/pdf/1803.04402.pdf) and I believe that if you show that this problem or class has a polynomial-time, then there must be a collapse in the PH which is unlikely to happen. – YOUSEFY Oct 31 '19 at 15:18
• @YOUSEFY Indeed, that was my impression too. Thanks for the reference! – Sanchayan Dutta Oct 31 '19 at 15:27