BQP (复杂度)
在计算复杂度理论内，有限错误量子多项式时间（英语：bounded error quantum polynomial time，BQP）是一个决定性问题的复杂度类，并且其内的问题可以在多项式时间内以量子电脑解决，错误的几率小于1/3。BQP也可以视为是复杂度类BPP的量子电脑版。
换句话说，对BQP里面的问题，存在一个使用量子电脑的算法（量子算法）花费多项式时间运作，并且有很高的几率回答正确的答案。对任何状况，回答错误答案的几率小于三分之一。
与其他“有限错误”的几率算法相同，这里所提到的1/3是一个比较随意的定义。如果原本算法的错误几率比较大，我们可以运作多次该算法，然后取多数回答正确的答案以取得比较高的准确率。详细的分析显示错误的下限可以高达1/2 − n−c或者低达2−nc，所包含的题目范围均不会有变化。这里c是一个正数的常数，n是输入的长度。
量子计算
[编辑]算法所使用量子位元的数目可以为输入大小的任何多项式。举例来说，因式分解n位元整数的算法使用大约2'n'个量子位元（参考秀尔算法）。
一般状况之下，量子电脑的计算停止于量子测量上面。测量行为会导致量子位元塌缩到其中一个量子态上。我们可以说量子位元在经过运算之后，最终的测量会让他有极高的机会出现正确的答案。
量子电脑受到许多瞩目，因为有许多问题已知在BQP内，但是一般认为在P之外（换句话说，使用量子电脑比起一般电脑，能大幅缩短计算这些问题的时间）。一些著名的例子有：
- 整数分解（参考秀尔算法）[1]
- 离散对数[1]
- 模拟量子系统（参考universalquantum simulator）
- 在特定根之下计算Jones polynomial
参考资料
[编辑]- ^ 1.0 1.1 arXiv:quant-ph/9508027v2 Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor. [2012-12-02]. （原始内容存档于2014-12-04）.
