論文の概要: Quantum $k$-nearest neighbors algorithm
- arxiv url: http://arxiv.org/abs/2003.09187v3
- Date: Thu, 17 Jun 2021 15:10:02 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-28 15:48:04.728350
- Title: Quantum $k$-nearest neighbors algorithm
- Title(参考訳): 量子k$-nearest近傍アルゴリズム
- Authors: Afrad Basheer, A. Afham, Sandeep K. Goyal
- Abstract要約: 古典的な$k$NN $-$quantum $k$NN (Q$k$NN) $-$の量子類似を類似度尺度として示す。
従来の$k$NNや既存の$k$NNアルゴリズムとは異なり、提案アルゴリズムは量子データに直接使用することができる。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: One of the simplest and most effective classical machine learning algorithms
is the $k$-nearest neighbors algorithm ($k$NN) which classifies an unknown test
state by finding the $k$ nearest neighbors from a set of $M$ train states. Here
we present a quantum analog of classical $k$NN $-$ quantum $k$NN (Q$k$NN) $-$
based on fidelity as the similarity measure. We show that Q$k$NN algorithm can
be reduced to an instance of the quantum $k$-maxima algorithm, hence the query
complexity of Q$k$NN is $O(\sqrt{kM})$. The non-trivial task in this reduction
is to encode the fidelity information between the test state and all the train
states as amplitudes of a quantum state. Converting this amplitude encoded
information to a digital format enables us to compare them efficiently, thus
completing the reduction. Unlike classical $k$NN and existing quantum $k$NN
algorithms, the proposed algorithm can be directly used on quantum data thereby
bypassing expensive processes such as quantum state tomography. As an example,
we show the applicability of this algorithm in entanglement classification and
quantum state discrimination.
- Abstract(参考訳): 最も単純で効果的な古典的機械学習アルゴリズムの1つは、$k$-nearest neighborsアルゴリズム(k$NN)である。
ここでは、古典的な$k$nn $-$ quantum $k$nn (q$k$nn) $-$の量子アナログを類似度尺度として忠実性に基づいて提示する。
Q$k$NNアルゴリズムは量子$k$-maximaアルゴリズムのインスタンスに還元できるので、Q$k$NNのクエリ複雑性は$O(\sqrt{kM})$である。
この還元における非自明なタスクは、テスト状態と全列車状態の間の忠実度情報を量子状態の振幅として符号化することである。
この振幅符号化情報をデジタルフォーマットに変換することにより、効率よく比較することが可能となり、削減が完了する。
従来の$k$NNや既存の$k$NNアルゴリズムとは異なり、提案アルゴリズムは量子データに直接使用することができ、量子状態トモグラフィなどの高価なプロセスをバイパスすることができる。
一例として,このアルゴリズムが絡み合い分類や量子状態判別に応用可能であることを示す。
関連論文リスト
- Efficient learning of quantum states prepared with few fermionic
non-Gaussian gates [0.0]
ガウスゲートの任意の数で用意された$n$フェルミオンモード上での学習状態の効率的なアルゴリズムを提案する。
我々の研究は、ガウス門をほとんど持たない状態の構造に光を当て、回路の複雑さを改良した上界を提供する。
論文 参考訳(メタデータ) (2024-02-28T19:18:27Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。
3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。
数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文 参考訳(メタデータ) (2023-11-19T00:06:11Z) - Mind the $\tilde{\mathcal{O}}$: Asymptotically Better, but Still
Impractical, Quantum Distributed Algorithms [0.0]
確率の高い分散計算の量子ConGEST-CLIQUEモデルに2つのアルゴリズムを提案する。
従来のCONGEST-CLIQUEモデルでは、既知のアルゴリズムよりもラウンドとメッセージの複雑さが低い。
Groverの検索アルゴリズムの分散バージョンを使用して三角形探索を高速化する既存のフレームワークは、スピードアップのコアにある。
論文 参考訳(メタデータ) (2023-04-06T02:18:52Z) - Fast Quantum Algorithms for Trace Distance Estimation [8.646488471216262]
本稿では, 加算誤差$varepsilon$内のトレース距離を, ランク$r$の混合量子状態間で推定する効率的な量子アルゴリズムを提案する。
低ランクトレース距離推定の判定版が$mathsfBQP$-completeであることを示す。
論文 参考訳(メタデータ) (2023-01-17T10:16:14Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳(メタデータ) (2022-12-13T16:04:16Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳(メタデータ) (2022-07-07T08:04:15Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳(メタデータ) (2022-05-26T20:32:36Z) - Exponential separations between learning with and without quantum memory [17.763817187554096]
量子システムと力学の学習特性を学習するための量子メモリのパワーについて検討する。
多くの最先端の学習アルゴリズムは、追加の外部量子メモリへのアクセスを必要とする。
このトレードオフは、幅広い学習問題に固有のものであることを示す。
論文 参考訳(メタデータ) (2021-11-10T19:03:49Z) - Can Noise on Qubits Be Learned in Quantum Neural Network? A Case Study
on QuantumFlow [25.408147000243158]
本論文は、別の角度からノイズ問題に取り組むことを目的としている。
一般量子アルゴリズムのための完全量子ビットを作成する代わりに、専用アルゴリズムのノイズ問題を緩和する可能性について検討する。
本稿では、量子ニューラルネットワーク(QNN)を対象とし、トレーニングフェーズにおける誤りを学習し、識別されたQNNモデルがノイズに耐性を持つようにすることを提案する。
論文 参考訳(メタデータ) (2021-09-08T04:43:12Z) - Quantum Algorithm for Fidelity Estimation [8.270684567157987]
2つの未知の混合量子状態 $rho$ と $sigma$ に対して、それらの忠実度 $F(rho,sigma)$ は基本的な問題である。
我々は、この問題を$namepoly(log (N), r, 1/varepsilon)$ timeで解く量子アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-03-16T13:57:01Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。