edited tags; edited tags
glS
• 16.7k
• 4
• 22
• 71
Sanchayan Dutta
• 15.5k
• 5
• 39
• 91

Note: This has been cross-posted to CS Theory 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?

Sanchayan Dutta
• 15.5k
• 5
• 39
• 91

Note: This has been cross-posted to CS Theory SE.

If we assume $$\mathsf{BQP} \neq \mathsf{BPP}$$, then we can say with reasonable certaintyreasonable certainty that Google's random sampling experiment falsifies the Extended Church Turing thesis (cf. this). 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, as the CT thesis requires?

Sanchayan Dutta
• 15.5k
• 5
• 39
• 91