論文の概要: Quantum algorithms for matrix scaling and matrix balancing
- arxiv url: http://arxiv.org/abs/2011.12823v1
- Date: Wed, 25 Nov 2020 15:26:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-23 00:58:48.017890
- Title: Quantum algorithms for matrix scaling and matrix balancing
- Title（参考訳）: 行列スケーリングと行列バランスのための量子アルゴリズム
- Authors: Joran van Apeldoorn and Sander Gribling and Yinan Li and Harold
Nieuwboer and Michael Walter and Ronald de Wolf
- Abstract要約: 行列スケーリングと行列バランシングは、様々な応用の2つの基本的な線形代数問題である。
これらの問題に対する量子アルゴリズムのパワーと限界について検討する。
Sinkhornの行列スケーリングアルゴリズムとOsborneの行列バランスアルゴリズムの2つの古典的手法の量子的実装を提供する。
- 参考スコア（独自算出の注目度）: 9.010461408997646
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Matrix scaling and matrix balancing are two basic linear-algebraic problems
with a wide variety of applications, such as approximating the permanent, and
pre-conditioning linear systems to make them more numerically stable. We study
the power and limitations of quantum algorithms for these problems.
We provide quantum implementations of two classical (in both senses of the
word) methods: Sinkhorn's algorithm for matrix scaling and Osborne's algorithm
for matrix balancing. Using amplitude estimation as our main tool, our quantum
implementations both run in time $\tilde O(\sqrt{mn}/\varepsilon^4)$ for
scaling or balancing an $n \times n$ matrix (given by an oracle) with $m$
non-zero entries to within $\ell_1$-error $\varepsilon$. Their classical
analogs use time $\tilde O(m/\varepsilon^2)$, and every classical algorithm for
scaling or balancing with small constant $\varepsilon$ requires $\Omega(m)$
queries to the entries of the input matrix. We thus achieve a polynomial
speed-up in terms of $n$, at the expense of a worse polynomial dependence on
the obtained $\ell_1$-error $\varepsilon$. We emphasize that even for constant
$\varepsilon$ these problems are already non-trivial (and relevant in
applications).
Along the way, we extend the classical analysis of Sinkhorn's and Osborne's
algorithm to allow for errors in the computation of marginals. We also adapt an
improved analysis of Sinkhorn's algorithm for entrywise-positive matrices to
the $\ell_1$-setting, leading to an $\tilde O(n^{1.5}/\varepsilon^3)$-time
quantum algorithm for $\varepsilon$-$\ell_1$-scaling in this case.
We also prove a lower bound, showing that our quantum algorithm for matrix
scaling is essentially optimal for constant $\varepsilon$: every quantum
algorithm for matrix scaling that achieves a constant $\ell_1$-error with
respect to uniform marginals needs to make at least $\Omega(\sqrt{mn})$
queries.
- Abstract（参考訳）: 行列スケーリングと行列バランシングは、より数値的に安定な線形系を近似するなど、多種多様な応用の2つの基本的な線形代数的問題である。
これらの問題に対する量子アルゴリズムの力と限界について研究する。
我々は,2つの古典的手法,すなわち行列スケーリングのためのsinkhornアルゴリズムと行列分散のためのosborneアルゴリズムの量子的実装を提供する。
我々の主要なツールとして振幅推定を用いると、我々の量子実装は時間$\tilde O(\sqrt{mn}/\varepsilon^4)$で実行され、$n \times n$Matrix(オラクルによって取得)と$m$非ゼロエントリを$\ell_1$-error $\varepsilon$でスケーリングまたはバランスする。
それらの古典的アナログは、時間$\tilde O(m/\varepsilon^2)$を使用し、小さな定数$\varepsilon$でスケーリングまたはバランスをとるすべての古典的アルゴリズムは、入力行列のエントリに対する$\Omega(m)$クエリを必要とする。
これにより、得られる$\ell_1$-error $\varepsilon$に対する多項式依存の悪化を犠牲にして、$n$の多項式スピードアップを達成する。
一定の$\varepsilon$であっても、これらの問題はもはや自明ではない(アプリケーションに関係している)。
その過程で、SinkhornのアルゴリズムとOsborneのアルゴリズムの古典的解析を拡張し、限界の計算における誤差を許容する。
また、エントリワイズ正の行列に対するシンクホーンのアルゴリズムの改善された解析を $\ell_1$-setting に適応させ、ここでは$\tilde o(n^{1.5}/\varepsilon^3)$-time 量子アルゴリズムを $\varepsilon$-$\ell_1$-scaling とする。
我々はまた、行列スケーリングの量子アルゴリズムが定数$\varepsilon$に対して本質的に最適であることを証明し、一様境界に関して定数$\ell_1$-errorを達成する行列スケーリングの全ての量子アルゴリズムは、少なくとも$\Omega(\sqrt{mn})$クエリを作成する必要があることを示した。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。
また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-07-04T11:03:48Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Fast and Practical Quantum-Inspired Classical Algorithms for Solving
Linear Systems [11.929584800629673]
線形系を解くための高速で実用的な量子インスパイアされた古典的アルゴリズムを提案する。
我々の主な貢献は、線形系を解くために量子に着想を得た古典的アルゴリズムへの重球運動量法の適用である。
論文 参考訳（メタデータ） (2023-07-13T08:46:19Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Efficient quantum algorithms for solving quantum linear system problems [0.0]
拡張行列 $C$ の特異値 0 の右特異ベクトルを求める問題を解くための2つの量子アルゴリズムを提案する。
どちらのアルゴリズムも$kappa $の最適なクエリ複雑性を満たす。
論文 参考訳（メタデータ） (2022-08-14T02:49:26Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Improved quantum lower and upper bounds for matrix scaling [0.0]
古典的2次アルゴリズムにおける量子スピードアップの可能性について検討する。
我々は,高精度システムにおける入力サイズに関して,本質的に量子スピードアップが存在しないことを示す。
我々は低精度方式で改良された量子アルゴリズムを与える。
論文 参考訳（メタデータ） (2021-09-30T17:29:23Z) - Sublinear classical and quantum algorithms for general matrix games [11.339580074756189]
行列ゲームに対する線形古典的および量子的アルゴリズムについて検討する。
任意の固定 $qin (1,2) に対して、$mathcalX$ が$ell_q$-norm 単位球である行列ゲームが加法誤差内で解決される。
同じタスクを時間内に解く、対応する部分線形量子アルゴリズムも提供する。
論文 参考訳（メタデータ） (2020-12-11T17:36:33Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。