量子信息的过去、现在和未来(5)

理论上还发现，对于现代密码学感兴趣的问题，量子算法相比最著名的经典算法具有超多项式优势，例如找到大合数的质因数[33–35]。此外，众所周知，量子计算机可以加速对组合优化问题的解的穷举搜索，但在这种情况下，加速是二次的，这意味着求解的量子时间是经典时间的平方根量级[36,37]。
5. 什么是量子计算机？
一种描述理想量子计算机的数学模型已被创立出来，即量子电路模型（quantum circuit model），它包含如下五个基本要素[38]。
（1）一个含有大量量子比特的物理系统，其中的量子比特数可以根据待解决问题规模的增大而增加。
（2）能够制备量子比特的简单标准初态，实际上是将系统冷却到低熵状态。
（3）一组通用的纠缠量子操作，称为量子门，每个量子门都作用于两个或多个量子比特。这意味着通过连续组合许多这样的门，我们可以近似出作用于大量量子比特的任意酉变换。
（4）一种能有效地将问题转化为合适的量子门电路的经典计算机。
（5）能够在标准基上对量子比特进行测量，以读出提供计算结果的经典比特。能有效解决的问题指的是那些可以用大量量子门以高成功率解决的问题，这些量子门的数目是问题输入规模的多项式量级。
其他物理上合理的量子计算模型也有被研究过，如拓扑模型[39,40]和绝热模型[41,42]，并被证明与量子电路模型等价，从而进一步支持了扩展的丘奇-图灵论题的量子版本。
应该意识到，如果用随机数生成器来得到最终量子测量的不确定性，量子电路模型的所有特征都可以由传统的经典计算机模拟。经典计算机所需要做的就是，当我们用一系列矩阵作用于希尔伯特空间中的矢量时，跟踪这个矢量的变化。至于最终读出，就是将该矢量投影到一组标准基上，并相应地为不同的测量结果分配概率。由于一台（随机化的）经典计算机可以做量子计算机能做的所有事，因此它们在可计算性上没有区别——量子计算机能计算的任何东西也可以由经典计算机计算。
量子模型和经典模型之间的重要区别在于效率。一般来说，经典计算机要模拟量子计算机，就必须处理一个空间维度为量子比特数的指数的矢量。对于最困难的问题实例，所有已知的用于进行这一模拟的经典方法都需要随量子比特数呈指数级增长的资源。
6. 量子硬件
1994年发现Shor的大数分解算法后，人们对量子计算的兴趣激增，引发了对构建硬件的可能方法的寻求。这些硬件要能满足上述五个标准（至少达到合理的近似值）。人们注意到，出于其他原因已经在开发的一些技术可以用于相干量子信息处理。