INTRODUCTION to Quantum Computer

INTRODUCTION to Quantum Computer

Particle-wave duality

We normally think of electrons, atoms and molecules as particles. But each of these objects can also behave as waves. This dual particle-wave behaviour was first suggested in the 1920's by Louis de Broglie.

This concept emerged as follows. Thomas Young's experiments with double slits in the early 1800's shows that light behaves as if it is a wave. But, strikingly, Einstein's explanation of the photoelectric effect in 1905 shows that light consists of particles. In 1923 de Broglie suggested this dual particle-wave property might apply to all particles including electrons. Then in 1926 Davisson and Germer found that electrons scattered off a crystal of nickel behaved as if they were waves. Since then neutrons, atoms and even molecules (including bucky balls) have been shown to behave as waves. The waves tell us where the particle is likely to be found.

This dual particle-wave property is exploited in quantum computing in the following way. A wave is spread out in space. In particular, a wave can spread out over two different places at once. This means that a particle can also exist at two places at once. This concept is called the superposition principle - the particle can be in a superposition of two places.

Bits and Qubits

The basic data unit in a conventional (or classical) computer is the bit, or binary digit. A bit stores a numerical value of either 0 or 1. An example of how bits are stored is given by a CD rom: ``pits'' and ``lands'' (absence of a pit) are used to store the binary data.

We could also represent a bit using two different electron orbits in a single atom. In most atoms there are many electrons in many orbits. But we need only consider the orbits available to a single outermost electron in each atom. The figure on the right shows two atoms representing the binary number 10. The inner orbits represent the number 0 and the outer orbits represent the binary number 1. The position of the electron gives the number stored by the atom.

However, a completely new possibility opens up for atoms. Electrons have a wave property which allows a single electron to be in two orbits simultaneously. In other words, the electron can be in a superposition of both orbits. The figure on the left shows two atoms each with a single electron in a superposition of two orbits. Each atom represents the binary numbers 0 and 1 simultaneously. The two atoms together represent the 4 binary numbers 00, 01, 10 and 11 simultaneously.

To distinguish this new kind data storage from a conventional bit, it is called a quantum bit which is shortened to qubit. Each atom in the figure above is a qubit. The key point is that a qubit can be in a superposition of the two numbers 0 and 1. Superposition states allow many computations to be performed simultaneously, and gives rise to what is known as quantum parallelism.

Quantum parallelism

A one bit memory can store one of the numbers 0 and 1. Likewise a two bit memory can store one of the binary numbers 00, 01, 10 and 11 (i.e. 0, 1, 2 and 3 in base ten). But these memories can only store a single number (e.g. the binary number 10) at a time.

As described above, a quantum superposition state allows a qubit to store 0 and 1 simultaneously. Two qubits can store all the 4 binary numbers 00, 01, 10 and 11 simultaneously. Three qubits stores the 8 binary numbers 000, 001, 010, 011, 100, 101, 110 and 111 simultaneously. The table below shows that 300 qubits can store more than 1090 numbers simultaneously. That's more than the number of atoms in the visible universe!

This shows the power of quantum computers: just 300 photons (or 300 ions etc.) can store more numbers than there are atoms in the universe, and calculations can be performed simultaneously on each of these numbers!

Qubit Systems

Ion traps

An ion is an atom with extra or missing electron. Being electrically charged, individual ions can be trapped using electric and magnetic fields. The linear ion trap pictured uses 4 rod electrodes (light blue) which are fed an AC voltage of about 1 kilovolt at a frequency of a few megahertz. This confines the ions (red dots) along a central line. The end-rings (dark blue) are electrically charged to prevent the ions from escaping at the ends.

Finely focused lasers are used to prepare and inspect individual ions. The outer electron of each ion is manipulated to be in two different orbits about the nucleus. Each ion therefore represents a qubit. As an ion scatters photons from the laser it recoils. Its recoil motion is felt by the other ions. This recoil motion is equivalent to the data bus of a classical computer

Quantum dots

Using advanced lithographic techniques it is possible to etch small structures called quantum dots in semiconductor materials. Each such dot, which can be as small as 30nm across (about 30 times the size of an atom) can confine a single electron in discrete energy levels.

Thus the quantum dot behaves like a large artificial atom and can be used as a qubit. A user can access individual quantum dots using focused laser beams which can flip the electron between two discrete energy levels or place it into a superposition of the two levels. The required interaction between qubits occurs through externally applied electric and optical fields.

Shor's algorithm

Shor's algorithm is a quantum algorithm for factoring a number N in O((log N)3) time and O(log N) space, named after Peter Shor.

Many public key cryptosystems, such as RSA, will become obsolete if Shor's algorithm is ever implemented in a practical quantum computer. A message encrypted with RSA can be deciphered by factoring the public key N, which is the product of two prime numbers. Known classical algorithms cannot do this in time O((log N)k) for any k, so they quickly become infeasible as N is increased. By contrast, Shor's algorithm can crack RSA in polynomial time. It has also been extended to attack many other public key cryptosystems.

Like all quantum computer algorithms, Shor's algorithm is probabilistic: it gives the correct answer with high probability, and the probability of failure can be decreased by repeating the algorithm.

Shor's algorithm was demonstrated in 2001 by a group at IBM, which factored 15 into 3 and 5, using a quantum computer with 7 qubits

Quantum Mechanics

We can describe the Quantum System by the mathematical way. In n-level system, any state can use the following equation to describe:

is orthonomal basis

計算速度突飛猛進的原因

現在的電腦是以「位元」為資訊的最小單位，來讀取1或0的值。相對來說，量子電腦則是以1和0疊加(superposition)表示的「量子位元」(quantum bit)為資訊的最小單位。在量子力學控制的世界裡，對於電子能夠取得的兩個狀態，可能呈現「量子力學疊加狀態」，也就是「兩種狀態都有」的奇妙狀態。

量子電腦就是對這種量子位元進行演算。1量子位元有2個疊加狀態，2量子位元有2^2(=4)個疊加狀態，3量子位元百2^3(=8)個疊加狀態，隨著量子位元數增加，疊加狀態數也以指數函數 (exponential function) 增加。由於量子電腦可以同時針對這許多疊加狀態加以演算，在某種計算上的計算速度便突飛猛進。

如果1000量子位元的量子電腦實用化，只花數十分鐘，將可計算目前超級電腦須花數百年計算的多位數質因素因子分解。

不斷開發的量子位元裝置

1999年，日本電氣公司基礎研究所中村泰信主任領先世界，成功開發與真的製造出量子電腦有關的單量子位元固態裝置(1 quantum bit solid-state device，即超導量子位元裝置)而受到矚目。

他將矽基板上的鋁薄膜製超導電路冷卻到-273℃左右(正確地說為絕對溫度0.03K)，在-273℃下製造出1和0的疊加狀態。

詳細說明請見.ppt

將有可能像目前製造電腦那樣，利用積體電路(integrated circuit) 製造量子電腦。目前中村主任正致力開發2量子位元裝置。

此外，日本理化學研究所青柳教授研究室也以碳奈管製「量子點」(quantum dot)，嘗試製造量子位元裝置。

量子點是1邊大約10奈米的超微粒狀物質，內部電子波行為明顯。青柳教授表示︰「以碳奈管為材料，只要控制長度，或許可以製造出性能極佳的量子位元裝置。」

量子電腦擅長的計算

量子電腦能超高速作任何計算嗎？中村主任說︰「量子電腦最適合處理像大數質因素因子分解那樣必須一一執行的龐大計算，因此可以在資料庫檢索、解決某物種最適化問題等方面發揮威力。」

「量子電腦將來可能不像現在個人電腦那樣屬於廣泛應用型，而是像超級電腦那樣，在必須超高速執行特定、龐大計算的條件下才使用。」

B90901036 電機三 莊子德

前言 :

資訊，本來就是離散的東西了。但是這與「量子資訊」還是不太一樣。在一般的電腦裡，我們用電位的高低代表「零」與「壹」，進而組成各種資訊。在量子電腦裡，我們用原子的能階來代表資訊的「零」與「壹」。用氫原子的基態表示「零」 (記為 | 0 > )，激發態表示「壹」( 記為 | 1 > )。一個位元的量子資訊，稱為 qubit，可以是這兩個狀態的線性組合；代表該位元在某一瞬間的狀態。這種狀態，我們稱為同調態 (co- herent states)。如此一串氫原子就可以組成各種資訊了。

量子資訊與古典資訊最大的不同在於︰古典資訊中，位元只能處在一個狀態，非0即1；而在量子資訊中，量子位元（量子系統）可以同時處在狀態|0＞和狀態|1＞中。量子位元的這一特性來自量子力學的狀態疊加原理，即如果狀態|0＞和|1＞是兩個互相獨立的量子態，它們的任意線性疊加 |ψ>=α|0＞+β|1＞也是某一時刻的一個量子態，而係數α和β的絕對值的平方則描述系統分別處在|0＞和|1＞的機率。這使得每個量子位元的組態比古典位元多得多，量子位元能利用不同的量子疊加態記錄不同的資訊，在同一位置上可擁有不同的資訊。因此，同樣由二個狀態組成的物理裝置，量子位元元的功能比古典位元強得多。然而量子態是非常不穩定的，並且根據量子力學的測量理論，任何觀測都會立刻改變系統的狀態，因此量子資訊的實際可行性一直受到懷疑。但令人驚訝的是，這正是保證量子資訊的絕對安全性，因為任何竊聽（測量）者都會被發現。

利用量子位元的特性，就開發出了具有平行運算功能的量子運算，一般電腦若要模擬量子系統，所需的時間會隨系統大小成指數增長。然而量子電腦模擬所需的時間只與系統大小成正比。一個 40 位元的量子電腦在百步之內所能模擬的量子系統，一般電腦要可能需要 1012 位元花上數年的時間。

量子電腦怎能做到這麼快呢？原來它的每一個位元都是同時有「零」，同時也有「壹」存在而疊加在一起的。因此，從起始值開始，它就是同時代表了所有可能的的狀態。所有可能的情況都一次算掉了，這就是Deutsch 所稱的量子平行處理 (quantum parallelism)。

量子平行處理聽起來很奇怪嗎？想一想，聲波的例子：如果「零」與「壹」各代表某個頻率的聲波。那麼，一個同調態就是一個和聲了。正如和聲，聽起來和各別的單音不同，這種組成之量子態亦然。但是，無論是和聲或同調態，兩個波都會互相干涉。量子電腦就好像交響樂演奏一樣，您聽到的是和聲，而不是單獨的樂器。 Shor 就是利用這種「和聲」的特性來做因數分解。他告訴我們，因數分解的結果會，像交響樂團的各個樂器，各有自己的音域而分出來。目前，無論是電腦中、銀行中或者軍事上，傳遞訊息所用的密碼，都是利用到傳統電腦無法在有限的時間內找出一個做為「鑰匙」的大質數。有了量子電腦後，這一切就要改觀了。量子電腦可以在短時間內找到這個「鑰匙」。

量子電腦的運用:

量子電腦的一個重要用途是模擬量子系統。雖然現在的電腦已被廣泛用來解各種複雜的量子力學問題，利用量子電腦的平行運算功能，可以用來模擬複雜的量子系統。費曼早已注意到：一般電腦若要模擬量子系統，所需的時間會隨系統大小成指數增長。然而量子電腦模擬所需的時間只與系統大小成正比。費因曼告訴我們：用量子電腦來即時 (real time) 模擬量子系統，在理論上，是可能的；只要設計個能平行處理的量子電腦就可以了。但是，若想用古典電腦來即時模擬量子系統，卻是理論上也行不通的！ 另一方面，傳統電腦中的隨機變數都是虛假的，而量子態是一種真正的隨機分佈在「自然」狀態下去讀取一個量子電腦的狀態，有一半的機率可以讀到「零」，一半的機率可以讀到「壹」。這可是最好的隨機變數！量子電腦內的運算過程本身就是量子態的一個變換過程，因此只有量子電腦能瞬間模擬量子系統的演化。

量子運算完全摒棄傳統運演算法則，其大量瞬間計算的能力是傳統電腦望塵莫及的。一台三十二個量子位元的電腦，其能力相當於四十億部傳統電腦作平行運算。如用量子電腦做因數分解，以目前最快速的電腦而言，大概要花上數十億年的時間，才能求出一個四百位的數字的所有質因數，而量子電腦可能只需要一小時甚至幾分鐘的時間。此外，現今網路上廣泛使用的RSA加密法，則是利用一個約一千個位元的大數，作為公開金鑰(Public key)，而其質因數作為私人金鑰(Private key) ；另一方面，若能快速分解質因數，則RSA加密法即可破解。一九九四年，P. Shor提出的演算法顯示，利用量子傅立葉轉換，可大幅加速質因數分解的運算速度。若以現今的超級電腦，將一個數百位元的大數做質因數分解，需要數億年的時間；若能利用量子電腦從事運算，則將僅需數秒鐘的時間。故利用量子計算現今最廣泛使用的加密法，可被輕易的破解。

除了P. Shor所提出分解質因數的演算法，一九九六年，Grover提出資料庫搜尋的量子演算法：設若一非排序的資料庫含有N筆資料利用量子原理，利用量子原理，可在N1/2的時間內搜尋到所需資料。在傳統的演算法中，則需要N的時間。所以利用量子電腦，可大幅減少搜尋時間。實驗也確認這兩個演算法的可行性。這兩個量子演算法的成功，也顯示了量子計算確實可加速傳統計算的速度，讓人必須重新思考計算的複雜性。

未來的挑戰

量子通訊、資訊與量子計算，真正發展到現在，約有二十年的光景，雖已有許多突破性的進展，而目前仍有太多實驗上以及理論上的問題，等待克服。以下僅簡述目前所面臨的一些重大考驗。

1. 糾纏態的準備。在量子通訊、資訊與量子計算中，糾纏態的重要性，不言可喻。然而要將量子通訊資訊廣泛使用，或在實驗上能夠有重大的進展，就必須能大量而有效率製造最大測度的糾纏態。目前，仍沒有一個有效的方法，能夠達成這個目標。

2. 量子尺度下的精確測量與操控。在一般傳統的實驗上，並不要求在量子尺度的精確度。而在量子資訊或是量子計算的領域中，必須直接對單一量子系統的量子態，而不是傳統的物理量，加以量測。從了解量子物理，到真正能操控量子系統。更進一步而言，要企圖去操空兩個量子位元之間的交互作用，像是C-NOT或是SWAP邏輯閘。這對現今奈米科技中，乃是一個嚴峻的挑戰；也是下一代的製程，所必須完成的任務。

3. 新的量子演算法。人們目前仍試著去深刻理解計算理論與量子物理之間的關係。由於量子計算牽涉到，有限個量子系統之間的干涉，人們對此仍不夠熟悉。如果能對量子原理與計算理論之間，有更多的體會，人們該能理解BQP問題與古典計算中P的問題之間的關聯。更進一步能指引出新的量子演算法，以便加速目前的運算。

4.量子位元的測量:

量子電腦運算中的狀態你不可以去偷看它；也就是「讀」或者「測量」它。你一看它，它就變成 | 0 > 或者 | 1 >而不再是一個混合的狀態了。因此量子電腦在運算完成前，你一看就全錯了！這可是量子力學最奧妙的地方了。 所謂的薛丁格之貓說的就是這件事：

話說 1935 年哥本哈根學派的成員之一的薛丁格發表了一篇文章，舉了這麼個例子：如果一個密閉的盒子裡關了一隻貓、一點放射性元素還有一個收到輻射後能放出毒藥殺死這隻貓的設備。就這麼簡單。放射性元素的狀態是由「衰變」與「不衰變」兩個狀態疊加在一起。貓的狀態，如果依照（歌本哈根學派的）量子力學描述，是由「死」與「活」兩個狀態疊加起來的態所描述。但是當你打開箱子去「看」貓時；你做了一種「測量」，一切都變成事實，貓不是「死」就是「活」；不可能「不死不活」。但是你還沒看他時他卻可能「不死不活」呢！因此當你去看的那一瞬間系統的狀態，突然有了改變；不再是個連續變化。但是波爾卻會說：貓是個「古典」的物體，你不應用量子力學去描述他。因此即使你不看他，他也是不是「死」就是「活」。或者說貓是一個宏觀的物體，放射性元素卻是個微觀的物體。宏觀的物體「應該」是依照古典力學做既定的運動。觀測時這兩個狀態不可能同時存在，波爾稱之為互補性 (complementarity)。可是什麼東西算是「古典」的什麼東西才算是「量子」的呢？這就是問題所在。最近我們已經有相當不錯的解釋了。這就是「一致歷史詮釋」（consistent history interpretation）。當然我們也已經知道這種劃分「古典」與「量子」、「宏觀」與「微觀」、「系統」與「儀器」的觀念是錯的。二分法的方法在任何領域中對的機會本來就太少了。

不管是量子平行計算還是量子模擬計算，本質上都是利用量子糾纏態特有的相干性，但在實際系統中，量子糾纏態很難維持。在量子電腦中，由於量子位元是由原子或其他微粒子系統所構成，很容易受外部環境雜訊影響，導致量子相干性的消失，稱為消相干，從而使運算容易產生錯誤結果。
要使量子計算成為現實，最重要的問題就是克服這種消相干。其最有效的方法是在發生消相干前完成運算，或用誤差修正的方法消去因消相干引起的錯誤。前者依賴糾纏態的壽命，一般說來，一個量子資訊由產生到消失的時間只有十億分之一秒。而後者是同時做幾種相同的運算，並不斷對相應狀態做比較，發生偏差時及時修正，但這樣的方法會降低運算效率。如何保持糾纏態不衰減，或當糾纏態發生偏差時及時修正，是目前量子資訊研究中最基本且亟待解決的問題。

5. 錯誤更正碼(Error correction code) 與容錯(Fault-tolerance)理論。量子通訊、資訊與量子計算要能實際可行，一方面比須讓邏輯位元能有改錯的能力；另一方面，在設計量子電路時，就必須讓此電路可容忍一定程度的缺陷。量子電腦無論是對系統的時間、振幅、相位的要求均很嚴格。當一個系統的狀態與它的環境狀態纏結在一起時，錯誤就會發生了。量子電腦，必需「和聲」不受外界的幹擾而「走音」 (decoherence) 。我們必須在「走音」之前完成計算。這也是與古典電腦不同的地方：以前，一個計算能否完成，全視使用者所擁有的電腦記憶體及電腦時間而定。現在，則是要看這個同調態的壽命了。如何能夠降低一個邏輯位元所需的量子位元，而仍有足夠的改錯能力；以及如何設計可容錯的量子電路，仍僅在起步的階段。

6. 對量子物理更深刻的理解。首先是對量子系統的模擬。當初設計量子電腦，其中之一的目的，是利用量子電腦強大的威力，能更真實的模擬量子系統，如易辛模型(Ising Model)、量子色動力學(Quantum chromodynamics)等等。人們期待量子電腦的誕生，能真正做到模擬量子系統，以幫助人們更廣泛也更深刻的理解量子物理，甚而發現新的物理。其次是透過對於糾纏─量子與古典物理之間最大的差異─的理解，幫助人們重新認識量子物理與古典物理之間模糊的界線。

7.電腦中，邏輯運算是由 AND、OR、XOR、NOT 及COPY 幾個基本動作所組成。除後二者為線性元件外，均為非線性元件。A.Ekert，D. Deutsch 及 E. Barenco 與 S. Lloyd 分別告訴我們：一個量子電腦，只要能做 NOT 及任和其他一種非線性運算，就可以達成全部的運算功能了。[3] 因此，要找到可以製作量子電腦的物理現象並不難。而且，C. H. Bennett 告訴我們，如果量子電腦是以「可逆邏輯元件」組成的話，那麼計算所需之最小能量，將與計算之複雜度無關。

這些邏輯元件只要連起來就可做成量子電腦了！但是怎麼連呢？在傳統電腦裡是用金屬線。它傳遞的其實是電壓訊號。但是要連接這些量子電腦的雙共振閘可就難了；總不能把原子拆開來，取出自旋，再原封不動的裝回去吧？不過，研究人員也已經想出好方法了：例如，光纖或空氣中的光子，都可以作為傳遞自旋資訊的媒介。加州理工學院的 H.Kimble 則設法運用共振腔增強光子與空腔間之交互作用，使得輸入輸出管道間的傳輸更有效。這樣做成的電腦不但快，而且不容易受外界的幹擾而出錯。不過，它還是有一些 Landauer 早就預見的問題：尤其是，所有元件間的光程，必須精確到幾分之一個所使用的光波波長。

各國研究：

在各國都有很多關於量子電腦的研究。在美國有一堆大學和公司都有投入大量資金和心力去做相關方面的研究。其中Stanford-Berkeley-MIT-IBM 主要是在研究一種NMR Quantum Computation 的技術。

在英國則有牛津和劍橋大學合作的CQC( Centre for Quantum Computation) 機構，主要分有理論和實驗的兩大部分研究。在實驗方面他們主要是用一種 Ion Trap Quantum Information Processing 主要得要的研究在於錯誤容忍及錯誤更正兩方面有具體發現。

其他在澳洲，有十幾所澳洲大學聯合的Centre for Quantum Computer Technology 。這個機構在元件、測量、理論上也有卓越的研究，主要在Kane quantum computer architecture 上有成就。