2019/07/01 by K. Shimizu, Ryuhei Mori, Shimizu, Kazuya +1 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1907.00529
openalex publication_date 2019/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The fastest known classical algorithm deciding the k-colorability of n-vertex graph requires running time Ω(2n) for k≥ 5. In this work, we present an exponential-space quantum algorithm computing the chromatic number with running time O(1.9140n) 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). In the polynomial-space quantum algorithm, we essentially show (4-ε)n-time classical algorithms that can be improved quadratically by Grover's search.