No programming theorem?

12-31

在讀一本科普讀物的時候看到No programming theorem，書中只是簡單的說量子計算機架構不是馮諾依曼結構。我的理解是馮諾依曼結構的最大特點就是可以把程序存到內存里，運行的時候可以讀取出來，是不是這就意味著量子計算機沒法編程？

謝邀. 這裡的 No-programming theorem 看起來 Michael Nielsen 很喜歡這麼叫[1], 我甚至找到了他做的某個 Slides[2] 上的說明:

(吐槽: 把 Bill Gates 這麼支持 Quantum Computing 的人叉掉真的好么......)

看了看定義, 說的類似 No-cloning theorem. 簡單的說, 就是任意的量子態不可能精確的複製, 除了系統的本徵態. 不太嚴格的說, 考慮一個 CNOT 門和下面的初態(輸入):

我們想在第二個 Qubit 上複製它, 那麼需要得到:

即上式滿足 $alphaeta = 0$ , 但是用 CNOT 作用輸入可以得到

$CNOT|psi angle|0 angle = alpha|00 angle + eta|11 angle$

也就是說, 能複製的只有 $|0 angle$ 和 $|1 angle$ 而已.

回到 No-programming theorem, $U$ 的輸入形式看起來非常像通用 Turing 機(Universal Turing Machine)的處理手法. 我們考慮比較簡單的情況: $|psi angle$ 只有一個 Qubit, 而 $U$ 是單比特量子門.

由於單比特量子門對應 Bloch Sphere 上的一個三維旋轉[3], 所以對其進行 Euler 角分解, 考慮 Euler 角的而二進位形式. 那麼, 我們可以把 $U$ 編碼成一系列類似 $R_z(frac{2 pi}{2^k})$ 的旋轉, 這裡的 $k$ 表示編碼中第 $k$ 位. 如果我們的程序是互相正交的, 也就是說由三個確定的旋轉(z 軸, y 軸, z 軸)決定, 那麼當然可以執行. 但是, 如果編碼中允許疊加態, 也就是說這裡的程序 $U$ 是多個單比特量子門的疊加的話.

考慮類似 CNOT 的實現, 不過這裡的 target Qubit 對應的不是 Pauli X 門, 而是一個旋轉. 相當於第一個 Qubit 之前是 $|0 angle$ , 我們需要把第二個 Qubit 的東西拷貝上去, 那麼套用上一段的結果即得.

當然, 對於 Fixed Array 覆蓋所有單比特量子門已經不太現實了...不管你怎麼編碼, 我總是能讓長度變得無窮大. 但即使是精度有限的情形, 這樣的編碼也不能把允許疊加的 $U$ 作用到第一個 Qubit 上.

於是簡單的複製是不可能了, 但是 Programming 也不一定要能複製嘛?... Functional Programming 裡面不是也不允許複製么, 大家的 Haskell 還不是寫的好好的.

關於量子程序語言, 現在絕大多數成型的理論或者系統都是基於經典控制流的. 我曾經介紹過應明生老師在 CCCF 上寫的一篇綜述, 量子軟體是否有位數之說？ - Climber.pi 的回答. 簡單的說, 可以類比成 FPGA 對應的硬體設計語言, 不同的是這裡處理的是量子門(酉矩陣)的線路綜合. 這種東西足夠我們來實現量子演算法了, 雖然就像是沒有通用 Turing 機只有 Turing 機233. 但是基於量子控制流的那些就複雜得多(看看這裡的 No-cloning theorem), 甚至有人為此引入了 Categorical Quantum Mechanics 之類的東西...

有興趣的話, 可以看看 Quipper 或者 ScaffCC, 前者是基於 Haskell 的, 後者是比較正常的 Imperative Programming. 關於前者還有篇科普[4], 裡面對這種"Quantum data, classical control"的方式有很清楚的說明, 還給出了他們實現的幾個 non-trivial 的量子演算法:

Reference

[1] Nielsen M A, Chuang I L. Programmable quantum gate arrays[J]. Physical Review Letters, 1997, 79(2): 321.

[2] http://michaelnielsen.org/blog/qicss/q-comp.ppt

[3] 事實上多個 Qubit 的量子態也有類似的 Bloch Sphere, 不過對應的李代數生成元有關. 雖然相對複雜, 但是也能拆解成類似的形式. 具體見 Kimura G. The Bloch vector for N-level systems[J]. Physics Letters A, 2003, 314(5): 339-349.

[4] Valiron B, Ross N J, Selinger P, et al. Programming the quantum future[J]. Communications of the ACM, 2015, 58(8): 52-61.