4 ms·

Not sure if you’re being serious, but there are already quantum algorithms that have been mathematically proven to not be dequantizable, i.e. have no possible c

• Ar-Curunir 8y ago
  What's your definition of "as fast"? We can't separate BQP from P right now. That is, we don't know any problems that run in polynomial time on a quantum computer, but provably have no polynomial time classical algorithms.
  • qzw 8y ago
    “As fast” in the big-O sense. Here’s what Scott Aaronson says in reply to one of the comments on his blogpost about this paper: I should point out, though, that in many cases (Simon’s problem, period-finding, Forrelation, quantum walk on glued trees…), people have proved exponential separations between the quantum and randomized query complexities, which means that there certainly won’t be a dequantization in those cases along the same lines as what Ewin did.
• guelo 8y ago
  But nobody can figure out anything useful that those algorithms would be good for.
  • qzw 8y ago
    For literally centuries, people thought that number theory had no practical applications. Same for a number of other fields of mathematics. Is quantum computing somewhat overhyped at this moment in history? Undoubtedly (but way less so than block chains, I would argue). But that doesn’t mean it won’t ever become practically useful.