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?

  • 1
    $\begingroup$ 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! $\endgroup$ Commented Oct 30, 2019 at 19:58
  • $\begingroup$ Related: (CS Theory SE) Extended Church-Turing Thesis $\endgroup$ Commented Oct 30, 2019 at 20:14
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Oct 30, 2019 at 20:39
  • 2
    $\begingroup$ @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. $\endgroup$
    Commented Oct 31, 2019 at 15:18
  • 1
    $\begingroup$ @YOUSEFY Indeed, that was my impression too. Thanks for the reference! $\endgroup$ Commented Oct 31, 2019 at 15:27

1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.