論文の概要: Quantum Complexity of Weighted Diameter and Radius in CONGEST Networks
- arxiv url: http://arxiv.org/abs/2206.02767v2
- Date: Mon, 26 Sep 2022 06:32:05 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-10 09:23:04.771109
- Title: Quantum Complexity of Weighted Diameter and Radius in CONGEST Networks
- Title（参考訳）: CONGESTネットワークにおける重み付き直径と半径の量子複雑性
- Authors: Xudong Wu and Penghui Yao
- Abstract要約: 本稿では,量子CONGESTモデルにおけるグラフの重み付き直径と半径の計算の複雑さについて検討する。
我々は、$widetilde Oleft(minleftn9/10D3/10,nrightright)$という量子アルゴリズムを提示する。
- 参考スコア（独自算出の注目度）: 6.236743421605786
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper studies the round complexity of computing the weighted diameter
and radius of a graph in the quantum CONGEST model. We present a quantum
algorithm that $(1+o(1))$-approximates the diameter and radius with round
complexity $\widetilde O\left(\min\left\{n^{9/10}D^{3/10},n\right\}\right)$,
where $D$ denotes the unweighted diameter. This exhibits the advantages of
quantum communication over classical communication since computing a
$(3/2-\varepsilon)$-approximation of the diameter and radius in a classical
CONGEST network takes $\widetilde\Omega(n)$ rounds, even if $D$ is constant
[Abboud, Censor-Hillel, and Khoury, DISC '16]. We also prove a lower bound of
$\widetilde\Omega(n^{2/3})$ for $(3/2-\varepsilon)$-approximating the weighted
diameter/radius in quantum CONGEST networks, even if $D=\Theta(\log n)$. Thus,
in quantum CONGEST networks, computing weighted diameter and weighted radius of
graphs with small $D$ is strictly harder than unweighted ones due to Le Gall
and Magniez's $\widetilde O\left(\sqrt{nD}\right)$-round algorithm for
unweighted diameter/radius [PODC '18].
- Abstract（参考訳）: 本稿では,量子集束モデルにおけるグラフの重み付き直径と半径を計算するラウンド複雑性について検討する。
1+o(1))$が直径と半径を近似し、ラウンド複雑性$\widetilde o\left(\min\left\{n^{9/10}d^{3/10},n\right\}\right)$となる量子アルゴリズムを提案する。
これは、古典的なCONGESTネットワークにおける直径と半径の近似の$(3/2-\varepsilon)$-approximationが$\widetilde\Omega(n)$ roundsであり、たとえ$D$が定数であるとしても [Abboud, Censor-Hillel, and Khoury, DISC '16] である。
また、下限の$\widetilde\omega(n^{2/3})$ for $(3/2-\varepsilon)$- 量子集束ネットワークにおける重み付き直径/ラディウスを近似する、たとえ$d=\theta(\log n)$であっても。
したがって、量子CONGESTネットワークでは、L Gall と Magniez の $\widetilde O\left(\sqrt{nD}\right)$-round algorithm for unweighted diameter/radius [PODC '18] により、小さな$D$のグラフの重み付き直径と重み付き半径の計算は、未重み付きよりも厳密に難しい。
関連論文リスト
- Measuring quantum relative entropy with finite-size effect [53.64687146666141]
相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。
我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
論文 参考訳（メタデータ） (2024-06-25T06:07:20Z) - Quantum connection, charges and virtual particles [65.268245109828]
量子バンドル $L_hbar$ には接続 $A_hbar$ が与えられ、そのセクションは標準波動関数 $psi$ がシュリンガー方程式に従う。
L_Cpm$ と接続 $A_hbar$ を相対論的位相空間 $T*R3,1$ に持ち上げ、粒子と反粒子の両方を記述する Dirac スピノルバンドルに結合する。
論文 参考訳（メタデータ） (2023-10-10T10:27:09Z) - Unitarity estimation for quantum channels [7.323367190336826]
ユニタリティ推定は、量子デバイス認証とベンチマークにおいて基礎的で重要な問題である。
我々は、アンシラ効率のアルゴリズムを誘導するユニタリティ推定のための統一的なフレームワークを提供する。
アルゴリズムの$d$-dependenceと$epsilon$-dependenceの両方が最適であることを示す。
論文 参考訳（メタデータ） (2022-12-19T09:36:33Z) - A Fourier Approach to Mixture Learning [46.995354373649675]
d = O(log k/loglog k)$ dimensions under separation $d/sqrtlog k (modulo factor)。
我々の結果は、分布のフーリエスペクトルの穏やかな条件の下で、非ガウス分布の混合を学習するために容易に拡張できる。
論文 参考訳（メタデータ） (2022-10-05T17:35:46Z) - A Framework for Distributed Quantum Queries in the CONGEST Model [0.0]
量子クエリアルゴリズムを量子CONGESTで実装するための一般的なフレームワークを提供する。
分散Deutsch-Jozsa問題に対するプロトコルを一般化する。
また、サイクル検出と計算の問題を量子スピードアップする。
論文 参考訳（メタデータ） (2022-02-22T15:18:39Z) - On quantum algorithms for the Schr\"odinger equation in the
semi-classical regime [27.175719898694073]
半古典的状態におけるシュル・オーディンガーの方程式を考える。
このようなシュル・オーディンガー方程式はボルン=オッペンハイマーの分子動力学やエレンフェストの動力学など多くの応用を見出す。
論文 参考訳（メタデータ） (2021-12-25T20:01:54Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳（メタデータ） (2021-07-22T14:25:16Z) - Quantum double aspects of surface code models [77.34726150561087]
基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。
有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
論文 参考訳（メタデータ） (2021-06-25T17:03:38Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - 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) - Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks [0.0]
直径の計算は分散計算における最も中心的な問題の1つである。
正確な直径計算のための$tilde O(sqrtnD)$-round量子分散アルゴリズムを示し、$D$は直径を表す。
これは、CONGESTモデルにおける量子アルゴリズムと古典アルゴリズムの計算能力の分離を示す。
論文 参考訳（メタデータ） (2018-04-09T11:24:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。