1.1.3　算法

对于经典计算机难以解决（非多项式时间）而量子计算机相对容易解决（多项式时间）的计算问题，舒尔算法是一个非常好的例子。这个差异从何而来？我们将在第11章讨论，舒尔算法将整数分解问题转换为求函数周期性的问题，即求的值，使得对于所有的都有。这个问题在经典计算机上仍然很难解决，但在量子计算机上相对容易解决。

如今已知适用于量子计算机的大多数算法，都基于相同的原理：将初始问题转换为容易用量子计算机解决的问题。经典方法如图1.3所示，将知名的算法应用于该问题，并获得结果。

图1.3　经典方法：在经典计算机上解决问题

如果可以设法将初始问题转换为一个量子计算机容易解决的问题，就可以期待效率提升，如图1.4所示。

图1.4　将问题转换为量子计算机可以带来重大改变的领域

注意，需要考虑将初始问题转换为另一个问题，以及将结果转换回去的代价。但是在谈论计算密集型算法时，这一代价应该可以忽略。

注意：在阅读量子算法的解释时，你可能会奇怪为什么这看似是绕了远路。这是因为量子计算机可以快速地解决一些特定的问题，可以将初始问题转换为这些特定问题的其中之一，将有可能利用量子计算机执行快得多的算法。

提出这些算法通常需要深厚的数学背景。一般而言，开发人员不会为应用创建新的量子算法，而是使用现有算法，寻求量子计算机的帮助。但是，开发人员如果了解量子算法的基础知识，理解为什么它们更快以及如何使用它们，将在工作中具有优势。