1
$\begingroup$

Note: This has been cross-posted to Quantum Computing SE.

If we assume $\mathsf{BQP} \neq \mathsf{BPP}$, then we can say with reasonable certainty that Google's random sampling experiment falsifies the Extended Church Turing thesis. However, in a related thread, a user raised the objection that the random circuit sampling problem might not be a computation in the Church Turing sense:

@glS: Decision problems, computable functions, etc. are equivalent, so whichever form you like. Sampling is not even a function, much less a computable one. It's a physical process outside the scope of computing/functions.

Could someone elaborate on this apparent discrepancy? Can the random circuit sampling problem indeed be framed in terms of computable functions and effective calculability or a decision problem, as the CT thesis requires?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ "If we assume BQP≠BPP, then we can say with reasonable certainty that Google's random sampling experiment falsifies the Extended Church Turing thesis." I disagree with this. You need something stronger: you need that this particular problem (posed as a decision problem) is not in BPP. BQP≠BPP just says that there exists such a problem, not that it's this one. $\endgroup$ – Huck Bennett Oct 31 '19 at 0:22
  • $\begingroup$ Please do not post the same question on multiple sites simultaneously. $\endgroup$ – D.W. Oct 31 '19 at 0:28
  • $\begingroup$ Even though I answered the question here, I think that per policy the whole question should be deleted. $\endgroup$ – Greg Kuperberg Oct 31 '19 at 16:16
  • 1
    $\begingroup$ @GregKuperberg It's technically not possible to delete the question when the answer has a score of >0; a moderator could do it though. In any case, I don't think there's any pressing need to delete it. Both the communities could potentially benefit from the discussion here. I personally find the policy to be a bit silly, given that the question is perfectly on-topic on both the sites and that the fact that it was cross-posted was mentioned upfront. $\endgroup$ – Sanchayan Dutta Oct 31 '19 at 16:20
  • $\begingroup$ Okay, I guess I don't feel strongly about it. $\endgroup$ – Greg Kuperberg Nov 1 '19 at 16:02
5
$\begingroup$

Answer from the other SE site

The Church-Turing thesis is not in and of itself a rigorous concept, but rather a judgment on rigorous concepts of computability. As such, it's negotiable. The language in Rosser's 1939 expository paper about provability and computability is biased towards deterministic algorithms. There is an important simplifying theorem here: If you only care about what is ever computable, then you don't need randomness or quantum randomness, because you can simulate them using exponentially more time. Like many simplifying results, it can be taken in the wrong way. It meant that in the 1930s, back when mainly logicians were defining what was computable at all, randomized algorithms were not yet on their radar.

If you extend your thinking to the Extended Church-Turing thesis, then you should also extend your scope to randomized computation. You have no choice, because even if an algorithm answers a deterministic question (like whether a number is prime), the method of calculation could be randomized (like Miller-Rabin or ECPP). And then it's not very natural to demand that the answer be deterministic even if the solution doesn't have to be.

On the other hand, you're free to be a stickler in your personal interpretation of ECT, because it's not a rigorous concept. You're free to say that Google's quantum supremacy gets a bronze medal in its fight against ECT, but not a gold medal, because it doesn't answer a deterministic question.

Or you could be even more of a stickler and say that none of this counts because quantum computing isn't deterministic. Then I would say that I believe this reactionary version ECT after all --- a TM with a linear tape is polynomially equivalent to one with a 2D tape, etc. But I would also say that that's not the right question.

| cite | improve this answer | |
$\endgroup$

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