請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/91710
標題: | 利用量子虛數時間演化演算法求解漢米頓路徑問題 Using the Quantum Imaginary Time Evolution Algorithm to Solve Hamilton Cycle Problems |
作者: | 歐政富 Cheng-Fu Ou |
指導教授: | 管希聖 Hsi-Hseng Goan |
關鍵字: | 漢米頓路徑問題,絕熱定理,二次無約束二元優化,路徑積分法,量子虛數時間演化,量子近似優化算法, Hamilton Cycle Problem,Adiabatic Theorem,Quadratic Unconstrained Binary Optimization,Path Integral Formulation,Quantum Imaginary Time Evolution,Quantum Approximate Optimization Algorithm, |
出版年 : | 2024 |
學位: | 碩士 |
摘要: | 本論文的研究目的在於使用量子虛數時間演化(Quantum Imaginary Time Evolution)尋找漢米頓路徑問題(Hamilton Cycle Problem)的全新解法。論文中探討的解法是將欲解決的問題表示為二次無約束二元優化(Quadratic Unconstrained Binary Optimization)的形式,再轉換成易辛模型(Ising Model)。傳統的優化方法例如最陡下降法(Method of Steepest Descent)難以近似目標函數(Objective Function)的全域極值(Global Minimum);但使用易辛模型(Ising Model)在量子計算機上進行近似時,相對應的量子力學演算模型允許量子穿隧(Quantum Tunneling),可以避免運算時目標函數值在局部最大值(Local Maximum)與局部最小值(Local Minimum)之間來回振盪,取得較佳近似結果。再者,絕熱定理(Adiabatic Theorem)可以證明量子退火與其衍生的近似方法具有收斂性,並能夠計算收斂條件(Convergence Condition)。為了取得易辛模型(Ising Model)的最佳解,本論文採用路徑積分法(Path Integral Formulation)計算對應物理系統的基態(Ground State)與時間演化(Time Evolution)。據已知可以透過數學證明路徑積分法(Path Integral Formulation)與費曼-卡茨公式(Feynman-Kac Formula)相等,即可使用多變數黎曼積分(Multivariate Riemann Integral)計算系統狀態。從以上的推論與其他參考資料得知,量子虛數時間演化(Quantum Imaginary Time Evolution)可以在量子線路(Quantum Circuit)上實現費曼-卡茨公式(Feynman-Kac Formula)的數值近似。本論文採解釋並推導量子虛數時間演化(Quantum Imaginary Time Evolution)的演算過程,大致上分為哈密頓量(Hamiltonian)的分解與對應的量子邏輯閘(Quantum Logic Gate)參數計算。其次,本論文以比較此方法與現在相關領域最熱門的兩種方法包括量子近似優化算法(Quantum Approximate Optimization Algorithm)與變分量子特徵值求解算法(Variational Quantum Eigensolver)之間的優劣,並分析它們數值解之間的差異。除此之外,本論文亦分析二次無約束二元優化(Quadratic Unconstrained Binary Optimization)的時間複雜度(Time Complexity),其證明方法是透過將此類優化問題轉換為零一整數線性問題(0-1 Integer Linear Problem),並嘗試計算該類問題在確定型圖靈機(Deterministic Turing Machine)中需要的計算步驟數,藉此估算時間複雜度。欲證明以上論證的有效性,我會採用IBM Qiskit作為數值計算的模組平台,模擬量子近似優化算法(Quantum Approximate Optimization Algorithm)與量子虛數時間演化(Quantum Imaginary Time Evolution)的數值計算,代入本論文欲解決的問題,以求得最小特徵值(Minimum Energy Eigenvalue)進行比較,藉以研究預期量子虛數時間演化(Quantum Imaginary Time Evolution)能夠在量子計算機上以更快速度解決漢米頓路徑問題(Hamilton Cycle Problem)。除此之外,同時本論文會採用PyQUBO與相關程式碼進行模擬退火 (Simulated Annealing)演算法求解本論文欲解決的問題,據以證實本論文的最小特徵值算法能發揮效用,並使量子近似優化算法(Quantum Approximate Optimization Algorithm)與量子虛數時間演化(Quantum Imaginary Time Evolution)的數值計算結果更具說服力。其中快速求解漢米頓路徑問題有許多實際的應用,並能衍生出解決其他問題的方法,包括解決旅行推銷員問題(Traveling Salesman Problem)、布林可滿足性問題(Boolean Satisfiability Problem)與頂點覆蓋問題(Vertex Covering Problem)。同時漢米頓路徑問題的快速解法可以套用到這些組合優化問題(Combinatorial Optimization Problems)的演算上,提供比傳統演算法更好的解答。 This thesis aims to obtain solutions for Hamilton cycle problems by a novel method of quantum imaginary time evolution (QITE). The main approach is to formulate the problem into a quadratic unconstrained binary optimization (QUBO) form and then to convert it into the Ising Model Hamiltonian. It is hard for classical algorithms, such as method of steepest descent, to reach the global minimum of the cost (penalty) function; however, the optimization of Ising model on a quantum machine allows the quantum tunneling of the states, which could avoid the barrier of high energy states between local minima and the global minimum of the system and reach a better solution. Based on the mathematical description of the adiabatic theorem, we are able to determine the convergence condition of quantum annealing. Then we can use path integral formulation of Schrödinger equation to solve the eigenstate of the system, including the time evolution. The path integral formulation can be proved to establish an equivalence relation with the Feynman-Kac formula, and be calculated by the multivariable Riemann Integral. From this deduction, the numerical calculation of the Feynman-Kac type formalism can be achieved by QITE. First, we will describe the processes of QITE by decomposing system Hamiltonian, and illustrate a way to calculate parameters for quantum gates associating to the decomposed terms of Hamiltonian. Then we will compare QITE with other popular hybrid classical-quantum algorithms such as Monte Carlo integration, quantum approximate optimization algorithm (QAOA) and variational quantum eigensolver (VQE), and describe the differences of these methods on obtaining optimized solutions. Moreover, we will elaborate the time complexity of QUBO problems by showing a link of a QUBO problem to an integer linear problem between 0-1, and discuss the error bound of QITE by proving some theorems. To justify this argument, we will implement QAOA and QITE for Hamilton Cycle problems on IBM Qiskit to obtain the minimum energy eigenvalue, and compare the results of the two algorithms. One could expect that the QITE algorithm solves Hamilton Cycle Problem on quantum machines faster than classical algorithms on deterministic Turing machines. We will use the simulated annealing algorithm implemented through PyQUBO and a developed program code to compare and justify the solutions obtained by QITE and QAOA. To be able to obtain solutions for Hamilton cycle problems has implications and applications to other problems such as traveling salesman problem, Boolean satisfiability problems, and vertex covering problems. If such solutions are achieved, the NP problems which can be converted into these kinds of problems will have faster algorithms for obtaining solutions. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/91710 |
DOI: | 10.6342/NTU202400373 |
全文授權: | 同意授權(全球公開) |
顯示於系所單位: | 物理學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-112-1.pdf | 7.95 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。