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:2311.06999 · ACM Symposium on Theory of Computing (STOC)

Quantum and Classical Query Complexities of Functions of Matrices

Ashley Montanaro, Changpeng Shao

Published Jun 10, 2024• 17 citations
arXivHTMLPDF

Abstract

Let A be an s-sparse Hermitian matrix, f(x) be a univariate function, and i, j be two indices. In this work, we investigate the query complexity of approximating i f(A) j. We show that for any continuous function f(x):[−1,1]→ [−1,1], the quantum query complexity of computing i f(A) j± ε/4 is lower bounded by Ω(degε(f)). The upper bound is at most quadratic in degε(f) and is linear in degε(f) under certain mild assumptions on A. Here the approximate degree degε(f) is the minimum degree such that there is a polynomial of that degree approximating f up to additive error ε in the interval [−1,1]. We also show that the classical query complexity is lower bounded by Ω((s/2)(deg2ε(f)−1)/6) for any s≥ 4. Our results show that the quantum and classical separation is exponential for any continuous function of sparse Hermitian matrices, and also imply the optimality of implementing smooth functions of sparse Hermitian matrices by quantum singular value transformation. The main techniques we used are the dual polynomial method for functions over the reals, linear semi-infinite programming, and tridiagonal matrices.

DOI
10.1145/3618260.3649665

Related papers

Implementing smooth functions of a Hermitian matrix on a quantum computer

Sathyawageeswar Subramanian, Stephen Brierley, Richard Jozsa

Abstract We consider methods for implementing smooth functions f(A) of a sparse Hermitian matrix A on a quantum computer, and analyse a further combination of these techniques which has advantages of simplicity and resource consumption in some cases. Our construction uses the linear combination of unitaries method with Chebyshev polynomial approximations. The query complexity we obtain is  log C ϵ where ϵ is the approximation precision, and C > 0 is an upper bound on the magnitudes of the derivatives of the function f over the domain of interest. The success probability depends on the 1-norm of the Taylor series coefficients of f, the sparsity d of the matrix, and inversely on the smallest singular value of the target matrix f(A).

arXiv:1806.06885•Journal of Physics Communications•May 30, 2019•22 citations

Quantum lower bounds for convex optimization and real matrix-vector query problems

Andrew M. Childs

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 $\mathbb{R}^n$ with evaluation and membership queries is $\tildeΩ(n)$, nearly matching the best known upper bound. In particular, we show this even for quadratic minimization, which is equivalent to inverting an $n \times 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.

quant-pharXiv:2609.05679•Sep 8, 2026•1 citation

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

Optimal query complexity for fractional quantum evolution

Anthony Yuezhang Liu, Adam Wesołowski, Jayne Thompson +2 more

Given oracle access to an unknown unitary $U=e^{iH}$ , the fractional query problem asks how many queries are required to implement a noninteger power $U^t=e^{itH}$, $0<t<1$, when the spectrum is separated from the branch cut by a gap $δ$. Quantum singular value transformation gives an upper bound of $O\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$ queries for approximation error $\varepsilon$. We prove a matching lower bound for arbitrary query algorithms. Our argument reduces any $N$-query circuit to the approximation of $e^{itθ}$ by a trigonometric polynomial with degree bounded by $O(N)$, together with Remez inequality. This allows us to establish the lower bound of $Ω_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$. Consequently, the optimal query complexity for fractional query problem is $Θ_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$, showing that the known QSVT construction is asymptotically optimal. We also give an alternative lower bound proof based on constructing a linear functional that annihilates the approximant space, yielding a $Ω_τ\!\left(\log\frac{1}{\varepsilon}\right)$ bound uniform to $δ$.

quant-pharXiv:2610.01940•Oct 2, 2026•0 citations

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

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
Let A be an s-sparse Hermitian matrix, f(x) be a univariate function, and i, j be two indices. In this work, we investigate the query complexity of approximating i f(A) j. We show that for any continuous function f(x):[−1,1]→ [−1,1], the quantum query complexity of computing i f(A) j± ε/4 is lower bounded by Ω(degε(f)). The upper bound is at most quadratic in degε(f) and is linear in degε(f) under certain mild assumptions on A. Here the approximate degree degε(f) is the minimum degree such that there is a polynomial of that degree approximating f up to additive error ε in the interval [−1,1]. We also show that the classical query complexity is lower bounded by Ω((s/2)(deg2ε(f)−1)/6) for any s≥ 4. Our results show that the quantum and classical separation is exponential for any continuous function of sparse Hermitian matrices, and also imply the optimality of implementing smooth functions of sparse Hermitian matrices by quantum singular value transformation. The main techniques we used are the dual polynomial method for functions over the reals, linear semi-infinite programming, and tridiagonal matrices.
Abstract We consider methods for implementing smooth functions f(A) of a sparse Hermitian matrix A on a quantum computer, and analyse a further combination of these techniques which has advantages of simplicity and resource consumption in some cases. Our construction uses the linear combination of unitaries method with Chebyshev polynomial approximations. The query complexity we obtain is  log C ϵ where ϵ is the approximation precision, and C > 0 is an upper bound on the magnitudes of the derivatives of the function f over the domain of interest. The success probability depends on the 1-norm of the Taylor series coefficients of f, the sparsity d of the matrix, and inversely on the smallest singular value of the target matrix f(A).
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\mathbb{R}^nRn with evaluation and membership queries is Ω~(n)\tildeΩ(n)Ω~(n), nearly matching the best known upper bound. In particular, we show this even for quadratic minimization, which is equivalent to inverting an n×nn \times nn×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 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.
Given oracle access to an unknown unitary U=eiHU=e^{iH}U=eiH , the fractional query problem asks how many queries are required to implement a noninteger power Ut=eitHU^t=e^{itH}Ut=eitH, 0<t<10<t<10<t<1, when the spectrum is separated from the branch cut by a gap δδδ. Quantum singular value transformation gives an upper bound of O ⁣(1δlog⁡1ε)O\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)O(δ1​logε1​) queries for approximation error ε\varepsilonε. We prove a matching lower bound for arbitrary query algorithms. Our argument reduces any NNN-query circuit to the approximation of eitθe^{itθ}eitθ by a trigonometric polynomial with degree bounded by O(N)O(N)O(N), together with Remez inequality. This allows us to establish the lower bound of Ωτ ⁣(1δlog⁡1ε)Ω_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)Ωτ​(δ1​logε1​). Consequently, the optimal query complexity for fractional query problem is Θτ ⁣(1δlog⁡1ε)Θ_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)Θτ​(δ1​logε1​), showing that the known QSVT construction is asymptotically optimal. We also give an alternative lower bound proof based on constructing a linear functional that annihilates the approximant space, yielding a Ωτ ⁣(log⁡1ε)Ω_τ\!\left(\log\frac{1}{\varepsilon}\right)Ωτ​(logε1​) bound uniform to δδδ.
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.
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.