量子计算带来了计算能力大幅提升的希望。这便是量子计算机的承诺，它们能够处理数十万甚至数百万个量子比特（qubits）。
但目前，最先进的量子计算机仅能处理几十个量子比特，并且在任何有意义的方面都无法超越经典计算机。部分原因是，即使是简单的问题，量子算法通常也需要数百甚至数千个量子比特。因此，数学家和计算机科学家们迫切地在寻找更优雅、依赖更少量子比特的算法。
德国汉堡大学的 Kapil Goswami 和他的同事们找到了用一个量子比特解决旅行商问题的方法。他们表示，这种方法可以应用于其他问题，并有可能改变计算机科学家对量子算法的思考方式。
旅行商问题是一个组合优化问题，也是数学中最受深入研究的难题之一。挑战在于找到访问给定列表中所有城市的最短路线。据数学家所知，要做到这一点，唯一的方法是计算所有路线的长度，然后选择最短的那一条。
当城市数量很少时，这很容易解决。但随着城市数量的增加，可能的路线数量会以 n!（城市数量的阶乘）的速度增长。例如，4! 是 24，但 10! 是 3,628,800，100! 是 9 x 10^157。因此，即使是最强大的经典计算机也很快无法处理。
优雅的球面
因此，计算机科学家们开发了计算最优路线的算法，这些路线可能不是最短的，但可能只比最短路线长几个百分点。但即使是这些算法，在城市数量很大的情况下也是计算密集型的。
量子计算一直有望加速这些算法。但 Goswami 及其团队表示，即使是最好的量子算法也需要大量的量子比特。“在 D-wave 量子架构上编码 9 和 10 个城市问题的量子算法需要 73 个逻辑量子比特或 5436 个物理量子比特，”他们说道。
因此，将这个问题压缩到只有一个量子比特是一个重大的进步。Goswami 及其团队利用一种将量子系统的状态空间表示为几何球体的方法，称为 Bloch 球。然后，他们将城市的位置表示为 Bloch 球上的量子态。因此，从一个城市旅行到下一个城市的过程可以通过一系列的球体旋转来实现。
事实上，通过叠加过程，这个球体可以表示从每个城市到所有其他城市的路线。“我们利用状态的叠加一次性遍历多条路径，”他们说。然后，可以通过对量子态进行适当的测量来选择最优路线。
这种方法适用于任何能够以任何方式旋转量子比特的量子计算机。这包括超导机器、离子阱平台机器、金刚石中的氮空位中心等。
结果显示，这些方法比使用更大设备以前取得的成果要好得多。“我们表明，对于四到六个城市的旅行商问题，该算法能够找到大多数问题实例的精确解，这比目前的量子方案要好得多，”Goswami 及其团队说道。
对于更多的城市，量子态必须更紧密地聚集在球面上，这使得它们更容易受到噪声和错误的影响。尽管如此，该团队在最多 9 个城市的问题上取得了成功。
量子搜索
这是一项引人入胜的工作，具有重大的潜力。该团队表示，将问题映射到几何球体上的可视化过程本身就是一项重要的进展，因为它立即为以同样的方式映射其他问题开辟了道路。“我们的方案将作为模板，进一步开发利用叠加原理实现资源效率的算法，”研究人员说。
特别是，该团队指出，在 Bloch 球上的状态叠加中进行搜索，在数学上与 Grover 的量子搜索算法相似，Grover 的算法是最简单也是最强大的量子算法之一，并且比经典算法的速度快得多。这表明，无论如何应用，这种方法都应该能实现与经典算法相似的加速。
尽管量子计算机仍然是嘈杂的机器，量子比特数量有限，但这将 Bloch 球作为量子工具库中的一个有希望的新工具。
参考：使用单个量子比特解决旅行商问题：arxiv.org/abs/2407.17207
