1樓：南瓜星人
說一下我的見解，我認為就算量子計算機成功在多項式時間解決了某個NP完全問題那也不能說P=NP。
一切從定義出發，P表示確定性圖靈機多項式可解問題集合，NP表示非確定性圖靈機多項式可解問題集合。
P=?NP是問：在非確定性圖靈機上多項式可解的問題是不是在確定性圖靈機上也多項式可解？
你現在直接造了乙個非確定性圖靈機（量子計算機）多項式時間解決為NPC問題。但是這和我們要證明的P=?NP沒有關係啊。
2樓：
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問題上，大家看看可能有所啟發。
以上是我的一點拙見。
3樓：Fang
匿名回答基本都講到了。以目前有的結果來看，NP 和 BQP 似乎更像是互不包含。Scott Aaronson 有一篇survey（有點老）可以讀一讀 [quant-ph/0502072] NP-complete Problems and Physical Reality
量子計算機屬於幾進製？
苦逼青年DB 量子有多種自旋態，可以表示多進製位，然後就可以做成多進製計算機，二進位制也屬於多進製中 具體採用幾進製還沒有定則，要看目前各個專案的具體設計 sari 不能用進製衡量，是一種狀態疊加，倒不是0或1的疊加，而是介於0和1的無數種可能性，量子科學不是具象科學，不能確定狀態。至少對於觀測者而...
量子計算機會取代人們家中的普通計算機還要經過多少年？
本源量子 量子計算機不會取代經典計算機，而是與經典計算機融合發展，解決目前無法完成的超大規模資料的處理。從目前的技術路徑來看，量子計算機需要足夠穩定的執行環境才能避免外界雜訊干擾，這意味著量子計算機需要製冷裝置，需要大量的能源消耗。從這一點來看，量子計算機不太可能像家用計算機一樣。當然，我們可以通過...
量子計算機什麼時候民用
你在該有多好 量子計算機現在已經誕生，不過，這只能算是雛形，而非真正意義上的量子計算機。在較長一段時間內 估計20 30年吧 理想而且通用的量子計算機都不會面世，頂多只是運算能力提公升N多倍而已，只能作特定運算而非通用。真正意義的通用量子計算機，估計最少也得40 50年以後才能上市，我們拭目以待吧，...