量子計算機有沒有能力窮盡圍棋狀態搜索？

01-02

圍棋盤上的一個點，只能是黑棋0，白棋1，或者空（同時事0或者1）三種狀態；很像量子比特；假設有一台通用的量子計算機，能不能窮盡圍棋狀態搜索找出最優路徑？

更正一下樓上那位的答案。

而且不考慮有效（efficiently）的話這答案是 trivial 的，但凡可計算的你都可以說是能窮盡。

--------------------------------------------------------------------------------------

（基本）沒有。圍棋（Go）是 PSPACE-hard 的[1]，不光不在 PSPACE 里，事實上還是 EXP-complete 的[2]。下面的 efficient time 的 post-selection [3] 也是假想操作（即量子力學允許線所有線性算符作為可觀測量），有一系列 bound：

[4,5,6]： $mathsf{P} subseteq mathsf{BPP} subseteq mathsf{BQP} subseteq mathsf{QMA} subseteq mathsf{PP} subseteq mathsf{PSPACE}$
[3]: $mathsf{PP} = mathsf{PostBQP}$
由定義導出: $mathsf{NP} subseteq mathsf{PP} subseteq mathsf{#P}$
由 $mathsf{#SAT}$ 可推出: $mathsf{#P} subseteq mathsf{PSPACE}$
由定義導出: $mathsf{PH}subseteq mathsf{PSPACE}$
[JJUW"09] $mathsf{QIP}=mathsf{PSPACE}=mathsf{IP}$

假定存在某種規則使得圍棋是 PSPACE-complete 的，並且非要讓上面的東西 collapse 掉的話（即 $mathsf{BQP}=mathsf{PSPACE}$ ），那就有

$mathsf{NP} subseteq mathsf{PH} subseteq mathsf{BQP}=mathsf{#P}=mathsf{QMA}=mathsf{PostBQP}=mathsf{PSPACE}=mathsf{QIP}$

直接後果包括但不限於：

量子計算機能夠有效地求解所有 NP-complete 問題，直接後果之一就是宣判 lattice-based cryptography 的死刑；
量子計算機能夠有效地求解所有 QMA-complete 問題，包括所有的 k-local Hamiltonian problem，那麼 Hamiltonian complexity theory 也（幾乎）沒有存在價值；
量子計算機能夠有效地求解所有 #P-complete 問題（如 Permanent，而不是和 Boson sampling 一樣給個近似）；
量子計算機能夠有效地求解所有 PSPACE-complete 問題（如 TQBF，自然也包括整個polynomial hierarchy）；
量子（經典）互動式證明系統和量子計算機直接求解相比沒有任何優越性，打個比方的話，就是你自學的理解能力和有靠譜導師指導的理解能力是一樣的。

除了第一條（樂觀地）看起來像小概率事件，其他的基本上是不可能事件了。

Reference

[1] http://www.levreyzin.com/presentations/Go.pdf

[2] J. M. Robson (1983). "The complexity of Go". Information Processing; Proceedings of IFIP Congress. pp. 413–417.

[3] Aaronson, Scott (2005). "Quantum computing, postselection, and probabilistic polynomial-time". Proceedings of the Royal Society A. 461 (2063): 3473–3482. doi:10.1098/rspa.2005.1546.

[4] Bernstein and Vazirani, Quantum complexity theory, SIAM Journal on Computing, 26(5):1411-1473, 1997

[5] L. Adleman, J. DeMarrais, and M.-D. Huang. Quantum computability. SIAM J. Comput., 26(5):1524–1540, 1997.

[6] Watrous, John (2009). "Quantum Computational Complexity". In Meyers, Robert A. Encyclopedia of Complexity and Systems Science. pp. 7174–7201. arXiv:0804.3401 Freely accessible. doi:10.1007/978-0-387-30440-3_428.

(隱隱的感到，量子計算已經成為知乎上誤解最多的領域之一了)

要看有沒有能力完成計算，需要參考3個方向:

1. 問題本身是「可計算的」(這是個嚴格定義的學術名詞)，比如判斷任意一個程序是否能夠有限步終止就是不可計算問題(也就是著名的停機問題)。如果圍棋是不可計算問題，則不可能存在一種演算法或者操作，保證有限步能終止;但是圍棋是有限狀態的，因而必然是可計算的問題。(注: 量子計算機在「可計算」能力上和經典計算機相同)

2. 問題所屬的複雜度域是否足以讓計算機以某種特定的演算法在多項式時間內解決問題。否則隨著規模的擴張(對於圍棋來說是步數)，計算所需的時間會急劇增加到沒有實際意義的數字。經典計算機能夠保證一定在多項式時間內解決的問題的複雜度域為P(或者至多BPP)。而量子計算機為BQP(分解大質因數問題就屬於BQP而不屬於BPP，因此量子計算機可以在相對可以接受的時間內解決這個問題，而經典計算機目前沒有希望)。可惜圍棋問題的複雜度域至少是P-SPACE hard，無論量子還是經典計算機都沒有希望在可以接受的時間內解決這個問題。

3. 複雜度只是個隨著規模增加計算量變化的趨勢。如果說規模本身很小，複雜度是沒有什麼特別意義的，比如說把圍棋盤減小到5*5要求搜索到底，或者19*19的棋盤搜索深度限制為3，這個時候手機都可以較快解決問題。

但是按照題意，應該是要把19*19的棋盤的所有狀態搜索完，按照之前複雜度的結論這(對量子計算機)是不合實際的。

補充兩點:

1. 看到很多人回答有問題。量子計算領域中提的量子並行性和並行計算中的並行性根源上不是一回事。這導致大部分已經成為經典的並行演算法無法在量子計算機上(利用量子並行性來)實現;即使實現，使用的方法也完全不同(比如QFT對於FFT)。但是反過來，任何量子並行性都可以用一個簡單的經典並行演算法來模擬(這個其實暗示了量子計算機計算能力弱於一台可以指數級拓展規模的並行機(當然這種機器現實中也不存在，否則我們也不用量子計算了))。

2. 即使我們不能有效的遍歷所有狀態，也不代表我們不能很好的解決問題。對於一個非常困難的問題，往往只要我們拋棄追求完美和徹底解決，轉而使用一種近似和追求實際可用的態度，問題往往就會迎刃而解。AlphaGo下圍棋就是這樣一種方式，機器學習取得了棋盤估值的良好近似，從而也達到了我們預期的性能，而不用遍歷整個棋盤的狀態，甚至連其百億億億億億億...........億分之一的狀態都沒有遍歷到就做的足夠好了。同樣的，大量的NPC複雜度域的問題是經典和量子計算機都難以有效解決的，但是很多經典的近似或者啟發式演算法可以求得一個相當好的解，以至於當初很多用NPC內問題(比如背包問題，子集和等等)設計的密碼學方案(比如Merkle-Hellman cryptosystem，當然方案本身也存在一些問題而不僅僅是依賴的數學難題的鍋)都被拋棄了。而數論和格問題大多是難以近似的(RSA，離散對數，橢圓曲線，和專門對付量子計算機的格密碼和一系列變種)，所以被當今公鑰密碼學廣泛使用。

窮舉總有盡頭，問題是看你撐不撐得到海枯石爛。

不懂強答……

窮盡搜索不是無敵，那不是痛打阿爾法狗……

別相信那什麼量子計算機如何如何快到無法考量。所謂快，是指天然的大量數據並發計算。然而，裝載有效數據的過程並不天然地並發。建立一個搜索樹，窮盡所有圍棋的狀態，然後遞歸找到最佳落子點，就需要大量地把數據放進內存，再讀取進處理器，這不可能是全並發的。

圍棋不必如例如黑白棋(奧賽羅)那樣窮盡著法，遞歸出最佳落點，這是由於黑白棋盤面小，容易遍歷。圍棋空間過大，不該遍歷，因為過分浪費資源。

作為棋類遊戲，圍棋盤上的每個點，只能是「可佔據」和「不可佔據」兩種狀態。可佔據的一定是空點，不可佔據的則是已經落子的點和禁止落子的空點(劫爭點和無氣空點，所謂眼)。當對弈雙方都同意不再有可增加己方空間的落點(日韓規則，點目)或位於公共空間的所有空白點都被佔領(中國規則，數子)之時，就是終局。

圍棋的死活是以每塊棋子都擁有或必然擁有兩個及更多的眼，為活棋。陷入敵方活棋包圍且不能擁有兩個眼的棋子群(塊)為死棋，在終局時要被清除。特殊情況下，雙方的各自一塊棋在雙方其它活棋的包圍下，共有一個兩目眼或自有一眼，共有一眼，叫做共活，終局都算為活棋。還有多塊共活的情形。活的根本原理就是對方在任何情況下都無法投下一子將本方某塊棋子的所有「氣」全部堵塞。

說這麼多是為了表明所謂遍歷勝負樹，特別是作為並行計算的機器利用運算速度來遍歷勝負樹，全無必要。因為棋盤上的大多數空白點，都不是求生和佔據更多空間的高效率點，遍歷這些點，特別是每走一步之後還要再次判斷局面，以發現新的高效率點(好棋)，仍需要重複這個過程。

遍歷整個勝負樹，等於復現古往今來以至未來所有的圍棋棋局。圍棋的目標是爭勝，是效率之爭，沒必要一直重複那些無盡的壞棋。

記得我最初與人下圍棋，第一盤，就是搭出一個活形後，逐步自己填空，直至剩下兩眼。我的著法直接讓對手傻眼了。遍歷勝負樹，則進一步會有自行填眼將活棋走死的棋出現，那就是完全浪費時間了。

謝邀，答案應該是絕對可以。但是是不是有效的目前我們不知道。雖然圍棋是一個Pspace-hard問題，但是目前為止沒有人知道BQP，甚至更大的post-BQP包不包含整個pspace。目前只有證明post-BQP&>BQP。十分可能BQP&>BPP（目前沒有嚴瑾的數學證明）。

但是換一個角度來思考。窮盡圍棋狀態並不是沒有可能。圍棋一共才361個位子，那麼一個位子的狀態只可能有 $1/ sqrt{2}$ （|白子&>+|黑子&>）（沒有落子的狀態最終也可能用黑子或者白子填滿）。也就是說如果不考慮qubit correlation的話，那麼361個qubit的量子計算機絕對可以窮盡。只不過是不是有效的，那就得看post-BQP有多大了。

個人認為是可以的，但我缺乏對科技以及圍棋的相關知識，所以我算是說了堆屁話。

從一個高中生的眼裡看，是不是只需要把每一次落點的可能性相乘就可以了呢？