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

International Journal of Bio-Inspired Computation

Quantum inspired cuckoo search algorithm for graph colouring problem

Halima Djelloul, Abdesslem Layeb, Salim Chıkhı

Published Jan 1, 2015• 17 citations
Publisher

Abstract

The graph colouring problem (GCP) is one of the most interesting, studied and difficult combinatorial optimisation problems. That is why, several approaches were developed for solving this problem, including exact approaches, heuristic approaches, metaheuristics and hybrid approaches. In this paper, we try to solve the graph colouring problem using a new approach based on the quantum inspired cuckoo search algorithm. The first contribution consists in defining an appropriate quantum representation based on qubit representation to represent the graph colouring solutions. The second contribution is the proposition of a novel measure operator based on the adjacency matrix. The third contribution involves the proposition of an adapted hybrid quantum mutation operation. To show the feasibility and the effectiveness of the algorithm, we have used the standard DIMACS benchmark, and the obtained results are very encouraging.

DOI
10.1504/ijbic.2015.069554

Related papers

Quantum-Inspired Evolutionary Algorithm to Solve Graph Coloring Problem

Mozammel H. A. Khan

Graph Coloring Problem (GCP) bears an enormous significance to the researchers in the field of soft computing. In this paper, we demonstrate a Quantum-Inspired Evolutionary Algorithm (QEA) to solve GCP. We use two dimensional arrays of Q-bits called Q-bit individual to produce binary individual. Q-gate operation is applied as a variation operator on Q-bit individuals. In traditional evolutionary algorithm (EA) for GCP, k-coloring approach is used and the EA is run several times for decreasing value of k until lowest possible k is reached. In our QEA, we start with the number of colors equal to the theoretical upper bound of the chromatic number, which is maximum out-degree + 1, and during evolution some colors are made unused to reduce the number of color in each generation. As a result, solution is found in a single run. We test 36 datasets from DIMACS benchmark and compare the result with several recent works. For five datasets, our algorithm obtains better solution than other. Keywords—quantum-inspired evolutionary algorithm (QEA), graph coloring problem (GCP), combinatorial optimization, Qbit representation, Q-gate.

•Jan 1, 2014•4 citations

A Novel Quantum Inspired Cuckoo Search Algorithm for Bin Packing Problem

Abdesslem Layeb, Seriel Rayene Boussalia

The Bin Packing Problem (BPP) is one of the most known combinatorial optimization problems.This problem consists to pack a set of items into a minimum number of bins.There are several variants of this problem; the most basic problem is the onedimensional bin packing problem (1-BPP).In this paper, we present a new approach based on the quantum inspired cuckoo search algorithm to deal with the 1-BPP problem.The contribution consists in defining an appropriate quantum representation based on qubit representation to represent bin packing solutions.The second contribution is proposition of a new hybrid quantum measure operation which uses first fit heuristic to pack no filled objects by the standard measure operation.The obtained results are very encouraging and show the feasibility and effectiveness of the proposed approach.

International Journal of Information Technology and Computer Science•May 2, 2012•59 citations

Qudit-inspired optimization for graph coloring

David Jansen, Timothy Heightman, Luke Mortimer +2 more

We introduce a quantum-inspired algorithm for graph coloring problems (GCPs) that utilizes qudits in a product state, with each qudit representing a node in the graph and parameterized by $d$-dimensional spherical coordinates. We propose and benchmark two optimization strategies: qudit gradient descent, initiating qudits in random states and employing gradient descent to minimize a cost function; and qudit local quantum annealing, which adapts the local quantum annealing method to optimize an adiabatic transition from a tractable initial function to a problem-specific cost function. Our approaches are benchmarked against established solutions for standard GCPs, showing that our methods not only rival but frequently surpass the performance of recent state-of-the-art algorithms in terms of solution quality and computational efficiency. The adaptability of our algorithm and its high-quality solutions, achieved with minimal computational resources, point to an advancement in the field of quantum-inspired optimization, with potential applications extending to a broad spectrum of optimization problems.

arXiv:2406.00792•Physical Review Applied•Dec 2, 2024•11 citations

Optimization by quantum annealing for the graph colouring problem

Olawale Titiloye

Quantum annealing is the quantum equivalent of the well known classical simulated annealing algorithm for combinatorial optimization problems. Despite the appeal of the approach, quantum annealing algorithms competitive with the state of the art for specific problems hardly exist in the literature. Graph colouring is a difficult problem of practical significance that can be formulated as combinatorial optimization. By introducing a symmetry-breaking problem representation, and finding fast incremental techniques to calculate energy changes, a competitive graph colouring algorithm based on quantum annealing is derived. This algorithm is further enhanced by tuning simplification techniques; replica spacing techniques to increase robustness; and a messaging protocol, which enables quantum annealing to efficiently take advantage of multiprocessor environments. Additionally, observations of some patterns in the tuning for random graphs led to a more effective algorithm able to find new upper bounds for several widely-used benchmark graphs, some of which had resisted improvement in the last two decades.

•May 27, 2026•0 citations

A novel quantum inspired cuckoo search for knapsack problems

Abdesslem Layeb

This paper presents a new inspired algorithm called quantum inspired cuckoo search algorithm (QICSA). This one is a new framework relying on quantum computing principles and cuckoo search algorithm. The contribution consists in defining an appropriate representation scheme in the cuckoo search algorithm that allows applying successfully on combinatorial optimisation problems some quantum computing principles like qubit representation, superposition of states, measurement, and interference. This hybridisation between quantum inspired computing and bioinspired computing has led to an efficient hybrid framework which achieves better balance between exploration and exploitation capabilities of the search process. Experiments on knapsack problems show the effectiveness of the proposed framework and its ability to achieve good quality solutions.

International Journal of Bio-Inspired Computation•Jan 1, 2011•185 citations

A novel greedy quantum inspired cuckoo search algorithm for variable sized bin packing problem

Abdesslem Layeb, Seriel Rayene Boussalia

Bin packing is a well-known NP-hard optimisation problem which has several real applications. Classical bin packing (BPP) is a simple model where all bins are identical. However, the variable sized bin packing problem (VSBPP) is a generalisation of the bin packing problem where bins of different capacities are available for packing a set of items having different weights. The objective is to pack all the items in the bins minimising the sum of the remaining spaces of the used bins. In this paper, we present a new approach based on the quantum inspired cuckoo search algorithm to deal with the variable sized bin packing problem (VSBPP) problem. The contribution consists in defining an appropriate quantum representation based on qubit representation to represent bin packing solutions. The second contribution is a proposition of a new hybrid quantum measure operation which uses first fit heuristic to pack no filled objects by the standard measure operation. The third contribution is the use of a new hybrid randomised heuristic based on both first fit and best heuristics. The obtained results are very encouraging and show the feasibility and effectiveness of the proposed approach.

International Journal of Mathematics in Operational Research•Jan 1, 2014•3 citations
The graph colouring problem (GCP) is one of the most interesting, studied and difficult combinatorial optimisation problems. That is why, several approaches were developed for solving this problem, including exact approaches, heuristic approaches, metaheuristics and hybrid approaches. In this paper, we try to solve the graph colouring problem using a new approach based on the quantum inspired cuckoo search algorithm. The first contribution consists in defining an appropriate quantum representation based on qubit representation to represent the graph colouring solutions. The second contribution is the proposition of a novel measure operator based on the adjacency matrix. The third contribution involves the proposition of an adapted hybrid quantum mutation operation. To show the feasibility and the effectiveness of the algorithm, we have used the standard DIMACS benchmark, and the obtained results are very encouraging.
Graph Coloring Problem (GCP) bears an enormous significance to the researchers in the field of soft computing. In this paper, we demonstrate a Quantum-Inspired Evolutionary Algorithm (QEA) to solve GCP. We use two dimensional arrays of Q-bits called Q-bit individual to produce binary individual. Q-gate operation is applied as a variation operator on Q-bit individuals. In traditional evolutionary algorithm (EA) for GCP, k-coloring approach is used and the EA is run several times for decreasing value of k until lowest possible k is reached. In our QEA, we start with the number of colors equal to the theoretical upper bound of the chromatic number, which is maximum out-degree + 1, and during evolution some colors are made unused to reduce the number of color in each generation. As a result, solution is found in a single run. We test 36 datasets from DIMACS benchmark and compare the result with several recent works. For five datasets, our algorithm obtains better solution than other. Keywords—quantum-inspired evolutionary algorithm (QEA), graph coloring problem (GCP), combinatorial optimization, Qbit representation, Q-gate.
The Bin Packing Problem (BPP) is one of the most known combinatorial optimization problems.This problem consists to pack a set of items into a minimum number of bins.There are several variants of this problem; the most basic problem is the onedimensional bin packing problem (1-BPP).In this paper, we present a new approach based on the quantum inspired cuckoo search algorithm to deal with the 1-BPP problem.The contribution consists in defining an appropriate quantum representation based on qubit representation to represent bin packing solutions.The second contribution is proposition of a new hybrid quantum measure operation which uses first fit heuristic to pack no filled objects by the standard measure operation.The obtained results are very encouraging and show the feasibility and effectiveness of the proposed approach.
We introduce a quantum-inspired algorithm for graph coloring problems (GCPs) that utilizes qudits in a product state, with each qudit representing a node in the graph and parameterized by ddd-dimensional spherical coordinates. We propose and benchmark two optimization strategies: qudit gradient descent, initiating qudits in random states and employing gradient descent to minimize a cost function; and qudit local quantum annealing, which adapts the local quantum annealing method to optimize an adiabatic transition from a tractable initial function to a problem-specific cost function. Our approaches are benchmarked against established solutions for standard GCPs, showing that our methods not only rival but frequently surpass the performance of recent state-of-the-art algorithms in terms of solution quality and computational efficiency. The adaptability of our algorithm and its high-quality solutions, achieved with minimal computational resources, point to an advancement in the field of quantum-inspired optimization, with potential applications extending to a broad spectrum of optimization problems.
Quantum annealing is the quantum equivalent of the well known classical simulated annealing algorithm for combinatorial optimization problems. Despite the appeal of the approach, quantum annealing algorithms competitive with the state of the art for specific problems hardly exist in the literature. Graph colouring is a difficult problem of practical significance that can be formulated as combinatorial optimization. By introducing a symmetry-breaking problem representation, and finding fast incremental techniques to calculate energy changes, a competitive graph colouring algorithm based on quantum annealing is derived. This algorithm is further enhanced by tuning simplification techniques; replica spacing techniques to increase robustness; and a messaging protocol, which enables quantum annealing to efficiently take advantage of multiprocessor environments. Additionally, observations of some patterns in the tuning for random graphs led to a more effective algorithm able to find new upper bounds for several widely-used benchmark graphs, some of which had resisted improvement in the last two decades.
This paper presents a new inspired algorithm called quantum inspired cuckoo search algorithm (QICSA). This one is a new framework relying on quantum computing principles and cuckoo search algorithm. The contribution consists in defining an appropriate representation scheme in the cuckoo search algorithm that allows applying successfully on combinatorial optimisation problems some quantum computing principles like qubit representation, superposition of states, measurement, and interference. This hybridisation between quantum inspired computing and bioinspired computing has led to an efficient hybrid framework which achieves better balance between exploration and exploitation capabilities of the search process. Experiments on knapsack problems show the effectiveness of the proposed framework and its ability to achieve good quality solutions.
Bin packing is a well-known NP-hard optimisation problem which has several real applications. Classical bin packing (BPP) is a simple model where all bins are identical. However, the variable sized bin packing problem (VSBPP) is a generalisation of the bin packing problem where bins of different capacities are available for packing a set of items having different weights. The objective is to pack all the items in the bins minimising the sum of the remaining spaces of the used bins. In this paper, we present a new approach based on the quantum inspired cuckoo search algorithm to deal with the variable sized bin packing problem (VSBPP) problem. The contribution consists in defining an appropriate quantum representation based on qubit representation to represent bin packing solutions. The second contribution is a proposition of a new hybrid quantum measure operation which uses first fit heuristic to pack no filled objects by the standard measure operation. The third contribution is the use of a new hybrid randomised heuristic based on both first fit and best heuristics. The obtained results are very encouraging and show the feasibility and effectiveness of the proposed approach.