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.
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.
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.
We (the author and the AI systems that did the heavy lifting) show that the quantum query complexity of minimizing a convex function over a convex subset of Rn with evaluation and membership queries is Ω~(n), nearly matching the best known upper bound. In particular, we show this even for quadratic minimization, which is equivalent to inverting an n×n real matrix using matrix-vector queries. We also show linear or nearly linear lower bounds on the quantum query complexity of computing the trace, the sign of the determinant, and the magnitude of the determinant of a real matrix in the matrix-vector query model. We use a novel quantum lower bound technique, the determinantal witness method, based on identifying a witness whose Fourier transform vanishes on low-rank matrices and that correlates well with the function being computed.
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 statistical properties of probability distributions is a fundamental problem in statistics and theoretical computer science. We develop quantum algorithms for estimating the q-Tsallis entropy HqTsa(P)=1−q∑i=1npiq−1 when 0<q<1, given purified quantum query access to a distribution P on [n]. When 0<q≤21, we provide a quantum algorithm with query complexity $\widetilde{O}\rbra{\left(\frac{n}{\varepsilon}\right)^{\frac{1}{2q}}}$, which is optimal up to polylogarithmic factors. When 21<q<1, we introduce a two-stage simultaneous probability estimation procedure, yielding a quantum algorithm with query complexity O(ε2q1n21+2q1+εn1−q), which improves the result given by Chen et al. (ICALP 2026) when $\varepsilon=O\rbra{n^{1-2q}}$.
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.
We consider the problem of estimating the expected outcomes of Monte Carlo processes whose outputs are described by multidimensional random variables. We tightly characterize the quantum query complexity of this problem for various choices of oracle access to the Monte Carlo process and various normalization conditions on its output variables and the estimates to be made. More specifically, we design quantum algorithms that provide a quadratic speed-up in query complexity with respect to the precision of the resulting estimates and show that these complexities are asymptotically optimal in each of our scenarios. Interestingly, we find that these speed-ups with respect to the precision come at the cost of a (up to exponential) slowdown with respect to the dimension of the Monte Carlo random variables, for most of the parameter settings we consider. We also describe several applications of our algorithms, notably in the field of machine learning, and discuss the implications of our results.