Funktionen

Investigating Evolving Ansatz VQE Algorithms for Job Shop Scheduling

The job shop scheduling problem (JSSP) is an important and much researched combinatorial optimisation problem, which 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 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 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 optimisation problems like the JSSP. Yet, it remains unclear, how such methods scale for problems of increasing size and complexity. To alleviate this gap in current research, this thesis investigates the scaling of evolving ansatz variational eigensolvers for the JSSP and compares it to the scaling of QAOA and VQE. To this end, the average amount of quantum circuit evaluations needed for the algorithms to converge is 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. From the benchmarking results, an approximation of the respective algorithm's scaling is inferred. Finally, improvements are proposed and evaluated to reduce the amount of circuit evaluations needed by evolving ansatz VQE algorithms.

Organisatorisches:

Aufgabensteller:

• Prof. Dr. D. Kranzlmüller

Dauer der Arbeit:

• gemäß Studienordnung

Anzahl Bearbeiter: 1

Betreuer:

• Xiao-Ting Michelle To
• Korbinian Staudacher
• Justyna Zawalska (Cyfronet)
• Dr. Sven Prüfer (DLR)