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

Quantum query complexity of edge connectivity.

Simon Apers, Troy Lee

Published Nov 19, 2020• 0 citations
OpenAlex

Abstract

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.

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

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

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

A sublinear time 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 in time $\widetilde O(\sqrt{m} n^{5/6} W^{1/3} + n^{5/3} W^{2/3})$, given adjacency list access to $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.

•Oct 29, 2021•0 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
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.
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).
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).
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.
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.
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 in time O~(mn5/6W1/3+n5/3W2/3)\widetilde O(\sqrt{m} n^{5/6} W^{1/3} + n^{5/3} W^{2/3})O(m​n5/6W1/3+n5/3W2/3), given adjacency list access to 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 = \Omega(n^2)m=Ω(n2). In contrast, a randomized algorithm must make Ω(m)\Omega(m)Ω(m) queries to the adjacency list of a simple graph GGG even to decide whether sss and ttt are connected.
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.