Metraipolis › archive › dc_a928fd2aec02
Quantum query complexity of Hurwitz stability testing — arXiv:2610.41180
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.41180
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-02T05:07:40.996Z
- SHA-256 of the archived text
bf5fb115abfb22f4ca72126249d9a53b00f899983f96016e1fc27583bc85b435- Stable URL of this page
https://metraipolis.com/documento/dc_a928fd2aec02
How to cite
Quantum query complexity of Hurwitz stability testing — arXiv:2610.41180 — arXiv (en), https://arxiv.org/abs/2610.41180 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a928fd2aec02 (Metraipolis archive dc_a928fd2aec02, sha256 bf5fb115abfb22f4ca72126249d9a53b00f899983f96016e1fc27583bc85b435)
BibTeX
@misc{dca928fd2aec02,
title = {Quantum query complexity of Hurwitz stability testing — arXiv:2610.41180},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.41180},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a928fd2aec02; sha256 bf5fb115abfb22f4ca72126249d9a53b00f899983f96016e1fc27583bc85b435},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.41180. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2610.41180 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-02T04:50:58.152Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).