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\subset {\mathbb{R}}^d$, we show that estimating $\mathrm{v}\mathrm{o}\mathrm{l}(K)$ to relative error $\epsilon$ takes $\tilde{O}(d^{5\mathrm{/}2}+d^{3\mathrm{/}2}\mathrm{/}\epsilon )$ queries. This improves the previous quantum upper bound $\tilde{O}(d^3+d^{9\mathrm{/}4}\mathrm{/}\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 $\tilde{O}(d^{7\mathrm{/}2}+d^3\mathrm{/}{\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 $\mathrm{\Omega }(d)$ quantum query lower bound for constant relative error, improving the previous $\mathrm{\Omega }(\sqrt{d})$ lower bound.