Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Scientific Reports

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

Wojciech Bożejko, Mariusz Uchroński, Mieczysław Wodecki

Published Aug 17, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.1038/s41598-026-66284-9

Related papers

Non-crossing neighborhood searching on quantum computer for a single machine scheduling problem

Wojciech Bożejko, Mariusz Uchroński, Mieczysław Wodecki

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.

IFAC-PapersOnLine•Jan 1, 2025•1 citation

Optimized QUBO formulation methods for quantum computing

Dario De Santis, Salvatore Tirone, Stefano Marmi +1 more

Abstract Quantum computers have strict requirements for the problems that they can efficiently solve. One of the principal limiting factor for the performances of noisy intermediate-scale quantum (NISQ) devices is the number of qubits required by the running algorithm. Several combinatorial optimization problems can be solved with NISQ devices once that a corresponding quadratic unconstrained binary optimization (QUBO) form is derived. Numerous techniques have been proposed to achieve such reformulations and, depending on the method chosen, the number of binary variables required, and therefore of qubits, can vary considerably. The aim of this work is to drastically reduce the variables needed for these QUBO reformulations in order to unlock the possibility to efficiently obtain optimal solutions for a class of optimization problems with NISQ devices. This goal is achieved by introducing novel tools that allow an efficient use of slack variables, even for problems with non-linear constraints, without the need to approximate the starting problem. We divide our new techniques in two independent parts, called the iterative quadratic polynomial and the master-satellite methods. Hence, we show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario called Max-Profit Balance Settlement . We follow by submitting several instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios. Moreover, this study allows to appreciate several performance differences between the D-wave Advantage and next-generation Advantage2 quantum annealers. We show that the adoption of our techniques in this context allows to obtain QUBO formulations with significantly fewer slack variables, i.e. around 90% less, and D-wave annealers provide considerably higher correct solution rates, which moreover do not decrease with the input size as fast as when adopting standard techniques.

arXiv:2406.07681•Quantum Science and Technology•Jan 21, 2026•17 citations

Optimal Solving of a Scheduling Problem Using Quantum Annealing Metaheuristics on the D-Wave Quantum Solver

Wojciech Bożejko, Ryszard Klempous, Jarosław Pempera +4 more

Accurately solving discrete optimization problems is still a serious challenge for classical computing systems. Despite significant progress, it is still impossible to optimally solve examples of the size found in real-world applications. This article examines the problem of scheduling tasks on one machine. Each task has an associated execution time, desired completion date, and a late penalty feature weight. The order of executing tasks should be determined in a manner that minimizes the sum of delay costs. Despite the simplicity of the formulation, this problem is NP-hard and is representative of optimization challenges encountered in the practice of production control, management, and logistics.In this work, we propose using a quantum computing environment to solve it. The main disadvantage of calculations on quantum computers is their nondeterminism. Therefore, there is no guarantee of optimality of solutions to discrete optimization problems determined on a quantum computer.We propose a novel approach to constructing hybrid algorithms that guarantee the optimality of the solution. The algorithm for solving the task scheduling problem considered here is based on the branch and bound method. Calculations are performed alternately on a classical computer and a quantum computer. The lower and upper bounds of the criterion function are determined on a quantum computer. Computational experiments were performed on the D-Wave quantum computer. In small examples, the algorithm runs faster and generates significantly fewer solution tree vertices than its counterpart running on a classic computer. For larger examples, the proposed runtime-constrained method, acting as a heuristic, is an interesting alternative to using quantum computing hardware in relation to classical approaches based on silicon computers.

IEEE Transactions on Systems Man and Cybernetics Systems•Oct 2, 2024•25 citations

Qubit‐Efficient Quantum Local Search for Combinatorial Optimization

Mikhail Podobrii, Viacheslav Kuzmin, Vladimir Voloshinov +2 more

ABSTRACT An essential component of many sophisticated metaheuristics for solving combinatorial optimization problems is some variation of a local search routine that iteratively searches for a better solution within a chosen set of immediate neighbors. The size of this set is limited due to the computational costs required to run the method on classical processing units. We present a qubit‐efficient variational quantum algorithm that implements a quantum version of local search with only qubits and, therefore, can potentially work with classically intractable neighborhood sizes. Increasing the amount of quantum resources employed in the algorithm allows for a larger neighborhood size, improving the quality of obtained solutions. This trade‐off is crucial for present and near‐term quantum devices characterized by a limited number of logical qubits. Numerically simulating our algorithm, we successfully solved the largest graph coloring instance that was tackled by a quantum method. This achievement highlights the algorithm's potential for solving large‐scale combinatorial optimization problems on near‐term quantum devices.

arXiv:2502.02245•Advanced Quantum Technologies•Mar 1, 2026•2 citations

A QUBO Formulation of Minimum Multicut Problem Instances in Trees for D-Wave Quantum Annealers

William Cruz-Santos, Salvador Elías Venegas-Andraca, Marco O. Lanzagorta

Quantum annealing algorithms were introduced to solve combinatorial optimization problems by taking advantage of quantum fluctuations to escape local minima in complex energy landscapes typical of NP - hard problems. In this work, we propose using quantum annealing for the theory of cuts, a field of paramount importance in theoretical computer science. We have proposed a method to formulate the Minimum Multicut Problem into the QUBO representation, and the technical difficulties faced when embedding and submitting a problem to the quantum annealer processor. We show two constructions of the quadratic unconstrained binary optimization functions for the Minimum Multicut Problem and we review several tradeoffs between the two mappings and provide numerical scaling analysis results from several classical approaches. Furthermore, we discuss some of the expected challenges and tradeoffs in the implementation of our mapping in the current generation of D-Wave machines.

Scientific Reports•Nov 20, 2019•32 citations

Solving Scheduling Problems with Quantum Computing: a Study on Flexible Open Shop

Marco Baioletti, Angelo Oddi, Riccardo Rasconi

Despite quantum computing is revealing an increasingly promising technology that has the potential to introduce a significant speed-up in many areas of computation, the number of problems that it can represent and solve is currently rather limited. Therefore, one of the current challenges faced by the quantum computing community is to broaden the class of problems that can be tackled. Among these problems, scheduling problems are a class of particularly interesting and hard combinatorial problems; in this paper, we present a novel solution for representing and solving the Flexible Open Shop Scheduling Problem (FOSSP) to optimality by minimizing the makespan. We firstly present a compact formulation of this problem as a Quadratic unconstrained binary optimization (QUBO), which can be used to solve this problem with a quantum annealer. Then, we proceed to the Quantum Approximate Optimization Algorithm (QAOA) problem formulation, thus producing both the cost and mix Hamiltonians related to the problem. From the Hamiltonians, we provide the complete description of the quantum circuit that can be used to tackle the FOSSP within the QAOA framework. This second approach can be used to solve the optimization problem with a general-purpose quantum gate-based hardware.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 15, 2023•3 citations
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.
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.
Abstract Quantum computers have strict requirements for the problems that they can efficiently solve. One of the principal limiting factor for the performances of noisy intermediate-scale quantum (NISQ) devices is the number of qubits required by the running algorithm. Several combinatorial optimization problems can be solved with NISQ devices once that a corresponding quadratic unconstrained binary optimization (QUBO) form is derived. Numerous techniques have been proposed to achieve such reformulations and, depending on the method chosen, the number of binary variables required, and therefore of qubits, can vary considerably. The aim of this work is to drastically reduce the variables needed for these QUBO reformulations in order to unlock the possibility to efficiently obtain optimal solutions for a class of optimization problems with NISQ devices. This goal is achieved by introducing novel tools that allow an efficient use of slack variables, even for problems with non-linear constraints, without the need to approximate the starting problem. We divide our new techniques in two independent parts, called the iterative quadratic polynomial and the master-satellite methods. Hence, we show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario called Max-Profit Balance Settlement . We follow by submitting several instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios. Moreover, this study allows to appreciate several performance differences between the D-wave Advantage and next-generation Advantage2 quantum annealers. We show that the adoption of our techniques in this context allows to obtain QUBO formulations with significantly fewer slack variables, i.e. around 90% less, and D-wave annealers provide considerably higher correct solution rates, which moreover do not decrease with the input size as fast as when adopting standard techniques.
Accurately solving discrete optimization problems is still a serious challenge for classical computing systems. Despite significant progress, it is still impossible to optimally solve examples of the size found in real-world applications. This article examines the problem of scheduling tasks on one machine. Each task has an associated execution time, desired completion date, and a late penalty feature weight. The order of executing tasks should be determined in a manner that minimizes the sum of delay costs. Despite the simplicity of the formulation, this problem is NP-hard and is representative of optimization challenges encountered in the practice of production control, management, and logistics.In this work, we propose using a quantum computing environment to solve it. The main disadvantage of calculations on quantum computers is their nondeterminism. Therefore, there is no guarantee of optimality of solutions to discrete optimization problems determined on a quantum computer.We propose a novel approach to constructing hybrid algorithms that guarantee the optimality of the solution. The algorithm for solving the task scheduling problem considered here is based on the branch and bound method. Calculations are performed alternately on a classical computer and a quantum computer. The lower and upper bounds of the criterion function are determined on a quantum computer. Computational experiments were performed on the D-Wave quantum computer. In small examples, the algorithm runs faster and generates significantly fewer solution tree vertices than its counterpart running on a classic computer. For larger examples, the proposed runtime-constrained method, acting as a heuristic, is an interesting alternative to using quantum computing hardware in relation to classical approaches based on silicon computers.
ABSTRACT An essential component of many sophisticated metaheuristics for solving combinatorial optimization problems is some variation of a local search routine that iteratively searches for a better solution within a chosen set of immediate neighbors. The size of this set is limited due to the computational costs required to run the method on classical processing units. We present a qubit‐efficient variational quantum algorithm that implements a quantum version of local search with only qubits and, therefore, can potentially work with classically intractable neighborhood sizes. Increasing the amount of quantum resources employed in the algorithm allows for a larger neighborhood size, improving the quality of obtained solutions. This trade‐off is crucial for present and near‐term quantum devices characterized by a limited number of logical qubits. Numerically simulating our algorithm, we successfully solved the largest graph coloring instance that was tackled by a quantum method. This achievement highlights the algorithm's potential for solving large‐scale combinatorial optimization problems on near‐term quantum devices.
Quantum annealing algorithms were introduced to solve combinatorial optimization problems by taking advantage of quantum fluctuations to escape local minima in complex energy landscapes typical of NP - hard problems. In this work, we propose using quantum annealing for the theory of cuts, a field of paramount importance in theoretical computer science. We have proposed a method to formulate the Minimum Multicut Problem into the QUBO representation, and the technical difficulties faced when embedding and submitting a problem to the quantum annealer processor. We show two constructions of the quadratic unconstrained binary optimization functions for the Minimum Multicut Problem and we review several tradeoffs between the two mappings and provide numerical scaling analysis results from several classical approaches. Furthermore, we discuss some of the expected challenges and tradeoffs in the implementation of our mapping in the current generation of D-Wave machines.
Despite quantum computing is revealing an increasingly promising technology that has the potential to introduce a significant speed-up in many areas of computation, the number of problems that it can represent and solve is currently rather limited. Therefore, one of the current challenges faced by the quantum computing community is to broaden the class of problems that can be tackled. Among these problems, scheduling problems are a class of particularly interesting and hard combinatorial problems; in this paper, we present a novel solution for representing and solving the Flexible Open Shop Scheduling Problem (FOSSP) to optimality by minimizing the makespan. We firstly present a compact formulation of this problem as a Quadratic unconstrained binary optimization (QUBO), which can be used to solve this problem with a quantum annealer. Then, we proceed to the Quantum Approximate Optimization Algorithm (QAOA) problem formulation, thus producing both the cost and mix Hamiltonians related to the problem. From the Hamiltonians, we provide the complete description of the quantum circuit that can be used to tackle the FOSSP within the QAOA framework. This second approach can be used to solve the optimization problem with a general-purpose quantum gate-based hardware.