Benchmarking QAOA on the Job Reassignment Problem: An Empirical Analysis

Abstract

In the past decade, there has been significant progress in the development of NISQ (Noisy Intermediate-Scale Quantum) computers, though further hardware improvements are necessary for large-scale quantum algorithms to execute without errors. In the meantime, researchers continue to focus on developing effective algorithms for current hardware, with an emphasis on near-term applications like combinatorial optimisation. This study presents a benchmarking analysis of the
Quantum Approximate Optimisation Algorithm (QAOA) applied to the Job Reassignment Problem (JRP), which involves assigning n workers to m vacant jobs to maximize high-priority task completion and worker satisfaction. The benchmarking, performed with classical simulation on 105 JRP instances, shows promising results with approximation ratios ranging from 0.86 to 0.97. This leads to an average improvement of 12% in the organisational productivity thanks to a better assignment of highpriority
tasks and worker satisfaction.