Nowadays in Quantum Computing, the implementation of quantum algorithm has created a stir since Noisy Intermediate-Scale Quantum (NISQ) devices are out in the market. Researchers are mostly interested in solving NP-complete problems with the help of quantum algorithms for its speedup. As per the work on computational complexity by Karp [1], if any of the NP-complete problem can be solved then any other NP-complete problem can be reduced to that problem in polynomial time. In this Paper, K-coloring problem (NP-complete problem) has been considered to solve using Grover's search. A comparator-based approach has been used to implement K-coloring problem which enables the reduction of the qubit cost compared to the state-of-the-art. An end-to-end automated framework has been proposed to implement the K-coloring problem for any unweighted and undirected graph on any available Noisy Intermediate-Scale Quantum (NISQ) devices, which helps in generalizing our approach.
Nowadays in Quantum Computing, the implementation of quantum algorithm has created a stir since Noisy Intermediate-Scale Quantum (NISQ) devices are out in the market. Researchers are mostly interested in solving NP-complete problems with the help of quantum algorithms for its speedup. As per the work on computational complexity by Karp [1], if any of the NP-complete problem can be solved then any other NP-complete problem can be reduced to that problem in polynomial time. In this Paper, K-coloring problem (NP-complete problem) has been considered to solve using Grover's search. A comparator-based approach has been used to implement K-coloring problem which enables the reduction of the qubit cost compared to the state-of-the-art. An end-to-end automated framework has been proposed to implement the K-coloring problem for any unweighted and undirected graph on any available Noisy Intermediate-Scale Quantum (NISQ) devices, which helps in generalizing our approach.
Graph coloring is a well-known NP-complete problem with applications in scheduling, register allocation, frequency assignment, and network optimization. Quantum computing offers the potential for polynomial or even super-polynomial speedups in certain problem instances, yet practical quantum graph coloring methods must carefully balance qubit resources, circuit depth, and constraint enforcement. We proposed a solver agnostic quantum framework for K-coloring. Along with a novel encoding and efficient constraint implementation for its exact coloring exploiting Grover search and almost optimal coloring by the Quantum Approximate Optimization Algorithm \emph{(QAOA)}, and \emph{Quantum Annealing}. Unlike using O(NK) qubits as in \emph{SOTA}, we reduced the qubit requirements to O(Nlog2K), along with optimized comparator circuits enforcing adjacency constraints. Further symmetry-based graph reduction is incorporated as an optional preprocessing step to further reduce the instance size before quantum execution.
In the near future of the noisy intermediate-scale quantum (NISQ) era, almost all quantum computing devices will be restricted to a specific fixed qubits connectivity architecture. Thus, the synthesis of quantum circuits with limited connectivity is urgent. We design quantum circuit synthesis algorithms for basic and essential synthesis problems, such as quantum state preparation, general unitary synthesis, and quantum isometries. For any architecture, the controlled not (cnot) count is at most 5/3 times the state-of-the-art result on complete-graph architecture. For some specific architectures, such as square-grid ones, the ratio is reduced to 1.126. The numerical simulation result is confirmatory of theoretical conclusions. Our algorithms significantly reduce by more than 50 additional cnot count compared to mapping algorithms. These algorithms help to implement the larger-scale algorithm in the physics device. Our results illustrate that well-designed synthesis algorithms can mitigate the problem of limited qubit connectivity in the NISQ era and may suggest the design of large-scale quantum devices.
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.
Using quantum algorithms to solve various problems has attracted widespread attention with the development of quantum computing. Researchers are particularly interested in using the acceleration properties of quantum algorithms to solve NP-complete problems. This paper focuses on the well-known NP-complete problem of finding the minimum dominating set in undirected graphs. To expedite the search process, a quantum algorithm employing Grover’s search is proposed. However, a challenge arises from the unknown number of solutions for the minimum dominating set, rendering direct usage of original Grover’s search impossible. Thus, a swap test method is introduced to ascertain the number of iterations required. The oracle, diffusion operators, and swap test are designed with achievable quantum gates. The query complexity is O(1.414 n ) and the space complexity is O(n). To validate the proposed approach, qiskit software package is employed to simulate the quantum circuit, yielding the anticipated results.
Abstract Finding cliques in a graph has a wide range of applications due to its pattern matching ability. The k ‐clique problem, a subset of the clique problem, determines whether or not an arbitrary network has a clique of size k . Modern‐day applications include a variation of the k ‐clique problem that lists all cliques of size k . However, the quantum implementation of such a variation of the k ‐clique problem has not been addressed yet. In this work, apart from the theoretical solution of such a k ‐clique problem, practical quantum‐gate‐based implementation has been addressed using Grover's algorithm. In a classical‐quantum hybrid architecture, this approach is extended to build the circuit for the maximum clique problem. Our technique is generalised since the program automatically builds the circuit for any given undirected and unweighted graph and any chosen k . For a small k with regard to a big graph, the proposed solution to addressing the k ‐clique issue has shown a reduction in qubit cost and circuit depth when compared to the state‐of‐the‐art approach. A framework is also presented for mapping the automated generated circuit for clique problems to quantum devices. Using IBM's Qiskit, an analysis of the experimental results is demonstrated.
Abstract Quantum search algorithm (also known as Grover's algorithm) lays the foundation for many other quantum algorithms. Although it is very simple, its implementation is limited on noisy intermediate-scale quantum (NISQ) processors. Grover's algorithm was designed without considering the physical resources, such as depth, in the real implementations. Therefore, Grover's algorithm can be improved for NISQ devices. In this paper, we demonstrate how to implement quantum search algorithms better on NISQ devices. We present detailed benchmarks of the five-qubit quantum search algorithm on different quantum processors, including IBMQ, IonQ, and Honeywell quantum devices. We report the highest success probability of the five-qubit search algorithm compared to previous works. Our results show that designing the error-aware quantum search algorithms is possible, which can maximally harness the power of NISQ computers.