The problems of computing eccentricity, radius, and diameter are fundamental to graph theory. These parameters are intrinsically defined based on the distance metric of the graph. In this work, we propose quantum algorithms for the diameter and radius of undirected, weighted graphs in the adjacency list model. The algorithms output diameter and radius with the corresponding paths in $\widetilde{O}(n\sqrt{m})$ time. Additionally, for the diameter, we present a quantum algorithm that approximates the diameter within a $2/3$ ratio in $\widetilde{O}(\sqrt{m}n^{3/4})$ time. We also establish quantum query lower bounds of $Ω(\sqrt{nm})$ for all the aforementioned problems through a reduction from the minima finding problem.
The problems of computing eccentricity, radius, and diameter are fundamental to graph theory. These parameters are intrinsically defined based on the distance metric of the graph. In this work, we propose quantum algorithms for the diameter and radius of undirected, weighted graphs in the adjacency list model. The algorithms output diameter and radius with the corresponding paths in O(nm) time. Additionally, for the diameter, we present a quantum algorithm that approximates the diameter within a 2/3 ratio in O(mn3/4) time. We also establish quantum query lower bounds of Ω(nm) for all the aforementioned problems through a reduction from the minima finding problem.
Given an undirected, weighted graph, with n vertices and m edges, and two special vertices s and t, the problem is to find the shortest path between them. We give two bounded-error quantum algorithms with improved runtime in the adjacency list model that solve the problem on special classes of graphs defined via pathfinding probabilities of classical random walks and the electrical network framework. Firstly, we give a simple quantum algorithm based on sampling edges from a graph via the quantum flow state and running a classical algorithm on the sampled edges. It runs in O~(l2m) expected time and uses O(logn) space on graphs where the shortest s-t path is also a minimum resistance s-t subgraph. Our main algorithm can be thought of as a divide and conquer version of this approach and works on a special class of graphs where classical loop-erased random walk has a probability q>0.537 of finding the shortest s-t path. In such cases the quantum algorithm outputs the shortest s-t path with high probability in O(ℓm) expected time and O(logn) space, where l is the length (or total weight, in case of weighted graphs) of the shortest s-t path. This algorithm can be parallelised to O~(lm) circuit depth when using O(llogn) space. With the latter we partially resolve with an affirmative answer the open problem of whether a path between two vertices can be found in the number of steps required to detect it.
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).
Computing the distance parameters of a network, including the diameter, radius, eccentricities and the all-pairs shortest paths (APSP) is a central problem in distributed computing. This paper investigates the distance parameters in the quantum CONGEST models and establishes almost linear lower bounds on eccentricities and APSP, which match the classical upper bounds. Our results imply that there is not quantum speedup for these two problems. In contrast with the diameter and radius, exchanging quantum messages is able to save the communication when the networks have low diameters [F. L. Gall and F. Magniez, Sublinear-time quantum computation of the diameter in CONGEST networks, in Proc. 2018 ACM Symp. Principles of Distributed Computing (PODC), (2018), pp. 337–346; F. Magniez and A. Nayak, arXiv:2002.11795 ]. We obtain the lower bounds via a reduction from the two-way quantum communication complexity of the set intersection [A. A. Razborov, Izv. Math. 159 (2003)].
The quantum query complexity of subgraph-containment problems, which ask whether a given subgraph H is present in an input graph G, has been the subject of considerable study. However, even for relatively simple subgraphs, such as paths and cycles, a complete understanding of their query complexities remains elusive. In this work, we consider several variants of path- and cycle-containment problems in the adjacency matrix model, where we search for paths or cycles of constant length k. We compare the settings where the graphs are directed or undirected, where the goal is to detect or find the existence of a path/cycle, and where the path/cycle we are looking for has length exactly k, or at most k. We also consider several promise versions of these problems, where we suppose that the input graph has a certain structure. We characterize the relative difficulty of these variants of the path/cycle-containment problems, by relating them to one another using randomized reductions, and grouping them into equivalence classes.
When we restrict our attention to path-containment problems, we get a dichotomy result. Some of the path-containment problems can be solved using a linear number of queries, and all the others are equivalent to one another (and additionally to several cycle-containment problems) under randomized reductions, up to constant overhead. For the latter equivalence class, we prove a novel quantum-walk-based algorithm that achieves query complexity O(n3/2−αk), where αk∈Θ(c−k) and c=3+17/2≈1.33, beating the previous best upper bound O(n3/2) on its query complexity. We also provide a conditional lower bound based on the graph-collision problem, which implies that this equivalence class does not admit linear-query quantum algorithms unless graph collision admits an O(n) query algorithm.
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.