臺灣博碩士論文加值系統

本研究探討量子Grover搜尋法(簡稱QGSA)實際運用的可行性。為建構儲存資料及執行資料搜尋的量子系統，本研究採用QuaSi2模擬軟體在傳統三十二位元電腦上模擬對N筆資料進行單一資料的量子搜尋過程。透過針對256筆資料數進行單一資料搜尋，設計對應的256個搜尋模擬電路，然後對每一個電路進行模擬量子搜尋。研究結果顯示模擬的量子搜尋結果與QGSA的理論預測結果非常接近，證實在256筆資料數以內的量子搜尋法的可行性。
關鍵字：量子搜尋法、模擬電路、Grover搜尋法

We investigate the applicability of the quantum Grover search algorithm (QGSA) for real cases. In order to have a quantum system for storing the data and performing the search procedures, we employ the quantum simulator (QuaSi2) software to simulate the system on a traditional computer of 32 bits. We investigate the cases of the number, equal to or smaller than 256, of the data. By designing the corresponding quantum circuits to carry out the QGSA simulation, we found the simulation results being close to the predictions of the QGSA theory. It is shown in our studies that the QGSA for the number of the data less than 256 are applicable.

Key words : Quantum Search Alogrithm , Quantum Circuit,Grover Search Alogrithm

目錄
第一章 緒論…………………....................... 1
第一節 簡介…………………………………. 1
第二節 量子演算法的發展歷史……………..2
第三節 Dirac表述法………………………...3
第四節 量子平行計算與量子糾纏態………..4
第五節 論文架構……………………………..5
第二章 量子電路……………………………..6
第一節 概論…………………………………..6
第二節 量子閘………………………………..8
第三章 Grover搜尋法……………………...17
第一節 古典搜尋法…………………………17
第二節 Grover量子搜尋法………………...18
第四章 GSA電路設計模組………………..24
第一節 模組簡介……………………………24
第二節 GSA電路設計模組：以8為例…..26
第三節 G迭代次數與量測…………………29
第五章 研究分析……………………………31
第一節 模擬器簡介…………………………31
第二節 GSA模擬電路設計………………..35
第三節 執行GSA程式模擬……………….37
第四節 其他模擬器………………………...42
第六章 結論………………………………..49

參考文獻……………………………………49

附錄…………………………………………52



表目錄
表2.1 CN真值表………………………… 13
表2.2 CCN真值表……………………….14
表5.1 機率表……………………………..40
表5.1 不同n值的比較…………………..42

圖目錄
圖2.1 布洛赫球面………………………………7
圖2.2 反閘………………………………………9
圖2.3 反閘電路…………………………………9
圖2.4 哈達馬閘…………………………………10
圖2.5 哈達馬閘電路……………………………10
圖2.6 鮑立轉換…………………………………12
圖2.7 CN閘電路………………………………..13
圖2.8 CCN閘電路……………………………..14
圖2.9 (a)控制位元為0,(b)控制位元為1……..15
圖2.10 電路的串聯與並聯……………………15
圖2.11 量測符號……………………………….16
圖3.1 擴散轉換前……………………………...21
圖3.2 擴散轉換後……………………………...21
圖4.1 GSA電路模組…………………………...24
圖4.2 GSA的G迭代電路模組………………..23
圖4.3 N=8,電路模組……………………………26
圖4.4 N=8,量子狀態向量圖示…………………26
圖4.5 G迭代的影響……………………………29
圖5.1 QuaSi2介面……………………………..32
圖5.2 電路設計…………………………………33
圖5.3 波長及方向………………………………33
圖5.4 實數與虛數部分…………………………34
圖5.5 數字部分…………………………………34
圖5.6 N=256,5的搜尋電路……………………38
圖5.7 用QuaSi2執行GSA電路結果……….38
圖5.8 比較理論與模擬電路機率值之曲線圖…41
圖5.9 不同n值模擬程式搜尋機率圖…………42

參考文獻
蘇正耀, 量子計算淺談, 《物理雙月刊》, 25, 502-509. 2003.
蔡淑慧, 量子電腦的物理實作, 收錄於郭斯彥．郭耀煌(編), 《量子教材》.
黃吉川．謝金源．李哲明, 量子計算與資訊}, 《科學發展》, 306, 46-53, 2003.
曾謹言, 量子力學導論, 凡異出版社, 1999.
李建二,量子物理簡介, 收錄於郭斯彥．郭耀煌(編), 《量子教材》.
蔡一鳴．朱怡霖．郭斯彥, 量子電路簡介, 收錄於郭斯彥．郭耀煌(編), 《量子教材》.
徐士良, 數值方法常用演算法, 清華大學出版社, 1991.
謝金源, 加速資料搜尋之量子演算法, 收錄於郭斯彥．郭耀煌(編), 《量子教材》.
L. Grover, "A fast quantum-machanical algorithm for database search", Annual Symposium on the Theory of computing, pp.212-219, 1996.
L. M. K. Vandersypen et al., "Implementation of a three-quantum-bit search algorithm", Appl. Phys. Lett., Vol.76, pp.464-486, 2000.
L. M. K. Vandersypen et al., "Experiment realization of Shor's quantum factoring algorithm using nuclear magnetic resonance", Nature, Vol.414, pp.883-886, 2001.
QuaSi, M. Eck, P. Wocjan and R. M. Zeier, web address:http//iaks-www.iar.uka.de/home/matteck/QuaSi/aboutquasi.html.



P. Benioff, "The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines", J. of Stat. Phys., Vol.22, pp.563-591, 1980.
R. Feynman, "Simulating physics with computers", Inter. J. of Theo. Phys., Vol.21, pp.467-488, 1982.
D. Deutsch, "Quantum Theory, the Church-turning principle, and the universal quantum computer", Proc. Royal Soc. London, Series A, Vol.400, pp.97-117, 1985.
P. W. Shor, "Algorithms for quantum computation:discrete logarithms and gactoring", Proceedings $35^{th}$ Annual Symposium on Foundation of Computer Science, IEEE Press, Los Alamitos, pp.124-134, 1994.
M. A. Nielsen and I. L. Chuang, "Quatum Computation and Quatum Information", Cambridge University Press, 2000.
C. Lavor, LRU. Manssur and R. Portugal, "Grover's Algorithm:
Quantum database search", arXIV:quant-ph/0301079, unpublished.
T. H. Cormen, C. E. Leiserson and R. L. Rivest. "Introduction to Algorithms", MIT Press, Cambridge, Mass, 1990.
P. Emberson,"An Introduction To Quantum Algorithm Design", Masters Thesis, Department of Compuyrt Science, University of Youk, unpublished.
Quark, P. P. Rohde, web address:http://www.physics.uq.edu.au/people/rohde/blog/?pag$e_{i}$d=20.
Open Qubit, Y. Pritzker et al., web address:http://www.gnu.org/copyleft/gpl.html.
Fraunhofer Quantum Computing Simulation, H. Ros$acute{e}$ et al., web address:http//www.qc.fraumbofer.de/
QCSim, M. Cass, web address:http://hissa.nist.gov/~black/Quantum/download.html.
QuiDDPro, G. F. Viamontes, I. L. Markov and J. P. Hayes, web address:http://vlsicad.eecs.umich.edu/Quantum/qp/.
QCL, B. Omer, web address:http://tph.tuwin.ac.at/oemer/qc/.html.
jQuantum, A. de Vries, web address:http://jquantum.sourceforge.net/.
QCE, K. Michielsen and H. de Raedt, web address:http://rugth30.phys.rug.nl/compphys0/qce.html.