Preprint on quantum algorithm for list coloring published on arXiv

To everyone that had been following my earlier blog posts (part 1 and part 2) on the 3-coloring problem, we have published our results for its most general version on arXiv. Feel free to give the preprint a read at: https://arxiv.org/pdf/2108.09061.pdf!


The preprint extends the circuit we described in the previous posts to the most general problem of list coloring. In list coloring we are given a graph G=(V,E) along with a list L(v) for every vertex v of G. When L(v) = {1, 2, ... , k} for every vertex v, the list coloring problem reduces to the renowned k-coloring problem!


It would be interesting to figure out if we can find better algorithms for specific instances of the list coloring problem, such as k-coloring.


We're now exploring the usage of quantum computing in machine learning/data science and computer graphics, so stay tuned for updates!

Sayan Mukherjee
Comments
Sayan Mukherjee
Related posts

blueqat Inc.

Shibuya Scramble Square 39F 2-24-12, Shibuya, Shibuya-ku, Tokyo
Contact: info@blueqat.com