5 ms·

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]

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]