BQP

양자 컴퓨터가 다항 시간에 2/3 이상의 확률로 옳은 답을 내는 결정 문제의 모임이다. BPP ⊆ BQP ⊆ PSPACE 가 알려져 있다. 인수분해는 쇼어의 알고리즘 덕분에 BQP 에 속한다. 그러나 양자 컴퓨터가 NP-완전 문제를 다항 시간에 푼다고 믿을 근거는 없다. 구조를 쓰지 않는 탐색에서는 양자 컴퓨터도 경우의 수의 제곱근만큼은 물어봐야 한다는 한계가 증명되어 있다. 「양자 컴퓨터는 모든 답을 동시에 시도하므로 NP 문제를 곧바로 푼다」는 말은 틀린 설명이다. BQP 와 NP 는 어느 쪽도 다른 쪽을 포함한다고 알려져 있지 않다.