二面體群的隱含子群問題量子算法的研究.pdf

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

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

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