論文の概要: Quantum diffusion map for nonlinear dimensionality reduction
- arxiv url: http://arxiv.org/abs/2106.07302v1
- Date: Mon, 14 Jun 2021 11:14:01 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-15 15:33:48.857018
- Title: Quantum diffusion map for nonlinear dimensionality reduction
- Title(参考訳): 非線形次元低減のための量子拡散マップ
- Authors: Apimuk Sornsaeng, Ninnat Dangniam, Pantita Palittapongarnpim, Thiparat
Chotibut
- Abstract要約: 拡散マップ(DM)は、高次元データセットに隠された低次元データ構造の自動識別を提供する教師なし機械学習のクラスである。
我々は、量子拡散マップ(qDM)と呼ばれるDMのための量子アルゴリズムを提案する。
我々のqDMは入力N古典的データベクトルとして、時間$O(log3 N)$でマルコフ遷移行列の固有分解を行い、固有ベクトルの読み出しを通して拡散写像を構築する。
- 参考スコア(独自算出の注目度): 2.724141845301679
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Inspired by random walk on graphs, diffusion map (DM) is a class of
unsupervised machine learning that offers automatic identification of
low-dimensional data structure hidden in a high-dimensional dataset. In recent
years, among its many applications, DM has been successfully applied to
discover relevant order parameters in many-body systems, enabling automatic
classification of quantum phases of matter. However, classical DM algorithm is
computationally prohibitive for a large dataset, and any reduction of the time
complexity would be desirable. With a quantum computational speedup in mind, we
propose a quantum algorithm for DM, termed quantum diffusion map (qDM). Our qDM
takes as an input N classical data vectors, performs an eigen-decomposition of
the Markov transition matrix in time $O(\log^3 N)$, and classically constructs
the diffusion map via the readout (tomography) of the eigenvectors, giving a
total runtime of $O(N^2 \text{polylog}\, N)$. Lastly, quantum subroutines in
qDM for constructing a Markov transition operator, and for analyzing its
spectral properties can also be useful for other random walk-based algorithms.
- Abstract(参考訳): グラフ上のランダムウォークにインスパイアされた拡散マップ(DM)は、高次元データセットに隠された低次元データ構造の自動識別を提供する教師なし機械学習のクラスである。
近年、多くの応用において、DMは多体系における関連する秩序パラメータの発見に成功し、物質の量子位相の自動分類を可能にしている。
しかし、古典的DMアルゴリズムは大規模データセットでは計算が禁止されており、時間複雑性の低減が望ましい。
量子計算の高速化を念頭に置いて,量子拡散マップ(qdm)と呼ばれるdmのための量子アルゴリズムを提案する。
我々のqDMは、入力Nの古典的データベクトルとして、時間$O(\log^3 N)$でマルコフ遷移行列の固有分解を行い、古典的には固有ベクトルの読み出し(トモグラフィ)を通して拡散マップを構築し、合計ランタイムは$O(N^2 \text{polylog}\, N)$である。
最後に、マルコフ遷移作用素を構成するためのqDMの量子サブルーチンとそのスペクトル特性の分析は、他のランダムウォークベースのアルゴリズムにも有用である。
関連論文リスト
- Polynomial-depth quantum algorithm for computing matrix determinant [49.494595696663524]
正方行列の行列式を計算するアルゴリズムを提案し,それを実現する量子回路を構築する。
行列の各行は、ある量子系の純粋な状態として符号化される。
したがって、認められた行列はこれらの系の量子状態の正規化まで任意である。
論文 参考訳(メタデータ) (2024-01-29T23:23:27Z) - Stochastic Quantum Sampling for Non-Logconcave Distributions and
Estimating Partition Functions [13.16814860487575]
非対数確率分布からサンプリングする量子アルゴリズムを提案する。
f$ は有限和 $f(x):= frac1Nsum_k=1N f_k(x)$ と書くことができる。
論文 参考訳(メタデータ) (2023-10-17T17:55:32Z) - Randomized semi-quantum matrix processing [0.0]
汎用行列関数のモンテカルロシミュレーションのためのハイブリッド量子古典フレームワークを提案する。
我々のフレームワークは、初期のフォールトトレラント量子線型代数アプリケーションへの経路を提供する。
論文 参考訳(メタデータ) (2023-07-21T18:00:28Z) - End-to-end resource analysis for quantum interior point methods and
portfolio optimization [92.13478140615481]
問題入力から問題出力までの完全な量子回路レベルのアルゴリズム記述を提供する。
アルゴリズムの実行に必要な論理量子ビットの数と非クリフォードTゲートの量/深さを報告する。
論文 参考訳(メタデータ) (2022-11-22T18:54:48Z) - Quantum-inspired algorithm applied to extreme learning [0.6181093777643575]
量子インスパイアされた特異値分解を極端な学習フレームワークに適用する。
スピードアップは、それらのノルムに従って行列要素の効率的なサンプリングによって可能である。
この研究は量子インスパイアされたアルゴリズムの実用化に向けた第一歩である。
論文 参考訳(メタデータ) (2022-09-26T06:49:53Z) - A quantum algorithm for training wide and deep classical neural networks [72.2614468437919]
勾配勾配勾配による古典的トレーサビリティに寄与する条件は、量子線形系を効率的に解くために必要な条件と一致することを示す。
MNIST画像データセットがそのような条件を満たすことを数値的に示す。
我々は、プールを用いた畳み込みニューラルネットワークのトレーニングに$O(log n)$の実証的証拠を提供する。
論文 参考訳(メタデータ) (2021-07-19T23:41:03Z) - Quantum Algorithms for Data Representation and Analysis [68.754953879193]
機械学習におけるデータ表現のための固有problemsの解を高速化する量子手続きを提供する。
これらのサブルーチンのパワーと実用性は、主成分分析、対応解析、潜在意味解析のための入力行列の大きさのサブ線形量子アルゴリズムによって示される。
その結果、入力のサイズに依存しない実行時のパラメータは妥当であり、計算モデル上の誤差が小さいことが示され、競合的な分類性能が得られる。
論文 参考訳(メタデータ) (2021-04-19T00:41:43Z) - Tree tensor network classifiers for machine learning: from
quantum-inspired to quantum-assisted [0.0]
本稿では,データベクトルの長さが指数関数的に大きいヒルベルト空間において,多変量データを量子状態に符号化する量子支援機械学習(QAML)法について述べる。
本稿ではゲートベースの量子コンピューティングデバイスに実装可能なアプローチを提案する。
論文 参考訳(メタデータ) (2021-04-06T02:31:48Z) - Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
時間に依存しない深さの量子回路を生成するための構成的アルゴリズムを提案する。
一次元横フィールドXYモデルにおけるアンダーソン局在化を含む、モデルの特殊クラスに対するアルゴリズムを強調する。
幅広いスピンモデルとフェルミオンモデルに対して正確な回路を提供するのに加えて、我々のアルゴリズムは最適なハミルトニアンシミュレーションに関する幅広い解析的および数値的な洞察を提供する。
論文 参考訳(メタデータ) (2021-04-01T19:06:00Z) - Quantum Dimensionality Reduction by Linear Discriminant Analysis [14.671957651032638]
データの次元性低減(DR)は、パターン認識やデータ分類など、多くの機械学習タスクにおいて重要な問題である。
本稿では,次元減少のための線形判別分析(LDA)を効率的に行う量子アルゴリズムと量子回路を提案する。
論文 参考訳(メタデータ) (2021-03-04T16:06:30Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。