从理论上讲，量子计算机在计算速度上远优于经典计算机。苏黎世联邦理工学院超级计算专家Torsten Hoefler说，为了让他们在实践中实际计算得更快，需要更多的高速算法。

量子计算机承诺它们可以比经典计算机更快地解决一些计算问题。这在多大程度上是真实的，或者至少是现实的？

Torsten Hoefler：总的来说，这种说法是正确的。量子计算机实际上可以比经典计算机更快地解决一些计算问题。我想说，他们实际上能够将计算时间从几十年或几年减少到几个小时甚至几分钟。这是真的，但对于所有的计算问题来说并不现实。

量子计算机不擅长哪些问题？

Torsten Hoefler：例如，如果我们想更快地进行天气预报或气候模拟，那么我还不知道如何用量子计算机显著加速这些应用。我也不知道今天量子计算机如何显著加速机器学习。此外，对于湍流中的流动动力学，在可预见的未来，我们可能无法利用当前的量子算法获得实际优势。

您是否看到量子计算机可以在不久的将来展示其优势的基础研究或工业应用领域？

Torsten Hoefler：到目前为止，我们确信量子计算机与大量研发领域极为相关。我正在考虑诸如破解基于质因数分析的著名密码方法之类的问题。或者当涉及到以非常高的精度模拟化学系统时，量子计算具有巨大的改进潜力。

此外，量子计算对于基于量子现象模拟材料特性、未来新药、发明新肥料或了解生物系统如何运作等研究领域非常有前途。在所有这些领域，量子计算机都可以在加速计算方面发挥关键作用。

但这仍然是未来的愿景吗？

Torsten Hoefler：是的，但即使量子计算还不能应用于这些领域的所有未决问题，我们清楚地看到了一种可以更好地发挥量子计算机潜力的方法。但是，这并不适用于所有算法。你不能只采用任何算法，在量子计算机上运行它，计算就会自动变得更快。原则上，量子计算机可以解决任何计算问题，但其应用的关键问题是它们在实践中比经典计算机更快或更便宜地解决了哪些问题。

您在多大程度上修正了量子计算机总是比经典计算机快的假设？

Torsten Hoefler：一些人认为量子计算机从根本上来说速度更快，因为它们能够以更少的平方步骤解决许多问题。但是单个量子计算步骤比经典计算步骤慢得多。由于叠加、干涉或纠缠等量子力学原理，解决给定问题所需的计算步骤更少。这就是为什么量子计算机承诺比经典计算机更快地解决某些问题。然而，如果认为量子计算机可以比传统计算机更快地解决任何问题，那将是一个谬论。

这是为什么？

Torsten Hoefler：在当前量子计算机的设计中，每个计算步骤都比相应的经典计算步骤慢。这是由于纠错的高复杂性和量子计算的各个步骤。此外，传统的数据处理行业60年代以来一直在进步技术，因此速度极快。如今，一台经典的计算机每秒可以执行数百万到数十亿步。另一方面，量子计算机每秒只能执行数十万到数百万步。因此，量子计算机并不总是优越的。我们试图反驳这种包罗万象的量子优越性的错误观点。但我非常乐观地认为，我们将建造可靠的量子计算机。

你在研究中得到了什么科学发现？量子计算机在哪些类型的问题上最有可能更快？

Torsten Hoefler：我们将市场领先的经典芯片的性能与优化设计的量子芯片的性能进行了比较，每个芯片都针对相同的问题。在这样做的过程中，我们是第一个确定量子计算机实现真正的速度优势到底需要什么的人。我们的分析表明，对于几乎所有算法，经典计算机对于非常小的问题规模更快，而量子计算机对于非常大的问题规模更快。这是因为与经典计算机相比，在量子计算机上解决某些问题所需的时间随着问题规模的增加而增长得更慢。

我们也看到，对于小数据的大计算问题，量子计算机一般速度更快，更实用，但对于大数据问题就不实用了。由于输入和输出带宽有限，大量数据是经典计算机计算速度更快的问题。此外，经典计算机还可以比量子计算机更快地解决数据库中的搜索问题。因此，量子计算机在大数据方面被不公平地炒作。

您的一项发现是，“平方加速”不足以让量子计算机真正发挥其潜在的速度优势。

Torsten Hoefler：在我们的研究中，我们表明平方加速通过对算法的运行时间求平方根来减少计算时间，在可预见的未来不足以实现实际的量子优势。

我们看到，如果只实现二次方的速度提升，很多问题的量子计算仍然需要几个月的时间。实际上，这太慢而且太昂贵。由此我们推断，至少需要基于三次方根和四次方根的三次或四次加速度，因为只有这样才能进行数千或数百万次算术运算。但即使是三次或四次加速度也只是最低要求。

有必要关注指数加速度，其中量子算法的运行时间是经典算法运行时间的对数。因此，最有希望实现真正实用的量子优势的候选者是小数据集和指数加速的问题。

要实现真正的高速量子计算，需要采取哪些不同的措施？

Torsten Hoefler：新型量子算法是加速量子计算的关键。如果不对算法进行重大改进，即使是一些经常被引用的应用程序也不太可能在实践中真正带来量子优势。从实用的角度来看，当今可用的大多数量子算法都无法真正加速量子计算。即使我们知道三次、四次或指数算法比二次算法更能加速量子计算，但实际情况仍然是这样的，到目前为止我们还不知道很多这样的加速算法。

目前，许多量子加速算法都基于二次“量子加速”，它建立在著名的 Grover 算法之上。我们认为开发更多 Grover 风格的算法是不够的。为了开发真正使计算速度更快的新量子算法，研究需要集中在实际使更快的量子计算成为可能的算法上。否则，量子计算机将无法超越最快的经典计算机。

计算机科学家需要什么才能真正加速量子计算？

Torsten Hoefler：我们必须发明新颖的高速量子算法。最大的挑战是，我们目前只有少数基本量子算法，如Grover算法或Shor算法，它们广泛用于化学或密码学。开发新的基本算法非常困难。由于量子力学是一个复杂的数学概念，理解如何将其转化为有用的量子算法是一项艰巨的任务。根据经验，大约每十年开发一种基本算法。

量子算法开发的下一步是什么？

Torsten Hoefler：我们需要更多的计算机科学家和数学家来研究新的量子算法。到目前为止，很难找到优秀的量子算法科学家。

这篇文章于5月26日发布在苏黎世联邦理工学院官网上。

DOI:10.1145/3571725