⚛️ quantum physics

A competitive NISQ and qubit-efficient solver for the LABS problem

本文证明了保利相关编码（PCE）框架作为一种高效利用量子比特的变分方法，能够有效解决低自相关二进制序列（LABS）问题，在提升扩展性和抗噪性的同时，以显著更少的量子资源超越了最先进的经典启发式算法。

原作者： Marco Sciorilli, Giancarlo Camilo, Thiago O. Maciel, Askery Canabarro, Lucas Borges, Leandro Aolita

发布于 2026-01-27

📖 1 分钟阅读🧠 深度阅读

原作者： Marco Sciorilli, Giancarlo Camilo, Thiago O. Maciel, Askery Canabarro, Lucas Borges, Leandro Aolita

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

想象一下，你正试图排列一长队人，每个人手里都拿着要么是红旗（+1），要么是蓝旗（-1）。你的目标是进行排列，使得当你从不同角度观察这排队伍时，红蓝旗帜的模式不会意外地产生混淆的重叠。在科学界，这被称为**低自相关二进制序列（Low Autocorrelation Binary Sequences, LABS）**问题。这是一个著名的难题，用于测试计算机解决复杂优化问题的能力。

这篇论文介绍了一种巧妙的新方法，让量子计算机（特别是目前这种带有噪声的 NISQ 量子计算机）能够比许多传统方法更好地解决这个谜题。以下是他们方法的详细拆解：

1. 问题所在：“错误”构成的“高尔夫球场”

把寻找完美排列的过程想象成在广阔且充满迷雾的景观中寻找最低点。

景观： 大多数情况下，你走在一个有着许多小凹陷的平原上（局部极小值）。这些看起来像是谷底，但它们并不是真正的谷底。
目标： 真正的解是位于平原中心的一个微小且深邃的洞穴（全局最小值）。
难度： 由于存在如此多的“假底”，标准的计算机程序往往会陷入其中一个，然后放弃，认为自己已经找到了最佳答案，而实际上并非如此。

2. 解决方案：一个“压缩”后的地图（泡利相关编码）

通常，为了解决一个拥有 $N$ 个变量（比如 45 面旗帜）的问题，量子计算机需要 45 个量子比特（qubits）。但目前的量子计算机规模较小且脆弱，还无法处理那么多比特。

作者使用了一种被称为**泡利相关编码（Pauli Correlation Encoding, PCE）**的技巧。

类比： 想象你有一个巨大的图书馆（45 面旗帜），但你只有一个小笔记本（4 个量子比特）。你并没有记录每一本书，而是使用了一种特殊的代码。你记录的是书与书之间的关系。
原理： 他们将 45 面旗帜映射到仅有的 4 个量子比特上。这就像是将一部高清电影压缩成一个极小的文件，却又不丢失剧情。这使得他们能够利用极少的量子资源来处理巨大的问题（在他们的模拟中高达 45 面旗帜，在实际实验中甚至达到 120 面）。

3. 策略：选择正确的“问题”

为了从这 4 个量子比特中获得最多的信息，团队必须决定如何向量子计算机提问。

对易集合（Commuting Set）： 询问那些互不干扰的问题（比如同时询问天气和时间）。
非对易集合（Non-Commuting Set）： 询问那些会相互干扰的问题（比如试图同时测量一个旋转硬币的位置和速度）。
结果： 他们发现，“相互干扰”的问题（非对易问题）效果更好。这就像是摇晃一个装满弹珠的罐子来观察全貌，而不是只看其中一面。这种方法给了他们最好的结果。

4. 性能表现：更快、更聪明

他们将这种新方法与最好的经典（常规）计算机程序以及其他量子方法进行了对比测试。

竞赛： 他们测量了“求解时间”（Time-to-Solution，即找到完美答案所需的时间）。
结果： 在他们测试的规模下，这种量子方法比最好的经典“启发式”（一种被称为 Tabu Search 的智能猜测算法）更快。
规模： 虽然其他量子方法需要庞大且完美的计算机（而这类计算机尚未存在），但这种方法在规模扩展方面表现出色。这意味着随着问题规模的增大，他们的这种方法比其他方法能更持久地保持竞争力。

5. 现实世界测试：“噪声”游乐场

作者不仅进行了模拟，还实际在由 IonQ 制造的量子计算机（名为 Forte 处理器）上运行了他们的算法。

挑战： 真实的量子计算机是“有噪声的”。这就像是在飓风中试图听清一声低语。硬件本身会产生错误。
结果： 他们成功解决了拥有 120 面旗帜 的问题（这是在该特定问题上量子硬件所展示的最大规模）。
韧性： 即使面对“飓风”般的噪声，最终的答案仍然是优秀的。他们发现不需要进行数百万次的尝试（shots）就能得到一个不错的答案，几千次就足够了。然而，噪声确实使最终答案比完美的模拟结果略逊一筹。

总结

论文声称，通过使用一种巧妙的“压缩”技术（PCE）和提出正确类型的“问题”（非对易算符），他们可以在小型、不完美的量子计算机上解决极其困难的数学谜题（LABS）。对于他们测试的规模，这种方法比目前最好的经典猜测方法更快，并且足够鲁棒，可以在现有的、带有噪声的硬件上运行。他们认为，即使在拥有完美、无误差的量子计算机出现之前，这也可以成为现在解决困难问题的强大工具。

技术摘要：一种针对 LABS 问题具有竞争力的 NISQ 与低比特效率求解器

问题定义
低自相关二进制序列（Low Autocorrelation Binary Sequences, LABS）问题是一个著名的 NP-hard 组合优化挑战，在工程、通信和统计物理学领域具有广泛应用。给定一个整数 $N$ ，目标是找到一个二进制序列 $x \in \{-1, +1\}^N$ ，以最小化旁瓣能量 $E(x)$ ，其中 $E(x)$ 定义为 $\ell > 0$ 时自相关函数 $C_\ell(x)$ 的平方和。等价地，目标是最大化默里特因子（merit factor） $F(x) = N^2 / 2E(x)$ 。该问题的特征是具有“高尔夫球场”（golf course）式的优化景观，其中存在大量的局部极小值和孤立的全局极小值。虽然对于 $N \le 66$ 已知存在精确解，但对于较大的 $N$ ，寻找最优解或高质量近似解对于经典的暴力搜索方法而言已变得难以处理，甚至连最先进的启发式算法（如 Memetic Tabu Search）也面临显著的扩展性挑战。

方法论：泡利相关编码（Pauli Correlation Encoding, PCE）
作者提出了一种基于泡利相关编码（PCE）框架的高效量子变分求解器，该框架具有极高的比特效率。与每个二进制变量需要一个量子比特的标准编码不同，PCE 将 $N$ 个二进制变量压缩到 $n$ 个量子比特中，其中 $N = \text{poly}(n)$ ，具体表现为 $n \ll N$ 。

编码： 二进制变量 $x_i$ 被编码为一组 $n$ 比特泡利字符串 $\Pi = \{\Pi_i\}_{i \in [N]}$ 期望值的符号：
$x_i := \text{sgn}(\langle \Pi_i \rangle)$
其中 $\langle \Pi_i \rangle = \langle \Psi | \Pi_i | \Psi \rangle$ 。
优化： 量子态 $|\Psi\rangle$ 由参数化的砖块结构电路（brickwork circuit）生成。通过经典方式优化参数，以最小化非线性损失函数 $L$ 。为了便于基于梯度的优化，使用双曲正切函数对二进制变量进行松弛： $\tilde{x}_i = \tanh(\alpha \langle \Pi_i \rangle)$ 。损失函数包含一个正则项，以防止相关器消失。
泡利集合选择： 研究评估了两组不同的 $\Pi$ $Π$ 集合：
1. $\Pi(C)$ ：一组随机选择的、相互对易的泡利算符。
2. $\Pi(NC)$ ：旨在最大化相互非对易泡利算符数量的集合。作者假设，非对易性会导致相互不确定（mutually unbiased）的测量，从而增加所编码变量的表达能力和独立性。

核心贡献与结果

数值模拟 ( $N \le 45$ )：
- 作者使用 $n=4$ 个量子比特和 15 层的电路深度（30 个双比特门，150 个参数）对 PCE 求解器进行了模拟。
- $\Pi(NC)$ 变体始终优于对易变体。
- 扩展性分析： 求解时间（Time-to-Solution, TTS，定义为找到精确解所需的代价函数评估次数）被与 QAOA 和 Memetic Tabu Search 进行了基准测试。
  - PCE 扩展性： 对于偶数实例为 $O(1.330^N)$ ，对于奇数实例为 $O(1.326^N)$ 。
  - 对比： 该扩展性优于 QAOA 的 $O(1.46^N)$ 扩展性，并且略好于最先进的 Tabu Search 扩展性（对于偶数实例为 $O(1.34^N)$ ，对于奇数实例为 $O(1.409^N)$ ）。
- 结果表明，在测试范围内，PCE 相比于经典基准具有幂律优势。
实验演示 (IonQ Forte)：
- 作者在 IonQ 的 Forte 量子处理器上进行了原理验证演示，实例规模为 $N=120$ ，这是目前为止在量子硬件上演示的最大规模。
- 对于该实验，使用了一组特定的硬件友好型 $k$ -体相关器（ $k=2$ ），仅需三次测量设置。
- 噪声韧性： 研究发现，虽然샷噪声（shot noise）影响较小（仅需几千次采样），但硬件噪声会显著降低最终解的质量。然而，训练过程本身保持了鲁棒性，这表明误差缓解或更高的压缩率对于近期的部署至关重要。

意义与主张
本文声称 PCE 求解器为以下两个方向提供了有前景的途径：

量子启发式经典启发式算法： 即使在经典模拟的情况下，PCE 框架也为解决如 LABS 等困难问题提供了具有竞争力的或更优的扩展性，可作为一种强大的量子启发式算法。
NISQ 资源缩减： 通过将 $N$ 个变量编码到极少量的量子比特（ $n$ ）中，PCE 大幅降低了对近端设备的量子比特需求。作者指出， $n=8$ 个量子比特理论上可以处理高达 $N=66$ 的实例（已知其精确解），而 $n \le 20$ 则可以挑战能够解决最大规模实例的经典启发式算法。

作者对“量子优越性”持谨慎态度。他们承认，在经典基准测试中模拟完整的量子态矢量所带来的开销，推迟了真正体现量子运行时优势的交叉点。此外，他们指出虽然该方法表现出强大的性能，但目前仍缺乏性能保证。尽管如此，能够以适中的采样预算解决 $N=120$ 的实例，以及观察到的噪声韧性，都凸显了 PCE 作为减少实际量子算法资源需求工具的潜力。