News for hackers. Stuff that matters.
Re:The Great Software Stagnation by tsimionescu on Saturday January 02, 2021 @09:27AM (#25613014)
Problems in the complexity class BQP are mathematically proven to be more efficient on a quantum computer than on a classical computer.

You can still doubt that quantum computers are physically realizable. Perhaps the number of qubits needed for error correction will turn out to increase fundamentally faster than the number of useful qubits, or perhaps there is some other fundamental limit that we will hit.

But the maths is clear: if it is at all possible to create a quantum computer, it will be faster for certain specific problems than a classical computer (in particular, it will be faster than a classical computer at simulating quantum phenomena).

Re:The Great Software Stagnation by pfdietz on Saturday January 02, 2021 @01:23PM (#25614986)
Since BQP is a subset of PSPACE, are you claiming that P != PSPACE has been proved?
Re:The Great Software Stagnation by tsimionescu on Saturday January 02, 2021 @02:14PM (#25615492)
Oops, you're right, I misspoke when I claimed this was proven. I mixed up BQP with the recent quantum superiority demonstration, apologies.

Still, it is strongly suspected that BQP != P. This was especially reinforced by the MIP* = RE result, as far as I understand from Scott Aaronson [0].

[0] https://www.scottaaronson.com/blog/?p=4512#comment-1829033

Re:The Great Software Stagnation by pfdietz on Saturday January 02, 2021 @02:20PM (#25615544)
I see your Scott Aaronson and raise you one Gil Kalai.

https://gilkalai.wordpress.com/2020/12/29/the-argument-again...