TIGHT QUANTUM BOUNDS FOR COMPUTATIONAL GEOMETRY PROBLEMS
We present new quantum lower bounds and upper bounds for several computational geometry problems. The bounds presented here improve on currently known results in a number of ways. We give asymptotically optimal bounds for one of the problems considered, and we provide, up to logarithmic factors, optimal bounds for a number of other problems and, in particular, we settle an open problem of Bahadur et al. Some of these new bounds are obtained using a general algorithm for finding a minimum pair over a given arbitrary order relation.
computational geometry lower bound upper bound quantum computing quantum algorithm