The fastest known classical algorithm deciding the @math -colorability of @math -vertex graph requires running time @math for @math . In this work, we present an exponential-space quantum algorithm computing the chromatic number with running time @math using quantum random access memory (QRAM). Our approach is based on '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 @math -coloring problem with running time @math . In the polynomial-space quantum algorithm, we essentially show @math -time classical algorithms that can be improved quadratically by Grover's search.
There is almost no previous theoretical work on quantum algorithms for the graph coloring problems. F "urer mentioned that Grover's algorithm can be applied to branching algorithms so that Beigel and Eppstein's algorithm for the graph 3-coloring problem can be improved to running time @math @cite_2 . The quantum algorithms for Theorem are basically obtained by applying Grover's search to generalized Byskov's reduction algorithms on the basis of F "urer's observation.
@cite_2
1727475799
In his seminal paper, Grover points out the prospect of faster solutions for an NP-complete problem like SAT. If there are n variables, then an obvious classical deterministic algorithm checks out all 2n truth assignments in about 2n steps, while his quantum search algorithm can find a satisfying truth assignment in about 2n 2 steps. For several NP-complete problems, many sophisticated classical algorithms have been designed. They are still exponential, but much faster than the brute force algorithms. The question arises whether their running time can still be decreased from T(n) to O (√T(n)) by using a quantum computer. Isolated positive examples are known, and some speed-up has been obtained for wider classes. Here, we present a simple method to obtain the full T(n) to O(√T(n)) speed-up for most of the many nontrivial exponential time algorithms for NP-hard problems. The method works whenever the widely used technique of recursive decomposition is employed. This included all currently known algorithms for which such a speedup has not yet been known.