Αναζήτηση

Πλοήγηση

• Κοινότητες
• Συγγραφείς
• Έτος
• Τίτλοι
• Θέματα

Ο Χώρος μου

• Είσοδος

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

Venetis Nikolaos

Πλήρης Εγγραφή

---

Περίληψη

Αυτή η διπλωματική εργασία εξετάζει την εφαρμογή υβριδικών κβαντικών-κλασικών αλγορίθμων για την επίλυση Job Shop Scheduling προβλημάτων - JSSP, μιας κατηγορίας συνδυαστικών προβλημάτων βελτιστοποίησης που ανήκουν στην κλάση NP-Hard. Η εργασία ξεκινά με την παρουσίαση των βασικών αρχών της κβαντομηχανικής και της κβαντικής υπολογιστικής, επισημαίνοντας τα ιδιαίτερα χαρακτηριστικά τους που ενδέχεται να φέρουν επανάσταση στα υπολογιστικά πρότυπα.Ακολούθως, παρουσιάζεται το πρωτόκολλο της κβαντικής τηλεμεταφοράς, ως παράδειγμα αξιοποίησης των ιδιοτήτων της κβαντικής φυσικής στην πράξη, εντός πραγματικών κβαντικών αλγορίθμων. Στη συνέχεια, διερευνάται η χρήση του μοντέλου Quadratic Unconstrained Binary Optimization - QUBO ως πλαίσιο αναπαράστασης και επίλυσης συνδυαστικών προβλημάτων βελτιστοποίησης μέσω τόσο κλασικών όσο και κβαντικών υπολογιστικών πόρων.Ακολουθεί μελέτη σύγχρονων κβαντικών προσεγγίσεων λύσης του παραπάνω, όπως ο Κβαντικός Προσεγγιστικός Αλγόριθμος Βελτιστοποίησης (Quantum Approximate Optimization Algorithm – QAOA) και ο Κβαντικός Αλγόριθμος Έυρεσης Ιδιωτιμών (Variational Quantum Eigensolver – VQE), ο οποίος υλοποιείται με τη χρήση ενός κυκλώματος που ονομάζεται Hardware-Efficient Ansatz - HEΑ. Οι αλγόριθμοι αυτοί δοκιμάζονται αρχικά σε πρότυπα προβλήματα όπως το Max-Cut και το Subset Sum, θέτοντας τις βάσεις για την εφαρμογή τους σε πιο πολύπλοκα προβλήματα χρονοπρογραμματισμού.Έπειτα, διατυπώνεται μαθηματικά ένα συγκεκριμένο παράδειγμα του προβλήματος JSSP, με αυστηρό ορισμό όλων των απαραίτητων περιορισμών. Η διατύπωση αυτή μεταφράζεται σε μορφή συμβατή με το πλαίσιο QUBO, προκειμένου να μπορεί να εκτελεστεί σε κβαντικά υπολογιστικά περιβάλλοντα. Πραγματοποιούνται αρχικά πειράματα με χρήση των QAOA και HEA σε μικρές περιπτώσεις προβλημάτων, ώστε να αξιολογηθεί η ορθότητα και η πρακτική εφαρμοσιμότητα της προτεινόμενης μεθόδου.Αναγνωρίζοντας τους περιορισμούς των σύγχρονων κβαντικών υπολογιστών—ιδίως ως προς την κλιμάκωση πέρα από απλοποιημένες περιπτώσεις—η εργασία εισάγει αποδοτικά μια τεχνική που ονομάζεται qubit efficient encoding schemes ως στρατηγική για την αντιμετώπιση των προκλήσεων επεκτασιμότητας που παρουσιάζονται στις συμβατικές κβαντικές προσεγγίσεις. Τα σχήματα αυτά αξιολογούνται σε πρότυπα προβλήματα όπως το Subset Sum και στη συνέχεια εφαρμόζονται σε επεκταμένη εκδοχή του JSSP, προσεγγίζοντας σενάρια που αντανακλούν ρεαλιστικά προβλήματα χρονοπρογραμματισμού.Τέλος, επιλεγμένα προβλήματα εκτελούνται σε πραγματικούς κβαντικούς υπολογιστές της ΙΒΜ μέσω cloud, παρέχοντας πολύτιμη πληροφορία για τη συμπεριφορά των αλγορίθμων υπό ρεαλιστικές συνθήκες κβαντικού θορύβου. Τα αποτελέσματα υποδεικνύουν ότι, παρόλο που η επίλυση συνδυαστικών προβλημάτων με πολλούς περιορισμούς με συμπαγείς QUBO διατυπώσεις παραμένει πρόκληση, η συνεχής πρόοδος του κβαντικού υλικού προσφέρει υποσχόμενες προοπτικές. Η παρούσα εργασία συμβάλλει στην πρόοδο των τεχνικών κβαντικής υπολογιστικής για την επίλυση σύνθετων προβλημάτων χρονοπρογραμματισμού και θέτει τις βάσεις για μελλοντική έρευνα στον συγκεκριμένο τομέα.

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

Υπηρεσίες