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

Computational Complexity

Quantum Query Complexity of Almost All Functions with Fixed On-set Size

Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita

Published Jun 21, 2016• 3 citations
Publisher
DOI
10.1007/s00037-016-0139-6

Related papers

Quantum Query Complexity of Boolean Functions with Small On-Sets

Andris Ambainis, Kazuo Iwama, Masaki Nakanishi +4 more

Lecture notes in computer science•Jan 1, 2008•11 citations

Average/Worst-Case Gap of Quantum Query Complexities by On-Set Size

Andris Ambainis, Kazuo Iwama, Masaki Nakanishi +4 more

This paper considers the query complexity of the functions in the family F_{N,M} of N-variable Boolean functions with onset size M, i.e., the number of inputs for which the function value is 1, where 1<= M <= 2^{N}/2 is assumed without loss of generality because of the symmetry of function values, 0 and 1. Our main results are as follows: (1) There is a super-linear gap between the average-case and worst-case quantum query complexities over F_{N,M} for a certain range of M. (2) There is no super-linear gap between the average-case and worst-case randomized query complexities over F_{N,M} for every M. (3) For every M bounded by a polynomial in N, any function in F_{N,M} has quantum query complexity Theta (sqrt{N}). (4) For every M=O(2^{cN}) with an arbitrary large constant c<1, any function in F_{N,M} has randomized query complexity Omega (N).

arXiv:0908.2468•Aug 18, 2009•9 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

On Exact Quantum Query Complexity

Ashley Montanaro, Richard Jozsa, Graeme Mitchison

arXiv:1111.0475•Algorithmica•Aug 29, 2013•48 citations

Classical and Quantum Query Complexity of Boolean Functions under Indefinite Causal Order

Alastair A. Abbott, Mehdi Mhalla, Pierre Pocreau

Computational models typically assume that operations are applied in a fixed sequential order.In recent years several works have looked at relaxing this assumption, considering computations without any fixed causal structure and showing that such "causally indefinite" computations can provide advantages in various tasks.Recently, the quantum query complexity of Boolean functions has been used as a tool to probe their computational power in a standard complexity theoretic framework, but no separation in exact query complexity has thus-far been found.In this paper, we investigate this problem starting with the simpler and fully classical notion of deterministic query complexity of Boolean functions, and using classical-deterministic processes -which may exhibit causal indefiniteness -as a generalised computational framework.We first show that the standard polynomial and certificate lower bounds of deterministic query complexity also hold in such generalised models.Then, we formulate a Boolean function for which causal indefiniteness permits a reduction in query complexity and show that this advantage can be amplified into a polynomial separation.Finally, with the insights gained in the classical-deterministic setting, we give a Boolean function whose quantum query complexity is reduced by causally indefinite computations.

arXiv:2506.05187•Electronic Proceedings in Theoretical Computer Science•Aug 19, 2025•4 citations

A lower bound on the quantum query complexity of read-once functions

Howard Barnum, Michael Saks

arXiv:quant-ph/0201007•Journal of Computer and System Sciences•May 15, 2004•71 citations
This paper considers the query complexity of the functions in the family F_{N,M} of N-variable Boolean functions with onset size M, i.e., the number of inputs for which the function value is 1, where 1<= M <= 2^{N}/2 is assumed without loss of generality because of the symmetry of function values, 0 and 1. Our main results are as follows: (1) There is a super-linear gap between the average-case and worst-case quantum query complexities over F_{N,M} for a certain range of M. (2) There is no super-linear gap between the average-case and worst-case randomized query complexities over F_{N,M} for every M. (3) For every M bounded by a polynomial in N, any function in F_{N,M} has quantum query complexity Theta (sqrt{N}). (4) For every M=O(2^{cN}) with an arbitrary large constant c<1, any function in F_{N,M} has randomized query complexity Omega (N).
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.
Computational models typically assume that operations are applied in a fixed sequential order.In recent years several works have looked at relaxing this assumption, considering computations without any fixed causal structure and showing that such "causally indefinite" computations can provide advantages in various tasks.Recently, the quantum query complexity of Boolean functions has been used as a tool to probe their computational power in a standard complexity theoretic framework, but no separation in exact query complexity has thus-far been found.In this paper, we investigate this problem starting with the simpler and fully classical notion of deterministic query complexity of Boolean functions, and using classical-deterministic processes -which may exhibit causal indefiniteness -as a generalised computational framework.We first show that the standard polynomial and certificate lower bounds of deterministic query complexity also hold in such generalised models.Then, we formulate a Boolean function for which causal indefiniteness permits a reduction in query complexity and show that this advantage can be amplified into a polynomial separation.Finally, with the insights gained in the classical-deterministic setting, we give a Boolean function whose quantum query complexity is reduced by causally indefinite computations.