新的量子算法提高了解决方案的效率水平

研究人员提出了一种全新的算法，可以显着提高量子计算机在某些问题上的性能，并表明经典解决方案在其他情况下也可以同样出色。

量子计算机利用量子力学原理，使其能够以比经典计算机快得多的速度执行一些复杂的计算。与经典计算机一样，量子计算机通过执行由一组精确指令组成的算法来工作。

“我们的新算法有效地缩短了浏览大量解决方案空间的任务，使其成为解决经典困难优化问题的强大工具，”澳大利亚国立大学的学生、该论文的主要作者 V Vijeendran 说。

实用的量子计算面临着由噪声、状态设置误差、测量误差和有限的通信带来的挑战，这些挑战通常限制了量子电路的大小和可以执行的操作数量（称为电路深度）。

然而，这个新算法发表于 量子科学与技术 它旨在克服这些障碍，因此更容易在当前一代量子计算机上实现。

Vijendran 先生表示：“这意味着在不牺牲性能的情况下使用更少的量子资源和更少的量子电路。”他在澳大利亚国立大学与 ARC 量子计算和通信技术卓越中心 (CQC2T) 和 A*STAR 进行了本科研究。新加坡。

Vijendran 先生在所谓的 MaxCut 上测试了他的算法，这是一类组合优化问题，需要从一组有限的可能性中找到最佳解决方案。 MaxCut 以最大化它们之间相关性的方式处理图上的划分点 – 挑战在于可能性的数量会随着问题的大小（在本例中为点的数量）呈指数增长。

“对于此类问题，找到最佳解决方案通常是不切实际的，”Vijendran 先生说。

“相反，我们使用近似算法来找到足够好的解决方案。但是，存在一个权衡：您想要的解决方案越快，您就越需要在其质量上做出妥协，这意味着它可能不接近最优。解决方案。”

MaxCut 问题最著名的近似算法是 1994 年的 Goemans-Williamson 算法，该算法堪称经典。

2014 年，麻省理工学院的研究人员首次转向量子计算。他们的方法被称为量子近似优化算法（QAOA），从初始猜测的量子态开始，旨在通过调整控制演化的参数，将其演化到解决给定问题的状态。对量子近似优化算法有效性的持续研究表明，理论上，在足够深的量子电路下，量子近似优化算法有可能超越现代 Gomans-Williamson 算法。

但到目前为止，还无法测试其潜力，因为量子计算硬件还不够好，维金德兰先生说。

“实际上，硬件噪音很大，这​​意味着在进行许多连续操作时，解决方案的质量会下降。”

“即使容错量子计算成为现实，QA 分析在搜索整个参数空间时仍然可能陷入陷阱，这可能会抵消任何量子优势。”

在寻找克服这些限制的方法时，Vijeendran 先生从神经网络中获得了灵感。神经网络的优点之一是它们能够学习和逼近不同的函数，特别是当模型的参数多于它要学习和逼近的函数时，这种情况称为过度参数化。

Vijendran 先生预测，通过对 QAOA 进行过度参数化，可以更有效地调整可变参数，从而获得更好的性能并克服一些固有的限制。

Vijendran 先生在 Syed Asad 博士和 Ping Kui Lam 教授的监督下与澳大利亚国立大学博士生 Aritra Das 和 A*STAR 科学家 Dax Enchan Koh 博士合作，将这种方法应用于农业质量保证。

为了评估算法的有效性，团队推导了分析表达式来衡量性能，并进行了经典模拟。

他们的算法称为 eXpressive QAOA (XQAOA)，在具有 128 和 256 个顶点（相当于 128 和 256 量子位）的图的 MaxCut 问题中，其性能优于标准 QAOA 算法及其变体以及现代经典 Goemans-Williamson 算法 – 即使使用最少的操作。

与 QAOA 不同，XQAOA 不会受到陷阱的影响，这极大地促进了量子态的演化。

Vijeendran 先生解释说，最令人惊讶的是，他们发现他们的算法收敛到了经典解决方案。

“XQAOA从实验性的纠缠量子态开始，通过微调参数直到算法收敛到最优的过程，纠缠以及叠加等其他量子特征逐渐减弱，最终得到的状态是经典态。 ”

Vijendran 先生表示，这一发现证实量子计算机不会取代经典计算机，而是提供解决问题的补充方法。

“人们有一种误解，认为量子计算机可以提供全面、通用的解决方案，但事实证明，经典解决方案在某些任务上更为有效。

“在不首先考虑定量方法是否优于经典方法的情况下立即选择定量方法来解决问题是一个错误。

“这些问题包括现实世界的优化挑战，例如运输优化、车辆路线、调度和规划，这些问题与行业高度相关。”

虽然他们目前的研究表明他们考虑的一系列问题没有数量上的优势，但维金德兰先生仍然保持乐观。

“当我们处理更复杂的问题时，我们可能会发现量子计算提供明显优势的场景，”他补充道。

本文首发于 澳大利亚国立大学物理系。