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 τ, we give a quantum algorithm to solve the minimum cut problem using Õ(n^{3/2}√{τ}) queries and time. Moreover, for every integer 1 ≤ τ ≤ n we give an example of a graph G with edge weights 1 and τ such that solving the minimum cut problem on G requires Ω(n^{3/2}√{τ}) queries to the adjacency matrix of G. These results contrast with the classical randomized case where Ω(n²) 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 ̃ Θ(m). We show that the quantum query and time complexity are Õ(√{mnτ}) and Õ(√{mnτ} + n^{3/2}), respectively, where again the edge weights are between 1 and τ. For dense graphs we give lower bounds on the quantum query complexity of Ω(n^{3/2}) for τ > 1 and Ω(τ n) for any 1 ≤ τ ≤ 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).
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 τ, we give a quantum algorithm to solve the minimum cut problem using Õ(n^{3/2}√{τ}) queries and time. Moreover, for every integer 1 ≤ τ ≤ n we give an example of a graph G with edge weights 1 and τ such that solving the minimum cut problem on G requires Ω(n^{3/2}√{τ}) queries to the adjacency matrix of G. These results contrast with the classical randomized case where Ω(n²) 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 ̃ Θ(m). We show that the quantum query and time complexity are Õ(√{mnτ}) and Õ(√{mnτ} + n^{3/2}), respectively, where again the edge weights are between 1 and τ. For dense graphs we give lower bounds on the quantum query complexity of Ω(n^{3/2}) for τ > 1 and Ω(τ n) for any 1 ≤ τ ≤ 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).
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 τ, we give a quantum algorithm to solve the minimum cut problem using O~(n3/2τ) queries and time. Moreover, for every integer 1≤τ≤n we give an example of a graph G with edge weights 1 and τ such that solving the minimum cut problem on G requires Ω(n3/2τ) many queries to the adjacency matrix of G. These results contrast with the classical randomized case where Ω(n2) 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 Θ~(m). We show that the quantum query and time complexity are O~(mnτ) and O~(mnτ+n3/2), respectively, where again the edge weights are between 1 and τ. For dense graphs we give lower bounds on the quantum query complexity of Ω(n3/2) for τ>1 and Ω(τn) for any 1≤τ≤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).
The edge connectivity of a simple graph is the least number of edges whose removal disconnects the graph. We study the quantum query complexity of computing the edge connectivity of a simple graph with n vertices and m edges in both the adjacency matrix and adjacency array models. For classical randomized algorithms, Ω(n2) and Ω(m) lower bounds are known for these models, respectively, showing that the trivial algorithm is optimal in terms of query complexity for both cases. In contrast, we show upper bounds of O~(n3/2) and O~(mn) on the quantum query complexity of computing edge connectivity in the adjacency matrix and adjacency array models, respectively. Our upper bound is tight up to logarithmic factors for the adjacency matrix model, while for the adjacency array model the best quantum query lower bound we know is Ω(n). Our upper bounds follow by combining a lemma on the structure of near-minimum cuts due to Rubinstein, Schramm and Weinberg (ITCS 2018) with a quantum sparsification algorithm by Apers and de Wolf (FOCS 2020).
For a weighted graph, instead of edge connectivity the relevant notion is the weight of a minimum cut, i.e. the minimum total weight of a set of edges whose removal disconnects the graph. For weighted graphs we show that in the worst case Ω(n2) queries can be needed to compute the weight of a minimum cut by a quantum algorithm in both the adjacency matrix and adjacency array models, thus no quantum speedup is possible in this case.
An s-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-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-t cut after O(mn5/6W1/3) queries to the adjacency list of G. For simple graphs this bound is always O(n11/6), even in the dense case when m=Ω(n2). In contrast, a randomized algorithm must make Ω(m) queries to the adjacency list of a simple graph G even to decide whether s and t are connected.
An s-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-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-t cut in time O(mn5/6W1/3+n5/3W2/3), given adjacency list access to G. For simple graphs this bound is always O(n11/6), even in the dense case when m=Ω(n2). In contrast, a randomized algorithm must make Ω(m) queries to the adjacency list of a simple graph G even to decide whether s and t are connected.
We study the minimum weight cycle problem (MWC) and the minimum weight triangle problem (MWT) in the quantum query model, for n-vertex graphs with integer edge weights in [M] given by their adjacency matrix. Roditty and Vassilevska Williams showed that the two problems are classically equivalent. We show that an exact minimum weight cycle of an undirected graph can be found with O~(n19/12) queries, while Ω(n3/2) queries are necessary. The algorithm learns only the n7/6 lightest vertex pairs, uses quantum counting to locate weight thresholds above them, applies a strict form of the Moore bound to bound the optimum and the size of each weight class, and searches the classes for the few heavy edges of an optimal cycle with nested quantum walks. A simpler version gives O~(n5/3) queries, and searching for fewer heavy edges trades queries for approximation, with a 2-approximation in O~(n8/5) queries and a tight O(logn)-approximation in O~(n3/2) queries. In contrast, MWT costs O(n9/7logM) queries, so the classical equivalence becomes a polynomial separation. For cycles of constant length we give explicit exponents, such as O~(n125/83) for the minimum weight 5-cycle, and we prove that deciding whether a graph has a k-cycle of total weight exactly zero requires Ω(n2−2/(⌊k/2⌋+1)) queries for every constant k≥4. Finally, non-adaptive learning graphs cannot beat n2 for cycles of about logn edges, and we conjecture that exact MWC on directed graphs requires n2−o(1) queries.
In this work, we resolve the query complexity of global minimum cut problem for a graph by designing a randomized algorithm for approximating the size of minimum cut in a graph, where the graph can be accessed through local queries like {\sc Degree}, {\sc Neighbor}, and {\sc Adjacency} queries. Given ε∈(0,1), the algorithm with high probability outputs an estimate t^ satisfying the following (1−ε)t≤t^≤(1+ε)t, where m is the number of edges in the graph and t is the size of minimum cut in the graph. The expected number of local queries used by our algorithm is $\min\left\{m+n,\frac{m}{t}\right\}\mbox{poly}\left(\log n,\frac{1}ε\right)$ where n is the number of vertices in the graph. Eden and Rosenbaum showed that Ω(m/t) many local queries are required for approximating the size of minimum cut in graphs. These two results together resolve the query complexity of the problem of estimating the size of minimum cut in graphs using local queries. Building on the lower bound of Eden and Rosenbaum, we show that, for all t∈N, Ω(m) local queries are required to decide if the size of the minimum cut in the graph is t or t−2. Also, we show that, for any t∈N, Ω(m) local queries are required to find all the minimum cut edges even if it is promised that the input graph has a minimum cut of size t. Both of our lower bound results are randomized, and hold even if we can make {\sc Random Edge} query apart from local queries.