Quantum query complexity in computational geometry revisited

摘要

We are interested in finding quantum algorithms for problems in the area of computation geometry. Many of the problems we study have already polynomial time algorithms. But since in this area the input sizes are huge, quadratic time algorithms are often not good enough. Bounded error quantum algorithms can actually have sublinear running time. To our knowledge there have been two works on the subject. One is by K. Sadakane, N. Sugawara, T. Tokuyama and the other by W. Smith. These papers do not contain lower bounds. The main quantum ingredient in their algorithms is a quantum algorithm for the Element Distinctness problem based on Grover's quantum search algorithm. We revisit the problems using the recent quantum algorithm for Element Distinctness based on a quantum walk. We also show new lower bounds and study new problems, in particular problems on polygons and the 3-Sum problem.