Abstract 1 Introduction 2 Preliminaries 3 Algorithms 4 Lower bounds References Appendix A Query complexities of bitstring problems

How to Compute the Volume in Low Dimension?

Arjan Cornelissen ORCID Simons Institute, UC Berkeley, CA, USA
Université Paris Cité, CNRS, IRIF, Paris, France
Simon Apers ORCID Université Paris Cité, CNRS, IRIF, Paris, France Sander Gribling ORCID Tilburg University, The Netherlands
Abstract

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.

Keywords and phrases:
Query complexity, computational geometry, quantum computing, volume estimation, high-precision limit
Category:
Track A: Algorithms, Complexity and Games
Funding:
Arjan Cornelissen: Supported by a Simons-CIQC postdoctoral fellowship through NSF QLCI Grant No. 2016245.
Simon Apers: Supported in part by the European QuantERA project QOPT (ERA-NET Cofund 2022-25), the French PEPR integrated projects EPiQ (ANR-22-PETQ-0007) and HQI (ANR-22-PNCQ-0002), and the French ANR project QUOPS (ANR-22-CE47-0003-01).
Copyright and License:
[Uncaptioned image] © Arjan Cornelissen, Simon Apers, and Sander Gribling; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation Quantum query complexity
; Theory of computation Computational geometry
Related Version:
Full Version: https://arxiv.org/abs/2503.02207
Editors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis

1 Introduction

The volume estimation problem is a widely-studied problem, that lies on the interface between convex geometry and computational complexity. The typical setting is the following, see for instance [33]. We consider a convex body Kd that satisfies BdKRBd, where Bd={xd:x1} denotes the unit ball in d dimensions, and RBd the radius-R ball in d dimensions. Denoting the volume of K by Vol(K), the aim of volume estimation is to output V~0 such that |V~Vol(K)|<εVol(K), for a given relative precision ε>0.

In this work, we are interested in the query complexity of volume estimation. Specifically, we will assume access to K through a membership oracle which, after querying a point xd, returns whether xK. The key question is then how many membership queries (as a function of d, R and ε) are required to solve the volume estimation problem. We analyze this question in three computational models, namely the deterministic, randomized and quantum models, each of which is more powerful than the last.

Previous work mostly studied query complexity in the high-dimensional setting, which tracks the dependency of the query complexity on the dimension d. The title of this work is a reference to the early survey by Simonovits called “How to compute the volume in high dimension?” [33], and we refer the interested reader to this survey for a more in-depth discussion of this setting. In this work, however, we focus on the low-dimensional limit, or high-precision limit, i.e., the limit where the dimension d is fixed and the precision ε goes to zero. While we are not aware of any literature targeting this regime in the membership oracle setting, there are numerous algorithms in different access models targeting this regime. We summarize the most relevant of these below, and refer the interested reader to the excellent survey by Brunel [11].

1.1 Low-dimensional computational geometry

Before turning to volume estimation, we discuss a related problem that has been well studied in the low-dimensional limit. In the convex set estimation problem, one tries to output a convex set K~d that estimates the original convex set K.

One way to measure the error in this problem is through the relative Nikodym metric, defined as the volume of the symmetric difference K~ΔK divided by the volume of K. An interesting sequence of results in this setting starts with a paper by Schütt [32]. They considered a bounded convex set KRBdd with RO(1), and showed that the convex hull of n points sampled uniformly at random from K, approximates it up to relative Nikodym distance O(n2/(d+1)). Later, Brunel proved a matching lower bound [10], implying that in order to achieve relative error ε, one requires Θ(ε(d+1)/2) samples from the uniform distribution over K to solve the convex set estimation problem. Surprisingly, Baldin and Reiß [4] showed that the volume estimation problem is significantly easier in this setting, i.e., they show that Θ(ε2(d+1)/(d+3)) uniform samples from K are necessary and sufficient to estimate its volume up to relative error ε.

Another line of research considers a qualitatively stronger error metric for the convex set estimation problem. To that end, suppose that a convex body K~d is an approximation of a convex body Kd. For any ε(0,1), Agarwal, Har-Peled and Varadarajan [2] define K~ to be an ε-kernel of K if K~K, and

uSd1,maxxK~uTxminxK~uTx(1ε)[maxxKuTxminxKuTx],

where Sd1=Bd is the unit sphere in d dimensions. If K~ is an ε-kernel of K, then the Hausdorff distance between K~ and K, i.e., the maximum distance between a point in K from K~ and vice versa, is at most εdiam(K) (see Lemma 7). Being an ε-kernel is invariant under taking arbitrary linear transformations, just like the Nikodym metric, and any ε-kernel of K approximates it up to relative Nikodym distance O(ε) too (see Proposition 8), yet the converse does not hold.

The starting point towards algorithmically constructing such ε-kernels is an early paper by Dudley [18, 23], which proves that every convex body KBd has an approximate polytope K~K with Hausdorff distance at most ε and only O(ε(d1)/2) faces. Independently, Brohnsteyn and Ivanov [9] proved that a similar approximate polytope exists with only O(ε(d1)/2) vertices. Subsequently, in the more restricted setting where K is well-rounded, i.e., BdKRBd, Agarwal, Har-Peled and Varadarajan [2] used Brohnsteyn and Ivanov’s construction to produce an ε-kernel with O((R/ε)(d1)/2) vertices, and their algorithm was subsequently improved independently by [13] and [34]. The referenced resources only explicitly analyze their algorithms’ performance in terms of the runtime in the case where K is the convex hull of n points, with [34] ultimately achieving a runtime of O(n+ε1/2) for d=2 and O~(n+εd2) for d3. In this work, we build on these algorithmic ideas and port them to the membership oracle setting.

1.2 Our results

In this paper, we tightly characterize the membership oracle query complexity for the convex set estimation and volume estimation problems, in the low-dimensional limit, and in the deterministic, randomized and quantum models. The resulting complexities are displayed in Table 1.

Table 1: Overview of the query complexity results obtained in this paper for the convex set estimation and volume estimation problems. We only track the dependence on 1/ε and R, the prefactors are allowed to depend exponentially on the dimension d. The tilde hides polylogarithmic factors in 1/ε and R.
Problem Convex set estimation Volume estimation
Error metric Constructing ε-kernel Rel. Nikodym distance ε Rel. error ε
Deterministic Θ~(εd12) Θ~(εd12) Θ~(εd12)
Randomized Θ~(εd12) Θ~(εd12) Θ~(ε2(d1)d+3)
Quantum Θ~(εd12) Θ~(εd12) Θ~(εd1d+1)

For the convex set estimation problem, we consider both the problem of constructing an ε-kernel, as well as estimating K up to relative Nikodym distance ε. We obtain that the query complexities of both problems are Θ~(ε(d1)/2) in all three computational models. This shows in particular that randomness and quantumness alike do not provide any benefit over the deterministic model. Furthermore, for estimating a convex set up to relative Nikodym error, having access to a membership oracle is strictly more powerful than uniform sampling from the convex body, as we beat the Θ(ε(d+1)/2) samples that are required in that setting [10].

For the volume estimation problem, we plot the obtained complexities in Figure 1. For any fixed dimension d, we beat the previously best-known algorithms in the randomized and quantum settings, that respectively make O(1/ε2) and O(1/ε) queries. The exponents in our complexities converge to these naive bounds as d increases, showing that the obtained advantage becomes ever smaller with increasing d. Moreover, the gap between the randomized and quantum query complexity is small when d is small, and becomes bigger as d increases, converging to a full quadratic separation in the regime where d is large. Like in the uniform sampling setting, the volume estimation problem is significantly easier than the convex set estimation problem in the randomized model.

Figure 1: Graph of the exponents in the query complexities for the volume estimation problem. d is fixed, and the asymptotic limit is for R and ε0. The tilde hides polylogarithmic factors in 1/ε and R. The dashed lines represent the previously best-known results, and the solid ones connect the newly-found complexities.

1.3 Techniques

Our algorithms are based on the approaches taken in [2, 13, 34], and they all proceed in a similar manner. First, we apply an existing, deterministic rounding procedure [22, Theorem 4.6.1] that makes O~(1) queries and transforms the convex body into a “well-rounded” one, i.e., satisfying BdKRBd with RO(1) when d is fixed.

Then, we follow [34], and take a set {vj}j=1n of n roughly equally spaced points on the boundary of (R+1)Bd, with nΘ(ε(d1)/2). Every point vj is subsequently projected onto the convex body, and the convex hull of the resulting points forms an ε-kernel of K, as was shown in [2]. Since these projections cannot be implemented directly in our model, we formulate every projection operation as a convex optimization problem, and use existing solvers from [22] to obtain an approximate projection. It was already shown in [13] and [34, Theorem 1] that this suffices to obtain an ε-kernel K~ of K. It also follows that K~ is an ε-precise approximation of K in the relative Nikodym metric.

Next, we find a speed-up of this approach for the volume estimation problem. To that end, we first run the convex set estimation procedure to some precision ε>ε, to obtain an ε-kernel K¯ of K. We slightly enlarge the inner approximation K¯K to generate an outer approximation K¯K of K, with the property that Vol(K¯K¯)/Vol(K)O(ε). Then, in the randomized setting, we sample Θ((ε/ε)2) times uniformly from the region K¯K¯, and compute the fraction of samples ξ that is inside K. We then use this as a refinement to our estimate of Vol(K), i.e., we output Vol(K¯)+ξVol(K¯K¯). In the quantum case, we employ the same idea, but this time we use quantum amplitude estimation to quadratically speed up the computation of ξ. In both cases, balancing the number of queries made in the first and second step yields the complexity bounds from Table 1.

The matching lower bounds for the query complexities follow from a construction that dates back to Dudley [18], where it was used to prove a lower bound on the number of facets needed for approximating convex bodies by polytopes. The construction packs n disjoint, identical spherical caps on the boundary of the unit ball through a δ-net, for some suitable value of δ that depends on d and ε. Then, a convex body KxBd is associated to a bitstring x of length n by including the jth spherical cap in Kx if and only if xj=1. See Figure 2 for an illustration.

The core observation is that estimating Kx, or its volume, becomes equivalent to learning a fraction of the entries of the bitstring x, or its Hamming weight, respectively. Additionally, a membership query to Kx can be simulated with a single query to x. Recovering a constant fraction of bits of an n-bit string is known to cost Θ(n) queries in all three models that we consider. Similarly, the problem of estimating the Hamming weight of a bitstring is also known as the approximate counting problem and its (deterministic, randomized and quantum) query complexity has been tightly characterized in earlier work. We show that by carefully choosing the size of the spherical caps, this construction provides matching lower bounds for the query complexities from Table 1 up to polylogarithmic factors in R and ε (and large factors in the dimension d).

1.4 History in the high-dimensional setting

For completeness, we also comment on volume estimation in the high-dimensional setting, which tracks the dependency of the query complexity on the dimension d. The title of this work is a reference to the early survey by Simonovits called “How to compute the volume in high dimension?” [33], and we refer the interested reader to this survey for a more in-depth discussion of this setting. The main takeaways in this setting are the following:

  • In the deterministic setting, any deterministic algorithm must make a number of queries that is exponential in d [20, 5].

  • In the randomized setting, there famously exists a Markov chain Monte Carlo algorithm that makes a number of queries polynomially in d and 1/ε [19]. While the initial bound scaled as O~(d23/ε2), a long of research led to the current best bound that is O~(d3/ε2). This bound follows from combining algorithms in [17, 25] with recent breakthroughs on the so-called KLS-constant (see e.g. [27]), and it approaches a lower bound of Ω~(d2) on the randomized query complexity [31].

  • In the quantum setting, Chakrabarti, Childs, Hung, Li, Wang and Wu [12] gave an improved bound of the form O~(d3+d2.5/ε).111In [12, Page 20:11], the authors claim that recent breakthroughs in the KLS-conjecture [14, 24, 26] improve the analysis of their volume estimation algorithm to O~(d2.5+o(1)+d2+o(1)/ε) membership oracle queries. They argue that the mixing time of the hit-and-run walk is O~(d2ψ2), where ψ is the KLS-constant. This indeed appears to be a correct upper bound on the mixing time of the ball walk, see [25, Theorem 2.7], but, as far as we are aware, the mixing time of the hit-and-run walk is not known to be improved due to the resolution of the KLS-conjecture. Adapting the algorithm of [12] to make use of the ball walk is highly non-trivial. Consequently, the question of whether volume estimation can be done in O~(d2.5+o(1)+d2+o(1)/ε) quantum queries to the membership oracle is still open. This was later improved to O~(d3+d2.25/ε) by Cornelissen and Hamoudi [15]. Both use quantum algorithms to speed up the Markov chain Monte Carlo method. The authors of [12] also prove that the query complexity is Ω(d) when ε is constant, and Ω(1/ε) in the regime where 1/dε1/3, which in turn implies Ω(d) when ε=1/d.222In [12], the authors additionally informally suggest a lower bound of Ω(1/ε) in general, but the corresponding theorem statement excludes the limit ε0. A lower bound of Ω(1/ε) for fixed d and in the limit where ε0 would indeed contradict our results.

1.5 Organization

In Section 2, we fix notation, formally define algorithmic models and computational problems, and state results from (computational) geometry. Subsequently, in Section 3 we develop the algorithms, and in Section 4 we prove the corresponding lower bounds.

2 Preliminaries

2.1 Notation

We start by fixing some notation. Let be the set of all positive integers. For all n, let [n]={1,,n}, and [n]0={0}[n]. For any k (or x), we let k (resp. x) be the set of all integers (resp. reals) that are bigger than or equal to k (resp. x). We denote the Euclidean norm by . For every d, we denote the unit ball in d dimensions by Bd={xd:x1}. We write Γd=Vol(Bd) for the volume of Bd. We denote the unit sphere in d dimensions by Sd1=Bd. For two sets A and B we let AΔB=(AB)(BA) be the symmetric difference of A and B.

A set Kd is convex if for any two points x,yK, the straight line segment between x and y is fully contained in K, i.e., for every λ[0,1], λx+(1λ)yK. For two convex sets K,Kd, we recall that KK and K+K={x+y:xK,yK} are again convex. For ease of notation, we typically make an implicit assumption that all convex bodies are closed.

We use big-O-notation to hide constant factors. That is, for two functions f,g:0d0, we write fO(g) if there exist C,r>0 such that f(x)Cg(x) whenever xr. We write fΩ(g) if gO(f), and we write fΘ(g) if fO(g)Ω(g). Sometimes, the limit in which the big-O-notation is to be interpreted plays an important role. For instance if the big-O-notation holds in the limit where ε0, then we interpret the function f,g as functions in the variable 1/ε.

Similarly, we use the big-O-tilde-notation to hide polylogarithmic factors. That is, if f,g:0d0, then we write fO~(g) if there exist constants C,k,r0 such that f(x)Cg(x)j=1dlogk(xj) whenever xr. We write fΩ~(g) if gO~(f), and fΘ~(g) if fO~(g)Ω~(g).

2.2 Access model and computational models

The input to the algorithms we design in this work are a dimension d, outer radius R1, precision ε(0,1), and a convex body Kd. The access model specifies how the algorithm can access this input. Throughout, we will assume that the parameters d, R and ε are set beforehand, and hence are known to the algorithm. As for the convex body K, many ways to access it have been considered in the literature. We refer to [22, Chapter 2] for an overview of several different access models. In this work, we assume that it can be accessed by means of a (strong) membership oracle, in line with [22, Definition 2.1.5].

Definition 1 (Membership oracle).

Let d, and Kd be a convex body. A membership oracle to K is a procedure that, given a point xd, outputs whether xK.

In general, an oracle is a subroutine that the algorithm can run only as a black box, i.e., it has no more information about what happens when it is run. One such call to the oracle is referred to as a query. The query complexity of a problem is the minimum number of queries any algorithm needs to make to solve said problem.

Additional to the access model, we also specify computational models that define the operations that the algorithms are allowed to use. We consider three different computational models in this work. In the deterministic model, the algorithm is completely described beforehand and follows a deterministic computational path. In the randomized model, the algorithm is allowed to use randomness during the execution of the algorithm, and in particular let the oracle’s inputs depend on it. It is required to output a correct answer with probability at least 2/3. In the quantum model, the algorithm is additionally allowed to perform operations on a quantum state, and supply the oracle’s inputs in a superposition, which it answers coherently. For a more detailed introduction to quantum algorithms, we refer to [30].

Throughout the execution of our algorithms, we additionally assume that we can store vectors in d precisely in memory in all three models, and that we can perform basic arithmetic with them exactly. We also assume in the randomized model that we can sample from any distribution on d as long as we have a classical description of it, and we use this to sample uniformly from an arbitrary region in Theorem 13. Similarly, in the quantum model, we assume that we can generate a uniform superposition over an arbitrary region in d, and we use this in Theorem 14. Both of these operations do not depend on K, so in an implementation of the algorithms presented in this work, one can suppress the finite-precision errors that arise from these assumptions arbitrarily without increasing the number of membership oracle queries.

2.3 Rounding convex bodies

We start by describing a routine that “rounds” the convex body. A similar idea appears in [2, 13, 34], but in contrast to their approach, we use inner and outer ellipses, rather than inner and outer cubes in our rounding procedure. This difference is not fundamental, it merely allows us to use a rounding routine that already exists in the literature [22].

The aim of “rounding” a convex body Kd is to find an invertible affine linear map L:xx0+Tx, such that BdL(K)RBd with R1 as small as possible. Intuitively, one can think of rounding as finding a linear transformation that compresses the convex body as much as possible, so that it does not have parts that stick out far from the origin. Most of the existing literature focuses on randomized algorithms to compute this affine linear map [28, 25], with the current state-of-the-art obtaining RO~(d) and requiring O~(d3) queries. In our setting, though, we require a deterministic procedure, and since we take d to be a constant we don’t necessarily need R to scale optimally in the dimension. Below, we sketch how to obtain a deterministic rounding procedure that obtains RO(d3) and runs in time O(poly(d,log(R))).

Theorem 2 ([22]).

Let d, R1, and let Kd be convex such that BdKRBd. Then, there is a deterministic algorithm that makes O(poly(d,log(R)) queries, and finds an invertible affine linear map L such that BdL(K)RBd, with R=d(d+1)2O(d3). When d is fixed, the algorithm makes O~(1) queries, and RO(1).

Proof.

Since Kd satisfies BdKRBd, we observe from [22, Figure 4.1] that we can deterministically turn a membership oracle into a weak separation oracle. The total multiplicative factor incurred from this conversion is O(poly(d,log(R))), and hence is O~(1) in the case where d is fixed.

Subsequently, from [22, Theorem 4.6.1], we find that with O(poly(d,log(R))) calls to a weak separation oracle to K, we can find an ellipsoid E, such that EKd(d+1)2E. Thus, by letting L be the affine linear transformation that maps E to the unit ball, we obtain that

BdL(K)RBd,whereR=d(d+1)2O(d3).

For fixed d, we obtain RO(1), and the query complexity of finding L is in O~(1).

2.4 Geometry

We proceed by recalling some theoretical background in geometry. We start by formally introducing the concept of a net.

Definition 3 (δ-net).

Let d, δ>0, and let Sd be any set. We say that NS is a δ-net of S if

  1. 1.

    For any two distinct points v,wN, we have vwδ.

  2. 2.

    For any vS, there exists a wN such that vwδ.

Intuitively, one can think of a δ-net N as the centers of a set of balls of radius δ, that together cover the set S. Moreover, since these centers are at least separated by distance δ, the balls with radius δ/2 centered at the points in N must be disjoint up to a measure-zero set. By comparing the surface area of the sphere to that of {uSd1:uvδ} (for some fixed vSd1), the following bound follows on the number of points in a δ-net on the sphere. We stress that the assumption that d is fixed is crucial in the above proposition. Indeed, the Θ-notation hides a prefactor that might depend exponentially on d.

Proposition 4.

Let d be fixed. Let δ(0,1), and let Nδ be a δ-net of Sd1. Then, |Nδ|Θ(δ(d1)).

Proof.

For any vV and r>0, let Rv,r={wSd1:vwr}. The surface areas of Rv,r is Av,rΘ(rd1) and the surface area of Sd1 is Ad1Θ(1). Since Nδ is a δ-net, all Rv,δ/2’s with vNδ are disjoint up to possibly some measure-zero set, and all Rv,δ’s cover Sd1. Thus, we find |Nδ|Av,δ/2Ad1|Nδ|Av,δ, from which we conclude that |Nδ|Θ(δ(d1)).

We proceed with formally defining an ε-kernel.

Definition 5 (ε-kernel [2]).

Let d, and ε(0,1). Let Kd be a convex body. Then a convex body K~K is an ε-kernel of K if

uSd1,maxxK~uTxminxK~uTx(1ε)[maxxKuTxminxKuTx].

One very desirable property of ε-kernels is its invariance under affine linear transformations.

Lemma 6 ([2],[1, Lemma 2.5]).

Let d, ε(0,1), and let L be an invertible affine linear map on d. Let K~,Kd be convex sets. Then, K~ is an ε-kernel of K if and only if L(K~) is an ε-kernel of L(K).

Next, we make a connection between ε-kernels and approximations w.r.t. the Hausdorff metric.

Lemma 7.

Let d, R1, ε>0, and let K,K~d be convex sets.

  1. 1.

    If BdK and K~K is an ε-precise Hausdorff approximation of K, then K~ is also an ε-kernel of K.

  2. 2.

    If KRBd and K~ is an ε-kernel of K, it is a 2εR-precise Hausdorff approximation of K.

Proof.

Observe that if K~K, then the Hausdorff distance d between K~ and K is

d=maxuSd1[maxxKuTxmaxxK~uTx]=maxuSd1[minxK~uTxminxKuTx]. (1)

For the first claim, we take uSd1 arbitrarily, and observe from Equation 1 that

maxxK~uTxminxK~uTxmaxxKuTxminxKuTx2ε(1ε)[maxxKuTxminxKuTx].

For the second claim, let d be the Hausdorff distance between K and K~, and u the vector that maximizes the middle expression in Equation 1. Then, we have

d =maxxKuTxmaxxK~uTx[maxxKuTxminxKuTx][maxxK~uTxminxK~uTx]
ε[maxxKuTxminxKuTx]εdiam(K)2εR.

Finally, we observe that an ε-kernel naturally provides a relative Nikodym approximation of K, and can be used to construct an outer approximation of K, in the following proposition.

Proposition 8.

Let d, ε(0,1/(4d(d+1)2)), and let K~ be an ε-kernel of a convex set Kd. Then, given a full description of K~, we can construct a convex set K¯K such that Vol(K¯K~)/Vol(K)(1+4εd(d+1)2)d1O(ε), with O~(1) membership oracles to K. In particular, this implies that Vol(K~ΔK)/Vol(K)O(ε).

Proof.

Since being an ε-kernel and being a relative Nikodym-distance approximation are both invariant under affine linear transformations, we can without loss of generality first round the convex body K using Theorem 2, using just O~(1) membership queries. It then suffices to consider the case where BdKRBd, with R=d(d+1)2O(1). Since ε<1/(4R), we find by Lemma 7 that BdKK~+2εRBdK~+Bd/2, and so Bd/2K~. Thus,

Bd/2K~KK~+2εRBd(1+4εR)K~=:K¯,

from which we find that

Vol(K¯K~)Vol(K)=Vol(K¯)Vol(K~)Vol(K)=[(1+4εR)d1]Vol(K~)Vol(K)(1+4εR)d1O(ε).

2.5 Problem definitions

We consider three computational problems in this paper. We formally introduce them here.

Definition 9 (Problem definitions).

Let d, R>1, and ε(0,1). Let Kd be a convex body such that BdKRBd. We consider three problems:

  1. 1.

    The ε-kernel construction problem is the problem of outputting an ε-kernel of K.

  2. 2.

    The ε-Nikodym construction problem is the problem of outputting a convex body K~d such that Vol(KΔK~)εVol(K).

  3. 3.

    The volume estimation problem is the problem of outputting a non-negative real V~0 such that |Vol(K)V~|εVol(K).

It follows directly that these problems are qualitatively decreasing in terms of their query complexity. That is, solving the ε-kernel construction problem also solves the Nikodym construction problem with precision O(ε), by virtue of Proposition 8, which in turn solves the volume estimation problem with the same precision, since we can simply output the volume of the approximation K~. These relations are less clear if one considers the runtime instead, e.g., since computing the volume might be very costly.

3 Algorithms

3.1 Convex set estimation

In this subsection, we develop a deterministic algorithm that constructs an ε-kernel of a well-rounded convex set Kd, using membership queries to it. The algorithm follows the same general strategy as in [34], and we replace their approximate nearest-neighbor queries by a query-efficient approximate projection onto a convex body. For this, we use the well-known observation that projection onto a convex body can be phrased as a convex optimization problem, which we can deterministically solve approximately with only polylogarithmically many membership oracles calls, using for example the ellipsoid method [22].

Proposition 10.

Let d, R1, ε>0, Kd convex such that BdKRBd. Let xdK, and y its projection onto K. There is a deterministic algorithm that obtains an element y~K such that y~yε. The algorithm makes O(poly(d,logx,logR,log(1/ε))) queries to a membership oracle of K. When d is fixed and RO(1), this complexity is O~(1).

Now, we are ready to state the ε-kernel construction algorithm. We start by considering the well-rounded case, in Algorithm 1. We subsequently prove its properties in Theorem 11.

Algorithm 1 Well-rounded deterministic ε-kernel construction [34].

Input:

  1. 1.

    d2: the dimension.

  2. 2.

    ε(0,1): the desired precision.

  3. 3.

    R1: the outer radius, with RO(1).

  4. 4.

    OK: a membership oracle that on input xd returns whether xK, where BdKRBd.

Derived constant: η=ε/R.

Output: An ε-kernel K~ of K.

Number of queries: O~(ε(d1)/2) (in the limit where d is fixed).

Procedure: RoundedEpsKernConstr(d,ε,R,OK):

  1. 1.

    Let {xj}j=1n be an η-net of (R+1)Sd1.

  2. 2.

    For j=1,,n,

    1. (a)

      Project xj onto K with precision ε, using Proposition 10. Denote the outcome by pj.

  3. 3.

    Output conv({pj}j=1n).

Theorem 11.

Let d2, R1 with RO(1), and Kd be a convex body such that BdKRBd. Then, Algorithm 1 computes an ε-kernel of K that satisfies K~K, with O~(ε(d1)/2) membership oracle queries.

Proof.

Correctness is proven in [34, Theorem 1]. For the bound on the number of queries, observe from Proposition 4 that the η-net contains O(η(d1))=O(ε(d1)/2) points. Furthermore, for every point, we perform one approximate projection, which costs O~(1) queries by Proposition 10. As such, we conclude that the total number of membership oracle queries is O~(ε(d1)/2).

In the case where K is not well-rounded, we combine Algorithm 1 with the rounding procedure of Theorem 2, and conversion to Nikodym distance in Proposition 8, to obtain the following corollary.

Corollary 12 (Deterministic ε-kernel construction).

Let d2, R1, ε(0,1/(4d(d+1)2)), and Kd be convex such that BdKRBd. Then, we can deterministically compute an ε-kernel K~ of K with O~(ε(d1)/2) membership oracle queries. K~ is also an O(ε)-precise approximation of K in the relative Nikodym distance, and Vol(K~) is an O(ε)-precise relative estimate of Vol(K).

This corollary proves all the O~(ε(d1)/2) upper bounds in Table 1. In Section 4.2, we prove that this approach is essentially optimal for the reconstruction problem in all computational models, i.e., even in the randomized and quantum settings we cannot improve significantly over the approach taken in Corollary 12.

3.2 Volume estimation

In this subsection, we switch to the volume estimation problem. To start off, we remark that Corollary 12 solves it in the deterministic setting. In the randomized and quantum settings, however, we can obtain a significant improvement over this approach.

The core idea is to run the (deterministic) ε-kernel construction algorithm up to some worse precision ε>ε, to obtain an inner approximation K¯K. We can the use Proposition 8 to obtain an outer approximation K¯K, such that Vol(K¯K¯)/Vol(K)O(ε).

Subsequently, in the randomized setting, we sample uniformly from K¯K¯, and compute the fraction of points ξ that is inside K. We then compute Vol(K¯)+ξVol(K¯K¯) as a refined estimate of the volume of K, eventually resulting in the following theorem.

Theorem 13 (Randomized volume estimation).

Let d2, R1, ε(0,1), Kd convex such that and BdKRBd. We can compute V~0 such that |V~Vol(K)|εVol(K) with probability at least 2/3, using a randomized algorithm that makes O~(ε2(d1)/(d+3)) queries to a membership oracle of K.

Proof.

We first use Corollary 12 to obtain an ε-kernel K¯K with

ε=(1+ε4d+3)1d14d(d+1)2Θ(ε4d+3).

We make O~((ε)(d1)/2)=O~(ε2(d1)/(d+3)) membership oracles in this step of the algorithm. Then, we use Proposition 8 to generate an outer approximation K¯K, using just O~(1) membership oracle queries. We find that Vol(K¯/K¯)/Vol(K)ε.

Next, we take n:=3(ε/ε)2 random samples from K¯K¯, and we check for each of them whether they are in K. We denote the fraction of them that is in K by ξ. This step requires n=O~((ε/ε)2)=O~(ε2(d1)/(d+3)) membership oracle queries too.

Finally, we output V~=Vol(K)+ξVol(K¯K¯). We observe that

𝔼[V~]=Vol(K¯)+𝔼[ξ]Vol(K¯K¯)=Vol(K¯)+Vol(KK¯)Vol(K¯K¯)Vol(K¯K¯)=Vol(K),

and

Var[V~]=Vol(K¯K¯)2Var[ξ](εVol(K))2n(εVol(K))23.

We conclude with Chebyshev’s inequality that

[|V~Vol(K)|>εVol(K)]Var[V~](εVol(K))213.

In the quantum case, we speed up the sampling phase from the randomized algorithm by replacing it with a quantum primitive known as amplitude estimation [8]. We attain a quadratic speed-up of this step, and the claimed complexity follows after rebalancing the costs of the different steps.

Theorem 14 (Quantum volume estimation).

Let d2, R1, ε(0,1), and Kd convex such that BdKRBd. We can compute V~0 such that |V~Vol(K)|εVol(K) with probability at least 2/3, using a quantum algorithm that makes O~(ε(d1)/(d+1)) queries to OK.

Proof.

Similarly to the proof of Theorem 13, we start by constructing an ε-kernel K¯K using Corollary 12, and then use Proposition 8 to obtain K¯K such that Vol(K¯K¯)εVol(K). In contrast to Theorem 13, though, we choose

ε=(1+ε2d+1)1d14d(d+1)2Θ(ε2d+1),

which brings the total number of membership oracle queries in this part to O~((ε)(d1)/2)=O~(ε(d1)/(d+1)).

Next, we use amplitude estimation to find an estimate ξ of Vol(KK¯)/Vol(K¯K¯) up to precision ε/ε. To that end, we compute the overlap between the uniform superposition on K¯K¯, and the subspace spanned all the quantum states representing vectors in K. From [8], we find that this can be done with success probability at least 8/π2>2/3, and with a total number of queries that satisfies O~(ε/ε)=O~(ε(d1)/(d+1)). Finally, we output V~=Vol(K)+ξVol(K¯K¯), and observe that

|V~Vol(K)|=Vol(K¯K¯)|ξVol(KK¯)Vol(K¯K¯)|εVol(K)εε=εVol(K).

This concludes our discussion of randomized and quantum algorithms estimating the volume of a convex body. In Section 4.2, we prove that these algorithms are essentially optimal.

4 Lower bounds

In this section, we prove matching lower bounds for the computational problems from Definition 9. We can always rescale our problems, and so we can freely change the assumption that BdKRBd to (1/R)BdKBd. For ease of notation, we will phrase everything with the latter assumption in mind.

The lower bounds crucially rely on embedding a bitstring on the boundary of the unit ball in d dimensions. To that end, we let {vj}j=1n be a net of Sd1, and for every j[n], we define a spherical cap Pj around vj, i.e., a small region cut off from the unit ball by a hyperplane that is orthogonal to vj. We take all the spherical caps to be disjoint and with equal volume, and we let K0 be the remaining part of the unit ball, as shown in Figure 2.

Figure 2: The lower bound construction in two dimensions with n=6. For any x{0,1}6, the convex body Kx is formed by taking the union of K0 and all spherical caps Pj if and only if the corresponding bit xj is 1.

The core idea is to associate a convex body Kx to every bitstring x{0,1}n, defined as the union of K0, and all the spherical caps Pj if and only if xj=1. We then immediately observe that Vol(Kx)=Vol(K0)+|x|Vol(P1), and Vol(KxΔKy)=|xy|Vol(P1).

Intuitively, now, if we find an approximation to the convex body Kx, then we also find an approximation to the bitstring x. Similarly, if we find a sufficiently precise estimate of Kx’s volume, we also obtain a good approximation of x’s Hamming weight. In short, we can reduce the bitstring recovery problem to convex set estimation, and the Hamming weight estimation problem to volume estimation, and hence lower bounds on the former imply lower bounds on the latter.

4.1 Query complexity of bitstring problems

We first recall the bitstring recovery and the Hamming weight estimation problems. These are well-studied in the existing literature, albeit a bit scattered, and we gather the existing results in two concise theorem statements. The proofs can be found in Appendix A.

Theorem 15 (Bitstring recovery problem).

Let n, and let x{0,1}n be a bitstring that we can access through bit queries. Suppose we wish to output a bitstring y{0,1}n such that |xy|n/4. The query complexities for this problem are Θ(n) in the deterministic, randomized and quantum setting.

Next, we consider the Hamming weight estimation problem. This problem is sometimes also referred to as the approximate counting problem. In short, given a bitstring of length n, we wish to estimate the number of 1’s it contains up to some additive precision k. Its hardness is also well-understood – we gather the previous known results in Theorem 16.

Theorem 16 (Hamming weight estimation problem).

Let n and let x{0,1}n be a bitstring that we can access through bit queries. Let k be such that 1kn/4. Suppose we wish to output w[n]0 such that ||x|w|k. The query complexities for this problem are Θ(n) in the deterministic setting, Θ(min{(n/k)2,n}) in the randomized setting, and Θ(n/k) in the quantum setting.

4.2 Reduction to convex set estimation and volume estimation

We start by formalizing the concept of a spherical cap, and provide a visualization in Figure 3.

Definition 17 (Spherical cap).

Let d, vSd1 and r>0. Let Sv={uSd1:uv<r}, and let Pv be its convex hull. Then Pv is the spherical cap around v with radius r.

Figure 3: The shaded region is a spherical cap around v with radius r.

Next, we prove some properties of spherical caps.

Lemma 18 (Properties of spherical caps).

Let d, v,wSd1, r>0, and Pv and Pw the spherical caps with radius r around v and w, respectively. Then,

  1. 1.

    Pv={xBd:xTv>1r2/2}.

  2. 2.

    If vw2r, then Pv and Pw are disjoint.

  3. 3.

    Vol(Pv)Θ(rd+1), in the limit where d is fixed and r0.

Proof.

For the first claim, observe that xSv if and only if xTv=(x2+v2xv2)/2>1r2/2. Consequently, xPv if and only if it is inside the unit ball and satisfies this inequality.

For the second claim, we prove the contrapositive, i.e., we prove that zPvPwvw<2r. To that end, let zPvPw. Then, using that z1 and Cauchy-Schwarz’s inequality, we obtain

vw2 =2v2+2w2v+w24z2v+w2
4(zT(v+w))2<4(2r2)24r2.

Finally, computing the volume yields

Vol(Pv)=Γd11r2/21(1x2)d12dx=Γd10r2/2(x(2x))d12dxΘ(rd+1).

We now use the above properties to compute how many spherical caps we can pack on the surface of a unit ball.

Lemma 19 (Packing of spherical caps).

Let d2 and let δ>0. Let {vj}j=1n be a δ-net, for each j[n] let Pj:=Pvj be a spherical cap with radius δ/2, and let P={Pj}j=1n. Then, n=Θ(δ(d1)), all the spherical caps are disjoint, and the total volume of the spherical caps is Vol(P):=nVol(P1)=Θ(δ2).

Proof.

The claims follow immediately from Proposition 4 and Lemma 18.

Finally, we show how embedding a bitstring in these spherical caps naturally leads to a lower bound on the query complexity of the volume estimation and the convex set estimation problems.

Theorem 20.

Let d2 and ε>0. Then, any algorithm 𝒜 that solves the convex set estimation problem or the volume estimation problem, must make a number of queries that satisfies the complexities listed in Table 1.

Proof.

We start with the lower bounds on the convex set estimation problems. To that end, suppose that an algorithm 𝒜 solves it with relative Nikodym distance ε.

For every δ>0, we choose a particular δ-net {vj}j=1n, and then we let {Pj}j=1n and P be as in Lemma 19. Observe that Vol(P)Θ(δ2). We now choose the smallest δ>0 such that Vol(P)8εΓd, which for small enough ε>0 is guaranteed to be well-defined. Then δΘ(ε), which implies that nΘ(ε(d1)/2).

Now, for any bitstring x{0,1}n, we define a convex body Kx by

Kx=K0j=1xj=1nPj, (2)

Then, given any bitstring x{0,1}n, 𝒜 outputs K~, an approximation of Kx with relative precision ε. Next, we can define a bitstring z{0,1}n such that

Vol(K~ΔKz)=min{Vol(K~ΔKy):y{0,1}n}Vol(K~ΔKx)εVol(Kx)εΓd.

Then, we obtain that

|xz|=Vol(KzΔKx)Vol(P1)n(Vol(K~ΔKz)+Vol(K~ΔKx))Vol(P)n(εΓd+εΓd)8εΓd=n4.

Finally, we observe that any call to the membership oracle of Kx can be simulated with at most one query to the bitstring x. Thus, according to Theorem 15, 𝒜 must make at least Ω(n)=Ω(ε(d1)/2) queries to the membership oracle of Kx, in the deterministic, randomized and quantum settings. Finally, since the ε-kernel construction problem is harder than the ε-Nikodym construction problem, the lower bounds from the first two columns in Table 1 follow.

It remains to prove the lower bounds for volume estimation. To that end, suppose that 𝒜 solves the volume estimation problem up to precision ε. Again for every δ>0 we choose a particular δ-net {vj}j=1n, and we let {Pj}j=1n and P as in Lemma 19, which means that Vol(P)Θ(δ2). Next, we let ε>0 arbitrarily and choose the smallest δ>0 such that Vol(P)8εΓd. For small enough ε, this is well-defined, and we find that δΘ(ε), from which we find that nΘ((ε)(d1)/2).

We let x{0,1}n and Kx as in Equation 2. Then,

Vol(Kx)=Vol(K0)+|x|Vol(P1).

𝒜 outputs an estimate V~ of Vol(Kx), such that |V~Vol(Kx)|εVol(Kx)εΓd. Hence, we can compute w=(V~Vol(K0))/Vol(P1), and we observe that

|w|x||=|V~Vol(K0)Vol(P1)Vol(Kx)Vol(K0)Vol(P1)|=n|V~Vol(Kx)|Vol(P)nεΓd8εΓd=nε8ε=:k.

Finally, similarly as before, since we can simulate any query to a membership oracle to Kx by one query to the bitstring x, we can use the lower bounds from Theorem 16 to lower bound the query complexity of 𝒜.

For the lower bounds of Theorem 16 to apply, we have to choose ε>0 as a function of ε such that 1kn/4. To that end, we let =ε/2 and u=nε/8, and observe that we must choose ε[,u]. We choose ε as , u and u, in the deterministic, randomized, and quantum settings, respectively. We remark in the randomized setting that n/k=8ε/εΘ(n), and so the lower bound from Theorem 16 becomes Ω(n). Similarly, in the quantum case, we have kΘ(1), and so the lower bound also becomes Ω(n). It remains to plug in the asymptotic scaling of n, from which we obtain the following lower bounds for the volume estimation problem:

Deterministic: Ω(n)=Ω((ε)d12)=Ω(εd12)
Randomized: Ω(n)=Ω(n4d+3nd1d+3)=Ω((ε)2(d1)d+3(ε/ε)2(d1)d+3)=Ω(ε2(d1)d+3).
Quantum: Ω(n)=Ω(n2d+1nd1d+1)=Ω((ε)d1d+1(ε/ε)d1d+1)=Ω(εd1d+1).

References

  • [1] Pankaj K Agarwal and Sariel Har-Peled. Computing instance-optimal kernels in two dimensions. Discrete & Computational Geometry, pages 1–28, 2024.
  • [2] Pankaj K Agarwal, Sariel Har-Peled, and Kasturi R Varadarajan. Approximating extent measures of points. Journal of the ACM (JACM), 51(4):606–635, 2004. doi:10.1145/1008731.1008736.
  • [3] Andris Ambainis. Quantum lower bounds by quantum arguments. In Proceedings of the 32nd annual ACM symposium on Theory of computing, pages 636–643, 2000. doi:10.1145/335305.335394.
  • [4] Nikolay Baldin and Markus Reiß. Unbiased estimation of the volume of a convex body. Stochastic Processes and their Applications, 126(12):3716–3732, 2016.
  • [5] Imre Bárány and Zoltán Füredi. Computing the volume is difficult. Discret. Comput. Geom., 2:319–326, 1987. doi:10.1007/BF02187886.
  • [6] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. Journal of the ACM (JACM), 48(4):778–797, 2001. doi:10.1145/502090.502097.
  • [7] Shalev Ben-David and Eric Blais. A tight composition theorem for the randomized query complexity of partial functions. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 240–246. IEEE, 2020.
  • [8] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53–74, 2002.
  • [9] E.M. Bronshteyn and L.D. Ivanov. The approximation of convex sets by polyhedra. Siberian Mathematical Journal, 16(5):852–853, 1975.
  • [10] Victor-Emmanuel Brunel. Adaptive estimation of convex and polytopal density support. Probability Theory and Related Fields, 164(1):1–16, 2016.
  • [11] Victor-Emmanuel Brunel. Methods for estimation of convex sets. Statistical Science, 33(4):615–632, 2018.
  • [12] Shouvanik Chakrabarti, Andrew M. Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang, and Xiaodi Wu. Quantum algorithm for estimating volumes of convex bodies. ACM Transactions on Quantum Computing, 4(3):1–60, 2023.
  • [13] Timothy M Chan. Faster core-set constructions and data-stream algorithms in fixed dimensions. Computational Geometry, 35(1-2):20–35, 2006. doi:10.1016/J.COMGEO.2005.10.002.
  • [14] Yuansi Chen. An almost constant lower bound of the isoperimetric coefficient in the KLS conjecture. Geometric and Functional Analysis, 31:34–61, 2021.
  • [15] Arjan Cornelissen and Yassine Hamoudi. A sublinear-time quantum algorithm for approximating partition functions. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1245–1264. SIAM, 2023. doi:10.1137/1.9781611977554.CH46.
  • [16] Arjan Cornelissen, Yassine Hamoudi, and Sofiene Jerbi. Near-optimal quantum algorithms for multivariate mean estimation. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 33–43, 2022.
  • [17] Ben Cousins and Santosh Vempala. Gaussian cooling and O(n3) algorithms for volume and Gaussian volume. SIAM Journal on Computing, 47(3):1237–1273, 2018.
  • [18] R.M. Dudley. Metric entropy of some classes of sets with differentiable boundaries. Journal of Approximation Theory, 10(3):227–236, 1974.
  • [19] Martin Dyer, Alan Frieze, and Ravi Kannan. A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the ACM (JACM), 38(1):1–17, 1991. doi:10.1145/102782.102783.
  • [20] György Elekes. A geometric inequality and the complexity of computing volume. Discrete & Computational Geometry, 1:289–292, 1986. doi:10.1007/BF02187701.
  • [21] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Bound on the number of functions that can be distinguished with k quantum queries. Physical Review A, 60(6):4331, 1999.
  • [22] Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms and combinatorial optimization. Springer-Verlag Berlin Heidelberg, 1 edition, 1988.
  • [23] Sariel Har-Peled and Mitchell Jones. Proof of Dudley’s convex approximation. arXiv preprint arXiv:1912.01977, 2019. arXiv:1912.01977.
  • [24] Arun Jambulapati, Yin Tat Lee, and Santosh S. Vempala. A slightly improved bound for the KLS constant. arXiv preprint arXiv:2208.11644, 2022. doi:10.48550/arXiv.2208.11644.
  • [25] He Jia, Aditi Laddha, Yin Tat Lee, and Santosh Vempala. Reducing isotropy and volume to KLS: an O(n3ψ2) volume algorithm. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 961–974, 2021.
  • [26] Bo’az Klartag. Logarithmic bounds for isoperimetry and slices of convex sets. arXiv preprint arXiv:2303.14938, 2023.
  • [27] Bo’az Klartag and Joseph Lehec. Bourgain’s slicing problem and KLS isoperimetry up to polylog. Geometric and Functional Analysis, 32(5):1134–1159, 2022.
  • [28] László Lovász and Santosh Vempala. Simulated annealing in convex bodies and an O(n4) volume algorithm. Journal of Computer and System Sciences, 72(2):392–417, 2006. doi:10.1016/J.JCSS.2005.08.004.
  • [29] Ashwin Nayak and Felix Wu. The quantum query complexity of approximating the median and related statistics. In Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 384–393, 1999. doi:10.1145/301250.301349.
  • [30] Michael A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge University Press, 2010.
  • [31] Luis Rademacher and Santosh Vempala. Dispersion of mass and the complexity of randomized geometric algorithms. Advances in Mathematics, 219(3):1037–1069, 2008.
  • [32] Carsten Schütt. Random polytopes and affine surface area. Mathematische Nachrichten, 170(1):227–249, 1994.
  • [33] Miklós Simonovits. How to compute the volume in high dimension? Mathematical programming, 97:337–374, 2003. doi:10.1007/S10107-003-0447-X.
  • [34] Hai Yu, Pankaj K Agarwal, Raghunath Poreddy, and Kasturi R Varadarajan. Practical methods for shape fitting and kinetic data structures using coresets. Algorithmica, 52:378–402, 2008. doi:10.1007/S00453-007-9067-9.

Appendix A Query complexities of bitstring problems

In this appendix, we provide the proofs to the query complexities of the bitstring problems that we use in the lower bound constructions in Section 4. We restate the theorems for convenience.

See 15

Proof.

The (deterministic) algorithm is trivial – simply query all the entries of x and output the bitstring exactly. Since the randomized and quantum settings can simulate the deterministic setting, this provides the upper bounds on the query complexities.

It remains to prove that this algorithm is optimal in all three models up to constant multiplicative factors. Since we can simulate any deterministic and randomized algorithm in the quantum setting, proving hardness in the latter suffices. An information-theoretic argument tells us that quantumly we need at least Ω(n) queries to output a bitstring that differs from x in at most n/4 positions. The core technique stems from [21], and all remaining details can for instance be found in [16, Lemma 4.6].

See 16

Proof.

We first prove the upper bounds. The deterministic upper bound is trivial. In the randomized setting, we need to show that the query complexity is O((n/k)2). To that end, suppose that we sample 3(n/k)2 bits at random, with replacement, and output n times the fraction of 1’s observed. Let Xj be the random variable describing the output of the jth sample, and we write the output of the algorithm as w:=n/3(k/n)2j=13(n/k)2Xj. Then, we trivially find that 𝔼[w]=|x|, and its variance can be bounded as

Var[w]=Var[n3(kn)2j=13(n/k)2Xj]=n29(kn)43(nk)2Var[X1]=13k2Var[X1]13k2,

and so by Chebyshev’s inequality, we have

[|w|x||k]Var[w]k213.

Finally, quantumly, the algorithm is known as the quantum approximate counting algorithm [8], and the upper bound follows directly.

Then, it remains to prove the lower bounds. Deterministically, the problem is easiest when k is largest, so it suffices to prove the lower bound when k=n/4. Once we have queried n/21 bits of the bitstring – let’s say we observed w ones – there are still n/2+1 bits left to query. Then, we know that the true Hamming weight must be between w and w+n/2+1. Since this interval is larger than 2k, we cannot guarantee that whatever number we output is at most k away from the true Hamming weight. Thus, we need to make at least n/2Ω(n) queries.

In the randomized setting, we use [7, Lemma 26]. If k=n, we need at least Ω(n) queries. Since the problem becomes more difficult when k decreases, this proves the lower bound for all kn. On the other hand, if k>n, then we define nΘ((n/k)2). For any bitstring x{0,1}n, we define a bitstring x of length Θ(n) by duplicating all the bits of x a total of n/nΘ(k2/n) times. Then, a Hamming weight estimation algorithm with precision k will find an approximation of the Hamming weight of x with precision k, which means that it outputs an approximation of the Hamming weight of x with precision Θ(k/(k2/n))=Θ(n/k)=Θ(n). Thus, this algorithm must query x at least Ω(n)=Ω((n/k)2) times.

Finally, in the quantum setting, the result follows easily from [3]. For k=1, the hardness already follows from the majority function, whose hardness was proved in [6], and the hardness of the general case was basically proved in [29], even though not phrased as such.