Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2007.09202 · Leibniz international proceedings in informatics

Query Complexity of Global Minimum Cut

Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar

Published Jul 17, 2020• 3 citations
arXivHTMLPDF

Abstract

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 $ε\in (0,1)$, the algorithm with high probability outputs an estimate $\hat{t}$ satisfying the following $(1-ε) t \leq \hat{t} \leq (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 \in \mathbb{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 \in \mathbb{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.

DOI
10.4230/lipics.approx/random.2021.6

Related papers

Quantum complexity of minimum cut

Simon Apers, Troy Lee

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 $\tilde O(n^{3/2}\sqrtτ)$ queries and time. Moreover, for every integer $1 \le τ\le 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}\sqrtτ)$ many queries to the adjacency matrix of $G$. These results contrast with the classical randomized case where $Ω(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 Θ(m)$. We show that the quantum query and time complexity are $\tilde O(\sqrt{mnτ})$ and $\tilde O(\sqrt{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 \leq τ\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).

arXiv:2011.09823•Nov 19, 2020•0 citations

Quantum Query Complexity of Maximum Degree and its Generalizations

Amin Shiraz Gilani, Nikhil S. Mande, Subhasree Patro +1 more

We study the quantum query complexity of several basic graph problems. 1) We prove a tight $Θ(n^{3/2})$ bound for finding a maximum-out-degree vertex in an $n$-vertex tournament, resolving a conjecture of Mande, Paraashar, and Saurabh [FSTTCS'23]. 2) Using the same proof idea, we give a direct proof that finding a maximum-degree vertex in an $n$-vertex undirected graph requires $Θ(n^{3/2})$ quantum queries, a bound implicit in the work of Apers and Lee [CCC'21]. Both lower bounds above hold even for computing only the maximum degree or maximum out-degree. 3) We also study Maximum $(k,n-k)$-Cut, which asks for the largest cut with one side of size $k$. For every constant $k\geq 1$, we give an $O(n^{2-1/(k+1)})$-query quantum algorithm. 4) We establish a reduction to Maximum $(k,n-k)$-Cut involving $k$-Graph Collision, which asks whether the marked vertices of a known graph contain a $k$-clique. For $k\geq 3$, this yields unconditional lower bounds with exponents strictly larger than $3/2$, showing that this problem is strictly harder than computing maximum degree. Additionally, under a conjecture we propose for $k$-Graph Collision, the reduction yields a lower bound matching our upper bound above.

quant-pharXiv:2610.13906•Oct 12, 2026•0 citations

Quantum Complexity of Minimum Cut

Simon Apers, Troy Lee

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).

Leibniz international proceedings in informatics•Jan 1, 2021•2 citations

Quantum algorithms for graph problems with cut queries

Troy Lee, Miklós Sántha, Shengyu Zhang

Let G be an n-vertex graph with m edges. When asked a subset S of vertices, a cut query on G returns the number of edges of G that have exactly one endpoint in S. We show that there is a bounded-error quantum algorithm that determines all connected components of G after making O(log(n)6) many cut queries. In contrast, it follows from results in communication complexity that any randomized algorithm even just to decide whether the graph is connected or not must make at least Ω(n/log(n)) many cut queries. We further show that with O(log(n)8) many cut queries a quantum algorithm can with high probability output a spanning forest for G. En route to proving these results, we design quantum algorithms for learning a graph using cut queries. We show that a quantum algorithm can learn a graph with maximum degree d after O(d log(n)2) many cut queries, and can learn a general graph with many cut queries. These two upper bounds are tight up to the poly-logarithmic factors, and compare to Ω(dn) and Ω(m/log(n)) lower bounds on the number of cut queries needed by a randomized algorithm for the same problems, respectively. The key ingredients in our results are the Bernstein-Vazirani algorithm, approximate counting with “OR queries”, and learning sparse vectors from inner products as in compressed sensing.

arXiv:2007.08285•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2021•13 citations

Quantum query complexity of edge connectivity.

Simon Apers, Troy Lee

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, $\Omega(n^2)$ and $\Omega(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 $\tilde O(n^{3/2})$ and $\tilde O(\sqrt{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 $\Omega(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 $\Omega(n^2)$ 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.

•Nov 19, 2020•0 citations

A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs

Simon Apers, Arinta Auza, Troy Lee

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 = Ω(n^2)$. 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.

arXiv:2110.15587•Oct 29, 2021•0 citations
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)ε\in (0,1)ε∈(0,1), the algorithm with high probability outputs an estimate t^\hat{t}t^ satisfying the following (1−ε)t≤t^≤(1+ε)t(1-ε) t \leq \hat{t} \leq (1+ε) t(1−ε)t≤t^≤(1+ε)t, where mmm is the number of edges in the graph and ttt is the size of minimum cut in the graph. The expected number of local queries used by our algorithm is min⁡{m+n,mt}\mboxpoly(log⁡n,1ε)\min\left\{m+n,\frac{m}{t}\right\}\mbox{poly}\left(\log n,\frac{1}ε\right)min{m+n,tm​}\mboxpoly(logn,ε1​) where nnn is the number of vertices in the graph. Eden and Rosenbaum showed that Ω(m/t)Ω(m/t)Ω(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∈Nt \in \mathbb{N}t∈N, Ω(m)Ω(m)Ω(m) local queries are required to decide if the size of the minimum cut in the graph is ttt or t−2t-2t−2. Also, we show that, for any t∈Nt \in \mathbb{N}t∈N, Ω(m)Ω(m)Ω(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 ttt. Both of our lower bound results are randomized, and hold even if we can make {\sc Random Edge} query apart from local queries.
The minimum cut problem in an undirected and weighted graph GGG is to find the minimum total weight of a set of edges whose removal disconnects GGG. We completely characterize the quantum query and time complexity of the minimum cut problem in the adjacency matrix model. If GGG has nnn vertices and edge weights at least 111 and at most τττ, we give a quantum algorithm to solve the minimum cut problem using O~(n3/2τ)\tilde O(n^{3/2}\sqrtτ)O~(n3/2τ​) queries and time. Moreover, for every integer 1≤τ≤n1 \le τ\le n1≤τ≤n we give an example of a graph GGG with edge weights 111 and τττ such that solving the minimum cut problem on GGG requires Ω(n3/2τ)Ω(n^{3/2}\sqrtτ)Ω(n3/2τ​) many queries to the adjacency matrix of GGG. These results contrast with the classical randomized case where Ω(n2)Ω(n^2)Ω(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 GGG has mmm edges the classical randomized complexity of the minimum cut problem is Θ~(m)\tilde Θ(m)Θ~(m). We show that the quantum query and time complexity are O~(mnτ)\tilde O(\sqrt{mnτ})O~(mnτ​) and O~(mnτ+n3/2)\tilde O(\sqrt{mnτ} + n^{3/2})O~(mnτ​+n3/2), respectively, where again the edge weights are between 111 and τττ. For dense graphs we give lower bounds on the quantum query complexity of Ω(n3/2)Ω(n^{3/2})Ω(n3/2) for τ>1τ> 1τ>1 and Ω(τn)Ω(τn)Ω(τn) for any 1≤τ≤n1 \leq τ\leq n1≤τ≤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).
We study the quantum query complexity of several basic graph problems. 1) We prove a tight Θ(n3/2)Θ(n^{3/2})Θ(n3/2) bound for finding a maximum-out-degree vertex in an nnn-vertex tournament, resolving a conjecture of Mande, Paraashar, and Saurabh [FSTTCS'23]. 2) Using the same proof idea, we give a direct proof that finding a maximum-degree vertex in an nnn-vertex undirected graph requires Θ(n3/2)Θ(n^{3/2})Θ(n3/2) quantum queries, a bound implicit in the work of Apers and Lee [CCC'21]. Both lower bounds above hold even for computing only the maximum degree or maximum out-degree. 3) We also study Maximum (k,n−k)(k,n-k)(k,n−k)-Cut, which asks for the largest cut with one side of size kkk. For every constant k≥1k\geq 1k≥1, we give an O(n2−1/(k+1))O(n^{2-1/(k+1)})O(n2−1/(k+1))-query quantum algorithm. 4) We establish a reduction to Maximum (k,n−k)(k,n-k)(k,n−k)-Cut involving kkk-Graph Collision, which asks whether the marked vertices of a known graph contain a kkk-clique. For k≥3k\geq 3k≥3, this yields unconditional lower bounds with exponents strictly larger than 3/23/23/2, showing that this problem is strictly harder than computing maximum degree. Additionally, under a conjecture we propose for kkk-Graph Collision, the reduction yields a lower bound matching our upper bound above.
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).
Let G be an n-vertex graph with m edges. When asked a subset S of vertices, a cut query on G returns the number of edges of G that have exactly one endpoint in S. We show that there is a bounded-error quantum algorithm that determines all connected components of G after making O(log(n)6) many cut queries. In contrast, it follows from results in communication complexity that any randomized algorithm even just to decide whether the graph is connected or not must make at least Ω(n/log(n)) many cut queries. We further show that with O(log(n)8) many cut queries a quantum algorithm can with high probability output a spanning forest for G. En route to proving these results, we design quantum algorithms for learning a graph using cut queries. We show that a quantum algorithm can learn a graph with maximum degree d after O(d log(n)2) many cut queries, and can learn a general graph with many cut queries. These two upper bounds are tight up to the poly-logarithmic factors, and compare to Ω(dn) and Ω(m/log(n)) lower bounds on the number of cut queries needed by a randomized algorithm for the same problems, respectively. The key ingredients in our results are the Bernstein-Vazirani algorithm, approximate counting with “OR queries”, and learning sparse vectors from inner products as in compressed sensing.
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 nnn vertices and mmm edges in both the adjacency matrix and adjacency array models. For classical randomized algorithms, Ω(n2)\Omega(n^2)Ω(n2) and Ω(m)\Omega(m)Ω(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)\tilde O(n^{3/2})O~(n3/2) and O~(mn)\tilde O(\sqrt{mn})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)\Omega(n)Ω(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)\Omega(n^2)Ω(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-⁡ts{\operatorname{-}}ts-t minimum cut in a graph corresponds to a minimum weight subset of edges whose removal disconnects vertices sss and ttt. Finding such a cut is a classic problem that is dual to that of finding a maximum flow from sss to ttt. In this work we describe a quantum algorithm for the minimum s-⁡ts{\operatorname{-}}ts-t cut problem on undirected graphs. For an undirected graph with nnn vertices, mmm edges, and integral edge weights bounded by WWW, the algorithm computes with high probability the weight of a minimum s-⁡ts{\operatorname{-}}ts-t cut after O~(mn5/6W1/3)\widetilde O(\sqrt{m} n^{5/6} W^{1/3})O(m​n5/6W1/3) queries to the adjacency list of GGG. For simple graphs this bound is always O~(n11/6)\widetilde O(n^{11/6})O(n11/6), even in the dense case when m=Ω(n2)m = Ω(n^2)m=Ω(n2). In contrast, a randomized algorithm must make Ω(m)Ω(m)Ω(m) queries to the adjacency list of a simple graph GGG even to decide whether sss and ttt are connected.