⚛️ 量子物理

Rotational Encoding of Objective Functions for Quantum Optimization

本文介绍了角旋转计数器（Angular Rotational Counter, ARC），这是一种将目标函数编码为单比特量子旋转的新颖方法，与传统的基于布尔逻辑的预言机相比，该方法显著降低了量子优化任务中的量子比特数、门数量、电路深度以及量子代价。

原作者： Sonia Yang, Ali Al-Bayaty, Shanyan Chen, Marek Perkowski

发布于 2026-11-10

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Sonia Yang, Ali Al-Bayaty, Shanyan Chen, Marek Perkowski

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

在计算领域，存在着一个被称为“优化”的持久挑战：即在浩如烟海的可能性中寻找唯一的最佳解。想象一下，试图在一个拥有数十亿个转弯的迷宫中寻找最短路径；传统的计算机必须逐一检查每条路径，对于复杂问题而言，这个过程可能比宇宙的年龄还要长。量子计算提供了一种不同的方法。通过利用支配亚原子世界的奇异物理定律，量子计算机可以同时探索许多路径。然而，为了实现这一点，研究人员必须构建一个被称为“算谕”（oracle）的特殊组件。可以将这个算谕想象成一个向导，它能够瞬间识别出好的解，并将其标记出来供计算机寻找。多年来，为优化问题构建这些向导就像是用锤子建造摩天大楼一样：这个过程需要大量的微小且脆弱的部件，使得最终的结构对于当前技术而言过于庞大且昂贵。

一支研究团队现在推出了一种构建这些向导的高效新方法。他们开发了一种名为“角旋转计数器”（Angular Rotational Counter，简称 ARC）的方法，该方法改变了量子计算机处理解值的方式。在旧的方法中，计算机必须计算出解的精确代价，并将这个数字存储在一长排内存位中，这非常类似于在纸上写下一个大数字。这需要大量的空间和复杂的机械装置来将该数字与目标进行比较。新的 ARC 方法则完全跳过了编写和比较的过程。该方法不再存储数字，而是通过一个量，使一个量子比特（qubit）轻微旋转一个与解的代价相对应的角度。如果一个解很好，比特就向一个方向旋转；如果解很差，则向另一个方向旋转。计算机不需要通过读取一个数字来了解答案的质量，它只需测量比特旋转的角度即可。

研究人员在数字设计中一个经典的课题——状态分配（state assignment）上测试了这种新方法。状态分配涉及确定为机器的不同状态贴标签的最有效方式。他们创建了 26 个不同的测试案例，范围从小型、简单的机器到更大、更复杂的机器，并将他们新的基于 ARC 的向导与传统的、存储数字的向导进行了对比。结果令人瞩目。新方法所需的物理组件显著减少。平均而言，新向导使用的量子比特（信息的基本单位）减少了约百分之二十。更令人震撼的是，它们将逻辑门（执行计算的开关）的数量减少了近百分之九十。电路深度（与计算持续时间相关）下降了超过百分之九十二。在综合衡量所有这些因素的“成本”指标方面，新方法比旧方法高效了百分之九十以上。

这些发现表明，改变量子计算机中信息的表示方式可以节省资源。研究人员证明，通过将一个数值编码为物理旋转而非存储的二进制数字，他们可以用极少的硬件解决相同的优化问题。虽然这项研究是通过经典计算机上的模拟而非在物理量子机器上进行的，但其数学证明和详细的电路设计为未来的硬件提供了清晰的路线图。这项工作并不声称已经解决了量子加速问题，也没有声称构建了一台能瞬间运行的机器，但它确实表明，构建这些机器的道路现在变得不再那么拥挤。通过减轻存储和比较大数字的沉重负担，角旋转计数器为引导量子计算机寻找最佳答案提供了一种更轻便、更实用的方式，这使得未来的量子设备处理复杂的优化任务变得具有可行性。

技术摘要：用于量子优化的旋转编码目标函数

问题陈述

量子搜索算法（如 Grover 算法）为约束满足问题（CSP）和组合优化提供了计算优势。然而，其实用性受到构建特定问题预言机（Oracle）成本的严重制约。在传统的优化方法中，预言机是基于布尔逻辑的，并依赖多比特寄存器来显式地以二进制形式存储目标函数值。这些值随后通过算术算子（例如受控增量器）和比较器与动态更新的阈值进行比较。

这种传统方法带来了显著的开销：

资源密集型： 它需要多个多比特寄存器（一个用于目标值，一个用于阈值）以及大量的辅助比特（ancilla qubits）。
电路深度与成本： 算术和比较器电路由许多可逆门组成，导致高门计数、深层电路，并增加了对退相干的敏感性。
迭代执行： 由于布尔预言机本身无法对有效解进行按成本排序，因此优化需要通过不断更新阈值来重复运行搜索算法，从而进一步增加了执行时间。

本文旨在寻求一种替代表示方法，将目标函数信息直接整合进量子操作中，以降低上述成本。

方法论：角度旋转计数器 (ARC)

作者引入了角度旋转计数器 (ARC)，这是一种电路设计，它将目标函数编码为单比特寄存器上累积的量子旋转之和，而非将其作为二进制值存储在多比特寄存器中。

核心机制

ARC 适用于可以分解为布尔函数加权和的形式的目标函数：
$C(x) = \sum_{i=1}^{m} w_i f_i(x)$
其中 $w_i \geq 0$ 是权重， $f_i(x)$ 是布尔函数。

该电路的操作流程如下：

输入： 处理候选解 $x$ 。
布尔评估： 在控制比特上计算每个项 $f_i(x)$ 。
旋转编码： 如果 $f_i(x) = 1$ ，则受控旋转门（具体为 $RX$ 门）会对输出比特施加一个角度为 $\frac{\pi}{K} w_i$ 的旋转。如果 $f_i(x) = 0$ ，则不发生旋转。
累积： 应用于输出比特的总旋转角度与目标值 $C(x)$ 成正比： $\theta = \frac{\pi}{K} C(x)$ 。

数学特性

论文证明了输出比特的测量概率与目标值 $C(x)$ 具有单调相关性：

最大化： 如果输出比特初始化为 $|0\rangle$ ，则随着 $C(x)$ 的增加，测量到 $|1\rangle$ 的概率会在区间 $(0, K)$ 内增大。
最小化： 如果初始化为 $|1\rangle$ ，则随着 $C(x)$ 的增加，测量到 $|1\rangle$ 的概率会减小。
约束： 常数 $K$ 必须设置得大于或等于可能的最大目标值，以确保在相关范围内保持单调性。

应用：状态分配

作者将 ARC 应用于有限自动机的状态分配问题，这是结构化自动机综合中的一个基本问题。其目标是为状态分配不同的二进制编码，以最小化成本函数。

成本函数： 状态编码之间的启发式加权汉明距离，这是二次指派问题的一种特例。
预言机构建： 预言机包含一个编码检查器（以确保状态唯一）和一个基于 ARC 的成本计算器。ARC 取代了传统的算术计数器和比较器。
算法： 该预言机被集成到 Grover 搜索算法中。算法仅需使用构建的预言机执行一次 Grover 搜索。随后对输入比特进行测量，并根据最高的测量概率选择 $r \geq 1$ 个解。至关重要的是，这些选定的解仍必须经过检查，以验证其有效性和最优性，因为测量概率指示了成本趋势，但在没有后处理验证的情况下，并不能保证单次运行即可获得有效解。

主要贡献

旋转编码框架： 引入 ARC 作为一种通过单比特上的累积量子旋转来表示可分解目标函数的方法，这与显式的二进制编码形成对比。
数学形式化： 证明了 ARC 旋转地编码了目标函数，并且输出比特的测量概率与目标值呈单调依赖关系，从而实现了无需迭代更新阈值的直接优化。
状态分配的预言机设计： 利用加权汉明距离成本函数构建了针对状态分配问题的特定预言机，展示了 ARC 在重要组合优化问题中的适用性。
全面评估： 将 ARC 预言机与基于布尔的预言机在 26 个基准测试上进行了对比分析。

实验结果

作者在来自 LGSynth'91 库的 26 个有限状态机基准测试上，评估了 ARC 预言机与相应的基于布尔的预言机的性能。电路使用 Qiskit（等级 3 优化）转译为原生门（CZ, RX, RZ, $\sqrt{X}$ , X）。

性能指标（算术平均减少量）：

量子比特数： 减少了 20.8%（范围为 3.9% 至 45.2%）。这归功于用单比特寄存器取代了用于成本和阈值处理的多比特寄存器。
门计数： 减少了 89.3%（范围为 63.8% 至 99.5%）。
电路深度： 减少了 92.4%（范围为 72.8% 至 99.7%）。
转译量子成本 (TQC)： 减少了 90.6%（范围为 67.4% 至 99.6%）。

门计数和深度的显著降低主要源于消除了昂贵的受控增量器门和比较器，取而代之的是 ARC 设计中的受控旋转门。

意义与声明

论文声称，对于所评估的基准测试，ARC 提供了显著的电路成本降低，确立了旋转编码作为在量子搜索优化中替代显式二进制编码的一种极具前景的方法。

资源效率： 该方法显著降低了量子比特、门和深度的需求，这对于具有有限相干性和连通性的近期待机量子设备至关重要。
算法结构： 它通过将成本直接编码进概率振幅中，实现了在单次量子搜索算法执行内的优化，从而消除了布尔预言机所需的迭代阈值更新。算法根据测量概率选择候选解，随后进行验证步骤以确认其有效性。
可扩展性： 理论分析表明，ARC 成本计算器的复杂度为 $O(n^2 \log n)$ ，这明显低于之前基于布尔的方法在状态分配中所表现出的指数级缩放。

局限性与谦逊态度：
作者明确指出，虽然其结果展示了在电路资源效率方面的显著提升，但它们本身并未建立起物理执行时间的减少或渐近量子加速。目前的收益被界定为电路综合成本（量子比特、门、深度）方面的改进，而非保证的物理硬件运行时间优势，后者还将取决于噪声和纠错。目前该方法的适用性是在可分解目标函数（即布尔函数的加权和）下展示的，尽管作者暗示该框架可以扩展到其他问题类别。