Quantum Feasibility Labeling for NP-complete Vertex Coloring Problem

Abstract

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.

11 pages, 6 figures, this version of the paper has been accepted by IEEE Access

References in corpus (26)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum Machine Learning
• A variational eigenvalue solver on a quantum processor
• Quantum Mechanics helps in searching for a needle in a haystack
• Quantum algorithm for solving linear systems of equations
• Variational Quantum Algorithms
• Quantum computational advantage using photons
• The theory of variational hybrid quantum-classical algorithms
• Quantum support vector machine for big data classification
• Quantum Circuit Learning
• Quantum Amplitude Amplification and Estimation
• Quantum principal component analysis
• Quantum algorithms: an overview
• The Variational Quantum Eigensolver: a review of methods and best practices
• Exponential algorithmic speedup by quantum walk
• Quantum optimization using variational algorithms on near-term quantum devices
• Variational ansatz-based quantum simulation of imaginary time evolution
• Quantum circuits with many photons on a programmable nanophotonic chip
• Quantum Data Fitting
• A four-qubit germanium quantum processor
• Layerwise learning for quantum neural networks
• Towards Quantum Machine Learning with Tensor Networks
• Preconditioned quantum linear system algorithm
• Variational Quantum Linear Solver
• Theory of analytical energy derivatives for the variational quantum eigensolver
• Unimon qubit