Συντάχθηκε 11-10-2021 10:11
Ενημερώθηκε:
12-10-2021 14:10
Τόπος: Η παρουσίαση θα γίνει με τηλεδιάσκεψη
Σύνδεσμος τηλεδιάσκεψης
Έναρξη: 13/10/2021 09:30
Λήξη: 13/10/2021 10:30
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
ΙΩΑΝΝΗΣ ΛΕΩΝΙΔΑΣ
Θέμα
Προσεγγιστικοί Κβαντικοί Αλγόριθμοι Βελτιστοποίησης και Εφαρμογές
Quantum Approximate Optimization Algorithms and Applications
Εξεταστική Επιτροπή
Καθηγητής Δημοσθένης Έλληνας (επιβλέπων)
Καθηγητής Άγγελος Μπλέτσας
Αναπληρωτής Καθηγητής Δημήτριος Αγγελάκης (Principal Investigator and Assoc. Prof, CQT, National University of Singapore)
Περίληψη
Σε αυτή τη διατριβή ξεκινάμε καθορίζοντας τα βασικά συστατικά που υλοποιούν ένα κβαντικό κύκλωμα. Εξηγούμε τις βασικές πύλες, την έννοια του εναγκαλισμού (entanglement) και γιατί αυτές είναι σημαντικές για την κατασκευή κβαντικών αλγορίθμων. Στη συνέχεια, προχωρούμε αναλύοντας δύο βασικούς κβαντικούς αλγόριθμους (αλγόριθμοι Deutsch-Josza και Grover), οι οποίοι αποτελούν την είσοδο στον κβαντικό υπολογισμό. Στο κεφάλαιο 3 εξηγούμε τη θεωρία πίσω από την κβαντική βελτιστοποίηση και εξηγούμε τον πρώτο κύριο αλγόριθμο αυτής της διπλωματικής εργασίας, ο οποίος είναι ο αλγόριθμος Quantum Approximate Optimization Algorithm (QAOA). Επίσης, εξηγούμε τον Variational Quantum Eigensolver (VQE) και τον συγκρίνουμε με τον QAOA στο πλαίσιο του προβλήματος MAXCUT. Στο κεφάλαιο 4 αναλύουμε τον QAOA σε ένα πιο βιομηχανικό πρόβλημα βελτιστοποίησης, το Tail Assignment Problem για την εκχώρηση αεροπλάνων σε διαφορετικές διαδρομές. Για αυτό το πρόβλημα δοκιμάζουμε τον QAOA χρησιμοποιώντας τη συμβατική μέθοδο ελαχιστοποίησης της μέσης τιμής της Χαμιλτονιανής κόστους. Μετά από αυτό δοκιμάζουμε τον QAOA ελαχιστοποιώντας τη συνάρτηση κόστους Gibbs όπου βλέπουμε βελτιώσεις στην πιθανότητα επιτυχίας. Αναλύουμε τα αποτελέσματα και συγκρίνουμε τις διάφορες μεθόδους για διαφορετικά μεγέθη και περιπτώσεις προβλημάτων. Εκτελούμε τους κβαντικούς αλγόριθμους σε προσομοιωτές και πραγματικούς κβαντικούς υπολογιστές διαθέσιμους στο cloud στο IBM Q.
Abstract
In this thesis we start by defining the basic components that bring together a quantum circuit. We explain basic gates, the concept of entanglement and why these are important for the construction of quantum algorithms. Then we proceed by analyzing two basic quantum algorithms (Deutsch-Josza and Grover's algorithms), which are the entry gate to quantum computing. In chapter 3 we explain the theory behind quantum optimization and explain the first main algorithm of this thesis which is the Quantum Approximate Optimization Algorithm (QAOA). Also we explain the Variational Quantum Eigensolver (VQE) and compare it with QAOA on the context of MAXCUT problem. In chapter 4 we analyze QAOA on a more industrial optimization setting, the Tail Assignment Problem for assigning planes in different routes. For this problem we test QAOA using the conventional method of minimizing the expectation value of the cost Hamiltonian. After this we test QAOA by minimizing the Gibbs objective function where we see improvements in the success probability. We analyze the results and compare the various methods for different problem sizes and instances. We run our quantum algorithms in simulators and real quantum hardware available in the cloud in IBM Q.
Meeting ID: 980 6092 8492
Password: 758616
