We present a novel technique, based on the Jensen-Shannon divergence from information theory, to prove lower bounds on the query complexity of sampling algorithms that approximate functions over arbitrary domain and range. Unlike previous methods, our technique does not use a reduction from a decision promise problem. As a result, it gives stronger bounds for functions that possess a large set of inputs, each two of which exhibit a gap in the function value.We demonstrate the technique with new query complexity lower bounds for three fundamental problems: (1) the "election problem", for which we obtain a quadratic improvement over previous bounds, (2) low rank matrix approximation, for which we prove the first lower bounds, showing that the algorithms given for this problem are almost optimal, and (3) matrix reconstruction.In addition, we introduce a new method for proving lower bounds on the expected query complexity of functions, using the Kullback-Leibler divergence. We demonstrate its use by a simple query complexity lower bound for the mean.
We present a novel technique, based on the Jensen-Shannon divergence from information theory, to prove lower bounds on the query complexity of sampling algorithms that approximate functions over arbitrary domain and range. Unlike previous methods, our technique does not use a reduction from a decision promise problem. As a result, it gives stronger bounds for functions that possess a large set of inputs, each two of which exhibit a gap in the function value.We demonstrate the technique with new query complexity lower bounds for three fundamental problems: (1) the "election problem", for which we obtain a quadratic improvement over previous bounds, (2) low rank matrix approximation, for which we prove the first lower bounds, showing that the algorithms given for this problem are almost optimal, and (3) matrix reconstruction.In addition, we introduce a new method for proving lower bounds on the expected query complexity of functions, using the Kullback-Leibler divergence. We demonstrate its use by a simple query complexity lower bound for the mean.
We present a novel technique, based on the Jensen-Shannon divergence from information theory, to prove lower bounds on the query complexity of sampling algorithms that approximate functions over arbitrary domain and range. Unlike previous methods, our technique does not use a reduction from a decision promise problem. As a result, it gives stronger bounds for functions that possess a large set of inputs, each two of which exhibit a gap in the function value.We demonstrate the technique with new query complexity lower bounds for three fundamental problems: (1) the election problem, for which we obtain a quadratic improvement over previous bounds, (2) low rank matrix approximation, for which we prove the first lower bounds, showing that the algorithms given for this problem are almost optimal, and (3) matrix reconstruction.In addition, we introduce a new method for proving lower bounds on the expected query complexity of functions, using the Kullback-Leibler divergence. We demonstrate its use by a simple query complexity lower bound for the mean.
Abstract. The polynomial method by Beals, Buhrman, Cleve, Mosca, and de Wolf (FOCS 1998; [ J. ACM, 48 (2001), pp. 778–797]) and the adversary method by Ambainis (STOC 2000; [ J. Comput. System Sci., 64 (2002), pp. 750–767]) and the compressed oracle method by Zhandry [ Proceedings of the 39 th CRYPTO, 2019, pp. 239–268] have been shown to be powerful in proving quantum query lower bounds for a wide variety of problems. In this paper, we propose a new method for proving quantum query lower bounds by a quantum sample-to-query lifting theorem, which is from an information theory perspective. Using this method, we obtain the following new results: (1) A quadratic relation between quantum sample and query complexities regarding quantum property testing, which is optimal and saturated by quantum state discrimination. Here, the sample complexity is measured given sample access to the quantum state to be tested, while the query complexity is measured given query access to an oracle that block-encodes the quantum state. (2) A matching lower bound [Formula: see text] for quantum Gibbs sampling at inverse temperature [Formula: see text] ([Formula: see text] suppresses logarithmic factors), showing that the quantum Gibbs sampler by Gilyén, Su, Low, and Wiebe [ Proceedings of the 51 st STOC, 2019, pp. 193–204] is optimal. (3) A new lower bound [Formula: see text] for the entanglement entropy problem with gap [Formula: see text], which was recently studied by She and Yuen [ Proceedings of the 14 th ITCS, 2023, pp. 96:1–96:17]. (4) A series of quantum query lower bounds for matrix spectrum testing, based on the sample lower bounds for quantum state spectrum testing by O’Donnell and Wright (STOC 2015; [ Comm. Math. Phys., 387 (2021), pp. 1–95]). In addition, we provide unified proofs for some known lower bounds that have been proven previously via different techniques, including those for phase/amplitude estimation and Hamiltonian simulation.
We define a canonical version of the recursive Fourier sampling problem from quantum complexity theory, and systematically address a variety of its computational properties, including quantum query complexity, classical randomized query complexity, polynomial degree, and circuit size. Our analysis yields improvements for several of the known upper and lower bounds with regard to these complexity measures.
For quantum query complexity, we define an explicit reduced-query quantum algorithm for the problem, and recursively construct a quantum circuit that implements the algorithm. For classical query complexity, we give new proofs of the known lower bounds that improve the constants, and we give complete proofs of the complexity class separations relative to oracles, that follow from these bounds. For polynomial degree, we construct an exactly representing real polynomial of extremely low degree, and extend it to representations over other Fields. We show that this degree is exactly optimal, even for a 2 weakly-representing polynomial. For circuit size, we construct a small depth-two circuit for the non-recursive version of the problem, and we show that the size is optimal even if the depth is not restricted. We also prove asymptotically matching upper and lower bounds on circuit size for the full recursive version of the problem when the depth is restricted to two.
To prove the tight results for polynomial degree and circuit size we introduce and define a general notion of reduction for both polynomials and circuits that represent boolean functions on a partial domain. We also introduce and define, separately, a new measure of circuit complexity called effort.
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.
We study the query complexity of Boolean functions f:{0,1}n→{0,1} in the noisy query model introduced by Feige, Raghavan, Peleg and Upfal [SICOMP 1994]. In this model, an algorithm can adaptively query the bits of an input vector, but each query result is independently flipped with constant probability p∈(0,1/2); repeated queries are allowed. The noisy query complexity Np(f) of a function f is defined as the minimum expected number of queries needed to compute f(x) with error probability at most 1/3, for the worst case input x. We prove a general lower bound on Np(f) based on degree statistics of certain subgraphs of the Boolean hypercube. This is the first general lower bound beyond those implied by the simple observation that Np(f) is lower bounded by the randomized query complexity. We show that this recovers (up to a constant factor) most previously known lower bounds on the noisy query complexity of Boolean functions, providing a unified framework for understanding these results and simplifying the proofs in several cases. Furthermore, this resolves in the affirmative an open problem of Gu, Li and Xu [COLT 2025] that Np(f)=Ω(I(f)logI(f)), where I(f) denotes the total influence of f. We also apply our general lower bound to obtain tight bounds on the noisy query complexity for several new functions.
We prove lower bounds on complexity measures, such as the approximate degree of a Boolean function and the approximate rank of a Boolean matrix, using quantum arguments. We prove these lower bounds using a quantum query algorithm for the combinatorial group testing problem. We show that for any function f, the approximate degree of computing the OR of n copies of f is Omega(sqrt n) times the approximate degree of f, which is optimal. No such general result was known prior to our work, and even the lower bound for the OR of ANDs function was only resolved in 2013. We then prove an analogous result in communication complexity, showing that the logarithm of the approximate rank (or more precisely, the approximate gamma-2 norm) of F: X x Y to 0,1 grows by a factor of Omega (sqrtn) when we take the OR of n copies of F, which is also essentially optimal. As a corollary, we give a new proof of Razborov's celebrated Omega(sqrtn) lower bound on the quantum communication complexity of the disjointness problem. Finally, we generalize both these results from composition with the OR function to composition with arbitrary symmetric functions, yielding nearly optimal lower bounds in this setting as well.