論文の概要: A Framework for Distributed Quantum Queries in the CONGEST Model
- arxiv url: http://arxiv.org/abs/2202.10969v2
- Date: Fri, 17 Jun 2022 15:36:21 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-24 05:50:36.993592
- Title: A Framework for Distributed Quantum Queries in the CONGEST Model
- Title（参考訳）: CONGESTモデルにおける分散量子クエリのためのフレームワーク
- Authors: Joran van Apeldoorn, Tijn de Vos
- Abstract要約: 量子クエリアルゴリズムを量子CONGESTで実装するための一般的なフレームワークを提供する。
分散Deutsch-Jozsa問題に対するプロトコルを一般化する。
また、サイクル検出と計算の問題を量子スピードアップする。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Quantum CONGEST model is a variant of the CONGEST model, where messages
consist of $O(\log(n))$ qubits. We give a general framework for implementing
quantum query algorithms in Quantum CONGEST, using the concept of
parallel-queries. We apply our framework for distributed quantum queries in two
settings: when data is distributed over the network, and graph theoretical
problems where the network defines the input. The first is slightly unusual in
CONGEST but our results follow almost directly. The second is more traditional
for the CONGEST model but here we require some classical CONGEST steps to get
our results.
In the setting with distributed data, we show how a network can schedule a
meeting in one of $k$ dates using $\tilde{O}(\sqrt{kD}+D)$ rounds, with $D$ the
network diameter. We also give an algorithm for element distinctness: if all
nodes together hold a list of $k$ numbers, they can find a duplicate in $\tilde
O(k^{2/3}D^{1/3}+D)$ rounds. We also generalize the protocol for the
distributed Deutsch-Jozsa problem from the two-party setting considered in
[arXiv:quant-ph/9802040] to general networks, giving a novel separation between
exact classical and exact quantum protocols in CONGEST.
When the input is the network structure itself, we almost directly recover
the $O(\sqrt{nD})$ round diameter computation algorithm of Le Gall and Magniez
[arXiv:1804.02917]. We also compute the radius in the same number of rounds,
and give an $\epsilon$-additive approximation of the average eccentricity in
$\tilde{O}(D+D^{3/2}/\epsilon)$ rounds. Finally, we give quantum speedups for
the problems of cycle detection and girth computation. We detect whether a
graph has a cycle of length at most $k$ in $O(k+(kn)^{1/2-1/\Theta(k)})$
rounds. For girth computation we give an $\tilde{O}(g+(gn)^{1/2-1/\Theta(g)})$
round algorithm for graphs with girth $g$, beating the known classical lower
bound.
- Abstract（参考訳）: 量子集束モデル(quantum congest model)は集束モデルの変種であり、メッセージは$o(\log(n))$ qubitsで構成される。
並列クエリの概念を用いて、量子CONGESTで量子クエリアルゴリズムを実装するための一般的なフレームワークを提供する。
ネットワーク上でデータが分散されている場合と、ネットワークが入力を定義する理論的問題をグラフ化する場合の2つの設定で、分散量子クエリのフレームワークを適用します。
第1回はやや異例だが、結果はほぼ直接的だ。
第2の方法は,より従来的なコンジェストモデルですが,結果を得るためには,いくつかの古典的なコンジェストステップが必要です。
分散データを用いた設定では、ネットワーク直径が$D$の$\tilde{O}(\sqrt{kD}+D)$ラウンドを使用して、ネットワークが$k$日付の1つでミーティングをスケジュールする方法を示す。
すべてのノードが$k$の数値のリストを持っていれば、$\tilde O(k^{2/3}D^{1/3}+D)$のラウンドで重複を見つけることができる。
また, [arxiv:quant-ph/9802040] で考慮される二者構成から一般ネットワークへの分散deutsch-jozsa問題のプロトコルを一般化し, 密集した古典的プロトコルと厳密な量子プロトコルを分離した。
入力がネットワーク構造自身である場合、Le Gall と Magniez [arXiv:1804.02917] の$O(\sqrt{nD})$ round diameter 計算アルゴリズムをほぼ直接復元する。
また、同じラウンド数の半径を計算し、$\tilde{O}(D+D^{3/2}/\epsilon)$ラウンドの平均偏心度を$\epsilon$-additive approximation(英語版)を与える。
最後に、サイクル検出とガース計算の問題を量子スピードアップする。
グラフが少なくとも$O(k+(kn)^{1/2-1/\Theta(k)})$ラウンドで長さのサイクルを持つかどうかを検出する。
桁計算では、桁$g$を持つグラフに対して$\tilde{o}(g+(gn)^{1/2-1/\theta(g)})$ roundアルゴリズムを与える。
関連論文リスト
- Matching the Statistical Query Lower Bound for k-sparse Parity Problems with Stochastic Gradient Descent [83.85536329832722]
勾配勾配降下(SGD)は,$d$次元ハイパーキューブ上の$k$パリティ問題を効率的に解くことができることを示す。
次に、SGDでトレーニングされたニューラルネットワークがどのようにして、小さな統計的エラーで$k$-parityの問題を解決するかを実証する。
論文 参考訳（メタデータ） (2024-04-18T17:57:53Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - 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) - Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。
我々はモンテカルロ法と量子ウォークの量子アナログを利用する。
また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
論文 参考訳（メタデータ） (2022-10-12T19:10:43Z) - Quantum Complexity of Weighted Diameter and Radius in CONGEST Networks [6.236743421605786]
本稿では,量子CONGESTモデルにおけるグラフの重み付き直径と半径の計算の複雑さについて検討する。
我々は、$widetilde Oleft(minleftn9/10D3/10,nrightright)$という量子アルゴリズムを提示する。
論文 参考訳（メタデータ） (2022-06-06T17:43:27Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳（メタデータ） (2021-07-22T14:25:16Z) - Quantum Distributed Complexity of Set Disjointness on a Line [3.2590610391507444]
Set Disjointness on a Line は分散コンピューティングシナリオにおける Set Disjointness 問題の変種である。
条件のない$widetildeOmegabig(sqrt[3]n d2+sqrtn, big)$$$$d + 1$プロセッサを持つライン上の集合不整合のラウンドを証明する。
論文 参考訳（メタデータ） (2020-02-26T21:17:53Z) - Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
NISQとフォールトトレラントの両方の設定で格子シュウィンガーモデルをシミュレートするために、スケーラブルで明示的なデジタル量子アルゴリズムを提供する。
格子単位において、結合定数$x-1/2$と電場カットオフ$x-1/2Lambda$を持つ$N/2$物理サイト上のシュウィンガーモデルを求める。
NISQと耐故障性の両方でコストがかかるオブザーバブルを、単純なオブザーバブルとして推定し、平均ペア密度を推定する。
論文 参考訳（メタデータ） (2020-02-25T19:18:36Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳（メタデータ） (2020-02-18T16:14:55Z) - Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks [0.0]
直径の計算は分散計算における最も中心的な問題の1つである。
正確な直径計算のための$tilde O(sqrtnD)$-round量子分散アルゴリズムを示し、$D$は直径を表す。
これは、CONGESTモデルにおける量子アルゴリズムと古典アルゴリズムの計算能力の分離を示す。
論文 参考訳（メタデータ） (2018-04-09T11:24:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。