1樓：SIY.Z
(隱隱的感到，量子計算已經成為知乎上誤解最多的領域之一了)
要看有沒有能力完成計算，需要參考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，離散對數，橢圓曲線，和專門對付量子計算機的格密碼和一系列變種)，所以被當今公鑰密碼學廣泛使用。
2樓：
但是換乙個角度來思考。窮盡圍棋狀態並不是沒有可能。圍棋一共才361個位子，那麼乙個位子的狀態只可能有 （|白子》+|黑子》）（沒有落子的狀態最終也可能用黑子或者白子填滿）。
也就是說如果不考慮qubit correlation的話，那麼361個qubit的量子計算機絕對可以窮盡。只不過是不是有效的，那就得看post-BQP有多大了。
3樓：Climber.pI
更正一下樓上那位的答案。
而且不考慮有效（efficiently）的話這答案是 trivial 的，但凡可計算的你都可以說是能窮盡。
（基本）沒有。圍棋（Go）是 PSPACE-hard 的[1]，不光不在 PSPACE 裡，事實上還是 EXP-complete 的[2]。下面的efficient time的 post-selection [3] 也是假想操作（即量子力學允許線所有線性算符作為可觀測量），有一系列 bound：
[4,5,6]：
[3]:
由定義匯出:
由可推出:
由定義匯出:
[JJUW'09]
假定存在某種規則使得圍棋是 PSPACE-complete 的，並且非要讓上面的東西 collapse 掉的話（即 ），那就有
直接後果包括但不限於：
量子計算機能夠有效地求解所有 NP-complete 問題，直接後果之一就是宣判 lattice-based cryptography 的死刑；
量子計算機能夠有效地求解所有 QMA-complete 問題，包括所有的 k-local Hamiltonian problem，那麼 Hamiltonian complexity theory 也（幾乎）沒有存在價值；
量子計算機能夠有效地求解所有 #P-complete 問題（如 Permanent，而不是和 Boson sampling 一樣給個近似）；
量子計算機能夠有效地求解所有 PSPACE-complete 問題（如 TQBF，自然也包括整個polynomial hierarchy）；
量子（經典）互動式證明系統和量子計算機直接求解相比沒有任何優越性，打個比方的話，就是你自學的理解能力和有靠譜導師指導的理解能力是一樣的。
除了第一條（樂觀地）看起來像小概率事件，其他的基本上是不可能事件了。
加密演算法中有沒有量子計算機也無法破解的？
暴風雪 目前量子演算法對於基於大整數分解和離散對數問題 迴圈群隱藏子群問題 的公鑰演算法可以達到指數級的加速，其他密碼體制暫時安全，但是這只是對於密碼演算法本身而言，安全是乙個系統問題，看的是最短的那塊板，現在絕大多數安全協議或系統，都是使用了各種密碼演算法或協議，離不開公鑰演算法，所以即使其他演算...
有沒有與計算機無關的理科專業？
小王同學 大學裡大部分的理科專業在大一都會學最基礎的計算機知識，大學生計算機基礎 和 c語言程式設計 後面基本上不是專門的計算機專業就不會接觸計算機的相關知識了。 RicardoK.Ls 計算機在現代非常普及 通常人人都會基礎的使用 所以想要避免計算機課是不可能的 不過如果只想上初級還是可以達成的，...
想選計算機方面專業，有沒有建議
飄飄計算機二級 選擇乙個好學校比專業更重要 張大博 正視差距，奮起直追 極少數有程式設計基礎的，大學沒有荒廢的話，畢業會收割大量offer北上廣深城市的學生更容易得到實習機會，工作了的學長會在學校bbs招收簡歷內推實習，畢業招聘開始之前實習過的學生很多已經拿到了轉正offer，推薦北上廣深計算機專業...