Quantum query complexity of Hurwitz stability testing
Abstract
Determining whether every trajectory of the linear system ẋ=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∈ℂn× 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∈ℝσ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/(4√n))-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ν−1log 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.
Related
- Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity
- Quantum Query Complexity Beyond the Worst Case
- Quantum Query Complexity of Tournament Solutions
- Optimal query complexity for fractional quantum evolution
- Quantum Query Complexity of Maximum Degree and its Generalizations
BibTeX
@misc{fitzsimmons2026quantum,
title = {{Quantum query complexity of Hurwitz stability testing}},
author = {Maxwell Fitzsimmons and Mohamed Serry and Meenu Kumari and Jun Liu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41180},
eprint = {2610.41180},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41180},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum query complexity of Hurwitz stability testing
AU - Maxwell Fitzsimmons
AU - Mohamed Serry
AU - Meenu Kumari
AU - Jun Liu
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.41180
UR - https://arxiv.org/abs/2610.41180
AB - Determining whether every trajectory of the linear system ẋ=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∈ℂ^n× 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:=min_t∈ℝσ_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/(4√n))-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ν^−1log 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.
ER -