量子算法與量子密碼導(dǎo)論 課件全套 第1-6章 緒論 - 量子密鑰分發(fā)技術(shù)

量子算法與量子密碼導(dǎo)論量子線路模型

一古典密碼二現(xiàn)代密碼三量子計算對現(xiàn)代密碼的影響四后量子時代密碼本章內(nèi)容

1.1古典密碼古典密碼學(xué)設(shè)計主要有兩大基本方法，分別為置換和代換。置換：將明文字母保持不變，但順序被打亂。典型的置換密碼是移位密碼，將原文中的所有明文字母都在字母表上向后（或向前）按照一個固定數(shù)目進行偏移后得出密文?！皭鹑雒艽a”就是典型的移位密碼。代換：明文字母被替換，但順序保持不變。代換密碼又可進一步分為單表代換、多表代換和多字母代換。典型的代換密碼包括維吉尼亞密碼、普萊費爾密碼等。古典密碼設(shè)計1.1古典密碼頻率分析在密碼學(xué)中，頻率分析是指研究字母或者字母組合在文本中出現(xiàn)的頻率。無論在何種自然語言體系當中，不同的文字單位都有其特定的出現(xiàn)頻率，這個特征一般表現(xiàn)在長篇幅、有意義的文字序列中。以英文為例，出現(xiàn)頻率最高的字母是e，其次是t、a、o…..找到出現(xiàn)頻率最高的符號，假設(shè)為e并將原符號替換

找到含有e的單詞，根據(jù)語言學(xué)基礎(chǔ)嘗試判斷其是否可能為明文中一個合理的單詞將得到新的假設(shè)重復(fù)類似步驟2的操作，直至密碼破譯。如果步驟2-3無法實施，則考慮將出現(xiàn)頻率最高的符號假設(shè)為t（按照頻率表從高到低依次假設(shè)），重復(fù)步驟2、3直至密碼破譯。1.1古典密碼完善保密系統(tǒng)（一次一密）1.2現(xiàn)代密碼私鑰密碼學(xué)

序列密碼：對數(shù)據(jù)流進行連續(xù)處理的一類密碼，通過密鑰序列生成器產(chǎn)生與明文消息相同長度的密鑰流序列，通過密鑰流序列與明文消息流序列的異或操作完成加解密。典型序列密碼包括：RC4算法、A5算法、ZUC算法等分組密碼：將明文消息序列劃分成固定長度的組，每組分別在密鑰的控制下變換成等長的密文序列。分組密碼的設(shè)計原則主要包括混淆與擴散。典型分組密碼包括：AES、SM4等

雜湊函數(shù)的定義：將任意長的消息M映射為較短的、固定長度的一個值H(M)。雜湊函數(shù)H一般是公開的，需要滿足單向性、抗碰撞性和抗第二原像碰撞性。典型雜湊函數(shù)包括：MD5、SHA-1、SHA-3等1.2現(xiàn)代密碼公鑰密碼學(xué)明文消息密文消息密文消息公鑰私鑰公鑰加密算法1.2現(xiàn)代密碼公鑰密碼學(xué)Diffie-Hellman(DH)密鑰交換協(xié)議1.2現(xiàn)代密碼公鑰密碼學(xué)密鑰封裝機制1.2現(xiàn)代密碼公鑰密碼學(xué)數(shù)字簽名方案1.2現(xiàn)代密碼公鑰密碼學(xué)

安全協(xié)議是建立在密碼算法基礎(chǔ)之上的高互通協(xié)議，為計算機網(wǎng)絡(luò)和通信系統(tǒng)的安全需求提供直接的解決方案,是構(gòu)建安全信息系統(tǒng)的基本要素,也是信息與網(wǎng)絡(luò)安全的關(guān)鍵技術(shù)。常用的安全協(xié)議包括TLS、IKE、SSH等。1.3量子計算對現(xiàn)代密碼的影響Shor量子算法Grover量子算法Simon算法BHT算法1.3量子計算對現(xiàn)代密碼的影響密碼算法類型功能量子計算的影響AES對稱密碼學(xué)加密更長的密鑰SHA-2，SHA-3對稱密碼學(xué)雜湊函數(shù)更長的摘要輸出RSA公鑰密碼學(xué)簽名密鑰建立不再安全ECDSA,ECDH（橢圓曲線密碼學(xué)）公鑰密碼學(xué)簽名密鑰建立不再安全DSA（有限域密碼學(xué)）公鑰密碼學(xué)簽名密鑰建立不再安全1.4后量子時代密碼基于量子力學(xué)基本原理的密碼學(xué)量子密鑰分發(fā)量子隨機數(shù)發(fā)生器基于數(shù)學(xué)問題的密碼學(xué)格密碼基于糾錯碼密碼多變量密碼學(xué)基于雜湊函數(shù)的密碼學(xué)謝謝量子算法與量子密碼導(dǎo)論量子力學(xué)基礎(chǔ)一量子力學(xué)革命二量子力學(xué)數(shù)學(xué)基礎(chǔ)三量子力學(xué)基本假設(shè)四量子力學(xué)基本現(xiàn)象本章內(nèi)容

2.1量子力學(xué)革命1兩次量子力學(xué)革命上世紀末以來，第二次量子科技革命在信息技術(shù)領(lǐng)域興起，如今已接近產(chǎn)業(yè)化階段在上世紀40年代興起第一次量子科技革命，催生了原子彈、半導(dǎo)體晶體管、激光器等重要成果2.1量子力學(xué)革命2黑體輻射—量子的誕生馬克斯·普朗克于1900年建立了黑體輻射定律的公式

為普朗克常數(shù)2.1量子力學(xué)革命1光電效應(yīng)—發(fā)現(xiàn)光量子愛因斯坦于1905年對光電效應(yīng)給出解釋光束描述為一群離散的量子，現(xiàn)稱為“光子”。從普朗克黑體輻射定律，組成光束的每一個光子所擁有的能量等于頻率乘以一個常數(shù)，即普朗克常數(shù)2.1量子力學(xué)革命2氫原子—分立能級玻爾于1913年提出了氫原子的量子理論：1）原子核外的電子只能處于一些分立的穩(wěn)態(tài)上，E1,E2,E3,···；2）如果電子要從能量較低的穩(wěn)態(tài)躍遷到能量更高的穩(wěn)態(tài)，它必須吸收一個光子；如果要從高能態(tài)躍遷低能態(tài)，它必須放出一個光子。吸收或釋放的光子能量等于兩個穩(wěn)態(tài)間的能量差，即2.1量子力學(xué)革命2波粒二象性—波&粒子德·布羅意于1923年提出微觀粒子都具有波粒二象性這個關(guān)系式后來就叫做德·布羅意公式，德·布羅意預(yù)言的電子同樣具有波粒二象性后來得到了實驗的證實2.1量子力學(xué)革命2波動力學(xué)—薛定諤方程薛定諤于1926年提出了薛定諤波動方程是約化普朗克常數(shù)，這個公式能夠正確地描述波函數(shù)的量子行為2.1量子力學(xué)革命2矩陣力學(xué)——與波動力學(xué)統(tǒng)一用線性代數(shù)中的矩陣可完全描述量子力學(xué)，給出了量子力學(xué)理論簡單而優(yōu)美的數(shù)學(xué)語言形式上與波動力學(xué)完全等價，是量子力學(xué)的兩種表現(xiàn)形式2.2量子力學(xué)數(shù)學(xué)基礎(chǔ)1線性空間—狄拉克符號其共軛行向量為

其中左矢

讀作bra，a*和

b*分別為

a和

b的共軛復(fù)數(shù)左矢和右矢連起來就是英文單詞bra(c)ket

任意一個二維列向量子態(tài)記作

其中

a和

b都是復(fù)數(shù)，且符號

為狄拉克符號的右矢，讀作ket2.2量子力學(xué)數(shù)學(xué)基礎(chǔ)1線性空間—內(nèi)積內(nèi)積在量子力學(xué)中，對于向量

和

，它們內(nèi)積形式如下：其結(jié)果是一個復(fù)數(shù)反過來，向量

和

的內(nèi)積為

幾何意義：表征兩個向量之間的夾角，以及一個向量在另一向量方向上的投影

2.2量子力學(xué)數(shù)學(xué)基礎(chǔ)1內(nèi)積的性質(zhì)內(nèi)積當兩個向量的內(nèi)積是一個實數(shù)時，有特別的，當兩個向量的內(nèi)積為0時，即稱這兩個向量正交2.2量子力學(xué)數(shù)學(xué)基礎(chǔ)1內(nèi)積的性質(zhì)內(nèi)積向量與它自身的內(nèi)積為其結(jié)果的平方根

稱為向量的模，幾何上表示向量的長度2.2量子力學(xué)數(shù)學(xué)基礎(chǔ)1線性空間—希爾伯特空間線性空間：也稱向量空間，常記為V，定義在某個數(shù)域K中，其元素為向量，對向量加法和標量乘法封閉內(nèi)積空間：具有內(nèi)積運算的線性空間希爾伯特空間：完備的內(nèi)積空間，有距離和角的概念量子態(tài)由希爾伯特空間中的單位向量來描述2.2量子力學(xué)數(shù)學(xué)基礎(chǔ)1線性空間—標準正交基希爾伯特空間中模長為1且兩兩正交的向量，如二維空間中的一組向量或可以表示空間中任意向量2.2量子力學(xué)數(shù)學(xué)基礎(chǔ)2線性算子—定義n維線性空間上的線性算子可以表示成一個

n×n的矩陣定義：若映射

A:V

V保持向量加法運算和標量乘法運算，即對于

，有

則稱A為線性空間V上的線性算子2.2量子力學(xué)數(shù)學(xué)基礎(chǔ)2線性算子—厄米算子與幺正算子泡利算子：厄米算子：其轉(zhuǎn)置復(fù)共軛等于它本身，即幺正算子：其轉(zhuǎn)置共軛等于它的逆，即顯然，四個泡利算子也都是幺正算子2.2量子力學(xué)數(shù)學(xué)基礎(chǔ)2線性算子—外積在量子力學(xué)中有一種非常有用的表示線性算子的方法，即外積表示法。對于向量

和

，其外積為其結(jié)果是一個線性算子可用于構(gòu)造測量算子，尤其是投影算子2.2量子力學(xué)數(shù)學(xué)基礎(chǔ)3本征值與本征態(tài)當線性算子A對線性空間

V中向量

v的作用是v的倍數(shù)時，

則稱

為的

A本征值，v為

A對應(yīng)于本征值

的本征態(tài)由本征值與本征態(tài)的定義可得

有非平凡解的充要條件，即本征值方程為

2.2量子力學(xué)數(shù)學(xué)基礎(chǔ)3本征值與本征態(tài)例.求泡利算子

的本征值和本征態(tài)

解：

本征方程為本征方程

解得本征值為

2.2量子力學(xué)數(shù)學(xué)基礎(chǔ)3本征值與本征態(tài)同理可得：

因此，歸一化后得：

令

為對應(yīng)于本征值

的本征態(tài)，則

2.2量子力學(xué)數(shù)學(xué)基礎(chǔ)3正規(guī)算子定理：若

A是正規(guī)算子，則其對應(yīng)不同本征值的本征態(tài)是正交的定義：若算子A滿足

，則稱

A為正規(guī)算子

簡并：對應(yīng)于同一本征值的多個不同的本征態(tài)稱為簡并態(tài)2.2量子力學(xué)數(shù)學(xué)基礎(chǔ)3譜分解定理及推論譜分解定理：A是一個正規(guī)算子，其本征值及相對應(yīng)的本征態(tài)分別為

和

，則

A可以分解為

推論：對于正規(guī)算子A，有

若算子A可逆，則有

對于任意自然數(shù)n都成立2.2量子力學(xué)數(shù)學(xué)基礎(chǔ)3正規(guī)算子函數(shù)

A是正規(guī)算子，f(x)為任意的解析函數(shù)，則稱

f(A)為正規(guī)算子函數(shù)，且有

例如

，求解：2.2量子力學(xué)數(shù)學(xué)基礎(chǔ)4張量積特別的，若

、

分別是V、W中的正交基，則

是

中的正交基，通常簡記為

或定義

：設(shè)V、W分別是

n維和

m

維的線性空間，v、w分別是V、W中的向量，A、B分別是V、W中的線性算子，則

是由張量積

構(gòu)成的nm維線性空間，張量積

是在空間

上的線性算子，有2.2量子力學(xué)數(shù)學(xué)基礎(chǔ)4張量積的計算假定線性算子A、B在空間V、W中n×n、m×m的矩陣，則

例如，2.3量子力學(xué)基本假設(shè)1波函數(shù)假設(shè)微觀物理系統(tǒng)的狀態(tài)由一個波函數(shù)完全描述。

如果一個微觀系統(tǒng)包含若干個粒子，而這些粒子又是按照量子力學(xué)的規(guī)律運動的話，則稱此系統(tǒng)處于某種量子狀態(tài)，簡稱量子態(tài)。波函數(shù)是粒子位置和時間的復(fù)函數(shù)，當一個微觀系統(tǒng)的波函數(shù)確定時，該系統(tǒng)的全部性質(zhì)都可以由此得出，即波函數(shù)表征了系統(tǒng)的量子態(tài)。2.3量子力學(xué)基本假設(shè)2量子態(tài)演化假設(shè)封閉量子系統(tǒng)量子態(tài)的演化由薛定諤方程描述

2.3量子力學(xué)基本假設(shè)3算子假設(shè)量子力學(xué)中的可觀測量由厄米算子來表示。這里的可觀測量是指可通過物理實驗得到測量結(jié)果的量，它對應(yīng)于經(jīng)典理論中的力學(xué)量。如果算子描述對應(yīng)于力學(xué)量，那么當系統(tǒng)處于某個本征態(tài)時，則力學(xué)量有確定值，即該本征態(tài)所對應(yīng)的本征值。

2.3量子力學(xué)基本假設(shè)4測量假設(shè)若算子F為量子力學(xué)中的一個力學(xué)量，其正交歸一化本征函數(shù)為，對應(yīng)的概率為cn，則任一量子態(tài)可表示為：當對一個量子體系進行某一力學(xué)量的測量時，測量結(jié)果一定為該力學(xué)量算子的本征值當中的某一個，測量結(jié)果為的概率為，當測量完成后，該量子體系塌縮至量子態(tài)。

2.3量子力學(xué)基本假設(shè)5全同粒子假設(shè)在量子系統(tǒng)中，存在內(nèi)稟屬性完全相同的粒子，對任意兩個這樣的粒子進行交換，不會改變系統(tǒng)的狀態(tài)。這表明在量子力學(xué)中，交換任意兩個全同粒子，不會導(dǎo)致任何可被觀測到的現(xiàn)象出現(xiàn)，也即微觀粒子是不能被標識的，無法在兩個電子之間做出區(qū)分，這與經(jīng)典世界的情況是不同的。2.4量子力學(xué)基本現(xiàn)象1基本原理不可克隆原理:量子力學(xué)中對任意一個未知的量子態(tài)進行完全相同的復(fù)制的過程是不可實現(xiàn)的。2.4量子力學(xué)基本現(xiàn)象1基本原理不確定性原理:對于一個微觀粒子，其位置與動量不能同時具有確定值。其位置信息的準確度越高，則同時能夠獲得的其動量信息的準確度越低，位置的不確定性與動量的不確定性遵守不等式2.4量子力學(xué)基本現(xiàn)象1基本原理不可區(qū)分原理:非正交的量子態(tài)不可能被同時精確測量。2.4量子力學(xué)基本現(xiàn)象2量子糾纏在量子力學(xué)里，當幾個粒子在彼此相互作用后，由于各個粒子所擁有的特性已綜合成為整體性質(zhì)，無法單獨描述各個粒子的性質(zhì)，只能描述整體系統(tǒng)的性質(zhì)，稱這種現(xiàn)象為量子糾纏（Quantumentanglement）。糾纏是一種純粹發(fā)生于量子系統(tǒng)的現(xiàn)象，在經(jīng)典力學(xué)里找不到類似的現(xiàn)象。2.4量子力學(xué)基本現(xiàn)象3貝爾不等式1964年，約翰·貝爾在其論文中根據(jù)定域性隱變量理論提出了貝爾不等式，對于兩個分隔的粒子同時被測量時其結(jié)果的可能關(guān)聯(lián)程度建立了一個嚴格的限制關(guān)系。而量子力學(xué)預(yù)言，在某些分離系統(tǒng)之間關(guān)聯(lián)的程度可以突破任何“定域?qū)嵲谛浴崩碚撝械南拗?，這表明量子力學(xué)是違背貝爾不等式的。量子算法與量子密碼導(dǎo)論量子線路模型一單比特量子門二兩比特量子門三量子通用門組四簡單量子算法本章內(nèi)容

3.1單比特量子門1單比特量子門表示常見的單比特量子門：單比特量子門即作用在單個量子比特上的幺正矩陣，在線路圖中通常表示為3.1單比特量子門1單比特量子門表示其他常見單比特門：相應(yīng)的，將量子線路中的U分別換成Y、Z、H、T、S即可。3.1單比特量子門1單比特量子門表示單比特旋轉(zhuǎn)門：3.1單比特量子門1單比特量子門表示單比特旋轉(zhuǎn)門：

3.2兩比特量子門1一般兩比特量子門兩比特量子門，即只涉及兩量子比特的幺正變換。例如兩比特交換門：3.2兩比特量子門2C-U兩比特量子門

3.2兩比特量子門2C-U兩比特量子門

其他控制兩比特門：3.3量子通用門組1多比特量子門

3.3量子通用門組1多比特量子門常見的Toffoli門思考：Toffoli門能用兩比特門表示嗎？3.3量子通用門組1多比特量子門Toffoli門等價線路

3.3量子通用門組2量子通用門組

3.3量子通用門組2量子通用門組

3.3量子通用門組2量子通用門組

使得其中3.3量子通用門組2量子通用門組

接下來構(gòu)造兩級幺正矩陣使得3.3量子通用門組2量子通用門組

接下來構(gòu)造兩級幺正矩陣使得3.3量子通用門組2量子通用門組

接下來按照上述規(guī)則依次構(gòu)造兩級幺正矩陣，使得

3.3量子通用門組2量子通用門組

分解成兩級幺正矩陣的乘積。3.3量子通用門組2量子通用門組

給定兩級幺正矩陣

3.3量子通用門組2量子通用門組

3.3量子通用門組2量子通用門組

3.3量子通用門組2量子通用門組

由于另外3.3量子通用門組2量子通用門組

3.4簡單量子算法1量子黑盒

3.4簡單量子算法2D-J算法Deutsch算法是首個展示了量子計算優(yōu)越性的玩具算法，該算法針對的是Deutsch問題設(shè)計的量子算法。Deutsch問題：給定函數(shù)判斷函數(shù)是常函數(shù)還是對稱函數(shù)。常函數(shù)：對稱函數(shù)：3.4簡單量子算法2D-J算法（1）經(jīng)過H操作，系統(tǒng)態(tài)演化為（2）經(jīng)過黑盒操作，系統(tǒng)態(tài)演化為3.4簡單量子算法2D-J算法（3）對第一個qubit施加H操作，系統(tǒng)態(tài)演化為3.4簡單量子算法2D-J算法結(jié)果分析（i）常函數(shù)時（ii）對稱函數(shù)時3.4簡單量子算法2D-J算法Deutsch-Jozsa問題：給定函數(shù)

，判斷函數(shù)是常函數(shù)還是對稱函數(shù)。常函數(shù)：或x為任意n比長常二進制串。對稱函數(shù)：所有n比特長二進制串中，有一半的x，其函數(shù)值為：另一半的x，其函數(shù)值為：算法所需qubit數(shù)：n+1

輸入態(tài)3.4簡單量子算法2D-J算法（1）經(jīng)過H門操作，系統(tǒng)態(tài)演化為（2）經(jīng)過黑盒操作，系統(tǒng)態(tài)演化為（3）對前n個qubit做H操作，系統(tǒng)態(tài)演化為3.4簡單量子算法2D-J算法結(jié)果分析（i）常函數(shù)時，前n個qubit測量只能得到全0態(tài)；（ii）對稱函數(shù)時，前n個qubit測量測得全0態(tài)的概率為0；因此，通過調(diào)用一次黑盒，即可判定函數(shù)的性質(zhì)！3.4簡單量子算法3BV算法1992年，Vazirani和Bernstein構(gòu)造了一種典型的數(shù)學(xué)問題，并提出了相應(yīng)的量子算法——BV算法。問題：給定未知二進制串

及函數(shù)若要確定

a

，需要調(diào)用幾次函數(shù)f（x）。算法所需qubit數(shù)：n+1

輸入態(tài)3.4簡單量子算法3BV算法（1）經(jīng)過H門操作，系統(tǒng)態(tài)演化為（2）經(jīng)過黑盒操作，系統(tǒng)態(tài)演化為（3）對前n個qubit做H操作，系統(tǒng)態(tài)演化為3.4簡單量子算法3BV算法結(jié)果分析（i），中態(tài)的概率幅為因此，通過調(diào)用一次黑盒，即可通過測量得到a的值?。╥i），。因此，。故3.4簡單量子算法4量子傅里葉變換經(jīng)典上的離散傅里葉變換是將一組復(fù)矢量

變換為另外一組復(fù)矢量

，其中量子傅里葉變換（QFT，用算子

表示）是經(jīng)典離散傅里葉變換的量子形式，量子傅里葉變換將量子態(tài)

變換為可證明

是幺正變換。3.4簡單量子算法4量子傅里葉變換

3.4簡單量子算法4量子傅里葉變換

3.4簡單量子算法5Simon算法給定函數(shù)

。要求：函數(shù)是下面兩種函數(shù)中的一種。（1）函數(shù)是一一映射函數(shù)，即輸入不同，函數(shù)值則不同；（2）函數(shù)是二對一的周期函數(shù)，即函數(shù)值相同當且僅當算法所需qubit數(shù)：2n

輸入態(tài)3.4簡單量子算法5Simon算法（1）經(jīng)過H門操作，系統(tǒng)態(tài)演化為（2）經(jīng)過黑盒操作，系統(tǒng)態(tài)演化為（3）對前n個qubit施加H門操作，系統(tǒng)態(tài)演化為3.4簡單量子算法5Simon算法結(jié)果分析（i）函數(shù)為一一映射時，系統(tǒng)態(tài)可以寫為測量得到的概率為3.4簡單量子算法5Simon算法結(jié)果分析（ii）函數(shù)為周期函數(shù)時，系統(tǒng)態(tài)可以寫為測量得到的滿足。3.4簡單量子算法6量子相位估計算法

算法所需qubit數(shù)：n+m

3.4簡單量子算法6量子相位估計算法（1）制備初始態(tài)（2）對前n個比特施加H門操作，系統(tǒng)態(tài)演化為3.4簡單量子算法6量子相位估計算法（3）對第一寄存器和第二寄存器施加黑盒操作3.4簡單量子算法6量子相位估計算法（4）對前n個比特做逆傅里葉變換，系統(tǒng)態(tài)演化為3.4簡單量子算法6量子相位估計算法（5）對前n個qubit在計算基矢下測量。結(jié)果分析：case1：

。顯然有這種情況下會確定性的測量得到case2：

。此時測量得到態(tài)

的概率為謝謝量子算法與量子密碼導(dǎo)論Shor算法及其應(yīng)用一RSA公鑰密碼算法二Shor算法三DH秘鑰交換協(xié)議四Shor算法在離散對數(shù)問題中的應(yīng)用本章內(nèi)容

4.1RSA公鑰密碼算法1RSA公鑰密碼算法1976年，Diffie與Hellman在其劃時代的論文《密碼學(xué)的新方向》一文中提出：可以利用單向函數(shù)設(shè)計一對密鑰，如果公開其中的一個（公鑰），并不會危害到另一個（私鑰）的秘密性質(zhì)。1978年，Rivest、Shamir、Adleman三人提出了著名的RSA公鑰密碼算法。4.1RSA公鑰密碼算法1RSA公鑰密碼算法在RSA算法中，包含了三個子算法：1.秘鑰產(chǎn)生算法：

4.1RSA公鑰密碼算法1RSA公鑰密碼算法在RSA算法中，包含了三個子算法：2.加密算法：

并將計算結(jié)果c通過公開通信渠道發(fā)送給A.4.1RSA公鑰密碼算法1RSA公鑰密碼算法在RSA算法中，包含了三個子算法：3.解密算法：

4.1RSA公鑰密碼算法2經(jīng)典整數(shù)分解算法

4.1RSA公鑰密碼算法2經(jīng)典整數(shù)分解算法

4.1RSA公鑰密碼算法2經(jīng)典整數(shù)分解算法

4.2Shor算法1Shor算法思想

4.2Shor算法2Shor算法流程

其中（1）制備初始態(tài)4.2Shor算法2Shor算法流程

（3）對兩個寄存器施加量子模冪操作

，系統(tǒng)態(tài)演化為4.2Shor算法2Shor算法流程

（5）對第一、第二寄存器施加計算基矢下的測量操作，由量子力學(xué)的測量假設(shè)可知，此時系統(tǒng)以一定概率塌縮為某個態(tài)。4.2Shor算法2Shor算法流程分析：系統(tǒng)塌縮為態(tài)

的概率是可以證明：

4.2Shor算法3模冪的量子線路實現(xiàn)思路：

通過量子加法器作為基本構(gòu)件構(gòu)造量子模加器，再由量子模加器作為基本構(gòu)件構(gòu)造控制量子模乘器，最后由控制量子模乘器作為基本構(gòu)件構(gòu)造量子模冪操作1量子加法器非進位加法模塊4.2Shor算法3模冪的量子線路實現(xiàn)1量子加法器進位模塊CARRY的線路如下圖4.2Shor算法3模冪的量子線路實現(xiàn)1量子加法器4.2Shor算法3模冪的量子線路實現(xiàn)3量子模加器練習(xí)：寫出后續(xù)量子態(tài)演化過程。4.2Shor算法3模冪的量子線路實現(xiàn)3量子控制模乘操作量子控制模乘操作實現(xiàn)以下功能4.2Shor算法3模冪的量子線路實現(xiàn)3量子控制模乘操作練習(xí)：寫出量子模乘操作中態(tài)的演化過程。4.2Shor算法3模冪的量子線路實現(xiàn)4量子模冪操作其中：前三條線表示x，下面兩部分初始時刻是1、0。4.3DH秘鑰交換協(xié)議1離散對數(shù)問題

4.3DH秘鑰交換協(xié)議2DH秘鑰交換協(xié)議DH秘鑰交換協(xié)議由Diffie和Hellman于1976年在其合作發(fā)表的論文《NewdirectionsinCryptography》中首先提出，同時這篇文章的發(fā)表也意味著公鑰密碼學(xué)思想的誕生。如何在公開信道中進行安全的秘鑰分發(fā)？4.3DH秘鑰交換協(xié)議2DH秘鑰交換協(xié)議DH秘鑰交換協(xié)議流程：

4.3DH秘鑰交換協(xié)議2DH秘鑰交換協(xié)議DH秘鑰交換協(xié)議流程：

A和B的秘鑰是一樣的嗎？秘鑰是安全的嗎？4.3DH秘鑰交換協(xié)議3經(jīng)典離散對數(shù)問題求解算法

4.3DH秘鑰交換協(xié)議3經(jīng)典離散對數(shù)問題求解算法（2）大步小步算法：

4.3DH秘鑰交換協(xié)議3經(jīng)典離散對數(shù)問題求解算法

4.4Shor算法在離散對數(shù)問題中的應(yīng)用1思想

4.4Shor算法在離散對數(shù)問題中的應(yīng)用2算法流程

（0）制備初始態(tài)

4.4Shor算法在離散對數(shù)問題中的應(yīng)用2算法流程

（3）對第一、第二寄存器分別施加量子傅里葉變換

，其中因此，系統(tǒng)狀態(tài)為4.4Shor算法在離散對數(shù)問題中的應(yīng)用2算法流程（4）對第一、第二、第三寄存器施加計算基矢下的測量操作。系統(tǒng)塌縮為態(tài)

的概率為可以證明，滿足

謝謝量子算法與量子密碼導(dǎo)論量子搜索算法及其應(yīng)用

一搜索算法原理及框架二搜索算法分析及示例三Grover算法與可滿足性問題四Grover算法求解代數(shù)方程組Grover算法與密鑰搜索本章內(nèi)容

5.1搜索算法原理及框架1背景搜索問題是一個基礎(chǔ)性問題，在計算機科學(xué)、密碼學(xué)等許多領(lǐng)域中，很多問題的求解均可規(guī)約為搜索問題，如路徑搜索、密鑰搜索、碰撞搜索等。理論上來說，一般的NP問題均可用搜索的思路進行求解。對于特定問題來說，搜索不一定是最有效的方法。很多問題自身存在特殊結(jié)構(gòu)，如果能夠充分利用問題特征，則可能得到更高效的求解方法。對于無結(jié)構(gòu)的搜索問題，如無序數(shù)據(jù)庫搜索，暴力窮舉可能是最優(yōu)的方法。5.1搜索算法原理及框架1量子Oracle與搜索問題給定一個輸出為0或1的函數(shù)可以將函數(shù)值存入一個輔助寄存器，構(gòu)造一個量子Oracle，即5.1搜索算法原理及框架1量子Oracle與搜索問題根據(jù)量子Oracle，可以給出搜索問題的形式化描述。搜索問題：給定計算未知函數(shù)的量子Oracle，找到滿足條件

的輸入。5.1搜索算法原理及框架2Grover搜索算法框架如果滿足要求的目標文件地址為z，則可以定義函數(shù)其中可以給出量子Oracle為5.1搜索算法原理及框架2Grover搜索算法框架將量子Oracle作用于量子態(tài)則只考慮地址寄存器，量子Oracle的作用可視為5.1搜索算法原理及框架2Grover搜索算法框架與一般的量子算法類似，制備初始等概率疊加態(tài)對應(yīng)Grover算法框架如圖5.1搜索算法原理及框架2Grover搜索算法框架在Grover算法中，核心的部分是Grover迭代過程，其線路實現(xiàn)如圖5.2所示。5.1搜索算法原理及框架3搜索算法的圖形描述量子Oracle的作用是在目標文件地址上翻轉(zhuǎn)相位，實現(xiàn)標記目標文件地址的功能。5.2搜索算法分析及示例1搜索算法的復(fù)雜度算法初始態(tài)為第一次迭代后，逆時針旋轉(zhuǎn)角，對應(yīng)量子態(tài)變?yōu)檫M行k次迭代后，量子態(tài)變?yōu)?.2搜索算法分析及示例1搜索算法的復(fù)雜度

這是迭代的終極目標5.2搜索算法分析及示例2搜索算法示例根據(jù)Grover算法流程，可以給出針對4個數(shù)據(jù)的Grover算法線路圖以k=3時的量子Oracle為例，目標數(shù)據(jù)編碼為11，則量子Oracle可以直接用一個Toffoli門實現(xiàn)。5.3Grover算法與可滿足性問題1概述在計算機科學(xué)、密碼學(xué)等許多領(lǐng)域中，布爾可滿足性問題的求解具有重要的理論和現(xiàn)實意義。此類問題的核心是確定是否存在賦值滿足給定的布爾公式。換句話說，對于給定布爾公式的變量，確定是否存在一種賦值方式，使得公式計算結(jié)果為True。如果存在，則該公式稱為可滿足的；如果不存在，也就是公式對于所有可能的賦值的計算結(jié)果都是False，則該公式稱為不可滿足的。這可以看作一個搜索問題，目標是在布爾公式的各種賦值中尋找賦值計算結(jié)果為True的方案。5.3Grover算法與可滿足性問題1概述Grover算法可用于加速任何NP完全問題的求解，但是如果對應(yīng)的NP完全問題包含內(nèi)部結(jié)構(gòu)，則直接利用Grover算法可能無法實現(xiàn)有效加速。雖然在3-SAT問題上直接利用Grover算法窮舉沒有意義，但相關(guān)方法可以應(yīng)用于更一般的情況（如k-SAT問題），對于某些特定問題，Grover算法可以勝過最優(yōu)經(jīng)典算法。此外，理論上Grover算法可以與經(jīng)典算法進行深度融合，以獲得比最優(yōu)經(jīng)典算法更好的加速效果。5.3Grover算法與可滿足性問題2SAT問題Exactly-13-SATproblem：找到一個真值指派，使得每個Clause中恰好有一個literal賦值為1，且函數(shù)值為1。f(x1,x2,x3)=(x1∨x2∨?x3)∧(?x1∨?x2∨?x3)∧(?x1∨x2∨x3)x1x2x3f0001第二Clause中3個literal為10010函數(shù)值為00101第一Clause中2個literal為10111第三Clause中3個literal為11000函數(shù)值為01011Y1101第一Clause中3個literal為11110函數(shù)值為05.3Grover算法與可滿足性問題2SAT問題先構(gòu)造子模塊：考慮函數(shù)f的每個Clause取值為1，且恰好一個literal賦值為1；組合所有Clause。例：(x1∨?x2∨x3)考慮y=x1

?x2

x3

(x1

?x2

x3)5.3Grover算法與可滿足性問題2SAT問題(x1∨x2∨?x3)

(?x1∨?x2∨?x3)

(?x1∨x2∨x3)y1=

x1

x2

?x3

(x1

x2

?x3)y2=

?x1

?x2

?x3

(?x1

?x2

?x3)y3=

?x1

x2

x3

(?x1

x2

x3)初始化子句1子句2子句35.3Grover算法與可滿足性問題2SAT問題退計算q45.3Grover算法與可滿足性問題2SAT問題5.3Grover算法與可滿足性問題2SAT問題5.3Grover算法與可滿足性問題2SAT問題5.4Grover算法求解代數(shù)方程組1代數(shù)方程組問題代數(shù)攻擊在公鑰密碼、分組密碼和序列密碼分析領(lǐng)域，甚至在雜湊函數(shù)碰撞攻擊領(lǐng)域都有成功應(yīng)用，已經(jīng)發(fā)展成為一種重要的通用密碼分析方法。代數(shù)攻擊通過分析密碼算法的內(nèi)部結(jié)構(gòu)，構(gòu)建多變元高次代數(shù)方程組，利用求解方程組開展密碼分析。代數(shù)方程組的求解是一個困難問題，利用Grover算法可以暴力窮舉求解代數(shù)方程組。當然，這種方法并非最優(yōu)方法，這里只是以代數(shù)方程組為例，探索量子搜索算法如何直接應(yīng)用于密碼分析中的基礎(chǔ)數(shù)學(xué)問題。5.4Grover算法求解代數(shù)方程組1代數(shù)方程組問題以二元域上的代數(shù)方程組為例，給定如下方程組這是一個四變元的方程組，如果采用窮舉搜索算法求解，相當于在0000,…,1111這16個四比特的序列中找到同時滿足4個方程的解。利用Grover算法搜索方程組的解，核心是構(gòu)造一個能夠標記方程組正確解的量子Oracle。5.4Grover算法求解代數(shù)方程組1代數(shù)方程組問題以第二個方程

為例，可以用量子線路實現(xiàn)，如圖所示。5.4Grover算法求解代數(shù)方程組1代數(shù)方程組問題類似地，可以給出整個方程組的可逆線路5.4Grover算法求解代數(shù)方程組2搜索方程組解的量子線路5.4Grover算法求解代數(shù)方程組2搜索方程組解的量子線路單次迭代輸出結(jié)果如圖所示，從圖中可以看出，對于單次迭代算法，執(zhí)行1024

次后，得到正確解0110的次數(shù)約為480次，也就是說，成功概率約為0.469。5.5Grover算法與密鑰搜索1AES算法AES（AdvancedEncryptionStandard，高級加密標準）是一種典型的對稱密碼算法。AES是一種面向字節(jié)的算法，以AES-128為例，其以128位的明文塊和128位的密鑰塊作為輸入，并生成相同大小的密文塊。AES-128的狀態(tài)（State）可以用一個4×4的矩陣描述，矩陣每個元素代表1字節(jié)（8位）。5.5Grover算法與密鑰搜索1AES算法AES的每一輪加密可以分為SubBytes（字節(jié)代換）、ShiftRows（行移位）、MixColumns（列混合）及AddRoundKey（輪密鑰加）4個步驟，其中，前3個步驟分別以字節(jié)、行和列為單位進行數(shù)據(jù)處理，可并行計算。5.5Grover算法與密鑰搜索2Grover算法搜索AES密鑰框架密鑰搜索的目標是通過給定的明密文對，尋找用于加密的密鑰。從Grover算法框架來看，相位翻轉(zhuǎn)等模塊是基本固定的。因此，利用Grover算法搜索AES密鑰，核心是給出能夠標記正確密鑰的量子Oracle，本質(zhì)上需要設(shè)計AES加密（解密）算法的量子線路。先考慮簡化情況，對于AES-128，其量子Oracle實現(xiàn)框架如圖所示。5.5Grover算法與密鑰搜索2Grover算法搜索AES密鑰框架從量子Oracle的功能結(jié)構(gòu)可以看出，為實現(xiàn)標記正確密鑰的功能，關(guān)鍵是要給出AES加密過程的可逆實現(xiàn)，也就是在量子線路模型下，實現(xiàn)AES的加密過程。這樣能夠?qū)ΟB加態(tài)的密鑰進行并行處理，從而加速密鑰搜索過程。結(jié)合AES算法的流程可以看出，最為關(guān)鍵的是給出SubBytes、ShiftRows、MixColumns及AddRoundKey這4個步驟在量子線路上的可逆實現(xiàn)。5.5Grover算法與密鑰搜索3AES算法的可逆實現(xiàn)利用Grover算法搜索AES密鑰，核心是AES的可逆實現(xiàn)，主要資源消耗是SubBytes操作，本質(zhì)問題是有效的求有限域上元素的逆元。

需要構(gòu)造有限域上元素模平方運算量子線路5.5Grover算法與密鑰搜索3AES算法的可逆實現(xiàn)

5.5Grover算法與密鑰搜索3AES算法的可逆實現(xiàn)圖中每一個虛線框的編號，恰好對應(yīng)矩陣分解式中主對角線之外非零元所在的行，含幾個非零元就執(zhí)行幾個CNOT門操作。前6個虛線框?qū)?yīng)上三角矩陣操作，后2

個虛線框則對應(yīng)下三角矩陣操作。從圖中可以看出，利用12個CNOT門，不需要輔助比特，即可實現(xiàn)有限域上元素的平方運算。謝謝量子算法與量子密碼導(dǎo)論量子密鑰分發(fā)技術(shù)

一量子信息論基礎(chǔ)二QKD協(xié)議三QKD協(xié)議理論安全性四QKD系統(tǒng)組成及實際安全性本章內(nèi)容

6.1量子信息論基礎(chǔ)1背景量子信息技術(shù)除了可用于量子計算進行密碼分析之外，還可以用于進行信息加密。有別于傳統(tǒng)的加密技術(shù)，量子加密技術(shù)不在依賴于計算困難的數(shù)學(xué)問題，其利用量子力學(xué)基本原理對信息進行加密，從物理機制上保障信息的安全性。在諸多量子加密技術(shù)中，量子密鑰分發(fā)（quantumkeydistribution，QKD）技術(shù)受到關(guān)注最多也最為成熟。QKD理論上實現(xiàn)密鑰在遠距離通信雙方之間的安全分配，結(jié)合“一次一密”加密方法，理論上可以實現(xiàn)無條件安全的信息傳遞。因此，自1984年首次提出以來，經(jīng)過了30多年的發(fā)展，QKD理論及實驗得到了長足的進步。多種多樣的QKD協(xié)議層出不窮，相應(yīng)的安全性分析也不斷完善。與此同時，QKD實驗發(fā)展迅速，通信距離也在不斷增大。量子網(wǎng)絡(luò)及量子衛(wèi)星相繼出現(xiàn)，標志著QKD技術(shù)逐漸走出實驗室，向著實用化方向邁進。6.1量子信息論基礎(chǔ)1經(jīng)典信息論基礎(chǔ)經(jīng)典香農(nóng)熵6.1量子信息論基礎(chǔ)1經(jīng)典信息論基礎(chǔ)經(jīng)典香農(nóng)熵性質(zhì)6.1量子信息論基礎(chǔ)1經(jīng)典信息論基礎(chǔ)經(jīng)典相對熵6.1量子信息論基礎(chǔ)1經(jīng)典信息論基礎(chǔ)經(jīng)典聯(lián)合熵6.1量子信息論基礎(chǔ)1經(jīng)典信息論基礎(chǔ)經(jīng)典條件熵6.1量子信息論基礎(chǔ)1經(jīng)典信息論基礎(chǔ)互信息6.1量子信息論基礎(chǔ)1經(jīng)典信息論基礎(chǔ)維恩圖：互信息和各種熵之間的關(guān)系6.1量子信息論基礎(chǔ)1量子信息論基礎(chǔ)量子馮·諾伊曼熵6.1量子信息論基礎(chǔ)1量子信息論基礎(chǔ)量子聯(lián)合熵6.1量子信息論基礎(chǔ)1量子信息論基礎(chǔ)量子相對熵6.1量子信息論基礎(chǔ)1量子信息論基礎(chǔ)量子互信息6.1量子信息論基礎(chǔ)1量子信息論基礎(chǔ)Holevo界6.1量子信息論基礎(chǔ)1量子信息論基礎(chǔ)信道模型——比特翻轉(zhuǎn)信道6.1量子信息論基礎(chǔ)1量子信息論基礎(chǔ)信道模型——退極化信道6.1量子信息論基礎(chǔ)1量子信息論基礎(chǔ)信道模型——幅值阻尼信道6.1量子信息論基礎(chǔ)1量子信息論基礎(chǔ)信道模型——幅值阻尼信道6.1量子信息論基礎(chǔ)1量子信息論基礎(chǔ)信道模型——相位阻尼信道6.2量子密鑰分發(fā)協(xié)議1協(xié)議框架QKD發(fā)送設(shè)備QKD接收設(shè)備經(jīng)典信道量子信道（a）基于制備測量QKD方案信道示意圖AliceBob糾纏源量子信道量子信道經(jīng)典信道（b）基于糾纏QKD方案信道示意圖幾乎所有QKD協(xié)議框架中，均存在量子信道和經(jīng)典信道兩種信道，其中量子信道用于傳輸量子信息，經(jīng)典信道用于傳輸量子態(tài)制備、測量所選擇基矢等信息。經(jīng)典信道中傳輸?shù)男畔⑼耆_，任何人都可以隨意獲取。6.2量子密鑰分發(fā)協(xié)議1協(xié)議分類按照使用的物理資源分類，QKD協(xié)議可以大致分為糾纏光子QKD協(xié)議、單光子QKD協(xié)議和連續(xù)變量QKD協(xié)議三類。1.糾纏光子QKD協(xié)議。

該類協(xié)議利用量子糾纏和經(jīng)典通信實現(xiàn)高安全性密鑰生成與分發(fā)，主要代表為Ekert在1991年提出的E91協(xié)議；2.單光子QKD協(xié)議。

該類協(xié)議利用單光子的偏振或相位傳遞密鑰信息，主要包括1984年Bennett和Brassard共同提出的BB84協(xié)議、1992年Bennett提出了B92協(xié)議、六態(tài)協(xié)議及SARG04協(xié)議等；3.連續(xù)變量QKD協(xié)議。

該類協(xié)議主要包括基于高斯調(diào)制的壓縮態(tài)協(xié)議和基于相干態(tài)的平衡零拍探測協(xié)議等。6.2量子密鑰分發(fā)協(xié)議1基于糾纏光子的QKD協(xié)議基于糾纏光子的QKD協(xié)議中，最為知名