跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

Determining whether every trajectory of the linear system x˙=Ax\dot{x}=Ax converges to zero (or, equivalently, whether AA 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} is Hurwitz stable, given an exact normalized block-encoding of AA. The query complexity is characterized in terms of the system dimension nn and a supplied lower bound 0<ν≤ωA0<ν\leq ω_A on the imaginary-axis distance ωA:=min⁡t∈Rσmin⁡(A−itI)ω_A:=\min_{t\in\mathbb{R}}σ_{\min}(A-\mathrm{i}tI), where σmin⁡(A)σ_{\min}(A) is the smallest singular value of AA. We prove a query-complexity lower bound of Ω(n/ν)Ω(\sqrt{n}/ν), which holds even when AA is restricted to be real and diagonal. For general matrices with nonzero ω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))/2 as a block of a matrix inverse, where AA 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}))-block-encoded projector matrix (like sign⁡+(A)\operatorname{sign}^+(A)) is zero or not; for constant success probability, it has complexity Θ(βn)Θ(β\sqrt{n}). When the zero test is applied to specific approximations of sign⁡+(A)\operatorname{sign}^+(A), this yields an upper bound of O(nν−2log⁡(n/ν))O(\sqrt{n}ν^{-2}\log(\sqrt{n}/ν)) queries in the general case, and O(nν−1log⁡n)O(\sqrt{n}ν^{-1}\log n) when AA 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

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v2,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v2 · 2026-11-13 23:28 · 最新观测版本

Quantum query complexity of Hurwitz stability testing

Determining whether every trajectory of the linear system x˙=Ax\dot{x}=Ax converges to zero (or, equivalently, whether AA 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} is Hurwitz stable, given an exact normalized block-encoding of AA. The query complexity is characterized in terms of the system dimension nn and a supplied lower bound 0<ν≤ωA0<ν\leq ω_A on the imaginary-axis distance ωA:=min⁡t∈Rσmin⁡(A−itI)ω_A:=\min_{t\in\mathbb{R}}σ_{\min}(A-\mathrm{i}tI), where σmin⁡(A)σ_{\min}(A) is the smallest singular value of AA. We prove a query-complexity lower bound of Ω(n/ν)Ω(\sqrt{n}/ν), which holds even when AA is restricted to be real and diagonal. For general matrices with nonzero ω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))/2 as a block of a matrix inverse, where AA 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}))-block-encoded projector matrix (like sign⁡+(A)\operatorname{sign}^+(A)) is zero or not; for constant success probability, it has complexity Θ(βn)Θ(β\sqrt{n}). When the zero test is applied to specific approximations of sign⁡+(A)\operatorname{sign}^+(A), this yields an upper bound of O(nν−2log⁡(n/ν))O(\sqrt{n}ν^{-2}\log(\sqrt{n}/ν)) queries in the general case, and O(nν−1log⁡n)O(\sqrt{n}ν^{-1}\log n) when AA 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.

查看此版本解读 →查看此版本原文 ↗