# Quantum query complexity of edge connectivity

**Authors:** Simon Apers, Troy Lee  
**arXiv:** [2011.09823](https://arxiv.org/abs/2011.09823)  
**Date:** 2020-11-19  
**Summary page:** https://www.summarizepaper.com/en/paper/2011.09823v1/

## Key points

- The paper studies the quantum query complexity of computing edge connectivity in simple graphs.
- Edge connectivity is defined as the minimum number of edges whose removal disconnects the graph.
- Lower bounds of $\Omega(n^2)$ and $\Omega(m)$ are known for classical randomized algorithms in adjacency matrix and adjacency array models, respectively.
- Upper bounds of $\tilde O(n^{3/2})$ and $\tilde O(\sqrt{mn})$ are presented for quantum query complexity in adjacency matrix and adjacency array models, respectively.
- Quantum sparsification algorithm is used to obtain these upper bounds by combining a lemma on near-minimum cuts.
- For weighted graphs, no quantum speedup is possible for computing minimum cut weights in both models as $\Omega(n^2)$ queries can be needed in worst-case scenarios.
- Five open problems related to their work are presented, including finding tight lower bounds on computing minimum cut weights and similar time complexity bounds for computing edge connectivity.

## Summary

This paper studies 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. The edge connectivity of a simple graph is defined as the least number of edges whose removal disconnects the graph. For classical randomized algorithms, lower bounds of $\Omega(n^2)$ and $\Omega(m)$ are known for these models, respectively, showing that the trivial algorithm is optimal in terms of query complexity for both cases. However, this paper presents 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. These upper bounds follow by combining a lemma on the structure of near-minimum cuts with a quantum sparsification algorithm. The authors also consider weighted graphs where 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, they show that in both adjacency matrix and adjacency array models no quantum speedup is possible as $\Omega(n^2)$ queries can be needed to compute the weight of a minimum cut by a quantum algorithm in worst-case scenarios. The paper concludes with five open problems related to their work. One such problem asks if it's possible to give an algorithm that shows that their lower bound on computing minimum cut weights in adjacency matrix model is tight throughout all ranges 1 ≤ α < n when we have an upper bound α on maximum weight. Another open problem seeks similar time complexity bounds as their query complexity results for computing edge connectivity. Finally, they note that there remains a gap between their upper bound on query complexity for adjacency array model and existing lower bounds from previous works for simple graphs.