Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Αποτελεσματική σε Qubit κβαντική βελτιστοποίηση και εφαρμογές σε προβλήματα δρομολόγησης και προγραμματισμού οχημάτων

Leonidas Ioannis

Απλή Εγγραφή


URIhttp://purl.tuc.gr/dl/dias/2B1FC6E4-AEA0-4757-864D-454C91A68A3C-
Αναγνωριστικόhttps://doi.org/10.26233/heallink.tuc.99392-
Γλώσσαen-
Μέγεθος5.2 megabytesen
Μέγεθος108 pagesen
ΤίτλοςQubit efficient quantum optimization and applications in routing and scheduling problemsen
ΤίτλοςΑποτελεσματική σε Qubit κβαντική βελτιστοποίηση και εφαρμογές σε προβλήματα δρομολόγησης και προγραμματισμού οχημάτωνel
ΔημιουργόςLeonidas Ioannisen
ΔημιουργόςΛεωνιδας Ιωαννηςel
Συντελεστής [Επιβλέπων Καθηγητής]Angelakis Dimitriosen
Συντελεστής [Επιβλέπων Καθηγητής]Αγγελακης Δημητριοςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Ellinas Dimosthenisen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Ελληνας Δημοσθενηςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Spyropoulos Thrasyvoulosen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Σπυροπουλος Θρασυβουλοςel
ΕκδότηςΠολυτεχνείο Κρήτηςel
ΕκδότηςTechnical University of Creteen
Ακαδημαϊκή ΜονάδαTechnical University of Crete::School of Electrical and Computer Engineeringen
Ακαδημαϊκή ΜονάδαΠολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστώνel
ΠεριγραφήΜεταπτυχιακή διατριβή που υποβλήθηκε στη σχολή ΗΜΜΥ για την λήψη του μεταπτυχιακού διπλώματος.el
ΠερίληψηThis thesis presents a novel approach for solving route and scheduling problems of the Quadratic Unconstrained Binary Optimization (QUBO) type using a novel quantum algorithm developed with collaborators at the Centre for Quantum Technologies in Singapore. The algorithm allows the mapping of classical binary variables to log2(N) + 1 qubits allowing for implementation of industrial level problems in near term quantum computers. We start the work by attacking a problem from the shipping industry known as the Vehicle Routing Problem with Time Windows (VRPTW), which we first cast in QUBO format. We then study how to adapt the qubit efficient algorithm to the problem at hand for different parameter regimes and constraints and design the relevant quantum circuits. We run the circuits on simulators first and pick the optimal ones to implement on real quantum computers on the cloud using superconducting and ion based qubits from provided by AWS (IONQ, Riggetti) and IBMQ. We demonstrate that is possible to solve problem instances of 128 and 3964 classical variables using only 8 and 13 qubits, well beyond capabilities of standard approaches based on the quantum approximate optimization algorithm (QAOA). We benchmark our results with the standard binary-to-qubit mappings used in QAOA and standard commercial solvers such as Gurobi find excellent agreement. Next, we introduce a novel reinforcement learning (RL) enhancement algorithm that can be used on top of our qubit efficient encoding to further enhance the quality of solutions obtained. In the final two chapters, we formulate as QUBO and then solve two more optimization problems from the aviation industry, namely the Tail Assignment Problem (TAP) and the Flight Gate Assignment (FGA) to test the effectiveness of the enhanced algorithm in tackling problems up to 25000 classical variables. Our simulator results show that using the enhanced RL pipeline one can find solutions belonging to the top 1% of the solution space.en
ΠερίληψηΑυτή η διατριβή παρουσιάζει μια νέα προσέγγιση για την επίλυση προβλημάτων βέλτιστης διαδρομής και προγραμματισμού που τετραγωνικής βελτιστοποίησης χωρίς περιορισμούς (ΤΒΧΠ) χρησιμοποιώντας έναν νέο κβαντικό αλγόριθμο που αναπτύξαμε με συνεργάτες στο Κέντρο Κβαντικών Τεχνολογιών της Σιγκαπούρης. Ο αλγόριθμος επιτρέπει την αντιστοίχιση Ν κλασικών δυαδικών μεταβλητών σε log2(N)+1 qubits επιτρέποντας την υλοποίηση προβλημάτων βιομηχανικού επιπέδου σε κβαντικούς υπολογιστές του προσεχούς μέλλοντος . Ξεκινάμε την μελέτη λύνοντας ένα πρόβλημα από τη ναυτιλιακή βιομηχανία, γνωστό ως το πρόβλημα δρομολόγησης οχημάτων με χρονικούς περιορισμούς, το οποίο μεταφράζουμε πρώτα σε μορφή (ΤΒΧΠ). Στη συνέχεια μελετάμε πώς να προσαρμόσουμε τον αποδοτικό σε qubit αλγόριθμο στο πρόβλημα για διαφορετικές τιμές των παραμέτρων και των περιορισμών, σχεδιάζοντας και τα σχετικά κβαντικά κυκλώματα. Κατόπιν τρέχουμε τα κυκλώματα σε προσομοιωτές και επιλέγουμε αυτά με βέλτιστη απόδοση για εφαρμογή σε πραγματικούς κβαντικούς υπολογιστές στο νέφος χρησιμοποιώντας υπεραγώγιμα και ιοντικά qubit που παρέχονται από την AWS (IONQ, Rigetti) και IBMQ. Αποδεικνύουμε ότι είναι δυνατό να λυθούν περιπτώσεις προβλημάτων με 128 και 3964 κλασικές μεταβλητές χρησιμοποιώντας μόνο 8 και 13 qubits, πολύ πέρα από τις δυνατότητες τυπικών προσεγγίσεων που βασίζονται στον κβαντικό αλγόριθμο βελτιστοποίησης κατά προσέγγιση (QAOA). Συγκρίνουμε τα αποτελέσματά μας με τις τυπικές αντιστοιχίσεις binary-to-qubit που χρησιμοποιούνται με QAOA και εμπορικές λύσεις όπως ο Gurobi και βρίσκουμε εξαιρετική συμφωνία. Στη συνέχεια, εισάγουμε έναν νέο αλγόριθμο βελτίωσης ενισχυτικής μάθησης (RL) που μπορεί να χρησιμοποιηθεί πάνω από τον αποδοτικό σε qubit αλγόριθμο για την περαιτέρω βελτίωση της ποιότητας των λύσεων που λαμβάνουμε. Στα δύο τελευταία κεφάλαια, διατυπώνουμε ως ΤΒΧΠ και στη συνέχεια επιλύουμε δύο ακόμη προβλήματα βελτιστοποίησης από την αεροπορική βιομηχανία, συγκεκριμένα το Tail Assignment Problem (TAP) και το Flight Gate Assignment (FGA) και δοκιμαζουμε την αποτελεσματικότητα του βελτιωμένου αλγορίθμου στην αντιμετώπιση προβλημάτων έως και 25000 κλασικών μεταβλητών. Τα αποτελέσματα του προσομοιωτή μας δείχνουν ότι χρησιμοποιώντας τον βελτιωμένο αγωγό RL, μπορεί κανείς να βρει λύσεις που ανήκουν στο κορυφαίο 1% του χώρου λύσης. el
ΤύποςΜεταπτυχιακή Διατριβήel
ΤύποςMaster Thesisen
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by/4.0/en
Ημερομηνία2024-04-03-
Ημερομηνία Δημοσίευσης2024-
Θεματική ΚατηγορίαQuantum optimizationen
Θεματική ΚατηγορίαOptimization theoryen
Θεματική ΚατηγορίαReinforcement learningen
Θεματική ΚατηγορίαQuantum computingen
Θεματική ΚατηγορίαQuantumen
Βιβλιογραφική ΑναφοράIoannis Leonidas, "Qubit efficient quantum optimization and applications in routing and scheduling problems", Master Thesis, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2024en
Βιβλιογραφική ΑναφοράΙωάννης Λεωνίδας, "Αποτελεσματική σε Qubit κβαντική βελτιστοποίηση και εφαρμογές σε προβλήματα δρομολόγησης και προγραμματισμού οχημάτων", Μεταπτυχιακή Διατριβή, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2024el

Διαθέσιμα αρχεία

Υπηρεσίες

Στατιστικά