論文の概要: 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$ノルムがある。
これらの量を推定する最も速い古典的ランダム化アルゴリズムは、行列の非零成分の数に少なくとも線形に依存するランタイムを持つ。
行列に対する量子アクセスを仮定すると、我々のアルゴリズムは行列サイズにおいてサブ線形であり、条件数や近似誤差などの他の量に大きく依存しているため、近年の文献で提案されているランダム化および分散された古典的アルゴリズムのほとんどと競合することができる。
これらのアルゴリズムは、スペクトル和の推定がしばしば計算ボトルネックを表す多くの実用的な問題を解決するためのサブルーチンとして使うことができる。
関連論文リスト
- Polynomial-depth quantum algorithm for computing matrix determinant [49.494595696663524]
正方行列の行列式を計算するアルゴリズムを提案し,それを実現する量子回路を構築する。
行列の各行は、ある量子系の純粋な状態として符号化される。
したがって、認められた行列はこれらの系の量子状態の正規化まで任意である。
論文 参考訳(メタデータ) (2024-01-29T23:23:27Z) - A fixed-point algorithm for matrix projections with applications in
quantum information [7.988085110283119]
このアルゴリズムは反復数において最適解に指数関数的に収束することを示す。
量子資源理論および量子シャノン理論における我々のアルゴリズムのいくつかの応用について論じる。
論文 参考訳(メタデータ) (2023-12-22T11:16:11Z) - A square-root speedup for finding the smallest eigenvalue [0.6597195879147555]
エルミート行列の最小固有値を求める量子アルゴリズムについて述べる。
このアルゴリズムは、量子位相推定と量子振幅推定を組み合わせて、2次高速化を実現する。
また、同じランタイムで同様のアルゴリズムを提供し、行列の低エネルギー部分空間に主に置かれる量子状態の準備を可能にします。
論文 参考訳(メタデータ) (2023-11-07T22:52:56Z) - Quantum Algorithm for Dynamic Mode Decomposition and Matrix Eigenvalue
Decomposition with Complex Eigenvalues [0.40792653193642503]
本稿では,量子微分方程式解法によりシミュレーションされた時系列データを解析する量子アルゴリズムを提案する。
我々の量子アルゴリズムは、対応する線形力学系を解析することによって行列固有値の抽出も可能である。
論文 参考訳(メタデータ) (2023-10-26T21:21:51Z) - 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) - A Quantum Computer Amenable Sparse Matrix Equation Solver [0.0]
本稿では,行列方程式の解法に関わる問題について検討する。
Harrow/Hassidim/Lloydアルゴリズムを固有位相推定のための代替ユニタリを提供することにより一般化する。
このユニタリは任意の行列方程式に対して十分に定義されているという利点があり、それによって解の手順を量子ハードウェアに直接実装することができる。
論文 参考訳(メタデータ) (2021-12-05T15:42:32Z) - 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) - Learning nonlinear dynamical systems from a single trajectory [102.60042167341956]
我々は、$x_t+1=sigma(Thetastarx_t)+varepsilon_t$という形の非線形力学系を学ぶアルゴリズムを導入する。
最適なサンプル複雑性と線形ランニング時間を持つ単一軌道から重み行列$Thetastar$を復元するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-04-30T10:42:48Z) - Optimal Iterative Sketching with the Subsampled Randomized Hadamard
Transform [64.90148466525754]
最小二乗問題に対する反復スケッチの性能について検討する。
本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。
これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
論文 参考訳(メタデータ) (2020-02-03T16:17:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。