While it is true that compatibility should remain intact, this comment seems to misunderstand what the STRONG Church-Turing thesis purports (EDIT: at least the one Google is probably referring to). I'm not sure if it's completely agreed upon, but the strong Church-Turing thesis that I am familiar with is: "Every realistic model of computation is polynomial time reducible to probabilistic Turing machines" (https://arbital.com/p/strong_Church_Turing_thesis/) "A probabilistic Turing machine can efficiently simulate any realistic model of computation" (An Introduction to Quantum Computing, Phillip Kaye, Raymond Laflamme, Michele Mosca)

In other words, the efficiency of every realized model of computation needs to be similar to that of a Turing machine for the thesis to hold. As soon as machines capable of quantum computation are realized, the thesis is broken, as they give superpolynomial speedup over classical Turing machines (assuming things like integer factorization are not in P).

EDIT: I guess it should be noted that there are probably other 'strong Church-Turing theses' hanging around, but I'm fairly certain the folks at Google are referring to this one, which I too am most familiar with. If OP is referring to one which does not require similar efficiency, then the quotation does seem kind of ridiculous. I also agree that the part of the quote that says "current computers cannot replicate" needs to be interpreted with some notion of efficiency as well.

From watching a couple of Scott Aaronson videos, I was under the understanding that Grover's algorithm shows that you don't get an exponential speedup over classical Turing machines from quantum computation in general, but only for specific problems that exhibit structure such as integer factorization à la Shor's algorithm. Here's a quotation from Lecture 10 of his Quantum Computing series [1]:

"So the bottom line is that, for "generic" or "unstructured" search problems, quantum computers can give some speedup over classical computers -- specifically, a quadratic speedup -- but nothing like the exponential speedup of Shor's factoring algorithm."

[1] https://www.scottaaronson.com/democritus/lec10.html

Right. But even having some individual problem that gives an exponential speedup will break the hypothesis.

According to Wikipedia:

"the [Church-Turing] thesis has several possible meanings:

1) The universe is equivalent to a Turing machine; thus, computing non-recursive functions is physically impossible. This has been termed the Strong Church–Turing thesis, or Church–Turing–Deutsch principle, and is a foundation of digital physics."

What is meant by "non-recursive functions" here?

From my knowledge a non-recursive function would be easier than a recursive one, since a non-recursive one will not call itself while a recursive one can. But the quoted phrase seems to imply it must be something more difficult instead...

Problem is, wikipedia's page https://en.wikipedia.org/wiki/Non-recursive_function does not define it either, it just redirects you to the recursion page (though not recursively, so wikipedia did not go for the joke) which does not define it either.

Non-recursive in this context means functions that aren’t computationally equivalent to those computable by recursive functions only [1]. This is equivalent to Turing completeness. It’s the second & third meaning in your link.

A “non-recursive function” would be more powerful than that; or, conversely, it would be a function which cannot be computed using a Turing machine. Alternatively, these are also know as super-recursive functions [2].

[1] https://en.wikipedia.org/wiki/Computable_function [2] https://en.wikipedia.org/wiki/Super-recursive_algorithm

Thanks for the explanation! Neither of the two linked articles mention the term "non-recursive" by the way, so it's thanks to your response I know it's a synonym of super-recursive, not thanks to wikipedia.

I too was skeptical. Is there any computation that a quantum computer can perform which cannot be simulated by a classical computer with an RNG?

No, just that some problems are believed to require superpolynomial slowdown.

Correct me if I'm wrong but isn't BQP ?= BPP considered a separate problem from the strong church turing thesis?

In this case the "strong Church-Turing thesis" (usually also known as the "extended Church-Turing thesis"[0]) is usually written as the following:

> A probabilistic TM can efficiently[1] simulate any realistic model of computation.

Taken from [0].

Note that this statement is actually false if two things are true: (a) BPP ≠ BQP (this is unknown, at the moment; we don't even know if BPP ≠ P, but it's not difficult to show that P ⊆ BPP ⊆ BQP) and (b) that BQP is physically realizable (e.g. we can actually make physical quantum computers)---both statements are, overall, what Google is claiming.

Why? Because (b) would mean that there is a realistic model of computation which models BQP and (a) would mean that there is at least one problem in BQP which is not polynomially reducible to a problem in BPP; therefore it follows that a probabilistic TM (which models BPP, by definition) cannot efficiently simulate the particular model of computation given by a model of BQP (i.e. a quantum computer).

On the other hand, if we find that BPP = BQP (which is widely believed to not be true) then we're back to square one and the strong Church-Turing thesis would still hold.

---

[0] https://en.wikipedia.org/wiki/Church–Turing_thesis#Variation...

[1] "Efficiently" here means that any model is polynomial-time reducible to a standard model of probabilistic computing.

Additionally, the "probabilistic" aspect comes from the "fact" (i.e. observation) that we can make "good" random number generators in real life (say, by measuring background radiation), but it's unclear if there exist pseudo RNGs that are "good enough," algorithmically, to derandomize BPP. That is, such that BPP = P (the claim of "good enough" PRNGs is stronger than BPP = P, in fact, see https://mathoverflow.net/questions/2272/pseudorandom-generat...).

That is, we do not know if P ≠ BPP.

There are a two cases: BQP contains something BPP doesn't: Then the thesis is false as long as we can realize a quantum computer, as then there exists something which can be solved in polynomial time (with bounded error) on a machine in the universe which cannot be done on a classic Turing machine as efficiently.

BQP is a subset of BPP (equal or ~~strict~~): Then the state of the thesis is unknown. There is still some chance that is is false, either by a superpolyomial speedup somewhere higher up the hierarchy (not too sure about this one, my complexity theory is not sharp enough to rule out that this is impossible given BQP is a subset of BPP), or that there exists another realizable model of computation other than quantum computing that beats the randomized turing machine.

EDIT: It appears that BPP (trivially) a subset of BQP, so that the strict inclusion of BQP in BPP is impossible, though BQP = BPP is possible.

It is certainly a separate problem. Just as the original comment says: I don't think anyone seriously argues that quantum computers will violate the CT thesis.

(Except Penrose, perhaps.)

I think it has to be. The former problem is about computational complexity; the latter is about computability.

I don't know much about this topic -- I skimmed through Scott Aaronson's "Quantum Computing and Democritus", and got lost by the last third. As far as I remember, it was all about computational complexity. I don't recall anything about computability, but correct me if I'm wrong.

I just had to look up the strong Church-Turing Thesis:

The universe is equivalent to a Turing machine; thus, computing non-recursive functions is physically impossible. This has been termed the Strong Church–Turing thesis, or Church–Turing–Deutsch principle, and is a foundation of digital physics.

https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis

I don't have much justification, but I believe it's false. There is a lot more to the universe than computers. Computers cannot simulate even elementary physical systems accurately.

Doesn't it take supercomputers to even accurately simulate even a few atoms?

I think the biggest cultural "lie" in the last couple decades is "the Matrix". Since that movie, educated people including software engineers take for granted the fact that the universe can be simulated by computers.

They write silly papers like "we are almost certainly living in a simulation". Granted, that argument is sound if you believe it's even possible to simulate the universe with a computer.

But I actually take that as further evidence that it's NOT possible to simulate the universe with a computer.

Anyway, I haven't thought about these things in a long time, but I would say that just because something is impossible on a Turing machine doesn't mean it's impossible in the universe!

> I don't have much justification, but I believe it's false. There is a lot more to the universe than computers. Computers cannot simulate even elementary physical systems accurately.

Correct me if I'm wrong, but wouldn't a system that computes a non-recursive function be some sort of box where, given the same inputs, you invariably obtain the same outputs; however there is no way of finding any mathematical or algorithmic expression that could, in any finite amount of time, predict the same result? To find yourself in that situation, you need a physical process that is intrinsically non-computable; being unable to compute the sum of computable processes is not enough.

A problem that I see in simulating the universe (i.e. the sum of computable processes) is that in quantum mechanics, you can't simply isolate yourself from the system under scrutiny. I.e. to compute and predict the state of the universe a computer would have to take into account its own internal present and future state which was the aim to compute in the first place.

You can simulate a lot of atoms with a modern supercomputer. The only problem is just how many atoms there are even in a tiny grain of sand. However that doesn’t mean all hope is lost. You just have to get really clever - there is a lot of repeating patterns in a grain of sand - you don’t really need to simulate all or even most of it. The same holds true for most structures.

Wouldn't an incomputable physical process have serious implications beyond CS? How would a physicist even model such a thing?

edit: I guess not, since all you need is access to the real numbers which is a strict superset of computable numbers, but this doesn't seem like an "interesting" violation of the SCT.

What makes you think physics can model everything? That's the point.

Math is FULL of functions that can be described -- have properties X and Y, which are useful to prove theorems -- which nobody has thought about how to compute.

(Obviously, there are the ones related to incomputibility like the Godel function, but there are others too... I'd appreciate help from others here :) )

And it might not even be useful or interesting (for the purposes of mathematics) to compute them. Not all math is constructive.

Likewise you can describe physical processes without computing them.

If SCT is false then for example it may be possible for a quantum computer to use an uncountable set of inputs to compute in finite time whether an arbitrary turing machine will end.

That said, you're right, if all that is required is real numbers, then hypothetically an analog computer is all that would be required. But in a truly quantum world where SCT holds, an "analog" computer is only a computable approximation.

(Full disclosure: I guess....)

Quantum computers (assuming we can build one) can access computational resources far beyond what classical computers can do: imagine a classical computer so big and hot that it collapses down into a black-hole. Or it takes so long to run the computation (eg. a classical computer the size of the solar system) that heat-death of the entire universe comes first. These are the physical limitations of classical computation, and a quantum computer will (if we can build one) surpass this.

> These are the physical limitations of classical computation

Classical computation (i.e. the Turing machine) is a mathematical model, and isn’t bound by the physical limitations you imagine. In particular, a Turing machine (which, after all, requires an infinite tape) is already not physically possible.

From the OP: "computations which current computers cannot replicate." I was just explaining a bit more why this is so.

If it matters at all, I've just finished a PhD in quantum computing.

I don't think that's really true. The difference between a quantum computer and a classical computer is that a classical computer can represent N states given N bits, whereas a quantum computer can represent 2^N states given N q-bits. However, this has a major caveat: you can never know the state of the system. You only get to measure one value at a time and you can never re-create or copy a previously obtained state.

Still, some clever people have figured out how to exploit this to achieve polynomial speedup on problems where certain properties of the problem are exploited to get around the limitation of measurement in a quantum system.

Whenever I hear that "quantum computers will forever be specialized processors" I think that at how we must've thought about the very first computers, which were only really good at doing math calculations. Even GPUs have gotten way more general-purpose than what we thought they could achieve even 2 decades ago.

I think that if quantum computers become mainstream enough we'll find ways to use them for more general-purpose stuff.

Why not?