<p><strong>Answer from the other SE site</strong></p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 4.0
2019-10-30T21:52:53.237Z
2019-10-30T21:52:53.237Z
Greg Kuperberg
<p><strong>Note</strong>: <em>This has been cross-posted to <a href="https://quantumcomputing.stackexchange.com/questions/8620/how-exactly-is-solving-the-random-circuit-sampling-problem-a-computation-in-the">Quantum Computing SE</a></em>.</p>

<p>If we assume <span class="math-container">$\mathsf{BQP} \neq \mathsf{BPP}$</span>, then we can say with <a href="https://quantumcomputing.stackexchange.com/a/8621/26">reasonable certainty</a> that Google's random sampling experiment falsifies the Extended Church Turing thesis. However, in a <a href="https://quantumcomputing.stackexchange.com/a/8560/26">related thread</a>, a user raised the objection that the random circuit sampling problem might not be a computation in the <a href="https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis#Statement_in_Church&#39;s_and_Turing&#39;s_words" rel="nofollow noreferrer">Church Turing sense</a>:</p>

<blockquote>
  <p>@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.</p>
</blockquote>

<p>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?</p>

CC BY-SA 4.0
2019-10-31T00:22:16.363Z
"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.
Huck Bennett
CC BY-SA 4.0
2019-10-31T00:28:59.883Z
Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068) simultaneously.
D.W.
CC BY-SA 4.0
2019-10-31T16:16:58.410Z
Even though I answered the question here, I think that per policy the whole question should be deleted.
Greg Kuperberg
CC BY-SA 4.0
2019-10-31T16:20:58.720Z
@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.
Sanchayan Dutta
CC BY-SA 4.0
2019-11-01T16:02:13.220Z
Okay, I guess I don't feel strongly about it.
Greg Kuperberg
<cc.complexity-theory><quantum-computing><church-turing-thesis>
How exactly is solving the random circuit sampling problem a computation in the Church-Turing thesis sense?
Sanchayan Dutta
# How exactly is solving the random circuit sampling problem a computation in the Church-Turing thesis sense?

(Asked by: username_0 on 2019-10-30)

**Note**: *This has been cross-posted to [Quantum Computing SE](https://quantumcomputing.stackexchange.com/questions/8620/how-exactly-is-solving-the-random-circuit-sampling-problem-a-computation-in-the)*.

If we assume $\mathsf{BQP} \neq \mathsf{BPP}$, then we can say with [reasonable certainty](https://quantumcomputing.stackexchange.com/a/8621/26) that Google's random sampling experiment falsifies the Extended Church Turing thesis. However, in a [related thread](https://quantumcomputing.stackexchange.com/a/8560/26), a user raised the objection that the random circuit sampling problem might not be a computation in the [Church Turing sense](https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis#Statement_in_Church's_and_Turing's_words):

> @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?

**Tags:** cc.complexity-theory, quantum-computing, church-turing-thesis

> **Comments:**
> **username_1**: "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.  
> **username_2**: Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068) simultaneously.  
> **username_3**: Even though I answered the question here, I think that per policy the whole question should be deleted.  
> **username_0**: @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.  
> **username_3**: Okay, I guess I don't feel strongly about it.  

---

## 1 answers

### Answer by username_3 on 2019-10-30. Score: 5 | Accepted answer

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


---

