量子計算機可以在理論上解決NPC問題嗎？

12-31

能否為證明出NP=P提供思路或是實驗驗證，或者退一步說，可以解決現有的NP完全問題嗎? 目前看到一些文章認為不能，有些認為能，不太理解，想請知乎相關領域的大神提提看法，謝謝！
https://en.wikipedia.org/wiki/P_versus_NP_problem

Quantum complexity theory
[quant-ph/9801041] Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems

謝邀。

匿名回答基本都講到了。以目前有的結果來看，NP 和 BQP 似乎更像是互不包含。Scott Aaronson 有一篇survey（有點老）可以讀一讀 [quant-ph/0502072] NP-complete Problems and Physical Reality

除了民科文章，怎麼可能會有正經的學術論文認為現在的量子力學體系（五大公設改一改當然不算，比如題主的例子3）下的量子計算機能解決NP-complete問題。。。？

另外，除了一些亂七八糟的科普，我還真沒見過有什麼正經地方寫NPC而不是NP-complete。按著記號是不是還要搞個PSPACEC，#PC，BQPC，QMAC（這是蘋果出的quantum mac嗎。。）。。

題主自己舉的例子里說的都是放棄線性的「量子力學」了。在承認量子力學五大公設的前提下定義的BQP（量子計算機上多項式時間，考慮多項式時間內生成的多項式規模量子線路，算完以後測量一下），如果存在能夠被量子計算機解決的NP-complete問題，那麼NP是BQP的子集。

我們知道P是NP的子集，P是BQP的子集，加上這個假設，那也就P subseteq NP subseteq BQP。就算題主找到了這麼驚世駭俗的構造（做格密碼的諸位恐怕都要因此失業了，題主這工作的影響力將不亞於94年peter shor那篇），證明NP subseteq BQP，對於P-vs-NP仍然沒有直接幫助。獎金的話，拿個牛逼的論文獎還是很有希望的，不過Clay Institute的六位數獎金還是別想了。。。

Peter Shor的量子演算法屬於找周期的，但是諸如3-SAT這個第一個NP-complete問題還有Hamilton迴路這個NP-complete問題而言，他似乎並不存在周期。Grover量子演算法可以將複雜度降至O(N^(1/2))，但是對於一些問題來說，當N是exponential的大的時候，其複雜度還是exponential的大，達不到polynomial級別。即使NP-complete問題被解決了，但是還有很多諸如lattice和LWE這些NP-hard的問題，依然可以抵抗量子計算機的攻擊。

推薦兩篇文章M.Alekhnovich (03FOCS)還有U.Feige (02STOC)，好像是想將LWE問題歸約到3-SAT問題上，大家看看可能有所啟發。

以上是我的一點拙見。

說一下我的見解，我認為就算量子計算機成功在多項式時間解決了某個NP完全問題那也不能說P=NP。

一切從定義出發，P表示確定性圖靈機多項式可解問題集合，NP表示非確定性圖靈機多項式可解問題集合。

P=?NP是問：在非確定性圖靈機上多項式可解的問題是不是在確定性圖靈機上也多項式可解？

你現在直接造了一個非確定性圖靈機（量子計算機）多項式時間解決為NPC問題。但是這和我們要證明的P=?NP沒有關係啊。

要解決NP問題肯定是可以的，NP問題包含於可解問題，只是不一定存在多項式時間內的演算法。