Benchmarking of D-Wave's and IBM's Devices on Known Quantum Solutions to NP-Complete Problems
Junjie Zhu, Filippo Orazi, Sara Marzella, Daniele Ottaviani, Stefano Lodi · 2025
Quantum computing has the potential to revolutionize the way we solve problems that are computationally infeasible for classical computers. This paper explores the application of quantum computing to NP-complete problems, and by focusing on the Graph Coloring Problem (GCP) we benchmark the performance of two prominent quantum computing devices: D-Wave's quantum annealer and IBM's gatebased quantum processors. After mapping instances of the GCP native formulation, we evaluate the effectiveness and limitations of quantum annealing and gate-based approaches in tackling such combinatorial problems. For annealers, the problem is cast into Quadratic Unconstrained Binary Optimization (QUBO) forms, while gate-based quantum devices employ variational algorithms like the Quantum Approximate Optimization Algorithm (QAOA). The research includes a comparative analysis, highlighting the scalability, accuracy, and practical challenges faced by current quantum hardware.