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

Zhu, Junjie (2024) Benchmarking of D-Wave's and IBM's devices on known Quantum solutions to NP-complete problems. [Laurea magistrale], Università di Bologna, Corso di Studio in Artificial intelligence [LM-DM270], Documento ad accesso riservato.
Documenti full-text disponibili:
[img] Documento PDF (Thesis)
Full-text non accessibile fino al 30 Settembre 2025.
Disponibile con Licenza: Creative Commons: Attribuzione - Non commerciale - Condividi allo stesso modo 4.0 (CC BY-NC-SA 4.0)

Download (1MB) | Contatta l'autore

Abstract

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.

Abstract
Tipologia del documento
Tesi di laurea (Laurea magistrale)
Autore della tesi
Zhu, Junjie
Relatore della tesi
Correlatore della tesi
Scuola
Corso di studio
Ordinamento Cds
DM270
Parole chiave
Quantum computing,NP-complete,Graph coloring problem,Quantum annealing,Quantum circuit,QUBO,QAOA
Data di discussione della Tesi
8 Ottobre 2024
URI

Altri metadati

Gestione del documento: Visualizza il documento

^