2026-07-26T19:18:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14302 2024-03-06T10:53:55Z ddc:004 open_access

Quantum Complexity of Minimum Cut Apers, Simon Lee, Troy Quantum algorithms quantum query complexity minimum cut 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Simon Apers and Troy Lee 2021 Is Part Of LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2021.28 urn:nbn:de:0030-drops-143026 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.28 eng https://creativecommons.org/licenses/by/4.0/legalcode