量子计算复杂性的介绍

一个问题的量子计算复杂性由求解这个问题的量子算法的计算复杂性所决定。量子计算复杂性指在量子环境下对于某个问题求解的困难程度，包含问题复杂性、算法复杂性等。由于求解一个问题的量子算法可能有多个，它们的量子计算复杂性也各不相同，因此在理论上将求解该问题的最有效量子算法的计算复杂性定义为一个问题的量子计算复杂性。目前，针对该领域的研究主要集中在两个方面：一是可行性检验问题，二是判定问题【62】。

在经典的计算复杂性理论中，人们已经证明存在多项式时间内可用通用Turing 机求解的可计算问题。类似地，Bernstein 和Vazirani 指出存在多项式时间内可用通用量子Turing 机求解的可计算问题。同时，他们提出了量子计算复杂性理论。随后，许多学者提出了各种量子算法和量子复杂性证明作为量子计算复杂性的进一步解释。譬如，Simon 定理说明量子计算优于经典计算，即存在具有有界错误概率的量子Turing 机求解问题的复杂性低于经典计算的复杂性，Shor 算法和Gover 算法分别验证了Simon 定理的正确性。(www.xing528.com)

但是，对于任意（或趋近）无穷多的输入，量子Turing 机（包含任意的概率Turing 机）以有界错误概率求解问题需要（亚）指数时间复杂度。一方面，量子Turing 机的出现降低了求解问题的计算复杂性；另一方面，不是所有的问题都在BPP 内。