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⊂ℝd, we show that estimating vol(K) to relative error ε takes Õ(d5/2+d3/2/ε) queries. This improves the previous quantum upper bound Õ(d3+d9/4/ε) 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 Õ(d7/2+d3/ε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 Ω(√d) lower bound.
Related
- Improved quantum volume estimation with transducers and amortized quantum walks
- Quantum lower bounds for convex optimization and real matrix-vector query problems
- Quantum Spectral Estimation with Multiple Initial States: Improved Error and Cost Scaling
- Improved Quantum Query Bounds for Boolean Matrix Product Verification
- Compiling the 2D Fermi-Hubbard ground-state energy estimation algorithm for active volume quantum architectures
BibTeX
@misc{zhang2026improved,
title = {{Improved Upper and Lower Bounds for Quantum Convex-Body Volume Estimation}},
author = {Ruizhe Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04987},
eprint = {2610.04987},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04987},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Improved Upper and Lower Bounds for Quantum Convex-Body Volume Estimation
AU - Ruizhe Zhang
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2610.04987
UR - https://arxiv.org/abs/2610.04987
AB - 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⊂ℝ^d, we show that estimating vol(K) to relative error ε takes Õ(d^5/2+d^3/2/ε) queries. This improves the previous quantum upper bound Õ(d^3+d^9/4/ε) 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 Õ(d^7/2+d^3/ε^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 Ω(√d) lower bound.
ER -