3 ms·

From a computational complexity standpoint, it's not even clear if quantum computing is actually faster. The discrete log problem and integer factoring problem

From a computational complexity standpoint, it's not even clear if quantum computing is actually faster. The discrete log problem and integer factoring problem aren't known to be NP-complete, so even assuming P != NP it's possible there are polynomial time algorithms for factoring and discrete log on classical computers as well. BQP vs. P is still, IIRC, unresolved. Though, from a practical standpoint, I have a feeling that, regardless of how the computational classes shake out, the quantum Fourier transform will prove to be faster than classical techniques. And possibly Grover's algorithm, though its results are somewhat less dramatic.

Robotbeat 9y ago
We are certain that quantum computing is much faster for simulating quantum phenomenon. And while it is difficult to show that quantum computing is faster for even some classical computations, it can be shown. Here's a skeptical eye on quantum algorithms: "Read the Fine Print" by Scott Aaronson: https://www.nature.com/articles/nphys3272 https://www.nature.com/articles/nphys3272 PDF: https://pdfs.semanticscholar.org/dfe4/d76e3fc27304a984a5daf1be530401724c25.pdf https://pdfs.semanticscholar.org/dfe4/d76e3fc27304a984a5daf1...