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

IFAC-PapersOnLine

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

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

Published Jan 1, 2025• 1 citation
Publisher

Abstract

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.

DOI
10.1016/j.ifacol.2025.11.834

Related papers

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

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.

Scientific Reports•Aug 17, 2026•0 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•1 citation

Hybrid Quantum Approximate Algorithms for Solving Flow Shop Scheduling Problem

Wojciech Bożejko, Radosław Marcin Idzikowski, Dariusz Jagielski +5 more

There is currently a large gap between the theoretical advantages of quantum computing and the practical use of quantum computers. This is due to the small number of qubits currently available. Rapid technological progress allows us to assume that in the near future, it will be possible to solve problems that are currently a challenge for algorithms running on classical computers. Using the example of an NP-hard flow problem, we present the application of the Qiskit optimization package performed on an IBM quantum computer. This problem is well-studied in classical computing, important for theoretical and practical reasons. The use of quantum optimization will undoubtedly affect the more efficient use of many resources in management, production, logistics, and medicine (duty plans, classification problems, etc.).

IEEE International Symposium on Computational Intelligence and Informatics (CINTI)•Nov 19, 2024•3 citations

Local Search Methods for Quantum Computers

Tad Hogg, Mehmet Fatih Yanik

Local search algorithms use the neighborhood relations among search states and often perform well for a variety of NP-hard combinatorial search problems. This paper shows how quantum computers can also use these neighborhood relations. An example of such a local quantum search is evaluated empirically for the satisfiability (SAT) problem and shown to be particularly effective for highly constrained instances. For problems with an intermediate number of constraints, it is somewhat less effective at exploiting problem structure than incremental quantum methods, in spite of the much smaller search space used by the local method.

arXiv:quant-ph/9802043•Feb 16, 1998•5 citations

Solving various NP-hard problems using exponentially fewer qubits on a quantum computer

Yagnik Chatterjee, Eric Bourreau, Marko J. Rančić

NP-hard problems are not believed to be exactly solvable through general polynomial time algorithms. Hybrid quantum-classical algorithms to address such combinatorial problems have been of great interest in the past few years. Such algorithms are heuristic in nature and aim to obtain an approximate solution. Significant improvements in computational time and/or the ability to treat large problems are some of the principal promises of quantum computing in this regard. The hardware, however, is still in its infancy and the current noisy intermediate-scale quantum (NISQ) computers are not able to optimize industrially relevant problems. Moreover, the storage of qubits and introduction of entanglement require extreme physical conditions. An issue with quantum optimization algorithms such as the quantum approximate optimization algorithm is that they scale linearly with problem size. In this paper, we build upon a proprietary methodology which scales logarithmically with problem size---opening an avenue for treating optimization problems of unprecedented scale on gate-based quantum computers. To test the performance of the algorithm, we first find a way to apply it to a handful of NP-hard problems: Maximum Cut, Minimum Partition, Maximum Clique, Maximum Weighted Independent Set. Subsequently, these algorithms are tested on a quantum simulator with graph sizes of over a hundred nodes and on a real quantum computer up to graph sizes of 256. To our knowledge, these constitute the largest realistic combinatorial optimization problems ever run on a NISQ device, overcoming previous problem sizes by almost tenfold.

arXiv:2301.06978•Physical Review A•May 30, 2024•33 citations

Quantum Local Search with the Quantum Alternating Operator Ansatz

Teague Tomesh, Zain H. Saleem, Martin Suchara

We present a new hybrid, local search algorithm for quantum approximate optimization of constrained combinatorial optimization problems. We focus on the Maximum Independent Set problem and demonstrate the ability of quantum local search to solve large problem instances on quantum devices with few qubits. This hybrid algorithm iteratively finds independent sets over carefully constructed neighborhoods and combines these solutions to obtain a global solution. We study the performance of this algorithm on 3-regular, Community, and Erdős-Rényi graphs with up to 100 nodes.

arXiv:2107.04109•Quantum•Aug 22, 2022•15 citations
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.
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 n2n^2n2 elements. We propose a new, cost-effective method for representing solutions using n−1n-1n−1 element binary sequences. For an n=50n=50n=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.
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.
There is currently a large gap between the theoretical advantages of quantum computing and the practical use of quantum computers. This is due to the small number of qubits currently available. Rapid technological progress allows us to assume that in the near future, it will be possible to solve problems that are currently a challenge for algorithms running on classical computers. Using the example of an NP-hard flow problem, we present the application of the Qiskit optimization package performed on an IBM quantum computer. This problem is well-studied in classical computing, important for theoretical and practical reasons. The use of quantum optimization will undoubtedly affect the more efficient use of many resources in management, production, logistics, and medicine (duty plans, classification problems, etc.).
Local search algorithms use the neighborhood relations among search states and often perform well for a variety of NP-hard combinatorial search problems. This paper shows how quantum computers can also use these neighborhood relations. An example of such a local quantum search is evaluated empirically for the satisfiability (SAT) problem and shown to be particularly effective for highly constrained instances. For problems with an intermediate number of constraints, it is somewhat less effective at exploiting problem structure than incremental quantum methods, in spite of the much smaller search space used by the local method.
NP-hard problems are not believed to be exactly solvable through general polynomial time algorithms. Hybrid quantum-classical algorithms to address such combinatorial problems have been of great interest in the past few years. Such algorithms are heuristic in nature and aim to obtain an approximate solution. Significant improvements in computational time and/or the ability to treat large problems are some of the principal promises of quantum computing in this regard. The hardware, however, is still in its infancy and the current noisy intermediate-scale quantum (NISQ) computers are not able to optimize industrially relevant problems. Moreover, the storage of qubits and introduction of entanglement require extreme physical conditions. An issue with quantum optimization algorithms such as the quantum approximate optimization algorithm is that they scale linearly with problem size. In this paper, we build upon a proprietary methodology which scales logarithmically with problem size---opening an avenue for treating optimization problems of unprecedented scale on gate-based quantum computers. To test the performance of the algorithm, we first find a way to apply it to a handful of NP-hard problems: Maximum Cut, Minimum Partition, Maximum Clique, Maximum Weighted Independent Set. Subsequently, these algorithms are tested on a quantum simulator with graph sizes of over a hundred nodes and on a real quantum computer up to graph sizes of 256. To our knowledge, these constitute the largest realistic combinatorial optimization problems ever run on a NISQ device, overcoming previous problem sizes by almost tenfold.
We present a new hybrid, local search algorithm for quantum approximate optimization of constrained combinatorial optimization problems. We focus on the Maximum Independent Set problem and demonstrate the ability of quantum local search to solve large problem instances on quantum devices with few qubits. This hybrid algorithm iteratively finds independent sets over carefully constructed neighborhoods and combines these solutions to obtain a global solution. We study the performance of this algorithm on 3-regular, Community, and Erdős-Rényi graphs with up to 100 nodes.