You'd think the title of this post is a joke paper title, but it actually isn't. There are now at least two papers (the second one even uses the word 'revisited' in the title!) on quantum algorithms for geometric problems.
Neither paper (and they basically admit this themselves) really pushes the envelope in the QC dimension. The first one, by Sadakane, Sugawara and Tokuyama, uses Grover's quantum search algorithm as a subroutine to solve a number of search problems in geometry, many of these reduced to the problem of finding the lowest point in the upper envelope of an arrangement of halfplanes. The second, by Bahadur, Durr, Lafaye and Kulkarni, uses a quantum algorithm for element distinctness based on a random walk method by Ambainis to solve some of the above problems. They also show lower bounds for some of these problems. One interesting result is an n^{2/3} lower bound, and nlog n upper bound (!) for 3SUM.
I'm not sure what to make of these results: apart from the fact that I have a hard time seeing a need for quantum algorithms for geometric problems, I don't know whether these are anything more than (insert model of computation) algorithm for (insert name of problem) type results (not that such results are bad, but they are not always interesting).
I don't know whether these are anything more than (insert model of computation) algorithm for (insert name of problem) type results.
ReplyDeleteSo, what if the model of computation = NC_k? I think Parallel geometric algorithms are not only interesting but even interesting!
I think Parallel geometric algorithms are not only interesting but even interesting!
ReplyDeleteBeen there, done that.