⚛️ 量子物理

Designing Quantum Solutions to the Closest String Problem with the Non-Variational QWOA

本文提出了一种基于 NV-QWOA 算法的端到端、非变分量子实现方案，用于解决最接近字符串问题，其特点在于采用了一种新的参数设定方法，该方法在避免特定实例优化需求的同时，能够通过解析估计的资源需求一致地放大最优解。

原作者： Benjamin Rossdeutscher, Jingbo Wang

发布于 2026-10-27

📖 1 分钟阅读🧠 深度阅读

原作者： Benjamin Rossdeutscher, Jingbo Wang

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

在现代计算的广袤版图中，存在着一类如此复杂的谜题，以至于即使是最强大的超级计算机也难以求得精确解。这些是组合优化问题，其目标是在天文数字般的可能性中找到唯一的最佳排列。想象一下，试图在一个装有数十亿把锁的房间里寻找那把完美的钥匙；随着锁的数量增加，检查每一把锁所需的时间增长得如此之快，以至于很快就会变得无法实现。其中一个谜题便是“最接近字符串”（Closest String）问题。它提出了一个简单的疑问：给定一组不同的字符字符串，能否找到一个新的字符串，使其能同时尽可能地接近所有这些字符串？这不仅仅是一个理论上的游戏。科学家们利用这种逻辑来重建受损的通信信息，识别蛋白质分子中的共同结构以进行药物研发，并追踪疾病爆发期间的病毒变异。由于随着问题规模扩大，可能答案的数量会呈爆炸式增长，寻找真正的最优解被认为是计算机科学中最困难的任务之一。

最近，西澳大利亚大学的研究人员利用量子计算机的独特力量，在解决这一问题方面迈出了重要一步。量子计算机不再像经典计算机那样逐一检查答案，而是利用量子力学的奇特规则同时探索多种可能性。他们将一种被称为非变分量子行走优化算法（Non-Variational Quantum Walk Optimization Algorithm，简称 NV-QWOA）的特定技术应用于“最接近字符串”问题。这种方法之所以独特，是因为它不依赖于通过试错过程来调整设置的缓慢过程。相反，研究人员设计了一套固定的指令集，能够自动引导量子计算机走向最佳解决方案。通过在经典计算机上模拟这一过程，他们证明了该方法可以成功放大找到正确答案的概率，将近乎不可能的搜索转化为中小规模问题中可控的任务。

其工作的核心在于构建一个数字蓝图，即量子计算机可以遵循的电路。这个电路就像是一个处理信息的工厂。首先，它创建一个叠加态，即计算机同时持有所有可能答案的状态。然后，它开始一个严格的评估过程。系统将这个潜在答案的云团与原始的参考字符串集合进行对比。它计算每个潜在答案与参考字符串之间的“距离”，即衡量为了使它们匹配需要改变多少个字符。目标是找到在全局范围内所需改动最少的答案。研究人员必须设计一种巧妙的方法，在量子领域内完成这项数学运算，利用特殊的门（gates）来计数差异并确定最大距离，同时又不丢失脆弱的量子信息。

这类量子算法的一个主要障碍是决定如何调整内部设置以获得最佳结果。许多现有方法需要经典计算机根据之前运行的结果不断微调这些设置，这是一个缓慢且低效的过程。研究人员在这项研究中为其中一个关键设置引入了一种新的固定规则。他们发现，通过仅根据问题规模来设定该值，就可以避免任何试错性的调优。这一改变防止了一个常见错误，即引导搜索的量子相位会发生缠绕并相互抵消。通过保持这些相位清晰且比例得当，算法可以更有效地提高找到正确答案的概率。

为了测试他们的想法，团队在模拟量子机器行为的经典计算机上运行了仿真。他们创建了数十个不同的问题场景，范围从简单的三个字符的字符串到更复杂的六个字符的字符串。在每种情况下，他们都从所有可能答案出现的概率均等的初始状态开始。随着算法执行其步骤，它开始偏向于最佳解。经过三十轮处理后，仿真显示测量到完美答案的概率跃升至 80% 以上。在许多情况下，找到最佳答案的机会甚至更高，达到了 90%。系统始终将正确的解推向顶端，同时抑制错误的解，证明了该方法在他们测试的规模内确实有效。

研究人员还仔细统计了如果是在真实的量子硬件上运行，其方法将需要多少资源。他们发现，随着问题规模的增大，所需的量子比特（qubits）数量呈可控方式增长。具体而言，量子比特的数量与参考字符串的数量及字符串的长度呈线性比例关系，但仅与所用字符集的规模呈对数比例关系。这意味着，即使问题变得更加复杂，硬件需求也不会失控爆炸。代表运行计算所需时间的电路深度也遵循一种可预测的模式。这些发现提供了一份清晰的路线图，指明了解决这些问题在现实世界中究竟需要什么样的机器。

尽管目前的结果基于仿真，但其对未来的意义是明确的。这项研究证实了对于经典计算机而言极具挑战性的“最接近字符串”问题，可以通过量子方法得到有效处理。团队的工作提供了一套完整的、循序渐进的指南，指导如何构建必要的量子电路，以及如何在无需持续人工干预的情况下设置其参数。尽管仿真仅限于较小的问题规模，但这些测试中算法的成功表明，它可以扩展到处理遗传学和通信领域中的复杂数据集。研究人员指出，该方法有可能被扩展到解决相关问题，例如在更长的序列中寻找共同子串，从而为更广泛的科学与技术应用打开大门。

这项研究代表了量子优化领域从理论向实践迈出的坚实一步。通过展示一个可运行的电路设计以及一种可靠的参数设置方法，作者为未来的硬件实验提供了基础。他们的工作表明，只要方法得当，量子计算机就可以在庞大的搜索空间中导航，将其力量集中在最有希望的答案上。随着量子硬件的不断进步，本研究中开发的技术很可能成为解决那些目前限制我们分析复杂生物和数字系统的最难优化谜题的蓝图。

技术摘要：基于非变分式 QWOA 的最接近字符串问题的量子解决方案

1. 问题定义

最接近字符串问题 (Closest String Problem, CSP) 是一种被归类为 NP-Hard 的组合优化问题。给定一组由长度为 $n$ 、字母表大小为 $k$ 的 $m$ 个参考字符串组成的集合，目标是找到一个长度为 $n$ 的解字符串 $s$ ，使得该字符串到参考集中任何字符串的最大汉明距离最小。其代价函数定义为：
$f(s) = \max_{i=1,2,...,m} d_H(s, s_i)$
其中 $d_H$ 为汉明距离。

在经典计算中，精确求解该问题对于大规模 $n$ 而言在计算上是难以实现的。穷举搜索的复杂度为 $O(k^n)$ ，且计算单个候选解的代价矩阵需要 $O(mn) $次比较，导致总体的经典复杂度为$ O(k^n mn) $。虽然存在参数化经典算法，但它们对于最大汉明距离$ d$ 仍表现出指数级的缩放特性。CSP 在生物信息学（例如，识别蛋白质分子或突变病毒株中的共同结构）、通信（重建受损信号）以及纠错码领域具有重要的应用价值。

2. 方法论：非变分式 QWOA (NV-QWOA)

作者提出了一种使用 非变分量子行走优化算法 (Non-Variational Quantum Walk Optimization Algorithm, NV-QWOA) 对 CSP 进行端到端量子实现的方案。与依赖于通过经典优化循环来调整参数的变分量子算法 (VQA，如 QAOA) 不同，NV-QWOA 使用由问题结构决定的固定超参数，从而避免了变分方法中存在的贫瘠高原 (barren plateau) 问题以及相关的经典计算开销。

算法步骤

该算法通过 $p$ 次迭代在量子电路中运行，每次迭代包含三个主要部分：

代价评估（相位分离）：
- 算法计算候选解字符串叠加态与所有 $m$ 个参考字符串之间的汉明距离。
- 它使用涉及量子傅里叶加法 (QFA) 和量子状态比较器的确定性量子电路架构来确定每个候选解的最大汉明距离（即代价）。
- 一个与代价成正比的相位偏移被施加到解寄存器上。作者引入了一种修正的相位分离参数 $\gamma$ 的规定，该参数被确定性地定义为 $\gamma = \frac{\pi}{2(n+1)}$ 。这避免了对特定实例进行优化的需求，并减轻了由于模 $2\pi$ 导致的相位缠绕问题，该问题会削弱代价与相位之间的相关性。
混合（量子行走）：
- 在混合图上执行连续时间量子行走 (CTQW)。对于 CSP，该图是一个 汉明图 (Hamming graph)，其中节点代表解字符串，边连接汉明距离为 1 的字符串。
- 该混合幺正算子在相邻状态之间重新分配振幅，从而放大那些具有有利（低）相位的状态。
迭代：
- 重复执行步骤 1 和 2 共 $p$ 次。算法会放大测量到最优或近优解的概率，同时抑制非最优状态。

电路实现细节

门级编码： 实现过程使用 Qiskit 将问题转化为一比特和两比特门。
寄存器： 电路利用七个量子寄存器：一个解寄存器、一个参考寄存器、一个字符寄存器（针对 $k>2$ ）、一个 QFT 寄存器、一个获胜者寄存器、一个获胜槽寄存器以及一个相位目标寄存器。
逆计算 (Uncomputation)： 用于代价计算的辅助寄存器通过埃尔米特共轭操作进行逆计算（去纠缠），以防止干扰混合步骤。
优化： 作者通过集成高效的 OR 门实现与 QFA，优化了汉明距离的计算，从而减少了对额外辅助比特的需求。

3. 核心贡献

显式门级实现： 本文提供了一个完整的自动化工作流，可将任意 CSP 实例转换为量子电路，包括参考字符串的编码、代价评估以及 NV-QWOA 拟设 (ansatz)。
确定性相位缩放： 引入了一种新的、依赖于问题规模的 $\gamma$ 参数规定。这消除了对 $\gamma$ 进行启发式估计或经典优化的需求，确保了算法的真正非变分特性。
资源复杂度分析：
- 量子比特复杂度： $O(nm \log k)$ 。
- 电路深度： 对于固定的字母表大小， $O(pm \log^2 n + pn \log n)$ 。
- 与指数级的经典搜索空间相比，这些估计值代表了一个有利的缩放轨迹。
高效 Max 函数电路： 作者设计了特定的电路架构（使用 CCNOT 和 CSwap 门），能够确定性地找到跨参考集的最大汉明距离，由于 max 函数的非二次性质，这在量子电路中是一项具有挑战性的任务。

4. 结果

作者通过使用 Qiskit-Aer 的经典状态向量模拟验证了该方法。

模拟参数： 实验针对字符串长度 $n \in \{3, 4, 5, 6\}$ 、参考字符串数量 $m=2$ 以及二进制字母表 ( $k=2$ ) 进行。这对应于 15 到 26 个量子比特的电路。
性能：
- 在经过 $p=30$ 次迭代后，算法一致地放大了最优解集（子壳层 0）。
- 测量到最优解的概率在所有测试实例中达到了 80–90%。
- 近优解（子壳层 1）保留了 10–20% 的概率，而所有其他子壳层的概率均收敛至接近于零。
- 确定性的 $\gamma$ 规定被证明是有效的，无需进行代价标准差缩放（研究发现该缩放法在较小规模下略有不利影响）。
观察结论： 结果表明，即使没有经典参数调优，NV-QWOA 也能有效地将测量概率集中在高品质候选解上，其起始状态为均匀叠加态。

5. 意义与声明

本文声称为在量子硬件上解决最接近字符串问题提供了基础框架。其意义在于：

验证适用性： 它证实了 NV-QWOA（此前已在 MaxCut 和 k-means 等问题上得到测试）同样适用于 NP-Hard 的 CSP 问题。
硬件就绪性： 通过提供显式的门级实现和资源估计，这项工作为未来在容错量子计算机上的实验奠定了基础。
基准测试潜力： 作者将这项工作定位为量子算法对比经典求解器的基准测试基础。他们明确指出，建立完整的“端到端量子加速”需要进一步分析迭代缩放 ( $p$ )、测量重复次数以及经典开销，而这些在当前研究中尚未完全解决。
未来扩展： 作者指出，该框架有可能扩展到 最接近子串问题 (Closest Substring Problem)（即解是长为 $L$ 的参考字符串中长度为 $n$ 的子串），尽管目前的研究尚未涉及此领域。

本文保持了审慎的基调，承认虽然该算法在模拟中表现出强大的放大能力，但向实际量子优势的过渡仍需对缩放规律和硬件约束进行进一步研究。