“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, tha

“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.