5 ms·
Conjecture: for every quantum algorithm that is faster than current classical algorithm exists yet undiscovered classical algorithm that is equally fast.
by dvh 8y ago
Conjecture: for every quantum algorithm that is faster than current classical algorithm exists yet undiscovered classical algorithm that is equally fast.
- qzw 8y agoNot 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 classical version that's as fast.
- Ar-Curunir 8y agoWhat'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 agoBut nobody can figure out anything useful that those algorithms would be good for.
- qzw 8y agoFor 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.
- Ar-Curunir 8y agoThe technical equivalent of this is that BQP = P. However, we have some evidence that this might be the case, namely Raz and Tal's recent oracle separation of BQP and the polynomial hierarchy
- Ar-Curunir 8y agoOops, that should say "might not be the case...", ie,, that BQP != P