4 ms·
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 tha
by tsimionescu 6y ago
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).
- pfdietz 6y agoSince BQP is a subset of PSPACE, are you claiming that P != PSPACE has been proved?
- tsimionescu 6y agoOops, 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 https://www.scottaaronson.com/blog/?p=4512#comment-1829033
- pfdietz 6y agoI see your Scott Aaronson and raise you one Gil Kalai. https://gilkalai.wordpress.com/2020/12/29/the-argument-against-quantum-computers-a-very-short-introduction/ https://gilkalai.wordpress.com/2020/12/29/the-argument-again...