Quantum query complexity of Hurwitz stability testing

Abstract

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.

The paper studies the quantum query complexity of deciding whether a matrix $A$ is Hurwitz stable—all eigenvalues have negative real part—from normalized block-encoding access. It assumes a supplied lower bound $0<\nu\leq\omega_A$, where $\omega_A=\min_{t\in\mathbb R}\sigma_{\min}(A-itI)$ measures distance to acquiring an imaginary-axis eigenvalue. The guarantees include nonnormal and nondiagonalizable matrices, without a supplied guiding state or eigenvector-conditioning promise. For constant success probability, a weak-oracle search reduction gives an $\Omega(\sqrt n/\nu)$ lower bound, already for real diagonal matrices. The general-matrix algorithm uses $O(\sqrt n\,\nu^{-2}\log(\sqrt n/\nu))$ queries; for normal matrices, including Hermitian matrices, the bound improves to $O(\sqrt n\,\nu^{-1}\log n)$. The algorithm tests whether the right-half-plane spectral projector $P=(I+\operatorname{sign}(A))/2$ vanishes. Given a $(\beta,b,\epsilon)$ block-encoding of an idempotent with $\epsilon\leq1/(4\sqrt n)$, maximally entangled initialization and amplitude estimation give optimal $\Theta(\beta\sqrt n)$ zero-testing complexity when both outcomes are admissible. For general $A$, a Padé approximation to $P$ is extracted from a structured matrix inverse implemented using QSVT. A separate matrix-analysis result establishes the sharp fixed-dimension scaling $\|P\|=O(\omega_A^{-(n-1)/n})$, with matching examples. The nonnormal upper and lower bounds retain an inverse-margin factor gap, apart from logarithms. Whether improved projector construction or direct testing closes it remains open. The normal-case logarithm may also be removable. Bounds count oracle queries, exclude input-oracle implementation costs, and require the margin promise; no advantage over alternative matrix-sign implementations is established.