論文の概要: A New Quantum Linear System Algorithm Beyond the Condition Number and Its Application to Solving Multivariate Polynomial Systems

• arxiv url: http://arxiv.org/abs/2510.05588v1
• Date: Tue, 07 Oct 2025 05:28:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-08 17:57:08.110332
• Title: A New Quantum Linear System Algorithm Beyond the Condition Number and Its Application to Solving Multivariate Polynomial Systems
• Title（参考訳）: 条件数を超えた新しい量子線形系アルゴリズムと多変量多項式系の解法への応用
• Authors: Jianqiang Li,
• Abstract要約: 量子線形系(QLS)問題は、$Avecy = vecb$の解に比例する量子状態$|vecyrangle$の準備を求める。 右辺ベクトル $vecb$ の構造を明示的に活用する新しい QLS アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 7.587280395664776
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a matrix $A$ of dimension $M \times N$ and a vector $\vec{b}$, the quantum linear system (QLS) problem asks for the preparation of a quantum state $|\vec{y}\rangle$ proportional to the solution of $A\vec{y} = \vec{b}$. Existing QLS algorithms have runtimes that scale linearly with the condition number $\kappa(A)$, the sparsity of $A$, and logarithmically with inverse precision, but often overlook structural properties of $\vec{b}$, whose alignment with $A$'s eigenspaces can greatly affect performance. In this work, we present a new QLS algorithm that explicitly leverages the structure of the right-hand side vector $\vec{b}$. The runtime of our algorithm depends polynomially on the sparsity of the augmented matrix $H = [A, -\vec{b}]$, the inverse precision, the $\ell_2$ norm of the solution $\vec{y} = A^+ \vec{b}$, and a new instance-dependent parameter \[ ET= \sum_{i=1}^M p_i^2 \cdot d_i, \] where $\vec{p} = (AA^{\top})^+ \vec{b}$, and $d_i$ denotes the squared $\ell_2$ norm of the $i$-th row of $H$. We also introduce a structure-aware rescaling technique tailored to the solution $\vec{y} = A^+ \vec{b}$. Unlike left preconditioning methods, which transform the linear system to $DA\vec{y} = D\vec{b}$, our approach applies a right rescaling matrix, reformulating the linear system as $AD\vec{z} = \vec{b}$. As an application of our instance-aware QLS algorithm and new rescaling scheme, we develop a quantum algorithm for solving multivariate polynomial systems in regimes where prior QLS-based methods fail. This yields an end-to-end framework applicable to a broad class of problems. In particular, we apply it to the maximum independent set (MIS) problem, formulated as a special case of a polynomial system, and show through detailed analysis that, under certain conditions, our quantum algorithm for MIS runs in polynomial time.
• Abstract（参考訳）: 行列 $A$ of dimension $M \times N$ とベクトル $\vec{b}$ が与えられたとき、量子線型系 (QLS) 問題は、$A\vec{y} = \vec{b}$ の解に比例する量子状態 $|\vec{y}\rangle$ の準備を求める。 既存のQLSアルゴリズムは、条件数$\kappa(A)$、$A$の間隔、逆精度で対数的にスケールするランタイムを持つが、$A$の固有空間との整合性は性能に大きな影響を与える。 本研究では、右辺ベクトル $\vec{b}$ の構造を明示的に活用する新しい QLS アルゴリズムを提案する。 我々のアルゴリズムのランタイムは、拡張行列 $H = [A, -\vec{b}]$、逆精度$\ell_2$ノルム$\vec{y} = A^+ \vec{b}$、新しいインスタンス依存パラメータ \[ ET= \sum_{i=1}^M p_i^2 \cdot d_i, \] の間隔に多項式的に依存する。 また、構造を意識した再スケーリング手法を、解 $\vec{y} = A^+ \vec{b}$ に合わせて導入する。 線形系を$DA\vec{y} = D\vec{b}$に変換する左プレコンディショニング法とは異なり、我々の手法は右再スケーリング行列を適用し、$AD\vec{z} = \vec{b}$とする。 インスタンス認識型QLSアルゴリズムと新しい再スケーリング手法の応用として,従来のQLSに基づく手法が失敗する状況下で,多変量多項式系を解く量子アルゴリズムを開発した。 これにより、幅広い種類の問題に適用可能なエンドツーエンドのフレームワークが得られる。 特に、多項式系の特別な場合として定式化された最大独立集合(MIS)問題に適用し、特定の条件下では、MISの量子アルゴリズムが多項式時間で実行されることを示す。

関連論文リスト

• Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure [16.324043075920564]
  線形システムと回帰問題を解くための新しい高精度ランダム化アルゴリズムを提供する。 我々のアルゴリズムは、これらの問題に対する高密度な入力の下で、自然の複雑さの限界をほぼマッチングする。 特異値の$k$を除くすべての値が有界な一般化平均を持つというより弱い仮定の下でも、これらの実行時間を得る方法を示す。
  論文  参考訳（メタデータ） (2025-07-15T20:48:30Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Quantum linear system algorithm with optimal queries to initial state preparation [0.0]
  線形システムの量子アルゴリズムは、2つのオラクルを問合せして解状態$A-1|brangle$を生成する。 本稿では,$mathbfThetaleft (1/sqrtpright)$クエリを$O_b$に変換する量子線形系アルゴリズムを提案する。 微分方程式の解法のような様々な応用において、ブロックプレコンディショニングスキームを用いて$p$への依存をさらに改善することができる。
  論文  参考訳（メタデータ） (2024-10-23T18:00:01Z)
• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。 我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
  論文  参考訳（メタデータ） (2024-10-07T19:47:13Z)
• 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)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number [0.0]
  量子線形系を解くことは、$A$が正定値であるとき、$kappa$のランタイム線形を必要とすることを示す。 2つの新しい量子アルゴリズムで、$kappa$の2次スピードアップを特徴とする。
  論文  参考訳（メタデータ） (2021-01-28T08:41:21Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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