3 ms·
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 comput
by 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.