論文の概要: Quantum algorithms and lower bounds for eccentricity, radius, and diameter in undirected graphs
- arxiv url: http://arxiv.org/abs/2502.20148v1
- Date: Thu, 27 Feb 2025 14:39:32 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-28 14:56:05.228736
- Title: Quantum algorithms and lower bounds for eccentricity, radius, and diameter in undirected graphs
- Title（参考訳）: 無向グラフにおける偏心性、半径、直径の量子アルゴリズムと下界
- Authors: Adam Wesołowski, Jinge Bao,
- Abstract要約: 本稿では,隣接度リストモデルにおける非方向重み付きグラフの直径と半径の量子アルゴリズムを提案する。
直径については、$widetildeO(sqrtmn3/4)$時間において、直径を2/3ドルの比率で近似する量子アルゴリズムを提案する。
また、上記のすべての問題に対して$Omega(sqrtnm)$の量子クエリローバウンドをミニマ探索問題からの還元により確立する。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: The problems of computing eccentricity, radius, and diameter are fundamental to graph theory. These parameters are intrinsically defined based on the distance metric of the graph. In this work, we propose quantum algorithms for the diameter and radius of undirected, weighted graphs in the adjacency list model. The algorithms output diameter and radius with the corresponding paths in $\widetilde{O}(n\sqrt{m})$ time. Additionally, for the diameter, we present a quantum algorithm that approximates the diameter within a $2/3$ ratio in $\widetilde{O}(\sqrt{m}n^{3/4})$ time. We also establish quantum query lower bounds of $\Omega(\sqrt{nm})$ for all the aforementioned problems through a reduction from the minima finding problem.
- Abstract（参考訳）: 偏心性、半径、直径の計算の問題はグラフ理論の基本である。
これらのパラメータは、グラフの距離メートル法に基づいて本質的に定義される。
本研究では,隣接度リストモデルにおける非方向重み付きグラフの直径と半径の量子アルゴリズムを提案する。
アルゴリズムは、対応する経路を$\widetilde{O}(n\sqrt{m})$ timeで出力する。
さらに、この直径については、$$\widetilde{O}(\sqrt{m}n^{3/4})$ timeにおいて、直径を2/3$の比率で近似する量子アルゴリズムを提案する。
また、上記のすべての問題に対して$\Omega(\sqrt{nm})$の量子クエリローバウンドをミニマ探索問題からの還元により確立する。
関連論文リスト
- A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Dynamic algorithms for k-center on graphs [3.568439282784197]
エッジ更新を行う動的グラフ上での$k$-center問題に対する最初の効率的なアルゴリズムを提供する。
完全に動的な$(2+epsilon)$-approximationアルゴリズムを$k$-center問題に対して提案する。
論文 参考訳（メタデータ） (2023-07-28T13:50:57Z) - Linearized Wasserstein dimensionality reduction with approximation
guarantees [65.16758672591365]
LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。
我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。
また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
論文 参考訳（メタデータ） (2023-02-14T22:12:16Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳（メタデータ） (2023-02-13T22:51:07Z) - Quantum Algorithm for Dynamic Programming Approach for DAGs and
Applications [0.0]
有向非巡回グラフ(DAG)問題に対する動的プログラミング手法のための量子アルゴリズムを提案する。
OR, AND, NAND, MAX, MIN 関数を主な遷移ステップとする問題を解くことができることを示す。
論文 参考訳（メタデータ） (2022-12-29T19:07:39Z) - Causal Bandits for Linear Structural Equation Models [58.2875460517691]
本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。
グラフの構造は知られており、ノードは$N$である。
頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-26T16:21:31Z) - Quantum Complexity of Weighted Diameter and Radius in CONGEST Networks [6.236743421605786]
本稿では,量子CONGESTモデルにおけるグラフの重み付き直径と半径の計算の複雑さについて検討する。
我々は、$widetilde Oleft(minleftn9/10D3/10,nrightright)$という量子アルゴリズムを提示する。
論文 参考訳（メタデータ） (2022-06-06T17:43:27Z) - Complexity of Eccentricities and All-Pairs Shortest Paths in the Quantum
CONGEST Model [5.279257531335345]
本稿では、量子CONGESTモデルにおけるヘテロジスタンスパラメータについて検討し、偏心性およびAPSPのほぼ線形な下界を確立する。
その結果、これらの2つの問題に対して量子スピードアップが存在しないことが示唆された。
論文 参考訳（メタデータ） (2022-06-06T17:42:37Z) - Robust Estimation for Random Graphs [47.07886511972046]
我々は、$n$ノード上のErdHos-R'enyiランダムグラフのパラメータ$p$を頑健に推定する問題について検討する。
情報理論の限界であるすべての$gamma 1/2$に対して、同様の精度で非効率なアルゴリズムを与える。
論文 参考訳（メタデータ） (2021-11-09T18:43:25Z) - Learning High Dimensional Wasserstein Geodesics [55.086626708837635]
高次元の2つの確率分布の間のワッサーシュタイン測地線を計算するための新しい定式化と学習戦略を提案する。
ラグランジュ乗算器の手法を最適輸送(OT)問題の動的定式化に適用することにより、サドル点がワッサーシュタイン測地線であるミニマックス問題を導出する。
次に、深層ニューラルネットワークによる関数のパラメータ化を行い、トレーニングのためのサンプルベースの双方向学習アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-02-05T04:25:28Z) - Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks [0.0]
直径の計算は分散計算における最も中心的な問題の1つである。
正確な直径計算のための$tilde O(sqrtnD)$-round量子分散アルゴリズムを示し、$D$は直径を表す。
これは、CONGESTモデルにおける量子アルゴリズムと古典アルゴリズムの計算能力の分離を示す。
論文 参考訳（メタデータ） (2018-04-09T11:24:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。