BEGIN:VCALENDAR VERSION:2.0 PRODID:-//TUC//Events//EN CALSCALE:GREGORIAN BEGIN:VTIMEZONE TZID:Europe/Athens TZNAME:EEST DTSTART:19700329T030000 RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=3 BEGIN:STANDARD TZOFFSETFROM:+0200 TZOFFSETTO:+0300 TZNAME:EET DTSTART:19701025T040000 RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=10 END:STANDARD END:VTIMEZONE BEGIN:VEVENT CREATED:20240226T123849Z LAST-MODIFIED:20240226T123849Z DTSTAMP:20260616T001715Z UID:1781558235@tuc.gr SUMMARY:Παρουσίαση Μεταπτυχιακής Εργασίας κ. Ιωάννη Λεωνίδα - Σχολή ΗΜΜΥ LOCATION: DESCRIPTION:https://www.tuc.gr/el/to-polytechnei o/ilektronikes-ypiresies/imerologio/ imerologio-ekdiloseon-1?tx_tucevents 2_tuceventsdisplay%5Baction%5D=show& tx_tucevents2_tuceventsdisplay%5Bcon troller%5D=Event&tx_tucevents2_tucev entsdisplay%5Bevent%5D=6778&cHash=13 856330581c07bb6d3d43a17cecf2df\nΠΟΛΥ ΤΕΧΝΕΙΟ ΚΡΗΤΗΣ\n Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών\ n Πρόγραμμα Μεταπτυχιακών Σπουδών\n ΠΑΡΟΥΣΙΑΣΗ ΜΕΤΑΠΤΥΧΙΑΚΗΣ ΕΡΓΑΣΙΑΣ \n Ιωάννη Λεωνίδα\n με θέμα\n Αποτελεσ ματική σε Qubit Κβαντική Βελτιστοποί ηση και Εφαρμογές σε Προβλήματα Δρομ ολόγησης και Προγραμματισμού Οχημάτω ν\n Qubit Efficient Quantum Optimiza tion and Applications in Routing and Scheduling Problems\n Εξεταστική Επ ιτροπή\n Αναπληρωτής Καθηγητής Δημήτ ριος Γ. Αγγελάκης (επιβλέπων)\n Καθη γητής Θρασύβουλος Σπυρόπουλος\n Καθη γητής Δημοσθένης Έλληνας\n Περίληψη  \n Αυτή η διατριβή παρουσιάζει μια ν έα προσέγγιση για την επίλυση προβλη μάτων βέλτιστης διαδρομής και προγρα μματισμού που τετραγωνικής βελτιστοπ οίησης χωρίς περιορισμούς (ΤΒΧΠ)  χρ ησιμοποιώντας έναν νέο κβαντικό αλγό ριθμο που αναπτύξαμε με συνεργάτες σ το Κέντρο Κβαντικών Τεχνολογιών της Σιγκαπούρης. Ο αλγόριθμος επιτρέπει την αντιστοίχιση Ν κλασικών δυαδικών μεταβλητών σε log2(N)+1 qubits επιτ ρέποντας την υλοποίηση προβλημάτων β ιομηχανικού επιπέδου σε κβαντικούς υ πολογιστές του προσεχούς μέλλοντος . Ξεκινάμε την μελέτη λύνοντας ένα πρ όβλημα από τη ναυτιλιακή βιομηχανία, γνωστό ως το πρόβλημα δρομολόγησης οχημάτων με χρονικούς περιορισμούς, το οποίο μεταφράζουμε πρώτα σε μορφή (ΤΒΧΠ). Στη συνέχεια μελετάμε πώς ν α προσαρμόσουμε τον αποδοτικό σε qub it αλγόριθμο στο πρόβλημα για διαφορ ετικές τιμές των παραμέτρων και των περιορισμών, σχεδιάζοντας και τα σχε τικά κβαντικά κυκλώματα. Κατόπιν τρέ χουμε τα κυκλώματα σε προσομοιωτές κ αι επιλέγουμε αυτά με βέλτιστη απόδο ση για εφαρμογή σε πραγματικούς κβαν τικούς υπολογιστές στο νέφος χρησιμο ποιώντας υπεραγώγιμα και ιοντικά qub it που παρέχονται από την AWS (IONQ, Rigetti) και IBMQ. Αποδεικνύουμε ότ ι είναι δυνατό να λυθούν περιπτώσεις προβλημάτων με 128 και 3964 κλασικέ ς μεταβλητές χρησιμοποιώντας μόνο 8 και 13 qubits, πολύ πέρα από τις δυν ατότητες τυπικών προσεγγίσεων που βα σίζονται στον κβαντικό αλγόριθμο βελ τιστοποίησης κατά προσέγγιση (QAOA). Συγκρίνουμε τα αποτελέσματά μας με τις τυπικές αντιστοιχίσεις binary-to -qubit που χρησιμοποιούνται με QAOA και εμπορικές λύσεις όπως ο Gurobi κ αι βρίσκουμε εξαιρετική συμφωνία. Στ η συνέχεια, εισάγουμε έναν νέο αλγόρ ιθμο βελτίωσης ενισχυτικής μάθησης ( RL) που μπορεί να χρησιμοποιηθεί πάν ω από τον αποδοτικό σε qubit αλγόριθ μο για την περαιτέρω βελτίωση της πο ιότητας των λύσεων που λαμβάνουμε. Σ τα δύο τελευταία κεφάλαια, διατυπώνο υμε ως ΤΒΧΠ και στη συνέχεια επιλύου με δύο ακόμη προβλήματα βελτιστοποίη σης από την αεροπορική βιομηχανία, σ υγκεκριμένα το Tail Assignment Probl em (TAP) και το Flight Gate Assignme nt (FGA) και δοκιμαζουμε την αποτελε σματικότητα του βελτιωμένου αλγορίθμ ου στην αντιμετώπιση προβλημάτων έως και 25000 κλασικών μεταβλητών. Τα α ποτελέσματα του προσομοιωτή μας δείχ νουν ότι χρησιμοποιώντας τον βελτιωμ ένο αγωγό RL, μπορεί κανείς να βρει λύσεις που ανήκουν στο κορυφαίο 1% τ ου χώρου λύσης.\n     \n Abstract\n     \n This thesis presents a novel approach for solving route and sched uling problems of the Quadratic Unco nstrained Binary Optimization (QUBO) type using a novel quantum algorith m developed with collaborators at th e Centre for Quantum Technologies in Singapore. The algorithm allows the mapping of Ν classical binary varia bles to log2(N)+1 qubits allowing fo r implementation of industrial level problems in near term quantum compu ters. We start the work by attacking a problem from the shipping industr y known as the Vehicle Routing Probl em with Time Windows (VRPTW), which we first cast in QUBO format. We the n study how to adapt the qubit effic ient algorithm to the problem at han d for different parameter regimes an d constraints and design the relevan t quantum circuits. We run the circu its on simulators first and pick the optimal ones to implement on real q uantum computers on the cloud using superconducting and ion-based qubits from provided by AWS (IONQ, Riggett i) and IBMQ. We demonstrate that is possible to solve problem instances of 128 and 3964 classical variables using only 8 and 13 qubits, well bey ond capabilities of standard approac hes based on the quantum approximate optimization algorithm (QAOA). We b enchmark our results with the standa rd binary-to-qubit mappings used in QAOA and standard commercial solvers such as Gurobi find excellent agree ment. Next, we introduce a novel rei nforcement learning (RL) enhancement algorithm that can be used on top o f our qubit efficient encoding to fu rther enhance the quality of solutio ns obtained. In the final two chapte rs, we formulate as QUBO and then so lve two more optimization problems f rom the aviation industry, namely th e Tail Assignment Problem (TAP) and the Flight Gate Assignment (FGA) to test the effectiveness of the enhanc ed algorithm in tackling problems up to 25000 classical variables. Our s imulator results show that using the enhanced RL pipeline one can find s olutions belonging to the top 1% of the solution space.\n \n Meeting ID: 944 5283 3423\n Password: 927504\n STATUS:CONFIRMED ORGANIZER;RSVP=FALSE;CN=TUC;CUTYPE=TUC:mailto:webmaster@tuc.gr DTSTART:20240228T100000 DTEND:20240228T110000 TRANSP:OPAQUE CLASS:DEFAULT END:VEVENT END:VCALENDAR