論文の概要: A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs

• arxiv url: http://arxiv.org/abs/2110.15587v2
• Date: Mon, 5 Feb 2024 01:45:51 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-07 07:41:21.156022
• Title: A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs
• Title（参考訳）: 高密度単純グラフ上のs-t最小カットに対するサブ線形クエリ量子アルゴリズム
• Authors: Simon Apers, Arinta Auza, Troy Lee
• Abstract要約: グラフにおける$soperatorname-t$最小カットは、削除が$s$と$t$を切断するエッジの最小ウェイトサブセットに対応する。 この研究では、無向グラフ上の最小$soperatorname-t$カット問題に対する量子アルゴリズムを記述する。
• 参考スコア（独自算出の注目度）: 1.0435741631709405
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: An $s{\operatorname{-}}t$ minimum cut in a graph corresponds to a minimum weight subset of edges whose removal disconnects vertices $s$ and $t$. Finding such a cut is a classic problem that is dual to that of finding a maximum flow from $s$ to $t$. In this work we describe a quantum algorithm for the minimum $s{\operatorname{-}}t$ cut problem on undirected graphs. For an undirected graph with $n$ vertices, $m$ edges, and integral edge weights bounded by $W$, the algorithm computes with high probability the weight of a minimum $s{\operatorname{-}}t$ cut after $\widetilde O(\sqrt{m} n^{5/6} W^{1/3})$ queries to the adjacency list of $G$. For simple graphs this bound is always $\widetilde O(n^{11/6})$, even in the dense case when $m = \Omega(n^2)$. In contrast, a randomized algorithm must make $\Omega(m)$ queries to the adjacency list of a simple graph $G$ even to decide whether $s$ and $t$ are connected.
• Abstract（参考訳）: グラフにおける$s{\operatorname{-}}t$ 最小カットは、削除によって$s$ と $t$ が切り離される辺の最小重みサブセットに対応する。 このようなカットを見つけることは、$s$から$t$への最大フローを見つけるという古典的な問題と双対である。 本研究では,無向グラフ上の最小$s{\operatorname{-}}t$カット問題に対する量子アルゴリズムを記述する。 n$頂点、$m$エッジ、および$w$で有界な積分辺重みを持つ無向グラフの場合、アルゴリズムは、$\widetilde o(\sqrt{m} n^{5/6} w^{1/3})$の随伴リストへのクエリに対して、$g$の最小$s{\operatorname{-}}t$の重みを高い確率で計算する。 単純なグラフの場合、この境界は常に$\widetilde O(n^{11/6})$である。 対照的に、ランダム化されたアルゴリズムは、$s$と$t$が接続されているかどうかを決定するために、単純なグラフの隣接リストに$\Omega(m)$クエリをしなければならない。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。 我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。 提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
  論文  参考訳（メタデータ） (2024-08-03T20:08:02Z)
• Efficient Continual Finite-Sum Minimization [52.5238287567572]
  連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。 我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。 また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
  論文  参考訳（メタデータ） (2024-06-07T08:26:31Z)
• A quantum algorithm for learning a graph of bounded degree [1.8130068086063336]
  本稿では,最大$tildeO(d2m3/4)$量子クエリにおいて,$G$のエッジを学習するアルゴリズムを提案する。 特に、確率の高い確率で$tildeO(sqrtm)$量子クエリでサイクルとマッチングを学習するランダム化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-28T21:23:40Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Finding the KT partition of a weighted graph in near-linear time [1.572727650614088]
  カワラバヤシとソープは、単純なグラフ $G = (V,E)$ の最小カットに対して、ほぼ自明な時間決定論的アルゴリズムを与えた。 重み付きグラフの$(1+varepsilon)$-KTパーティションを見つけるために、線形に近い時間ランダム化アルゴリズムを与える。
  論文  参考訳（メタデータ） (2021-11-02T05:26:10Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs [0.0]
  すべての次数$D ge 2$ of girth $> 5$に対して、QAOA$はQAOA$ on $G$よりも大きなカット率を持つことを示す。 任意の定数$p$に対して、すべてのグラフ上でQAOA$_p$と同様に動作する局所古典的MAX-CUTアルゴリズムが存在すると推測する。
  論文  参考訳（メタデータ） (2021-01-14T09:17:20Z)
• Quantum complexity of minimum cut [0.2538209532048867]
  隣接行列モデルにおける最小カット問題の量子クエリと時間複雑性を特徴付ける。 我々のアルゴリズムは、Apers and de Wolf (FOCS 2020) によるグラフスカラー化のための量子アルゴリズムを用いており、Kawarabayashi and Thorup (STOC 2015) と Rubinstein, Schramm and Weinberg (ITCS 2018) による準最小カットの構造に関する結果である。
  論文  参考訳（メタデータ） (2020-11-19T13:51:49Z)
• Quantum algorithms for graph problems with cut queries [17.149741568581096]
  量子アルゴリズムは、$O(d log(n)2) の後に最大$d$のグラフを学習できることを示す。 また、量子アルゴリズムは、$O(sqrtm log(n)3/2)$多くのカットクエリで一般的なグラフを学習できることを示す。
  論文  参考訳（メタデータ） (2020-07-16T12:21:01Z)

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

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