Quantum Algorithms of the Vertex Cover Problem on a Quantum Computer
Weng-Long Chang, Ting-Ting Ren, Mang Feng, Shu-Chien Huang, Lai Chin Lu, Kawuu W. Lin, Minyi Guo · 2009
In this paper, it is demonstrated that solving an instance of the vertex cover problem of any graph G with m edges and n vertices can be implemented by Hadamard gates, NOT gates, CNOT gates, CCNOT gates, Grover's operators, and quantum measurements on a quantum computer. To test our theory, an NMR (nuclear magnetic resonance) experiment for the simplest vertex-cover problem is also performed.