3 ms·
See the above thread given in [0]. It sounds weird, but they are talking about the strong CT thesis (e.g. that all realizable models are polynomial-time-reducib
by LolWolf 9y ago
See the above thread given in [0]. It sounds weird, but they are talking about the strong CT thesis (e.g. that all realizable models are polynomial-time-reducible to BPP), not just the usual one (that no realizable model can solve halting-hard problems).
---
[0] https://news.ycombinator.com/item?id=15785215 https://news.ycombinator.com/item?id=15785215
- jooke 9y agoThis is still a theoretical problem, not one solvable by building a faster computer
- LolWolf 9y agoYou're right that part of the problem is, indeed, theoretical (it remains to be shown that BPP ≠ BQP, even if it is widely believed to be true), but part of the problem is also physical (we need to build a model of BQP---i.e. a quantum computer---to show that there is a physically realizable model of it).
- klmr 9y agoAs alluded to above, “Strong CT” confusingly refers to several very similar, yet different, concepts. I think this is throwing people off. Quantum computers will almost certainly not disprove the CTD principle [1], which is also known as “Strong CT”. [1] https://en.wikipedia.org/wiki/Church%E2%80%93Turing%E2%80%93Deutsch_principle https://en.wikipedia.org/wiki/Church%E2%80%93Turing%E2%80%93...