Exponential-Time Quantum Algorithms for Graph Coloring Problems

Kazuya Shimizu, Ryuhei Mori

刘冬梅 Liu Dongmei, Jian Li, XIUBO CHEN +3 more

Shimizu, Kazuya, Ryuhei Mori

The fastest known classical algorithm deciding the $k$-colorability of $n$-vertex graph requires running time $Ω(2^n)$ for $k\ge 5$. In this work, we present an exponential-space quantum algorithm computing the chromatic number with running time $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.9575^n)$. In the polynomial-space quantum algorithm, we essentially show $(4-ε)^n$-time classical algorithms that can be improved quadratically by Grover's search.

Kazuya Shimizu, Ryuhei Mori

Abstract The fastest known classical algorithm deciding the k-colorability of n-vertex graph requires running time $$\varOmega (2^n)$$ Ω ( 2 n ) for $$k\ge 5$$ k ≥ 5 . In this work, we present an exponential-space quantum algorithm computing the chromatic number with running time $$O(1.9140^n)$$ 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.9575^n)$$ O ( 1 . 9575 n ) . For the polynomial-space quantum algorithm, we essentially develop $$(4-\epsilon )^n$$ ( 4 - ϵ ) n -time classical algorithms that can be improved quadratically by Grover’s search.

Olawale Titiloye, Alan J. Crispin

Angelo Oddi, Riccardo Rasconi, Marco Baioletti +2 more