量子計算是指以光子、電子、原子等微觀粒子為信息載體,基於量子力學規律進行的信息處理過程,其基本規律包括量子態相干性、量子態糾纏性、量子態疊加性、量子不可克隆原理等。

量子計算基於微觀粒子的量子態疊加效應,可以對所有的狀態進行並行計算。例如,一個4比特的量子寄存器可同時表達0-15的所有16個數值,針對該寄存器的操作會同時作用到所有16個數值上。表面看來,這種指數級的並行處理能力能對任何計算困難問題進行暴力搜索求解。但量子計算的輸出結果是疊加態,很難從中獲取真正答案。现在只有秀爾算法能基於量子傅立葉變換提取出函數周期,可以破解現代公鑰密碼依賴的因子分解問題與離散對數問題,對於其他無法歸結成周期問題的困難問題,现在還不能得到多項式複雜度的求解算法。

需要特別指出的是,雖然加拿大的量子計算機製造公司D-Wave已經製造並出售了一系列量子計算機,然而其製造的量子計算機並不能運行秀爾算法,因此不會給基於因子分解與離散對數的密碼算法構成直接威脅。

量子技術除了可以用強大的並行計算能力攻擊傳統的密碼算法之外,其獨特的物理特性也能用來設計新的密碼算法和密碼協議,學術界稱之為量子密碼。當前量子密碼僅有量子密鑰分配協議的研究相對來說成熟,其他協議與算法還在研究中。

最典型的量子密鑰分配協議是1984年提出的BB84協議,該協議基於單光子實現通信雙方的密鑰協商。由海森堡測不準原理,竊聽者的任何測量動作都會對通信系統產生無法逆轉的於擾。

因此,任何非法的竊聽均會被合法的收發雙方發現,因而保證了密鑰分配協議的安全性。

量子計算提升了密碼分析能力,但也加速了密碼創新能力。基於量子計算構建完善的密碼學體系是密碼學开展的趨勢之一。