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 $Ω(d)$ quantum query lower bound for constant relative error, improving the previous $Ω(\sqrt d)$ lower bound.
Keywords
Subject
Publication details
- Journal
- Not available
- Open access
- Green open access
Cite this article
APA 7
Zhang, R. (2026). Improved Upper and Lower Bounds for Quantum Convex-Body Volume Estimation. https://omanscience.com/en/articles/improved-upper-and-lower-bounds-for-quantum-convex-body-volume-estimation
MLA 9
Zhang, Ruizhe. "Improved Upper and Lower Bounds for Quantum Convex-Body Volume Estimation." https://omanscience.com/en/articles/improved-upper-and-lower-bounds-for-quantum-convex-body-volume-estimation.
Chicago (author–date)
Zhang, Ruizhe. 2026. "Improved Upper and Lower Bounds for Quantum Convex-Body Volume Estimation." https://omanscience.com/en/articles/improved-upper-and-lower-bounds-for-quantum-convex-body-volume-estimation.
Harvard
Zhang, R. (2026) 'Improved Upper and Lower Bounds for Quantum Convex-Body Volume Estimation', Available at: https://omanscience.com/en/articles/improved-upper-and-lower-bounds-for-quantum-convex-body-volume-estimation.
Vancouver
Zhang R. Improved Upper and Lower Bounds for Quantum Convex-Body Volume Estimation. https://omanscience.com/en/articles/improved-upper-and-lower-bounds-for-quantum-convex-body-volume-estimation
IEEE
R. Zhang, "Improved Upper and Lower Bounds for Quantum Convex-Body Volume Estimation," https://omanscience.com/en/articles/improved-upper-and-lower-bounds-for-quantum-convex-body-volume-estimation.