Classical and Quantum Distributed Algorithms for the Survivable Network Design Problem

We develop distributed classical and quantum approaches for the survivable network design problem (SNDP), also sometimes called the generalized Steiner problem. This generalizes many difficult graph problems of interest, such as the traveling salesman problem, the Steiner tree problem, and the k-connected network problem, among others. In the distributed settings that we consider, no classical or quantum algorithms had been formulated to the best of our knowledge. We describe algorithms that are heuristics for the general problem but give concrete approximation bounds under certain parameterizations of the SNDP, which in particular hold for the three aforementioned problems that SNDP generalizes. We use a classical algorithmic framework first studied by (Goemans & Bertsimas, 1993, Mathematical Programming, 60, 145–166) and provide a distributed implementation thereof. Notably, we obtain asymptotic quantum speedups by leveraging quantum shortest path computations in this framework, generalizing recent work of (Kerger, Bernal Neira, Izquierdo, & Rieffel, 2023,

Algorithms, 16, 332), which raises the question of whether there is a separation between the classical and quantum models for the problems considered.