論文の概要: A square-root speedup for finding the smallest eigenvalue

• arxiv url: http://arxiv.org/abs/2311.04379v1
• Date: Tue, 7 Nov 2023 22:52:56 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-09 17:28:09.479515
• Title: A square-root speedup for finding the smallest eigenvalue
• Title（参考訳）: 最小固有値を求める平方根高速化
• Authors: Alex Kerzner, Vlad Gheorghiu, Michele Mosca, Thomas Guilbaud, Federico Carminati, Fabio Fracas, Luca Dellantonio
• Abstract要約: エルミート行列の最小固有値を求める量子アルゴリズムについて述べる。 このアルゴリズムは、量子位相推定と量子振幅推定を組み合わせて、2次高速化を実現する。 また、同じランタイムで同様のアルゴリズムを提供し、行列の低エネルギー部分空間に主に置かれる量子状態の準備を可能にします。
• 参考スコア（独自算出の注目度）: 0.6597195879147555
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We describe a quantum algorithm for finding the smallest eigenvalue of a Hermitian matrix. This algorithm combines Quantum Phase Estimation and Quantum Amplitude Estimation to achieve a quadratic speedup with respect to the best classical algorithm in terms of matrix dimensionality, i.e., $\widetilde{\mathcal{O}}(\sqrt{N}/\epsilon)$ black-box queries to an oracle encoding the matrix, where $N$ is the matrix dimension and $\epsilon$ is the desired precision. In contrast, the best classical algorithm for the same task requires $\Omega(N)\text{polylog}(1/\epsilon)$ queries. In addition, this algorithm allows the user to select any constant success probability. We also provide a similar algorithm with the same runtime that allows us to prepare a quantum state lying mostly in the matrix's low-energy subspace. We implement simulations of both algorithms and demonstrate their application to problems in quantum chemistry and materials science.
• Abstract（参考訳）: エルミート行列の最小固有値を求める量子アルゴリズムについて述べる。 このアルゴリズムは、量子位相推定と量子振幅推定を組み合わせることで、行列次元の最良の古典的アルゴリズム、すなわち、行列を符号化するオラクルに対して、$n$が行列次元であり$\epsilon$が所望の精度である$\widetilde{\mathcal{o}}(\sqrt{n}/\epsilon)$ブラックボックスクエリを実現する。 対照的に、同じタスクに最適な古典的アルゴリズムは$\Omega(N)\text{polylog}(1/\epsilon)$クエリを必要とする。 さらに、このアルゴリズムにより、ユーザは一定の成功確率を選択できる。 また、同じランタイムで同様のアルゴリズムを提供し、行列の低エネルギー部分空間に主に置かれる量子状態の準備を可能にします。 両アルゴリズムのシミュレーションを実装し,量子化学および材料科学における問題への応用を実証する。

関連論文リスト

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix [2.7050250604223693]
  与えられた$dtimes d$ matrix $A$ のトップ固有ベクトルのよい近似を見つけることは、基礎的で重要な計算問題である。 上位固有ベクトルの近似の古典的な記述を出力する2つの異なる量子アルゴリズムを与える。
  論文  参考訳（メタデータ） (2024-05-23T16:33:13Z)
• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。 3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。 数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
  論文  参考訳（メタデータ） (2023-11-19T00:06:11Z)
• A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [102.46640028830441]
  最適行列乗算重み更新(OMMWU)アルゴリズムを導入し,平均収束複雑性を$mathcalO(d/epsilon)$ to $epsilon$-Nash equilibriaとする。 この二次的なスピードアップは、量子ゼロサムゲームにおける$epsilon$-Nash平衡の計算のための新しいベンチマークを定めている。
  論文  参考訳（メタデータ） (2023-11-17T20:38:38Z)
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra [3.4137115855910767]
  本稿では,行列関数からのサンプリング作業のためのランダム化量子アルゴリズムのクラスを提案する。 量子ビットの使用は純粋にアルゴリズムであり、量子データ構造には追加の量子ビットは必要ない。
  論文  参考訳（メタデータ） (2023-02-03T17:22:49Z)
• 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)
• A quantum algorithm for solving eigenproblem of the Laplacian matrix of a fully connected weighted graph [4.045204834863644]
  完全連結重み付きグラフのラプラシア行列の固有確率を解くための効率的な量子アルゴリズムを提案する。 具体的には,ブロック符号化フレームワークに基づく最適ハミルトンシミュレーション手法を採用する。 また、このアルゴリズムは対称(非対称)正規化ラプラス行列の固有確率を解くために拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-28T02:24:08Z)
• 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)
• 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)

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

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