論文の概要: Efficient Quantum Approximate $k$NN Algorithm via Granular-Ball Computing

• arxiv url: http://arxiv.org/abs/2505.23066v1
• Date: Thu, 29 May 2025 04:16:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-30 18:14:07.672081
• Title: Efficient Quantum Approximate $k$NN Algorithm via Granular-Ball Computing
• Title（参考訳）: 粒界計算による効率的な量子近似$k$NNアルゴリズム
• Authors: Shuyin Xia, Xiaojiang Tian, Suzhen Yuan, Jeremiah D. Deng,
• Abstract要約: リアルタイム複雑性は、$k$-Nearest Neighbors($k$NN)が直面する最大の課題の1つ 我々は、Granular-BallベースのQuantum $k$NN(GB-Q$k$NN)と呼ばれる革新的なアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 4.294483824607684
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: High time complexity is one of the biggest challenges faced by $k$-Nearest Neighbors ($k$NN). Although current classical and quantum $k$NN algorithms have made some improvements, they still have a speed bottleneck when facing large amounts of data. To address this issue, we propose an innovative algorithm called Granular-Ball based Quantum $k$NN(GB-Q$k$NN). This approach achieves higher efficiency by first employing granular-balls, which reduces the data size needed to processed. The search process is then accelerated by adopting a Hierarchical Navigable Small World (HNSW) method. Moreover, we optimize the time-consuming steps, such as distance calculation, of the HNSW via quantization, further reducing the time complexity of the construct and search process. By combining the use of granular-balls and quantization of the HNSW method, our approach manages to take advantage of these treatments and significantly reduces the time complexity of the $k$NN-like algorithms, as revealed by a comprehensive complexity analysis.
• Abstract（参考訳）: リアルタイムの複雑性は、$k$-Nearest Neighbors($k$NN)が直面している最大の課題の1つだ。 現在の古典的および量子的な$k$NNアルゴリズムはいくつかの改良がなされているが、大量のデータに直面している場合の速度ボトルネックは依然として残っている。 そこで本研究では,Granular-BallをベースとしたQuantum $k$NN(GB-Q$k$NN)という革新的なアルゴリズムを提案する。 このアプローチは、グラニュラーボールを用いることで、処理に必要なデータサイズを減らすことにより、高い効率を実現する。 そして、階層的ナビゲート可能な小型世界(HNSW)方式を採用することにより、探索処理を高速化する。 さらに,HNSWの量子化による距離計算などの時間消費を最適化し,構成・探索過程の時間的複雑さを低減させる。 HNSW法のグラニュラーボールの利用と量子化を組み合わせることで、我々はこれらの処理をうまく利用し、包括的複雑性解析で明らかになったように、$k$NNのようなアルゴリズムの時間的複雑さを著しく低減できる。

関連論文リスト

• Qubit-efficient quantum local search for combinatorial optimization [0.0]
  本稿では,lceil log l rceil$ qubitsのみを用いた局所探索の量子バージョンを実装した量子ビット効率変動量子アルゴリズムを提案する。 この成果は、短期量子デバイスにおける大規模最適化問題を解決するアルゴリズムの可能性を強調している。
  論文  参考訳（メタデータ） (2025-02-04T11:44:34Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Depth scaling of unstructured search via quantum approximate optimization [0.0]
  変分量子アルゴリズムは、現在の量子計算のデファクトモデルとなっている。 そのような問題の1つは、ある文字列の特定のビットを見つけることで構成される非構造化探索である。 我々は、CTQWを用いてQAOA配列を復元し、最近のトロッター公式の理論の進歩を利用して、クエリの複雑さを束縛する。
  論文  参考訳（メタデータ） (2024-03-22T18:00:03Z)
• Replicable Learning of Large-Margin Halfspaces [46.91303295440005]
  我々は,大マージンハーフスペースを学習する問題に対して,効率的なアルゴリズムを提供する。 Impagliazzo, Lei, Pitassi, Sorrellによるアルゴリズム [STOC 2022] の改良を行った。
  論文  参考訳（メタデータ） (2024-02-21T15:06:51Z)
• Variational Quantum Algorithms for the Allocation of Resources in a Cloud/Edge Architecture [1.072460284847973]
  変分量子アルゴリズムは, 近い将来, 古典的アルゴリズムの代替となる可能性が示唆された。 特に、2つのアルゴリズム、すなわち量子近似最適化アルゴリズム(QAOA)と変分量子固有解器(VQE)の性能を比較した。 シミュレーション実験は、クラウドと2つのエッジノードを含む %CM230124 の単純な問題に対して実施され、VQE アルゴリズムは、検索空間を制限できる適切な回路テクスタイタンサッチを備えている場合に、より良い性能を保証することを示す。
  論文  参考訳（メタデータ） (2024-01-25T17:37:40Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)

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

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