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

arXiv:1712.06349 · International Congress of Mathematicians (ICM)

UNDERSTANDING QUANTUM ALGORITHMS VIA QUERY COMPLEXITY

Andris Ambainis

Published May 1, 2019• 65 citations
arXivHTMLPDF

Abstract

Query complexity is a model of computation in which we have to compute a function $f(x_1, \ldots, x_N)$ of variables $x_i$ which can be accessed via queries. The complexity of an algorithm is measured by the number of queries that it makes. Query complexity is widely used for studying quantum algorithms, for two reasons. First, it includes many of the known quantum algorithms (including Grover's quantum search and a key subroutine of Shor's factoring algorithm). Second, one can prove lower bounds on the query complexity, bounding the possible quantum advantage. In the last few years, there have been major advances on several longstanding problems in the query complexity. In this talk, we survey these results and related work, including: - the biggest quantum-vs-classical gap for partial functions (a problem solvable with 1 query quantumly but requiring $Ω(\sqrt{N})$ queries classically); - the biggest quantum-vs-determistic and quantum-vs-probabilistic gaps for total functions (for example, a problem solvable with $M$ queries quantumly but requiring $\tildeΩ(M^{2.5})$ queries probabilistically); - the biggest probabilistic-vs-deterministic gap for total functions (a problem solvable with $M$ queries probabilistically but requiring $\tildeΩ(M^{2})$ queries deterministically); - the bounds on the gap that can be achieved for subclasses of functions (for example, symmetric functions); - the connections between query algorithms and approximations by low-degree polynomials.

DOI
10.1142/9789813272880_0181

Related papers

THEORETICAL FOUNDATIONS OF CLASSICAL AND QUANTUM QUERY MODELS: COMPLEXITY, LOWER BOUNDS, AND POLYNOMIAL-SPECTRAL INTERPLAY

Medak Srinivas

Query complexity provides a basic framework to quantify the inherent computational cost of functions in the model where access to the input is limited to oracle queries. In this paper, we provide a detailed discussion of classical and quantum models of inquiry, emphasizing the structural differences and the common mathematical basis. We consider deterministic, randomized and quantum query complexities and highlight key techniques to prove lower bounds such as adversarial techniques, polynomial approximations and hybrid arguments . The main theme of this paper is the polynomial-spectral relation which underlies both the classical and the quantum models. In the classical setting, the decision tree complexity is closely related to the degree of real polynomials representing Boolean functions. In the quantum setting, the relation involves the spectral properties of the operators controlling quantum query algorithms, and gives deep insights into quantum accelerations. We study tight bounds for basic problems such as search and element distinctness, proving separations between classical and quantum query complexity. The present study uses methods from approximation theory, linear algebra and spectrum analysis to build a foundation for a complete understanding of the power and limitations of query-based computation.

Iterative International Publishers eBooks•May 1, 2026•0 citations

Pseudo-deterministic Quantum Algorithms

Hugo Aaronson, Tom Gur, Jiawei Li

We initiate a systematic study of pseudo-deterministic quantum algorithms. These are quantum algorithms that, for any input, output a canonical solution with high probability. Focusing on the query complexity model, our main contributions include the following complexity separations, which require new lower bound techniques specifically tailored to pseudo-determinism: - We exhibit a problem, Avoid One Encrypted String (AOES), whose classical randomized query complexity is $O(1)$ but is maximally hard for pseudo-deterministic quantum algorithms ($Ω(N)$ query complexity). - We exhibit a problem, Quantum-Locked Estimation (QL-Estimation), for which pseudo-deterministic quantum algorithms admit an exponential speed-up over classical pseudo-deterministic algorithms ($O(\log(N))$ vs. $Θ(\sqrt{N})$), while the randomized query complexity is $O(1)$. Complementing these separations, we show that for any total problem $R$, pseudo-deterministic quantum algorithms admit at most a quintic advantage over deterministic algorithms, i.e., $D(R) = \tilde O(psQ(R)^5)$. On the algorithmic side, we identify a class of quantum search problems that can be made pseudo-deterministic with small overhead, including Grover search, element distinctness, triangle finding, $k$-sum, and graph collision.

quant-pharXiv:2602.17647•Feb 20, 2026•1 citation

Lower bounds on quantum query complexity for symmetric functions

Rajat Mittal, Sanjay S Nair, Sunayana Patro

One of the main reasons for query model's prominence in quantum complexity is the presence of concrete lower bounding techniques: polynomial method and adversary method. There have been considerable efforts to not just give lower bounds using these methods but even to compare and relate them. We explore the value of these bounds on quantum query complexity for the class of symmetric functions, arguably one of the most natural and basic set of Boolean functions. We show (using the recently introduced spectral sensitivity) that both these bounds (positive adversary and approximate degree) give the same value for every total symmetric Boolean function. We also look at the quantum query complexity of Gap Majority, a partial symmetric function. It has gained importance recently in regard to understanding the composition of randomized query complexity. We characterize the quantum query complexity of Gap Majority and show a lower bound on noisy randomized query complexity (Ben-David and Blais, FOCS 2020) in terms of quantum query complexity. In addition, we study how large certificate complexity and block sensitivity can be as compared to sensitivity (even up to constant factors) for symmetric functions. We show tight separations, i.e., give upper bound on possible separations and construct functions achieving the same.

•Oct 25, 2021•0 citations

Tight bounds for hybrid quantum-classical query algorithms

Andris Ambainis, András Gilyén, Martins Kokainis

We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most $q$ oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation up to a precision $ε$ requires $Θ(\frac{1}{q ε^2})$ queries; (ii) (Unbiased) Amplitude estimation up to a precision $ε$ requires $Θ(\frac{p(1-p)}{q ε^2})$ queries; (iii) Search among $N$ items requires $Θ(\frac{N}{q})$ queries; (iv) Two level AND-OR tree (AND of $m$ ORs, with $n$ inputs to each OR) requires $Θ(\frac{nm}{q})$ queries. All of these bounds are optimal up to a constant factor, for all $q$ from 1, corresponding to the classical complexity, to $Q(f)$, the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor. Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.

quant-pharXiv:2610.06803•Oct 6, 2026•0 citations

Query Complexity: Cryptography, Property Testing, and Lower Bounds Across Models

Weiqiang Yuan

Query complexity studies the amount of information about an input that is needed to solve a computational problem. This thesis investigates query complexity in several settings, with applications to cryptography and property testing, as well as connections to communication complexity and other computational models. In property testing, we study tolerant junta testing and establish the first superpolynomial quantum advantage for this problem: within a certain parameter regime, a quantum algorithm uses polynomially many queries, whereas every classical randomised algorithm requires quasipolynomially many queries. In cryptography, we study the average-case complexity of search problems. We show that verifiable delay functions do not exist in the random oracle model, and strengthen known barriers to constructing average-case hard TFNP problems from one-way functions. Finally, we study lower bounds and their behaviour across computational models. We prove new direct sum results for randomised parity decision trees. We also establish a new separation between query complexity measures of total Boolean functions and, through query-to-communication lifting, derive new communication lower bounds and lower bounds for unambiguous finite automata.

•Jan 1, 2026•0 citations

Pseudo-Deterministic Quantum Algorithms

Hugo Aaronson, Tom Gur, Jiawei Li

We initiate a systematic study of pseudo-deterministic quantum algorithms. These are quantum algorithms that, for any input, output a canonical solution with high probability. Focusing on the query complexity model, our main contributions include the following complexity separations, which require new lower bound techniques specifically tailored to pseudo-determinism: - We exhibit a problem, Avoid One Encrypted String (AOES), whose classical randomized query complexity is O(1) but is maximally hard for pseudo-deterministic quantum algorithms (Ω(N) query complexity). - We exhibit a problem, Quantum-Locked Estimation (QL-Estimation), for which pseudo-deterministic quantum algorithms admit an exponential speed-up over classical pseudo-deterministic algorithms (O(log(N)) vs. Θ(√N)), while the randomized query complexity is O(1). Complementing these separations, we show that for any total problem R, pseudo-deterministic quantum algorithms admit at most a quintic advantage over deterministic algorithms, i.e., 𝖣(R) = Õ(psQ(R)⁵). On the algorithmic side, we identify a class of quantum search problems that can be made pseudo-deterministic with small overhead, including Grover search, element distinctness, triangle finding, k-sum, and graph collision.

Leibniz international proceedings in informatics•Jan 1, 2026•0 citations
Query complexity is a model of computation in which we have to compute a function f(x1,…,xN)f(x_1, \ldots, x_N)f(x1​,…,xN​) of variables xix_ixi​ which can be accessed via queries. The complexity of an algorithm is measured by the number of queries that it makes. Query complexity is widely used for studying quantum algorithms, for two reasons. First, it includes many of the known quantum algorithms (including Grover's quantum search and a key subroutine of Shor's factoring algorithm). Second, one can prove lower bounds on the query complexity, bounding the possible quantum advantage. In the last few years, there have been major advances on several longstanding problems in the query complexity. In this talk, we survey these results and related work, including: - the biggest quantum-vs-classical gap for partial functions (a problem solvable with 1 query quantumly but requiring Ω(N)Ω(\sqrt{N})Ω(N​) queries classically); - the biggest quantum-vs-determistic and quantum-vs-probabilistic gaps for total functions (for example, a problem solvable with MMM queries quantumly but requiring Ω~(M2.5)\tildeΩ(M^{2.5})Ω~(M2.5) queries probabilistically); - the biggest probabilistic-vs-deterministic gap for total functions (a problem solvable with MMM queries probabilistically but requiring Ω~(M2)\tildeΩ(M^{2})Ω~(M2) queries deterministically); - the bounds on the gap that can be achieved for subclasses of functions (for example, symmetric functions); - the connections between query algorithms and approximations by low-degree polynomials.
Query complexity provides a basic framework to quantify the inherent computational cost of functions in the model where access to the input is limited to oracle queries. In this paper, we provide a detailed discussion of classical and quantum models of inquiry, emphasizing the structural differences and the common mathematical basis. We consider deterministic, randomized and quantum query complexities and highlight key techniques to prove lower bounds such as adversarial techniques, polynomial approximations and hybrid arguments . The main theme of this paper is the polynomial-spectral relation which underlies both the classical and the quantum models. In the classical setting, the decision tree complexity is closely related to the degree of real polynomials representing Boolean functions. In the quantum setting, the relation involves the spectral properties of the operators controlling quantum query algorithms, and gives deep insights into quantum accelerations. We study tight bounds for basic problems such as search and element distinctness, proving separations between classical and quantum query complexity. The present study uses methods from approximation theory, linear algebra and spectrum analysis to build a foundation for a complete understanding of the power and limitations of query-based computation.
We initiate a systematic study of pseudo-deterministic quantum algorithms. These are quantum algorithms that, for any input, output a canonical solution with high probability. Focusing on the query complexity model, our main contributions include the following complexity separations, which require new lower bound techniques specifically tailored to pseudo-determinism: - We exhibit a problem, Avoid One Encrypted String (AOES), whose classical randomized query complexity is O(1)O(1)O(1) but is maximally hard for pseudo-deterministic quantum algorithms (Ω(N)Ω(N)Ω(N) query complexity). - We exhibit a problem, Quantum-Locked Estimation (QL-Estimation), for which pseudo-deterministic quantum algorithms admit an exponential speed-up over classical pseudo-deterministic algorithms (O(log⁡(N))O(\log(N))O(log(N)) vs. Θ(N)Θ(\sqrt{N})Θ(N​)), while the randomized query complexity is O(1)O(1)O(1). Complementing these separations, we show that for any total problem RRR, pseudo-deterministic quantum algorithms admit at most a quintic advantage over deterministic algorithms, i.e., D(R)=O~(psQ(R)5)D(R) = \tilde O(psQ(R)^5)D(R)=O~(psQ(R)5). On the algorithmic side, we identify a class of quantum search problems that can be made pseudo-deterministic with small overhead, including Grover search, element distinctness, triangle finding, kkk-sum, and graph collision.
One of the main reasons for query model's prominence in quantum complexity is the presence of concrete lower bounding techniques: polynomial method and adversary method. There have been considerable efforts to not just give lower bounds using these methods but even to compare and relate them. We explore the value of these bounds on quantum query complexity for the class of symmetric functions, arguably one of the most natural and basic set of Boolean functions. We show (using the recently introduced spectral sensitivity) that both these bounds (positive adversary and approximate degree) give the same value for every total symmetric Boolean function. We also look at the quantum query complexity of Gap Majority, a partial symmetric function. It has gained importance recently in regard to understanding the composition of randomized query complexity. We characterize the quantum query complexity of Gap Majority and show a lower bound on noisy randomized query complexity (Ben-David and Blais, FOCS 2020) in terms of quantum query complexity. In addition, we study how large certificate complexity and block sensitivity can be as compared to sensitivity (even up to constant factors) for symmetric functions. We show tight separations, i.e., give upper bound on possible separations and construct functions achieving the same.
We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most qqq oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation up to a precision εεε requires Θ(1qε2)Θ(\frac{1}{q ε^2})Θ(qε21​) queries; (ii) (Unbiased) Amplitude estimation up to a precision εεε requires Θ(p(1−p)qε2)Θ(\frac{p(1-p)}{q ε^2})Θ(qε2p(1−p)​) queries; (iii) Search among NNN items requires Θ(Nq)Θ(\frac{N}{q})Θ(qN​) queries; (iv) Two level AND-OR tree (AND of mmm ORs, with nnn inputs to each OR) requires Θ(nmq)Θ(\frac{nm}{q})Θ(qnm​) queries. All of these bounds are optimal up to a constant factor, for all qqq from 1, corresponding to the classical complexity, to Q(f)Q(f)Q(f), the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor. Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.
Query complexity studies the amount of information about an input that is needed to solve a computational problem. This thesis investigates query complexity in several settings, with applications to cryptography and property testing, as well as connections to communication complexity and other computational models. In property testing, we study tolerant junta testing and establish the first superpolynomial quantum advantage for this problem: within a certain parameter regime, a quantum algorithm uses polynomially many queries, whereas every classical randomised algorithm requires quasipolynomially many queries. In cryptography, we study the average-case complexity of search problems. We show that verifiable delay functions do not exist in the random oracle model, and strengthen known barriers to constructing average-case hard TFNP problems from one-way functions. Finally, we study lower bounds and their behaviour across computational models. We prove new direct sum results for randomised parity decision trees. We also establish a new separation between query complexity measures of total Boolean functions and, through query-to-communication lifting, derive new communication lower bounds and lower bounds for unambiguous finite automata.
We initiate a systematic study of pseudo-deterministic quantum algorithms. These are quantum algorithms that, for any input, output a canonical solution with high probability. Focusing on the query complexity model, our main contributions include the following complexity separations, which require new lower bound techniques specifically tailored to pseudo-determinism: - We exhibit a problem, Avoid One Encrypted String (AOES), whose classical randomized query complexity is O(1) but is maximally hard for pseudo-deterministic quantum algorithms (Ω(N) query complexity). - We exhibit a problem, Quantum-Locked Estimation (QL-Estimation), for which pseudo-deterministic quantum algorithms admit an exponential speed-up over classical pseudo-deterministic algorithms (O(log(N)) vs. Θ(√N)), while the randomized query complexity is O(1). Complementing these separations, we show that for any total problem R, pseudo-deterministic quantum algorithms admit at most a quintic advantage over deterministic algorithms, i.e., 𝖣(R) = Õ(psQ(R)⁵). On the algorithmic side, we identify a class of quantum search problems that can be made pseudo-deterministic with small overhead, including Grover search, element distinctness, triangle finding, k-sum, and graph collision.