論文の概要: A quantum algorithm for estimating the determinant

• arxiv url: http://arxiv.org/abs/2504.11049v1
• Date: Tue, 15 Apr 2025 10:32:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-16 22:09:18.067970
• Title: A quantum algorithm for estimating the determinant
• Title（参考訳）: 行列式推定のための量子アルゴリズム
• Authors: Vittorio Giovannetti, Seth Lloyd, Lorenzo Maccone,
• Abstract要約: このアルゴリズムは、$n×n$正のスパース行列の行列式を精度$epsilon$ in time $cal O(log n/epsilon3)$と推定する。 量子スペクトルサンプリングアルゴリズムは、$sum_j f(lambda_j)$とすると、$lambda_j$は行列固有値である。
• 参考スコア（独自算出の注目度）: 4.369550829556577
• License:
• Abstract: We present a quantum algorithm for estimating the matrix determinant based on quantum spectral sampling. The algorithm estimates the logarithm of the determinant of an $n \times n$ positive sparse matrix to an accuracy $\epsilon$ in time ${\cal O}(\log n/\epsilon^3)$, exponentially faster than previously existing classical or quantum algorithms that scale linearly in $n$. The quantum spectral sampling algorithm generalizes to estimating any quantity $\sum_j f(\lambda_j)$, where $\lambda_j$ are the matrix eigenvalues. For example, the algorithm allows the efficient estimation of the partition function $Z(\beta) =\sum_j e^{-\beta E_j}$ of a Hamiltonian system with energy eigenvalues $E_j$, and of the entropy $ S =-\sum_j p_j \log p_j$ of a density matrix with eigenvalues $p_j$.
• Abstract（参考訳）: 量子スペクトルサンプリングに基づいて行列行列式を推定する量子アルゴリズムを提案する。 このアルゴリズムは、$n \times n$ 正のスパース行列の行列式を精度$\epsilon$ in time ${\cal O}(\log n/\epsilon^3)$と推定する。 量子スペクトルサンプリングアルゴリズムは、任意の量$\sum_j f(\lambda_j)$を推定し、$\lambda_j$は行列固有値である。 例えば、このアルゴリズムは分配関数 $Z(\beta) =\sum_j e^{-\beta E_j}$ のエネルギー固有値 $E_j$ とエントロピー $S =-\sum_j p_j \log p_j$ の固有値 $p_j$ を効率的に推定できる。

関連論文リスト

• Quantum algorithm for the gradient of a logarithm-determinant [0.0]
  スパースランク入力演算子の逆を効率的に決定することができる。 入力演算子のすべての$N2$要素の代わりに、量子状態の期待値を測定することは、$O(ksigma)$ timeで実現できる。 このアルゴリズムは、完全に誤り訂正された量子コンピュータ向けに構想されているが、短期的なマシンで実装可能である。
  論文  参考訳（メタデータ） (2025-01-16T09:39:31Z)
• A square-root speedup for finding the smallest eigenvalue [0.6597195879147555]
  エルミート行列の最小固有値を求める量子アルゴリズムについて述べる。 このアルゴリズムは、量子位相推定と量子振幅推定を組み合わせて、2次高速化を実現する。 また、同じランタイムで同様のアルゴリズムを提供し、行列の低エネルギー部分空間に主に置かれる量子状態の準備を可能にします。
  論文  参考訳（メタデータ） (2023-11-07T22:52:56Z)
• Do you know what q-means? [45.810803542748495]
  Kerenidis, Landman, Luongo, Prakash (NeurIPS')によって提案された量子アルゴリズムの改良版を提案する。 我々のアルゴリズムは、先行研究の量子線型代数プリミティブに頼るのではなく、QRAMを用いて単純な状態を作成する。 また、$varepsilon$-$k$-meansに対して、$Obigで実行される"dequantized"アルゴリズムも提示する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。 我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。 我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
  論文  参考訳（メタデータ） (2022-08-19T18:00:34Z)
• 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)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
  我々は、任意の正半定値(PSD)$A$に対して、$(1 pm epsilon)$を$tr(A)$に近似する新しいランダム化アルゴリズムであるHutch++を導入する。 実験ではハッチンソン法を著しく上回る結果を得た。
  論文  参考訳（メタデータ） (2020-10-19T16:45:37Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。 我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。 我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-14T11:05:26Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。