論文の概要: Quantum Distributed Algorithms for Detection of Cliques

• arxiv url: http://arxiv.org/abs/2201.03000v1
• Date: Sun, 9 Jan 2022 12:57:02 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-01 21:49:37.361752
• Title: Quantum Distributed Algorithms for Detection of Cliques
• Title（参考訳）: クランク検出のための量子分散アルゴリズム
• Authors: Keren Censor-Hillel, Orr Fischer, Fran\c{c}ois Le Gall, Dean Leitersdorf, Rotem Oshman
• Abstract要約: 本稿では,高速な量子分散傾き検出のためのフレームワークを提案する。 我々の主な技術的貢献は、より小さな斜めに付加できるノードの探索タスクとしてカプセル化することで、斜めを検出するための新しいアプローチである。 Omega(n3/5+epsilon)$ for $K_p$-detection for any $p geq 4$, even the classical (non-quantum) distributed CONGEST set。
• 参考スコア（独自算出の注目度）: 1.8374319565577157
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The possibilities offered by quantum computing have drawn attention in the distributed computing community recently, with several breakthrough results showing quantum distributed algorithms that run faster than the fastest known classical counterparts, and even separations between the two models. A prime example is the result by Izumi, Le Gall, and Magniez [STACS 2020], who showed that triangle detection by quantum distributed algorithms is easier than triangle listing, while an analogous result is not known in the classical case. In this paper we present a framework for fast quantum distributed clique detection. This improves upon the state-of-the-art for the triangle case, and is also more general, applying to larger clique sizes. Our main technical contribution is a new approach for detecting cliques by encapsulating this as a search task for nodes that can be added to smaller cliques. To extract the best complexities out of our approach, we develop a framework for nested distributed quantum searches, which employ checking procedures that are quantum themselves. Moreover, we show a circuit-complexity barrier on proving a lower bound of the form $\Omega(n^{3/5+\epsilon})$ for $K_p$-detection for any $p \geq 4$, even in the classical (non-quantum) distributed CONGEST setting.
• Abstract（参考訳）: 量子コンピューティングが提供する可能性は最近、分散コンピューティングコミュニティで注目を集めており、量子分散アルゴリズムは最も速い古典的アルゴリズムよりも高速に動作し、2つのモデル間の分離さえも示している。 主な例として、izumi, le gall, magniez [stacs 2020]による結果があり、量子分散アルゴリズムによる三角検出は三角形の表示よりも容易であるが、古典的なケースでは類似の結果は知られていない。 本稿では,高速量子分散クランク検出のためのフレームワークを提案する。 これはトライアングルケースの最先端の改良であり、より一般的であり、より大きなクランクサイズに適用できる。 我々の主な技術的貢献は、より小さな斜めに付加できるノードの探索タスクとしてカプセル化することで、斜めを検出するための新しいアプローチである。 我々のアプローチから最良の複雑さを抽出するために、我々はネスト化された分散量子検索のためのフレームワークを開発しました。 さらに、古典的な(非量子)分散CONGEST設定においても、任意の$p \geq 4$に対する$K_p$-検出に対して$\Omega(n^{3/5+\epsilon})$を下界とする回路複雑度障壁を示す。

関連論文リスト

• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。 次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
  論文  参考訳（メタデータ） (2023-11-07T04:59:02Z)
• Making the cut: two methods for breaking down a quantum algorithm [0.0]
  現在、ノイズの多い小規模量子ハードウェアの時代において、計算上の優位性に達する可能性のある量子アルゴリズムを見つけることは、依然として大きな課題である。 我々は、量子アルゴリズムを低い(クエリ)深さのラウンドに分解する2つの方法を特定し、特徴付ける。 最初の問題では並列化が最高のパフォーマンスを提供するのに対し、2番目はより良い選択であることを示す。
  論文  参考訳（メタデータ） (2023-05-17T18:00:06Z)
• 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)
• Concise and Efficient Quantum Algorithms for Distribution Closeness Testing [0.2741266294612775]
  本研究では, 量子計算が分布特性の試験の基礎的問題に与える影響について検討する。 この問題に対して現在最高の量子アルゴリズムを$l1$-distanceと$l2$-distanceのメトリクスで提案する。
  論文  参考訳（メタデータ） (2023-02-13T04:03:59Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• The NISQ Complexity of Collision Finding [2.9405711598281536]
  現代の暗号における基本的なプリミティブである衝突耐性ハッシュは、同じハッシュ値を生成する入力を効率的に見つける方法がないことを保証している。 現在、量子敵はNISQのパワーを備えたフルスケールのコンピュータを必要とする。 本稿では, NISQアルゴリズムの3つの異なるモデルについて検討する。
  論文  参考訳（メタデータ） (2022-11-23T13:55:28Z)
• 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)
• Efficient Bipartite Entanglement Detection Scheme with a Quantum Adversarial Solver [89.80359585967642]
  パラメータ化量子回路で完了した2プレーヤゼロサムゲームとして,両部絡み検出を再構成する。 このプロトコルを線形光ネットワーク上で実験的に実装し、5量子量子純状態と2量子量子混合状態の両部絡み検出に有効であることを示す。
  論文  参考訳（メタデータ） (2022-03-15T09:46:45Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。 3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
  論文  参考訳（メタデータ） (2021-08-03T17:49:09Z)

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

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