Prof Aaronson said the best upper bound they have so far is O(log(n)^33)... to give that more meaning, O(log(n)^33) grows faster than O(n) until about n = 10^15, so "not practical" is a bit of an understatement!

I still get why this is an interesting result, though. And if Scott thinks that lower bounds are achievable he is probably right.