論文の概要: Quantum query complexity of Hurwitz stability testing

• arxiv url: http://arxiv.org/abs/2610.41180v1
• Date: Fri, 30 Oct 2026 02:59:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-02 22:05:31.601077
• Title: Quantum query complexity of Hurwitz stability testing
• Title（参考訳）: Hurwitz安定テストの量子クエリ複雑性
• Abstract要約: 行列 $AinmathbbCntimes n$ が Hurwitz 安定かどうかを決定する量子クエリ複雑性について検討する。 我々は、$(,b,1/(4sqrtn))$-block-encoded projector matrix($operatornamesign+(A)$)がゼロかどうかを決定する量子アルゴリズムを作成する。
• 参考スコア（独自算出の注目度）: 5.7518089141031865
• License: http://creativecommons.org/licenses/by/4.0/
• 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.
• Abstract（参考訳）: 線型系 $\dot{x}=Ax$ のすべての軌道が 0 に収束するかどうかを決定する(または、同等に、$A$ がハルヴィッツ安定であるかどうか)は、制御理論の基本的な問題である。 これは例えば、フィードバックコントローラや状態オブザーバの安定性の検証や線形化された力学モデルの検証に現れる。 行列 $A\in\mathbb{C}^{n\times n}$ が Hurwitz 安定かどうかを決定する量子クエリの複雑性について、正確に正規化されたブロックエンコーディングが$A$であることを考える。 クエリ複雑性は、システム次元$n$と、供給された下界$0<ν\leq ω_A$の虚数軸距離$ω_A:=\min_{t\in\mathbb{R}}σ_{\min}(A-\mathrm{i}tI)$で特徴づけられる。 我々は、$A$が実数で対角線に制限されている場合でも、$Ω(\sqrt{n}/ν)$のクエリ-複素性の下界を証明する。 非ゼロの$ω_A$ の一般行列に対して、右半平面のスペクトル射影 $\operatorname{sign}^+(A):=(I+\operatorname{sign}(A))/2$ を行列逆数のブロックとして符号化する。 これをテストするために、$(β,b,1/(4\sqrt{n}))$-block-encoded projector matrix ($\operatorname{sign}^+(A)$) が 0 であるかどうかを判定する量子アルゴリズムを作成し、一定の成功確率に対して、複雑性$(β\sqrt{n})$を持つ。 ゼロテストが $\operatorname{sign}^+(A)$ の特定の近似に適用された場合、これは、一般に$O(\sqrt{n}ν^{-2}\log(\sqrt{n}/ν))$クエリと$O(\sqrt{n}ν^{-1}\log n)$A$がエルミートあるいは正規であるときの上限となる。 後者の上界は対数係数までの下界と一致する。 したがって、量子フルヴィッツ検定の次元依存性はほぼ最適であり、非正規の場合の残りの因子は開条件ギャップを分離する。

関連論文リスト

• Generic Characteristic-Zero Equivalence Between Derivative Bézout Inversion and Multipoint Evaluation [0.0]
  固有正規化された Bezout 対 $s,t$ を $sZ+tZ'=1$ で満たし、$tm$ と $sm-1$ で計算する。 古典的積木アプローチでは、$O(M_K(m)log m)$フィールド演算が必要であり、$M_K(m)$は、$K$に対して次数-$m$sを乗算するコストを表す。 標数 0 の無限体上において、一般有理直線計画モデルにおいて、正準のすべての係数を計算することが証明される。
  論文  参考訳（メタデータ） (2026-08-28T03:42:18Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• What Trace Powers Reveal About Log-Determinants: Closed-Form Estimators, Certificates, and Failure Modes [0.0]
  トレースパワーへのアクセスを$p_k = tr(Ak)$, 行列パワーが利用可能であれば自然に研究する。 非有界条件よりも連続的な正のモーメントが均一に正確であることはない。
  論文  参考訳（メタデータ） (2026-01-18T23:04:17Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
  論文  参考訳（メタデータ） (2025-10-12T15:42:44Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
  我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。 特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。 主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
  論文  参考訳（メタデータ） (2023-12-14T12:53:34Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
  論文  参考訳（メタデータ） (2021-09-06T14:21:43Z)
• Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
  我々は、$ell_4$ノルムが同じ$ell$ノルムを持つガウスベクトルと異なるプラントベクトル$v$の効率的な推定と検出について研究する。 規則$n rho gg sqrtN$ では、大クラスのスペクトル法(そしてより一般的には、入力の低次法)は、植込みベクトルの検出に失敗する。
  論文  参考訳（メタデータ） (2021-05-31T16:10:49Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。