臺灣博碩士論文加值系統

量子計算與量子資訊科學是一門新興的研究領域,藉著結合量子力學以及新的物理定律,提供給我們更進階的途徑,來解決傳統電腦所難以克服的問題。其中1996年Grover量子搜尋演算法被提出至今已若干年,其優於傳統搜尋演算法的表現使得量子電腦將為人類的未來提供更多可能性。

近年來,許多學者利用Grover量子演算法在一未排序的N筆資料中搜尋單一目標僅需要O((N)^{1/2})時間,來嘗試尋找最小值的問題。在傳統上,搜尋最小值需要O(N)時間;學者們利用Grover的量子搜尋演算法所得到之結果重複替代oracle中的門檻值來求得最小值,卻只需要O(N^{1/2})時間。不過因平均搜尋時間皆需>45/4(N^{1/2}),所以需N較大時,才能展現其特性。

在本篇論文中,我們提出兩個以Grover量子演算法為主的新式搜尋法在尋找最小值的問題上,方法(1)為使用量子計數來估計被標示狀態的數量以決定最佳所需的重複次數。方法(2)為判斷是否量測到目標值來調適性調整重複次數,藉此來降低方法(1)的複雜度,而其平均搜尋時間只需要O(6(N^{1/2})),因此無論N較大或較小時皆能擁有較佳的表現;且與各學者所提出的搜尋最小值之量子演算法做個討論與比較。

另外，我們把上述所提之演算法應用於天線選擇與影像處理中的區塊移動估測,
由實驗結果可證明,與傳統搜尋演算法比較起來,量子演算法確實擁有極佳的表現。

Quantum computation and quantum information science, which combine the exploration of quantum mechanics and new physical principals, have been a promise for solving complicated problems that are not tractable by conventional computers. In this thesis, we consider quantum search algorithms to search the minimum in an unordered database of N items.

Traditionally, the running time required to locate the minimum is O(N) steps. To alleviate the computational load, various quantum search algorithm of complexity O(N^{1/2}) have been addressed. This thesis presents two fast Grove-based quantum search algorithms to more efficiently find the minimum. The first one uses the quantum counting to estimate the number of marked states to determine the number of iterations required, whereas the second one, to reduce the complexity called for, adaptively adjusts the number of iterations based on whether we can find a lower minimum or not in the present iteration.

Comparison with other related quantum search algorithm is also thoroughly made. To justify the validity of the new algorithm, we apply it to antenna selection and block-based motion estimation problems. As shown by provided simulations, the new algorithm offers lower computational complexity compared with previous works in various scenarios.

第一章緒論
1.1 引言. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 研究動機與目的. . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 論文章節概述. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
第二章量子計算
2.1 量子計算概論. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 單一量子邏輯閘簡介. . . . . . . . . . . . . .. . . . . . . . . . . . 11
2.2.1 Pauli-X 閘 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.2 Pauli-Y 閘 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.3 Pauli-Z 閘 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.4 Hadamard 閘. . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 多量子邏輯閘簡介 . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.1 控制反向閘 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.2 控制-控制-反向閘 . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.3 量子邏輯閘之應用 . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4 結語. . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 22
第三章搜尋最小值之量子演算法
3.1 Grover量子搜尋演算法簡介 . . . . . . . . . . . . . . . . . . . . . . 23
3.2 D‥urr等學者所提之量子搜尋演算法簡介 . . . . . . . . . . . . . . . . 25
3.3 吳文榮所提之量子搜尋演算法簡介 . . . . . . . . . . . . . . . . . . . 28
3.4 Okubo等學者所提之量子搜尋演算法簡介 . . . . . . . . . . . . . . . . 34
3.5 本文所提出量子搜尋演算法(1). . . . . . . . . . . . . . . . . . . . . 36
3.6 本文所提出量子搜尋演算法(2) . . . . . . . . . . . . . . . . . . . . 41
3.7 討論與比較 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.8 結語 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
第四章應用
4.1 天線選擇 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.1.1 天線選擇方式 . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.1.2 天線選擇模擬結果 . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.2 區塊比對原理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.2.1 各種區塊比對法 . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.2.2 視訊壓縮模擬結果 . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.3 結語 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
第五章結論及未來展望
參考文獻

[1] S. Imre and F. Bal’azs, Quantum Computing and Communication. John Wiley
and sons, 2005.
[2] M. A. Nielsen and I. L. Chuang,Quantum Computation and Quantum Information.
Cambridge University Press, 2002.
[3] P. Shor, “Algorithms for quantum computation: discrete logarithms andfactoring,” in Proc. of the 35th Annual IEEE Symposium on Foundations of
Computer Science, pp. 124-134, 1994.
[4] L. Grover, “A fast quantum mechanical algorithm for database search,” in
Proc. of the 28th Annual ACM Symposium on the Theory of Computing, pp.212-219, 1996.
[5] http://domino.research.ibm.com/comm/pr.nsf/pages/news.html
[6] http://www.dwavesys.com/
[7] C. Durr and P. Hφyer, “ A quantum algorithm for finding the minimum,”
Quantum Physics, preprint (available at http://xxx.lanl.gov/abs/quantph/ 9607014), 1996.
[8] 吳文榮, The Study of The Quantum k-th Smallest Number Problem. 義守大
學資訊工程研究所碩士論文, 2003.
[9] S. Okubo, T. Nishino, K. Ohta and N. Kunihiro, “A quantum algorithm for
finding the minimum on NMR quantum computers” ERATO Workshop on Quantum Information Science, pp.152-153, 2004.
[10] T. Kailath and A. Paulraj,“Increasing capacity in wireless broadcast systems using distributed trasmission/directional reception (DTDR),” U.S. Patent 5 345 599, 1994.
[11] G. J. Foschini, “Layered space-time architecture for wireless communication in a fading environment when using multiple antennas,” Bell Labs Syst. Tech. J., vol. 1, p. 41-59, 1996.
[12] G. J. Foschini and M. J. Gans, “On limits of wireless communications in a
fading environment when using multiple antennas,” Wireless Personal Commun.,
vol. 6, no. 3, pp. 311-335, 1998.
[13] J. Preskill, Lecture Notes for Physics 229: Quantum information and computation. California Institute of Technology, 1998.
[14] A.Barenco, “A universal two-bit gate for quantum computation,”Proc. Roy.
Soc. Lond. A, vol. 449, pp. 679-683, 1995.
[15] D. Dectsch, “Quantum computational networks,” Proc. Roy. Soc. Lond. A,
vol. 425, pp. 73-99, 1989.
[16] A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter,“Elementary gates for quantum computation” Physical Review A, vol. 52(5), pp. 3457-3467, Nov. 1995.
[17] E. Arikan, “An information-theoretic analysis of Grover’s algorithm,” IEEE ISIT,Yokohama, Japan, June 29-July 4,2003.
[18] L.K. Grover, “Quantum mechanics helps in searching for a needle in a
haystack,” Physical Rev. Letters, vol. 79, no. 2, pp.325-328, 1997.
[19] G. Brassard, “Searching a quantum phone book,” Science, vol.275, p. 627,
1997.
[20] C. P. Williams. “Quantum search algorithms in science and engineering,”
IEEE Computing in Science and Engineering, 3(2):44-51, March-April, 2001.
[21] C. Zalka, “using Grover’s quantum algorithm for searching actual databases,” Physical Rev. A, vol. 62, pp 052305¡1-052305¡4, 2000.
[22] M. Boyer, G. Brassard, P. Hoyer and A. Tapp, “Tight bounds on quantum
searching,” Fortschritte Der Physik, vol.46, pp. 493-505 1998.
[23] G. Brassard, P. Hoyer and A. Tapp, “Quantum counting,” Proc. 25th International Colloquium on Automata, Languages, and ProgrammingLecture Notes
of Computer Science 1443, Springer-Verlag, Berlin, pp. 820-831, 1998 .
[24] A. Ambainis, Quantum search algorithms, Technical Report arXiv:quantph/
0504012, 2005.
[25] A. Gorokhov, D. Gore, and A. Paulraj, “Receive antenna selection for MIMO
flat-fading channels: Theory and algorithms,” IEEE Trans. Inform. Theory,
vol. 49, pp. 2687-2696, Oct. 2003.
[26] X. Kai, L. Tao, Y. Chang-chuan, and Y. Guang-xin, “Transmit antenna selection for MIMO systems,” Proceedings of the IEEE 6th circuits and systems
symposium, vol. 02, pp. 701-704, June 2004.
[27] S. Sanayei and A. Nosratinia, “Antenna selection in MIMO systems,” IEEE
Communications Magazine, vol. 42, no. 10, pp. 68.73, Oct. 2004.
[28] A. F. Molisch and M. Z. Win, “MIMO systems with antenna selection,” IEEE
Microw. Mag., vol. 5, pp. 46-56, Mar. 2004.
[29] H. M. Chen, P. H. Chen, K. L. Yeh, W. H. Fang, M. C. Shie, and F. Lai,
“Center of mass-based adaptive fast block motion estimation,” EURASIP Journal on Image and Video Processing, vol. 2007, 11 pages, 2007.
[30] A. M. Tekalp, Digital Video Processing. Prentice Hall, 1995.
[31] T. Ebrahimi, E. Reusens, and W. Li, “New trends in very low bitrate video
coding,” IEEE Proc., vol. 83, no. 6, pp. 877-891, June 1995.
[32] K.Aizawa, T. S. Huang, ”Model-based image coding : advanced video coding
techniques for very low bit-rate applications,” IEEE Proc., vol. 83, no. 2, pp. 259-271, Feb. 1995.
[33] M. J. Chen, L. G. Chen, and T. D. Chiueh, ”One-dimensional full search
motion estimation algorithm for video coding,” IEEE Trans. Circuits Syst.
Video Technol., vol. 4, no. 5, pp. 504-509, Oct. 1994.
[34] K. R. Rao and J. J. Hwang, Techniques and Standards for Image, Video,
Audio coding. Prentice Hall, 1996.
[35] L. M. Po and W. C. Ma, ”A novel four-step search algorithm for fast block
motion estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 6, no. 3,
pp. 313-317, June 1996.
[36] J. Y. Tham, S. Ranganath, M. Ranganath, and A. A. Kassim, ”A novel unrestricted center-based diamond search algorithm for block motion estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 8, no. 4, pp. 369-377, Aug. 1998.
[37] D. R. Walker and K. R. Rao, “Motion-compensated coder,” IEEE Trans.
Commun., vol. 35, no. 11, Nov. 1987.
[38] Y. Yokoyama, Y. Miyamoto, and M. Ohta, “Very low bit rate video coding
using arbitrarily shaped region-based motion compensation,” IEEE Trans.
Circuit Syst. Video Technol., vol. 5, no. 6, pp.500-507, Dec. 1995.
[39] P. Salembier, L. Torres, F. Meyer, and C. Gu, “Region-based video coding
using mathematical morphology,” IEEE Proc., vol. 83, no. 6, pp. 843-857,
June 1995.
[40] S. A. Seyedin and C. J. E. Philips, “Motion estimation using the radon transform in dynamic scenes,” SPIE, vol. 2501, pp. 137-1348,May 1995.
[41] L. Wu, J. Bemois-Pineau, P. Delagnes, D. Barba, “Spectial-temporal segmentation of image sequences for object-oriented low bit-rate image coding,” Signal Processing: Image Commun, vol. 8, pp. 513-543, 1996.