Resource efficient quantum-classical computing and applications in scheduling and optimization problemsResource efficient quantum-classical computing and applications in scheduling and optimization problemsΥβριδική κβαντική-κλασσική υπολογιστική με αποδοτική χρήση πόρων και εφαρμογές σε προβλήματα χρονοπορογραμματισμού και βελτιστοποίησης Διπλωματική Εργασία Diploma Work 2025-07-032025enThis thesis investigates the application of hybrid quantum-classical algorithms to solve Job Shop Scheduling Problems (JSSP), a class of NP-hard combinatorial optimization problems. The work begins by introducing the foundational principles of quantum mechanics and quantum computing, highlighting their unique characteristics that hold the potential to revolutionize computational paradigms. Then, teleportation is presented to demonstrate how these quantum properties can be harnessed in practice in real quantum algorithms. The study then explores the use of Quadratic Unconstrained Binary Optimization (QUBO) as a framework for representing and solving combinatorial optimization problems using both classical and quantum computational resources. State-of-the-art quantum approaches, such as the Quantum Approximate Optimization Algorithm (QAOA) and the Variational Quantum Eigensolver (VQE)—implemented with a Hardware-Efficient Ansatz (HEA)—are discussed in depth. These algorithms are tested on benchmark problems including Max-Cut and Subset Sum, establishing a foundation for their application to more complex scheduling problems. A particular instance of the JSSP is then formulated mathematically, with all necessary constraints rigorously defined. This formulation is translated into a QUBO-compatible representation to enable its execution on quantum backends. Initial experiments using QAOA and HEA are conducted on small problem instances to assess the correctness and feasibility of the proposed formulation. Recognizing the limitations of current quantum hardware—particularly when scaling beyond toy problems—the thesis introduces qubit-efficient encoding schemes as a strategy to address scalability challenges inherent in conventional quantum approaches. These schemes are evaluated using standard problems such as Subset Sum before being applied to a scaled-up version of the JSSP, approaching instances that resemble real-world scheduling tasks. Finally, real IBM quantum hardware accessed via cloud platforms is used to run selected problem instances, providing insight into the behavior of the algorithms under realistic noise conditions. The findings suggest that while solving multi-constraint combinatorial problems with compact QUBO formulations remains challenging, the continued evolution of quantum hardware offers promising potential. This work contributes to the advancement of quantum computing techniques for addressing complex scheduling problems and lays the groundwork for future research in this domain.Αυτή η διπλωματική εργασία εξετάζει την εφαρμογή υβριδικών κβαντικών-κλασικών αλγορίθμων για την επίλυση 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 διατυπώσεις παραμένει πρόκληση, η συνεχής πρόοδος του κβαντικού υλικού προσφέρει υποσχόμενες προοπτικές. Η παρούσα εργασία συμβάλλει στην πρόοδο των τεχνικών κβαντικής υπολογιστικής για την επίλυση σύνθετων προβλημάτων χρονοπρογραμματισμού και θέτει τις βάσεις για μελλοντική έρευνα στον συγκεκριμένο τομέα.http://creativecommons.org/licenses/by/4.0/Πολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών ΥπολογιστώνVenetis_Nikolaos_Dip_2025.pdfChania [Greece]Library of TUC2025-07-03application/pdf3.6 MBfree Venetis Nikolaos Βενετης Νικολαος Angelakis Dimitrios Αγγελακης Δημητριος Spyropoulos Thrasyvoulos Σπυροπουλος Θρασυβουλος Christopoulos Dionysios Χριστοπουλος Διονυσιος Πολυτεχνείο Κρήτης Technical University of Crete Quantum computing Quantum optimization