論文の概要: Block-encoding dense and full-rank kernels using hierarchical matrices:
applications in quantum numerical linear algebra
- arxiv url: http://arxiv.org/abs/2201.11329v4
- Date: Wed, 7 Dec 2022 02:05:04 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-27 18:34:43.006285
- Title: Block-encoding dense and full-rank kernels using hierarchical matrices:
applications in quantum numerical linear algebra
- Title（参考訳）: 階層行列を用いたブロックエンコーディングとフルランクカーネル:量子数値線形代数への応用
- Authors: Quynh T. Nguyen, Bobak T. Kiani, Seth Lloyd
- Abstract要約: 本稿では,量子コンピュータ上の階層行列構造のブロック符号化方式を提案する。
我々の手法は、次元$N$から$O(kappa operatornamepolylog(fracNvarepsilon))$の量子線型系を解くランタイムを改善することができる。
- 参考スコア（独自算出の注目度）: 6.338178373376447
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Many quantum algorithms for numerical linear algebra assume black-box access
to a block-encoding of the matrix of interest, which is a strong assumption
when the matrix is not sparse. Kernel matrices, which arise from discretizing a
kernel function $k(x,x')$, have a variety of applications in mathematics and
engineering. They are generally dense and full-rank. Classically, the
celebrated fast multipole method performs matrix multiplication on kernel
matrices of dimension $N$ in time almost linear in $N$ by using the linear
algebraic framework of hierarchical matrices. In light of this success, we
propose a block-encoding scheme of the hierarchical matrix structure on a
quantum computer. When applied to many physical kernel matrices, our method can
improve the runtime of solving quantum linear systems of dimension $N$ to
$O(\kappa \operatorname{polylog}(\frac{N}{\varepsilon}))$, where $\kappa$ and
$\varepsilon$ are the condition number and error bound of the matrix operation.
This runtime is near-optimal and, in terms of $N$, exponentially improves over
prior quantum linear systems algorithms in the case of dense and full-rank
kernel matrices. We discuss possible applications of our methodology in solving
integral equations and accelerating computations in N-body problems.
- Abstract（参考訳）: 数値線型代数の多くの量子アルゴリズムは、興味のある行列のブロックエンコーディングへのブラックボックスアクセスを仮定するが、これは行列がスパースでない場合の強い仮定である。
カーネル行列は、カーネル関数 $k(x,x')$ を離散化することによって生じるもので、数学や工学において様々な応用がある。
概して密度が高く、フルランクである。
古典的には、有名な高速多重極法(fast multipole method)は、階層行列の線形代数的枠組みを用いて、n$ in time 次元の核行列の行列乗算を行う。
この成功を踏まえ,量子コンピュータ上の階層行列構造のブロックエンコーディングスキームを提案する。
多くの物理カーネル行列に適用すると、この手法は次元$N$から$O(\kappa \operatorname{polylog}(\frac{N}{\varepsilon})$への量子線型系の解法ランタイムを改善することができる。
このランタイムはほぼ最適であり、$N$の観点では、密度とフルランクのカーネル行列の場合、以前の量子線形系アルゴリズムよりも指数関数的に改善される。
我々は,N体問題における積分方程式の解法と計算の高速化における方法論の適用可能性について論じる。
関連論文リスト
- Optimal Quantization for Matrix Multiplication [35.007966885532724]
我々は、ネスト格子に基づく普遍量化器を、任意の(非ランダムな)行列対に対する近似誤差の明示的な保証付きで、フロベニウスノルム$|A|_F, |B|_F$, $|Atop B|_F$のみの観点から、$A$, $B$とする。
論文 参考訳（メタデータ） (2024-10-17T17:19:48Z) - Quantum Time-Space Tradeoffs for Matrix Problems [0.5524804393257919]
量子コンピュータが行列を含む様々な問題を解くのに必要な時間と空間を考察する。
ほぼ全ての行列$A$に対して、少なくとも$T$の入力クエリと$S$のメモリを持つ量子回路は$T=Omega(n2/S)$を必要とすることを証明している。
我々の下界の多くは時間と空間の複雑さで決定論的アルゴリズムと一致するため、量子コンピュータは任意の空間境界を持つこれらの問題に対していかなる利点も提供できないことを示す。
論文 参考訳（メタデータ） (2024-01-10T18:38:43Z) - CoLA: Exploiting Compositional Structure for Automatic and Efficient
Numerical Linear Algebra [62.37017125812101]
機械学習における大規模線形代数問題に対して, CoLA という, 単純だが汎用的なフレームワークを提案する。
線形演算子抽象と合成ディスパッチルールを組み合わせることで、CoLAはメモリと実行時の効率的な数値アルゴリズムを自動的に構築する。
偏微分方程式,ガウス過程,同変モデル構築,教師なし学習など,幅広い応用で有効性を示す。
論文 参考訳（メタデータ） (2023-09-06T14:59:38Z) - Vectorization of the density matrix and quantum simulation of the von
Neumann equation of time-dependent Hamiltonians [65.268245109828]
我々は、von-Neumann方程式を線形化するための一般的なフレームワークを開発し、量子シミュレーションに適した形でレンダリングする。
フォン・ノイマン方程式のこれらの線型化のうちの1つは、状態ベクトルが密度行列の列重ね元となる標準的な場合に対応することを示す。
密度行列の力学をシミュレートする量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-14T23:08:51Z) - Multiresolution kernel matrix algebra [0.0]
本研究では, あるS形式において, 最適スパース行列を生成するサンプルレットを用いて, カーネル行列の圧縮を示す。
カーネル行列の逆数(もし存在するなら)は S-形式でも圧縮可能である。
行列代数は擬微分計算によって数学的に正当化される。
論文 参考訳（メタデータ） (2022-11-21T17:50:22Z) - Quantum algorithms for matrix operations and linear systems of equations [65.62256987706128]
本稿では,「Sender-Receiver」モデルを用いた行列演算のための量子アルゴリズムを提案する。
これらの量子プロトコルは、他の量子スキームのサブルーチンとして使用できる。
論文 参考訳（メタデータ） (2022-02-10T08:12:20Z) - A Quantum Computer Amenable Sparse Matrix Equation Solver [0.0]
本稿では,行列方程式の解法に関わる問題について検討する。
Harrow/Hassidim/Lloydアルゴリズムを固有位相推定のための代替ユニタリを提供することにより一般化する。
このユニタリは任意の行列方程式に対して十分に定義されているという利点があり、それによって解の手順を量子ハードウェアに直接実装することができる。
論文 参考訳（メタデータ） (2021-12-05T15:42:32Z) - Fundamental Machine Learning Routines as Quantum Algorithms on a
Superconducting Quantum Computer [0.0]
Harrow-Hassidim-Lloydアルゴリズムは、量子デバイス上の線形方程式のシステムを解くことを目的としている。
本稿では,これらの特徴が完全に一致しない場合のアルゴリズムの性能に関する数値的研究を行う。
論文 参考訳（メタデータ） (2021-09-17T15:22:06Z) - Non-PSD Matrix Sketching with Applications to Regression and
Optimization [56.730993511802865]
非PSDおよび2乗根行列の次元削減法を提案する。
複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
論文 参考訳（メタデータ） (2021-06-16T04:07:48Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - What if Neural Networks had SVDs? [66.91160214071088]
様々なニューラルネットワークでは、行列反転のような時間を要する行列演算を採用している。
本稿では,行列演算を高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-29T12:58:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。