1量子計算：簡介、應(yīng)用與前景潘屹量子計算是基于量子力學(xué)理論的全新計算方式，相比起經(jīng)典計算機的計算模式，量子計算在應(yīng)對一些特定問題時能帶來較大的效率提了基礎(chǔ)的量子計算知識，對這一領(lǐng)域產(chǎn)生好奇與興趣，在課后閱讀了量課堂筆記；對量子計算的發(fā)展、理論與應(yīng)用有了初步的認知。本文對當(dāng)前量子計算的基礎(chǔ)理論進行科普性概述，介紹了一些簡單的量子算法與應(yīng)用，并展望量子計算的前景。所有源代碼在/Conless/quantum-computing-intro開源。2量子計算基礎(chǔ)52.1量子比特 52.2量子比特門 62.3量子電路及其簡單應(yīng)用 82.4量子電路的設(shè)計：Deutsch-Jozsa算法 3量子算法應(yīng)用：以ACM班程序設(shè)計作業(yè)為例123.1背景與題目 3.2前置知識 3.3電路設(shè)計 4思考與展望161引入與簡介3量子計算，指一種運用量子力學(xué)現(xiàn)象，例如量子疊加、量子干涉與量子糾纏進行計算的方式，是過去的數(shù)十年中興起的一種全新計算方式，在近幾年中也是一個在各類科普中高頻出現(xiàn)的熱點詞匯。下面的內(nèi)容從經(jīng)典計算機講起，簡要地介紹量子計算的發(fā)展歷史與其重要意義1。引入量子計算的初衷，就是為了打破經(jīng)典計算機出現(xiàn)的性能瓶頸。經(jīng)典計算機的發(fā)展領(lǐng)先于量子計算機約半個世紀；AlanTuring在1936年發(fā)表的論文中提出了圖靈機（TuringMachine）的模型[2]，宣告了現(xiàn)代計算機科學(xué)的誕生。Turing證明了存在一臺通用圖靈機，即任何可以在個人電腦上執(zhí)行的算法，都可以在這臺圖靈機上完成，這個論斷被稱為Church-Turing命題。隨后，vonNeumann設(shè)計出了這樣的理論模型，用實際元件實現(xiàn)了通用圖靈機的全部功能，在隨后的幾十年里，個人計算機的發(fā)展也一直沿用vonNeumann架構(gòu)，其發(fā)展速度遵從1965年GordonMoore所概括的Moore定律，即集成電路中單位面積的晶體管數(shù)量，以及與之相對應(yīng)的，計算機計算速度，大約每兩年增長一倍[3]。自Moore定律提出以來，經(jīng)典計算機硬件發(fā)展速度都近似地遵從于該定律；但進入21世紀以來，Moore定律的有效性逐漸下降，許多研究人員認為其將在21世紀的前20年終結(jié)，著名芯片企業(yè)，Nvidia公司的首席執(zhí)行官JensenHuang就于日前宣稱，Moore定律已死[4]。其中的重要原因在于傳統(tǒng)半導(dǎo)體原件在柵極線寬較小時，可能會出現(xiàn)量子隧穿等效應(yīng)[5]。解決Moore定律最終失效的一個可能方案是采用不同的計算模式，量子計算就是其中一種。量子計算這一概念于1980年由物理學(xué)家PaulBenioff首次提出[6]。隨后，F(xiàn)eymann指出，在經(jīng)典計算機上有效地模擬量子系統(tǒng)的演化似乎是不可能的，量子計算機可能可以模擬經(jīng)典計算機無法做到的事情[7]，并引入了早期版本的量子電路符號[8]。1985年，DavidDesutsch提出，能否用量子力學(xué)原理推導(dǎo)出更強的Church-Turing命題，并引導(dǎo)出了現(xiàn)代量子計算機的概念[9]。他舉了一個簡單的例子（見節(jié)2.4表明量子計算機的計算能力確實超過了經(jīng)典計算機。在隨后的十年里，量子算法相關(guān)研究不斷涌現(xiàn)出新的成果。1994年，1部分內(nèi)容參考了維基百科詞條與QuantumComputationandQuantumInformation[1]1引入與簡介4PeterShor提出了一種新的量子算法，可以有效地解決大整數(shù)的質(zhì)因數(shù)分解問題[10]，這在經(jīng)典計算機上被認為是不可解（難以在多項式時間內(nèi)解決）的；Shor算法的出現(xiàn)一度讓基于質(zhì)因數(shù)分解的RSA加密算法的安全性受到威脅[11]。1996年，LovGrover證明了，在非結(jié)構(gòu)化搜索空間進行搜索的問題也可以通過量子計算機加速[12]，這種搜索方法的廣泛適用性引起了人們對Grover算法的相當(dāng)關(guān)注。由此可以看出，量子計算與量子算法可以對許多運用經(jīng)典計算機難以解決的問題進行加速。如今，量子計算領(lǐng)域依舊處于蓬勃發(fā)展之中。在下面的章節(jié)中，量子計算的相關(guān)基礎(chǔ)理論將會被介紹。2量子計算基礎(chǔ)52量子計算基礎(chǔ)量子計算理論以量子物理領(lǐng)域的數(shù)學(xué)物理方法、記號與公式為重要基礎(chǔ)；本節(jié)將對相關(guān)內(nèi)容進行簡單介紹。在學(xué)習(xí)量子比特與其相關(guān)表示的過程中，筆者發(fā)現(xiàn)其與本科一年級所學(xué)習(xí)的線性代數(shù)課程有著高度相關(guān)性，再一次感受到了理論計算機科學(xué)中數(shù)學(xué)的重要性。2.1量子比特量子比特（qubit）是量子計算和量子信息的基本概念。在經(jīng)典計算機中，經(jīng)典比特以0和1兩種狀態(tài)存在。而量子比特也有相對應(yīng)的兩種形態(tài)，在Dirac表示法中記作j0〉,j1〉，任何一個兩態(tài)的量子系統(tǒng)都可以實現(xiàn)這一點，例如在氫原子中j0〉,j1〉可以代表基態(tài)和第一激發(fā)態(tài)，在質(zhì)子自旋中可以表示任意方向的分量。與經(jīng)典比特不同的是，量子比特除了j0〉組合，可以記為其中α,β∈R（實際上取值域為C2，方便起見，這里首先以實數(shù)系作為研究對象）且jαj2+jβj2=1。此時，我們不妨從幾何的角度理解這一式子：如果將j0〉看作x方向上的單位向量，j1〉看作y方向上的單位向量，那么容易發(fā)現(xiàn)，jψ〉就在單位圓上運動，其模長始終為1。更進一步地，考慮態(tài)向量jψ〉在這組正交基上的投影，這也就是量子力學(xué)中的測量過程：ψ=→T→→)jψ〉tj0其中，左式是在線性代數(shù)中熟知的投影運算形式p=uTvu，右式是在量子2.(3)而在j1〉上的分量模長平方同理則為β2，這樣一來，約束條件α2+β2=12量子計算基礎(chǔ)6在經(jīng)典比特意義下，n個比特可以表示2n種不同的狀態(tài)，在量子比特意義下，也可以通過n個量子比特的疊加生成一個dim=2n的量子比特空間。這個時候需要引入張量積（tensorproduct）這一概念，這在線性代數(shù)課程中尚未涉及，但是可以用一些簡單的例子進行理解：于是，疊加兩個量子比特可以看作對兩個向量進行張量積。這意味著，我們可以首先對基求張量積上式可以從許多角度進行理解，例如若置j0〉=e0=(0,1),j1〉=e1=(1,0)為R2的標準基，計算可得j00〉=(0,0,0,1)=e0,j11〉=(1,0,0,0)=e3是R4的標準基（這里選取0-base可以讓單位基的角標恰好為j〉中二進制數(shù)的十進制表示）。而后，計算兩個任意單量子比特的張量積，例如就可以得到(5)特殊地，長度為n的全零量子比特表示為0?n，全一量子比特表示為1?n。2.2量子比特門每一個量子比特都可以由一個特定維度的單位向量表示，而量子比特之間的運算同樣可以用向量變換的手段，即矩陣，進行刻畫。值得注意的2量子計算基礎(chǔ)7是，根據(jù)vonNeumann提出的量子力學(xué)公設(shè)[13]，量子比特之間的運算必須是酉變換（unitarytransformation也即，兩個沿時間先后順序出現(xiàn)的量的乘積UtU=I。根據(jù)線性代數(shù)知識，這蘊含了Ut=U=U?1。在此基礎(chǔ)上，我們可以構(gòu)建出幾個常用的合法量子運算門定義矩陣X表示非門X,(6)顯然地，這表示將單量子比特的兩位相互交換。這與傳統(tǒng)非門是相似的。定義矩陣Z,U表示相位翻轉(zhuǎn)和旋轉(zhuǎn)Z,(7)定義矩陣H表示Hadamard門這代表著將一個在R2的向量沿θ=進行對稱。于是(10)(10)這兩個向量分別對應(yīng)了士，前者位于j0〉,j1〉的角平分線上，代表了兩者若需要n個量子比特的等概率疊加，即j+〉的n維張量積可以考慮對線性算符H作張量積并作用于j0〉上，就得到了H?n(j0〉?n)=j+〉?n.(12)2量子計算基礎(chǔ)82.3量子電路及其簡單應(yīng)用在經(jīng)典計算機中，邏輯電路由一系列邏輯門與電路元件構(gòu)成，圖2.1即為熟知的與或非邏輯門的表示，它們之間相互嵌套組合，構(gòu)成了經(jīng)典電子計算機的電路體系。(a)邏輯與門(b)邏輯或門(c)邏輯非門圖2.1:與或非門（ANSI及IEEE標準）而在量子電路中的計算則由一系列邏輯門、測量與賦值操作構(gòu)成。但是，不同于傳統(tǒng)電路是用金屬線所連接以傳遞電壓信號或電流信號；在量子線路中，線路是由時間所連接，亦即量子比特的狀態(tài)隨著時間自然演化，一直到遇上邏輯門而被操作。另一方面，經(jīng)典計算機的大多數(shù)基本邏輯門（除了非門）都是不可逆的，例如，對于與門，我們不可能從輸出信息的每一位恢復(fù)到兩個輸入信息；而量子計算中的每一步操作都是酉變換。剛剛的幾個酉變換在量子電路中都有他們的電路元件表示j0〉HZXU-///上面的過程中，量子比特的變換過程為[]→]→-11]→1]→[]jψ〉在實際的計算中，僅僅進行單元操作顯然是不夠的，因此需要考慮將對單量子比特的操作拓展到多量子比特,從一種簡單的情況出發(fā)?，F(xiàn)在有兩個量子比特，但是僅對其中的一個，即目標量子比特進行操作，另一個作為控制量子比特，決定是否對目標進行否運算,于是容易得到這一操作的酉矩2量子計算基礎(chǔ)9陣當(dāng)且僅當(dāng)控制量子比特為1時,目標量子比特通過非門.可以被表示為CNOT=?=?=X理論研究證明，任何多量子比特邏輯門可以由受控非門和單量子門組成[1]，因此，受控非門具有通用性，這也與經(jīng)典電路中與非門（XAND）的通用性相對應(yīng)。下面介紹幾個量子電路的簡單應(yīng)用。交換兩個量子比特的電路可以被表示為 ?? 山?山這是因為容易驗證如果在二維Hadamard門后面跟著一個CNOT門j00〉H?2CNOT///2量子計算基礎(chǔ)10對四個二維本征態(tài)進行計算,我們會得到(15)(15)概括地這就是著名的Bell態(tài)（或EPR2對它描述了一種最簡單的量子糾纏示例：上面的四個量子比特雖然都具有兩個維度，但是在測量中，只要測量了其中的一維，另一維也被唯一地確定了。Bell態(tài)的這一性質(zhì)使其在超密編碼與量子隱形傳態(tài)的領(lǐng)域扮演著重要的角色。2.4量子電路的設(shè)計：Deutsch-Jozsa算法Desutsch-Jozsa算法可由一個簡單的游戲進行引入：Alice從0-2n-1中選一個數(shù)x并將其傳送給Bob。Bob計算出某個函數(shù)f(x)的值，可以為0或1，并將它傳回給Alice。已知該函數(shù)只有可能有兩種情況：要么f(x)對于所有的x均為常數(shù)，要么f(x)恰好對于一半的x取0，一半的取1。Alice怎樣能夠最快地判斷f(x)的類型？形式化地，已知函數(shù)f:{0,1}?n→{0,1}一定是下列兩種極端形式的2.Balanced：f(x)=0forhalfof{0,1}?n,andf(x)=1fortheotherhalf問如何用最少的查詢次數(shù)確定f屬于二者中的哪一種。2Einstein-Podolsky-Rosen2量子計算基礎(chǔ)11H?n////H?n////H?n?nUfXHxy⊕f(x)XH圖2.2:Deustch-Jozsa算法的量子電路考慮圖2.2所示量子電路，輸入Uf的初態(tài)為j+〉?nj-〉?？紤]初態(tài)的前n位，設(shè)其在某一狀態(tài)下為x，那么Uf從而另外，容易驗證，對于單量子比特門Hjx〉=Σz∈{0,1}xzjz，將這一結(jié)果推廣到n個量子比特上，就有了從而于是考慮測量結(jié)果在〈0?nj上的分量，即z只取j0〉?n時表達式的值因此，當(dāng)f為常值函數(shù)時，測量結(jié)果必為j0〉?n；當(dāng)f為平衡函數(shù)時，測量結(jié)果不可能出現(xiàn)j0〉?n。在整個過程中，運用了3個n量子比特門，總時間復(fù)雜度在O(n)=O(logN)級別，相比于樸素算法O(N)的時間開銷，量子算法在效率上產(chǎn)生了質(zhì)的飛躍。Deustch-Jozsa算法是第一個具有重要意義的量子算法，其出現(xiàn)證明了量子計算在一些方面有著經(jīng)典計算機無可比擬的性能，為接下來出現(xiàn)的許多量子算法奠基。3量子算法應(yīng)用：以ACM班程序設(shè)計作業(yè)為例123量子算法應(yīng)用：以ACM班程序設(shè)計作業(yè)為例3.1背景與題目在量子算法發(fā)明之初，以Deutsch-Jozsa為例的多種算法應(yīng)用范圍都相對局限，對于多數(shù)實際問題都無能為力或無法帶來顯著變化。但隨著量子算法的逐步發(fā)展，許多經(jīng)典計算機能解決的問題都能被量子計算機找到更優(yōu)的方案。下面以上海交通大學(xué)ACM班2022級程序設(shè)計大作業(yè)的一道題P1754int2048-乘法速度測試為例，講解量子算法的簡單應(yīng)用。題目的大意為：給定若干個大整數(shù)，求它們的乘積，所有運算結(jié)果范圍在[1,10200000]內(nèi)。為簡化題意，題目可以改寫為，給定正整數(shù)a,b滿足a,b≤10100000，求a×b。一種樸素的做法是直接模擬豎式乘法，其時間復(fù)雜度為n2（其中N=「logkmaxa,bl，k為運算過程中的進制）。進一步地，可以考慮整數(shù)的多項式表示：對于一個k進制整數(shù)i∈[N]考慮多項式同理可構(gòu)造出b對應(yīng)的多項式B(z)，那么令在經(jīng)典計算機中，利用快速傅里葉變換（FastFourierTransform）與其逆變換可以在O(NlogN)的時間內(nèi)求出對應(yīng)的多項式C[14]，進行進位就得到了a×b。接下來，嘗試使用量子計算機得到一種更加高效的做法。3量子算法應(yīng)用：以ACM班程序設(shè)計作業(yè)為例133.2前置知識在離散傅里葉變換（DiscreteFourierTransform，DFT）中，我們熟知對多項式f(x)進行點值(!,yk)求值的方法在量子計算機中，我們同樣希望進行相同的變換，使得N-1維量子態(tài)jXxjjj〉，經(jīng)過變換得到j(luò)Y〉=Σ1ykjk〉，其中yk與xk的關(guān)系滿足上式，jj〉,jk〉表示其二進制分解所得結(jié)果的張量積。代入可得(26)對比jX〉,jY〉的形式，發(fā)現(xiàn)變換的實質(zhì)就是一次基變換兩組標準正交基的變換可改寫為酉變換!N!···!-17 7l1!-1!N(N-1)×2 !N(N-1)(N-1)5這樣就完成了一個滿足量子計算要求的傅里葉變換算法，也即量子傅里葉上面的內(nèi)容已經(jīng)完成了量子傅里葉變換的算法設(shè)計，但得到了這樣的酉陣，還不能直接設(shè)計出所需的量子電路，因此，在這里將式27進行進一3量子算法應(yīng)用：以ACM班程序設(shè)計作業(yè)為例14步演化：考慮直接對exp指數(shù)中的進行二進制小數(shù)分解，也即對k進行二進制分解，得到(29)這里的{}表示取的小數(shù)部分，由于e2πi=1，因此等式是成立的。為了方便構(gòu)建電路，記那么式29就可以寫作這種張量積意義下的量子電路就可以通過旋轉(zhuǎn)門Rk加以控制生成，特殊地，H可以直接看作自身受控的R1門，這是因為Hj0〉=j+〉,Hj1〉=j—〉例如，考慮輸入態(tài)jj1,···,jn〉，將其首位通過H門將得到隨后，每次讓首位通過受jk控的Rk門，相位都將增加，最終顯然會得到3量子算法應(yīng)用：以ACM班程序設(shè)計作業(yè)為例15依此類推，每一位需要的狀態(tài)都可以這樣進行制備，這樣就得到了量子電路3jjnjjn-1〉jjn-2〉...HR2R3Rn ?HR2Rn-1 ??HR2Rn-2...H1〉2〉3〉...n〉于是，這樣就可以完成量子傅里葉變換，將兩個乘數(shù)的傅里葉變換點jjnjjn-1〉jjn-2〉...HHH值相乘，就得到了積的多項式點值，進而可以利用量子運算可逆的性質(zhì)方便地進行量子傅里葉逆變換，只需要將剛剛的操作完全反轉(zhuǎn)即可，其電路為HHH(Rn)-1(Rn-1)-1(R2)-1(Rn-1)-1(R2)-1(Rn-2)-1(R2)-1H ??????H1〉2〉3〉...n〉在此不再列出其電路。在每一個過程中，用到了個量子門，時間復(fù)雜度為O(n2)=O(log2N)，算法效率較經(jīng)典計算機中的快速傅里葉變換有了顯著的提升。利用IBM的Python宏包Qiskit可以在JupyterNotebook中完成這樣的量子乘法器，筆者的代碼4在GitHub開源。4參考了qiskit-tutorials中的實現(xiàn)代碼[16]與《20行Python代碼說清量子霸權(quán)[17]。4思考與展望16在過去的一段時間里，我對量子計算這一領(lǐng)域進行了初步的了解與學(xué)習(xí)。從一開始，對量子的疊加性特點與對量子比特進行數(shù)學(xué)計算方法的困惑，后來，通過檢索資料、求助同學(xué)等方式，我逐漸理解了量子計算的原理，并通過與經(jīng)典計算機的對比理解了量子計算的諸多特點；下面簡要概括我對此的一些思考。在深入學(xué)習(xí)之前，我一直不理解的一個問題是：如果說量子計算可以直接由矩陣與向量等傳統(tǒng)數(shù)學(xué)操作完成，那么它和經(jīng)典計算機中直接進行數(shù)學(xué)運算的區(qū)別在哪里？為什么可以帶來效率的提升？后來，通過學(xué)習(xí)節(jié)2.4中用Deustch-Jozsa算法，我形成了較為直觀的理解：考慮一個n量子比特門，對于一個酉變換，它能在O(n)的時間內(nèi)完成量子比特的變換，表面上看僅僅是改變了n個比特位上的概率分布，實際上卻同時改變了關(guān)于一組2n個標準正交基的線性組合。這就意味著，如果初態(tài)與變換選取得當(dāng)，量子計算就可以用O(n)的時間完成O(2n)的工作。這樣的案例，也即剛剛提到的Deustch-Jozsa算法，已經(jīng)在前文中展示了。在了解了簡單的幾種量子算法后，我產(chǎn)生了進一步的好奇：目前有哪些類型的量子算法，它們能解決哪些經(jīng)典計算機科學(xué)中的問題？QuantumComputationandQuantumInformation[1]中對現(xiàn)有的量子算法進行了這樣的分類：基于傅里葉變換的量子算法，例如Shor的素因子分解和離散對數(shù)算法；量子搜索算法，例如大名鼎鼎的Grover搜索；以及量子模擬算法。此前一段時間里我主要學(xué)習(xí)的是第一類量子算法。在嘗試學(xué)習(xí)后面兩種算法時，遇到的瓶頸在于對復(fù)向量空間的變換還沒有建立起一個很好的幾何直觀，因此對例如Grover搜索中的AmplitudeAmplification與迭代操作并沒有理解得很透徹，希望在本學(xué)期結(jié)束后繼續(xù)這一領(lǐng)域的學(xué)習(xí)。展望量子計算領(lǐng)域的未來發(fā)展，這一結(jié)合物理原理、數(shù)學(xué)知識與計算機科學(xué)思想的計算方法，能帶來跨時代意義的進步，具有相當(dāng)光明的前景。不過在工程領(lǐng)域中，業(yè)界許多人認為該領(lǐng)域的前景具有很強的不確定性；很大程度上這是因為量子計算機的物理實現(xiàn)進展較為緩慢，理論領(lǐng)域的許多算法在工程上依舊無法進行實現(xiàn)。為了實現(xiàn)量子計算機，人們也提出了多種方案，目前較為熱門的有超導(dǎo)量子計算、量子點量子計算等?；氐嚼碚擃I(lǐng)域，盡管現(xiàn)在已經(jīng)有許多高效的量子算法，但它們的應(yīng)用范圍還是相對4思考與展望17狹窄，學(xué)者們一直在致力于拓展量子算法的應(yīng)用范圍，并降低其不確定性；目前，對于很多量子計算相關(guān)問題的研究還非常有限[18]，例如量子計算機多項式時間能否解決經(jīng)典計算機在多項式時間所不能求解的問題，即BQP是否等于BPP。希望在不遠的未來，量子計算領(lǐng)域的相關(guān)工作能取得進一步進展，人們對于量子計算能力的認識能變得更加全面。參考文獻18[1]MichaelANielsenandIsaacChuang.Quantumcomputationandquantuminformation,2002.1,2.3,4[2]AlanMathisonTuringetal.Oncomputablenumbers,withanapplicationtotheentscheidungsproblem.J.ofMath,58(345-363):5,1936.1[3]GordonEMooreetal.Crammingmorecomponentsontointegratedcircuits,[4]WallaceWitkowski.”moore’slaw’sdead,”nvidiaceojensenhuangsaysinjustifyinggaming-cardpricehike,92022.1[5]SuhasKumar.Fundamentallimitstomoore’slaw.arXivpreprintarXiv:1511.05956,2015.1[6]PaulBenioff.Thecomputerasaphysicalsystem:Amicroscopicquantummechanicalhamiltonianmodelofcomputersasrepresentedbyturingma-chines.Journalofstatisticalphysics,22(5):563–591,1980.1[7]RichardPFeynman.Simulatingphysicswithcomputers,1981.InternationalJournalofTheoreticalPhysics,21(6/7),1981.1[8]RichardPFeynman.Quantummechanicalcomputers.Found.Phys.,16(6):507–532,1986.1[9]DavidDeutsch.Quantumtheory,thechurch–turingprincipleandtheuni-versalquan