量子計(jì)算機(jī)概述

楊洪應(yīng)

摘 要 眾所周知，計(jì)算機(jī)的發(fā)明為許多進(jìn)行大量計(jì)數(shù)字運(yùn)算的問題提供了一條捷徑，其能力是一般的人工無法比擬的。但是有的問題是經(jīng)典計(jì)算機(jī)無法解決的，運(yùn)用量子計(jì)算卻能很快的解決。本文將對(duì)量子計(jì)算機(jī)做一個(gè)簡(jiǎn)單介紹。

關(guān)鍵詞 量子信息 量子比特 量子計(jì)算機(jī) Shor算法

中圖分類號(hào)：O561 文獻(xiàn)標(biāo)識(shí)碼：A

0引言

半導(dǎo)體工業(yè)在過去的幾十年發(fā)展表明：計(jì)算機(jī)的中央處理器在每1-2年就會(huì)增長一倍，芯片上的集成的晶體管數(shù)目更是呈指數(shù)形式增長。在不遠(yuǎn)的將來每個(gè)芯片上的晶體管將會(huì)超過十億個(gè)，這樣的增長速度使得半導(dǎo)體的加工變得越來越困難。另一方面，隨著納米技術(shù)的發(fā)展，今后計(jì)算機(jī)的儲(chǔ)存尺度單位將是原子級(jí)別的。當(dāng)人們把這些器件加工到原子尺度程度的時(shí)候，就應(yīng)該用量子理論來描述這些性質(zhì)。量子理論作為描述微觀世界的理論，它具有與經(jīng)典理論有許多的不同之處，甚至和我們?nèi)粘＝?jīng)驗(yàn)發(fā)生矛盾。

在1994年P(guān)eter Shor首次提出一種具體的量子大數(shù)因子分解加密算法，這個(gè)對(duì)RSA等公鑰密碼系統(tǒng)的安全性來說是一個(gè)挑戰(zhàn)。隨后在1996年，Grover發(fā)現(xiàn)了Grover迭代算法，它能求解某些解典計(jì)算機(jī)不能解決的問題，如經(jīng)典的NPC問題。除此外，利用量子不可克隆實(shí)現(xiàn)保密通信，可以防止通信過程中被監(jiān)聽。這些性質(zhì)使得量子通信具有廣泛地應(yīng)用前景而成為一個(gè)較熱的課題。量子信息和量子計(jì)算已被我國列入“十三五”重大研究課題。

1量子比特

在經(jīng)典的計(jì)算機(jī)里，基本的構(gòu)造單元是比特。不論是用電子管來實(shí)現(xiàn)的一個(gè)比特還是用晶體管來實(shí)現(xiàn)的比特，其基本原理都要遵從牛頓力學(xué)定律。在一個(gè)經(jīng)典的計(jì)算機(jī)里，其儲(chǔ)存量是用比特的多少來衡量的。它的運(yùn)算速度可有單位時(shí)間內(nèi)比特的轉(zhuǎn)換數(shù)目來決定。

在圖1中可以看到，經(jīng)典的比特實(shí)質(zhì)是就是兩個(gè)點(diǎn)10>和11>，所以在儲(chǔ)存的時(shí)候也只能是10>和11>。因此我們想要提高其運(yùn)行速度就受到了原理上的限制。首先是我們?cè)谧非笏俣葧r(shí)，就需要不斷地提高微電子元件的集成度，小型化的電子器件必然會(huì)受到量子極限尺寸的限制。其次就是由于經(jīng)典計(jì)算機(jī)的操作是不可逆的，由熱力學(xué)原理知道，計(jì)算芯片必然發(fā)熱，這是提高經(jīng)典計(jì)算機(jī)的計(jì)算能力主要障礙。最后就是經(jīng)典計(jì)算機(jī)不具備內(nèi)在的并行運(yùn)算。通過連接更多的計(jì)算資源來解決并行運(yùn)算是比較復(fù)雜且難以實(shí)現(xiàn)的。

2量子比特

量子比特是計(jì)算信息科學(xué)里一個(gè)重要的概念，是量子計(jì)算機(jī)的基本單元，因此在這里我們對(duì)它做一個(gè)詳細(xì)的介紹。

量子比特其可以對(duì)應(yīng)量子力學(xué)里一個(gè)粒子態(tài)的疊加，對(duì)于一個(gè)自旋為1/2的粒子，其本征態(tài)為兩種定態(tài) ，單粒子的疊加態(tài)可表示為

| >= |1>+ |0> （1.1）

這里的 ， 為任意復(fù)數(shù)，其分別對(duì)應(yīng)兩個(gè)定態(tài)在疊加態(tài)中所占的比例，如果 =0或者是 =0 時(shí)，疊加態(tài)就轉(zhuǎn)化為定態(tài)，兩個(gè)系數(shù)的模方 分別代表粒子狀態(tài)在每一個(gè)定態(tài)中的幾率。Bloch球面中則表示在量子力學(xué)里一個(gè)一把態(tài)的疊加。我們可以看到，經(jīng)典的兩個(gè)比特只是Bloch球面中一種特殊的情況，其被Bloch球面所包圍。而量子態(tài)在三維的坐標(biāo)中表示出來就是Bloch球面上的一個(gè)點(diǎn)。所以一個(gè)量子比特有無窮個(gè)態(tài)，每個(gè)態(tài)對(duì)應(yīng)Bloch上的一個(gè)點(diǎn)，對(duì)量子比特進(jìn)行操縱，就是把Bloch球面上的一個(gè)點(diǎn)移到另外的一個(gè)點(diǎn)，這個(gè)操縱是一個(gè)幺正變換。

3量子計(jì)算機(jī)

從（1.1）式我們可以看到，經(jīng)典計(jì)算機(jī)是只是量子計(jì)算機(jī)的特例，量子計(jì)算機(jī)是經(jīng)典計(jì)算機(jī)的推廣，這一推廣使得其計(jì)算能力成指數(shù)倍的增長。對(duì)于由量子力學(xué)原理所支配的量子計(jì)算機(jī)來說，原則上制約著經(jīng)典計(jì)算機(jī)計(jì)算能力的原理都不存在，首先因?yàn)闃?gòu)成量子計(jì)算機(jī)的一些芯片實(shí)質(zhì)上就是量子器件。其次是量子計(jì)算是由一系列幺正演化來完成的，所以這是一個(gè)可逆的過程，不存在耗熱問題。最后就是量子計(jì)算是建立在量子疊加態(tài)基礎(chǔ)上的，所以具有并行性運(yùn)算能力。因而某些在經(jīng)典的計(jì)算機(jī)里需要進(jìn)行指數(shù)倍運(yùn)算，在量子計(jì)算機(jī)里卻只需進(jìn)行多項(xiàng)式分解運(yùn)算。

其實(shí)，在早期（1982年）就有人預(yù)想到了量子元件的計(jì)算能力比經(jīng)典的元件強(qiáng)很多，不過在這個(gè)時(shí)期并沒有受到人們的關(guān)注。直到20世紀(jì)初Shor首次提出Shor算法后使得量子計(jì)算機(jī)有了現(xiàn)實(shí)意義，即能對(duì)現(xiàn)行信息安全所依仗的大數(shù)因子分解難題進(jìn)行有效的破解。從此以后就有越來越多的科研工作者開始關(guān)注量子計(jì)算機(jī)，關(guān)心和探討適合量子元件運(yùn)算規(guī)律的算法。

要實(shí)現(xiàn)量子計(jì)算過程，大致有一下三個(gè)步驟：

首先是初態(tài)的制備，在經(jīng)典的計(jì)算機(jī)中，進(jìn)行一個(gè)有用的計(jì)算最重要的要求是制備期望的輸入。同樣在量子計(jì)算機(jī)里，我們將芯片中的各個(gè)比特制備在某個(gè)特定的量子態(tài)上，這個(gè)過程中要求比特保持良好的量子相干性，以便保證量子疊加態(tài)能夠一直成立。

其次是去實(shí)施完成所預(yù)想的各種可逆幺正變換，這些幺正變換就是我們通常所說的各種操作。在量子計(jì)算機(jī)里，人們相信量子計(jì)算機(jī)和經(jīng)典計(jì)算機(jī)一樣，都是由一系列的基本的邏輯運(yùn)算組成。目前已經(jīng)證明任何的量子計(jì)算都可以通過一個(gè)基本量子邏輯門集的組合來完成。

最后就是信息的讀取，對(duì)量子器件進(jìn)行測(cè)量來讀出計(jì)算結(jié)果。需要注意的是，量子力學(xué)所掌握的是關(guān)于微觀系統(tǒng)的規(guī)律是一種統(tǒng)計(jì)規(guī)律，它只能告訴我們?cè)谀硞€(gè)時(shí)刻一個(gè)微觀系統(tǒng)的各個(gè)物理量取不同值的概率。在大多數(shù)時(shí)候，我們得到的末態(tài)有可能也是一個(gè)量子疊加態(tài)，所以我們測(cè)量的結(jié)果一般都是概率性的。量子計(jì)算通常要重復(fù)多次才能得到比較明確的結(jié)果。

4量子算法

在Shor算法為提出以后，人們意識(shí)到這將對(duì)當(dāng)今廣泛應(yīng)用著的公匙密碼體系的安全性構(gòu)成嚴(yán)重的威脅，因?yàn)樗軐?shí)現(xiàn)大數(shù)因子分解。

通常來說，RSA公匙密碼體系中，密碼的生成方式是這樣的：第一步是去尋找兩個(gè)大的質(zhì)數(shù)m，n，計(jì)算Q=mn的值以及歐拉函數(shù) （Q）=（m 1） （n 1）。第二步是在區(qū)間1≤e≤ （Q）隨機(jī)選擇一個(gè)和 （Q）互質(zhì)的整數(shù)，計(jì)算模 （Q）下的逆元d=e-1mod （Q）；最后一步是定義公匙私匙（M，e）是d。

由此可知，RAS公匙密碼的安全性完全取決于大整數(shù)n的質(zhì)因數(shù)分解的困難性，目前經(jīng)典計(jì)算機(jī)是不能破解的。而在物理上，Shor量子算法是有效的，Shor算法是對(duì)大數(shù)因子分解的一種有效的算法：其復(fù)雜程度隨著問題的規(guī)模只是多項(xiàng)式的增加。

5結(jié)論

在本文我們介紹了經(jīng)典的比特和量子比特。經(jīng)典的比特只是Bloch球上的兩個(gè)點(diǎn)，而量子比特則是Bloch球上的所有點(diǎn)。可以看出，經(jīng)典比特只是量子比特的一種特例。同時(shí)我們也討論了經(jīng)典的計(jì)算機(jī)和量計(jì)算機(jī)，量子計(jì)算機(jī)所執(zhí)行的是一個(gè)可逆幺正演化且具備并行運(yùn)算的能力，使得量子計(jì)算機(jī)能解決經(jīng)典計(jì)算機(jī)所不能解決的問題，尤其是對(duì)大數(shù)因子的分解。量子計(jì)算機(jī)是目前量子信息科學(xué)中最重要的研究領(lǐng)域之一，這將是目前以及未來一段時(shí)間內(nèi)科學(xué)家門所要研究的重點(diǎn)。

參考文獻(xiàn)

[1] Shor P W.Scheme for reducing decoherence in quantum computer memory，Phys.Rev.A.1995，52（4）：2493-2496.

[2] Geover L K，Quantum computers can search rapidly by using almost any transformation.Phys.Rev.Lett.1998，80（19）：4329-4332.

[3] M.A.Nielsen and I.L.Chuang，Quantum Computation and Quantum Information （Cambridge University Press，U.K，2000）

[4] 曾謹(jǐn)言.量子力學(xué)（卷二）[M].科學(xué)出版社，2007

[5] 梁九卿.量子物理新進(jìn)展[M]，科學(xué)出版社，2011.