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:2510.11786 · Physics Letters A

Krylov polynomials and quantum query complexity

Kiran Adhikari

Published Mar 21, 2026• 8 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1016/j.physleta.2026.131601

Related papers

Polynomials, Quantum Query Complexity, and Grothendieck's Inequality

Scott Aaronson, Andris Ambainis, Jānis Iraids +2 more

We show an equivalence between 1-query quantum algorithms and representations by degree-2 polynomials. Namely, a partial Boolean function f is computable by a 1-query quantum algorithm with error bounded by epsilon<1/2 iff f can be approximated by a degree-2 polynomial with error bounded by epsilon'<1/2. This result holds for two different notions of approximation by a polynomial: the standard definition of Nisan and Szegedy and the approximation by block-multilinear polynomials recently introduced by Aaronson and Ambainis [Aaronson/Ambainis, STOC 2015]. The proof uses Grothendieck's inequality to relate two matrix norms, with one norm corresponding to polynomial approximations and the other norm corresponding to quantum algorithms. We also show two results for polynomials of higher degree. First, there is a total Boolean function which requires ~Omega(n) quantum queries but can be represented by a block-multilinear polynomial of degree ~O(sqrt(n)). Thus, in the general case (for an arbitrary number of queries), block-multilinear polynomials are not equivalent to quantum algorithms. Second, for any constant degree k, the two notions of approximation by a polynomial (the standard and the block-multilinear) are equivalent. As a consequence, we solve an open problem from [Aaronson/Ambainis, STOC 2015], showing that one can estimate the value of any bounded degree-k polynomial p:{0,1}^n -> [-1,1] with O(n^{1-1/(2k)) queries.

arXiv:1511.08682•Leibniz international proceedings in informatics•Nov 27, 2015•31 citations

Constrained Optimal Polynomials for Quantum Linear System Solvers

Matthias Deiml, Daniel Peterseim

Quantum linear system solvers typically realize the inverse map as a polynomial transformation of the spectrum, so their practical cost hinges on implementing this transformation at a low polynomial degree. We introduce constrained optimal polynomials as a framework for this task, drawing on classical Krylov subspace theory. Within this framework, we develop two classes of solvers. Constrained Uniform Polynomial (CUP) solvers optimize the tradeoff between approximation accuracy and block encoding normalization under a uniform spectral model consistent with the available bounds. Constrained Adaptive Polynomial (CAP) solvers retain this structure but replace the uniform model with a probability measure reconstructed from spectral moments via a maximum entropy ansatz, where the moments are extracted from QSVT measurements. Numerical experiments under hardware and stochastic noise show that these methods achieve lower error than standard QSVT-based and Chebyshev-iteration-type solvers, particularly in noise-limited regimes. CUP offers robust performance under generic spectra, while CAP provides further improvement when the spectral structure can be exploited.

math.NACross-listedarXiv:2604.20513•Apr 23, 2026•1 citation

Quantum query complexity of Hurwitz stability testing

Maxwell Fitzsimmons, Mohamed Serry, Meenu Kumari +1 more

Determining whether every trajectory of the linear system $\dot{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\in\mathbb{C}^{n\times 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<ν\leq ω_A$ on the imaginary-axis distance $ω_A:=\min_{t\in\mathbb{R}}σ_{\min}(A-\mathrm{i}tI)$, where $σ_{\min}(A)$ is the smallest singular value of $A$. We prove a query-complexity lower bound of $Ω(\sqrt{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 $\operatorname{sign}^+(A):=(I+\operatorname{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/(4\sqrt{n}))$-block-encoded projector matrix (like $\operatorname{sign}^+(A)$) is zero or not; for constant success probability, it has complexity $Θ(β\sqrt{n})$. When the zero test is applied to specific approximations of $\operatorname{sign}^+(A)$, this yields an upper bound of $O(\sqrt{n}ν^{-2}\log(\sqrt{n}/ν))$ queries in the general case, and $O(\sqrt{n}ν^{-1}\log n)$ 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.

quant-pharXiv:2610.41180•Nov 2, 2026•0 citations

Orthogonal Quantum Krylov Diagonalisation

Hadi Rammal, Alexandre Perrin, Oumaya Ladhari +3 more

Quantum subspace-diagonalization methods, particularly Quantum Krylov Diagonalization (QKD), provide a promising route for computing low-energy spectra of quantum many-body Hamiltonians. However, existing quantum Krylov approaches rely on non-orthogonal Krylov bases, requiring overlap-matrix regularization that limits numerical stability and accuracy. In this work, we introduce an Orthogonal Quantum Krylov Diagonalization (OQKD) framework that reformulates the classical Lanczos recursion at the operator level, enabling an orthogonal quantum implementation of Krylov-subspace diagonalization. By expressing Lanczos vectors as polynomial transformations of the Hamiltonian, OQKD reproduces the orthogonality, tridiagonal structure, and convergence behavior of the classical Lanczos algorithm thus eliminating the need for overlap-matrix regularization. We further show that the required Lanczos polynomials can be implemented using block encoding and Generalized Quantum Signal Processing with the same asymptotic query complexity as Chebyshev-based QKD methods. Numerical simulations of the $J_1$--$J_2$ Heisenberg model confirm the classical Lanczos convergence and numerical stability of the proposed method, while the measurement-complexity scaling is established analytically. Building upon the OQKD framework, we then introduce a restarted state-preparation protocol that replaces a single high-degree polynomial transformation with a sequence of fixed low-degree transformations, maintaining an affordable block encoding success probability while retaining comparable convergence. These results establish OQKD as an orthogonal quantum analog of the classical Lanczos algorithm and identify the restarted protocol as a promising state-preparation strategy for Quantum Phase Estimation.

quant-pharXiv:2607.09476•Jul 13, 2026•3 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
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 show an equivalence between 1-query quantum algorithms and representations by degree-2 polynomials. Namely, a partial Boolean function f is computable by a 1-query quantum algorithm with error bounded by epsilon<1/2 iff f can be approximated by a degree-2 polynomial with error bounded by epsilon'<1/2. This result holds for two different notions of approximation by a polynomial: the standard definition of Nisan and Szegedy and the approximation by block-multilinear polynomials recently introduced by Aaronson and Ambainis [Aaronson/Ambainis, STOC 2015]. The proof uses Grothendieck's inequality to relate two matrix norms, with one norm corresponding to polynomial approximations and the other norm corresponding to quantum algorithms. We also show two results for polynomials of higher degree. First, there is a total Boolean function which requires ~Omega(n) quantum queries but can be represented by a block-multilinear polynomial of degree ~O(sqrt(n)). Thus, in the general case (for an arbitrary number of queries), block-multilinear polynomials are not equivalent to quantum algorithms. Second, for any constant degree k, the two notions of approximation by a polynomial (the standard and the block-multilinear) are equivalent. As a consequence, we solve an open problem from [Aaronson/Ambainis, STOC 2015], showing that one can estimate the value of any bounded degree-k polynomial p:{0,1}^n -> [-1,1] with O(n^{1-1/(2k)) queries.
Quantum linear system solvers typically realize the inverse map as a polynomial transformation of the spectrum, so their practical cost hinges on implementing this transformation at a low polynomial degree. We introduce constrained optimal polynomials as a framework for this task, drawing on classical Krylov subspace theory. Within this framework, we develop two classes of solvers. Constrained Uniform Polynomial (CUP) solvers optimize the tradeoff between approximation accuracy and block encoding normalization under a uniform spectral model consistent with the available bounds. Constrained Adaptive Polynomial (CAP) solvers retain this structure but replace the uniform model with a probability measure reconstructed from spectral moments via a maximum entropy ansatz, where the moments are extracted from QSVT measurements. Numerical experiments under hardware and stochastic noise show that these methods achieve lower error than standard QSVT-based and Chebyshev-iteration-type solvers, particularly in noise-limited regimes. CUP offers robust performance under generic spectra, while CAP provides further improvement when the spectral structure can be exploited.
Determining whether every trajectory of the linear system x˙=Ax\dot{x}=Axx˙=Ax converges to zero (or, equivalently, whether AAA 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×nA\in\mathbb{C}^{n\times n}A∈Cn×n is Hurwitz stable, given an exact normalized block-encoding of AAA. The query complexity is characterized in terms of the system dimension nnn and a supplied lower bound 0<ν≤ωA0<ν\leq ω_A0<ν≤ωA​ on the imaginary-axis distance ωA:=min⁡t∈Rσmin⁡(A−itI)ω_A:=\min_{t\in\mathbb{R}}σ_{\min}(A-\mathrm{i}tI)ωA​:=mint∈R​σmin​(A−itI), where σmin⁡(A)σ_{\min}(A)σmin​(A) is the smallest singular value of AAA. We prove a query-complexity lower bound of Ω(n/ν)Ω(\sqrt{n}/ν)Ω(n​/ν), which holds even when AAA is restricted to be real and diagonal. For general matrices with nonzero ωAω_AωA​, we encode an approximation of the right-half-plane spectral projector sign⁡+(A):=(I+sign⁡(A))/2\operatorname{sign}^+(A):=(I+\operatorname{sign}(A))/2sign+(A):=(I+sign(A))/2 as a block of a matrix inverse, where AAA 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))(β,b,1/(4\sqrt{n}))(β,b,1/(4n​))-block-encoded projector matrix (like sign⁡+(A)\operatorname{sign}^+(A)sign+(A)) is zero or not; for constant success probability, it has complexity Θ(βn)Θ(β\sqrt{n})Θ(βn​). When the zero test is applied to specific approximations of sign⁡+(A)\operatorname{sign}^+(A)sign+(A), this yields an upper bound of O(nν−2log⁡(n/ν))O(\sqrt{n}ν^{-2}\log(\sqrt{n}/ν))O(n​ν−2log(n​/ν)) queries in the general case, and O(nν−1log⁡n)O(\sqrt{n}ν^{-1}\log n)O(n​ν−1logn) when AAA 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.
Quantum subspace-diagonalization methods, particularly Quantum Krylov Diagonalization (QKD), provide a promising route for computing low-energy spectra of quantum many-body Hamiltonians. However, existing quantum Krylov approaches rely on non-orthogonal Krylov bases, requiring overlap-matrix regularization that limits numerical stability and accuracy. In this work, we introduce an Orthogonal Quantum Krylov Diagonalization (OQKD) framework that reformulates the classical Lanczos recursion at the operator level, enabling an orthogonal quantum implementation of Krylov-subspace diagonalization. By expressing Lanczos vectors as polynomial transformations of the Hamiltonian, OQKD reproduces the orthogonality, tridiagonal structure, and convergence behavior of the classical Lanczos algorithm thus eliminating the need for overlap-matrix regularization. We further show that the required Lanczos polynomials can be implemented using block encoding and Generalized Quantum Signal Processing with the same asymptotic query complexity as Chebyshev-based QKD methods. Numerical simulations of the J1J_1J1​--J2J_2J2​ Heisenberg model confirm the classical Lanczos convergence and numerical stability of the proposed method, while the measurement-complexity scaling is established analytically. Building upon the OQKD framework, we then introduce a restarted state-preparation protocol that replaces a single high-degree polynomial transformation with a sequence of fixed low-degree transformations, maintaining an affordable block encoding success probability while retaining comparable convergence. These results establish OQKD as an orthogonal quantum analog of the classical Lanczos algorithm and identify the restarted protocol as a promising state-preparation strategy for Quantum Phase Estimation.
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.