A Resource-Efficient Quantum Framework for Graph Coloring and Chromatic Number Estimation

Research Question and Approach

Graph coloring is a classic NP-hard problem with significant industrial applications, such as logistics, scheduling, and frequency allocation. Traditional classical algorithms struggle with large-scale instances, and standard quantum approaches (like QUBO formulations) often require a large number of qubits (scaling linearly with both vertices and colors). This paper proposes a more efficient quantum encoding that maps colors to the states of log2(η) qubits, significantly reducing the required hardware resources. To solve for the chromatic number (the minimum number of colors needed), the authors introduce a custom mixer Hamiltonian that operates exclusively within the feasible Hilbert space, alongside a single-vertex penalty term that suppresses configurations using excess colors.

The researchers demonstrate that their memory-efficient encoding, combined with the novel mixer Hamiltonian, effectively identifies the chromatic number for various graph structures. By restricting the mixer to the feasible subspace, the algorithm avoids the performance degradation typically caused by indiscriminately mixing valid and invalid color assignments. Numerical simulations using Qiskit show that this approach consistently yields the correct chromatic number for test graphs, outperforming standard X-mixer implementations in scenarios where the number of colors is not a power of two. The authors also outline how to extend this framework to include additional industrial constraints, such as weight capacity limits in truck loading problems, by incorporating slack variables.

This work provides a scalable pathway for applying quantum computing to complex combinatorial optimization problems. By reducing the qubit overhead and improving the success probability of the Quantum Adiabatic Algorithm (QAA), the framework makes it more feasible to address real-world scheduling and routing challenges on near-term quantum hardware. The ability to directly estimate the chromatic number—rather than just checking for feasibility with a fixed number of colors—is particularly valuable for resource-constrained industrial operations.