| dc.description.abstract | Quantum computation has gradually become an important research field in computer science in recent years. The property of quantum superposition gives quantum computation the potential to surpass classical computation, especially in complex problems like combinatorial optimization. In 2019, Google demonstrated quantum supremacy for the first time, which was a significant milestone. Quantum supremacy validated that quantum computers can perform computations beyond the capabilities of classical computers, attracting more researchers to delve into quantum computation and quantum algorithms. Among numerous quantum algorithms, Grover’s algorithm is one of the most famous. This paper designs a quantum circuit based on Grover′s algorithm to solve the vertex cover problem. The vertex cover problem belongs to the class of NP-complete problems, which implies that solving such problems often requires exponential time complexity. However, Grover’s algorithm provides a quadratic speedup by solving the vertex cover problem for a graph with |V| vertices using O(√(2^(|V|) )) time complexity, compared to the exponential time complexity O(2^(|V|)) of classical exhaustive search algorithms. The core of Grover′s algorithm lies in designing the corresponding quantum oracle to mark the solutions to a given problem, which poses a challenging task to design an efficient quantum oracle. This paper proposes a quantum oracle circuit design for the vertex cover problem in Grover′s algorithm. It improves the design of existing quantum counters to reduce the usage of quantum logic gates. The quantum counter ensures that the size of the selected vertex set satisfies the quantity restriction of the vertex cover problem. Additionally, a quantum semaphore circuit design is introduced, which can mark the edges connected to the selected vertices to confirm whether the selected vertex set forms a vertex cover. The implementation of the proposed methods in this paper is carried out using the open-source software development toolkit Qiskit provided by IBM Q. The correctness of the algorithm is verified through simulations on IBM′s quantum cloud platform using a quantum computer simulator. The results demonstrate that the proposed algorithm can indeed solve the vertex cover problem. To further compare the experimental results, the proposed algorithm is also tested on IBM′s NISQ quantum computer, called IBMQ mumbai. However, it is observed that the high noise level in current quantum computers can affect the success probability of execution results. Finally, this paper analyzes the usage of quantum bits and quantum logic gates in the proposed algorithm and compares its performance with existing classical algorithms. It also provides suggestions for future improvement directions. | en_US |