Benchmarking of D-Wave's and IBM's devices on known Quantum solutions to NP-complete problems

Quantum computing has the potential to revolutionize the way we solve complex problems that are computationally infeasible for classical computers. This thesis explores the application of quantum computing to NP-complete problems, focusing specifically on the Graph Coloring Problem (GCP), a fundamental NP-hard problem with real-world applications in areas such as scheduling, register allocation, and network frequency assignment. The study benchmarks the performance of two prominent quantum computing architectures: D-Wave’s quantum annealer and IBM’s gate-based quantum processors. By mapping instances of the GCP onto each platform’s native problem formulation, we evaluate the effectiveness and limitations of quantum annealing and gate-based approaches in tackling such combinatorial problems. For D-Wave, the GCP is translated into a Quadratic Unconstrained Binary Optimization (QUBO) problem, while IBM’s quantum devices employ variational algorithms like the Quantum Approximate Optimization Algorithm (QAOA). Key findings of the research include a comparative analysis of the results achieved on each platform, highlighting the scalability, accuracy, and practical challenges faced by current quantum hardware. This work serves as a foundation for understanding the capabilities of present-day quantum computers in solving NP-complete problems and discusses future improvements required to enhance their practical applicability. The thesis concludes by outlining future research directions, emphasizing the need for improvements in quantum hardware, error mitigation, and hybrid quantum-classical algorithms to push the boundaries of quantum computing in solving large and complex problems.