1.1.2 软件
虽然理论上量子计算可以在一些领域取得巨大突破，但是人们普遍认为，量子计算机或量子处理器可以接管经典计算机的部分任务，但不能取而代之。可以使用量子计算解决的问题，与目前使用经典计算机解决的问题并无不同。然而，量子计算由于采用了完全不同的底层方法，因此可以用完全不同的方式处理问题。对于给定的一组问题，使用量子计算可以显著提高性能。因此，当今由于没有足够的计算资源而无法解决的问题，如模拟化学反应、优化问题或整数分解，用量子计算机应该就可以求解。
关于时间复杂度
算法的复杂度通常用时间复杂度表示。一般而言，当输入规模增加时，算法就需要更长的时间。根据问题在输入规模增加时难度提升的值，可以将问题分为不同的类别。这通常用大O记号表示。
假设输入数据有n项。如果每项输入需要固定数量的处理步骤，则算法完成的总时间与n呈线性关系。在这种情况下，我们称算法需要线性时间。
许多算法比这更复杂。当输入数据的数量增加时，所需的总步数可能会以n的平方（n2）或n的k次方（nk，其中k为常数）的速度增加。在这种情况下，我们称算法需要多项式时间。
还有一些算法随着输入数据的增加而变得更难，如果没有已知的算法可以在多项式时间内解决问题，我们就称这一算法需要非多项式时间。如果算法的步骤数随n的增加指数级增长，则称该算法需要指数级时间。当问题需要2n步时，复杂度显然会急剧增加，因为n是步骤数量的指数。在稍后讨论的另一个示例中，所需步骤数为
，其中b是位数，因此该问题也被称为指数复杂度。
事实证明，量子计算机将有助于在多项式时间内解决经典计算机无法在多项式时间内解决。一个常见的例子是就是整数分解，它是加密中的常见操作（例如应用于广泛使用的密码系统RSA），或者更准确地说是破解加密算法。整数分解的基本思想是将一个数分解为几个质数，使它们的乘积等于原数，如15=3×5。虽然没有计算机也很容易做到，但可以想象，当数字变大时计算机就会变得很有帮助，例如将146963分解为281×523。
想要分解的数字越大，找到答案所需的时间就越长。这是许多安全算法的基础。其思路是几乎不可能分解一个包含1024位的数字。可以证明，解决这个问题所需时间的增长趋势大约与以下函数相同：
（1.1）
其中 b 是原数所包含的位数。此式开头的 e 是重要部分：简言之，这意味着 b增大，分解该数字所需的时间会指数级增加。图1.1显示了分解一个b位数字的时间复杂度。
需要注意的是，绝对时间并不重要。这里要表达的是，即使用现有最快的计算机，只增加一位也会带来巨大的差异。
由于没有已知的经典算法可以在多项式时间内解决这一问题，因此我们称这一问题是非多项式时间的，因而通过增加数字的位数，经典计算机就几乎不可能得到这一问题的答案。
然而，同样的问题可以利用量子算法在多项式时间内解决。利用舒尔算法，量子计算机解决这一问题的时间与
同阶，详情参见第11章。
为了说明这意味着什么，我们将量子计算机利用量子算法与经典计算机利用经典算法的时间复杂度图像叠加在一起，如图1.2所示。
图1.1 时间随位数指数级增长
图1.2 多项式时间与指数级时间的对比
从一定位数起，量子计算机的解题速度开始超越经典计算机。而且位数越多，这个差距就越大。这是因为经典计算机解决这一问题所需的时间随位数指数级增长，而量子算法只会随之以多项式方式增长。
这类问题在量子上是多项式时间的，是相对值得利用量子计算机处理的问题。
注意：舒尔算法是最流行的量子计算算法之一。但基于一些原因，仅在第11章中讨论该算法。首先，要想充分理解算法的工作原理，必须掌握量子计算的基本知识。其次，以当前的硬件状态，即使有了快速的革新，大多数专家认为，距离量子计算机能在实际可接受的时间内算出合理大小的密钥，仍有数年的时间。你应该尽早考虑舒尔算法，但我们也不想给你错误的期望。最后，尽管舒尔算法的影响可能很大，但量子计算在其他领域也能产生巨大影响，例如医疗、化学、优化问题等。