Συντάχθηκε 01-07-2024 11:36
Τόπος:
Σύνδεσμος τηλεδιάσκεψης
Έναρξη: 02/07/2024 13:30
Λήξη: 02/07/2024 14:30
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
Άρτεμις Ηλιοπούλου
με θέμα
Υβριδικοί Αλγόριθμοι Κβαντικής Βελτιστοποίησης και Εφαρμογές
Hybrid Quantum Optimization Algorithms and Applications
Εξεταστική Επιτροπή
Καθηγητής Δημήτριος Αγγελάκης (επιβλέπων)
Αναπληρωτής Καθηγητής Βασίλειος Σαμολαδάς
Καθηγητής Μιχαήλ Ζερβάκης
Περίληψη
Αυτή η διπλωματική εξετάζει την εφαρμογή της κβαντικής υπολογιστικής στην επίλυση προβλημάτων βελτιστοποίησης και, πιο συγκεκριμένα, προβλημάτων χρονοπρογραμματισμού. Το πρώτο κεφάλαιο παρέχει μια εισαγωγή στην κβαντική υπολογιστική. Καλύπτει βασικούς ορισμούς, συμπεριλαμβανομένων των μονών και πολλαπλών καταστάσεων κβαντικών δυαδικών ψηφίων (qubits), των κβαντικών πυλών και του φαινομένου της διαπλοκής. Επίσης, αναλύει τη σημασία και τον τρόπο κατασκευής ενός από τους θεμελιώδεις κβαντικούς αλγορίθμους, του αλγορίθμου Deutsch-Josza. Το δεύτερο κεφάλαιο επικεντρώνεται στις βασικές προσεγγίσεις της κβαντικής βελτιστοποίησης, όπως το Quadratic Unconstrained Binary Optimization (QUBO), το Ising μοντέλο, και τις έννοιες του quantum annealing και της αδιαβατικής κβαντικής υπολογιστικής. Επίσης, αναλύει τον Quantum Approximate Optimization Algorithm (QAOA) και παρουσιάζει το πρόβλημα MaxCut και πώς αυτό μπορεί να λυθεί χρησιμοποιώντας τον QAOA. Το τρίτο κεφάλαιο ασχολείται με τα προβλήματα χρονοπρογραμματισμού, συγκεκριμένα το Πρόβλημα Nurse Scheduling Problem (NSP). Εξερευνά το μοντέλο QUBO για το NSP και παρουσιάζει τα αποτελέσματα των προσομοιώσεων που διεξήχθησαν σε διάφορες περιπτώσεις προβλημάτων NSP. Για να ληφθούν τα αποτελέσματα, ο κβαντικός αλγόριθμος έτρεξε στην κβαντική υπηρεσία cloud της D-Wave. Στη συνέχεια, τα αποτελέσματα αναλύονται με βάση την απόδοση για διαφορετικά μεγέθη προβλημάτων και για διαφορετικές τοπολογίες του hardware. Συμπερασματικά, αυτή η διπλωματική παρουσιάζει μια συνολική επισκόπηση των θεμελιωδών εννοιών και τεχνικών που χρησιμοποιούνται στην υβριδική κβαντική-κλασική βελτιστοποίηση και δείχνει τις δυνατότητές της για την επίλυση προβλημάτων βελτιστοποίησης και χρονοπρογραμματισμού.
Abstract
This thesis explores the application of quantum computing in solving optimization and, more specifically, scheduling problems. The first chapter provides an introduction to quantum computing. It covers introductory definitions, including single and multiple qubit states, quantum gates, and entanglement. It also analyzes the construction and importance of one of the fundamental quantum algorithms, the Deutsch-Josza algorithm. The second chapter focuses on the basic approaches to quantum optimization, such as Quadratic Unconstrained Binary Optimization (QUBO), the Ising model, and the notions of quantum annealing and adiabatic quantum computing. It also analyzes the Quantum Approximate Optimization Algorithm (QAOA) and demonstrates the MaxCut problem and how it can be solved using the QAOA. The third chapter delves into scheduling problems, precisely the Nurse Scheduling Problem (NSP). It explores the formulation of NSP and presents the results of the simulations conducted on various instances of NSP problems. The quantum algorithm ran on the quantum cloud service in D-Wave to obtain the results. Then, the performance for different problem sizes and topologies of the hardware is analyzed. Overall, this thesis presents a comprehensive overview of the fundamental concepts and techniques used in hybrid quantum-classical optimization and demonstrates its potential for solving optimization and scheduling problems.
Meeting ID: 942 6621 0637
Password: 231504
