News for hackers. Stuff that matters.
Re:Quantum A.I. Publications by deepnotderp on Monday November 27, 2017 @01:17AM (#15785258)
"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...

Re:Quantum A.I. Publications by LolWolf on Monday November 27, 2017 @02:19AM (#15785461)
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

Re:Quantum A.I. Publications by klmr on Monday November 27, 2017 @06:40AM (#15786613)
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...

Re:Quantum A.I. Publications by jooke on Monday November 27, 2017 @04:36AM (#15786033)
This is still a theoretical problem, not one solvable by building a faster computer
Re:Quantum A.I. Publications by LolWolf on Monday November 27, 2017 @11:58AM (#15788776)
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).