“量子计算可以解决经典计算机无法解决的问题”
你听过上面这种说法吗？在本文中，我们将探索量子计算解决复杂问题的潜力，并研究有界错误量子多项式时间 ( BQP ) 的概念及其与经典复杂性类的关系。我们将研究量子计算的基础知识，直观地了解BQP是什么以及它与经典计算模型的区别。
经典复杂性类
理论计算机科学的世界充满了迷人的概念，其中最有趣的概念之一就是复杂性类。
即经典计算机解决不同类型的问题需要多长时间
两个最重要的复杂性类别是P和NP。
P代表“多项式时间”，它代表经典计算机可以在合理时间内解决的所有问题的集合。
NP代表“非确定性多项式时间”，它代表所有问题的集合，这些问题的解决方案可以在合理的时间内由经典计算机验证。
如果您曾经想过，赢得 100 万美元最难的方法是什么？NP中的所有问题是否也可以在多项式时间内解决，或者可能需要几十年的时间。
如果一个问题的解决方案很容易检查正确性，那么这个问题一定很容易解决吗？
不难看出P ⊆ NP，但上面的问题是P = NP。这被称为P vs NP问题，它被认为是理论计算机科学中最重要的开放性问题之一。这个问题的解决方案会给解决者 100 万美元的奖金，因为P vs NP被提及为千年奖问题之一（人们普遍认为P ≠ NP）
PSPACE代表“多项式空间”，它表示可以在经典计算机上使用多项式空间解决的问题类别。它是一个包含P和NP的复杂类，并且被认为是比它们都大的类。换句话说，任何可以在多项式时间或多项式空间解决的问题也是一个PSPACE问题。
复杂度子集 PSPACE
另一个有趣的概念是时间层次定理，它指出，对于任何复杂性类，都存在可以在比多项式函数增长更快的时间内解决的问题。简单来说，这意味着问题的复杂程度没有上限，并且不知道层次结构在哪里崩溃。
量子复杂性类
有界错误量子多项式时间( BQP ) 是一个复杂性类，它描述了可以在多项式时间内在量子计算机上以有界误差概率解决的问题类别。这类问题被认为是量子计算的“最佳点”，因为它代表了量子计算的能力和局限性之间的平衡，特别是所有实例的错误概率最多为 1/3
BQP中最重要和最著名的问题之一是Shor 算法，这是一种用于分解整数的量子算法。它比这项任务中最著名的经典算法快成指数级，并且有可能打破许多依赖大整数分解难度的现代密码系统。
BQP中另一个重要的问题是量子近似优化算法（QAOA），它是一种解决优化问题的量子算法。对于某些类型的优化问题，它已被证明比经典算法更有效，并且在机器学习和物流等领域具有潜在的应用。
P ⊆ BQP ⊆ P-SPACE
现在让我们回到复杂性层次结构表明每个经典电路都可以用量子电路来模拟，因此我们可以看到P ⊆ BQP。
此外，我们将证明BQP ⊆ P-SPACE。为此，我们需要使用一种称为历史总和的技术。这种技术是一种可视化量子电路中量子态演化的方法。它用于解决APPROX-QCIRCUIT-PROB问题。
该技术涉及将电路可视化为树，输入为根，每个门为树的级别。根到叶路径的过渡幅度是路径上边上所有权重的乘积。为了计算最终状态的概率，我们将结束于代表该最终状态的节点的所有根到叶路径的振幅相加。
在这里我们不会深入研究技术细节，这个过程可以看作是动态规划的一种形式，其中最终的概率是通过组合树中子路径的概率来计算的。这个过程可以在多项式内存中完成，这与P-SPACE问题所需的内存相同。因此，由于可以使用P-SPACE算法的历史求和技术有效地解决BQP问题，因此可以推断BQP是P-SPACE的子集。
NP与BQP的关系
如您所想，上面提到的是计算机科学中的一个未解决的问题。除非P vs NP问题得到解决，否则我们将无法给出这两个类之间的确切关系。但是，我们看到了P ⊆ BQP，并且推测即使在量子计算机上，像旅行商问题(TSP)这样的NP 完全问题也无法在误差有限的多项式时间内解决。
相对于BPP和其他概率类，BQP类的结果更好。看看这张图
如果BQP = NP，这意味着量子计算机可以有效地解决 NP 中的所有问题，这将对密码学和优化等领域产生重大影响。但是，如果BQP不等于NP，则意味着存在量子计算机可以有效解决而经典计算机无法解决的问题，这将提供一类可以使用量子计算机解决的新问题。
NP和BQP之间的关系是理论计算机科学领域正在进行的研究和争论的话题。虽然一些研究人员认为量子计算机可以有效地解决NP中的所有问题，但其他人认为经典计算和量子计算之间存在根本差异，这将阻止这种情况发生。它尚未得到证实，但它具有塑造量子计算领域的巨大潜力，并可能对广泛的行业和领域产生重大影响。
