論文の概要: A quantum algorithm for solving eigenproblem of the Laplacian matrix of
a fully connected weighted graph
- arxiv url: http://arxiv.org/abs/2203.14451v2
- Date: Sat, 28 May 2022 14:58:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-20 12:06:18.251388
- Title: A quantum algorithm for solving eigenproblem of the Laplacian matrix of
a fully connected weighted graph
- Title（参考訳）: 完全連結重み付きグラフのラプラシアン行列の固有問題を解く量子アルゴリズム
- Authors: Hai-Ling Liu, Su-Juan Qin, Lin-Chun Wan, Chao-Hua Yu, Shi-Jie Pan, Fei
Gao, and Qiao-Yan Wen
- Abstract要約: 完全連結重み付きグラフのラプラシア行列の固有確率を解くための効率的な量子アルゴリズムを提案する。
具体的には,ブロック符号化フレームワークに基づく最適ハミルトンシミュレーション手法を採用する。
また、このアルゴリズムは対称(非対称)正規化ラプラス行列の固有確率を解くために拡張可能であることを示す。
- 参考スコア（独自算出の注目度）: 4.045204834863644
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Solving eigenproblem of the Laplacian matrix of a fully connected weighted
graph has wide applications in data science, machine learning, and image
processing, etc. However, this is very challenging because it involves
expensive matrix operations. Here, we propose an efficient quantum algorithm to
solve it based on a assumption that the element of each vertex and its norms
can be effectively accessed via a quantum random access memory data structure.
Specifically, we adopt the optimal Hamiltonian simulation technique based on
the block-encoding framework to implement the quantum simulation of the
Laplacian matrix. Then, the eigenvalues and eigenvectors of the Laplacian
matrix are extracted by the quantum phase estimation algorithm. The core of our
entire algorithm is to construct the block-encoding of the Laplacian matrix. To
achieve this, we propose in detail how to construct the block-encodings of
operators containing the information of the weight matrix and the degree matrix
respectively, and further obtain the block-encoding of the Laplacian matrix.
Compared with its classical counterpart, our algorithm has a polynomial speedup
on the number of vertices and an exponential speedup on the dimension of each
vertex. We also show that our algorithm can be extended to solve the
eigenproblem of symmetric (non-symmetric) normalized Laplacian matrix.
- Abstract（参考訳）: 完全連結重み付きグラフのラプラシアン行列の固有問題を解くことは、データサイエンス、機械学習、画像処理などに広く応用できる。
しかし、これは高価な行列演算を必要とするため、非常に難しい。
本稿では,各頂点とそのノルムの要素が,量子ランダムアクセスメモリデータ構造を介して効率的にアクセス可能であるという仮定に基づいて,効率の良い量子アルゴリズムを提案する。
具体的には、ブロック符号化フレームワークに基づく最適ハミルトンシミュレーション手法を採用し、ラプラシア行列の量子シミュレーションを実装する。
そして、量子位相推定アルゴリズムにより、ラプラシア行列の固有値と固有ベクトルを抽出する。
アルゴリズム全体のコアは、ラプラシア行列のブロックエンコーディングを構築することである。
そこで本研究では,重み行列と次数行列の情報をそれぞれ含む演算子のブロックエンコーディングを構築する方法を提案し,さらにラプラシア行列のブロックエンコーディングを得る。
古典的手法と比較して,本アルゴリズムは頂点数に対する多項式の高速化と,各頂点の次元に対する指数的速度アップを有する。
また,本アルゴリズムは対称(非対称)正規化ラプラシアン行列の固有問題を解くために拡張可能であることを示した。
関連論文リスト
- A square-root speedup for finding the smallest eigenvalue [0.6597195879147555]
エルミート行列の最小固有値を求める量子アルゴリズムについて述べる。
このアルゴリズムは、量子位相推定と量子振幅推定を組み合わせて、2次高速化を実現する。
また、同じランタイムで同様のアルゴリズムを提供し、行列の低エネルギー部分空間に主に置かれる量子状態の準備を可能にします。
論文 参考訳（メタデータ） (2023-11-07T22:52:56Z) - 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 hybrid quantum-classical algorithm for multichannel quantum scattering
of atoms and molecules [62.997667081978825]
原子と分子の衝突に対するシュリンガー方程式を解くためのハイブリッド量子古典アルゴリズムを提案する。
このアルゴリズムはコーン変分原理の$S$-matrixバージョンに基づいており、基本散乱$S$-matrixを計算する。
大規模多原子分子の衝突をシミュレートするために,アルゴリズムをどのようにスケールアップするかを示す。
論文 参考訳（メタデータ） (2023-04-12T18:10:47Z) - Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra [3.4137115855910767]
本稿では,行列関数からのサンプリング作業のためのランダム化量子アルゴリズムのクラスを提案する。
量子ビットの使用は純粋にアルゴリズムであり、量子データ構造には追加の量子ビットは必要ない。
論文 参考訳（メタデータ） (2023-02-03T17:22:49Z) - Quantum algorithms for matrix operations and linear systems of equations [65.62256987706128]
本稿では,「Sender-Receiver」モデルを用いた行列演算のための量子アルゴリズムを提案する。
これらの量子プロトコルは、他の量子スキームのサブルーチンとして使用できる。
論文 参考訳（メタデータ） (2022-02-10T08:12:20Z) - Quantum Algorithms based on the Block-Encoding Framework for Matrix
Functions by Contour Integrals [1.5293427903448018]
本稿では,量子コンピュータ上での逆の線形結合を実現するための枠組みを示す。
本稿では,このフレームワークに基づく行列関数の量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-06-15T12:10:35Z) - Quantum algorithms for powering stable Hermitian matrices [0.7734726150561088]
行列パワーティング(英: Matrix Powering)は、線形代数における基本的な計算プリミティブである。
古典行列パワーリングアルゴリズムを高速化する2つの量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-03-15T12:20:04Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Multi-View Spectral Clustering with High-Order Optimal Neighborhood
Laplacian Matrix [57.11971786407279]
マルチビュースペクトルクラスタリングは、データ間の固有のクラスタ構造を効果的に明らかにすることができる。
本稿では,高次最適近傍ラプラシア行列を学習するマルチビュースペクトルクラスタリングアルゴリズムを提案する。
提案アルゴリズムは, 1次ベースと高次ベースの両方の線形結合の近傍を探索し, 最適ラプラシア行列を生成する。
論文 参考訳（メタデータ） (2020-08-31T12:28:40Z) - Optimal Iterative Sketching with the Subsampled Randomized Hadamard
Transform [64.90148466525754]
最小二乗問題に対する反復スケッチの性能について検討する。
本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。
これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
論文 参考訳（メタデータ） (2020-02-03T16:17:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。