論文の概要: 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)$クエリをしなければならない。
関連論文リスト
- 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) - Linear Bandits on Uniformly Convex Sets [88.3673525964507]
線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。
2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
論文 参考訳(メタデータ) (2021-03-10T07:33:03Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳(メタデータ) (2021-02-15T08:16:51Z) - 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) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳(メタデータ) (2020-07-07T17:10:00Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳(メタデータ) (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。