Fugu-MT 論文翻訳(概要): Quantum complexity of minimum cut

論文の概要: Quantum complexity of minimum cut

arxiv url: http://arxiv.org/abs/2011.09823v3
Date: Mon, 24 May 2021 13:22:26 GMT
ステータス: 処理完了
システム内更新日: 2023-04-23 17:19:47.569896
Title: Quantum complexity of minimum cut
Title（参考訳）: 最小カットの量子複雑性
Authors: Simon Apers and Troy Lee
Abstract要約: 隣接行列モデルにおける最小カット問題の量子クエリと時間複雑性を特徴付ける。我々のアルゴリズムは、Apers and de Wolf (FOCS 2020) によるグラフスカラー化のための量子アルゴリズムを用いており、Kawarabayashi and Thorup (STOC 2015) と Rubinstein, Schramm and Weinberg (ITCS 2018) による準最小カットの構造に関する結果である。
参考スコア（独自算出の注目度）: 0.2538209532048867
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
Abstract: The minimum cut problem in an undirected and weighted graph $G$ is to find the minimum total weight of a set of edges whose removal disconnects $G$. We completely characterize the quantum query and time complexity of the minimum cut problem in the adjacency matrix model. If $G$ has $n$ vertices and edge weights at least $1$ and at most $\tau$, we give a quantum algorithm to solve the minimum cut problem using $\tilde O(n^{3/2}\sqrt{\tau})$ queries and time. Moreover, for every integer $1 \le \tau \le n$ we give an example of a graph $G$ with edge weights $1$ and $\tau$ such that solving the minimum cut problem on $G$ requires $\Omega(n^{3/2}\sqrt{\tau})$ many queries to the adjacency matrix of $G$. These results contrast with the classical randomized case where $\Omega(n^2)$ queries to the adjacency matrix are needed in the worst case even to decide if an unweighted graph is connected or not. In the adjacency array model, when $G$ has $m$ edges the classical randomized complexity of the minimum cut problem is $\tilde \Theta(m)$. We show that the quantum query and time complexity are $\tilde O(\sqrt{mn\tau})$ and $\tilde O(\sqrt{mn\tau} + n^{3/2})$, respectively, where again the edge weights are between $1$ and $\tau$. For dense graphs we give lower bounds on the quantum query complexity of $\Omega(n^{3/2})$ for $\tau > 1$ and $\Omega(\tau n)$ for any $1 \leq \tau \leq n$. Our query algorithm uses a quantum algorithm for graph sparsification by Apers and de Wolf (FOCS 2020) and results on the structure of near-minimum cuts by Kawarabayashi and Thorup (STOC 2015) and Rubinstein, Schramm and Weinberg (ITCS 2018). Our time efficient implementation builds on Karger's tree packing technique (STOC 1996).
Abstract（参考訳）: 無向および重み付きグラフ$G$の最小カット問題は、除去が$G$を切断するエッジの集合の最小トータルウェイトを見つけることである。随伴行列モデルにおける最小カット問題の量子クエリと時間複雑性を完全に特徴付ける。もし$G$が少なくとも$n$の頂点と辺の重みを持ち、少なくとも$\tau$を持つなら、$\tilde O(n^{3/2}\sqrt{\tau})$クエリと時間を使って最小カット問題を解決する量子アルゴリズムを与える。さらに、すべての整数 $1 \le \tau \le n$ に対して、エッジウェイトを持つグラフ $G$ と $\tau$ の例を挙げると、$G$ の最小カット問題を解くには$\Omega(n^{3/2}\sqrt{\tau}) と$G$ の隣接行列への多くのクエリが必要である。これらの結果は、非重み付きグラフが接続されているか否かを決定するために、最悪の場合においても、$\Omega(n^2)$クエリが隣接行列に必要となる古典的なランダム化ケースとは対照的である。隣接配列モデルにおいて、$G$が$m$エッジを持つとき、最小カット問題の古典的ランダム化複雑性は$\tilde \Thetaである。 (m)$。量子クエリと時間複雑性はそれぞれ$\tilde O(\sqrt{mn\tau})$と$\tilde O(\sqrt{mn\tau} + n^{3/2})$であることを示す。密度グラフに対しては、$\Omega(n^{3/2})$ for $\tau > 1$ and $\Omega(\tau)の量子クエリ複雑性の低い境界を与える。 n) 1 の \leq \tau \leq n$ に対して。我々のクエリアルゴリズムは、Apers and de Wolf (FOCS 2020) によるグラフスカラー化のための量子アルゴリズムを用いており、Kawarabayashi and Thorup (STOC 2015) と Rubinstein, Schramm and Weinberg (ITCS 2018) による準最小カットの構造に関する結果である。我々の時間効率のよい実装はKarger's Tree Packing Technique (STOC 1996) に基づいている。

関連論文リスト

The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering [18.29151197560866]
我々は[Makarychev, Makarychev and Vijayaraghavan, STOC'12] の半ランダムグラフモデルを考える。時間アルゴリズムは、カットされた$(A, B)$がサイズ$Omega(alpha)$である限り、alphad Cutの問題を最大$O(alpha)$ [MMV'12]に近似することが知られている。この問題の微細な複雑さについて検討し,[MMV'12]と同じような性能を示す最初のニア線形時間サブルーチンを提示する。
論文参考訳（メタデータ） (2024-06-07T11:40:54Z)
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)
A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs [1.0435741631709405]
グラフにおける$soperatorname-t$最小カットは、削除が$s$と$t$を切断するエッジの最小ウェイトサブセットに対応する。この研究では、無向グラフ上の最小$soperatorname-t$カット問題に対する量子アルゴリズムを記述する。
論文参考訳（メタデータ） (2021-10-29T07:35:46Z)
Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文参考訳（メタデータ） (2021-08-19T16:16:48Z)
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 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)

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

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