Improved Upper and Lower Bounds for Quantum Convex-Body Volume Estimation

Estimating the volume of a high-dimensional convex body is a fundamental problem in theoretical computer science. Given a quantum membership oracle for a convex body K R d, we show that estimating vol(K) to relative error epsilon takes O(d 5/2+d 3/2/epsilon) queries. This improves the previous quantum upper bound O(d 3+d 9/4/epsilon) of Chakrabarti et al. (ACM TQC 2023) and Cornelissen--Hamoudi (SODA 2023), and achieves a larger quantum speedup over the currently best classical upper bound O(d 7/2+d 3/epsilon 2) of Jia et al. (JACM 2026). Our quantum algorithm combines two new ingredients: an input-dependent effective spectral-gap analysis of quantum walks based on uniform classical warm-start mixing bounds, and a single quantum estimator for products of normalizer ratios in simulated annealing based on classical bridge sampling. We also prove an Ω(d) quantum query lower bound for constant relative error, improving the previous Ω(sqrt d) lower bound.