論文の概要: Laplacian Eigenmaps with variational circuits: a quantum embedding of
graph data
- arxiv url: http://arxiv.org/abs/2011.05128v1
- Date: Tue, 10 Nov 2020 14:51:25 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-24 19:05:44.299690
- Title: Laplacian Eigenmaps with variational circuits: a quantum embedding of
graph data
- Title（参考訳）: 変分回路を持つラプラシアン固有写像:グラフデータの量子埋め込み
- Authors: Slimane Thabet, Jean-Francois Hullo
- Abstract要約: 量子変分回路を用いたラプラシアン固有写像の計算法を提案する。
量子シミュレータを用いた32ノードグラフ上でのテストでは,古典的なラプラシアン固有写像アルゴリズムと同様の性能が得られた。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: With the development of quantum algorithms, high-cost computations are being
scrutinized in the hope of a quantum advantage. While graphs offer a convenient
framework for multiple real-world problems, their analytics still comes with
high computation and space. By mapping the graph data into a low dimensional
space, in which graph structural information is preserved, the eigenvectors of
the Laplacian matrix constitute a powerful node embedding, called Laplacian
Eigenmaps. Computing these embeddings is on its own an expensive task knowing
that using specific sparse methods, the eigendecomposition of a Laplacian
matrix has a cost of O($rn^2$), $r$ being the ratio of nonzero elements.
We propose a method to compute a Laplacian Eigenmap using a quantum
variational circuit. The idea of our algorithm is to reach the eigenstates of
the laplacian matrix, which can be considered as a hamiltonian operator, by
adapting the variational quantum eigensolver algorithm. By estimating the $d$
first eigenvectors of the Laplacian at the same time, our algorithm directly
generates a $d$ dimension quantum embedding of the graph. We demonstrate that
it is possible to use the embedding for graph machine learning tasks by
implementing a quantum classifier on the top of it. The overall circuit
consists in a full quantum node classification algorithm. Tests on 32 nodes
graph with a quantum simulator shows that we can achieve similar performances
as the classical laplacian eigenmap algorithm. Although mathematical properties
of this approximate approach are not fully understood, this algorithm opens
perspectives for graph pre-processing using noisy quantum computers.
- Abstract（参考訳）: 量子アルゴリズムの開発により、高コスト計算は量子優位性を期待して精査されている。
グラフは複数の実世界の問題に便利なフレームワークを提供するが、その分析には高い計算量と空間が伴う。
グラフデータをグラフ構造情報が保存される低次元空間にマッピングすることにより、ラプラシア行列の固有ベクトルはラプラシア固有写像と呼ばれる強力なノード埋め込みを構成する。
これらの埋め込みを計算することは、特定のスパース法を用いて、ラプラシアン行列の固有分解が非零要素の比である o($rn^2$) のコストを持つことを知って、それ自体は高価なタスクである。
量子変分回路を用いたラプラシアン固有写像の計算法を提案する。
このアルゴリズムの考え方は、変動量子固有解法アルゴリズムを適用することにより、ハミルトン作用素とみなすことができるラプラシアン行列の固有状態に到達することである。
同時にラプラシアンの第一固有ベクトルを$d$と推定することにより、我々のアルゴリズムはグラフの$d$次元量子埋め込みを直接生成する。
本稿では,その上に量子分類器を実装することにより,グラフ機械学習タスクに埋め込みを適用できることを実証する。
回路全体は完全な量子ノード分類アルゴリズムで構成されている。
量子シミュレータを用いた32ノードグラフによるテストでは,従来のラプラシアン固有マップ法と同様の性能が得られる。
この近似アプローチの数学的性質は十分には理解されていないが、このアルゴリズムは雑音量子コンピュータを用いたグラフ前処理の展望を開く。
関連論文リスト
- Quantum Algorithm for Testing Graph Completeness [0.0]
グラフ完全性をテストすることは、コンピュータ科学とネットワーク理論において重要な問題である。
Szegedy量子ウォークと量子位相推定(QPE)を用いた効率的なアルゴリズムを提案する。
このアプローチは、ネットワーク構造解析、古典的なルーティングアルゴリズムの評価、ペア比較に基づくシステム評価に有用である。
論文 参考訳（メタデータ） (2024-07-29T14:56:25Z) - QuOp: A Quantum Operator Representation for Nodes [0.0]
量子演算子を持つグラフ内のノードを表現するための直感的で斬新な手法を導出する。
この方法はパラメータトレーニングを必要とせず、ノード間の類似性を評価する古典的な手法と競合する。
論文 参考訳（メタデータ） (2024-07-19T13:10:04Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。
3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。
数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文 参考訳（メタデータ） (2023-11-19T00:06:11Z) - Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra [3.4137115855910767]
本稿では,行列関数からのサンプリング作業のためのランダム化量子アルゴリズムのクラスを提案する。
量子ビットの使用は純粋にアルゴリズムであり、量子データ構造には追加の量子ビットは必要ない。
論文 参考訳（メタデータ） (2023-02-03T17:22:49Z) - Compilation of algorithm-specific graph states for quantum circuits [55.90903601048249]
本稿では,高レベル言語で記述された量子回路から,アルゴリズム固有のグラフ状態を作成する量子回路コンパイラを提案する。
この計算は、このグラフ状態に関する一連の非パウリ測度を用いて実装することができる。
論文 参考訳（メタデータ） (2022-09-15T14:52:31Z) - A quantum algorithm for solving eigenproblem of the Laplacian matrix of
a fully connected weighted graph [4.045204834863644]
完全連結重み付きグラフのラプラシア行列の固有確率を解くための効率的な量子アルゴリズムを提案する。
具体的には,ブロック符号化フレームワークに基づく最適ハミルトンシミュレーション手法を採用する。
また、このアルゴリズムは対称(非対称)正規化ラプラス行列の固有確率を解くために拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-03-28T02:24:08Z) - Benchmarking Small-Scale Quantum Devices on Computing Graph Edit
Distance [52.77024349608834]
グラフ編集距離(GED: Graph Edit Distance)は、2つのグラフ間の(異なる)相似性の度合いを測定する。
本稿では、GED計算における2つの量子アプローチの比較研究について述べる。
論文 参考訳（メタデータ） (2021-11-19T12:35:26Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative
GLASSO and Projection [58.5350491065936]
グラフ Laplacian 行列 $L$ 上の構造的仮定を考える。
最初の$K$ eigenvectors of $L$は、例えばドメイン固有の基準に基づいて事前選択される。
本稿では,H_u+$$$$barC$で最も適切なグラフラプラシアン行列$L*を計算するために,効率的なハイブリッドグラフラッソ/投影アルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-10-25T18:12:50Z) - Quantum Spectral Clustering [5.414308305392762]
スペクトルクラスタリングは、非凸構造やネスト構造でデータをクラスタリングするための強力な機械学習アルゴリズムである。
本稿では,エンドツーエンドの量子アルゴリズムのスペクトルクラスタリングを提案し,量子機械学習における多くの研究を拡張した。
論文 参考訳（メタデータ） (2020-07-01T07:11:42Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。