論文の概要: A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix

• arxiv url: http://arxiv.org/abs/2405.14765v2
• Date: Thu, 14 Nov 2024 18:26:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-15 15:21:41.641617
• Title: A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix
• Title（参考訳）: 行列のトップ固有ベクトル近似のための量子スピードアップ
• Authors: Yanlin Chen, András Gilyén, Ronald de Wolf,
• Abstract要約: 与えられた$dtimes d$ matrix $A$ のトップ固有ベクトルのよい近似を見つけることは、基礎的で重要な計算問題である。 上位固有ベクトルの近似の古典的な記述を出力する2つの異なる量子アルゴリズムを与える。
• 参考スコア（独自算出の注目度）: 2.7050250604223693
• License:
• Abstract: Finding a good approximation of the top eigenvector of a given $d\times d$ matrix $A$ is a basic and important computational problem, with many applications. We give two different quantum algorithms that, given query access to the entries of a Hermitian matrix $A$ and assuming a constant eigenvalue gap, output a classical description of a good approximation of the top eigenvector: one algorithm with time complexity $\mathcal{\tilde{O}}(d^{1.75})$ and one with time complexity $d^{1.5+o(1)}$ (the first algorithm has a slightly better dependence on the $\ell_2$-error of the approximating vector than the second, and uses different techniques of independent interest). Both of our quantum algorithms provide a polynomial speed-up over the best-possible classical algorithm, which needs $\Omega(d^2)$ queries to entries of $A$, and hence $\Omega(d^2)$ time. We extend this to a quantum algorithm that outputs a classical description of the subspace spanned by the top-$q$ eigenvectors in time $qd^{1.5+o(1)}$. We also prove a nearly-optimal lower bound of $\tilde{\Omega}(d^{1.5})$ on the quantum query complexity of approximating the top eigenvector. Our quantum algorithms run a version of the classical power method that is robust to certain benign kinds of errors, where we implement each matrix-vector multiplication with small and well-behaved error on a quantum computer, in different ways for the two algorithms. Our first algorithm estimates the matrix-vector product one entry at a time, using a new "Gaussian phase estimation" procedure. Our second algorithm uses block-encoding techniques to compute the matrix-vector product as a quantum state, from which we obtain a classical description by a new time-efficient unbiased pure-state tomography procedure.
• Abstract（参考訳）: 与えられた$d\times d$ matrix $A$ のトップ固有ベクトルのよい近似を見つけることは、多くの応用において基礎的で重要な計算問題である。 エルミート行列のエントリへのクエリアクセスを与えられたとき、定数固有値ギャップを仮定すると、時間複雑性を持つ1つのアルゴリズム $\mathcal{\tilde{O}}(d^{1.75})$ と時間複雑性を持つ1つのアルゴリズム $d^{1.5+o(1)}$ という2つの異なる量子アルゴリズムを出力する。 どちらの量子アルゴリズムも、$A$のエントリに対して$\Omega(d^2)$クエリが必要であり、従って$\Omega(d^2)$タイムである。 これを量子アルゴリズムに拡張し、qd^{1.5+o(1)}$ の時間で、上位$q$固有ベクトルで区切られた部分空間の古典的な記述を出力する。 また、最上位固有ベクトルを近似する量子クエリの複雑さについて、ほぼ最適の$\tilde{\Omega}(d^{1.5})$を証明した。 我々の量子アルゴリズムは、ある種の良質なエラーに対して頑健な古典的パワーメソッドのバージョンを実行し、そこでは2つのアルゴリズムの異なる方法で、量子コンピュータ上で、小さくてよく定義されたエラーで各行列ベクトル乗法を実装します。 最初のアルゴリズムでは,新しい「ガウス位相推定」手法を用いて,行列ベクトル積を1回に1回推定する。 第2のアルゴリズムはブロックエンコーディング技術を用いて行列ベクトル積を量子状態として計算し、新しい時間効率の非バイアス純状態トモグラフィーによる古典的な記述を得る。

関連論文リスト

• Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices [7.174256268278207]
  古典的マルチロー反復法に着想を得た量子アルゴリズムを提案する。 本アルゴリズムは,不整合系の解法に適した係数行列の要求を小さくする。
  論文  参考訳（メタデータ） (2024-09-06T03:32:02Z)
• Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
  勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。 本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。 また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-07-04T11:03:48Z)
• A square-root speedup for finding the smallest eigenvalue [0.6597195879147555]
  エルミート行列の最小固有値を求める量子アルゴリズムについて述べる。 このアルゴリズムは、量子位相推定と量子振幅推定を組み合わせて、2次高速化を実現する。 また、同じランタイムで同様のアルゴリズムを提供し、行列の低エネルギー部分空間に主に置かれる量子状態の準備を可能にします。
  論文  参考訳（メタデータ） (2023-11-07T22:52:56Z)
• Do you know what q-means? [50.045011844765185]
  クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。 クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。 また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• Fast and Practical Quantum-Inspired Classical Algorithms for Solving Linear Systems [11.929584800629673]
  線形系を解くための高速で実用的な量子インスパイアされた古典的アルゴリズムを提案する。 我々の主な貢献は、線形系を解くために量子に着想を得た古典的アルゴリズムへの重球運動量法の適用である。
  論文  参考訳（メタデータ） (2023-07-13T08:46:19Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  効率的なプライベート推定アルゴリズムを設計するための一般的なツール。 最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
  論文  参考訳（メタデータ） (2023-01-11T09:12:28Z)
• Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
  本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。 文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。 我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
  論文  参考訳（メタデータ） (2021-06-01T19:51:55Z)
• 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)
• 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)

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

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