一種高效、容錯(cuò)的通用量子計(jì)算機(jī)體系結(jié)構(gòu)

1、一種高效、容錯(cuò)的通用量子計(jì)算機(jī)體系結(jié)構(gòu)吳楠宋方敏?，江蘇南京210093計(jì)算機(jī)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室 計(jì)算機(jī)科學(xué)與技術(shù)系摘要：通用量子計(jì)算機(jī)(universal quantum computer )在求解某些在經(jīng)典計(jì)算機(jī)上具有超多 項(xiàng)式復(fù)雜度的問(wèn)題上存在著潛在的巨大優(yōu)勢(shì)。通用量子計(jì)算機(jī)體系結(jié)構(gòu)在很大程度上影響量子計(jì)算功效和量子程序設(shè)計(jì)風(fēng)范。本文提出一種通用量子計(jì)算機(jī)的體系結(jié)構(gòu)，并考慮了在該體系結(jié)構(gòu)下的計(jì)算能力擴(kuò)展和容錯(cuò)性能等問(wèn)題。關(guān)鍵詞：通用量子計(jì)算機(jī)體系結(jié)構(gòu)量子存儲(chǔ)器可擴(kuò)展性容錯(cuò)A Novel Kind of Architecture with High-efficiency andErr

2、or-tolerance of Universal Quantum Computer?WU NanSONG Fan gmi nState Key Laboratory of Novel Software Technology, Nanjing University, Nanjing 210093, China?Corresponding author: Phn +86-25-83593673, E-mail: Abstract: Un iversal qua ntum computer offers great pote ntial adva ntage for

3、 solvi ng some problems which are of super-po lyno mial time complexity by con trasti ng with classical computer. The architecture of uni versal qua ntum computer will much affect qua ntum computi ng efficie ncy and the paradigm of qua ntum program ming. This paper proposes a new kind of architectur

4、e of uni versal quantum computer, and considers the enhancement of computing efficiency together with error-tolera nee un der this architecture.Keywords: uni versal qua ntum computer, architecture, qua ntum memory, expa ndability, error-tolera nee1概述量子計(jì)算機(jī)在求解諸如數(shù)的質(zhì)因子分解、無(wú)序數(shù)據(jù)庫(kù)搜索等在經(jīng)典計(jì)算機(jī)上尚未找到有效算法的問(wèn)題上具有潛在的

5、巨大優(yōu)勢(shì)，可在多項(xiàng)式時(shí)間內(nèi)完成上述諸類運(yùn)算(見(jiàn)表1)，同時(shí)在處理保密光通信等問(wèn)題上遠(yuǎn)遠(yuǎn)優(yōu)于目前的經(jīng)典計(jì)算機(jī)。目前，量子計(jì)算理論和量子計(jì)算機(jī)的研究業(yè)已成為熱點(diǎn)，包括中國(guó)在內(nèi)的許多國(guó)家已就該領(lǐng)域的研究提出遠(yuǎn)景規(guī)劃：美國(guó)軍方對(duì)量子計(jì)算的研究及量子計(jì)算機(jī)的研制給予高度重視，DAPRA專門制定了“量子信息科學(xué)和技術(shù)發(fā)展規(guī)劃”，目標(biāo)是2012年前開(kāi)發(fā)出包括核磁共振量子計(jì)算、離子阱量子計(jì)算、 光量子計(jì)算、固態(tài)量子計(jì)算等新型量子計(jì)算實(shí)現(xiàn)平臺(tái)并深入研究量子算法、量子保密通信等相關(guān)基礎(chǔ)理論2 ； 2004年以來(lái)，中國(guó)科學(xué)技術(shù)大學(xué)潘建偉等學(xué)者先后在國(guó)際上首次實(shí)現(xiàn)5粒子、6粒子光量子系統(tǒng)糾纏態(tài)以及終端開(kāi)放的兩字隱態(tài)傳

6、輸實(shí)驗(yàn)3，引起了國(guó)際學(xué)術(shù)界的廣泛關(guān)注；另外，歐洲、日本等多個(gè)研究機(jī)構(gòu)都對(duì)量子計(jì)算的理論和實(shí)現(xiàn)平臺(tái)的研究投入了 大量的人力和物力。表1.幾種量子算法與經(jīng)典算法復(fù)雜度比較1,4,5,17待解問(wèn)題經(jīng)典算法復(fù)雜度量子算法復(fù)雜度非結(jié)構(gòu)化搜索血）(Grover 算法)平衡函數(shù)確定00)0(1) (Deutsch-Jossa 算法)快速傅立葉變換（FFT）O(nlogn)Oi logDlOJllQFT 算法)整數(shù)質(zhì)因子分解12 10（滬）初護(hù)）0（n伽血耐n） or算法）量子計(jì)算機(jī)的物理實(shí)現(xiàn)已經(jīng)成為現(xiàn)實(shí)，性能也在不斷提高，但目前實(shí)現(xiàn)的量子計(jì)算設(shè) 備大都只能處理特定問(wèn)題或算法，計(jì)算機(jī)科學(xué)家和物理學(xué)家正在嘗試建

7、造通用量子計(jì)算機(jī)， 即可以在不改變體系結(jié)構(gòu)的情況下求解各類量子計(jì)算問(wèn)題?？梢灶A(yù)見(jiàn)，一旦通用量子計(jì)算機(jī)研制成功，即可針對(duì)各種待解問(wèn)題使用量子程序設(shè)計(jì)語(yǔ)言編寫相應(yīng)的量子程序，交由通用量子計(jì)算機(jī)執(zhí)行，這樣人們就可以像操作經(jīng)典計(jì)算機(jī)一樣方便地控制量子計(jì)算機(jī)進(jìn)行高效運(yùn) 算。為此，需要設(shè)計(jì)相應(yīng)于通用量子計(jì)算機(jī)體系結(jié)構(gòu)的通用量子指令系統(tǒng)?，F(xiàn)今通用量子計(jì)算機(jī)的體系結(jié)構(gòu)和指令系統(tǒng)在國(guó)外研究較少，國(guó)內(nèi)迄今未見(jiàn)相關(guān)論述。在對(duì)通用量子計(jì)算機(jī)的體系結(jié)構(gòu)及其指令系統(tǒng)進(jìn)行探討的基礎(chǔ)上，本文提出了一種通 用量子計(jì)算機(jī)體系結(jié)構(gòu)， 并考慮了在該體系結(jié)構(gòu)上的量子計(jì)算可擴(kuò)展性和容錯(cuò)性，旨在為未來(lái)通用量子計(jì)算機(jī)和通用量子程序設(shè)計(jì)語(yǔ)言的

8、設(shè)計(jì)提供理論基礎(chǔ)。2通用量子計(jì)算機(jī)的組成定義（通用量子計(jì)算機(jī)， Deutsch 1984年）：通用量子計(jì)算機(jī) Q是滿足如下條件的計(jì)算設(shè)備：（1）可精確模擬任意圖靈機(jī)；（2 ）可以以任意精度模擬任何量子計(jì)算機(jī)或量子計(jì)算模擬設(shè)備；（3） 可以模擬多種現(xiàn)實(shí)或理論的物理系統(tǒng)，其中有些是經(jīng)典通用圖靈機(jī)T無(wú)法模擬的；（4）可以完全模擬任意的有窮物理系統(tǒng)。我們必須在通用量子計(jì)算模型上考慮量子計(jì)算機(jī)的體系結(jié)構(gòu)。通用量子計(jì)算模型目前有多種，如通用量子圖靈機(jī) （universal quantum Turing Machine ），通用量子隨機(jī)存取機(jī) （universal qua ntum ran dom acce

9、ss machi ne）等，它們已被證明在計(jì)算能力上相互等價(jià)。量子圖靈機(jī)模型首先由Deutsch提出5，后由Bernstein等推廣為如下定義的通用量子圖靈機(jī)模型：定義（通用量子圖靈機(jī)，Bernstein 1997年）：令C是由這樣的復(fù)數(shù) 構(gòu)成的集合：存在在n的多項(xiàng)式時(shí)間內(nèi)計(jì)算:的實(shí)部和虛部并精確到 2之內(nèi)的算法。一臺(tái)通用量子圖靈機(jī)M定義為一個(gè)三元組(,Q,、J，其中1以空白符號(hào)#結(jié)束的有窮字母串；Q是以初始狀態(tài)qo和終止?fàn)顟B(tài)qf = q0標(biāo)識(shí)的有窮狀態(tài)集合；：是量子狀態(tài)轉(zhuǎn)換函數(shù)： 6 ： Q漢工T C兇乜下。量子圖靈機(jī)具有一條兩個(gè)方向均無(wú)窮長(zhǎng)的紀(jì)錄紙帶，紙帶上方 格的下標(biāo)設(shè)為Z, 個(gè)讀/寫頭

10、可沿紙帶向左(對(duì)應(yīng)于轉(zhuǎn)換函數(shù)中的L)或向右(對(duì)應(yīng)于轉(zhuǎn)換函數(shù)中的 R)任意移動(dòng)。量子圖靈機(jī)中格局(configurations )、初始格局和終止格局的定義均和確定性圖靈機(jī)中的定義完全一致。設(shè)M為一臺(tái)通用量子圖靈機(jī)，令S是M的格局的有窮復(fù)線性組合上的滿足歐幾里德歸一化條件的內(nèi)積空間，稱S中的每個(gè)元素為 M的一個(gè)疊加。量子圖靈機(jī)M定義了一個(gè)線性算符 Um ：S S，稱為M的時(shí)間演化算符：如果M以 格局c起始，當(dāng)前狀態(tài)為 p并且掃描了一個(gè)標(biāo)識(shí)符 二；下一步動(dòng)作時(shí)，M將會(huì)被置為格局 的疊加：；-、jc，其中每個(gè)非零的:i都與一個(gè)轉(zhuǎn)換、：(p,G .,q,d)對(duì)應(yīng)，Ci是由向c施 行轉(zhuǎn)換得到的新的格局。

11、通過(guò)線性時(shí)間演化算符U m可以將這種操作擴(kuò)展到整個(gè) S空間。經(jīng)典的馮諾依曼體系結(jié)構(gòu)計(jì)算機(jī)是以經(jīng)典確定性圖靈機(jī)為計(jì)算模型的，這是一種以程序儲(chǔ)存為核心的計(jì)算機(jī)體系結(jié)構(gòu)。經(jīng)典馮諾依曼體系結(jié)構(gòu)的提出以經(jīng)典確定性圖靈機(jī)的主 要組成部分為依據(jù)?？蓮娜缦挛鍌€(gè)主要部分考慮：分別為運(yùn)算器、控制器、存儲(chǔ)器、輸入設(shè) 備和輸出設(shè)備；每個(gè)部分都與經(jīng)典的確定性圖靈機(jī)模型中的要件一一對(duì)應(yīng)：存儲(chǔ)器對(duì)應(yīng)于圖靈機(jī)中的“紙帶”，輸入輸出設(shè)備對(duì)應(yīng)于圖靈機(jī)中的“讀/寫頭”，而控制器則對(duì)應(yīng)于狀態(tài)轉(zhuǎn)移函數(shù)的作用，運(yùn)算則對(duì)應(yīng)確定性圖靈機(jī)中格局的變化。仿照經(jīng)典馮諾依曼體系結(jié)構(gòu)計(jì)算機(jī)的設(shè)計(jì)思路，我們從通用量子圖靈機(jī)的構(gòu)成入手，以量子計(jì)算的物理背

12、景為依據(jù)，提出了構(gòu)成通用量子計(jì)算機(jī)的“部件”。首先，通用量子圖靈機(jī)也擁有一條無(wú)限長(zhǎng)的“紙帶”，由此可設(shè)置一個(gè)量子存儲(chǔ)器；量子存儲(chǔ)器可以儲(chǔ)存量子計(jì)算的中間結(jié)果，也可以用于輸入數(shù)據(jù)、輸出數(shù)據(jù)的暫存。量子圖靈機(jī)中的讀/寫頭和狀態(tài)轉(zhuǎn)移函數(shù)提示在通用量子計(jì)算機(jī)中應(yīng)設(shè)置輸入設(shè)備、輸出設(shè)備以及控 制器；與經(jīng)典圖靈機(jī)不同，通用量子圖靈機(jī)中存在著狀態(tài)的疊加，即量子態(tài)疊加(qua ntumsuperposition of states),而經(jīng)典圖靈機(jī)中引起的“格局變化”的“動(dòng)作”(可理解為運(yùn)算)在量子圖靈機(jī)中由一個(gè)時(shí)間演化算符(酉演化算符)UM取代。因此，在通用量子計(jì)算機(jī)中有必要加入一個(gè)部件來(lái)進(jìn)行專門的“量子運(yùn)算

13、”，即負(fù)責(zé)處理量子圖靈機(jī)運(yùn)行時(shí)刻所需的量子疊加態(tài)和酉演化。由此，一臺(tái)通用量子計(jì)算機(jī)則可具有如下組成，所使用的計(jì)算模型是通用量子圖靈機(jī)：(1 )存儲(chǔ)器；(2 )運(yùn)算器；(3 )控制器；(4 )輸入設(shè)備；(5 )輸出設(shè)備。3通用量子計(jì)算機(jī)體系結(jié)構(gòu)上一節(jié)我們提出了一種通用量子計(jì)算機(jī)的組成方案，本節(jié)我們?cè)敿?xì)討論通用量子計(jì)算機(jī)的體系結(jié)構(gòu)。學(xué)術(shù)界普遍認(rèn)為，雖然量子計(jì)算模型在計(jì)算能力上不弱于經(jīng)典概率圖靈機(jī)模型，也就是說(shuō)所有經(jīng)典計(jì)算機(jī)可以處理的計(jì)算問(wèn)題用量子計(jì)算機(jī)一定也可以處理，但考慮到功效和實(shí)現(xiàn)的復(fù)雜性，目前認(rèn)為量子計(jì)算機(jī)將不會(huì)取代經(jīng)典計(jì)算機(jī)而將成為經(jīng)典計(jì)算機(jī)的一個(gè)重要補(bǔ) 充。我們認(rèn)為，經(jīng)典計(jì)算機(jī)在處理普通

14、的算術(shù)運(yùn)算和控制方面具有相當(dāng)優(yōu)勢(shì)：一方面，已經(jīng)證明量子計(jì)算機(jī)在處理普通算術(shù)邏輯運(yùn)算等多項(xiàng)式復(fù)雜度問(wèn)題（P問(wèn)題）上的功效不會(huì)優(yōu)于經(jīng)典計(jì)算機(jī)，讓經(jīng)典計(jì)算機(jī)去處理類似的運(yùn)算是毫無(wú)問(wèn)題的；另一方面，如果使用量子計(jì) 算機(jī)對(duì)量子計(jì)算的流程進(jìn)行控制，則要消耗大量量子資源?！翱刂啤眲t是現(xiàn)代經(jīng)典計(jì)算機(jī)的一大優(yōu)勢(shì)，因此用經(jīng)典計(jì)算機(jī)控制量子計(jì)算流程十分簡(jiǎn)單直接?；谏鲜鲈?，我們認(rèn)為通用量子計(jì)算機(jī)應(yīng)該由經(jīng)典計(jì)算部分和量子計(jì)算部分兩者聯(lián)合完成運(yùn)算，其中經(jīng)典計(jì)算機(jī)負(fù)責(zé)控制量子運(yùn)算流程以及進(jìn)行普通算術(shù)邏輯運(yùn)算，量子計(jì)算部分則專門負(fù)責(zé)處理幾類已知的目前在經(jīng)典計(jì)算機(jī)上未見(jiàn)有效算法，而在量子計(jì)算機(jī)上存在有效算法的問(wèn)題（BQP問(wèn)

15、題）。學(xué)術(shù)界目前認(rèn)為比較理想的通用量子計(jì)算機(jī)體系結(jié)構(gòu)模型是一種混成結(jié)構(gòu)（hybridarchitecture）的模型，它由經(jīng)典計(jì)算設(shè)備和量子計(jì)算設(shè)備以及兩者之間的通信系統(tǒng)構(gòu)成。最 常見(jiàn)的混成結(jié)構(gòu)由 Knill提出8,9，如圖1所示，經(jīng)典計(jì)算部分作為量子計(jì)算機(jī)的主控端，量 子計(jì)算部分則作為受經(jīng)典部分控制的協(xié)同處理端。協(xié)同處理端Ih8imi-經(jīng)典計(jì)算設(shè)備；硬件與軟件1測(cè)量結(jié)果!吊子計(jì)算設(shè)備凰了資源的邏輯表示量子資源的物理實(shí)現(xiàn)圖i.通用量子計(jì)算機(jī)的混成結(jié)構(gòu)我們所提出的通用量子計(jì)算機(jī)的體系結(jié)構(gòu)建立在Knill提出的混成結(jié)構(gòu)之上，主控端是經(jīng)典計(jì)算機(jī)，負(fù)責(zé)量子計(jì)算中的算術(shù)和邏輯計(jì)算并控制量子計(jì)算部分；量子

16、計(jì)算設(shè)備作為協(xié)同處理端，專門負(fù)責(zé)處理以量子態(tài)形式所表示的數(shù)據(jù)。根據(jù)上述的基本框架，我們可以將第二節(jié)提出的通用量子計(jì)算機(jī)應(yīng)該具備的五個(gè)部分按 照物理實(shí)現(xiàn)方式（經(jīng)典實(shí)現(xiàn) /量子實(shí)現(xiàn)）進(jìn)行分類：（1） 存儲(chǔ)器：存儲(chǔ)器負(fù)責(zé)儲(chǔ)存量子計(jì)算中所涉及的經(jīng)典數(shù)據(jù)和/或量子數(shù)據(jù)的中間結(jié)果或最終結(jié)果，我們將存儲(chǔ)器分為兩類： 經(jīng)典存儲(chǔ)器 儲(chǔ)存經(jīng)典計(jì)算部分所產(chǎn)生的經(jīng)典數(shù)據(jù)（二進(jìn)制形式）以及經(jīng)典計(jì)算機(jī)控制量子計(jì)算部分時(shí)所產(chǎn)生的數(shù)據(jù)；量子存儲(chǔ)器負(fù)責(zé)儲(chǔ)存量子計(jì)算所產(chǎn)生的量子態(tài)，包括運(yùn)算中間結(jié)果和最終結(jié)果，值得注意的是，量子存儲(chǔ)器還是量子運(yùn)算發(fā)生的場(chǎng)所，也就是說(shuō)量子數(shù)據(jù)是不流動(dòng)的，這與經(jīng)典體系結(jié)構(gòu)不同。由于量子計(jì)算的特殊物理背

17、景，這樣設(shè)計(jì)量子存儲(chǔ)器可以有效避免“計(jì)算”這一相對(duì)獨(dú)立和集中的動(dòng)作被分散到多個(gè)物理器件中，并對(duì)提高量子計(jì)算的容錯(cuò)性和提高量子計(jì)算的功效很有好處。（2） 運(yùn)算器：經(jīng)典計(jì)算機(jī)中的運(yùn)算器稱為“ 算術(shù)邏輯運(yùn)算器 （ALU ）”，在我們提出的 通用量子計(jì)算機(jī)體系結(jié)構(gòu)中，它負(fù)責(zé)經(jīng)典算術(shù)和邏輯運(yùn)算以及控制所需要的經(jīng)典運(yùn)算，ALU可直接與經(jīng)典控制器進(jìn)行控制信息的通信，并與經(jīng)典存儲(chǔ)器進(jìn)行數(shù)據(jù)流的交互，經(jīng)典的算術(shù)和邏輯運(yùn)算均發(fā)生在 ALU中；在量子計(jì)算部分，專門處理量子計(jì)算的部件謂之量子運(yùn)算器， 量子運(yùn)算器受主控端控制，僅負(fù)責(zé)根據(jù)地址改變量子存儲(chǔ)器中某個(gè)或者某幾個(gè)量子位的狀態(tài)，量子運(yùn)算器可對(duì)指定量子位進(jìn)行一些基本

18、量子門的操作，這些量子門操作可作為該體系結(jié)構(gòu)下的基本量子指令。 量子運(yùn)算器與主控端和量子存儲(chǔ)器間存在控制流的交互，量子運(yùn)算器作用于量子存儲(chǔ)器內(nèi)的量子態(tài)。（3）控制器：通用量子計(jì)算機(jī)的控制器是主控端經(jīng)典計(jì)算機(jī)的控制器，控制器不僅控制著經(jīng)典計(jì)算部分的運(yùn)算，還在相應(yīng)系統(tǒng)軟件的操縱下通過(guò)主控端與量子計(jì)算部分的接口和 通信設(shè)備控制著量子協(xié)處理端的各個(gè)部件。因此，控制器是該體系結(jié)構(gòu)中起控制作用的核心部件，它與經(jīng)典存儲(chǔ)器、ALU、量子存儲(chǔ)器、量子運(yùn)算器以及經(jīng)典輸入、輸出設(shè)備和量子輸入、輸出接口(界面)設(shè)備之間均存在著控制流的交互。另外，由于馮諾依曼程序儲(chǔ)存 體系結(jié)構(gòu)的需要，程序和數(shù)據(jù)(包括控制量子運(yùn)算部分的

19、程序和數(shù)據(jù))是儲(chǔ)存在經(jīng)典存儲(chǔ)器當(dāng)中的，因此在經(jīng)典存儲(chǔ)器和控制器之間還有一條數(shù)據(jù)流。(4) 輸入設(shè)備：該體系結(jié)構(gòu)中經(jīng)典計(jì)算機(jī)部分的輸入設(shè)備與馮諾依曼體系結(jié)構(gòu)中所述的輸入設(shè)備無(wú)異；量子計(jì)算部分的輸入設(shè)備是一種將經(jīng)典計(jì)算所用的數(shù)據(jù)轉(zhuǎn)換為量子計(jì)算 所用數(shù)據(jù)的經(jīng)典設(shè)備，稱之為“ 量子輸入界面設(shè)備”。它接受主控端的指令及經(jīng)典數(shù)據(jù)信息 并將其轉(zhuǎn)換為概率幅信息。 必須強(qiáng)調(diào)的是，量子輸入界面設(shè)備本身不操控量子態(tài)，而僅受控產(chǎn)生量子態(tài)的概率幅信息，真正將概率幅信息轉(zhuǎn)換為量子數(shù)據(jù)的物理態(tài)并置入量子存儲(chǔ)器的過(guò)程需要通過(guò)量子運(yùn)算器完成。量子輸入界面設(shè)備與量子運(yùn)算器之間存在單向數(shù)據(jù)流，并通過(guò)通信接口與控制器存在控制流交互。

20、(5) 輸出設(shè)備：該體系結(jié)構(gòu)中經(jīng)典計(jì)算機(jī)部分的輸出設(shè)備與馮諾依曼體系結(jié)構(gòu)中所述的輸出設(shè)備無(wú)異；量子計(jì)算部分的輸出設(shè)備是一種將量子態(tài)轉(zhuǎn)換為經(jīng)典數(shù)據(jù)的設(shè)備，它即具有量子物理屬性又具有經(jīng)典物理屬性的，稱之為“量子輸出界面設(shè)備”。量子輸出界面設(shè)備中內(nèi)置一個(gè)量子測(cè)量器件，該器件屬于量子設(shè)備。量子輸出界面設(shè)備接受主控端的控制，直接根據(jù)地址訪問(wèn)量子存儲(chǔ)器中的某個(gè)量子位，并由量子測(cè)量器件對(duì)其進(jìn)行投影測(cè)量，測(cè)量造成該量子位的狀態(tài)向其本征值(“0”或者“ 1 ”)坍縮，坍縮導(dǎo)致反映量子態(tài)的某個(gè)物理量 發(fā)生可測(cè)的變化，這個(gè)變化被測(cè)量器件探測(cè)到并根據(jù)其矢量的正負(fù)或者相位將其映射為經(jīng)典 數(shù)值0或者1，并將其以經(jīng)典比特的

21、形式輸出。量子輸出界面設(shè)備通過(guò)通信接口與控制器存 在控制流交互，在量子輸出界面設(shè)備與量子存儲(chǔ)器之間存在單向數(shù)據(jù)流。我們給出一個(gè)所提出的通用量子計(jì)算機(jī)體系結(jié)構(gòu)的示意圖，見(jiàn)圖2。從圖中可以清晰地看出通用量子計(jì)算機(jī)各個(gè)組成部件之間的數(shù)據(jù)流和控制流。圖制蜓農(nóng)I殳* Mt*KI詛燈粧“設(shè)齊*如典吒制論 峠證電政崔加Mb S rKMit為了清晰地說(shuō)明上述體系結(jié)構(gòu)下的量子計(jì)算流程，有必要簡(jiǎn)述通用量子計(jì)算機(jī)一般的解題過(guò)程。目前被普遍認(rèn)同的量子計(jì)算理論建立在一套量子力學(xué)的數(shù)學(xué)框架之上，這個(gè)框架被總結(jié)為量子力學(xué)的“四大公設(shè)(postulates) ” 10。根據(jù)該框架，通用量子計(jì)算的一般步驟是11:(1) 初化(

22、initialization ):在量子設(shè)備中產(chǎn)生初態(tài)的過(guò)程。即在量子設(shè)備中制備輸入數(shù)據(jù) 對(duì)應(yīng)的量子物理態(tài)，初態(tài)既可以是確定的基態(tài)也可以是已知概率幅的疊加態(tài)；(2) 演化(evolution):在量子計(jì)算設(shè)備的操控下，量子位的態(tài)遵從量子力學(xué)原理在孤立物理環(huán)境下隨時(shí)間進(jìn)行變化的過(guò)程。由量子力學(xué)的第二公設(shè)可知，所有量子態(tài)的演化都是酉演化（unitary evolution），任何酉演化都可用酉矩陣精確描述；（3）測(cè)量（measurement）:量子計(jì)算部分完成所有演化后，計(jì)算結(jié)果存在于量子態(tài)中，欲將 其轉(zhuǎn)換為經(jīng)典數(shù)據(jù)，必須執(zhí)行測(cè)量步驟。該步驟一般是對(duì)計(jì)算結(jié)果所在量子位進(jìn)行量子投影 測(cè)量，測(cè)量使量子

23、位狀態(tài)向本征值坍縮，坍縮到不同本征值的概率為其疊加態(tài)中不同基態(tài)所對(duì)應(yīng)的概率幅之輻角主值。量子投影測(cè)量?jī)x器會(huì)將量子態(tài)坍縮得到的本征值通過(guò)表征物理量 的變化轉(zhuǎn)換為經(jīng)典信息 0或者1坍縮所引起的信息損失是不可逆的。一經(jīng)測(cè)量，當(dāng)前量子 計(jì)算操作即宣告結(jié)束，要進(jìn)行新一輪計(jì)算必須將原計(jì)算所涉及的所有量子位重置為零基態(tài)。 經(jīng)過(guò)測(cè)量，所需要的結(jié)果就會(huì)以經(jīng)典形式得到，這個(gè)結(jié)果以經(jīng)典數(shù)據(jù)形式傳出并送往經(jīng)典計(jì)算部分，通過(guò)進(jìn)一步分析該數(shù)據(jù)的可信度以確定使用此數(shù)據(jù)還是重新進(jìn)行該步驟的量子計(jì) 算。在假設(shè)通用量子計(jì)算機(jī)已經(jīng)具有相應(yīng)的系統(tǒng)軟件（包括經(jīng)典軟件系統(tǒng)和量子軟件系統(tǒng)） 的情況下，下面將詳細(xì)闡述在所提通用量子計(jì)算機(jī)體系

24、結(jié)構(gòu)下一個(gè)通用量子計(jì)算的流程。4本文體系結(jié)構(gòu)下通用量子計(jì)算的流程根據(jù)我們所提通用量子計(jì)算機(jī)體系結(jié)構(gòu)以及量子圖靈機(jī)計(jì)算模型，在計(jì)算開(kāi)始之前，所有的程序和數(shù)據(jù)（包括量子程序、量子數(shù)據(jù)和經(jīng)典數(shù)據(jù)）均以經(jīng)典數(shù)據(jù)的形式儲(chǔ)存于經(jīng)典存 儲(chǔ)器內(nèi)。通用量子計(jì)算機(jī)的主控部分在操作系統(tǒng)軟件的支撐下將經(jīng)典存儲(chǔ)器內(nèi)的程序所對(duì)應(yīng) 的指令逐一執(zhí)行。在本文所提體系結(jié)構(gòu)中，所有不涉及量子運(yùn)算的經(jīng)典計(jì)算均由主控端負(fù)責(zé)， 當(dāng)需要進(jìn)行量子計(jì)算時(shí)，量子協(xié)處理端就會(huì)在執(zhí)行第一條量子指令前由主控端啟動(dòng)；啟動(dòng)時(shí)，協(xié)處理端將量子存儲(chǔ)器內(nèi)的所有量子位的狀態(tài)制備為零基態(tài)（即量子位0態(tài)的概率幅為1，1態(tài)的概率幅為0），等待初化指令的到來(lái)。量子計(jì)算部

25、分的工作以初化指令開(kāi)始，此時(shí)主控端控制器通過(guò)經(jīng)典-量子部分的通信接口向量子輸入界面設(shè)備發(fā)出初化指令（包含要初化的量子位在量子存儲(chǔ)器內(nèi)的絕對(duì)地址），同時(shí)經(jīng)典輸出設(shè)備也通過(guò)通信接口向量子輸入界面設(shè)備發(fā)送待初化的量子數(shù)據(jù)（經(jīng)典形式）。例如，量子輸入界面設(shè)備接收到的信息可表示為“將001地址的量子位初始化為 1 ”，得到這些信息之后，量子輸入界面設(shè)備會(huì)將經(jīng)典形式的量子數(shù)據(jù)信息轉(zhuǎn)換為量子形式的信息，如將上例中的“ 1”轉(zhuǎn)換為“ 0態(tài)的概率幅為0, 1態(tài)的概率幅為1”，這些信息隨同絕對(duì)地址一 起交由量子運(yùn)算器。量子運(yùn)算器同樣在主控端控制器的控制下開(kāi)始動(dòng)作，它首先確定絕對(duì)地址所指向的量子位，如將001地址定

26、位為量子存儲(chǔ)器中第一個(gè)量子位，然后對(duì)指定量子位進(jìn)行相應(yīng)的量子門操作，將其狀態(tài)改變?yōu)橛?jì)算所需的初態(tài)。如上例，量子運(yùn)算器對(duì)第一個(gè)量子位進(jìn)行“非變換”（對(duì)換0，1態(tài)的概率幅），就可將001地址量子位由量子 0態(tài)置為1態(tài)， 從而完成了這條初化指令。經(jīng)過(guò)若干次這樣的操作，所有指定的量子變量就具有了初值。接下來(lái)是演化過(guò)程，在量子協(xié)處理端該過(guò)程僅量子運(yùn)算器和量子存儲(chǔ)器參與。執(zhí)行過(guò)程中，主控端控制器依次向量子運(yùn)算器發(fā)送量子門的代號(hào)和要操作量子位的絕對(duì)地址（均為經(jīng)典形式），量子運(yùn)算器則根據(jù)這些信息依次對(duì)量子存儲(chǔ)器內(nèi)的相應(yīng)量子位定位并發(fā)出各種門 的演化信號(hào)（如射頻脈沖）從而完成量子狀態(tài)的酉演化。值得注意的是，與經(jīng)

27、典算術(shù)邏輯運(yùn)算不同，量子運(yùn)算器進(jìn)行的量子計(jì)算完全是在量子存儲(chǔ)器內(nèi)進(jìn)行的，在前者與后者之間僅有量子控制流（可改變量子位狀態(tài)的控制流），而沒(méi)有任何數(shù)據(jù)流，量子存儲(chǔ)器內(nèi)量子位的狀態(tài)演化完全是依據(jù)時(shí)間進(jìn)行的（由量子力學(xué)第二公設(shè)決定），因此每一步量子門運(yùn)算是否完成將依賴于兩次計(jì)算的時(shí)間間隙（根據(jù)不同量子門而存在差異）。在所有的演化完成后，量子輸出界面設(shè)備在主控端控制器的命令下根據(jù)地址對(duì)量子存儲(chǔ) 器中的特定量子位發(fā)出測(cè)量信號(hào)，使該量子位發(fā)生坍縮， 獲取坍縮后的本征值狀態(tài)并將其轉(zhuǎn) 換為經(jīng)典比特0或者1進(jìn)而將量子計(jì)算設(shè)備輸出的結(jié)果回送到主控端經(jīng)典存儲(chǔ)器內(nèi)，由主 控端處理。測(cè)量操作之后，本輪量子計(jì)算完成， 量子

28、計(jì)算部分將重新制備零基態(tài)，等待新一輪量子計(jì)算的開(kāi)始。5通用量子計(jì)算機(jī)量子存儲(chǔ)器的結(jié)構(gòu)與經(jīng)典計(jì)算相比，由于其物理背景的特殊性，量子計(jì)算物理實(shí)現(xiàn)中的某些問(wèn)題在目前以及未來(lái)相當(dāng)長(zhǎng)時(shí)間內(nèi)不論從理論上還是技術(shù)上都有巨大的困難。然而，通過(guò)對(duì)通用量子計(jì)算機(jī)體系結(jié)構(gòu)的合理修改，可以在很大程度上避免這些問(wèn)題。量子計(jì)算的物理實(shí)現(xiàn)所面臨的最重要的困難是退相干(decohere nee)問(wèn)題，這已經(jīng)在實(shí)驗(yàn)上得到了證實(shí)12。簡(jiǎn)言之，產(chǎn)生退相干的原因是由于進(jìn)行量子計(jì)算的物理系統(tǒng)不可能對(duì) 外界環(huán)境絕對(duì)封閉，外界的影響可造成呈相干量子態(tài)的量子位的相干性減弱或者消失。退相干對(duì)量子計(jì)算影響極大：一方面隨著量子態(tài)相干性的減弱，量子

29、態(tài)將開(kāi)始自行向其本征態(tài)演化，造成信息的丟失，根據(jù)量子態(tài)不可克隆原理，退相干造成的量子信息流失將直接導(dǎo)致計(jì)算的失敗或結(jié)果錯(cuò)誤；另一方面，量子計(jì)算中對(duì)某個(gè)量子位的控制一般是依靠若干量子態(tài)間 的相干性來(lái)完成的，退相干將破壞這種間接的控制力，使得許多量子位無(wú)法被有效操控。退相干是與量子位受控時(shí)間和相干環(huán)境內(nèi)量子位數(shù)目有關(guān)的非線性效應(yīng)，它的產(chǎn)生機(jī)理尚不十分明確13。從有效量子態(tài)制備成功之時(shí)到量子態(tài)受到退相干現(xiàn)象干擾而發(fā)生信息損失之間 的時(shí)間稱為相干時(shí)間(cohere nee time),在目前技術(shù)狀況下根據(jù)不同的物理實(shí)現(xiàn)方式，10個(gè)量子位的量子體系相干時(shí)間一般介于10_10少秒，且隨量子位數(shù)目的增加指數(shù)

30、級(jí)減少，這相對(duì)于復(fù)雜的量子計(jì)算來(lái)說(shuō)相當(dāng)短暫。因此，在物理學(xué)界尚無(wú)有效辦法避免退相干現(xiàn)象時(shí)， 如何減小退相干對(duì)通用量子計(jì)算的影響成為設(shè)計(jì)量子計(jì)算體系結(jié)構(gòu)所考慮的一個(gè)重要問(wèn)題。在我們所提的通用量子計(jì)算機(jī)體系結(jié)構(gòu)下，所有的計(jì)算和存儲(chǔ)均發(fā)生在量子存儲(chǔ)器內(nèi)， 量子存儲(chǔ)器也是唯一包含量子位的量子設(shè)備。以此為前提，我們?cè)贠skin等提出的容錯(cuò)量子計(jì)算機(jī)存儲(chǔ)體系結(jié)構(gòu)14的基礎(chǔ)上提出了一種改進(jìn)量子存儲(chǔ)體系結(jié)構(gòu)以期避免退相干現(xiàn)象對(duì) 量子計(jì)算和量子存儲(chǔ)的影響。本文提出的改進(jìn)量子存儲(chǔ)體系結(jié)構(gòu)示意圖見(jiàn)圖3。量子存儲(chǔ)器中有若干量子存儲(chǔ)池(quantum memory pool)，每個(gè)存儲(chǔ)池中包含若干可用量子位及一個(gè)量子隱

31、形傳態(tài)(quantumteleportation)控制器和一個(gè)量子位相干性保持單元。圖3量子存儲(chǔ)體系結(jié)構(gòu)示意圖在量子存儲(chǔ)池中，每組(圖中的行)中的每?jī)蓚€(gè)相鄰的量子位之間均保持量子相干效應(yīng)，這種相干效應(yīng)伴隨著量子存儲(chǔ)器初化而開(kāi)始具有并由量子相干性保持單元保持。量子相干性保持單元是一種量子設(shè)備，它通過(guò)向相干量子體系中補(bǔ)充能量、保持概率幅或者相位校正等方式來(lái)校正因外界干擾導(dǎo)致能量耗散(energy dissipation)、概率幅衰減(amplitude damping)或者相位隨機(jī)化(phase ran domization、而產(chǎn)生的退相干效應(yīng) 問(wèn)。因此，這種量子存儲(chǔ)體系 結(jié)構(gòu)具有硬件容錯(cuò)性，可避

32、免或減小使用量子糾錯(cuò)碼所產(chǎn)生的額外量子位存儲(chǔ)空間開(kāi)銷。所有量子器件之間的通信都是量子信息的傳輸，這依靠稱之為量子線(quantum wire )的邏輯信息通路進(jìn)行。量子線由Oskin等提出15,事實(shí)上是一列輔助量子位加上一些制備好的EPR對(duì)并依賴量子隱形傳態(tài)控制設(shè)備進(jìn)行量子隱形傳態(tài)的物理實(shí)體。使用量子線的好處 有二：一是量子線上的所有量子位通過(guò)EPR對(duì)形成一種相互糾纏的貓態(tài)(cat state)”，這種糾纏度最大的糾纏態(tài)為量子信息傳輸過(guò)程中的容錯(cuò)和糾錯(cuò)提供了很好的條件16;二是Gottesman等提出，量子隱形傳態(tài)控制器在通過(guò)量子線向某個(gè)量子位傳送量子信息的同時(shí)可 以進(jìn)行一個(gè)任意量子門的計(jì)算W

33、，這大大提高了量子計(jì)算和存儲(chǔ)體系的協(xié)同性和并行性。另外，使用量子線還為量子存儲(chǔ)體系提供了良好的可擴(kuò)充性，如可以在圖3中中心量子線的頂端加入新的量子存儲(chǔ)器池；量子位數(shù)目的擴(kuò)充將使量子計(jì)算能力指數(shù)級(jí)提高。6本文體系結(jié)構(gòu)下量子程序運(yùn)行效率分析為了驗(yàn)證所提體系結(jié)構(gòu)在計(jì)算效率上的優(yōu)勢(shì)，我們針對(duì)本模型和另一種存儲(chǔ)遷移體系結(jié)構(gòu)模型分別設(shè)計(jì)了模擬實(shí)驗(yàn)。存儲(chǔ)遷移體系結(jié)構(gòu)模型的特點(diǎn)是，在量子運(yùn)算器和量子輸出設(shè)備中設(shè)置量子寄存單元(quantum register),量子計(jì)算發(fā)生的位置在量子運(yùn)算器而非本文體 系結(jié)構(gòu)下的量子存儲(chǔ)單元；同樣，量子計(jì)算結(jié)果的讀出也發(fā)生在量子輸出設(shè)備中。這樣計(jì)算過(guò)程中必須大量運(yùn)用對(duì)換(sw

34、ap、指令將寄存單元中的數(shù)據(jù)置入主存(主量子存儲(chǔ)單元) 或從主存中讀出，不但影響計(jì)算的效率，還嚴(yán)重影響了體系的相干時(shí)間，加大了容錯(cuò)量子運(yùn)算的難度。為了展示兩種結(jié)構(gòu)運(yùn)算效率的差異，我們用NDQJava語(yǔ)言編寫了 Shor算法在不同的輸入數(shù)據(jù)規(guī)模下的程序，并將其分別編譯至兩種模型的體系結(jié)構(gòu)下的基本量子操作序列，關(guān)于NDQJava語(yǔ)言及其編譯程序的說(shuō)明請(qǐng)參見(jiàn)18與19。程序輸入的待分解整數(shù)為：15（8量子位），105（ 12量子位），217（ 16量子位），1843（ 22量子位），11333（ 28量子位）和37237（ 32量子位）。圖4比較了這兩種體系結(jié)構(gòu)下同一組程序編譯所產(chǎn)生的量子基本操 作

35、序列20（sequenee of elementary operation, SEO）的長(zhǎng)度差異。 由于在特定物理實(shí)現(xiàn)平臺(tái)下 一個(gè)基本量子門的執(zhí)行時(shí)間相對(duì)恒定13，故量子基本操作序列的長(zhǎng)度是刻畫該體系結(jié)構(gòu)下程序執(zhí)行效率的重要標(biāo)準(zhǔn)。悴親齬構(gòu)16000140OT12000整 10000計(jì) 800040W20000輸入數(shù)據(jù)規(guī)模（業(yè)子位）圖4.兩種不同的量子計(jì)算機(jī)體系結(jié)構(gòu)對(duì)應(yīng)的量子基本操作序列長(zhǎng)度的差異7總結(jié)本文考慮了通用量子計(jì)算機(jī)所需要的體系結(jié)構(gòu)上的必備條件以及如何在該條件下高效、 精確地進(jìn)行量子計(jì)算，并在此基礎(chǔ)上提出了一個(gè)通用量子計(jì)算機(jī)體系結(jié)構(gòu)并重點(diǎn)討論了其中 量子存儲(chǔ)器的結(jié)構(gòu)。在此體系結(jié)構(gòu)下，可

36、以進(jìn)行通用、容錯(cuò)、高效的量子計(jì)算，并能有效避免量子資源的浪費(fèi)。對(duì)此體系結(jié)構(gòu)尚需從事的研究還有：（1）在量子存儲(chǔ)器中加入量子糾錯(cuò)處理系統(tǒng)，將其與現(xiàn)有的量子線等量子容錯(cuò)體系結(jié) 合發(fā)揮量子糾錯(cuò)作用，并研制專門適合該體系結(jié)構(gòu)的高效、低代價(jià)的量子糾錯(cuò)碼；（2 ）在量子運(yùn)算器中加入動(dòng)態(tài)調(diào)度單元，使量子運(yùn)算器發(fā)出的量子操作指令流的順序 更加合理，以提高量子運(yùn)算的功效；（3 ）研制該體系結(jié)構(gòu)基于經(jīng)典計(jì)算機(jī)的量子計(jì)算能力模擬軟件，提供相應(yīng)的數(shù)據(jù)以輔 助對(duì)通用量子計(jì)算機(jī)體系結(jié)構(gòu)的完善和改進(jìn)。致謝：本文的寫作得到南京大學(xué)計(jì)算機(jī)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室徐家福教授的悉心指導(dǎo)和耐心修改，南京大學(xué)量子計(jì)算與量子信息討論班的

37、全體成員均為本文提供材料并參與討論，藉此向徐家福教授和討論班全體老師同學(xué)致以深深的敬意謝忱！參考文獻(xiàn)1 Nielse n M, Chua ng I. Quan tum computati on and qua ntum in formatio n . Cambridge Uni versity Press, 2000.2 Qua ntum In formatio n Science and Tech no logy(QulST) programmer. 2.0). Defense Adva need Research Projects Age ncy(DARPA), 2004.3 Lu C,

38、Zhou X, Guhen, O, et al. Experimental entanglement of six photons in graph states.Nature Physics. 3(2), pp.91-95, 2007.4 Wu N, Song Fangmin. Quan tum comput ing and qua ntum computers.Journal of Fron tiers ofComputer Scienee and Technology. 1 (1), pp.1-16, 2007.(吳楠，宋方敏.量子計(jì)算與量子計(jì) 算機(jī).計(jì)算機(jī)科學(xué)與探索.1(1), pp.

39、1-16, 2007.)5 Deutsch D. Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. R. Lond. A, 400, pp.97-117, 1985. Bernstein E, Vazirani U. Quantum complexity theory. SIAM Journal on Computing, 26(5), pp.1411-1473.7 Benn ett C. Logical reversibility of computatio n.IBM

40、J.Res.Develop, 17, pp.525-532, 1973.8 Knill E. Conventions for quantum pseudocode, LANL report LAUR-96-2724 , 1996.9 Bettelli S, Calarco T, et al. Toward an architecture for quantum programming. qua nt-ph/0103009 v2, 2001.10 von Neumann, J. Mathematical foundations of quantum mechanics. Princeton Un

41、iversity Press, 1955.11 DiVi ncenzo D. Qua ntum computatio n. Scie nee, 270(5234),255,1995.12 Vandesypen L, Steffen M, Breyta M et al. Experimental realization of Shor quantum factoring algorithm using nuclear magnetic resonance. Nature, 414(6866), pp.883-887, 2001.13 Steffen M. A prototype quantum

42、computer using nuclear spins in liquid solution.Dissertationfor the degree of Ph.D., Stanford University, 2003.14 Oksin M, Chong F, Chunag I. A practical architecture for reliable qua ntum computers. IEEE Computer, 35(1), pp.79-87, 200215 Oskin M, Chong F, Chua ng I, et al. Buildi ng qua ntum wires:

43、 the long and the short of it. In:the 30th Ann ual In ternatio nal Symposium on Computer Architecture (ISCA) . 2003.16 Seife C. Teaching qubits new tricks. Scienee, 309, p.238, 2005.17 Gottesma n D, Chua ng I. Demon strat ing the viability of uni versal qua ntum computatio n using teleportation and

44、single-qubit operations. Nature, 402(6760), pp.390-393, 199918 Xu J, Song F, Qian S, et al. Quantum programming Ianguage NDQJava. Journal of Software , 19(1), pp.1-8, 2008.(徐家福，宋方敏，錢士鈞等 .量子程序設(shè)計(jì)語(yǔ)言 NDQJava.軟件學(xué)報(bào). 佃(1), pp.1- 8, 2008.)19 Song F, Qian S, Dai J, et al. Process ing system of qua ntum progr

45、am ming Ian guage NDQJava. Journal of Software ,佃(1), pp.9-16 , 2008.(宋方敏，錢士鈞，戴靜安等 .量子程序設(shè)計(jì)語(yǔ)言 NDQJava 處理系統(tǒng).軟件學(xué)報(bào).19(1), pp.8- 16, 2008.)20 Tucci R. A rudimentary quantum compiler. arXiv: quant-ph/0411097, 2004.作者簡(jiǎn)介:吳楠（1981-），山東濟(jì)南人，2004年獲得南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系理學(xué)學(xué)士學(xué)位，現(xiàn)為 南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系碩博連讀研究生，研究領(lǐng)域?yàn)榱孔佑?jì)算，量子計(jì)算機(jī)及其物理實(shí)現(xiàn)。參與江蘇省自然科學(xué)基金項(xiàng)目，863項(xiàng)目和中法合作項(xiàng)目的研究，在國(guó)內(nèi)重要學(xué)術(shù)期刊上發(fā)表論文8篇。聯(lián)系方式：WU Nan received the BSc degree in computer science from Nanjing University, China in 2004, his is now a Ph.D.