edited tags; edited tags
Link
glS
  • 16.7k
  • 4
  • 22
  • 71
added 22 characters in body
Source Link
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?

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, as the CT thesis requires?

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?

added 228 characters in body
Source Link
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?

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

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?

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, as the CT thesis requires?

added 3 characters in body
Source Link
Sanchayan Dutta
  • 15.5k
  • 5
  • 39
  • 91
Loading
added 109 characters in body
Source Link
Sanchayan Dutta
  • 15.5k
  • 5
  • 39
  • 91
Loading
Source Link
Sanchayan Dutta
  • 15.5k
  • 5
  • 39
  • 91
Loading