← 研踪 PaperTrailarXiv:2610.41180 · v2
Quantum query complexity of Hurwitz stability testing
首次提交 2026-10-30 10:59
版本更新 2026-11-13 23:28
雷达观测 2026-11-16 11:41
摘要
Determining whether every trajectory of the linear system converges to zero (or, equivalently, whether 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 is Hurwitz stable, given an exact normalized block-encoding of . The query complexity is characterized in terms of the system dimension and a supplied lower bound on the imaginary-axis distance , where is the smallest singular value of . We prove a query-complexity lower bound of , which holds even when is restricted to be real and diagonal. For general matrices with nonzero , we encode an approximation of the right-half-plane spectral projector as a block of a matrix inverse, where is Hurwitz if and only if the projector is zero. To test this, we produce a quantum algorithm which determines if a -block-encoded projector matrix (like ) is zero or not; for constant success probability, it has complexity . When the zero test is applied to specific approximations of , this yields an upper bound of queries in the general case, and when 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.
作者备注:36 pages, including appendices; 1 figure, 1 table
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-13 23:28 · 最新观测版本
Quantum query complexity of Hurwitz stability testing
Determining whether every trajectory of the linear system converges to zero (or, equivalently, whether 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 is Hurwitz stable, given an exact normalized block-encoding of . The query complexity is characterized in terms of the system dimension and a supplied lower bound on the imaginary-axis distance , where is the smallest singular value of . We prove a query-complexity lower bound of , which holds even when is restricted to be real and diagonal. For general matrices with nonzero , we encode an approximation of the right-half-plane spectral projector as a block of a matrix inverse, where is Hurwitz if and only if the projector is zero. To test this, we produce a quantum algorithm which determines if a -block-encoded projector matrix (like ) is zero or not; for constant success probability, it has complexity . When the zero test is applied to specific approximations of , this yields an upper bound of queries in the general case, and when 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.
查看此版本解读 →查看此版本原文 ↗