arXiv preprint ·
Improved Upper and Lower Bounds for Quantum Convex-Body Volume Estimation
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
Rubix: Global Correspondence-Free Point Set Alignment through Assignment Geometry
Min-Max Uniform Circle Formation by Asynchronous Mobile Robots
Deterministic Distance Selection in $O(n^{4/3})$ Time
Locality Sensitive Hashing for p-Exponential Kernels with Applications to Density Estimation
Peeling Half the Onion: Embedding $k$-Outerplanar Graphs into $\ell_1$ and Trees with a Polynomial Distortion (in $k$)
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.