量子算法與量子密碼導論第1章

量子線路模型第2章

量子力學基礎第3章

量子線路模型第4章Shor算法及其應用第5章

量子搜索算法及其應用第6章

量子線路模型全套可編輯PPT課件

量子算法與量子密碼導論量子線路模型

一古典密碼二現代密碼三量子計算對現代密碼的影響四后量子時代密碼本章內容

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

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

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

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

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

本課件是可編輯的正常PPT課件2.1量子力學革命1兩次量子力學革命上世紀末以來，第二次量子科技革命在信息技術領域興起，如今已接近產業化階段在上世紀40年代興起第一次量子科技革命，催生了原子彈、半導體晶體管、激光器等重要成果本課件是可編輯的正常PPT課件2.1量子力學革命2黑體輻射—量子的誕生馬克斯·普朗克于1900年建立了黑體輻射定律的公式

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

其中左矢

讀作bra，a*和

b*分別為

a和

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

任意一個二維列向量子態記作

其中

a和

b都是復數，且符號

為狄拉克符號的右矢，讀作ket本課件是可編輯的正常PPT課件2.2量子力學數學基礎1線性空間—內積內積在量子力學中，對于向量

和

，它們內積形式如下：其結果是一個復數反過來，向量

和

的內積為

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

本課件是可編輯的正常PPT課件2.2量子力學數學基礎1內積的性質內積當兩個向量的內積是一個實數時，有特別的，當兩個向量的內積為0時，即稱這兩個向量正交本課件是可編輯的正常PPT課件2.2量子力學數學基礎1內積的性質內積向量與它自身的內積為其結果的平方根

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

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

A:V

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

，有

則稱A為線性空間V上的線性算子本課件是可編輯的正常PPT課件2.2量子力學數學基礎2線性算子—厄米算子與幺正算子泡利算子：厄米算子：其轉置復共軛等于它本身，即幺正算子：其轉置共軛等于它的逆，即顯然，四個泡利算子也都是幺正算子本課件是可編輯的正常PPT課件2.2量子力學數學基礎2線性算子—外積在量子力學中有一種非常有用的表示線性算子的方法，即外積表示法。對于向量

和

，其外積為其結果是一個線性算子可用于構造測量算子，尤其是投影算子本課件是可編輯的正常PPT課件2.2量子力學數學基礎3本征值與本征態當線性算子A對線性空間

V中向量

v的作用是v的倍數時，

則稱

為的

A本征值，v為

A對應于本征值

的本征態由本征值與本征態的定義可得

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

本課件是可編輯的正常PPT課件2.2量子力學數學基礎3本征值與本征態例.求泡利算子

的本征值和本征態

解：

本征方程為本征方程

解得本征值為

本課件是可編輯的正常PPT課件2.2量子力學數學基礎3本征值與本征態同理可得：

因此，歸一化后得：

令

為對應于本征值

的本征態，則

本課件是可編輯的正常PPT課件2.2量子力學數學基礎3正規算子定理：若

A是正規算子，則其對應不同本征值的本征態是正交的定義：若算子A滿足

，則稱

A為正規算子

簡并：對應于同一本征值的多個不同的本征態稱為簡并態本課件是可編輯的正常PPT課件2.2量子力學數學基礎3譜分解定理及推論譜分解定理：A是一個正規算子，其本征值及相對應的本征態分別為

和

，則

A可以分解為

推論：對于正規算子A，有

若算子A可逆，則有

對于任意自然數n都成立本課件是可編輯的正常PPT課件2.2量子力學數學基礎3正規算子函數

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

f(A)為正規算子函數，且有

例如

，求解：本課件是可編輯的正常PPT課件2.2量子力學數學基礎4張量積特別的，若

、

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

是

中的正交基，通常簡記為

或定義

：設V、W分別是

n維和

m

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

是由張量積

構成的nm維線性空間，張量積

是在空間

上的線性算子，有本課件是可編輯的正常PPT課件2.2量子力學數學基礎4張量積的計算假定線性算子A、B在空間V、W中n×n、m×m的矩陣，則

例如，本課件是可編輯的正常PPT課件2.3量子力學基本假設1波函數假設微觀物理系統的狀態由一個波函數完全描述。

如果一個微觀系統包含若干個粒子，而這些粒子又是按照量子力學的規律運動的話，則稱此系統處于某種量子狀態，簡稱量子態。波函數是粒子位置和時間的復函數，當一個微觀系統的波函數確定時，該系統的全部性質都可以由此得出，即波函數表征了系統的量子態。本課件是可編輯的正常PPT課件2.3量子力學基本假設2量子態演化假設封閉量子系統量子態的演化由薛定諤方程描述

本課件是可編輯的正常PPT課件2.3量子力學基本假設3算子假設量子力學中的可觀測量由厄米算子來表示。這里的可觀測量是指可通過物理實驗得到測量結果的量，它對應于經典理論中的力學量。如果算子描述對應于力學量，那么當系統處于某個本征態時，則力學量有確定值，即該本征態所對應的本征值。

本課件是可編輯的正常PPT課件2.3量子力學基本假設4測量假設若算子F為量子力學中的一個力學量，其正交歸一化本征函數為，對應的概率為cn，則任一量子態可表示為：當對一個量子體系進行某一力學量的測量時，測量結果一定為該力學量算子的本征值當中的某一個，測量結果為的概率為，當測量完成后，該量子體系塌縮至量子態。

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

本課件是可編輯的正常PPT課件3.1單比特量子門1單比特量子門表示常見的單比特量子門：單比特量子門即作用在單個量子比特上的幺正矩陣，在線路圖中通常表示為本課件是可編輯的正常PPT課件3.1單比特量子門1單比特量子門表示其他常見單比特門：相應的，將量子線路中的U分別換成Y、Z、H、T、S即可。本課件是可編輯的正常PPT課件3.1單比特量子門1單比特量子門表示單比特旋轉門：本課件是可編輯的正常PPT課件3.1單比特量子門1單比特量子門表示單比特旋轉門：

本課件是可編輯的正常PPT課件3.2兩比特量子門1一般兩比特量子門兩比特量子門，即只涉及兩量子比特的幺正變換。例如兩比特交換門：本課件是可編輯的正常PPT課件3.2兩比特量子門2C-U兩比特量子門

本課件是可編輯的正常PPT課件3.2兩比特量子門2C-U兩比特量子門

其他控制兩比特門：本課件是可編輯的正常PPT課件3.3量子通用門組1多比特量子門

本課件是可編輯的正常PPT課件3.3量子通用門組1多比特量子門常見的Toffoli門思考：Toffoli門能用兩比特門表示嗎？本課件是可編輯的正常PPT課件3.3量子通用門組1多比特量子門Toffoli門等價線路

本課件是可編輯的正常PPT課件3.3量子通用門組2量子通用門組

本課件是可編輯的正常PPT課件3.3量子通用門組2量子通用門組

本課件是可編輯的正常PPT課件3.3量子通用門組2量子通用門組

使得其中本課件是可編輯的正常PPT課件3.3量子通用門組2量子通用門組

接下來構造兩級幺正矩陣使得本課件是可編輯的正常PPT課件3.3量子通用門組2量子通用門組

接下來構造兩級幺正矩陣使得本課件是可編輯的正常PPT課件3.3量子通用門組2量子通用門組

接下來按照上述規則依次構造兩級幺正矩陣，使得

本課件是可編輯的正常PPT課件3.3量子通用門組2量子通用門組

分解成兩級幺正矩陣的乘積。本課件是可編輯的正常PPT課件3.3量子通用門組2量子通用門組

給定兩級幺正矩陣

本課件是可編輯的正常PPT課件3.3量子通用門組2量子通用門組

本課件是可編輯的正常PPT課件3.3量子通用門組2量子通用門組

本課件是可編輯的正常PPT課件3.3量子通用門組2量子通用門組

由于另外本課件是可編輯的正常PPT課件3.3量子通用門組2量子通用門組

本課件是可編輯的正常PPT課件3.4簡單量子算法1量子黑盒

本課件是可編輯的正常PPT課件3.4簡單量子算法2D-J算法Deutsch算法是首個展示了量子計算優越性的玩具算法，該算法針對的是Deutsch問題設計的量子算法。Deutsch問題：給定函數判斷函數是常函數還是對稱函數。常函數：對稱函數：本課件是可編輯的正常PPT課件3.4簡單量子算法2D-J算法（1）經過H操作，系統態演化為（2）經過黑盒操作，系統態演化為本課件是可編輯的正常PPT課件3.4簡單量子算法2D-J算法（3）對第一個qubit施加H操作，系統態演化為本課件是可編輯的正常PPT課件3.4簡單量子算法2D-J算法結果分析（i）常函數時（ii）對稱函數時本課件是可編輯的正常PPT課件3.4簡單量子算法2D-J算法Deutsch-Jozsa問題：給定函數

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

輸入態本課件是可編輯的正常PPT課件3.4簡單量子算法2D-J算法（1）經過H門操作，系統態演化為（2）經過黑盒操作，系統態演化為（3）對前n個qubit做H操作，系統態演化為本課件是可編輯的正常PPT課件3.4簡單量子算法2D-J算法結果分析（i）常函數時，前n個qubit測量只能得到全0態；（ii）對稱函數時，前n個qubit測量測得全0態的概率為0；因此，通過調用一次黑盒，即可判定函數的性質！本課件是可編輯的正常PPT課件3.4簡單量子算法3BV算法1992年，Vazirani和Bernstein構造了一種典型的數學問題，并提出了相應的量子算法——BV算法。問題：給定未知二進制串

及函數若要確定

a

，需要調用幾次函數f（x）。算法所需qubit數：n+1

輸入態本課件是可編輯的正常PPT課件3.4簡單量子算法3BV算法（1）經過H門操作，系統態演化為（2）經過黑盒操作，系統態演化為（3）對前n個qubit做H操作，系統態演化為本課件是可編輯的正常PPT課件3.4簡單量子算法3BV算法結果分析（i），中態的概率幅為因此，通過調用一次黑盒，即可通過測量得到a的值！（ii），。因此，。故本課件是可編輯的正常PPT課件3.4簡單量子算法4量子傅里葉變換經典上的離散傅里葉變換是將一組復矢量

變換為另外一組復矢量

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

表示）是經典離散傅里葉變換的量子形式，量子傅里葉變換將量子態

變換為可證明

是幺正變換。本課件是可編輯的正常PPT課件3.4簡單量子算法4量子傅里葉變換

本課件是可編輯的正常PPT課件3.4簡單量子算法4量子傅里葉變換

本課件是可編輯的正常PPT課件3.4簡單量子算法5Simon算法給定函數

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

輸入態本課件是可編輯的正常PPT課件3.4簡單量子算法5Simon算法（1）經過H門操作，系統態演化為（2）經過黑盒操作，系統態演化為（3）對前n個qubit施加H門操作，系統態演化為本課件是可編輯的正常PPT課件3.4簡單量子算法5Simon算法結果分析（i）函數為一一映射時，系統態可以寫為測量得到的概率為本課件是可編輯的正常PPT課件3.4簡單量子算法5Simon算法結果分析（ii）函數為周期函數時，系統態可以寫為測量得到的滿足。本課件是可編輯的正常PPT課件3.4簡單量子算法6量子相位估計算法

算法所需qubit數：n+m

本課件是可編輯的正常PPT課件3.4簡單量子算法6量子相位估計算法（1）制備初始態（2）對前n個比特施加H門操作，系統態演化為本課件是可編輯的正常PPT課件3.4簡單量子算法6量子相位估計算法（3）對第一寄存器和第二寄存器施加黑盒操作本課件是可編輯的正常PPT課件3.4簡單量子算法6量子相位估計算法（4）對前n個比特做逆傅里葉變換，系統態演化為本課件是可編輯的正常PPT課件3.4簡單量子算法6量子相位估計算法（5）對前n個qubit在計算基矢下測量。結果分析：case1：

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

。此時測量得到態

的概率為本課件是可編輯的正常PPT課件謝謝量子算法與量子密碼導論Shor算法及其應用一RSA公鑰密碼算法二Shor算法三DH秘鑰交換協議四Shor算法在離散對數問題中的應用本章內容

本課件是可編輯的正常PPT課件4.1RSA公鑰密碼算法1RSA公鑰密碼算法1976年，Diffie與Hellman在其劃時代的論文《密碼學的新方向》一文中提出：可以利用單向函數設計一對密鑰，如果公開其中的一個（公鑰），并不會危害到另一個（私鑰）的秘密性質。1978年，Rivest、Shamir、Adleman三人提出了著名的RSA公鑰密碼算法。本課件是可編輯的正常PPT課件4.1RSA公鑰密碼算法1RSA公鑰密碼算法在RSA算法中，包含了三個子算法：1.秘鑰產生算法：

本課件是可編輯的正常PPT課件4.1RSA公鑰密碼算法1RSA公鑰密碼算法在RSA算法中，包含了三個子算法：2.加密算法：

并將計算結果c通過公開通信渠道發送給A.本課件是可編輯的正常PPT課件4.1RSA公鑰密碼算法1RSA公鑰密碼算法在RSA算法中，包含了三個子算法：3.解密算法：

本課件是可編輯的正常PPT課件4.1RSA公鑰密碼算法2經典整數分解算法

本課件是可編輯的正常PPT課件4.1RSA公鑰密碼算法2經典整數分解算法

本課件是可編輯的正常PPT課件4.1RSA公鑰密碼算法2經典整數分解算法

本課件是可編輯的正常PPT課件4.2Shor算法1Shor算法思想

本課件是可編輯的正常PPT課件4.2Shor算法2Shor算法流程

其中（1）制備初始態本課件是可編輯的正常PPT課件4.2Shor算法2Shor算法流程

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

，系統態演化為本課件是可編輯的正常PPT課件4.2Shor算法2Shor算法流程

（5）對第一、第二寄存器施加計算基矢下的測量操作，由量子力學的測量假設可知，此時系統以一定概率塌縮為某個態。本課件是可編輯的正常PPT課件4.2Shor算法2Shor算法流程分析：系統塌縮為態

的概率是可以證明：

本課件是可編輯的正常PPT課件4.2Shor算法3模冪的量子線路實現思路：

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

本課件是可編輯的正常PPT課件4.3DH秘鑰交換協議2DH秘鑰交換協議DH秘鑰交換協議由Diffie和Hellman于1976年在其合作發表的論文《NewdirectionsinCryptography》中首先提出，同時這篇文章的發表也意味著公鑰密碼學思想的誕生。如何在公開信道中進行安全的秘鑰分發？本課件是可編輯的正常PPT課件4.3DH秘鑰交換協議2DH秘鑰交換協議DH秘鑰交換協議流程：

本課件是可編輯的正常PPT課件4.3DH秘鑰交換協議2DH秘鑰交換協議DH秘鑰交換協議流程：

A和B的秘鑰是一樣的嗎？秘鑰是安全的嗎？本課件是可編輯的正常PPT課件4.3DH秘鑰交換協議3經典離散對數問題求解算法

本課件是可編輯的正常PPT課件4.3DH秘鑰交換協議3經典離散對數問題求解算法（2）大步小步算法：

本課件是可編輯的正常PPT課件4.3DH秘鑰交換協議3經典離散對數問題求解算法

本課件是可編輯的正常PPT課件4.4Shor算法在離散對數問題中的應用1思想

本課件是可編輯的正常PPT課件4.4Shor算法在離散對數問題中的應用2算法流程

（0）制備初始態

本課件是可編輯的正常PPT課件4.4Shor算法在離散對數問題中的應用2算法流程

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

，其中因此，系統狀態為本課件是可編輯的正常PPT課件4.4Shor算法在離散對數問題中的應用2算法流程（4）對第一、第二、第三寄存器施加計算基矢下的測量操作。系統塌縮為態

的概率為可以證明，滿足

本課件是可編輯的正常PPT課件謝謝量子算法與量子密碼導論量子搜索算法及其應用

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

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

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

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

?x2

x3

(x1

?x2

x3)本課件是可編輯的正常PPT課件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子句3本課件是可編輯的正常PPT課件5.3Grover算法與可滿足性問題2SAT問題退計算q4本課件是可編輯的正常PPT課件5.3Grover算法與可滿足性問題2SAT問題本課件是可編輯的正常PPT課件5.3Grover算法與可滿足性問題2SAT問題本課件是可編輯的正常PPT課件5.3Grover算法與可滿足性問題2SAT問題本課件是可編輯的正常PPT課件5.4Grover算法求解代數方程組1代數方程組問題代數攻擊在公鑰密碼、分組密碼和序列密碼分析領域，甚至在雜湊函數碰撞攻擊領域都有成功應用，已經發展成為一種重要的通用密碼分析方法。代數攻擊通過分析密碼算法的內部結構，構建多變元高次代數方程組，利用求解方程組開展密碼分析。代數方程組的求解是一個困難問題，利用Grover算法可以暴力窮舉求解代數方程組。當然，這種方法并非最優方法，這里只是以代數方程組為例，探索量子搜索算法如何直接應用于密碼分析中的基礎數學問題。本課件是可編輯的正常PPT課件5.4Grover算法求解代數方程組1代數方程組問題以二元域上的代數方程組為例，給定如下方程組這是一個四變元的方程組，如果采用窮舉搜索算法求解，相當于在0000,…,1111這16個四比特的序列中找到同時滿足4個方程的解。利用Grover算法搜索方程組的解，核心是構造一個能夠標記方程組正確解的量子Oracle。本課件是可編輯的正常PPT課件5.4Grover算法求解代數方程組1代數方程組問題以第二個方程

為例，可以用量子線路實現，如圖所示。本課件是可編輯的正常PPT課件5.4Grover算法求解代數方程組1代數方程組問題類似地，可以給出整個方程組的可逆線路本課件是可編輯的正常PPT課件5.4Grover算法求解代數方程組2搜索方程組解的量子線路本課件是可編輯的正常PPT課件5.4Grover算法求解代數方程組2搜索方程組解的量子線路單次迭代輸出結果如圖所示，從圖中可以看出，對于單次迭代算法，執行1024

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

需要構造有限域上元素模平方運算量子線路本課件是可編輯的正常PPT課件5.5Grover算法與密鑰搜索3AES算法的可逆實現

本課件是可編輯的正常PPT課件5.5Grover算法與密鑰搜索3AES算法的可逆實現圖中每一個虛線框的編號，恰好對應矩陣分解式中主對角線之外非零元所在的行，含幾個非零元就執行幾個CNOT門操作。前6個虛線框對應上三角矩陣操作，后2

個虛線框則對應下三角矩陣操作。從圖中可以看出，利用12個CNOT門，不需要輔助比特，即可實現有限域上元素的平方運算。本課件是可編輯的正常PPT課件謝謝量子算法與量子密碼導論量子密鑰分發技術

一量子信息論基礎二QKD協議三QKD協議理論安全性四QKD系統組成及實際安全性本章內容

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

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

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

該類協議主要包括基于高斯調制的壓縮態協議和基于相干態的平衡零拍