量子算法與量子密碼導(dǎo)論 課件 第3章 量子線路模型

量子算法與量子密碼導(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算法是首個展示了量子計(jì)算優(yōu)越性的玩具算法，該算法針對的是Deutsch問題設(shè)計(jì)的量子算法。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比長常二進(jìn)制串。對稱函數(shù)：所有n比特長二進(jì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算法。問題：給定未知二進(jìn)制串

及函數(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ù)值相同當(dāng)且僅當(dāng)算法所需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量子相位估計(jì)算法

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

3.4簡單量子算法6量子相位估計(jì)算法（1）制備初始態(tài)（2）對前n個比特施加H門操作，系統(tǒng)態(tài)演化為3.4簡單量子算法6量子相位估計(jì)算法（3）對第一寄存器和第二寄存器施加黑盒操作3.4簡單量子算法6量子相位估計(jì)算法（4）對前n個比特做逆傅里葉變換，系