論文の概要: Quantum algorithm for Neighborhood Preserving Embedding

• arxiv url: http://arxiv.org/abs/2110.11541v1
• Date: Fri, 22 Oct 2021 00:55:40 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-10 19:37:07.604666
• Title: Quantum algorithm for Neighborhood Preserving Embedding
• Title（参考訳）: 近傍保存埋め込みのための量子アルゴリズム
• Authors: Shi-Jie Pan, Lin-Chun Wan, Hai-Ling Liu, Yu-Sen Wu, Su-Juan Qin, Qiao-Yan Wen, Fei Gao
• Abstract要約: NPE(Norborhood Preserving Embedding)は重要な線形次元低減技術である。 LiangらはNPEのための変分量子アルゴリズム(VQA)を提案した。 NPEのための完全量子アルゴリズムを提案し、3つのサブアルゴリズムを再設計する。
• 参考スコア（独自算出の注目度）: 4.248054546466641
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Neighborhood Preserving Embedding (NPE) is an important linear dimensionality reduction technique that aims at preserving the local manifold structure. NPE contains three steps, i.e., finding the nearest neighbors of each data point, constructing the weight matrix, and obtaining the transformation matrix. Liang et al. proposed a variational quantum algorithm (VQA) for NPE [Phys. Rev. A 101, 032323 (2020)]. The algorithm consists of three quantum sub-algorithms, corresponding to the three steps of NPE, and was expected to have an exponential speedup on the dimensionality $n$. However, the algorithm has two disadvantages: (1) It is incomplete in the sense that the input of the third sub-algorithm cannot be obtained by the second sub-algorithm. (2) Its complexity cannot be rigorously analyzed because the third sub-algorithm in it is a VQA. In this paper, we propose a complete quantum algorithm for NPE, in which we redesign the three sub-algorithms and give a rigorous complexity analysis. It is shown that our algorithm can achieve a polynomial speedup on the number of data points $m$ and an exponential speedup on the dimensionality $n$ under certain conditions over the classical NPE algorithm, and achieve significant speedup compared to Liang et al.'s algorithm even without considering the complexity of the VQA.
• Abstract（参考訳）: NPE(Norborhood Preserving Embedding)は局所多様体の保存を目的とした重要な線形次元削減手法である。 NPEは、各データポイントの最も近い隣人を見つけ、重み行列を構築し、変換行列を得るという3つのステップを含む。 LiangらはNPEのための変分量子アルゴリズム(VQA)を提案した[Phys. Rev. A 101, 032323 (2020)]。 このアルゴリズムは、NPEの3つのステップに対応する3つの量子準アルゴリズムで構成され、次元$n$の指数的なスピードアップが期待された。 しかし、アルゴリズムには2つの欠点がある:(1)第三次アルゴリズムの入力が第二次アルゴリズムでは得られないという意味で不完全である。 2) 3番目の準アルゴリズムはVQAであるため,その複雑性は厳密には解析できない。 本稿では,NPEのための完全量子アルゴリズムを提案し,三つの部分アルゴリズムを再設計し,厳密な複雑性解析を行う。 提案アルゴリズムは,古典的NPEアルゴリズムの特定の条件下では,データ点数$m$の多項式スピードアップと次元数$n$の指数速度アップを達成でき,VQAの複雑さを考慮せずに,Liangらのアルゴリズムと比較して大幅に高速化できることを示す。

関連論文リスト

• Depth scaling of unstructured search via quantum approximate optimization [0.0]
  変分量子アルゴリズムは、現在の量子計算のデファクトモデルとなっている。 そのような問題の1つは、ある文字列の特定のビットを見つけることで構成される非構造化探索である。 我々は、CTQWを用いてQAOA配列を復元し、最近のトロッター公式の理論の進歩を利用して、クエリの複雑さを束縛する。
  論文  参考訳（メタデータ） (2024-03-22T18:00:03Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Time and Query Complexity Tradeoffs for the Dihedral Coset Problem [0.19731444261635428]
  Z_N$のディヘドラルコセット問題(DCP)は量子コンピューティングやポスト量子暗号において広く研究されている。 Ettinger-Hoyerアルゴリズムは$O(log(N))$クエリでDCPを解くことが知られている。 本稿では,Ettinger-Hoyerアルゴリズムよりも線形クエリ方式を改良した最初のアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-29T05:30:54Z)
• Quantum Topological Data Analysis with Linear Depth and Exponential Speedup [9.820545418277305]
  我々はQTDAアルゴリズムを完全にオーバーホールし、$O(n4/(epsilon2 delta))の指数的高速化深度を改良した。 理論的誤差解析とベッチ数推定のための回路・計算時間・深度複雑度について述べる。
  論文  参考訳（メタデータ） (2021-08-05T18:56:17Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
  本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。 文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。 我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
  論文  参考訳（メタデータ） (2021-06-01T19:51:55Z)
• Quantum Algorithms for Prediction Based on Ridge Regression [0.7612218105739107]
  本稿では,リッジ回帰モデルに基づく量子アルゴリズムを提案する。 提案アルゴリズムは幅広い応用範囲を持ち,提案アルゴリズムは他の量子アルゴリズムのサブルーチンとして利用することができる。
  論文  参考訳（メタデータ） (2021-04-27T11:03:52Z)
• NOMA in UAV-aided cellular offloading: A machine learning approach [59.32570888309133]
  複数の無人航空機(UAV)によるセルローディングのための新しい枠組みの提案 非直交多重アクセス(NOMA)技術は、無線ネットワークのスペクトル効率をさらに向上するために、各UAVに採用されている。 相互深いQ-network (MDQN) アルゴリズムは,UAVの最適3次元軌道と電力配分を共同で決定するために提案される。
  論文  参考訳（メタデータ） (2020-10-18T17:38:48Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)
• Quantum Relief Algorithm [12.599184944451833]
  リリーフアルゴリズム(Relief algorithm)は、Kira と Rendell によって提案された二項分類における特徴選択アルゴリズムである。 Reliefアルゴリズム(quantum Relief algorithm)と呼ばれるReliefアルゴリズムに基づく量子特徴選択アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-01T10:18:34Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。