量子計算機到底是啥？

• 1 量子計算機是誰想起來的？
• • 1.1 Nature isn't classical, dammit (Feynman 1981)
  • 1.2 Many worlds interpretation (David Deutsch)
• 2 量子計算機到底能干什么？
• • 2.1 能不能算停機問題？
  • 2.2 能不能實現(xiàn)指數(shù)加速？
• 3 量子計算機咋實現(xiàn)的？
• • 3.1 量子圖靈機 Quantum Turing machines
  • 3.2 量子電路 Quantum circuits
  • 3.3 Universal gates (to be continued)
• 附錄：概念回顧

• 量子計算機是誰想起來的？
• 量子計算機到底能干什么？
• 量子計算機咋實現(xiàn)的？

激動人心的量子計算環(huán)節(jié)終于來了，其實我們在前11回書中已經(jīng)完整的介紹了量子計算里面的基本概念，今天在介紹量子計算機的時候會回顧到不少；今天你會發(fā)現(xiàn)不知不覺你已經(jīng)掌握了降龍十八掌前十七招，把這些招數(shù)都連起來你就發(fā)現(xiàn)，自己已經(jīng)學會了量子計算機的基本原理，讓我們一起走進量子計算機的大門！

1 量子計算機是誰想起來的？

學到現(xiàn)在我們會發(fā)現(xiàn)，量子比特的表達和操作其實我們都能用矩陣來表達，其實我們就可以用經(jīng)典計算機來模擬量子計算，不過，量子比特是處于疊加態(tài)的，一個量子比特$|\psi ?=\alpha |0?+\beta |1?$的狀態(tài)要用兩個量子幅(Amplitude)來表達，對于$n$個量子比特的狀態(tài)$|\psi ?={\sum }_{x\in \{0,1{\}}^n}{\alpha }_x|x?$，由于量子糾纏(Entanglement)的存在，需要用$O(2^n)$個量子幅來表達，如果沒有糾纏，$n$個量子比特的狀態(tài)可以由這$n$個量子比特用張量積乘起來$|\psi ?={\sum }_{x\in \{0,1{\}}^n}{\alpha }_x|x?=({\alpha }_0|0?+{\beta }_0|1?)?({\alpha }_1|0?+{\beta }_1|1?)\dots ({\alpha }_{n?1}|0?+{\beta }_{n?1}|1?)$，這個時候用$O(n)$個量子幅就可以表達了，那這個時候量子計算機說實話和經(jīng)典計算機可以說區(qū)別不大了，因此在量子計算中幾乎都要考慮量子糾纏。

順便再提一句，指數(shù)復雜度是很可怕的，如果你有300個糾纏的量子比特，表達他們所需要的量子幅的個數(shù)已經(jīng)比我們能觀察到的宇宙中的原子數(shù)量還要多了。

1.1 Nature isn’t classical, dammit (Feynman 1981)

費曼在1981年關于如何模擬量子力學的演講中說過這么一句名言：

Nature isn’t classical, dammit, and if you want to make a simulation of nature, you’d better make it quantum mechanical, and by golly it’s a wonderful problem, because it doesn’t look so easy

反正意思就是，TMD，世界是量子的，如果你想用經(jīng)典計算機模擬量子力學甚至量子化學量子生物的應用，不可避免的會遇到指數(shù)復雜度的問題，當然你可以想一些方法來hack，還有人因為hack的比較好拿到了諾貝爾獎，但是更自然的做法是應該能用量子計算機去模擬量子力學，那還是相當牛x的研究課題，因為這并沒有那么簡單。

而且后來人們還發(fā)現(xiàn)量子計算機還可以用來解決其它領域的問題，比如密碼學，后面我們會學到，這就令人非常激動了！

1.2 Many worlds interpretation (David Deutsch)

David Deutsch認為多世界詮釋是對的，即觀察者也可以處于量子疊加態(tài)，雖然這與哥本哈根學派的觀點不通，因為這樣經(jīng)典世界和量子世界就混到一起了；他想的是建造個具有意識的計算機，然后讓它既考慮一個問題，又考慮另一個問題，即處于兩種狀態(tài)的疊加，比如：
$$\frac{|M_0?+|M_1?}{\sqrt{2}}$$然后通過在基$\{|M_0?+?|M_1?\}$的測量確保其處于疊加態(tài)，所以還是得建造量子計算機。

David Deutsch也有比Feynman厲害的時候，比如在復仇者聯(lián)盟里面，不然就沒法兩次打敗滅霸救活一半的宇宙生命惹~~~

當然量子計算機的想法肯定有很多人都構(gòu)思過，這里只是挑倆影響力最大的來介紹一下。

2 量子計算機到底能干什么？

量子計算機好像很牛x，那么我們到底能用量子計算機干啥呢？

2.1 能不能算停機問題？

很遺憾，答案是，不能；我們要牢記前面1.1里面的一句話，量子計算機能算的，經(jīng)典計算機都能算，只不過要付出指數(shù)復雜度的代價，所以經(jīng)典計算機里面討論的不可計算問題，用量子計算機也無能為力，所以量子計算機符合 命題三(邱奇圖靈命題)

2.2 能不能實現(xiàn)指數(shù)加速？

目前，很少有問題可以用量子計算機進行指數(shù)加速；且當前的一種理解是指數(shù)加速是指數(shù)并行，比如疊加態(tài)同時計算倆結(jié)果，然后能同時計算指數(shù)個結(jié)果，這種思路雖然容易理解，但是并不是量子計算機的工作方式！很簡單的理解，如果我們把若干量子比特分配一樣的amplitude，最后不管疊加什么的，只能得到指數(shù)個均勻分布的測量結(jié)果，這并沒有什么卵用；
其真正的工作方式是，通過量子幅值與經(jīng)典概率的最大不同，即其是復數(shù)而不是非負實數(shù)，通過算法實現(xiàn)一定的干涉模式，使得壞的結(jié)果，他們的量子幅相加為零，而好的結(jié)果量子幅越加越大，由此盡可能大概率的得到我們想要的測量結(jié)果。

這些過程需要在不事先知道結(jié)果的情況下快速完成，這是大自然賦予我們的一個奇怪的工具，需要不斷探索其到底能干啥。

在這里有三個概念：(1) 干涉 (Interference)；(2) 指數(shù)級別的量子幅；(3) 糾纏 (Entanglement)；

干涉是量子幅不同經(jīng)典概率之處，量子幅的指數(shù)特點就不用說了，而糾纏是指數(shù)量子幅的原因，也是我們能利用的一個重點特點，這三個特點都會在量子計算中用到，算是理解量子計算的不同角度了。

3 量子計算機咋實現(xiàn)的？

3.1 量子圖靈機 Quantum Turing machines

經(jīng)典計算機中，我們通常將其抽象為圖靈機，其實就是無限長的紙帶，然后通過讀寫頭執(zhí)行指令，來讀取、改變紙帶上的狀態(tài)。那量子圖靈機就把這些東西變成量子的，紙帶寫的是量子比特，讀寫頭也是量子的。

3.2 量子電路 Quantum circuits

一個比較modern的看法就是，量子計算機就是處理多個比特的量子電路，如圖所示；

每個門電路都應該只作用在2、3個量子比特，因為：(1) 物理就是局部的; (2) 大的門可以由小的門組成；(3) 經(jīng)典計算機電路也是一樣的，只是由與(AND)或(OR)非(NOT)異或(XOR)這些小的邏輯電路組成；

在這里時間復雜度就是門的數(shù)量，如果考慮并行就是門的深度或者層數(shù)；空間復雜度就是量子比特的數(shù)量；

不過怎么確定哪些門作用在哪些量子比特上呢？當然是用經(jīng)典計算機來算咯，經(jīng)典計算機會把門序列發(fā)送到量子計算設備上，里面可能有激光啊光子啊啥的，讓后返回一系列測量結(jié)果給經(jīng)典計算機，由經(jīng)典計算機來確定control flow，loops，memory allocation，when to halt。當然也可以嘗試把這些工作也用量子計算機做，但是呢，Yao (1993)搞了個定理，證明這種經(jīng)典+量子的計算模式，是和量子圖靈機等價的。

3.3 Universal gates (to be continued)

那我們設計這些門電路時，到底該用哪些門備選呢？哪些門能實現(xiàn)所有的運算呢？這就涉及到通用門 Universal gate的概念啦，這個我們下次再說！

附錄：概念回顧

命題三(邱奇圖靈命題)，量子計算 1
量子幅(Amplitude)，干涉(Interference)，量子計算 2
量子糾纏(Entanglement)，量子電路(Quantum circuits) 量子計算 3
多世界詮釋(Many worlds interpretation)，哥本哈根詮釋(Copenhagen Interpretation)，量子計算9

總結(jié)

以上是生活随笔為你收集整理的量子计算 12 量子计算机到底是啥？的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。