How significant are the variants of Grover's Algorithm?

Question

I found a paper by Grover titled "How significant are the known collision and element distinctness quantum algorithms?", in which he expressed criticism to several famous algorithms, including Ambainis's algorithm for element distinctness. More precisely, he argues that all those algorithms use too much space, and there is a trivial way to obtain the same speedup(using same amount of memory) by separating the search space into several parts and search them on independent processors simultaneously. It seems Ambainis admitted this in another article.

My questions are:

1.Is Grover correct about those algorithms? That is, are they "trivial" in Grover's sense?

2.Have there been new algorithms obtaining the same speedup and using less space since then?

Answer 1

1. Grover focuses on gate costs, while Ambainis focuses on queries. Ambainis solves element distinctness in $O(N^{2/3})$ queries, using $O(N^{2/3})$ memory. If you used that memory to run $O(N^{2/3})$ copies of Grover's algorithm (since each copy needs poly-log space, and I'm being imprecise about logarithmic factors) then each one would search a space of size $N^2/N^{2/3}=N^{4/3}$, and with the square-root speed up, would take time $O(N^{2/3})$. But, each copy is making simultaneous queries, so parallel Grover makes $O(N^{4/3})$ queries in total. So in query complexity, it's not a trivial result.

   Is query complexity a good measure? It depends on your model of computation, and in this case: Do you have a quantum random access gate? If you only have Clifford+T gates (or any other finite set with bounded fanin) then quantum random memory access to $M$ elements needs $\Omega(M)$ gates. This is because the gates you use cannot be "dynamically generated" by the input, which is quantum. When I think about this, I always envision a classical control computer that applies gates somehow. The classical control cannot measure the input (which is quantum) so it must apply the necessary gates for any possible memory access. If you had given a superposition of addresses for the memory access, then it would definitely need to apply all the gates!

   Ambainis explicitly adds a random access gate to the usual gate set. Once he does this, the query complexity he derives will be roughly equal to the total gate cost. If you don't add a random access gate, and you need to "build" one out of Clifford+T, then a single memory access would use $O(N^{2/3})$ gates itself. Then Ambainis' algorithm will end up with an $O(N^{4/3})$ total gate cost - the same as Grover's algorithm (up to poly-log factors).

2. For other algorithms, I've looked a lot (this is the subject of my master's thesis, essentially) and I haven't seen much. The algorithms at the end of "Efficient Distributed Quantum Computing" do slightly better, though they focus on depth, not gate cost, and they rely on hypercube connectivity in their qubits.