Quantum Algorithms for Graph Coloring and other Partitioning, Covering, and Packing Problems
Serge Gaspers, Jerry Zirui Li · arXiv (Cornell University) · 2023
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 c0.