A sublinear query quantum algorithm for s-t minimum cut on dense simple
graphs
- URL: http://arxiv.org/abs/2110.15587v2
- Date: Mon, 5 Feb 2024 01:45:51 GMT
- Title: A sublinear query quantum algorithm for s-t minimum cut on dense simple
graphs
- Authors: Simon Apers, Arinta Auza, Troy Lee
- Abstract summary: An $soperatorname-t$ minimum cut in a graph corresponds to a minimum weight subset of edges whose removal disconnects $s$ and $t$.
In this work we describe a quantum algorithm for the minimum $soperatorname-t$ cut problem on undirected graphs.
- Score: 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.
Related papers
- Efficient Continual Finite-Sum Minimization [52.5238287567572]
We propose a key twist into the finite-sum minimization, dubbed as continual finite-sum minimization.
Our approach significantly improves upon the $mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$ requires.
We also prove that there is no natural first-order method with $mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$, establishing that the first-order complexity of our method is nearly tight.
arXiv Detail & Related papers (2024-06-07T08:26:31Z) - A quantum algorithm for learning a graph of bounded degree [1.8130068086063336]
We present an algorithm that learns the edges of $G$ in at most $tildeO(d2m3/4)$ quantum queries.
In particular, we present a randomized algorithm that, with high probability, learns cycles and matchings in $tildeO(sqrtm)$ quantum queries.
arXiv Detail & Related papers (2024-02-28T21:23:40Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem.
We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
arXiv Detail & Related papers (2022-04-13T22:18:47Z) - Finding the KT partition of a weighted graph in near-linear time [1.572727650614088]
Kawarabayashi and Thorup gave a near-trivial time deterministic algorithm for minimum cut in a simple graph $G = (V,E)$.
We give a near-linear time randomized algorithm to find the $(1+varepsilon)$-KT partition of a weighted graph.
arXiv Detail & Related papers (2021-11-02T05:26:10Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling.
Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
arXiv Detail & Related papers (2021-10-21T18:43:00Z) - Linear Bandits on Uniformly Convex Sets [88.3673525964507]
Linear bandit algorithms yield $tildemathcalO(nsqrtT)$ pseudo-regret bounds on compact convex action sets.
Two types of structural assumptions lead to better pseudo-regret bounds.
arXiv Detail & Related papers (2021-03-10T07:33:03Z) - Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth
regular graphs [0.0]
We show that for all degrees $D ge 2$ of girth $> 5$, QAOA$ has a larger expected cut fraction than QAOA$$ on $G$.
We conjecture that for every constant $p$, there exists a local classical MAX-CUT algorithm that performs as well as QAOA$_p$ on all graphs.
arXiv Detail & Related papers (2021-01-14T09:17:20Z) - Quantum complexity of minimum cut [0.2538209532048867]
We characterize the quantum query and time complexity of the minimum cut problem in the adjacency matrix model.
Our 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)
arXiv Detail & Related papers (2020-11-19T13:51:49Z) - Quantum algorithms for graph problems with cut queries [17.149741568581096]
We show that a quantum algorithm can learn a graph with maximum degree $d$ after $O(d log(n)2)$ many cut queries.
We also show that a quantum algorithm can learn a general graph with $O(sqrtm log(n)3/2)$ many cut queries.
arXiv Detail & Related papers (2020-07-16T12:21:01Z) - Streaming Complexity of SVMs [110.63976030971106]
We study the space complexity of solving the bias-regularized SVM problem in the streaming model.
We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
arXiv Detail & Related papers (2020-07-07T17:10:00Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model.
Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
arXiv Detail & Related papers (2020-02-09T03:39:46Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.