BQP（量子複雜度，bounded-error quantum polynomial time）
/ B-Q-P /
量子電腦不只是更快的普通電腦；它以一種真正不同的物理來計算，操弄能處於疊加態、並能像波一樣彼此干涉的量子位元（qubit）。BQP 是量子電腦能高效求解的決定問題之類別：在多項式時間內、帶有界錯誤（以高機率正確，像 BPP 但屬量子）。這是「量子電腦擅長做什麼」的誠實定義。
它如何運作？任何加速的真正來源又是什麼？量子演算法把一個計算同時鋪展到許多可能性的疊加上，再利用干涉讓錯誤答案相消、正確答案相長，使最後的測量很可能讀出有用的東西。著名的成功是特定的：Shor 演算法在多項式時間內分解整數並計算離散對數（被相信在古典上很難的問題，這正是它威脅 RSA 式密碼學的原因），而 Grover 演算法在約 N 的平方根步內搜尋一個 N 個項目的無結構空間——一個真實但僅為二次的加速，並非指數。其力量來自利用隱藏的數學結構（如分解中的週期性），而非盲目地試遍一切。
現在是關鍵的誠實，因為這是本學科被過度炒作得最厲害的主題。量子電腦並不是一台靠「平行試遍每個答案」就能瞬間解開所有 NP 問題的魔法裝置。疊加確實探索了許多分支，但測量會把它塌縮成單一結果，而沒有巧妙的干涉，你讀不出你想要的那一個。一般相信 BQP 並不包含整個 NP——量子電腦並不被認為能高效解開像 SAT 或 TSP 這樣的 NP 完全問題。我們知道 P 落在 BQP 之內，BQP 落在 PSPACE 之內，但 BQP 與古典類別之間的確切關係（甚至 BQP 是否異於 P）仍未解。量子計算是一個真實而重要的前沿，而非一條萬用捷徑。
Shor 演算法同時展現了力量與極限。它在量子電腦上以多項式時間分解一個大數 n，靠的是用量子傅立葉變換找出一個隱藏的週期——一個被相信在古典上呈指數困難的任務。但它之所以可行，正因為分解擁有豐富的數論結構可資利用。對沒有這種結構的一般 NP 完全搜尋，並不存在已知的類似量子訣竅。
量子加速來自利用結構的干涉——而非一次試遍所有答案。
最大的迷思：量子電腦並不能高效解開 NP 完全問題——一般不相信 BQP 包含 NP。疊加探索了許多狀態，但測量只回傳一個，所以「平行試遍每個答案」並非加速的運作方式；加速來自對有結構問題上的干涉。