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<\nu\leq \omega_A$ on the imaginary-axis distance $\omega_A:=\min_{t\in\mathbb{R}}\sigma_{\min}(A-\mathrm{i}tI)$, where $\sigma_{\min}(A)$ is the smallest singular value of $A$. We prove a query-complexity lower bound of $\Omega(\sqrt{n}/\nu)$, which holds even when $A$ is restricted to be real and diagonal. For general matrices with nonzero $\omega_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 $(\beta,b,1/(4\sqrt{n}))$-block-encoded projector matrix (like $\operatorname{sign}^+(A)$) is zero or not; for constant success probability, it has complexity $\Theta(\beta\sqrt{n})$. When the zero test is applied to specific approximations of $\operatorname{sign}^+(A)$, this yields an upper bound of $O(\sqrt{n}\nu^{-2}\log(\sqrt{n}/\nu))$ queries in the general case, and $O(\sqrt{n}\nu^{-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.

Quantum Physics (quant-ph); Computational Complexity (cs.CC)

arXiv:2610.41180 [quant-ph]

(or arXiv:2610.41180v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2610.41180 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.