Αναζήτηση

Πλοήγηση

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

Ο Χώρος μου

• Είσοδος

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

Leonidas Ioannis

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

---

Περίληψη

Αυτή η διατριβή παρουσιάζει μια νέα προσέγγιση για την επίλυση προβλημάτων βέλτιστης διαδρομής και προγραμματισμού που τετραγωνικής βελτιστοποίησης χωρίς περιορισμούς (ΤΒΧΠ) χρησιμοποιώντας έναν νέο κβαντικό αλγόριθμο που αναπτύξαμε με συνεργάτες στο Κέντρο Κβαντικών Τεχνολογιών της Σιγκαπούρης. Ο αλγόριθμος επιτρέπει την αντιστοίχιση Ν κλασικών δυαδικών μεταβλητών σε 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% του χώρου λύσης.

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

Υπηρεσίες