量子隨機漫步於一般圖形的統一架構

A Unified Framework for Quantum Random Walk Algorithms on General Graphs

楊育翰(Yu-Han Yang)

指導教授 ： 顏嗣鈞

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2007年)

https://doi.org/10.6342/NTU.2007.00383

摘要

在文獻中，有幾個量子演算法已被證明具有優越性超過其相對應之傳統演算法。最近的一個是量子隨機漫步。我們提出一個量子隨機漫步於一般圖形的統一架構。引進單一標籤的概念進入量子隨機漫步演算法。如果單一約束都無法滿足，我們還提供另一種中間量測的方法。我們並以幾個例子說明了所設計的演算法能保持量子干涉性質。

關鍵字

量子演算法 ； 隨機漫步

並列摘要

In the literature, several quantum computation algorithms have been shown to have superiority over their classical counterparts. The most recent one is quantum random walks. We propose a unified framework for quantum walk algorithms on general graphs. We introduce the concept of unitary labeling into the quantum walk algorithm, and also provide another solution with intermediate measurement if the unitary constraint is not satisfied. We also demonstrate that the designed algorithms maintain the quantum interfering property with a few examples.

並列關鍵字

quantum algorithm ； random walk

參考文獻

[1] P. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM J. Comp., 26: 1484-1509, 1997.

[2] L. Grover, “A fast quantum mechanical algorithm for database search,” Proceedings of STOC’96, pp. 212-219.

[4] U. Schöning. “A probabilistic algorithm for k-SAT and constraint satisfaction problems,” Proc. 40th IEEE Symp. Foundations of Computer Science, pp. 410-414, October 1999.

[5] D. Meyer. “From quantum cellular automata to quantum lattice gases,” Journal of Statistical Physics, 85: 551-574, 1996.

[6] E. Farhi and S. Gutmann. “Quantum computation and decision trees,” Physical Review A, 58: 915-928, 1998.