6 ms·

"Soon we hope to falsify the strong Church-Turing thesis: we will perform computations which current computers cannot replicate." Yeah, no. This is a ridiculou

"Soon we hope to falsify the strong Church-Turing thesis: we will perform computations which current computers cannot replicate." Yeah, no. This is a ridiculous statement and it is embarrassing to hear it from Google. Quantum computers are not hyper-Turing machines, and there is no reason to suspect they ever will be.

sobellian 9y ago
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?
- petters 9y ago
  No, just that some problems are believed to require superpolynomial slowdown.
  - sobellian 9y ago
    Correct me if I'm wrong but isn't BQP ?= BPP considered a separate problem from the strong church turing thesis?
    - petters 9y ago
      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.)
      - deleted 9y ago
        [deleted]
    - chubot 9y ago
      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 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!
      - nightsd01 9y ago
        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.
      - sobellian 9y ago
        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.
        chubot 9y ago
        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.
        daxfohl 9y ago
        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....)
      - Udik 9y ago
        > 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.
    - LolWolf 9y ago
      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.
    - urgoroger 9y ago
      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.
      - deleted 9y ago
        [deleted]
adamnemecek 9y ago
Why not?
urgoroger 9y ago
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/ 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.
- Udik 9y ago
  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."
  - Aardwolf 9y ago
    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 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.
mtgx 9y ago
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.
mathgenius 9y ago
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.
- klmr 9y ago
  > 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.
  - mathgenius 9y ago
    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.
- h2j24 9y ago
  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.

sobellian 9y ago

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?

petters 9y ago
No, just that some problems are believed to require superpolynomial slowdown.
- sobellian 9y ago
  Correct me if I'm wrong but isn't BQP ?= BPP considered a separate problem from the strong church turing thesis?
  - petters 9y ago
    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.)
    - deleted 9y ago
      [deleted]
  - chubot 9y ago
    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 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!
    - nightsd01 9y ago
      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.
    - sobellian 9y ago
      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.
      - chubot 9y ago
        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.
      - daxfohl 9y ago
        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....)
    - Udik 9y ago
      > 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.
  - LolWolf 9y ago
    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.
  - urgoroger 9y ago
    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.
    - deleted 9y ago
      [deleted]

adamnemecek 9y ago

Why not?

urgoroger 9y ago

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

Udik 9y ago
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."
- Aardwolf 9y ago
  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 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.

mtgx 9y ago

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.

mathgenius 9y ago

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.

klmr 9y ago
> 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.
- mathgenius 9y ago
  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.
h2j24 9y ago
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.