量子線路研究快速費(fèi)馬數(shù)變換的量子線路邏輯實(shí)現(xiàn).pdf

1、Shor算法能夠在多項(xiàng)式時(shí)間內(nèi)分解一個(gè)大數(shù)的質(zhì)因子，對(duì)現(xiàn)行RSA公鑰加密體系的安全性提出嚴(yán)峻挑戰(zhàn)。很多研究人員提出了Shor算法的改進(jìn)，其中Zalka的改進(jìn)使用改造的Sch(o)nhage-Strassen算法來(lái)降低Shor算法的復(fù)雜度，并提出量子電路來(lái)計(jì)算Sch(o)nhage-Strassen算法中用到的快速費(fèi)馬數(shù)變換。然而，Zalka提出的電路會(huì)產(chǎn)生垃圾位。在量子計(jì)算中，沒(méi)有得到處理的垃圾位會(huì)和運(yùn)算結(jié)果糾纏并對(duì)其產(chǎn)生影響，最壞情形

2、下會(huì)導(dǎo)致運(yùn)算結(jié)果出錯(cuò)。
　　本文提出一個(gè)不產(chǎn)生任何垃圾位的量子電路來(lái)計(jì)算快速費(fèi)馬數(shù)變換。對(duì)于長(zhǎng)度為b的n+1位整數(shù)序列，已知最好的電路需要使用17/2nblog b個(gè)Toffoli門(mén)來(lái)計(jì)算該序列的費(fèi)馬數(shù)變換，同時(shí)會(huì)產(chǎn)生3/2 blog b位垃圾位;相比之下，本文提出的電路則需要使用192nb log b個(gè)Toffoli門(mén)來(lái)完成同樣的任務(wù)，但是不會(huì)產(chǎn)生任何垃圾位。這個(gè)結(jié)果是通過(guò)洞察運(yùn)算結(jié)果和垃圾位之間的關(guān)系，并審慎地選擇垃圾位清除方