# How exactly is solving the random circuit sampling problem a computation in the Church-Turing thesis sense? [closed]

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?

• "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. Oct 31, 2019 at 0:22
• Please do not post the same question on multiple sites simultaneously.
– D.W.
Oct 31, 2019 at 0:28
• Even though I answered the question here, I think that per policy the whole question should be deleted. Oct 31, 2019 at 16:16
• @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. Oct 31, 2019 at 16:20
• Okay, I guess I don't feel strongly about it. Nov 1, 2019 at 16:02