論文の概要: Quantum Kaczmarz Algorithm for Solving Linear Algebraic Equations
- arxiv url: http://arxiv.org/abs/2601.01342v1
- Date: Sun, 04 Jan 2026 03:13:36 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-01-06 16:25:22.238503
- Title: Quantum Kaczmarz Algorithm for Solving Linear Algebraic Equations
- Title（参考訳）: 線形代数方程式の量子Kaczmarzアルゴリズム
- Authors: Nhat A. Nghiem, Tuan K. Do, Trung V. Phan,
- Abstract要約: 本稿では,Kaczmarz法に基づく量子線形システム解法を提案する。
その単純さとメモリコストの低さにより、データ回帰、トモグラフィー再構成、最適化にまたがる実用的な選択肢となっている。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We introduce a quantum linear system solving algorithm based on the Kaczmarz method, a widely used workhorse for large linear systems and least-squares problems that updates the solution by enforcing one equation at a time. Its simplicity and low memory cost make it a practical choice across data regression, tomographic reconstruction, and optimization. In contrast to many existing quantum linear solvers, our method does not rely on oracle access to query entries, relaxing a key practicality bottleneck. In particular, when the rank of the system of interest is sufficiently small and the rows of the matrix of interest admit an appropriate structure, we achieve circuit complexity $\mathcal{O}\left(\frac{1}{\varepsilon}\log m\right)$, where $m$ is the number of variables and $\varepsilon$ is the target precision, without dependence on the sparsity $s$, and could possibly be without explicit dependence on condition number $κ$. This shows a significant improvement over previous quantum linear solvers where the dependence on $κ,s$ is at least linear. At the same time, when the rows have an arbitrary structure and have at most $s$ nonzero entries, we obtain the circuit depth $\mathcal{O}\left(\frac{1}{\varepsilon}\log s\right)$ using extra $\mathcal{O}(s)$ ancilla qubits, so the depth grows only logarithmically with sparsity $s$. When the sparsity $s$ grows as $\mathcal{O}(\log m)$, then our method can achieve an exponential improvement with respect to circuit depth compared to existing quantum algorithms, while using (asymptotically) the same amount of qubits.
- Abstract（参考訳）: そこで我々は,大線形系に対して広く用いられているワークホースであるKaczmarz法に基づく量子線形系解法と,1つの方程式を一度に1つの方程式を強制することによって解を更新する最小二乗問題を導入する。
その単純さとメモリコストの低さにより、データ回帰、トモグラフィー再構成、最適化にまたがる実用的な選択肢となっている。
既存の多くの量子線形解法とは対照的に、我々の手法はクエリエントリへのオラクルアクセスに頼らず、重要な実用性ボトルネックを緩和する。
特に、興味を持つ系の階数が十分に小さく、興味を持つ行列の列が適切な構造を持つ場合、回路複雑性を$\mathcal{O}\left(\frac{1}{\varepsilon}\log m\right)$, ここで$m$は変数の数であり、$\varepsilon$はスパース性$s$に依存せず、条件番号$κ$に明示的に依存しない可能性がある。
これは、$κ,s$への依存が少なくとも線型である以前の量子線型解法よりも大幅に改善されたことを示している。
同時に、行が任意の構造を持ち、少なくとも$s$ 0 でないエントリを持つとき、回路深さ $\mathcal{O}\left(\frac{1}{\varepsilon}\log s\right)$ を余剰 $\mathcal{O}(s)$ ancilla qubits で取得する。
スパーシティ$s$が$\mathcal{O}(\log m)$として成長すると、我々の手法は、同じ量子ビットを(漸近的に)使用しながら、既存の量子アルゴリズムと比較して回路深さに関して指数関数的に改善できる。
関連論文リスト
- Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
多くの機械学習タスクにおいて重要なボトルネックとなっているが、大規模な線形システムの解決コストは定量化が難しいことが証明されている。
低次元構造を示すアプリケーションによって動機づけられた線形システムの解法における複雑性の微妙な概念を考察する。
線形システム $Ax = b$, すなわち $|Abarx - b| le epsilon |b|$ であるような $barx$ を求める。
論文 参考訳（メタデータ） (2024-05-09T14:56:49Z) - A quantum central path algorithm for linear optimization [5.450016817940232]
中心経路の量子力学的シミュレーションにより線形最適化問題を解くための新しい量子アルゴリズムを提案する。
このアプローチは、$m$制約と$n$変数を含む線形最適化問題を$varepsilon$-optimalityに解くアルゴリズムをもたらす。
標準ゲートモデル(すなわち、量子RAMにアクセスせずに)では、我々のアルゴリズムは少なくとも$$mathcalO left( sqrtm + n textsfnnz (A) fracR_1 を用いてLO問題の高精度な解を得ることができる。
論文 参考訳（メタデータ） (2023-11-07T13:26:20Z) - Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs [0.0]
そこで我々は, 断熱量子計算に基づく線形線形解法アルゴリズムを開発した。
このアルゴリズムは最適スケーリング$O(kappa/log$)$に改善され、$epsilon$が指数関数的に改善される。
ハミルトンシミュレーションの代わりに、より安価なランダム化されたウォーク演算子法を導入する。
論文 参考訳（メタデータ） (2023-05-19T00:07:32Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Quantum-classical algorithms for skewed linear systems with optimized
Hadamard test [10.386115383285288]
我々は、過度に決定された場合と過度に決定された場合のスキュード線形系に対するハイブリッド量子古典アルゴリズムについて論じる。
我々の入力モデルは、線形系を定義する行列の列または行が多対数深さの量子回路によって与えられるようなものである。
本稿では,各次元における実時間多対数性を持つ分解線形系の特殊ケースに対するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-28T12:59:27Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Learning nonlinear dynamical systems from a single trajectory [102.60042167341956]
我々は、$x_t+1=sigma(Thetastarx_t)+varepsilon_t$という形の非線形力学系を学ぶアルゴリズムを導入する。
最適なサンプル複雑性と線形ランニング時間を持つ単一軌道から重み行列$Thetastar$を復元するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-04-30T10:42:48Z) - Second-order Conditional Gradient Sliding [70.88478428882871]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。