論文の概要: Quantum Speedup for Spectral Approximation of Kronecker Products
- arxiv url: http://arxiv.org/abs/2402.07027v1
- Date: Sat, 10 Feb 2024 19:21:29 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-13 17:54:30.482839
- Title: Quantum Speedup for Spectral Approximation of Kronecker Products
- Title（参考訳）: クロネッカー製品のスペクトル近似のための量子スピードアップ
- Authors: Yeqi Gao, Zhao Song, Ruizhe Zhang
- Abstract要約: 量子法を用いてKronecker 積 $A_otimes A$ のスペクトル近似を効率的に解くための革新的なアプローチを導入する。
行列を量子状態として扱うことにより,スペクトル近似の時間的複雑さを$O_d,epsilon(sqrtn)$に大幅に低減する。
- 参考スコア（独自算出の注目度）: 10.602399256297032
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Given its widespread application in machine learning and optimization, the
Kronecker product emerges as a pivotal linear algebra operator. However, its
computational demands render it an expensive operation, leading to heightened
costs in spectral approximation of it through traditional computation
algorithms. Existing classical methods for spectral approximation exhibit a
linear dependency on the matrix dimension denoted by $n$, considering matrices
of size $A_1 \in \mathbb{R}^{n \times d}$ and $A_2 \in \mathbb{R}^{n \times
d}$. Our work introduces an innovative approach to efficiently address the
spectral approximation of the Kronecker product $A_1 \otimes A_2$ using quantum
methods. By treating matrices as quantum states, our proposed method
significantly reduces the time complexity of spectral approximation to
$O_{d,\epsilon}(\sqrt{n})$.
- Abstract（参考訳）: 機械学習と最適化に広く応用されていることから、クロネッカー積は中心線型代数作用素として現れる。
しかし、その計算要求により高価な演算となり、従来の計算アルゴリズムによるスペクトル近似のコストが増大した。
既存のスペクトル近似の古典的手法は、大きさ$A_1 \in \mathbb{R}^{n \times d}$と$A_2 \in \mathbb{R}^{n \times d}$を考えると、$n$で表される行列次元に線形依存を示す。
本研究は,Kronecker 積 $A_1 \otimes A_2$ のスペクトル近似を量子法で効率的に解くための革新的な手法を提案する。
行列を量子状態として扱うことにより、スペクトル近似の時間的複雑さを$O_{d,\epsilon}(\sqrt{n})$に大幅に低減する。
関連論文リスト
- Exploiting Hankel-Toeplitz Structures for Fast Computation of Kernel Precision Matrices [14.25435308779899]
ヒルベルト空間ガウス過程(HGP)アプローチは、GP推論を高速化するための超独立基底関数近似を提供する。
本稿では,この計算複雑性を,余分な近似を伴わずに$mathcalO(NM)$に下げる。
我々の貢献は、いくつかの既存の、広く使われているGP近似の純粋なスピードアップを提供するが、それ以上の近似は行わない。
論文 参考訳（メタデータ） (2024-08-05T09:45:31Z) - Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
我々は、スペクトルテール条件数である$kappa_ell$を、システムを表す行列の最小特異値と$ell$2の比として定義する。
結果のいくつかの意味と$kappa_ell$の使用は、Conjugateメソッドのきめ細かい解析を直接改善することを含んでいる。
論文 参考訳（メタデータ） (2024-05-09T14:56:49Z) - Tensor networks based quantum optimization algorithm [0.0]
最適化において、よく知られた古典的アルゴリズムの1つは電力反復である。
我々はこの落とし穴を回避するために量子化を提案する。
我々の手法はインスタンス非依存となり、量子コンピューティングの枠組みの中でブラックボックス最適化に対処することができる。
論文 参考訳（メタデータ） (2024-04-23T13:49:11Z) - An efficient quantum algorithm for generation of ab initio n-th order susceptibilities for non-linear spectroscpies [0.13980986259786224]
我々は,$n$-thの応答特性を計算するために,フォールトトレラントな量子アルゴリズムを開発し,解析する。
電子自由度を量子力学的に扱い、光を古典的場として扱う半古典的記述を用いる。
論文 参考訳（メタデータ） (2024-04-01T20:04:49Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Leverage Score Sampling for Tensor Product Matrices in Input Sparsity
Time [54.65688986250061]
我々は,$q$-foldカラムワイドテンソル積の$q$行列に対応するグラム行列を近似するための入力空間時間サンプリングアルゴリズムを提案する。
我々のサンプリング技術は、合計時間でデータセット$X$に同時に適用できる$q$部分相関ランダムプロジェクションのコレクションに依存している。
論文 参考訳（メタデータ） (2022-02-09T15:26:03Z) - Reducing the Variance of Gaussian Process Hyperparameter Optimization
with Preconditioning [54.01682318834995]
プレコンディショニングは、行列ベクトル乗算を含む反復的な方法にとって非常に効果的なステップである。
プレコンディショニングには、これまで検討されていなかった付加的なメリットがあることを実証する。
基本的に無視可能なコストで、同時に分散を低減することができる。
論文 参考訳（メタデータ） (2021-07-01T06:43:11Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。
我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-30T19:10:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。