Quantum Query Complexity in Computational Geometry

Akinori Kawachi

亮周 河内

Parijat Prashun Purohit

Abhinav Bahadur, Christoph Dürr, Thibault Lafaye +1 more

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. Bounded error quantum algorithms can actually have sublinear running time.

Sebastian Dörn, Thomas Thierauf

Arjan Cornelissen, Simon Apers, Sander Gribling

Estimating the volume of a convex body is a canonical problem in theoretical computer science. Its study has led to major advances in randomized algorithms, Markov chain theory, and computational geometry. In particular, determining the query complexity of volume estimation to a membership oracle has been a longstanding open question. Most of the previous work focuses on the high-dimensional limit. In this work, we tightly characterize the deterministic, randomized and quantum query complexity of this problem in the high-precision limit, i.e., when the dimension is constant.