使用格羅弗演算法解決漢米爾頓循環問題;Solving Hamiltonian Cycle Problem with Grover′s Algorithm

NCUIR > College of Electrical Engineering & Computer Science > Graduate Institute of Computer Science and Information Engineering > Electronic Thesis & Dissertation > Item 987654321/93246

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/93246

Title:	使用格羅弗演算法解決漢米爾頓循環問題;Solving Hamiltonian Cycle Problem with Grover′s Algorithm
Authors:	高子豪;Kao, Tzu-Hao
Contributors:	資訊工程學系
Keywords:	格羅弗演算法;漢米爾頓循環問題;神諭;量子線路;量子電腦;量子計數器;Grover′s algorithm;hamiltonian cycle;oracle;quantum circuit;quantum computer;quantum counter
Date:	2023-07-25
Issue Date:	2024-09-19 16:50:34 (UTC+8)
Publisher:	國立中央大學
Abstract:	漢米爾頓循環(Hamiltonian Cycle)問題一直以來都是一個引人關注的難題，因為它具有廣泛的應用，例如 : 公車路線規劃和基因作圖(gene mapping)等等。在許多領域中，尋找漢米爾頓循環或漢米爾頓路徑的解答都具有重要性，然而，漢米爾頓循環問題屬於NP困難(NP-hard)問題，意味著在傳統的古典演算法中解決此問題需要龐大的時間和空間複雜度。隨著量子電腦的崛起，格羅弗演算法(Grover′s algorithm)的出現為解決漢米爾頓循環問題提供了新的可能性。因為格羅弗演算法在解決非結構搜尋(unstructured search)問題時相較於古典窮舉演算法具有平方量級的加速，因而引發本論文利用格羅弗演算法解決漢米爾頓循環問題的動機。本論文旨在提出更高效且節省量子位元的量子線路，以使用格羅弗演算法解決任意圖的漢米爾頓循環問題。所提出的量子線路使用三個依照漢米爾頓循環限制而建立的格羅弗演算法神諭(oracle)將正確的解標記為負相位，然後使用相位增幅器(diffuser)提高正確解的測量機率，並透過量子計數(quantum counting)演算法估計出的神諭迭代次數來迭代神諭以求出漢米爾頓循環問題的解答。為了驗證量子線路的正確性，透過IBM量子電腦模擬器及ibmq_mumbai 量子電腦來模擬執行或執行量子線路。本論文比較了所提出的量子線路在不同轉譯(transpiling)最佳化等級及佈局方式在量子電腦中執行的優劣，接著與幾個解決漢米爾頓循環問題的古典演算法進行比較。比較結果顯示所提出的方法只需較少的量子位元就可以達到與古典演算法相近的時間複雜度。 ;Hamiltonian cycle problem has long been a challenging and intriguing problem due to its wide range of applications, such as bus route planning and gene mapping. Finding solutions to hamiltonian cycles or paths is of great importance in various fields. However, hamiltonian cycle problem belongs to the class of NP-hard problems, which means that solving it using traditional classical algorithms requires significant time and space complexity. With the rise of quantum computers, the emergence of Grover′s algorithm has provided new possibilities for solving hamiltonian cycle problem. Grover′s algorithm offers a quadratic speedup compared to classical brute-force algorithms in solving unstructured search problems, which has motivated this paper to explore the application of Grover′s algorithm to tackle the Hamiltonian cycle problem. In this paper, we propose a more efficient and resource-saving quantum circuit for solving the Hamiltonian cycle problem of arbitrary graphs using Grover′s algorithm. The proposed quantum circuit utilizes three Grover’s algorithm oracles based on Hamiltonian cycle constraints to mark the correct solution with a negative phase, and then uses a phase amplifier (diffuser) to increase the measurement probability of the correct solution. The proposed approach further utilizes the quantum counting algorithm to estimate the number of iterations required for the oracle, in order to find the solution to the Hamiltonian cycle problem. To validate the correctness of the quantum circuit, simulations or executions are conducted using the IBM quantum computer simulator and ibmq_mumbai quantum computer.Furthermore, this paper compares the performance of the proposed quantum circuit when transpiling at different optimization levels and layout methods on quantum computers, and then compares it with several classical algorithms for solving hamiltonian cycle problem. The comparison results demonstrate that the proposed method achieves a comparable time complexity to classical algorithms with fewer quantum bits required.
Appears in Collections:	[Graduate Institute of Computer Science and Information Engineering] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	17	View/Open

社群 sharing

Loading...