Let U be a universe on n elements, let k be a positive integer, and let F be a family of (implicitly defined) subsets of U. We consider the problems of partitioning U into k sets from F, covering U with k sets from F, and packing k non-intersecting sets from F into U. Classically, these problems can be solved via inclusion-exclusion in O*(2^n) time [BjorklundHK09]. Quantumly, there are faster algorithms for graph coloring with running time O(1.9140^n) [ShimizuM22] and for Set Cover with a small number of sets with running time O(1.7274^n |F|^O(1)) [AmbainisBIKPV19]. In this paper, we give a quantum speedup for Set Partition, Set Cover, and Set Packing whenever there is a classical enumeration algorithm that lends itself to a quadratic quantum speedup, which, for any subinstance on a subset X of U, enumerates at least one member of a k-partition, k-cover, or k-packing (if one exists) restricted to (or projected onto, in the case of k-cover) the set X in O*(c^{|X|}) time with c<2. Our bounded-error quantum algorithm runs in O*((2+c)^(n/2)) for Set Partition, Set Cover, and Set Packing. When c<=1.147899, our algorithm is slightly faster than O*((2+c)^(n/2)); when c approaches 1, it matches the running time of [AmbainisBIKPV19] for Set Cover when |F| is subexponential in n. For Graph Coloring, we further improve the running time to O(1.7956^n) by leveraging faster algorithms for coloring with a small number of colors to better balance our divide-and-conquer steps. For Domatic Number, we obtain a O((2-ε)^n) running time for some ε>0.
Let U be a universe on n elements, let k be a positive integer, and let F be a family of (implicitly defined) subsets of U. We consider the problems of partitioning U into k sets from F, covering U with k sets from F, and packing k non-intersecting sets from F into U. Classically, these problems can be solved via inclusion-exclusion in O*(2^n) time [BjorklundHK09]. Quantumly, there are faster algorithms for graph coloring with running time O(1.9140^n) [ShimizuM22] and for Set Cover with a small number of sets with running time O(1.7274^n |F|^O(1)) [AmbainisBIKPV19]. In this paper, we give a quantum speedup for Set Partition, Set Cover, and Set Packing whenever there is a classical enumeration algorithm that lends itself to a quadratic quantum speedup, which, for any subinstance on a subset X of U, enumerates at least one member of a k-partition, k-cover, or k-packing (if one exists) restricted to (or projected onto, in the case of k-cover) the set X in O*(c^{|X|}) time with c<2. Our bounded-error quantum algorithm runs in O*((2+c)^(n/2)) for Set Partition, Set Cover, and Set Packing. When c<=1.147899, our algorithm is slightly faster than O*((2+c)^(n/2)); when c approaches 1, it matches the running time of [AmbainisBIKPV19] for Set Cover when |F| is subexponential in n. For Graph Coloring, we further improve the running time to O(1.7956^n) by leveraging faster algorithms for coloring with a small number of colors to better balance our divide-and-conquer steps. For Domatic Number, we obtain a O((2-ε)^n) running time for some ε>0.
Let U be a universe on n elements, let k be a positive integer, and let ℱ be a family of (implicitly defined) subsets of U. We consider the problems of partitioning U into k sets from ℱ, covering U with k sets from ℱ, and packing k non-intersecting sets from ℱ into U. Classically, these problems can be solved via inclusion-exclusion in 2ⁿ n^O(1) time [Andreas Björklund et al., 2009]. Quantumly, there are faster algorithms for graph coloring with running time O(1.9140ⁿ) [Kazuya Shimizu and Ryuhei Mori, 2022] and for Set Cover with a small number of sets with running time O(1.7274ⁿ |ℱ|^O(1)) [Andris Ambainis et al., 2019]. In this paper, we give a quantum speedup for Set Partition, Set Cover, and Set Packing whenever there is a classical enumeration algorithm that lends itself to a quadratic quantum speedup, which, for any subinstance on a set X ⊆ U, enumerates at least one member of a k-partition, k-cover, or k-packing (if one exists) restricted to (or projected onto, in the case of k-cover) the set X in c^|X| n^O(1) time with c < 2. Our bounded-error quantum algorithm runs in time (2+c)^{n/2} n^O(1) for Set Partition, Set Cover, and Set Packing. It is obtained by combining three algorithms that have the best running time for some values of c. When c ≤ 1.147899, our algorithm is slightly faster than (2+c)^{n/2} n^O(1); when c approaches 1, it matches the O(1.7274ⁿ |ℱ|^O(1)) running time of [Andris Ambainis et al., 2019] for Set Cover when |ℱ| is subexponential in n. For covering, packing, and partitioning into maximal independent sets, maximal cliques, maximal bicliques, maximal cluster graphs, maximal triangle-free graphs, maximal cographs, maximal claw-free graphs, maximal trivially-perfect graphs, maximal threshold graphs, maximal split graphs, maximal line graphs, and maximal induced forests, we obtain bounded-error quantum algorithms with running times ranging from O(1.8554ⁿ) to O(1.9629ⁿ). Packing and covering by maximal induced matchings can be done quantumly in O(1.8934ⁿ) time. For Graph Coloring (covering with k maximal independent sets), we further improve the running time to O(1.7956ⁿ) by leveraging faster algorithms for coloring with a small number of colors to better balance our divide-and-conquer steps. For Domatic Number (packing k minimal dominating sets), we obtain a O((2-ε)ⁿ) running time for some ε > 0. Several of our results should be of interest to proponents of classical computing: - We present an inclusion-exclusion algorithm with running time O^*(∑_{i=0}^⌊αn⌋ binom(n,i)), which determines, for each X ⊆ U of size at most α n, 0 ≤ α ≤ 1, whether (X,ℱ) has a k-cover, k-partition, or k-packing. This running time is best-possible, up to polynomial factors. - We prove that for any linear-sized vertex subset X ⊆ V of a graph G = (V,E), the number of minimal dominating sets of G that are subsets of X is O((2-ε)^|X|) for some ε > 0.
Abstract The fastest known classical algorithm deciding the k-colorability of n-vertex graph requires running time Ω(2n) Ω ( 2 n ) for k≥5 k ≥ 5 . In this work, we present an exponential-space quantum algorithm computing the chromatic number with running time O(1.9140n) O ( 1 . 9140 n ) using quantum random access memory (QRAM). Our approach is based on Ambainis et al’s quantum dynamic programming with applications of Grover’s search to branching algorithms. We also present a polynomial-space quantum algorithm not using QRAM for the graph 20-coloring problem with running time O(1.9575n) O ( 1 . 9575 n ) . For the polynomial-space quantum algorithm, we essentially develop (4−ϵ)n ( 4 - ϵ ) n -time classical algorithms that can be improved quadratically by Grover’s search.
Abstract Graph coloring with minimum colors is a well-known NP-complete problem in computer science and mathematics, having diverse real-life applications such as scheduling, register allocation, and frequency assignment. However, a classical computer requires exponential time to solve the graph coloring problem with the minimum number of colors. Therefore, classical approaches become infeasible for solving this problem on large graphs. In contrast, quantum computing offers the potential for speedup on specific problems, although solutions are typically obtained with a certain probability of correctness. This work proposes a quantum–classical method for solving the graph coloring problem and finding the chromatic number of a graph with guaranteed correctness, and also reduces the time and qubit complexities. The proposed method is inspired by Randomized Grover’s search algorithm, and the classical binary search algorithm. Here, Randomized Grover’s search algorithm provides quadratic speedup and this algorithm is useful in real situations when the number of solutions is not known in advance in contrast to the Grover’s search algorithm. The binary search algorithm helps to achieve logarithmic speedup, which reduces overall complexity. The experimental results strongly validate our claims and demonstrate the superiority of the approach. Furthermore, a comprehensive mathematical analysis is carried out to examine its complexities, as well as to compare its computational efficiency with existing methods.
Motivated by the quantum speedup for dynamic programming on the Boolean hypercube by Ambainis et al. (2019), we investigate which graphs admit a similar quantum advantage. In this paper, we examine a generalization of the Boolean hypercube graph, the n-dimensional lattice graph Q(D,n) with vertices in {0,1,…,D}n. We study the complexity of the following problem: given a subgraph G of Q(D,n) via query access to the edges, determine whether there is a path from 0n to Dn. While the classical query complexity is Θ((D+1)n), we show a quantum algorithm with complexity O(TDn), where TD<D+1. The first few values of TD are T1≈1.817, T2≈2.660, T3≈3.529, T4≈4.421, T5≈5.332. We also prove that TD≥eD+1, thus for general D, this algorithm does not provide, for example, a speedup, polynomial in the size of the lattice. While the presented quantum algorithm is a natural generalization of the known quantum algorithm for D=1 by Ambainis et al., the analysis of complexity is rather complicated. For the precise analysis, we use the saddle-point method, which is a common tool in analytic combinatorics, but has not been widely used in this field. We then show an implementation of this algorithm with time complexity poly(n)lognTDn, and apply it to the Set Multicover problem. In this problem, m subsets of [n] are given, and the task is to find the smallest number of these subsets that cover each element of [n] at least D times. While the time complexity of the best known classical algorithm is O(m(D+1)n), the time complexity of our quantum algorithm is poly(m,n)lognTDn.
Abstract The traveling salesman problem is the problem of finding out the shortest route in a network of cities, that a salesman needs to travel to cover all the cities, without visiting the same city more than once. This problem is known to be N P -hard with a brute-force complexity of O ( N N ) or O ( N 2 N ) for N number of cities. This problem is equivalent to finding out the shortest Hamiltonian cycle in a given graph, if at least one Hamiltonian cycle exists in it. Quantum algorithms for this problem typically provide with a quadratic speedup only, using Grover’s search, thereby having a complexity of O ( N N /2 ) or O ( N N ). We present a bounded-error quantum polynomial-time (BQP) algorithm for solving the problem, providing with an exponential speedup. The overall complexity of our algorithm is O ( N 3 log( N ) κ / ϵ + 1/ ϵ 3 ), where the errors ϵ are O (1/poly( N )), and κ is the not-too-large condition number of the matrix encoding all Hamiltonian cycles.
The Subset Sum problem asks whether, given n integers and a target, some subset of the integers sums to the target. Its best known worst-case running time is O∗(2n/2) (Horowitz and Sahni, 1974), whereas the best quantum upper bound is O∗(2n/3) (Bernstein, Jeffery, Lange, and Meurer, 2013). The k-SUM problem is a parameterized version of Subset Sum asking whether there are k integers that sum to the target. The best classical upper bound for it is O(n⌈k/2⌉), whereas the best quantum running time is O(nk/3) (Tani, 2009). For random instances, a quantum algorithm with running time O(nΦk) is known, where Φk=62k−⌊k/7⌋−⌊(k+3)/7⌋ (Schrottenloher, 2021). We present a new quantum algorithm solving worst-case k-SUM in time O(nΨk), where Ψk=Φk−9[k≡3mod7]−18[k≡6mod7]. The algorithm is not only faster for all k congruent to 3 or 6 modulo 7, but also gives a worst-case guarantee rather than a guarantee restricted to single-solution random instances. Combining our algorithm for 7-SUM with the standard block reduction technique yields an O∗(22n/7) quantum algorithm for Subset Sum, improving the previously known O∗(2n/3) algorithm.