Quantum Feasibility Labeling for NP-complete Vertex Coloring Problem
Many important science and engineering problems can be converted into
NP-complete problems which are of significant importance in computer science
and mathematics. Currently, neither existing classical nor quantum algorithms
can solve these problems in polynomial time. To address this difficulty, this
paper proposes a quantum feasibility labeling (QFL) algorithm to label all
possible solutions to the vertex coloring problem, which is a well-known
NP-complete problem. The QFL algorithm converts the vertex coloring problem
into the problem of searching an unstructured database where good and bad
elements are labeled. The recently proposed variational quantum search (VQS)
algorithm was demonstrated to achieve an exponential speedup, in circuit depth,
up to 26 qubits in finding good element(s) from an unstructured database. Using
the labels and the associated possible solutions as input, the VQS can find all
feasible solutions to the vertex coloring problem. The number of qubits and the
circuit depth required by the QFL each is a polynomial function of the number
of vertices, the number of edges, and the number of colors of a vertex coloring
problem. We have implemented the QFL on an IBM Qiskit simulator to solve a
4-colorable 4-vertex 3-edge coloring problem.
Junpeng Zhan