量子計算機出現後會不會重新定義時間複雜度和空間複雜度？

01-05

或者不在需要考慮時間和空間複雜度了。
我對量子計算機的理解是：
一個128位的存儲器可以存儲世界上地球上所有數據

並且對這些數據求和只要做一次加運算

量子計算並不是簡單通過對所有可能性同時進行疊加計算而一步得到答案：為了得到答案需要進行測量，而普通情形下測量得到的一般是垃圾。有speedup的情形的核心在於問題本身有合適的結構使得encode了有用信息的computational paths發生amplitude的相干疊加，而其他paths相互抵消。例如Q Fourier Transform利用周期性。（另一個很有意思的情形是welded tree的quantum walk [arXiv:quant-ph/0209131]，我個人非常喜歡這篇文章，這個也正好是我qualification口試的第一個題目。）我所了解的有指數speedup的情形基本都是基於這個subroutine。多推幾個經典的例子ie Grover, phase estimation很容易可以明白。

關於時間和空間複雜度，量子的generalization（eg polynomial: BQP/BQPSPACE：由於測量本身的probabilistic特性一般考慮bounded-error情形）定義都是很明確的。其中易證空間的BQPSPACE=PSPACE，也就是多項式空間的量子計算和經典計算是一樣的power。時間方面BQP和諸多類的關係和P vs NP一樣，沒有嚴格結論，但一般認為BQP嚴格包含P以至於BPP（eg Shor），但BQP不含NP-complete問題（雖然依賴於P != NP）。

會拓展吧，會顛覆的並不是很多。大數分解會降成多項式級別的，加密系統需要重做，目前還沒看到P=NP的跡象。做理論的已經研究有一陣子了。

量子計算機是用糾纏的128位可以表示一個「薛定諤的」地球上的所有數據。你可以對它進行觀測，然後每次以一定概率看到地球上的一個數據，並且觀測完了他就坍縮成經典的了。和經典數據的存儲和計算模型很不一樣的。

以前我還真沒有想過這個問題。。。

不過時間複雜度和空間複雜度一般都是對於輸入數據 n 說的

所以我覺得該考慮還是要考慮的

只不過如果可以用量子演算法的話

我們期望時間和空間複雜度會降低

運算和存儲還有輸出這些我還不是太明白。。