undefined | Better HN

0 pointsbloomer7y ago0 comments

That's actually incorrect. Many people believe a quantum computer may be more powerful than a classical computer, but that is definitely not proven and plenty of people also believe that may not be true.

0 comments

dplavery927y ago

Well, for certain classes of problems, it is certainly proven that quantum algorithms are faster than classical algorithms. And they're not totally theoretical pie-in-the-sky; you can implement a 5- or 16-qubit version of Shor's algorithm in IBM Q Experience[0] and run it on a real, physical quantum computer. The growing pains are in implementing quantum computers that are large enough to be of practical importance, and then building those systems several-fold larger for Quantum Fault Tolerance.[1]

Quantum computers are never going to replace or speed up every aspect of classical computation, but the idea of accessing them as a service for certain types of computation is probably not many decades off.

[0] https://quantumexperience.ng.bluemix.net/proxy/tutorial/full...

[1] https://en.wikipedia.org/wiki/Quantum_error_correction

adrianN7y ago

There are quantum algorithms for certain problems that are exponentially faster than any known classical algorithm, and there are good reasons to believe that BQP is not contained in BPP, but we don't have proof of that yet as far as I know.

(Technically we still don't really know whether physics actually allows quantum computers with more than a few bits. Quantum mechanics says yes, but the universe can still veto.)

trhway7y ago

>it is certainly proven that quantum algorithms are faster than classical algorithms.

yes. What isn't proven is that actual implementation of quantum algorithms would be fast enough (i.e. while a given quantum algorithm may be order of magnitude faster using the number of steps/operations a the metric, may it happen that the runtime (using time as the metric) of those quantum steps may take order of magnitude longer ?). There is some indications that various corrections/etc. have to grow faster than linear with the number of qubits.

j / k navigate · click thread line to collapse