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

CRC Press eBooks

Encoding

Maurice Clerc

Published Nov 22, 2024• 0 citations
Publisher

Abstract

Before delving into the study of algorithms for finding an optimal coloring, it is necessary to mathematically formalize the problem. Specifically, one must define codes to represent the entities involved: the graphs, with their arcs and nodes, and the colorings. By using such codes, it will be possible to write computer programs to solve the problem. Several methods are explained, even though not all of them will be used later on. Emphasis is placed on binary encodings because they are most suitable for the quantum algorithm that will be discussed later.

DOI
10.1201/9781003477785-3

Related papers

A Quantum Method

Maurice Clerc

Fundamentals of quantum computing are first introduced, specifically those necessary to understand the detailed algorithm later on, including classical concepts such as qubits, Poincaré-Bloch sphere, quantum gates, circuits, superposition, entanglement, and measurement. Once binary encodings have been performed (see Chapter 3) and with these elements, it is then relatively easy to design a quantum algorithm for searching for an optimal coloring. One such algorithm, the NK method, is detailed, based on the generation of so-called W quantum states, complemented by Grover's amplification-diffusion technique. In the absence of a real quantum computer, examples are treated through simulations coded in Qiskit language, with explicit representations of the constructed quantum circuits. They are necessarily of small size, but since the algorithm's complexity in terms of the number of nodes and colors is polynomial of low degree, it can, in principle, handle less trivial problems.

CRC Press eBooks•Nov 22, 2024•0 citations

Hierarchical quantum approximation optimization algorithm for solving graph-coloring problems

刘冬梅 Liu Dongmei, Jian Li, XIUBO CHEN +3 more

Physical Review A•Jan 26, 2026•0 citations

A quantum–classical approach to solve the graph coloring problem with minimum colors

Prem Shanker Dwivedi, Abhinav Kumar, Amit Biswas +1 more

Abstract Graph coloring with minimum colors is a well-known NP-complete problem in computer science and mathematics, having diverse real-life applications such as scheduling, register allocation, and frequency assignment. However, a classical computer requires exponential time to solve the graph coloring problem with the minimum number of colors. Therefore, classical approaches become infeasible for solving this problem on large graphs. In contrast, quantum computing offers the potential for speedup on specific problems, although solutions are typically obtained with a certain probability of correctness. This work proposes a quantum–classical method for solving the graph coloring problem and finding the chromatic number of a graph with guaranteed correctness, and also reduces the time and qubit complexities. The proposed method is inspired by Randomized Grover’s search algorithm, and the classical binary search algorithm. Here, Randomized Grover’s search algorithm provides quadratic speedup and this algorithm is useful in real situations when the number of solutions is not known in advance in contrast to the Grover’s search algorithm. The binary search algorithm helps to achieve logarithmic speedup, which reduces overall complexity. The experimental results strongly validate our claims and demonstrate the superiority of the approach. Furthermore, a comprehensive mathematical analysis is carried out to examine its complexities, as well as to compare its computational efficiency with existing methods.

Physica Scripta•Oct 9, 2026•0 citations

Optimal binary codes and binary construction of quantum codes

Weiliang Wang, Yangyu Fan, Ruihu Li

Frontiers of Computer Science•Oct 22, 2014•4 citations

Optimal binary codes and binary construction of quantum codes

Weiliang, Wang, Yangyu +3 more

Frontiers of Computer Science•Jan 1, 2014•1 citation

Encodings of the weighted MAX k-CUT problem on qubit systems

Franz Georg Fuchs, Ruben Pariente Bassa, Frida Lien

The weighted MAX k -CUT problem involves partitioning a weighted undirected graph into k subsets, or colors, to maximize the sum of the weights of edges between vertices in different subsets. This problem has significant applications across multiple domains. This study explores encoding methods for MAX k -CUT on qubit systems by utilizing quantum approximate optimization algorithms (QAOA) and addressing the challenge of encoding integer values on quantum devices with binary variables. We examine various encoding schemes and evaluate the efficiency of these approaches. The study presents a systematic and resource-efficient method to implement the phase separation operator for the cost function of the MAX k -CUT problem. When encoding the problem into the full Hilbert space, we show the importance of encoding the colors in a balanced way. We also explore the option of encoding the problem into a suitable subspace by designing suitable state preparations and constrained mixers (LX- and Grover-mixer). Numerical simulations on weighted and unweighted graph instances demonstrate the effectiveness of these encoding schemes, particularly in optimizing circuit depth, approximation ratios, and computational efficiency.

arXiv:2411.08594•Frontiers in Quantum Science and Technology•Dec 4, 2025•0 citations
Before delving into the study of algorithms for finding an optimal coloring, it is necessary to mathematically formalize the problem. Specifically, one must define codes to represent the entities involved: the graphs, with their arcs and nodes, and the colorings. By using such codes, it will be possible to write computer programs to solve the problem. Several methods are explained, even though not all of them will be used later on. Emphasis is placed on binary encodings because they are most suitable for the quantum algorithm that will be discussed later.
Fundamentals of quantum computing are first introduced, specifically those necessary to understand the detailed algorithm later on, including classical concepts such as qubits, Poincaré-Bloch sphere, quantum gates, circuits, superposition, entanglement, and measurement. Once binary encodings have been performed (see Chapter 3) and with these elements, it is then relatively easy to design a quantum algorithm for searching for an optimal coloring. One such algorithm, the NK method, is detailed, based on the generation of so-called W quantum states, complemented by Grover's amplification-diffusion technique. In the absence of a real quantum computer, examples are treated through simulations coded in Qiskit language, with explicit representations of the constructed quantum circuits. They are necessarily of small size, but since the algorithm's complexity in terms of the number of nodes and colors is polynomial of low degree, it can, in principle, handle less trivial problems.
Abstract Graph coloring with minimum colors is a well-known NP-complete problem in computer science and mathematics, having diverse real-life applications such as scheduling, register allocation, and frequency assignment. However, a classical computer requires exponential time to solve the graph coloring problem with the minimum number of colors. Therefore, classical approaches become infeasible for solving this problem on large graphs. In contrast, quantum computing offers the potential for speedup on specific problems, although solutions are typically obtained with a certain probability of correctness. This work proposes a quantum–classical method for solving the graph coloring problem and finding the chromatic number of a graph with guaranteed correctness, and also reduces the time and qubit complexities. The proposed method is inspired by Randomized Grover’s search algorithm, and the classical binary search algorithm. Here, Randomized Grover’s search algorithm provides quadratic speedup and this algorithm is useful in real situations when the number of solutions is not known in advance in contrast to the Grover’s search algorithm. The binary search algorithm helps to achieve logarithmic speedup, which reduces overall complexity. The experimental results strongly validate our claims and demonstrate the superiority of the approach. Furthermore, a comprehensive mathematical analysis is carried out to examine its complexities, as well as to compare its computational efficiency with existing methods.
The weighted MAX k -CUT problem involves partitioning a weighted undirected graph into k subsets, or colors, to maximize the sum of the weights of edges between vertices in different subsets. This problem has significant applications across multiple domains. This study explores encoding methods for MAX k -CUT on qubit systems by utilizing quantum approximate optimization algorithms (QAOA) and addressing the challenge of encoding integer values on quantum devices with binary variables. We examine various encoding schemes and evaluate the efficiency of these approaches. The study presents a systematic and resource-efficient method to implement the phase separation operator for the cost function of the MAX k -CUT problem. When encoding the problem into the full Hilbert space, we show the importance of encoding the colors in a balanced way. We also explore the option of encoding the problem into a suitable subspace by designing suitable state preparations and constrained mixers (LX- and Grover-mixer). Numerical simulations on weighted and unweighted graph instances demonstrate the effectiveness of these encoding schemes, particularly in optimizing circuit depth, approximation ratios, and computational efficiency.