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 probabil

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#Variations 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-generators https://mathoverflow.net/questions/2272/pseudorandom-generat...). That is, we do not know if P ≠ BPP.