Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Query Complexity in Expectation

Jędrzej Kaniewski, Troy Lee, Ronald de Wolf

Published Jan 1, 2015• 14 citations
Publisher
DOI
10.1007/978-3-662-47672-7_62

Related papers

Query complexity in expectation

Jędrzej Kaniewski, Troy Lee, Ronald de Wolf

We study the query complexity of computing a function f:{0,1}^n-->R_+ in expectation. This requires the algorithm on input x to output a nonnegative random variable whose expectation equals f(x), using as few queries to the input x as possible. We exactly characterize both the randomized and the quantum query complexity by two polynomial degrees, the nonnegative literal degree and the sum-of-squares degree, respectively. We observe that the quantum complexity can be unboundedly smaller than the classical complexity for some functions, but can be at most polynomially smaller for functions with range {0,1}. These query complexities relate to (and are motivated by) the extension complexity of polytopes. The linear extension complexity of a polytope is characterized by the randomized communication complexity of computing its slack matrix in expectation, and the semidefinite (psd) extension complexity is characterized by the analogous quantum model. Since query complexity can be used to upper bound communication complexity of related functions, we can derive some upper bounds on psd extension complexity by constructing efficient quantum query algorithms. As an example we give an exponentially-close entrywise approximation of the slack matrix of the perfect matching polytope with psd-rank only 2^{n^{1/2+epsilon}}. Finally, we show there is a precise sense in which randomized/quantum query complexity in expectation corresponds to the Sherali-Adams and Lasserre hierarchies, respectively.

arXiv:1411.7280•Nov 26, 2014•5 citations

The query complexity of order-finding

Richard Cleve

Information and Computation•May 1, 2004•18 citations

On the query computation and verification of functions

Hirakendu Das, Ashkan Jafarpour, Alon Orlitsky +2 more

In the query model of multi-variate function computation, the values of the variables are queried sequentially, in an order that may depend on previously revealed values, until the function's value can be determined. The function's computation query complexity is the lowest expected number of queries required by any query order. Instead of computation, it is often easier to consider verification, where the value of the function is given and the queries aim to verify it. The lowest expected number of queries necessary is the function's verification query complexity. We show that for all symmetric functions of independent binary random variables, the computation and verification complexities coincide. This provides a simple method for finding the query complexity and the optimal query order for computing many functions. We also show that if the symmetry condition is removed, there are functions whose verification complexity is strictly lower than their computation complexity, and mention that the same holds when the independence or binary conditions are removed.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2012•6 citations

Algorithmic Complexity

Fabio Benatti

Theoretical and mathematical physics•Jan 1, 2009•2 citations

Zero-error expectation equals amortized query complexity

Daiki Suruga

This paper investigates the direct sum question for expected randomized and distributional query complexity. Our main result gives an exact characterization of the amortized expected randomized query complexity. For any total relation $f$ and any error tolerance $\varepsilon \in [0,1]$, we prove \[ \lim_{n \to \infty} \frac{\overline{R}_\varepsilon(f^n)}{n} = (1 - \varepsilon) \overline{R}_0(f). \] Thus the amortization converts bounded-error into zero error with the exact multiplicative factor $1-\varepsilon$. We also prove corresponding liminf/limsup bounds for worst-case randomized and distributional query complexity. These results improve prior direct-sum bounds that were known only up to constant factors or in restricted error regimes, and they resolve an open question posed by Blais and Brody (2019). Additionally for one-sided computation of the function $\operatorname{OR}_n \circ f$, we obtain analogous exact amortized identities for both expected and worst-case cost. As applications, we obtain separations between amortized and single-instance costs, including unbounded separations for distributional complexity and randomized relations, and a quadratic barrier for randomized total functions.

arXiv:2608.04152•Aug 4, 2026•0 citations

Quantum Submodular Maximization

Yonggang Jiang, Xiaoming Sun, Penghui Yao +3 more

We study the quantum query complexity of maximizing a non-negative submodular function, considering both the unconstrained setting and, for monotone functions, a cardinality constraint $k$ on an $n$-element ground set. In the exact reversible digital value-oracle model, our unconstrained algorithm achieves an expected $(1/2-\varepsilon)$-approximation using only $O_\varepsilon(\log n)$ queries. In contrast, any classical randomized algorithm that attains a fixed expected ratio above $1/4$ requires $Ω(n/\log n)$ queries (Li, Feldman, Kazemi, and Karbasi, 2022), establishing an exponential separation in query complexity. For cardinality-constrained maximization, we give a bounded-error quantum algorithm that achieves a $(1-1/e-\varepsilon)$-approximation using $\widetilde O_\varepsilon(\min\{\sqrt n,n/k\})$ queries. When $k=o(n)$, our algorithm achieves at least a quadratic speedup up to logarithmic factors over classical randomized algorithms (Mirzasoleiman, Badanidiyuru, Karbasi, Vondrák, and Krause, 2015; Peng and Rubinstein, 2025). Moreover, when $k=cn$ for any fixed rational $c<1-1/e-\varepsilon$, the query complexity reduces to $O_{\varepsilon,c}(\log n)$, yielding an exponential separation from the classical $Ω(n/\log n)$ lower bound (Li, Feldman, Kazemi, and Karbasi, 2022). We further prove quantum lower bounds of $\exp(Ω(\varepsilon^2n))$ queries for achieving a ratio beyond $1/2+\varepsilon$ without constraints, and $\exp(Ω(\varepsilon^2k))$ queries for exceeding $1-1/e+\varepsilon$ when $k/n\le\varepsilon$. These barriers demonstrate that quantum computation offers no exponential speedup at these approximation thresholds.

quant-pharXiv:2610.04560•Oct 6, 2026•0 citations
We study the query complexity of computing a function f:{0,1}^n-->R_+ in expectation. This requires the algorithm on input x to output a nonnegative random variable whose expectation equals f(x), using as few queries to the input x as possible. We exactly characterize both the randomized and the quantum query complexity by two polynomial degrees, the nonnegative literal degree and the sum-of-squares degree, respectively. We observe that the quantum complexity can be unboundedly smaller than the classical complexity for some functions, but can be at most polynomially smaller for functions with range {0,1}. These query complexities relate to (and are motivated by) the extension complexity of polytopes. The linear extension complexity of a polytope is characterized by the randomized communication complexity of computing its slack matrix in expectation, and the semidefinite (psd) extension complexity is characterized by the analogous quantum model. Since query complexity can be used to upper bound communication complexity of related functions, we can derive some upper bounds on psd extension complexity by constructing efficient quantum query algorithms. As an example we give an exponentially-close entrywise approximation of the slack matrix of the perfect matching polytope with psd-rank only 2^{n^{1/2+epsilon}}. Finally, we show there is a precise sense in which randomized/quantum query complexity in expectation corresponds to the Sherali-Adams and Lasserre hierarchies, respectively.
In the query model of multi-variate function computation, the values of the variables are queried sequentially, in an order that may depend on previously revealed values, until the function's value can be determined. The function's computation query complexity is the lowest expected number of queries required by any query order. Instead of computation, it is often easier to consider verification, where the value of the function is given and the queries aim to verify it. The lowest expected number of queries necessary is the function's verification query complexity. We show that for all symmetric functions of independent binary random variables, the computation and verification complexities coincide. This provides a simple method for finding the query complexity and the optimal query order for computing many functions. We also show that if the symmetry condition is removed, there are functions whose verification complexity is strictly lower than their computation complexity, and mention that the same holds when the independence or binary conditions are removed.
This paper investigates the direct sum question for expected randomized and distributional query complexity. Our main result gives an exact characterization of the amortized expected randomized query complexity. For any total relation fff and any error tolerance ε∈[0,1]\varepsilon \in [0,1]ε∈[0,1], we prove lim⁡n→∞R‾ε(fn)n=(1−ε)R‾0(f). \lim_{n \to \infty} \frac{\overline{R}_\varepsilon(f^n)}{n} = (1 - \varepsilon) \overline{R}_0(f). limn→∞​nRε​(fn)​=(1−ε)R0​(f). Thus the amortization converts bounded-error into zero error with the exact multiplicative factor 1−ε1-\varepsilon1−ε. We also prove corresponding liminf/limsup bounds for worst-case randomized and distributional query complexity. These results improve prior direct-sum bounds that were known only up to constant factors or in restricted error regimes, and they resolve an open question posed by Blais and Brody (2019). Additionally for one-sided computation of the function OR⁡n∘f\operatorname{OR}_n \circ fORn​∘f, we obtain analogous exact amortized identities for both expected and worst-case cost. As applications, we obtain separations between amortized and single-instance costs, including unbounded separations for distributional complexity and randomized relations, and a quadratic barrier for randomized total functions.
We study the quantum query complexity of maximizing a non-negative submodular function, considering both the unconstrained setting and, for monotone functions, a cardinality constraint kkk on an nnn-element ground set. In the exact reversible digital value-oracle model, our unconstrained algorithm achieves an expected (1/2−ε)(1/2-\varepsilon)(1/2−ε)-approximation using only Oε(log⁡n)O_\varepsilon(\log n)Oε​(logn) queries. In contrast, any classical randomized algorithm that attains a fixed expected ratio above 1/41/41/4 requires Ω(n/log⁡n)Ω(n/\log n)Ω(n/logn) queries (Li, Feldman, Kazemi, and Karbasi, 2022), establishing an exponential separation in query complexity. For cardinality-constrained maximization, we give a bounded-error quantum algorithm that achieves a (1−1/e−ε)(1-1/e-\varepsilon)(1−1/e−ε)-approximation using O~ε(min⁡{n,n/k})\widetilde O_\varepsilon(\min\{\sqrt n,n/k\})Oε​(min{n​,n/k}) queries. When k=o(n)k=o(n)k=o(n), our algorithm achieves at least a quadratic speedup up to logarithmic factors over classical randomized algorithms (Mirzasoleiman, Badanidiyuru, Karbasi, Vondrák, and Krause, 2015; Peng and Rubinstein, 2025). Moreover, when k=cnk=cnk=cn for any fixed rational c<1−1/e−εc<1-1/e-\varepsilonc<1−1/e−ε, the query complexity reduces to Oε,c(log⁡n)O_{\varepsilon,c}(\log n)Oε,c​(logn), yielding an exponential separation from the classical Ω(n/log⁡n)Ω(n/\log n)Ω(n/logn) lower bound (Li, Feldman, Kazemi, and Karbasi, 2022). We further prove quantum lower bounds of exp⁡(Ω(ε2n))\exp(Ω(\varepsilon^2n))exp(Ω(ε2n)) queries for achieving a ratio beyond 1/2+ε1/2+\varepsilon1/2+ε without constraints, and exp⁡(Ω(ε2k))\exp(Ω(\varepsilon^2k))exp(Ω(ε2k)) queries for exceeding 1−1/e+ε1-1/e+\varepsilon1−1/e+ε when k/n≤εk/n\le\varepsilonk/n≤ε. These barriers demonstrate that quantum computation offers no exponential speedup at these approximation thresholds.