Sajko, W. (2023):

Exploring the Potential of Filtering Variational Quantum Eigensolvers for Job Scheduling

Job scheduling is a complex optimization problem with multiple variables, constraints, and goals. Solving such problems using classical computing can be challenging, since they are NP-complete and real-world instances can be quite large. Quantum computing is a promising solution, as it is theoretically faster than classical computing for certain types of problems. In this thesis, we use the filtering variational quantum eigensolver (F-VQE), a parameter- ized quantum algorithm, to solve a simplified real-world scheduling problem. The F-VQE algorithm optimizes solutions by filtering out unpromising ones and using a classical op- timization routine to refine the remaining solutions. Although the F-VQE algorithm is based on a paper by Amaro et al., it has not yet been fully evaluated for solving scheduling problems. While VQEs have been successful in solving combinatorial optimiza- tion problems, we seek to assess the performance of F-VQE in solving scheduling problems. We have two objectives in this research: firstly, to enhance and analyze the F-VQE al- gorithm, and secondly, to evaluate the potential of quantum computing in solving complex scheduling problems. To accomplish this, we will compare the performance of the F-VQE algorithm with other quantum and classical approaches for solving real-world scheduling problems. This will provide valuable insights into the effectiveness of quantum comput- ing for solving these problems, as well as identify potential improvements to the F-VQE algorithm. We delve deeper into the F-VQE algorithm to identify potential areas for improvement. We will examine various ansatz designs, different filtering strategies, and encoding techniques. Worthwhile additions are implemented and tested against. To compare the F-VQE algorithm’s performance with other variational quantum algo- rithms and an approach using Grover’s algorithm, which is already implemented by the DLR. We evaluate the efficiency, scalability, and quality of solutions provided by each algo- rithm and discuss the potential benefits and drawbacks of the F-VQE for solving real-world scheduling problems.

• PDF Version (6,649.9 KB)