Search

Browse

• Communities
• Authors
• Year
• Titles
• Subjects

My Space

• Login

Resource efficient quantum-classical computing and applications in scheduling and optimization problems

Venetis Nikolaos

Full record

---

Summary

This 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.

Available Files

Services