4
$\begingroup$

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?

Improve this question
$\endgroup$
3

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Thanks, this makes sense. Though, could you explain how sampling from a random quantum circuit classifies as a "function" (leaving aside the computability aspect)? $\endgroup$
    – Sanchayan Dutta
    Oct 30, 2019 at 21:55
  • 1
    $\begingroup$ Well, you can take it as a function that whose input is a quantum state and whose output is a classical state, i.e., a probability distribution on bit strings. $\endgroup$
    – Greg Kuperberg
    Oct 30, 2019 at 23:03
  • 1
    $\begingroup$ But another way to say it is that a traditional function in CS is a deterministic concept, exactly the old standard of producing a unique answer. $\endgroup$
    – Greg Kuperberg
    Oct 30, 2019 at 23:04
  • 2
    $\begingroup$ First of all, Rosser in Wikipedia clearly only discusses deterministic algorithms to compute deterministic answers. If you mean "in the CTT sense" for both the computation and the answer, then QC would simply not be relevant to CTT as either a violation or a non-violation. I certainly don't object to calling QC relevant to ECT (I would call it relevant), but that is already a departure from strict CTT. en.wikipedia.org/wiki/… $\endgroup$
    – Greg Kuperberg
    Oct 31, 2019 at 0:11
  • 1
    $\begingroup$ Second, I'm not trying to win a debate as much as to explain concepts. Say that you embrace QC as a test of ECT even though QC is not deterministic, but your standard is deterministic outputs. Then fine, Google's supremacy experiment does not meet that standard. But saying that Google's experiment is not relevant to ECT (not just that it doesn't yet contradict ECT) is different and just not true. If you allow non-deterministic algorithms to compute deterministic functions, then non-deterministic subroutines are clearly relevant. $\endgroup$
    – Greg Kuperberg
    Oct 31, 2019 at 0:17
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.