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

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.

In the framing of the question (which I believe to be asked in good faith), there seems to be at least two objections.

1. Sampling from a set of strings is not clearly a function, and

2. Sampling is a physical process, outside of computation.

---

Initially, with regard to the first objection, I assert that sampling is a function, as a search problem. For example, as noted by Ryan O'Donnell in comment #13, we can think of sampling as akin to searching for a set of strings that have an expected probability sufficiently $gt 1/2^n$ of being sampled.

To me this has a similar feel to the following:

• Given a set of strings ${0,1}^*$, suppose we wish to uniformly sample from the strings, with a probability, say, $p$. We can do this by searching for a set of strings such that a hash of the strings is $le p$ (for a hash with nice enough properties.)

---

With regard to the second objection, I assert that the process of sampling from a random quantum circuit, although a physical process, is not outside of computation.

For example, Martinis likes to relate sampling to speckle patterns - that is, to shining a light through fractured glass and determining where the peaks of coherent light may lie. This is clearly a "physical process." However, a difference between a quantum computer performing the task and a laser shown through glass is that the quantum computer is programmable to perform the said task, whereas the crushed glass does not.

That is, a quantum computer is able to prepare and sample from a state of someone's choosing. Although a physical process, I assert that it meets the definition of a computation.