論文の概要: Quantum Spectral Clustering
- arxiv url: http://arxiv.org/abs/2007.00280v4
- Date: Mon, 14 Jun 2021 07:16:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-11 23:18:56.050483
- Title: Quantum Spectral Clustering
- Title（参考訳）: 量子スペクトルクラスタリング
- Authors: Iordanis Kerenidis, Jonas Landman
- Abstract要約: スペクトルクラスタリングは、非凸構造やネスト構造でデータをクラスタリングするための強力な機械学習アルゴリズムである。
本稿では,エンドツーエンドの量子アルゴリズムのスペクトルクラスタリングを提案し,量子機械学習における多くの研究を拡張した。
- 参考スコア（独自算出の注目度）: 5.414308305392762
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Spectral clustering is a powerful unsupervised machine learning algorithm for
clustering data with non convex or nested structures. With roots in graph
theory, it uses the spectral properties of the Laplacian matrix to project the
data in a low-dimensional space where clustering is more efficient. Despite its
success in clustering tasks, spectral clustering suffers in practice from a
fast-growing running time of $O(n^3)$, where $n$ is the number of points in the
dataset. In this work we propose an end-to-end quantum algorithm performing
spectral clustering, extending a number of works in quantum machine learning.
The quantum algorithm is composed of two parts: the first is the efficient
creation of the quantum state corresponding to the projected Laplacian matrix,
and the second consists of applying the existing quantum analogue of the
$k$-means algorithm. Both steps depend polynomially on the number of clusters,
as well as precision and data parameters arising from quantum procedures, and
polylogarithmically on the dimension of the input vectors. Our numerical
simulations show an asymptotic linear growth with $n$ when all terms are taken
into account, significantly better than the classical cubic growth. This work
opens the path to other graph-based quantum machine learning algorithms, as it
provides routines for efficient computation and quantum access to the
Incidence, Adjacency, and projected Laplacian matrices of a graph.
- Abstract（参考訳）: スペクトルクラスタリングは、非凸構造やネスト構造でデータをクラスタリングするための強力な教師なし機械学習アルゴリズムである。
グラフ理論のルーツとして、ラプラシアン行列のスペクトル特性を用いて、クラスタリングがより効率的である低次元空間にデータを投影する。
クラスタリングタスクの成功にもかかわらず、スペクトルクラスタリングは実際に、データセットのポイント数である$O(n^3)$の急成長する実行時間に悩まされている。
本研究では,スペクトルクラスタリングを行うエンドツーエンドの量子アルゴリズムを提案する。
量子アルゴリズムは2つの部分から構成されており、1つは投影されたラプラシアン行列に対応する量子状態の効率的な生成、2つ目は既存の$k$-meansアルゴリズムの量子アナログを適用することからなる。
どちらのステップも、クラスタの数、量子手続きから生じる精度とデータパラメータ、入力ベクトルの次元に多元的に依存する。
数値シミュレーションにより, 古典的立方体成長よりもかなりよい条件が考慮された場合, 平均$n$の漸近線形成長を示す。
この研究は、Incidence、Adjacency、およびグラフの投影されたラプラシア行列に対する効率的な計算と量子アクセスのためのルーチンを提供するため、他のグラフベースの量子機械学習アルゴリズムへの道を開く。
関連論文リスト
- Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices [7.174256268278207]
古典的マルチロー反復法に着想を得た量子アルゴリズムを提案する。
本アルゴリズムは,不整合系の解法に適した係数行列の要求を小さくする。
論文 参考訳（メタデータ） (2024-09-06T03:32:02Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - Monte Carlo Graph Search for Quantum Circuit Optimization [26.114550071165628]
本研究はモンテカルログラフ探索に基づく量子アーキテクチャ探索アルゴリズムと重要サンプリングの尺度を提案する。
これは、離散ゲートと連続変数を含むゲートの両方に対して、ゲートオーダーの最適化に適用できる。
論文 参考訳（メタデータ） (2023-07-14T14:01:25Z) - Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra [3.4137115855910767]
本稿では,行列関数からのサンプリング作業のためのランダム化量子アルゴリズムのクラスを提案する。
量子ビットの使用は純粋にアルゴリズムであり、量子データ構造には追加の量子ビットは必要ない。
論文 参考訳（メタデータ） (2023-02-03T17:22:49Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - Variational Quantum and Quantum-Inspired Clustering [0.0]
本稿では,変動量子回路に基づくクラスタリングのための量子アルゴリズムを提案する。
このアルゴリズムはデータを多くのクラスタに分類することができ、数量子のノイズ中間スケール量子(NISQ)デバイスで容易に実装できる。
論文 参考訳（メタデータ） (2022-06-20T17:02:19Z) - Tensor Ring Parametrized Variational Quantum Circuits for Large Scale
Quantum Machine Learning [28.026962110693695]
本稿では,テンソルリング表現を用いて回路内の量子状態を圧縮するアルゴリズムを提案する。
ストレージと計算時間は、正確なシミュレーションアルゴリズムによる指数的な増加と比較して、キュービット数とレイヤー数で線形に増加する。
We achieve a test accuracy of 83.33% on Iris dataset and a maximum of 99.30% and 76.31% on binary and ternary classification of MNIST dataset。
論文 参考訳（メタデータ） (2022-01-21T19:54:57Z) - Quantum K-medians Algorithm Using Parallel Euclidean Distance Estimator [0.0]
本稿では,量子ユークリッド推定アルゴリズムを用いた効率的な量子k-メディアンクラスタリングアルゴリズムを提案する。
提案した量子k-メディアンアルゴリズムは、古典的なバージョンに比べて指数速度が向上した。
論文 参考訳（メタデータ） (2020-12-21T06:38:20Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Laplacian Eigenmaps with variational circuits: a quantum embedding of
graph data [0.0]
量子変分回路を用いたラプラシアン固有写像の計算法を提案する。
量子シミュレータを用いた32ノードグラフ上でのテストでは,古典的なラプラシアン固有写像アルゴリズムと同様の性能が得られた。
論文 参考訳（メタデータ） (2020-11-10T14:51:25Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。