Analyzing, Fixing and Optimizing a Space-Efficient Quantum Circuit for the Graph K-Coloring Problem

K-Coloring is a widely studied problem with both profound theoretical implications and practical applications. Its implementation with quantum means is significant because it can serve as a forerunner for a broad category of related subproblems, further enlarging the already available portfolio of quantum algorithms. In order to go beyond the state of the art we propose three different variants of a state of the art algorithm to account for the trade-off between the width and the depth of the circuit, taken as cost metrics. In particular, the third solution significantly improves the literature's best asymptotic complexity, calculated as the product of the circuit's width and depth, moving from O(N{3} N) to O(N{2} N), where N is the number of nodes in the considered graph.