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

Question

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?

Answer 1

1. A computational task doesn't have to have or be an application in order to be part of a valid model. If you claim that you can run a mile faster than I can, your four-minute mile doesn't have to be profitable employment in order to count. On the other hand, the random sampling demonstration with Sycamore certainly is an action of some kind performed by a computer. It is sort-of the same thing as (but much more sophisticated than) a computer algorithm to random-sort a list of numbers.

2. CS theorists have lived for decades with artificial complexity classes that they can't prove are different from P, or for that matter BPP. PSPACE is a vast complexity class that has to be bigger than P, but no one can prove that. But it isn't considered a realistic complexity class. For that matter the logicians who came before the CS theorists, including Church and Turing themselves, could and did define computation classes that they know are different from the Church-Turing standard of computability. It is Turing's own theorem (one of them anyway) that the class RE, recursively enumerable, is larger than R, recursive or computable. The Church-Turing thesis says that all realistic computability roads lead to the same Rome, namely R. The fact that you can also define something bigger like RE doesn't disprove that thesis. Any version of Church-Turing is about what is realistic, not about what you can define.

3. (Actually more 2.) The ECT says that all roads of polynomial computability also lead to the same Rome, P or BPP. In this case people cannot prove as much. In fact, even faith in ECT ultimately depends on the open conjecture that P and BPP are equal. BQP ≠ BPP is another thing that people can't prove, because they are both sandwiched between P and PSPACE and no one can prove that P ≠ PSPACE either. (In fact it's worse than that, there are major results on how not to prove that P ≠ PSPACE.) But that's okay, we can still believe these things based on evidence even if we can't prove them. Everyone also believes that there are infinitely many twin primes, etc. The relation between the quantum supremacy demo and ECT comes down to whether you believe that there is an efficient classical algorithm for what the Sycamore chip does.