Evaluating an RCPSP Implementation of Quantum Program Scheduling

Abstract

The goal of quantum application scheduling is to enable the execution of applications on a quantum network. As the final step in the application scheduling process, program scheduling locally schedules execution of blocks of instructions on each node by defining so-called node schedules. In this thesis, we present a formal definition of program scheduling and propose success metrics to evaluate the quality of node schedules. We implement program scheduling using the framework of Resource-Constrained Project Scheduling Problem (RCPSP) and and simulate the execution of node schedules. By evaluating the performance of program scheduling on datasets with diverse quantum applications including quantum key distribution and blind quantum computing, we observe that heuristic-driven approaches achieve comparable results to optimal program scheduling while requiring fewer computational resources. Our work offers valuable insights into the translation of classical scheduling problems into the quantum domain, contributing to the advancement of quantum application scheduling.