Quantum complexity of minimum cut
- URL: http://arxiv.org/abs/2011.09823v3
- Date: Mon, 24 May 2021 13:22:26 GMT
- Title: Quantum complexity of minimum cut
- Authors: Simon Apers and Troy Lee
- Abstract summary: 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)
- Score: 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).
Related papers
- A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering [18.29151197560866]
We consider the semi-random graph model of [Makarychev, Makarychev and Vijayaraghavan, STOC'12].
A time algorithm is known to approximate the Balanced Cut problem up to value $O(alpha)$ [MMV'12] as long as the cut $(A, B)$ has size $Omega(alpha)$.
We study the fine-grained complexity of the problem and present the first near-linear time subroutine that achieves similar performances to that of [MMV'12].
arXiv Detail & Related papers (2024-06-07T11:40:54Z) - 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) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
We consider the problem of minimizing the number of matrix-vector queries needed for accurate trace estimation in the dynamic setting where our underlying matrix is changing slowly.
We provide a novel binary tree summation procedure that simultaneously estimates all $m$ traces up to $epsilon$ error with $delta$ failure probability.
Our lower bounds (1) give the first tight bounds for Hutchinson's estimator in the matrix-vector product model with Frobenius norm error even in the static setting, and (2) are the first unconditional lower bounds for dynamic trace estimation.
arXiv Detail & Related papers (2022-09-30T04:15:44Z) - 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) - A sublinear query quantum algorithm for s-t minimum cut on dense simple
graphs [1.0435741631709405]
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.
arXiv Detail & Related papers (2021-10-29T07:35:46Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals.
Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
arXiv Detail & Related papers (2021-08-19T16:16:48Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
arXiv Detail & Related papers (2020-08-24T06:50:57Z) - 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.