臺灣博碩士論文加值系統

本論文探討Shor量子質因數分解演算法實際運用的可行性。我們利用傳統三十二位元個人電腦及QuaSi2量子電路模擬軟體來建構量子模擬電腦並在其上進行模擬演算。
本研究針對數字在32以下可進行質因數分解成兩個不同質數相乘的正整數進行分析。從模擬器上量子記錄器所記載的量子態振幅及量測機率等紀錄中，分析可能產生計算結果的各種量子態的分佈情形，接著計算最可能量子態的對應分解週期，進而得到被分解整數的可能質因數分解。因受演算法則的限制，僅能針對15及21正整數進行量子質因數分解，對於其他整數如6及10等則無法利用本演算法進行分析。
本研究在研究過程中發現進行模擬演算可能會遭遇下列的困難，值得提出作為相關研究的參考。首先是模擬軟體的模擬量子位元數的限制，使得本研究僅能針對32以下的正整數進行研究。其次是Shor量子分解演算法僅適用於計算分解週期為偶數的正整數，對於分解週期不為偶數的正整數則不適用。最後是模擬分析必須依賴人工進行逐步操作與分析，將不利於分析工作量很大的模擬演算。
為增進對Shor分解法的研究，本研究建議未來的量子模擬軟體最好具備下列兩項功能。其一是應具備能同時操作更多量子位元數的模擬器，以方便驗證對大數字進行Shor量子質因數分解計算的可行性；其二是能將演算分析與模擬器結合的模擬軟體以解決目前需要人工逐步操作的作業問題。

We investigated the applicability of Shor's quantum factoring algorithm.By employing the quantum simulator 2 (QuaSi2) on a traditional personal computer of 32 bits,we can construct the simulation environment for performing algorithm and related analysis.
We restricted to the positive integers smaller than 32,which can be factorized into a product of two different prime factor integers.According to the informations associated with the quantum states of the quantum registers,we analyzed the amplitudes of quantum registers with most probabilities to find out the factoring period and to derive the prime factors of the target integer.
Due to the limitation of Shor's algorithm,we can only analyze the target intergers 15 and 21.As for the other integers, such as 6 and 10,the employed factoring algorithm is inapplicable.
According to our analysis,we found that there exist following limitations in the simulation.The QuaSi2 can only imitate at most 20 quantum bits.This limitation restricts the target integer that can not be greater than 64.The next limitation comes from the fact that the Shor's quantum factoring algorithm can only be applied to the factoring period of even number.Since both performance of simulation and analysis of factoring algorithm require manual controls,it is indeed a time consuming work.
In order to improve the studies of Shor's factoring algorithm,we propose two suggestions for future simulators.The future simulator should be capable of a large enough number of quantum bits,in order to carry out quantum factoring algorithm for large target integers.The future simulator can perform simulation and analyze the factoring algorithm in a integrated way.

目錄
第一章 緒論…………………............................................. 1
第一節 簡介……………………………..………..… 1
第二節 量子力學與資訊學的關係…….…………....3
第三節 量子演算法………………………………....4
第四節 量子電路模擬器…………………………....6
第五節 論文架構…………………………………....9
第二章 量子質因數分解………………………………….....10
第一節 質因數分解介紹…………………………...10
第二節 古典質因數分解……………………….…..10
第三節 量子質因數分解…………………………...13
第三章 量子電路……………………………………............16
第一節 量子電路介紹………….………………..…16
第二節 量子基本閘………………………………...17..
第三小節 量子控制旋轉閘…………….....22
第三節 量子傅立業轉換電路……………………...23
第四節 模指數電路………………………………...25
第四章 研究分析……………………………………..……..28
第一節 模擬程式……………………………..……29
第二節 模擬結果與分析……………………..……32
第一小節 (x,n)=(2,15)的量子電路設……32
第二小節 其餘七個數值的量子電路設計..49
第五章 結論……………………………………..……………58

參考文獻………………………………………………………60
………………..
附錄一…………………………………………………………64
附錄二…………………………………………………………71. .
附錄三…………………………………………………………75
附錄四…………………………………………………………80

圖目錄
圖1.1 量子隱形傳輸圖示……………………..……………4
圖3.1 布洛赫球面…………………………………………18
圖3.2 哈達馬閘作用在布洛赫球面的圖示………………20
圖3.3 控制旋轉閘以y軸和z軸為軸心旋轉的圖示……23
圖3.4 模指數的電路圖……………………………………25
圖3,5 模指數電路圖示…………...……26
圖4.1 QuaSi2軟體的介面……………………………….29
圖4.1 QuaSi2的四個顯示視窗……………………….....30
圖4.2 質因數分解的量子電路架構…………………..…..31
圖4.4 執行(x,n)=(2.15)第一次的四個顯示視窗…………35
圖4.4 執行(x,n)=(2.15)第二次的四個顯示視窗…...…….37
圖4.6 執行(x,n)=(2.15)第三次的四個顯示視窗…….…...38
圖4.7 執行(x,n)=(2.15)第四次的四個顯示視窗….……...39
圖4.8 執行(x,n)=(2.15)第五次的四個顯示視窗………....40
圖4.9 執行(x,n)=(2.15)第六次的四個顯示視窗………....42
圖4.10 執行(x,n)=(2.15)第七次的四個顯示視窗……….…43
圖4.11 執行(x,n)=(2.15)第八次的四個顯示視窗…….……44
圖4.12 執行(x,n)=(2.15)第九次的四個顯示視窗….………45
圖4.13 執行(x,n)=(2.15)第十次的四個顯示視窗…………..46
圖4.14 執行(x,n)=(2.15)第十一次的四個顯示視窗……..…47
圖4.15 執行(x,n)=(2.15)第十二次的四個顯示視窗……..…48
圖4.16 執行(x,n)=(4.15)的四個顯示視窗………………..…52
圖4.17 執行(x,n)=(7.15)的四個顯示視窗………………..... 53
圖4.18 執行(x,n)=(8.15)的四個顯示視窗…………………...53
圖4.19 執行(x,n)=(11.15)的四個顯示視窗………………….54
圖4.20 執行(x,n)=(13,15)的四個顯示視窗………………….55
圖4.21 執行(x,n)=(8.21)的四個顯示視窗……………………56
圖4.22 執行(x,n)=(13.21)的四個顯示視窗…………………..56

表目錄
表3.1 CNOT閘真值表……………………………………… 22
表4.1 執行(x,n)=(2.15)第一次量測結果…………………….36
表4.2 執行(x,n)=(2.15)第二次量測結果…………………….37
表4.3 執行(x,n)=(2.15)第三次量測結果…………………….39
表4.4 執行(x,n)=(2.15)第四次量測結果…………………….40
表4.5 執行(x,n)=(2.15)第五次量測結果…………………….41
表4.6 執行(x,n)=(2.15)第六次量測結果…………………….41
表4.7 執行(x,n)=(2.15)第七次量測結果…………………….42
表4.8 執行(x,n)=(2.15)第八次量測結果…………………….44
表4.9 執行(x,n)=(2.15)第九次量測結果…………………….45
表4.10 執行(x,n)=(2.15)第十次量測結果…………………….46
表4.11 執行(x,n)=(2.15)第十一次量測結果………………….47
表4.12 執行(x,n)=(2.15)第十二次量測結果………………….48
表4.13 執行(x,n)=(2.15)十二次量測結果的峰值總表……….49
表4.14 執行(x,n)=(4.15)六次量測結果的峰值總表……..….52
表4.15 執行(x,n)=(7.15)六次量測結果的峰值總表……..….52
表4.16 執行(x,n)=(8.15)六次量測結果的峰值總表……..….54
表4.17 執行(x,n)=(11.15)六次量測結果的峰值總表……….54
表4.18 執行(x,n)=(13.15)六次量測結果的峰值總表……….55
表4.19 執行(x,n)=(8.21)六次量測結果的峰值總表……..….55
表4.20 執行(x,n)=(13.21)六次量測結果的峰值總表……….57

{1} 曾謹言, 量子力學導論, 凡異出版社, 1999.
{2} 史斌星, 量子物理, 凡異出版社, 1997.
{3} 張為民, 科學發展月刊, 351, 56-61, 2002.
{4} 徐士良, 數值方法常用演算法, 清華大學出版社, 1991.
{5} 曾建誠, 破解因數分解及離散對數的量子演算法, 收錄於郭斯彥‧郭耀煌(編), 《量子資訊教材》.
{6} A. Einstein, B. Podolsky and N. Rosen, Phys. Rev. Vol 47, pp.777-780, 1935.
{7} C. H. Bennett and S. J. Wiesner, {"Communication Via one- and two-particle operators on EPR ststes"}, Phys. Rev. Lett., Vol.69, pp.2881-2884, 1992.
{8} C. H. Bennett et al., {"Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen Channels"}, Phys. Rev. Lett., Vol.70, pp.1895-1899, 1993.
{9} 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.
{10} R. Feynman, {"Simulating physics with computers"}, J. of Theo. Phys., Vol.21, pp.467-488, 1982.
{11} D. Deutsch, {"Quantum Theory , the Church-Turing principle , and the universal quantum computer"}, Proc. Royal Society London, Series A, Vol.400, pp.97-117, 1985.
{12} A. Yao, {"quantum circuit complexity"}, Proceedings $34^{th}$ Annual Symposium on Foundations of Computer Science, IEEE Press, Los Alamitos, pp.352-360, 1993.

{13} P. W. Shor, {"Algorithms for quantum computation:discrete logarithms and factoring"}, Proceedings $35^{th}$ Annual Symposium on Foundations of Computer Science, IEEE Press, Los Alamitos, pp.124-134, 1994.
{14} P. W. Shor, {"Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer"}, SIAM Journal on Copputing, Vol.26, pp.1484-1509, 1997.
{15} S. J. Lomonaco, {"A lecture on Shor's quantum factoring algorithm"}, arXive e-print quant-ph/0010024vl, unpublished.
{16} V. Vlatko, B. Adriano and E. Artur, {"Quantum Networks for Elementary Arithmetic Operations"}, Phys. Rev., Series A, Vol.54, pp.147-153, 1996.
{17} L. Grover, {"A fast quantum-mechanica algorithm for databsae search"}, Annual Symposium on the Theory of computing, pp.212-219, 1996.
{18} 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.
{19} P. Emberson, {"An Ineroduction To Quantum Algorithm Design"}, 4th Year MMath Research project department of Computer Science, University of York, 2002.
{20} jQuantum, A. de Vries, web address:http://jquantum.sourceforge.
net/.
{21} QCE, K. Michielsen and H. de Raedt, web address:http://rugth30.
phys.rug.nl/compphys0/qce.htm.
{22} G. F. Viamontes, I. L. Markov and J. P. Hayes, {"QuIDDPro User's Guide Version 2.1"}, The university of Michigan, 2005.
{23} QCL, B. Omer, web address:http://tph.tuwien.ac.at/oemer/qcl.html.
{24} Open Qubit, Y. Pritzker et al., web address:http://www.gnu.org/
copyleft/gpl.html.
{25} Fraunhofer Quantum Computing Simulationg, H. $Ros\acute{e}$ et al., web address:http://www.qc.fraunhofer.de/.
{26} Quack,P. P. Rohde,web address:http://www.physics.uq.edu.au/
people/rohde/blog/$?page_id=20$.
{27} QCSim, M. Cass, web address:http://hissa.nist.gov/black/Quantum
/download.html.
{28} C. Zhengjun, {"A Note on Shor's Quantum Algorithms for Prime Factorization"}, unpublished.
{29} G. H. Hardy and E. M. Wright, {"An Introduction to the Theory of Numbers,Fourth Edition"}, Oxford University Press, London, 1960.
{30} G. Daniel and I. L. Chuang, {"Quantum Teleportation is a Universal Compupational Primitive"}, Nature, Vol 402, pp.390-393, 1999.
{31} M. A. Nielsen and I. L. Chuang, {"Quantum Computation and Quatum Information"}, Cambridge University Press, 2000.
{32} T. H. Cormen, C. E. Leiserson and R. L. Rivest, {"Introduction to Algorithms"}, MIT Press, Cambridge, Mass., 1990.
{33} QuaSi, M. Eck, P. Wocjan and R. M. Zeier, web address:http//iaks-www.iar.uka.de/home/matteck/QuaSi/aboutquasi.html.
{34} C. P. Williams and S. H. Clearwater, {"Ultimate Zero and One:
Computing at the Quantum Frontier"}, Copernicus, 2000.