運用量子基因遺傳演算法於搜尋迷宮問題的最佳解

Abstract

近年來，量子計算一直是個被人們廣泛討論的熱門話題。不論是學術界還是產業界大家都競相投入這個領域，大家相信在某些問題上量子計算會比古典計算更有優勢，最有名的兩個例子就是質因數分解和未排序資料庫搜索問題。在古典計算中，給定一個正整數N若想要找到他的質因數分解，至少也需要花費指數時間才行；然而若使用一個量子演算法--秀爾演算法，只要多項式時間就可以解決了。這也代表若存在一個量子位元數夠多、雜訊夠小的量子電腦，便可以破解現行的RSA加密演算法，因RSA加密演算法的基礎就是建構在古典計算無法輕易解開某數的質因數分解的前提下。格羅弗演算法則是一種量子搜尋演算法，透過多次Oracle和Diffusion Operator的接連作用，將共有N筆資料的資料庫裡我們所想要的那些資料的振幅不斷加大，並且減少其他我們不感興趣的資料的振幅，使最後做量測時可以高機率得到我們所想要的資料，相對於古典計算而言可以達到O(√N)級別的加速。

在此篇論文中，我們嘗試對格羅弗演算法做一些改進。雖然格羅弗演算法已經可以達到O(√N)加速，但隨著量子位元數增加，總資料量也會指數級別成長。就算有平方級別的加速，依然無法抑制因指數成長的搜索空間導致的複雜度上升。因此我們帶入動態規劃的技巧將搜索空間降成多項式級別成長，同時運用基因遺傳演算法增加額外探索性避免因分成好多段做格羅弗探索造成可能收斂到局部最佳解的情形，盡量搜索到全域最佳解。我們將這整個流程稱為量子基因遺傳演算法(QGA)。在之後的章節，我們會用一個自己定義的純量子遊戲環境來展示QGA整體的運算流程。

In recent years, quantum computing has been a popular topic which always widely discussed by people. No matter academia or industry, they are all dedicated to this field. They believe quantum computing is more powerful than classical computing in some specific problems. The two most famous examples are Integer factorization and unsorted database search problems. In classical computing, it takes at least exponential time to factor an integer N. But, if we apply a quantum algorithm called Shor’s Algorithm in the Integer factorization, we can solve this problem in polynomial time. Therefore, if there exists a quantum computer with a sufficient number of qubits that could operate without succumbing to quantum noise and other quantum-decoherence phenomena exist, then Shor's algorithm could be used to break public-key cryptography schemes, such as the RSA encryption algorithm. Because the basics of the RSA encryption algorithm are based on the assumption that factoring large integers is computationally intractable. Grover’s algorithm is a quantum searching algorithm. After the oracle and diffusion operator acting multiple iterations on the input quantum state, it amplifies the amplitudes of the data we want in the database and reduce the amplitude of the data we don’t interested in. Finally, the outcome of the quantum circuit will be what we want with a very high probability. In addition, the most important is that it can solve this problem O(√N) faster than the classical method.

In this thesis, we apply Grover's Algorithm to solve maze problems and propose a hybrid algorithm called Quantum Genetic Algorithm(QGA). Grover's Algorithm is guaranteed to give us O(√N) speed-up compared to the classical try and error method when solving a maze problem. This is undoubtedly a quick way to solve maze problems, but as the game map gets linearly deeper, the total space that Grover's Algorithm has to search grows exponentially at the same time. Consequently, we still can’t efficiently reduce the rapidly rising complexity caused by exponentially rising search space. In order to deal with this serious problem, we first use dynamic programming to decrease the growth of the search space into O(N) order and apply the Genetic Algorithm to assist the whole algorithm in reaching the global minimum. We will show how QGA working on the maze problem in chapter 4.