Hacker News Reader

"Soon we hope to falsify the strong Church-Turing thesis: we will perform computations which current computers cannot replicate. "

WTF, has Google gone completely insane? This is so wrong from every angle...

View on HN

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

As 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%93...

This is still a theoretical problem, not one solvable by building a faster computer

You'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).

Reply on news.ycombinator.com