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

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Προσεγγιστικοί κβαντικοί αλγόριθμοιβελτιστοποίησης και εφαρμογές

Leonidas Ioannis

Απλή Εγγραφή


URIhttp://purl.tuc.gr/dl/dias/5551FF4C-F40D-45AA-ACBF-1BC8492145AB-
Αναγνωριστικόhttps://doi.org/10.26233/heallink.tuc.90563-
Γλώσσαen-
Μέγεθος2 megabytesen
Μέγεθος97 pagesen
ΤίτλοςQuantum approximate optimization algorithms and applicationsen
ΤίτλοςΠροσεγγιστικοί κβαντικοί αλγόριθμοι βελτιστοποίησης και εφαρμογέςel
ΔημιουργόςLeonidas Ioannisen
ΔημιουργόςΛεωνιδας Ιωαννηςel
Συντελεστής [Επιβλέπων Καθηγητής]Ellinas Dimosthenisen
Συντελεστής [Επιβλέπων Καθηγητής]Ελληνας Δημοσθενηςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Bletsas Aggelosen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Μπλετσας Αγγελοςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Aggelakis Dimitriosen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Αγγελακης Δημητριοςel
ΕκδότηςΠολυτεχνείο Κρήτηςel
ΕκδότηςTechnical University of Creteen
Ακαδημαϊκή ΜονάδαTechnical University of Crete::School of Electrical and Computer Engineeringen
Ακαδημαϊκή ΜονάδαΠολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστώνel
ΠερίληψηIn this thesis we start by defining the basic components that bring together a quantum circuit. Weexplain basic gates, the concept of entanglement and why these are important for the construction ofquantum algorithms. Then we proceed by analyzing two basic quantum algorithms (Deutsch-Joszaand Grover’s algorithms), which are the earliest in quantum computing and illustrate the notion ofa quantum speed up. Next, we analyse the basic approaches for quantum optimization, includingthe notions of quantum annealing and adiabatic quantum computing, and analyze the first mainalgorithm of this thesis which is the Quantum Approximate Optimization Algorithm (QAOA). Wealso introduce and explain the Variational Quantum Eigensolver (VQE) and its hardware efficientversion, which does not require specific gates decomposition and compare it with QAOA on thecontext of solving MAXCUT problems. In the final part, we analyze QAOA on a more industrialoptimization setting, and solve instances of the Tail Assignment Problem for assigning planes indifferent routes. For this problem we test QAOA using the conventional method of minimizing theexpectation value of the cost Hamiltonian and discuss the results. Finally, we also apply solve theproblem by an another method based on minimizing the Gibbs objective function where we seeimprovements in the success probability. We analyse the inner workings of the algorithms, discussthe results and compare the various methods for different problem sizes and instances. We run ourquantum algorithms in simulators, with noise and ideal ones, as well as on and prototype quantumhardware available in the cloud in IBM Q and analyze the performance for different problem sizeand qubit numbers.en
ΠερίληψηΣε αυτή τη διατριβή ξεκινάμε καθορίζοντας τα βασικά συστατικά που υλοποιούν ένα κβαντικό κύκλωμα. Εξηγούμε τις βασικές πύλες, την έννοια του εναγκαλισμού (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.el
ΤύποςΔιπλωματική Εργασίαel
ΤύποςDiploma Worken
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by/4.0/en
Ημερομηνία2021-10-15-
Ημερομηνία Δημοσίευσης2021-
Θεματική ΚατηγορίαGibbs objective functionen
Θεματική ΚατηγορίαMAXCUTen
Θεματική ΚατηγορίαTail assignment problemen
Θεματική ΚατηγορίαVariational quantum eigensolver (VQE)en
Θεματική ΚατηγορίαQuantum approximation optimization algorithm (QAOA)en
Θεματική ΚατηγορίαOptimizationen
Θεματική ΚατηγορίαQuantum approximate optimization algorithmsen
Βιβλιογραφική ΑναφοράIoannis Leonidas, "Quantum approximate optimization algorithms and applications", Diploma Work, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2021en
Βιβλιογραφική ΑναφοράΙωάννης Λεωνίδας, "Προσεγγιστικοί κβαντικοί αλγόριθμοι βελτιστοποίησης και εφαρμογές", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2021el

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

Υπηρεσίες

Στατιστικά