量子計算(quantum computation)近年來逐漸成為計算機科學的一個重要研究領域，量子的疊加態(superposition)性質讓量子計算擁有超越古典計算的潛在能力，尤其在組合最佳化(combinatorial optimization)這類高複雜度的問題特別明顯，其中在2019年Google首次展現量子霸權(quantum supremacy)是最為顯著的一個里程碑。量子霸權實際驗證了量子電腦能夠進行超越古典電腦的計算，因此吸引更多研究學者投入量子計算與量子演算法的研究。在眾多量子演算法中，格羅弗演算法(Grover′s algorithm)是最著名的量子演算法之一，本篇論文設計出基於格羅弗演算法的量子線路用於求解頂點覆蓋(vertex cover)問題。頂點覆蓋問題屬於NP完全問題，這代表求解該類問題往往要花費指數時間複雜度(exponential time complexity)，而格羅弗演算法能以解決非結構搜尋(unstructured search)問題的方式以O(√(2^(|V|) ))時間複雜度解決|V|個頂點圖的頂點覆蓋問題，這相對於古典窮舉式演算法的O(2^(|V|))時間複雜度具有平方量級的加速。格羅弗演算法的核心是必需針對問題設計出對應的量子神諭(oracle)以標記出給定問題的解答，而設計一個高效的量子神諭為一個具有挑戰性的問題。本論文提出頂點覆蓋問題格羅弗演算法量子神諭線路設計，針對已有的量子計數器(quantum counter)設計進行改良以減少量子邏輯閘的使用數量，量子計數器能確保選取的頂點集合大小滿足頂點覆蓋問題的數量限制；並且提出量子號誌(quantum semaphore)量子線路設計，能夠標記選取頂點所連接的邊，以確認選取的頂點集合是一個頂點覆蓋。本篇論文使用 IBM Q 所提供的開源軟體開發工具包 Qiskit 進行實作，並在 IBM 的量子雲端平台使用量子電腦模擬器驗證演算法的正確性，結果顯示本論文所提演算法確實可求解頂點覆蓋問題。為了更進一步比較實驗結果，所提出的演算法也在屬於雜訊中等規模量子(NISQ)階段的IBMQ mumbai量子電腦上進行實驗，發現因為現階段量子電腦的雜訊(noise)過高會因而影響執行結果成功的機率。最後，本論文分析所提出演算法量子位元與量子邏輯閘使用數量，並與現存的古典演算法進行效能比較，而且針對未來可改進方向給出建議。;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.
