Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Exponential-Time Quantum Algorithms for Graph Coloring Problems

Kazuya Shimizu, Ryuhei Mori

Published Jan 1, 2020• 10 citations
Publisher
DOI
10.1007/978-3-030-61792-9_31

Related papers

Hierarchical quantum approximation optimization algorithm for solving graph-coloring problems

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

Physical Review A•Jan 26, 2026•3 citations

Quantum annealing of the graph coloring problem

Olawale Titiloye, Alan J. Crispin

Discrete Optimization•Jan 8, 2011•114 citations

Quantum Circuit Compilation for the Graph Coloring Problem

Angelo Oddi, Riccardo Rasconi, Marco Baioletti +2 more

Lecture notes in computer science•Jan 1, 2023•3 citations

Graph Coloring with a Distributed Hybrid Quantum Annealing Algorithm

Olawale Titiloye, Alan J. Crispin

Lecture notes in computer science•Jan 1, 2011•28 citations

Exponential-Time Quantum Algorithms for Graph Coloring Problems

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.

arXiv:1907.00529•Algorithmica•Jun 1, 2022•28 citations

A quantum–classical approach to solve the graph coloring problem with minimum colors

Prem Shanker Dwivedi, Abhinav Kumar, Amit Biswas +1 more

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.

Physica Scripta•Oct 9, 2026•0 citations
Abstract The fastest known classical algorithm deciding the k-colorability of n-vertex graph requires running time Ω(2n)\varOmega (2^n)Ω(2n) Ω ( 2 n ) for k≥5k\ge 5k≥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)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)O(1.9575n) O ( 1 . 9575 n ) . For the polynomial-space quantum algorithm, we essentially develop (4−ϵ)n(4-\epsilon )^n(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.