量子最佳化演算法設計

On the Design of Quantum Optimization Algorithm

江勁涵(Ching-Han Chiang)

指導教授 ： 陳博現

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

https://doi.org/10.6843/NTHU.2010.00545

摘要

本篇文章提出的量子最佳化演算法 (Quantum Optimization Algorithm) 將量子搜尋演算 (Quantum Search Algorithm) 法與量子計數演算法 (Quantum Counting Algorithm) 結合來解決最佳化問題。考慮一個含有N個元素的集合，並在此集合上定義一個函數使得集合內的每一個元素都對應一個函數值，而最佳化的目標即是在此集合內搜尋到具有最小或最大函數值的最佳元素。根據量子搜尋演算法，如果能建造一個最佳反相位量子閘擁有增加 相位到最佳元素的能力，則可以使用此最佳反相位量子閘O(√N) 次找到最佳元素。然而量子搜尋演算法並沒有提供製作最佳反相量子閘的方法，因此必須要另外尋找方法製作。觀察到最佳解同時具有最低的排序以及量子計數演算法可以用來製作排序估計演算法，這二觀察將有助於製作最佳反相位量子閘，方法如下：首先利用量子計數演算法設計一個排序估計演算法，接著利用此排序估計演算法辨識最佳原素進而製作最佳反向量子閘。然而排序估計演算法具有一些非理想的效應，且此效應將延續到量子最佳化演算法中而影響其效能，因此量子最佳化演算法的非理想效應與效能之分析亦在文中被討論。在最後的部分提供了一個數值範例驗證本篇論文的想法，此範例使用傳統電腦中的大矩陣乘法來模擬16個元素的量子最佳化演算法並得到了與推論相符合的結果。

關鍵字

量子最佳化演算法 ； 量子搜尋演算法 ； 量子計數演算法 ； 排序估計

並列摘要

In this study, we combine the quantum search algorithm and the quantum counting algorithm to perform a quantum optimization algorithm. We propose a method which applies the quantum counting algorithm to obtain the order of an element in a N-element set. Observing that the order information enable us to recognize the optimization solution, we employ the quantum search algorithm with order estimation algorithm to solve the optimization problem. Since the order estimation suffers a non-ideal effect that will affect the performance of quantum optimization algorithm, a performance analysis of quantum optimization algorithm is also provided. Finally, a numerical example is given to illustrate the proposed quantum optimization algorithm.

並列關鍵字

quantum optimization algorithm ； quantum search algorithm ； quantum counting algorithm ； order estimation

參考文獻

[1] M. Nielsen, I. Chuang, and L. Grover, “Quantum computation and quantum information,”American Journal of Physics, vol. 70, p. 558, 2002.

[2] L. Vandersypen and I. Chuang, “NMR techniques for quantum control and computation,”Reviews of modern physics, vol. 76, no. 4, pp. 1037–1069, 2005.

[3] J. Cirac and P. Zoller, “Quantum computations with cold trapped ions,” Physical Review Letters, vol. 74, no. 20, pp. 4091–4094, 1995.

[4] D. Loss and D. P. DiVincenzo, “Quantum computation with quantum dots,” Phys. Rev. A, vol. 57, no. 1, pp. 120–126, Jan 1998.

[5] D. P. DiVincenzo, “Two-bit gates are universal for quantum computation,” Phys. Rev. A, vol. 51, no. 2, pp. 1015–1022, Feb 1995.