在三正則圖下的最大獨立集量子近似演算法

Quantum Approximate Optimization Algorithm for Maximum Independent Set Problem in 3-regular Graph

吳秉陞(Bing-Sheng. Wu)

指導教授 ： 蔡明哲

國立清華大學/電機資訊學院/資訊工程學系所/碩士(2020年)

摘要

最大獨立集是ㄧ個NP困難問題。一般而言，最大獨立集問題沒有常數近似演算法。而傳統貪婪演算法證明了在有界度圖上有足夠好的近似比，並且給出了3/(delta+2)的近似比。在這篇論文我們嘗試去設計量子近似演算法來解決最大獨立集問題。這個量子近似演算法是基於 Farhi 等人最先提出的量子近似優化演算法(QAOA)。雖然QAOA是一個尋找組合優化近似解的演算法框架，但無法直接使用它來解決最大獨立集問題。並不是每一個基礎態都是最大獨立集的可行解。為了保證量子近似演算法只搜索可行解空間我們利用連續量子隨機漫步来確保我們最後得到的解是可行的。我們模擬量子近似演算法在最大度為三的圖上的效能且此以算法能在平均狀況下做得比貪婪演算法還要好。

關鍵字

量子計算 ； 近似演算法

並列摘要

The maximum independent set problem (MISP) is one of famous NP-hard problems, and it has no constant ratio bounded in polynomial time in a general graph. For a graph with maximum degree delta, it's has been shown that the classical greedy gives an approximation ratio of 3/(delta+2)(i.e., the greedy algorithm has an approximation ratio of 0.6 in 3-regular graph). In this thesis, the first attempt to design a quantum approximate algorithm is made for the MISP. The proposed quantum approximate algorithm is based on quantum approximate optimization algorithm (QAOA) that was first brought by Farhi et al. Although QAOA is a general algorithm which can approximate solutions to combinatorial optimization problems, it cannot be employed directly to solve the MISP. Since not every basis state is a feasible solution in the MISP. To ensure that the quantum approximate algorithm only searches for the feasible solutions, the continuous-time quantum walk is employed. We simulate the quantum approximate algorithm in graphs with maximum degree. Then, compare to the greedy algorithm and get the result that the quantum approximate algorithm can do better than the greedy on the average case.

並列關鍵字

quantum computing ； approximate algorithm

參考文獻

[1] P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer," SIAM review, 1999.

[2] E. Farhi, J. Goldstone, and S. Gutmann, A quantum approximate optimization algorithm," arXiv.org preprint arXiv:1411.4028, 2014.

[3] S. Hadeld, Z. Wang, E. G. Rieel, B. O'Gorman, D. Venturelli, and R. Biswas, Quantum approximate optimization with hard and soft constraints," 2017.

[4] I. Hen and M. S. Sarandy, Driver hamiltonians for constrained optimization in quantum annealing," Physical Review A, 2016.

[5] I. Hen and F. M. Spedalieri, Quantum annealing for constrained optimization," Physical Review Applied, 2016.