論文の概要: Quantum algorithms for spectral sums
- arxiv url: http://arxiv.org/abs/2011.06475v1
- Date: Thu, 12 Nov 2020 16:29:45 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-26 06:50:42.714774
- Title: Quantum algorithms for spectral sums
- Title（参考訳）: スペクトル和に対する量子アルゴリズム
- Authors: Alessandro Luongo, Changpeng Shao
- Abstract要約: 対称正定値行列(SPD)の最も一般的なスペクトル和を推定するための新しい量子アルゴリズムを提案し,解析する。
関数 $f$ と行列 $A に対して、スペクトル和は $S_f(A) :=textTr[f(A)] = sum_j f(lambda_j)$, ここで $lambda_j$ は固有値である。
- 参考スコア（独自算出の注目度）: 79.28094304325116
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We propose and analyze new quantum algorithms for estimating the most common
spectral sums of symmetric positive definite (SPD) matrices. For a function $f$
and a matrix $A \in \mathbb{R}^{n\times n}$, the spectral sum is defined as
$S_f(A) :=\text{Tr}[f(A)] = \sum_j f(\lambda_j)$, where $\lambda_j$ are the
eigenvalues. Examples of spectral sums are the von Neumann entropy, the trace
of inverse, the log-determinant, and the Schatten-$p$ norm, where the latter
does not require the matrix to be SPD. The fastest classical randomized
algorithms estimate these quantities have a runtime that depends at least
linearly on the number of nonzero components of the matrix. Assuming quantum
access to the matrix, our algorithms are sub-linear in the matrix size, and
depend at most quadratically on other quantities, like the condition number and
the approximation error, and thus can compete with most of the randomized and
distributed classical algorithms proposed in recent literature. These
algorithms can be used as subroutines for solving many practical problems, for
which the estimation of a spectral sum often represents a computational
bottleneck.
- Abstract（参考訳）: 対称正定値行列(SPD)の最も一般的なスペクトル和を推定するための新しい量子アルゴリズムを提案し,解析する。
関数 $f$ と行列 $A \in \mathbb{R}^{n\times n}$ に対して、スペクトル和は $S_f(A) :=\text{Tr}[f(A)] = \sum_j f(\lambda_j)$ と定義される。
スペクトル和の例としては、フォン・ノイマンのエントロピー、逆のトレース、対数行列式、Schatten-$p$ノルムがある。
これらの量を推定する最も速い古典的ランダム化アルゴリズムは、行列の非零成分の数に少なくとも線形に依存するランタイムを持つ。
行列に対する量子アクセスを仮定すると、我々のアルゴリズムは行列サイズにおいてサブ線形であり、条件数や近似誤差などの他の量に大きく依存しているため、近年の文献で提案されているランダム化および分散された古典的アルゴリズムのほとんどと競合することができる。
これらのアルゴリズムは、スペクトル和の推定がしばしば計算ボトルネックを表す多くの実用的な問題を解決するためのサブルーチンとして使うことができる。
関連論文リスト
- A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix [2.7050250604223693]
与えられた$dtimes d$ matrix $A$ のトップ固有ベクトルのよい近似を見つけることは、基礎的で重要な計算問題である。
上位固有ベクトルの近似の古典的な記述を出力する2つの異なる量子アルゴリズムを与える。
論文 参考訳（メタデータ） (2024-05-23T16:33:13Z) - A square-root speedup for finding the smallest eigenvalue [0.6597195879147555]
エルミート行列の最小固有値を求める量子アルゴリズムについて述べる。
このアルゴリズムは、量子位相推定と量子振幅推定を組み合わせて、2次高速化を実現する。
また、同じランタイムで同様のアルゴリズムを提供し、行列の低エネルギー部分空間に主に置かれる量子状態の準備を可能にします。
論文 参考訳（メタデータ） (2023-11-07T22:52:56Z) - Fast quantum algorithm for differential equations [0.5895819801677125]
我々は、数値複雑性を持つ量子アルゴリズムを、$N$で多対数であるが、大規模なPDEに対して$kappa$とは独立に提示する。
提案アルゴリズムは,解の特徴を抽出する量子状態を生成する。
論文 参考訳（メタデータ） (2023-06-20T18:01:07Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Quantum Algorithm for Matrix Logarithm by Integral Formula [0.0]
近年,行列ベクトル積 $f(A)b$ に対応する状態 $|frangle$ を計算する量子アルゴリズムが提案されている。
サブルーチンとしてLCU法とブロック符号化技術を用いる量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-11-17T05:46:12Z) - Improved quantum lower and upper bounds for matrix scaling [0.0]
古典的2次アルゴリズムにおける量子スピードアップの可能性について検討する。
我々は,高精度システムにおける入力サイズに関して,本質的に量子スピードアップが存在しないことを示す。
我々は低精度方式で改良された量子アルゴリズムを与える。
論文 参考訳（メタデータ） (2021-09-30T17:29:23Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - 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) - Optimal Iterative Sketching with the Subsampled Randomized Hadamard
Transform [64.90148466525754]
最小二乗問題に対する反復スケッチの性能について検討する。
本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。
これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
論文 参考訳（メタデータ） (2020-02-03T16:17:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。