Sorry I am just curious.. does this have implication to separation between randomized and quantum QUERY complexities as well?

]]>For total functions, quadratic, from the disjointness problem, a sort of “distributed” version of Grover search (Buhrman-Cleve-Wigderson 1998, Razborov 2002, a log factor removed by de Wolf and then by me and Ambainis).

]]>For communication complexity (e.g., getting better separations between randomized and quantum communication complexities for total Boolean functions than are currently known), *very* possibly yes. I know people who are working on it right now.

Speaking of “waiting for scientists imagination to catch up”, check out the following and be prepared to say: “Why didn’t I think of this”:

]]>- This seems like one of those rare cases where all the mathematical machinery has been there for some time, and the scientists’ imagination had to catch up.

Such cases are not particularly rare!

Bell’s Theorem is a slightly different case, where it took 30 years for anyone even to *pose the question* with any mathematical precision—but once they did, the answer was just simple arithmetic. Here, the questions were posed in the 1990s, but it took until now for anyone to have the right idea about what the answers would look like.

- And it makes one think what other “obvious in retrospect” discoveries are just waiting to be revealed.

If you find any, let us know! 😀

]]>