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

Abstract: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{vol}(K)$ to relative error $\varepsilon$ takes $\widetilde O(d^{5/2}+d^{3/2}/\varepsilon)$ queries. This improves the previous quantum upper bound $\widetilde O(d^3+d^{9/4}/\varepsilon)$ 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 $\widetilde O(d^{7/2}+d^3/\varepsilon^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 $\Omega(d)$ quantum query lower bound for constant relative error, improving the previous $\Omega(\sqrt d)$ lower bound.

Quantum Physics (quant-ph); Computational Geometry (cs.CG); Data Structures and Algorithms (cs.DS)

arXiv:2610.04987 [quant-ph]

(or arXiv:2610.04987v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2610.04987 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.