Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userQuantum Speedup for the Minimum Steiner Tree Problem
76
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A recent breakthrough by Ambainis, Balodis, Iraids, Kokainis, Pr=usis and Vihrovs (SODA19) showed how to construct faster quantum algorithms for the Traveling Salesman Problem and a few other NP-hard problems by combining in a novel way quantum search with classical dynamic programming. In this paper, we show how to apply this approach to the minimum Steiner tree problem, a well-known NP-hard problem, and construct the first quantum algorithm that solves this problem faster than the best known classical algorithms. More precisely, the complexity of our quantum algorithm is $mathcal{O}(1.812^kpoly(n))$, where $n$ denotes the number of vertices in the graph and $k$ denotes the number of terminals. In comparison, the best known classical algorithm has complexity $mathcal{O}(2^kpoly(n))$.
rate research
Read More
Given two sets of points in the plane, $P$ of $n$ terminals and $S$ of $m$ Steiner points, a Steiner tree of $P$ is a tree spanning all points of $P$ and some (or none or all) points of $S$. A Steiner tree with length of longest edge minimized is called a bottleneck Steiner tree. In this paper, we study the Euclidean bottleneck Steiner tree problem: given two sets, $P$ and $S$, and a positive integer $k le m$, find a bottleneck Steiner tree of $P$ with at most $k$ Steiner points. The problem has application in the design of wireless communication networks. We first show that the problem is NP-hard and cannot be approximated within factor $sqrt{2}$, unless $P=NP$. Then, we present a polynomial-time approximation algorithm with performance ratio 2.
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 $tau$, we give a quantum algorithm to solve the minimum cut problem using $tilde O(n^{3/2}sqrt{tau})$ queries and time. Moreover, for every integer $1 le tau le n$ we give an example of a graph $G$ with edge weights $1$ and $tau$ such that solving the minimum cut problem on $G$ requires $Omega(n^{3/2}sqrt{tau})$ many queries to the adjacency matrix of $G$. These results contrast with the classical randomized case where $Omega(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 Theta(m)$. We show that the quantum query and time complexity are $tilde O(sqrt{mntau})$ and $tilde O(sqrt{mntau} + n^{3/2})$, respectively, where again the edge weights are between $1$ and $tau$. For dense graphs we give lower bounds on the quantum query complexity of $Omega(n^{3/2})$ for $tau > 1$ and $Omega(tau n)$ for any $1 leq tau 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 Kargers tree packing technique (STOC 1996).
We study the multi-level Steiner tree problem: a generalization of the Steiner tree problem in graphs where terminals $T$ require varying priority, level, or quality of service. In this problem, we seek to find a minimum cost tree containing edges of varying rates such that any two terminals $u$, $v$ with priorities $P(u)$, $P(v)$ are connected using edges of rate $min{P(u),P(v)}$ or better. The case where edge costs are proportional to their rate is approximable to within a constant factor of the optimal solution. For the more general case of non-proportional costs, this problem is hard to approximate with ratio $c log log n$, where $n$ is the number of vertices in the graph. A simple greedy algorithm by Charikar et al., however, provides a $min{2(ln |T|+1), ell rho}$-approximation in this setting, where $rho$ is an approximation ratio for a heuristic solver for the Steiner tree problem and $ell$ is the number of priorities or levels (Byrka et al. give a Steiner tree algorithm with $rhoapprox 1.39$, for example). In this paper, we describe a natural generalization to the multi-level case of the classical (single-level) Steiner tree approximation algorithm based on Kruskals minimum spanning tree algorithm. We prove that this algorithm achieves an approximation ratio at least as good as Charikar et al., and experimentally performs better with respect to the optimum solution. We develop an integer linear programming formulation to compute an exact solution for the multi-level Steiner tree problem with non-proportional edge costs and use it to evaluate the performance of our algorithm on both random graphs and multi-level instances derived from SteinLib.
In this work, we initiate the study of the Minimum Circuit Size Problem (MCSP) in the quantum setting. MCSP is a problem to compute the circuit complexity of Boolean functions. It is a fascinating problem in complexity theory -- its hardness is mysterious, and a better understanding of its hardness can have surprising implications to many fields in computer science. We first define and investigate the basic complexity-theoretic properties of minimum quantum circuit size problems for three natural objects: Boolean functions, unitaries, and quantum states. We show that these problems are not trivially in NP but in QCMA (or have QCMA protocols). Next, we explore the relations between the three quantum MCSPs and their variants. We discover that some reductions that are not known for classical MCSP exist for quantum MCSPs for unitaries and states, e.g., search-to-decision reduction and self-reduction. Finally, we systematically generalize results known for classical MCSP to the quantum setting (including quantum cryptography, quantum learning theory, quantum circuit lower bounds, and quantum fine-grained complexity) and also find new connections to tomography and quantum gravity. Due to the fundamental differences between classical and quantum circuits, most of our results require extra care and reveal properties and phenomena unique to the quantum setting. Our findings could be of interest for future studies, and we post several open problems for further exploration along this direction.
Given a graph $G = (V,E)$ and a subset $T subseteq V$ of terminals, a emph{Steiner tree} of $G$ is a tree that spans $T$. In the vertex-weighted Steiner tree (VST) problem, each vertex is assigned a non-negative weight, and the goal is to compute a minimum weight Steiner tree of $G$. We study a natural generalization of the VST problem motivated by multi-level graph construction, the emph{vertex-weighted grade-of-service Steiner tree problem} (V-GSST), which can be stated as follows: given a graph $G$ and terminals $T$, where each terminal $v in T$ requires a facility of a minimum grade of service $R(v)in {1,2,ldotsell}$, compute a Steiner tree $G$ by installing facilities on a subset of vertices, such that any two vertices requiring a certain grade of service are connected by a path in $G$ with the minimum grade of service or better. Facilities of higher grade are more costly than facilities of lower grade. Multi-level variants such as this one can be useful in network design problems where vertices may require facilities of varying priority. While similar problems have been studied in the edge-weighted case, they have not been studied as well in the more general vertex-weighted case. We first describe a simple heuristic for the V-GSST problem whose approximation ratio depends on $ell$, the number of grades of service. We then generalize the greedy algorithm of [Klein & Ravi, 1995] to show that the V-GSST problem admits a $(2 ln |T|)$-approximation, where $T$ is the set of terminals requiring some facility. This result is surprising, as it shows that the (seemingly harder) multi-grade problem can be approximated as well as the VST problem, and that the approximation ratio does not depend on the number of grades of service.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
