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.
AI Summary
The paper studies quantum query complexity for estimating the volume of a convex body $K\subset\mathbb R^d$ from a membership oracle queried in superposition. It asks whether advances on the KLS constant can improve quantum volume algorithms despite obstacles in translating warm-start mixing bounds into quantum-walk guarantees.
The algorithm estimates volume to relative error $\varepsilon$ with probability at least $2/3$ using $\widetilde O(d^{5/2}+d^{3/2}/\varepsilon)$ membership queries. The explicit dependence on the reciprocal Cheeger parameter is $\widetilde O((d^{5/2}+d^{3/2}/\varepsilon)/\psi_d)$. Previous reported quantum bounds were $\widetilde O(d^3+d^{9/4}/\varepsilon)$, although the paper identifies unresolved arguments affecting earlier rounding guarantees.
The construction combines stationary-state reflections derived from mixing uniformly over all $2$-warm starts, a fixed-lattice multiscale Metropolis walk, and coherent covariance preconditioning. The reflection analysis controls unresolved slow eigencomponents using an input fourth-moment bound. A separate product estimator combines bridge sampling with Hamiltonian phase accumulation, using $\widetilde O(m/\varepsilon)$ reflections for an $m$-stage annealing schedule and streaming access to qsamples. An $\Omega(d)$ lower bound, improving $\Omega(\sqrt d)$, follows from two Haar-induced ellipsoid distributions with separated volumes but identical low-degree membership moments.
The guarantees assume known concentric inner and outer balls with polynomial radius ratio and exact membership answers at arbitrary chosen finite precision. The speedups concern query complexity; gate complexity is polynomial but its exponent is not optimized. A polynomial gap remains between the upper and lower bounds.
Little sign of AI-generated textAI use disclosed
The author verified all AI-generated material before incorporating it into the manuscript and wrote the final proofs and text, with AI assistance for polishing and creating figures.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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⊂Rd, we show that estimating vol(K) to relative error ε takes O(d5/2+d3/2/ε) queries. This improves the previous quantum upper bound O(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 O(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.
The paper studies quantum query complexity for estimating the volume of a convex body K⊂Rd from a membership oracle queried in superposition. It asks whether advances on the KLS constant can improve quantum volume algorithms despite obstacles in translating warm-start mixing bounds into quantum-walk guarantees.
The algorithm estimates volume to relative error ε with probability at least 2/3 using O(d5/2+d3/2/ε) membership queries. The explicit dependence on the reciprocal Cheeger parameter is O((d5/2+d3/2/ε)/ψd). Previous reported quantum bounds were O(d3+d9/4/ε), although the paper identifies unresolved arguments affecting earlier rounding guarantees.
The construction combines stationary-state reflections derived from mixing uniformly over all 2-warm starts, a fixed-lattice multiscale Metropolis walk, and coherent covariance preconditioning. The reflection analysis controls unresolved slow eigencomponents using an input fourth-moment bound. A separate product estimator combines bridge sampling with Hamiltonian phase accumulation, using O(m/ε) reflections for an m-stage annealing schedule and streaming access to qsamples. An Ω(d) lower bound, improving Ω(d), follows from two Haar-induced ellipsoid distributions with separated volumes but identical low-degree membership moments.
The guarantees assume known concentric inner and outer balls with polynomial radius ratio and exact membership answers at arbitrary chosen finite precision. The speedups concern query complexity; gate complexity is polynomial but its exponent is not optimized. A polynomial gap remains between the upper and lower bounds.
Estimating the volume of a convex body is a central problem in convex geometry and can be viewed as a continuous version of counting. We present a quantum algorithm that estimates the volume of an n -dimensional convex body within multiplicative error ε using Õ(n 3 + n 2.5 /ε ) queries to a membership oracle and Õ(n 5 +n 4.5 /ε) additional arithmetic operations. For comparison, the best known classical algorithm uses Õ(n 3.5 +n 3 /ε 2 ) queries and Õ(n 5.5 +n 5 /ε 2 ) additional arithmetic operations. To the best of our knowledge, this is the first quantum speedup for volume estimation. Our algorithm is based on a refined framework for speeding up simulated annealing algorithms that might be of independent interest. This framework applies in the setting of “Chebyshev cooling,” where the solution is expressed as a telescoping product of ratios, each having bounded variance. We develop several novel techniques when implementing our framework, including a theory of continuous-space quantum walks with rigorous bounds on discretization error. To complement our quantum algorithms, we also prove that volume estimation requires Ω (√ n+1/ε) quantum membership queries, which rules out the possibility of exponential quantum speedup in n and shows optimality of our algorithm in 1/ε up to poly-logarithmic factors.
Estimating the volume of a convex body is a canonical problem in theoretical computer science. Its study has led to major advances in randomized algorithms, Markov chain theory, and computational geometry. In particular, determining the query complexity of volume estimation to a membership oracle has been a longstanding open question. Most of the previous work focuses on the high-dimensional limit. In this work, we tightly characterize the deterministic, randomized and quantum query complexity of this problem in the high-precision limit, i.e., when the dimension is constant.
We establish a linear quantum query lower bound for high-accuracy convex optimization over an explicit family of n-dimensional ellipsoids. We focus on linear optimization with an explicitly given objective, where the feasible set is accessed through a membership oracle. We show that any algorithm that, for every unit linear objective, returns an exactly feasible point with additive objective error Θ(n−1/2) requires Ω(n) membership queries, where the ellipsoids are contained in the unit ball. The same lower bound can be shown to hold if the returned point is only required to be approximately feasible, within Θ(n−3/2) distance from the feasible set. This resolves an open question posed by Chakrabarti, Childs, Li, and Wu~(\textit{Quantum}, 2020) and by van Apeldoorn, Gilyén, Gribling, and de Wolf~(\textit{Quantum}, 2020). Coupled with the upper bounds in these papers, the query complexity of high-accuracy convex optimization is characterized tightly up to logarithmic factors. The proof is built around a lower bound for determinant computation that is derived via a novel polynomial method based on Fourier-rank. In the continuous matrix phase-query model, computing the determinant of a real n×n matrix requires at least n/2 matrix-vector product queries. The construction also yields an Ω(n) phase-query lower bound for estimating the minimum eigenvalue of a real symmetric n×n matrix to additive accuracy Θ(n−2). These results extend the determinant and minimum-eigenvalue lower bounds of Childs, Hung, and Li~(ICALP 2021) from finite fields to the real-valued setting. Based on the same constructions, we also prove an Ω(min{κ,n}) gradient-query lower bound for constant-accuracy optimization of 1-strongly convex and κ-smooth functions, which is optimal up to a logarithmic factor.
Matrix scaling is a simple to state, yet widely applicable linear-algebraic problem: the goal is to scale the rows and columns of a given non-negative matrix such that the rescaled matrix has prescribed row and column sums. Motivated by recent results on first-order quantum algorithms for matrix scaling, we investigate the possibilities for quantum speedups for classical second-order algorithms, which comprise the state-of-the-art in the classical setting. We first show that there can be essentially no quantum speedup in terms of the input size in the high-precision regime: any quantum algorithm that solves the matrix scaling problem for n×n matrices with at most m non-zero entries and with ℓ2-error ε=Θ(1/m) must make Ω(m) queries to the matrix, even when the success probability is exponentially small in n. Additionally, we show that for ε∈[1/n,1/2], any quantum algorithm capable of producing 100ε-ℓ1-approximations of the row-sum vector of a (dense) normalized matrix uses Ω(n/ε) queries, and that there exists a constant ε0>0 for which this problem takes Ω(n1.5) queries. To complement these results we give improved quantum algorithms in the low-precision regime: with quantum graph sparsification and amplitude estimation, a box-constrained Newton method can be sped up in the large-ε regime, and outperforms previous quantum algorithms. For entrywise-positive matrices, we find an ε-ℓ1-scaling in time O(n1.5/ε2), whereas the best previously known bounds were O(n2polylog(1/ε)) (classical) and O(n1.5/ε3) (quantum).
Entropy estimation of discrete probability distributions is a fundamental problem in statistical inference and quantum property estimation. In this paper, we study the problem of estimating Rényi entropy Hα(p) for any distribution p=(pi)i=1n given its purified quantum query-access. For non-integer α>1, our algorithm estimates Hα(p) to within additive error ε using only O(nmax{1/2,1−1/α}/ε) queries, which improves the best known upper bound for dependence on both n and 1/ε. For 0<α<1, our algorithm has query complexity O(n1/(2α)/εmax{1,1/(2α)}), which improves the dependence on 1/ε of the current best upper bound without incresing its n dependence. Our approach adapts the multi-level estimation framework to relative approximation of the power sums and leverage binary search to remove the requirement of prior knowledge of them. We also strengthen the precision-dependent lower bound to Ω(1/εmax{1,1/(2α)}) for 0<α<1, which identifies the optimal precision dependence of our algorithm.
Given a convex function f:Rd→R, the problem of sampling from a distribution ∝e−f(x) is called log-concave sampling. This task has wide applications in machine learning, physics, statistics, etc. In this work, we develop quantum algorithms for sampling log-concave distributions and for estimating their normalizing constants ∫Rde−f(x)dx. First, we use underdamped Langevin diffusion to develop quantum algorithms that match the query complexity (in terms of the condition number κ and dimension d) of analogous classical algorithms that use gradient (first-order) queries, even though the quantum algorithms use only evaluation (zeroth-order) queries. For estimating normalizing constants, these algorithms also achieve quadratic speedup in the multiplicative error ε. Second, we develop quantum Metropolis-adjusted Langevin algorithms with query complexity O(κ1/2d) and O(κ1/2d3/2/ε) for log-concave sampling and normalizing constant estimation, respectively, achieving polynomial speedups in κ,d,ε over the best known classical algorithms by exploiting quantum analogs of the Monte Carlo method and quantum walks. We also prove a 1/ε1−o(1) quantum lower bound for estimating normalizing constants, implying near-optimality of our quantum algorithms in ε.