Quantum optimization for the graph coloring problem with space-efficient embedding

Current quantum computing devices have varying strengths and weaknesses depending on their architectures. We address this by introducing a novel space-efficient quantum optimization algorithm for the graph coloring problem. While our circuits are deeper than those of the standard approach, the number of required qubits is exponentially reduced in the number of colors.