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.
Abstract The fastest known classical algorithm deciding the k-colorability of n-vertex graph requires running time Ω(2n) Ω ( 2 n ) for k≥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 ) 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 ) . For the polynomial-space quantum algorithm, we essentially develop (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.
In this paper, we study quantum algorithms for computing the exact value of the treewidth of a graph. Our algorithms are based on the classical algorithm by Fomin and Villanger (Combinatorica 32, 2012) that uses O(2.616ⁿ) time and polynomial space. We show three quantum algorithms with the following complexity, using QRAM in both exponential space algorithms: - O(1.618ⁿ) time and polynomial space; - O(1.554ⁿ) time and O(1.452ⁿ) space; - O(1.538ⁿ) time and space. In contrast, the fastest known classical algorithm for treewidth uses O(1.755ⁿ) time and space. The first two speed-ups are obtained in a fairly straightforward way. The first version uses additionally only Grover’s search and provides a quadratic speedup. The second speedup is more time-efficient and uses both Grover’s search and the quantum exponential dynamic programming by Ambainis et al. (SODA '19). The third version uses the specific properties of the classical algorithm and treewidth, with a modified version of the quantum dynamic programming on the hypercube. As a small side result, we give a new classical time-space tradeoff for computing treewidth in O^*(2ⁿ) time and O^*(√{2ⁿ}) space.
We investigate the quantum algorithms for dynamic programming by Ambainis et al. (SODA'19). While giving provable complexity speedups and applicable to a variety of NP-hard problems, these algorithms have a notable drawback: they require a large amount of Quantum Random Access Memory (QRAM), which potentially could be very challenging to implement in a physical quantum computer. In this work, we study how we can improve the space complexity by trading it for time, while still retaining a speedup over the classical algorithms. We show novel quantum time-space tradeoffs by combining different classical approaches with quantum techniques. For instance, we show that the Travelling Salesman Problem can be solved quantumly in O(1.859n) time and O(1.315n) QRAM space.
Graph coloring is a computationally difficult problem, and currently the best known classical algorithm fork-coloring of graphs onnvertices has runtimesΩ(2n)fork≥5. The list coloring problem asks the following more general question: given alistof available colors for each vertex in a graph, does it admit a proper coloring? We propose a hybrid classical-quantum algorithm based on Grover search 12 to quadratically speed up exhaustive search. Our algorithm loses in complexity to classical ones in specific restricted cases, but improves exhaustive search for cases, where the lists and graphs considered are arbitrary in nature.
We give quantum algorithms for exponential-time problems on n vertices or elements, with bounded error, polynomial space and no quantum random access memory. Our results are these. (1) 4-Colouring in quantum time O(1.3032n), from a polynomial-space branching algorithm with polynomial-space terminal algorithms; with the branching algorithm alone, O(1.3100n). The previous best bound in this model, to our knowledge, is O(1.3231n). (2) k-Colouring below the previous best bound for k∈{5,7,8,9,10,11} and 13≤k≤18, from O(1.4518n) for k=5 to O(1.9233n) for k=18. (3) Dominating Set in O(1.2235n), against the previous O(2n/2), Independent Dominating Set in O(1.1583n), and Edge Dominating Set and Minimum Maximal Matching in O(1.1501n). (4) A quantum form of monotone local search: if the extension problem has a backtracking tree with ck nodes up to polynomial factors, the problem is solved in quantum time (2−1/c)n/2 up to polynomial factors. This gives Feedback Vertex Set in O(1.3081n), Subset and Group Feedback Vertex Set in O(1.3229n), Cluster Vertex Deletion in O(1.2033n), 3-Hitting Set in O(1.2405n), Proper Interval Vertex Deletion in O(1.3541n), Multicut on Trees in O(1.1647n) and Min-Ones d-SAT in O∗((2−1/d)n/2). (5) Quantum exponential-time approximations below the quantum exact bounds, such as a 1.1-approximation for Vertex Cover in O(1.0555n) and for Feedback Vertex Set in O(1.2161n). The colouring exponents for k≥6 come from an evaluation of a known reduction recursion, computed in floating point with a margin.
This thesis presents a novel quantum algorithm that solves the Chromatic Number problem. Complexity analysis of this algorithm revealed a run time of O(2n/2n2(log2n)2). This is an improvement over the best known algorithm, with a run time of 2nnO(1) [1]. This algorithm uses the Quantum Search algorithm (often called Grover's Algorithm), and the Quantum Counting algorithm. Chromatic Number is an example of an NP-Hard problem, which suggests that other NP-Hard problems can also benefit from a speed-up provided by quantum technology. This has wide implications as many real world problems can be framed as NP-Hard problems, so any speed-up in the solution of these problems is highly sought after. A bulk of this thesis consists of a review of the underlying principles of quantum mechanics and quantum computing, building to the Quantum Search and Quantum Counting algorithms. The review is written with the assumption that the reader has no prior knowledge on quantum computing. This culminates with a presentation of algorithms for generating the quantum circuits required to solve K-Coloring and Chromatic Number.