Investigating Evolving Ansatz VQE Algorithms for Job Shop Scheduling

Kurzfassung

The job shop scheduling problem (JSSP) is an important and much-researched combinatorial optimization problem that is NP-complete for more than two machines. Many algorithms for solving it exactly and approximately exist. Recently, some research has been done on using variational quantum algorithms (VQA) like QAOA or VQE to approximately solve the JSSP. The hope is that such VQAs might be able to find better solutions with less computational effort than classical optimization heuristics. In VQAs, a quantum circuit whose behaviour is controlled by parameter values is used to create a quantum state. Measuring the expectation value of that quantum state with respect to the problem Hamiltonian yields its quality with respect to the optimization problem. A classical optimization algorithm is then used within VQAs in an iterative loop to minimize the expectation value by adjusting the parameter values. This procedure is repeated until a good solution to the optimization problem is found. The parameterized quantum circuit used within a VQA algorithm is usually referred to as its ansatz. It needs to be designed to provide a good amount of expressibility while avoiding barren plateaus. This is difficult and has led researchers to investigate adaptive VQA methods, which, in addition to optimizing the parameter values, also optimize the structure of the ansatz. Amongst these are evolving ansatz algorithms like EVQE, MoG-VQE, and QNEAT, which use evolutionary algorithms to achieve this goal. They have been shown to provide promising results and to be remarkably noise-resistant, while using much smaller ansatz circuits than typical for VQAs. These advantages might make them interesting for solving complex optimization problems like the JSSP. Yet, it remains unclear how such methods scale to problems of increasing size and complexity. To alleviate this gap in current research, this thesis investigates the scaling of evolving ansatz variational quantum eigensolvers for the JSSP and compares it to the scaling of QAOA and VQE. To this end, the average solution quality and the average number of expectation value evaluations needed for the algorithms to converge are measured over multiple random JSSP problem instances for each problem size. This entails the design of a method for generating random JSSP problem instances and their translation into a Hamiltonian usable by the VQA algorithms. To limit the impact of bad parameter choices on the performance of the VQA algorithms, hyperparameter optimisation is applied before benchmarking.