Fugu-MT 論文翻訳(概要): (Quantum) complexity of testing signed graph clusterability

論文の概要: (Quantum) complexity of testing signed graph clusterability

arxiv url: http://arxiv.org/abs/2311.10480v1
Date: Fri, 17 Nov 2023 12:22:10 GMT
ステータス: 処理完了
システム内更新日: 2023-11-20 14:41:11.811203
Title: (Quantum) complexity of testing signed graph clusterability
Title（参考訳）: 符号付きグラフクラスタビリティテストの(量子)複雑さ
Authors: Kuo-Chin Chen, Simon Apers, Min-Hsiu Hsieh
Abstract要約: 本研究では,有界度モデルにおける符号付きグラフのクラスタビリティ試験について検討する。我々は、クラスタビリティをテストするためにクエリ複雑性$tildeO(N)$の量子アルゴリズムを提供する。これはクラスタビリティテストにおける古典的なクエリの複雑さを解決し、我々の量子アルゴリズムが古典的なアルゴリズムよりも有利であることを示す。
参考スコア（独自算出の注目度）: 11.640839589988788
License: http://creativecommons.org/licenses/by/4.0/
Abstract: This study examines clusterability testing for a signed graph in the bounded-degree model. Our contributions are two-fold. First, we provide a quantum algorithm with query complexity $\tilde{O}(N^{1/3})$ for testing clusterability, which yields a polynomial speedup over the best classical clusterability tester known [arXiv:2102.07587]. Second, we prove an $\tilde{\Omega}(\sqrt{N})$ classical query lower bound for testing clusterability, which nearly matches the upper bound from [arXiv:2102.07587]. This settles the classical query complexity of clusterability testing, and it shows that our quantum algorithm has an advantage over any classical algorithm.
Abstract（参考訳）: 本研究では,有界度モデルにおける符号付きグラフのクラスタビリティ試験について検討する。私たちの貢献は2倍です。まず、クラスタビリティをテストするためにクエリ複雑性が$\tilde{O}(N^{1/3})$の量子アルゴリズムを提供する。次に, [arXiv:2102.07587] の上限にほぼ一致するクラスタ性をテストするために, $\tilde{\Omega}(\sqrt{N})$ 古典的なクエリローバウンドを証明した。これはクラスタビリティテストにおける古典的なクエリの複雑さを解決し、我々の量子アルゴリズムが古典的なアルゴリズムよりも有利であることを示す。

関連論文リスト

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)
Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文参考訳（メタデータ） (2023-11-07T04:59:02Z)
Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文参考訳（メタデータ） (2023-06-18T08:46:06Z)
Concise and Efficient Quantum Algorithms for Distribution Closeness Testing [0.2741266294612775]
本研究では, 量子計算が分布特性の試験の基礎的問題に与える影響について検討する。この問題に対して現在最高の量子アルゴリズムを$l1$-distanceと$l2$-distanceのメトリクスで提案する。
論文参考訳（メタデータ） (2023-02-13T04:03:59Z)
Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。我々は距離の計算を高速化するために量子現象を利用する。我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文参考訳（メタデータ） (2022-12-13T16:04:16Z)
Unitary property testing lower bounds by polynomials [0.15229257192293197]
我々は、量子アルゴリズムにブラックボックスのユニタリへのクエリアクセスを与えるユニタリプロパティテストについて研究する。これらの問題の複雑さを特徴づけるには、新しいアルゴリズム技術と低いバウンド法が必要である。我々は、$mathsfQMA$と$mathsfQMA(2)$の間のオラクル分離に対するユニタリなプロパティテストベースのアプローチを示す。
論文参考訳（メタデータ） (2022-10-12T03:01:00Z)
Variational Quantum and Quantum-Inspired Clustering [0.0]
本稿では,変動量子回路に基づくクラスタリングのための量子アルゴリズムを提案する。このアルゴリズムはデータを多くのクラスタに分類することができ、数量子のノイズ中間スケール量子(NISQ)デバイスで容易に実装できる。
論文参考訳（メタデータ） (2022-06-20T17:02:19Z)
Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文参考訳（メタデータ） (2022-05-26T20:32:36Z)
Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。最近の研究は、低次手法のクラスに対する低い境界を確立している。意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文参考訳（メタデータ） (2021-12-07T18:50:17Z)
Quantum Motif Clustering [0.0]
モチーフクラスタリング(モチーフクラスタリング)と呼ばれる高次パターンに基づいて,グラフをクラスタリングするための3つの量子アルゴリズムを提案する。一つはGroverサーチの簡単な応用で、もうひとつは量子近似計数を使い、もうひとつは様々な設定で、最も高速な古典的アルゴリズムよりも、平方根のようなスピードアップが得られる。
論文参考訳（メタデータ） (2021-11-25T19:00:01Z)
Binary Classification with Classical Instances and Quantum Labels [0.0]
古典的統計学習理論において、最もよく研究されている問題の1つは二項分類である。このタスクの量子アナログで、量子状態として与えられたトレーニングデータも激しく研究され、現在では古典的なデータと同じサンプルの複雑さを持つことが知られている。古典的入力と量子出力を持つ写像とそれに対応する古典的量子訓練データを考慮した古典的二項分類タスクの量子バージョンを提案する。
論文参考訳（メタデータ） (2020-06-10T18:00:09Z)

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