量子信息學引論第8講

1、1,清華大學 2012.11.7,Introduction to Quantum Information Science,第8講,量子信息學引論,1,2,第四章 量子線路,描述進行量子計算所需的基本元件和基本操作 4.1 量子算法 4.2 單量子位操作 4.3 受控操作 4.4 測量 4.5 普適量子門 4.6 量子計算線路模型總結(jié) 4.7 量子系統(tǒng)模擬,2,3,前節(jié)課總結(jié),單量子位操作，受控操作，測量,3,CNOT,CU,Z,CP,4,4.5 普適量子門Universal quantum gates,4.5.1 兩級(two-level)酉門是普適的 4.5.2 單量子位門與CNOT門是普適

2、的 4.5.3 普適操作的一個離散集 4.5.4 近似任意的酉門一般是困難的 4.5.5 量子計算復雜性,4,5,普適門的集合,什么是普適門？ 經(jīng)典線路中可由一組有限個邏輯門來計算任意函數(shù)。稱這一組邏輯門為普適的。例如：AND，OR，NOT 對于量子線路，如果任意的酉操作都可用一個集合中的門構(gòu)成的線路來近似，且可達到任意精度，則稱此集合中的門對于量子計算是普適的。例如：H，CNOT，S，T,5,6,4.5.3 普適運算的一個離散集合,上節(jié)證明了受控非門與單量子位酉操作一起構(gòu)成了量子計算的普適集。 尚不知如何實現(xiàn)具有抗錯(error-resistant) 能力的這些門的簡單方法。 幸運的是，本節(jié)

3、將找出一個用來執(zhí)行通用量子計算的門的離散集合。且這些門操作能在抗錯的形式下執(zhí)行。,6,7,對酉算子近似,為什么要近似？ 酉算子的集合是連續(xù)的。 門的離散集合不可能精確實現(xiàn)任意的酉運算。,7,8,對酉算子的近似,設(shè)U和V是在同一狀態(tài)空間上的兩個酉算子，U是希望實現(xiàn)的酉算子，V是實際實現(xiàn)了的酉算子。定義實現(xiàn)過程的誤差為 其中最大運算取遍狀態(tài)空間中所有量子狀態(tài)| 。,8,9,對酉算子的近似,前面的定義有一個合理的解釋： 如果E(U,V ) 測量后輸出的概率為PU，測量V|y后得到的概率為PV，那么它們的相差不會超過2e，也就是對任意POVM算子M，我們有：,9,10,證明,設(shè),那么,由于,11,酉算

4、子的近似,更進一步說，如果用一系列的門V1,Vm來近似U1,Um,則誤差是線性相加的： 為了使近似線路得到的結(jié)果在正確概率的一個允許量0以內(nèi)，則只需要保證：,11,12,門的普適性,1、Hadamard, CNOT, phase, p/8 2、Hadamard, CNOT, phase, Toffoli,這些門都可提供容錯設(shè)計。但是后者并不太吸引人 第十章會證明。,13,H + Phase + CNOT + T 門的普適性, Hadamard, CNOT, phase, p/8 ,下面我們來證明下面的集合是普適的：,我們可以證明除了一個全局相位，下面的的等式是成立的：,13,14,把前面的等式

5、結(jié)合則可得到：,用H和T門構(gòu)造,14,即僅利用T門和H 門就可以構(gòu)造出 ， 可以證明q是2p的無理倍數(shù)。,其中q由cos(q/2) cos2(p /8)給出。,繞著給定軸轉(zhuǎn)q角，這里,15,重復迭代則可用 以任意精度近似任意的旋轉(zhuǎn)算子 。 證明： 定義qk，使得qk0, 2p），且對于k=1, N (整數(shù) N 2p/d所需精度)，qk=(kq)mod2p。則根據(jù)鴿籠原理，存在不同的j 和k (Nkj)使得 |qk qj|2p/N 這也就意味著：0|qk-j| 2p/N,用 近似任意旋轉(zhuǎn),15,16,因此，序列 qk-j，q2(k-j) ，q3(k-j) , 可填滿區(qū)間0, 2p) 這樣對于任意

6、e 0，可以找到n使得,用 近似任意旋轉(zhuǎn),16,17,簡單的代數(shù)運算可以證明： 其中 是個如下的單位矢量： 我們同樣可得：,用 近似任意旋轉(zhuǎn),17,18,根據(jù)練習4.11任意的酉算子可以分解成： 則選擇合適的n1,n2,n3，根據(jù)誤差累計原則可以得到： 這就是說任意的單量子位酉算子U，可以僅用 Hadamard 和p/8門組成的線路，近似到指定的誤差e以內(nèi)。,單量子位U可用 Hadamard 和p/8門精確近似,18,19,任意的單量子位酉算子U，可以僅用 Hadamard 和p/8門組成的線路，近似到任意精度。前面已證明了受控非門和單比特酉門是普適的。這樣就證明我們可以用 Hadamard,

7、 CNOT和p/8 門近似含有m個門的量子線路。 也就是說Hadamard, CNOT和p/8 組成了一個量子線路的普適集。,Hadamard, CNOT和p/8 組成了量子線路的普適集,19,20,根據(jù)Solovay和Kitaev定理對任意單比特門近似到精度e, 需要 O(logc(1/e) 個門, c大約等于2。 近似含有m個門的線路(精度e)，則需要 O (mlogc(m/e) 個門。 需要的近似線路隨原線路成多重對數(shù)增長。對實際應(yīng)用是可以接受的。,近似的效率,20,21,4.5.4 近似任意的酉門一般是困難的,在n個量子位上的任意酉變換都可用一個小的離散集內(nèi)的門來構(gòu)造 是否總可有效地做

8、到這些？即，給定對于n個量子位的一個酉變換，是否存在n的多項式的線路來近似？ 答案：否。對大多數(shù)U門，近似的效率都很低。,21,22,4.5.5 量子計算復雜性,經(jīng)典復雜性分類: - 復雜類P - 求解所需時間: O(poly(|input|) -復雜類NP（nondeterministic polynomial time） -驗證所需時間: O(poly(|input|) -復雜類NP-complete -任何別的NP問題都可約化到此問題。 -復雜類NPI （NP Intermediate）- NP 但不是NP-complete -復雜類PSPACE(polynomial space) -

9、求解所需空間: O(poly(|input|) - 復雜類EXP -求解所需空間: O(2poly(|input|),22,23,復雜性類 PSAPCE,復雜性類 PSPACE - 可以用圖靈機解決的判定問題。 - 需要的空間隨問題的大小成多項式增長，可以使用任意長的時間。,23,24,量子復雜性類BQP,復雜性類BQP（bounded error quantum polynomial time，是BPP的量子對應(yīng)） 實質(zhì)上是量子復雜性類 可以利用多項式規(guī)模量子線路計算的，并且誤差在有界概率內(nèi)可解的判定問題。,24,25,復雜性類BPP,復雜性類 BPP(Bounded-error proba

10、bilistic time) - 經(jīng)典復雜性類 - 在經(jīng)典圖靈機上用多項式的時間，且誤差在有界概率內(nèi)可解的判定問題。 - 顯然： BPPBQP,25,26,量子計算復雜性類,P,BQP,NP,PSPACE,26,27,量子復雜性類PSAPCE 包含BQP,可以證明BQPPSAPCE，也就是任何利用量子算法在多項式大小的量子線路可以有界誤差確定的語言，L，都可以用經(jīng)典機器用多項式空間確定。即 LBPQ LPSPACE,27,28,量子復雜性類,量子計算機也遵守Church-Turing論題： 任何計算過程都可用圖靈機來模擬。,28,29,能量與計算,計算機復雜性研究了求解一個計算問題所需的時間和

11、空間量。另一類重要的計算資源是能量。,30,3.2.5 能量與計算,計算中的能量消耗與計算是否可逆是深刻相聯(lián)系的。 說一個計算是可逆的, 等價于說，在計算中沒有信息被擦除。,30,31,經(jīng)典不可逆邏輯門,如，與非門等是不可逆的，兩個輸入，一個輸出， 即給定輸出，不可唯一地確定輸入。,32,經(jīng)典可逆邏輯門,如，非門和offoli 門等是可逆的。,33,Landauer 原理,(第一種形式): 設(shè)一個計算機擦除一位的信息, 則耗散到環(huán)境中的能量至少為kBTln2，其中，kB為Boltzman常數(shù), T為計算機的環(huán)境溫度。 (第二種形式): 設(shè)一個計算機擦除一位信息, 則環(huán)境的熵至少增加kBln2。

12、,33,34,能量與計算的意義,盡管現(xiàn)有計算機遠沒有達到Landauer 原理給出的下限，弄清可以減少多少能量消耗仍然是有意義的。 主要源于摩爾定律，如果計算機的能力不斷增強，除非每個操作的能量消耗至少像計算能力提高一樣迅速降低，否則消耗的總能量必然增加。,35,從研究可逆計算學到什么？,計算的可逆性來源于我們保留所有的信息。信息的擦除帶來了不可逆。 可逆計算過程不耗費能量。 可以有效地進行可逆計算。也就是如果存在一個不可逆的線路計算某函數(shù)，則可以用一個可逆線路有效的模擬這個線路。 可逆計算導致了物理學中的一個老問題：麥克斯韋妖,35,36,Maxwell 妖,熱力學第二定律： 封閉系統(tǒng)的熵永

13、遠不會減少,Maxwells Demon Assisted Thermodynamic Cycle in Superconducting Quantum Circuits, H. T. Quan, Y. D. Wang, Yu-xi Liu, C. P. Sun, and F. Nori, Phys. Rev. Lett. 97, 180402 (2006) 2. Quantum thermodynamic cycles and quantum heat engines, H. T. Quan, Yu-xi Liu, C. P. Sun, and F. Nori, Phys. Rev. E 7

14、6, 031105 (2007) 3. The Physics of Maxwell demon and information, K. Maruyama, F. Nori, and V. Vedral， Rev. Mod. Phys. 81, 1 (2009),1871年， J. C. Maxwell 提出表面上違反這條定律的機器。 他提出如圖所示的小妖怪，把氣缸中的快慢氣體分為兩半，當快分子從左邊靠近小門，他就打開小門讓分子通過。通過足夠長的時間整個氣缸的熵就會減少。,37,4.6 量子計算線路模型總結(jié),（）經(jīng)典資源 量子計算包括經(jīng)典部分和量子部分。 （）一個合適的狀態(tài)空間 2n維的復Hi

15、lbert空間, 積形式|x1,x2,x3,xn的狀態(tài)稱為計算機的計算基態(tài)，其中xi=0,1,每一個基矢態(tài)簡寫為|x且x 是二進制表示為x1xn的數(shù)。,37,38,4.6 量子計算線路模型總結(jié),（）制備處于計算基矢態(tài)的能力 任何計算基矢態(tài)|x1,xn ,可在n步內(nèi)制備。 （）執(zhí)行量子門運算的能力 可以對量子比特的任意子集施加邏輯門。存在普適量子門集。 （）在計算基矢上進行測量的能力。,38,39,4.7 量子系統(tǒng)仿真,4.7.1 仿真原理 4.7.2 量子仿真算法 4.7.3 一個說明例子 4.7.4 量子仿真概覽,39,40,4.7.1 量子仿真,仿真的核心是解微分方程，這些微分方程用于刻畫

16、統(tǒng)治系統(tǒng)動力學行為的物理定律。 如: 牛頓定律, Poisson定律，擴散方程， Schrdinger方程等。 總的目標是：給定系統(tǒng)的初始態(tài)，在其它時間或位置的狀態(tài)如何？它是什么狀態(tài)？,40,41,模擬量子系統(tǒng),模擬的核心是解微分方程，這些微分方程用于刻畫統(tǒng)治系統(tǒng)動力學行為的物理定律。 以上步驟中的誤差是有界的，且小于迭代次數(shù)的某個低次冪。 不是所有的系統(tǒng)都能被有效率地模擬。,41,42,模擬量子系統(tǒng)的挑戰(zhàn),用經(jīng)典計算機可以模擬量子系統(tǒng)，但一般效率很低 模擬量子系統(tǒng)的關(guān)鍵挑戰(zhàn)是：需解的微分方程的數(shù)目為指數(shù)個。 對按薛定諤方程演化的N量子位，需要解2N個方程。,42,43,量子計算機可以模擬量子

17、系統(tǒng)，它們沒有有效的經(jīng)典仿真。 也可能有不能在量子計算機可以模擬的量子系統(tǒng)。,注意,44,4.7.2量子仿真算法,time-independent Hamiltonian 系統(tǒng)的初始狀態(tài)為 |y(0) 對時不變的哈密頓量 H, 作用在系統(tǒng)上的時間為t 。 系統(tǒng)演化成 |y(t) = e-iHt |y(0) H的指數(shù)一般極難求。 一階近似 |y(t + Dt) ( I - iH Dt)|y(t) 但這樣的一階解一般不能滿足要求。,44,45,有些Hamilton量是可以求解的 例子： 一個在均勻磁場中沿z軸的自旋為1/2的粒子的哈密頓量為： 其中c = (eB/mC) 則經(jīng)過時間t后：,系統(tǒng)Ha

18、milton量,45,46,系統(tǒng)Hamilton量,在均勻磁場中沿z軸兩個無相互作用的自旋為1/2的粒子的哈密頓量為：,46,47,Hamilton量可以分解,雖然Hamilton量的指數(shù)很難求，但對許多Hamilton量求高階近似解是可能的。 例如對大多數(shù)物理系統(tǒng)，Hamilton量可以寫成許多局部相互作用的和的形式；如對一個n粒子系統(tǒng)： 其中Hk最多作用在常數(shù)c數(shù)目的子系統(tǒng)上，L是n的一個多項式。,47,48,量子仿真,我們可以選擇子系統(tǒng)使得每一個e-iHkt 都很容易仿真。 但通常 Hk,Hj 0，所以 - 那么如何從e-iHkt構(gòu)造e-iHt？,48,49,我們可以對e-iHt近似（通

19、過無限逼近的辦法）。 定理4.3（Trotter公式）: 令A和B是Hermite算子，則對任意實數(shù)t，有,量子仿真算法的核心-漸進近似定理：Trotter 公式,49,50,三個記號,O 為函數(shù)行為設(shè)定的上界：定義設(shè)非負整數(shù)函數(shù)f(n)和g(n)，如果存在常數(shù)c和n0使得所有大于n0的n有如下關(guān)系 c g(n) f(n)，那么就說f(n)屬于類O（g(n)），即除去一個不重要的常數(shù)因子g(n)是f(n)的一個上界。 指除去不重要的常數(shù)因子 W下界：函數(shù)f(n)稱為是W（g(n)），如果存在常數(shù)c和n0使得所有大于n0的n有如下關(guān)系 f(n) c g(n) ，即除去一個不重要的常數(shù)因子g(n)

20、是f(n)的一個下界。,51,證明,由于,所以,并且用二項式展開,52,證明,因此,由于,53,近似Hamilton量的兩個有用公式,例子：,53,這里Dt是一個很小的量。,54,算法: 量子模擬,輸入： 1）作用在N維系統(tǒng)上的Hamilton量， 其中每個Hk作用在尺寸和N無關(guān)的子系統(tǒng)上。 2）在t=0的系統(tǒng)初始態(tài)為|y0。 3）正的非零精度d。 4）需要求的演變后狀態(tài)的時刻tf。 輸出：狀態(tài) ，使得 運行時間：O(poly(1/d)數(shù)目的操作。,54,55,量子模擬過程,過程： 選擇一個表示，使得n=poly(logN)量子比特的狀態(tài)，能近似系統(tǒng)狀態(tài)，且算子e-iHkDt具有有效的量子近似線路。選擇一個近似方法和Dt,使得期望誤差在可接受范圍內(nèi)（并且對某個整數(shù)j,jDt=tf),為迭代構(gòu)造一個相應(yīng)的量子線路