Non-crossing neighborhood searching on quantum computer for a single machine scheduling problem
Wojciech Bożejko, Mariusz Uchroński, Mieczysław Wodecki · IFAC-PapersOnLine · 2025
Many issues related to optimization practice belong to the class of NP-hard problems. Due to the large size of practical examples, metaheuristics are mainly used to solve them. However, calculations performed on classical computers, due to the computation time and values of the solutions determined, do not meet the expectations of many practitioners. In turn, quantum computers currently have too few qubits to solve even medium-sized examples. In this paper, we present a new approach to using neighborhoods with an exponential number of elements in local search algorithms. A hybrid CPU/QPU algorithm, in which the search of the neighborhood is performed on a quantum computer, allows for more efficient use of the currently available power of quantum computers.