论文标题
BQP不在NP中
BQP is not in NP
论文作者
论文摘要
人们普遍认为，量子计算机比古典计算机具有优势，有些计算机甚至发表了一些经验证据。但是，这些出版物不包含这种优势的严格证明，必须最低限制地表明，量子计算机在多项式时间（多项式时间）中可以决定的问题类别包含不在经典计算机所确定的问题类别中的问题。这证明量子计算能够有效地解决远远超出古典计算机功能的问题。
Quantum computers are widely believed have an advantage over classical computers, and some have even published some empirical evidence that this is the case. However, these publications do not include a rigorous proof of this advantage, which would have to minimally state that the class of problems decidable by a quantum computer in polynomial time, BQP, contains problems that are not in the class of problems decidable by a classical computer with similar time bounds, P. Here, I provide the proof of a stronger result that implies this result: BQP contains problems that lie beyond the much larger classical computing class NP. This proves that quantum computation is able to efficiently solve problems which are far beyond the capabilities of classical computers.
