論文の概要: Randomized and quantum approximate matrix multiplication
- arxiv url: http://arxiv.org/abs/2510.08509v1
- Date: Thu, 09 Oct 2025 17:44:03 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-10 17:54:15.261655
- Title: Randomized and quantum approximate matrix multiplication
- Title（参考訳）: ランダム化および量子近似行列乗法
- Authors: Simon Apers, Arjan Cornelissen, Samson Wang,
- Abstract要約: 長い行の文献ではランダム化アルゴリズムを考慮し、より速い時間で近似解を返す。
まず、Cohen-Lewis (99) によるランダムウォークに基づく古典的アルゴリズムの洗練された解析を行い、Sarl'os (06) と Drineas-Kannan-Mahoney (06) によるスケッチに基づく。
次に、他のすべての手法よりも高速な1つの古典的アルゴリズムを生成するコーエン=ルイスの改良を提案する。
- 参考スコア（独自算出の注目度）: 0.718791111462057
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The complexity of matrix multiplication is a central topic in computer science. While the focus has traditionally been on exact algorithms, a long line of literature also considers randomized algorithms, which return an approximate solution in faster time. In this work, we adopt a unifying perspective that frames these randomized algorithms in terms of mean estimation. Using it, we first give refined analyses of classical algorithms based on random walks by Cohen-Lewis (`99), and based on sketching by Sarl\'os (`06) and Drineas-Kannan-Mahoney (`06). We then propose an improvement on Cohen-Lewis that yields a single classical algorithm that is faster than all the other approaches, if we assume no use of (exact) fast matrix multiplication as a subroutine. Second, we demonstrate a quantum speedup on top of these algorithms by using the recent quantum multivariate mean estimation algorithm by Cornelissen-Hamoudi-Jerbi (`22).
- Abstract（参考訳）: 行列乗算の複雑さは計算機科学における中心的なトピックである。
従来は正確なアルゴリズムに焦点が当てられていたが、多くの文献ではランダム化アルゴリズムも検討しており、より速い時間で近似解を返す。
本研究では、これらのランダム化アルゴリズムを平均推定の観点からフレーム化する統一的な視点を採用する。
これを用いて、まずCohen-Lewis (`99) によるランダムウォークに基づく古典的アルゴリズムの洗練された解析を行い、Sarl\'os (`06) と Drineas-Kannan-Mahoney (`06) によるスケッチに基づく。
次に、他のすべてのアプローチよりも高速な1つの古典的アルゴリズムを生成するコーエン=ルイスの改良を提案し、もし(実際に)高速行列乗法をサブルーチンとして使わないと仮定する。
次に,Cornelissen-Hamoudi-Jerbi (`22。
関連論文リスト
- HARLI CQUINN: Higher Adjusted Randomness with Linear In Complexity QUantum INspired Networks for K-Means [0.0]
古典的k平均アルゴリズムと同等以上の量子性能を示す。
我々は、その精度のベンチマークを、よく知られたデータセットと実験データセットの両方のテストケースに提示する。
論文 参考訳（メタデータ） (2025-09-23T02:32:13Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。
3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。
数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文 参考訳（メタデータ） (2023-11-19T00:06:11Z) - Learning the Positions in CountSketch [49.57951567374372]
本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。
本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-11T07:28:35Z) - Quantum speedup of leverage score sampling and its application [0.0]
本稿では,レバレッジスコアの計算を高速化する量子アルゴリズムを提案する。
応用として,ベクトル解出力を用いた剛性回帰問題に対する新しい量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-15T14:40:18Z) - Quantum Algorithm For Estimating Eigenvalue [0.0]
与えられたエルミート行列の大きさで最大の固有値を推定するための量子アルゴリズムを提供する。
我々の量子プロシージャは、同じ問題を解決する古典的なアルゴリズムと比較して指数的なスピードアップを得ることができる。
論文 参考訳（メタデータ） (2022-11-11T13:02:07Z) - Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文 参考訳（メタデータ） (2020-08-29T14:58:26Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。