Improved Upper and Lower Bounds for Quantum Convex-Body Volume EstimationResearch Paper
Computing the volume of a convex body is a basic problem of algorithmic convex geometry. In the membership-oracle model every deterministic algorithm with polynomially many queries can only approximate the volume within a factor exponential in (Bárány–Füredi 1987), while randomized algorithms achieve any relative accuracy with polynomially many queries…