The new exponential Fibonacci neighborhood as QUBO generated on a D-Wave quantum computing environment for the permutational scheduling problem

Quantum computers open up new possibilities for faster and more efficient solutions to real-world, large-scale optimization problems that currently pose a challenge for classical computer systems. One such problem is searching very large neighborhoods, with an exponential number of elements, in local search algorithms for solving NP-hard problems. Currently, the only barrier to the effective use of quantum computers in optimization is the limited number of available qubits. Therefore, the main challenge today, given the limited number of qubits, is to formulate the problem to be solved in a form that minimizes the number of variables and, consequently, the number of necessary qubits. To meet these expectations, we propose a new solution representation used to generate neighborhoods with an exponential number of elements. We prove that for n -element permutations, the number of elements in this neighborhood is the n -th Fibonacci number. Permutations are commonly represented by binary matrices with \(n^2\) elements. We propose a new, cost-effective method for representing solutions using \(n-1\) element binary sequences. For an \(n=50\) element permutation, the former requires 2500 qubits, while the latter requires only 49. Computational experiments for a certain NP-hard single-machine scheduling problem were performed on a D-Wave quantum computer. The obtained results clearly indicate the high effectiveness of the presented method. With a limited number of qubits, it is possible to search neighborhoods for much larger permutations. By examining the capabilities and limitations of current quantum annealers, we can more precisely identify them and then use them in the construction of new algorithms better suited to current and future quantum computers.