二面體群的隱含子群?jiǎn)栴}量子算法的研究.pdf

1、Shor算法的提出引起了眾多學(xué)者對(duì)量子計(jì)算的關(guān)注。Shor算法利用量子力學(xué)的疊加、坍縮等特性,在多項(xiàng)式時(shí)間內(nèi)求解了大整數(shù)因子分解問(wèn)題和離散對(duì)數(shù)問(wèn)題。而公鑰密碼體制的安全性依賴(lài)于大整數(shù)分解問(wèn)題或離散對(duì)數(shù)問(wèn)題的困難性,因此Shor算法對(duì)這些公鑰密碼體制形成了嚴(yán)重的安全威脅。進(jìn)一步研究表明大整數(shù)分解問(wèn)題和離散對(duì)數(shù)問(wèn)題都可以轉(zhuǎn)化為循環(huán)群的隱含子群?jiǎn)栴}。目前針對(duì)于A(yíng)bel群隱含子群?jiǎn)栴}比較成熟,研究較多集中在二面體群和對(duì)稱(chēng)群的隱含子群?jiǎn)栴}。Reg

2、ev提出格的唯一最短向量問(wèn)題可轉(zhuǎn)化為二面體群的隱含子群?jiǎn)栴},而格的唯一最短向量問(wèn)題為格公鑰密碼體制的安全性提供保障。類(lèi)似于Shor算法一樣,若有效解決二面體群的隱含子群?jiǎn)栴}就可以攻破基于唯一最短向量問(wèn)題的格公鑰密碼體制。
　　本文著重研究了二面體群的隱含子群?jiǎn)栴}的量子算法。Regev提出了目前為止最優(yōu)的二面體群的隱含子群?jiǎn)栴}的量子算法,本文分析了Regev算法之后,對(duì)Regev算法進(jìn)行了改進(jìn)與優(yōu)化。在具體工作中,本文減少了Rege

3、v算法中的重復(fù)循環(huán)次數(shù),對(duì)通過(guò)求解子集求和問(wèn)題求出特定的疊加態(tài)的量子線(xiàn)路進(jìn)行了改進(jìn),給出了具體優(yōu)化方案,以更少的時(shí)間得到我們所需要的目標(biāo)量子態(tài)。最后通過(guò)仿真實(shí)驗(yàn),驗(yàn)證了算法的正確性。隨后提出了基于區(qū)分ESD的二面體群隱含子群?jiǎn)栴}的量子算法。量子算法輸出的量子態(tài)看作為一個(gè)系綜,對(duì)兩個(gè)有相同密度矩陣的系綜進(jìn)行區(qū)分,就可以解決二面體群的隱含子群?jiǎn)栴}。最后對(duì)量子算法進(jìn)行了性能分析,并通過(guò)量子計(jì)算仿真驗(yàn)證了算法的正確性。隨后提出了兩種基于概率量子