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.
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.
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.
Given oracle access to an unknown unitary U=eiH , the fractional query problem asks how many queries are required to implement a noninteger power Ut=eitH, 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(δ1logε1) queries for approximation error ε. We prove a matching lower bound for arbitrary query algorithms. Our argument reduces any N-query circuit to the approximation of eitθ by a trigonometric polynomial with degree bounded by O(N), together with Remez inequality. This allows us to establish the lower bound of Ωτ(δ1logε1). Consequently, the optimal query complexity for fractional query problem is Θτ(δ1logε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) 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.
Determining whether every trajectory of the linear system x˙=Ax converges to zero (or, equivalently, whether A is Hurwitz stable) is a fundamental problem in control theory. It arises, for example, in verifying the stability of feedback controllers and state observers, as well as of linearized dynamical models. We study the quantum query complexity of deciding whether a matrix A∈Cn×n is Hurwitz stable, given an exact normalized block-encoding of A. The query complexity is characterized in terms of the system dimension n and a supplied lower bound 0<ν≤ωA on the imaginary-axis distance ωA:=mint∈Rσmin(A−itI), where σmin(A) is the smallest singular value of A. We prove a query-complexity lower bound of Ω(n/ν), which holds even when A is restricted to be real and diagonal. For general matrices with nonzero ωA, we encode an approximation of the right-half-plane spectral projector sign+(A):=(I+sign(A))/2 as a block of a matrix inverse, where A is Hurwitz if and only if the projector is zero. To test this, we produce a quantum algorithm which determines if a (β,b,1/(4n))-block-encoded projector matrix (like sign+(A)) is zero or not; for constant success probability, it has complexity Θ(βn). When the zero test is applied to specific approximations of sign+(A), this yields an upper bound of O(nν−2log(n/ν)) queries in the general case, and O(nν−1logn) when A is Hermitian or normal. The latter upper bound matches the lower bound up to a logarithmic factor. Thus the dimension dependence of quantum Hurwitz testing is nearly optimal, while the remaining factor in the non-normal case isolates an open conditioning gap.
We show that the query complexity of preparing f ( H )| ψ 0 ⟩ is controlled by the optimal L 2 ( μ ) polynomial approximation degree of f , where μ is the spectral measure induced by ( H , | ψ 0 ⟩). Equivalently, the minimal number of queries is bounded below by the smallest Krylov–Favard truncation achieving error ε and bounded above, up to QSVT normalization overhead, by a linear function of that degree. This state-aware formulation sharpens worst-case bounds, unifies orthogonal-polynomial Krylov methods with quantum query complexity, and highlights how input-dependent spectral structure can yield substantial savings over uniform approximation schemes.
We study how to compute f(A)b on a quantum computer, where A is Hermitian. When f is nonsmooth or has localized difficulty in the spectrum, classical numerical linear algebra approximates it with rational functions rather than polynomials.
We propose the Cayley transform, parameterized by σ∈R and γ>0, as an alternative to the standard quantum access model. The two parameters let one concentrate accuracy where f is difficult, which standard models can achieve only by raising the polynomial degree globally. This transformation converts Hermitian matrices to unitaries, allowing generalized quantum signal processing to apply Laurent polynomials bounded on the unit circle.
We compare three access models (block encoding, matrix exponential, and Cayley encoding) in terms of query complexity and of the cost of their circuit realization. When the difficulty of f is localized in the spectrum, the Cayley encoding reduces the required degree by a factor of three to four, and it represents the shifted resolvent exactly at degree one. For spectral projectors, the standard models cannot reach the target accuracy at fixed degree, because their approximants cannot concentrate resolution near the discontinuity.
Realizing the Cayley encoding from a block encoding requires solving a shifted linear system, whose cost offsets its query-complexity gain over the standard models. For structured matrices arising in practice, however, low-depth circuits for the encoding can be constructed directly, and the gain is preserved at the circuit level.