Quantum Circuits for the Metropolis-Hastings Algorithm

本文提出了一种用于 Metropolis-Hastings 算法的资源高效 Szegedy 量子行走构造，该方法通过直接遵循经典提议 - 接受逻辑，避免了可逆计算所需的高昂量子比特开销，从而为马尔可夫链蒙特卡洛模拟实现了实用的端到端二次加速。

要点

想象一下，你正试图在一个摆满家具的广阔黑暗房间里找到最舒适的位置。你无法一眼看清整个房间，因此你采用了一种策略：随机迈出一步，检查新位置是否感觉更好，然后决定是留在那里还是回到原来的位置。这就是梅特罗波利斯 - 黑斯廷斯（Metropolis-Hastings, MH）算法的精髓，这是一种用于探索复杂概率景观的经典计算机方法。它就像一名在雾气缭绕的山脉中漫步的徒步者，根据一张告知其前往新山峰概率的地图来迈步。

几十年来，科学家们一直希望量子计算机能让这名徒步者移动得更快——具体来说，在找到最佳位置所需的“步数”上快两倍。这种加速源于一种名为**塞格迪量子化（Szegedy's quantization）**的数学技巧，它将徒步者的随机游走转化为“量子游走”，使徒步者能够同时探索多条路径。

然而，现有的量子方案存在一个大问题。为了让量子徒步者运作，计算机必须在徒步者行走的同时进行大量的复杂数学运算。这就像要求徒步者在迈出第一步之前，计算出每一个可能未来步骤的确切概率。要在量子计算机上实现这一点，你需要大量的额外“辅助”比特（量子比特）来存储这些计算。在当前量子计算机时代，我们可用的辅助比特非常有限，因此这种方法过于沉重，难以承载。

论文解决方案：“记忆”技巧

本文作者 Baptiste Claudon 及其团队发现了一种巧妙的方法来绕过繁重的数学运算。他们稍微改变了游戏规则，而不是试图计算每一次移动的概率。

将标准的 MH 算法想象成这样一个游戏：你提议一次移动，如果被拒绝，你就简单地忘记曾有过这个念头并原地不动。问题在于，“忘记”在量子世界中是混乱的；你无法轻易地逆转“忘记”这一动作。

作者们的解决方案是赋予徒步者记忆。

• 设置：量子计算机不再仅仅追踪徒步者的当前位置，而是追踪一对位置：徒步者现在所在的位置，以及他们刚刚来自的位置（或他们刚刚尝试移动到的位置）。
• 逻辑：
  • 如果新位置被接受，徒步者移向那里，记忆更新以显示旧位置。
  • 如果新位置被拒绝，徒步者留在原地，但记忆保留被拒绝的位置。
• 魔力：通过在记忆中保留被拒绝的位置，该过程永远不会真正“忘记”任何事。每一步都变得可逆（你总是可以回到之前的状态）。这种可逆性是关键，它使得量子计算机能够在无需实时进行复杂算术计算的情况下运行游走。

结果：更轻量、更快速的量子游走

由于不需要实时计算复杂的概率，他们新的量子电路极其轻量。

• 旧方法：需要随着问题复杂度的增加而增长的辅助比特（量子比特）数量。这就像每走一英里就需要一个新的背包。
• 新方法：无论问题多么复杂，都使用固定且少量的辅助比特（仅需三个额外量子比特）。这就像拥有一个适合任何旅程的小型高效背包。

他们的证明

作者们不仅构建了一个更轻量的电路，还证明了它仍能像理论最佳那样快速运行。

1. 速度：他们表明，他们的量子游走仍然实现了承诺的“二次加速”。如果经典徒步者需要 100 步来找到最佳位置，他们的量子徒步者仅需约 10 步。
2. 准确性：他们证明了“记忆”技巧不会扭曲结果。徒步者最终探索房间的比例仍然是正确的，找到正确位置的方式与经典徒步者一样，只是速度快得多。
3. 现实世界测试：他们在一种称为**梅特罗波利斯调整朗之万算法（Metropolis-Adjusted Langevin Algorithm, MALA）**的特定类型问题上进行了测试，该算法广泛应用于分子动力学（模拟分子如何运动）和机器学习。他们成功地在拥有 27 个量子比特的量子计算机上模拟了这一过程，证实了“量子差距”（速度的衡量指标）确实如理论预测那样被平方了。

总结

这篇论文提出了一种在量子计算机上运行梅特罗波利斯 - 黑斯廷斯算法的新的高效方法。通过给算法一个简单的“记忆”来记录被拒绝的移动，作者们消除了通常拖累量子模拟的繁重复杂计算的需求。这使得在现有的有限量子计算机上运行这些强大的采样算法成为可能，为更快的药物发现模拟和更优的机器学习模型铺平了道路，而无需大量的额外硬件。

技术摘要

技术摘要：用于 Metropolis-Hastings 算法的量子电路

问题陈述
马尔可夫链蒙特卡洛（MCMC）方法，特别是 Metropolis-Hastings（MH）算法，对于从分子动力学到机器学习等各个领域的概率分布采样至关重要。这些算法的效率由混合时间决定，而混合时间与底层马尔可夫链的谱隙成反比。Szegedy 的量化框架通过将可逆马尔可夫链映射到具有二次更大谱隙的量子行走，提供了理论上的二次加速。

然而，为 MH 算法实现 Szegedy 量子行走存在一个重大的实际障碍。通用实现需要相干地计算转移概率（具体而言，是代表拒绝概率的马尔可夫核的对角元素）。这需要在量子比特寄存器上进行复杂的可逆算术运算，导致量子比特开销随计算复杂度而增加。在近期容错量子计算的背景下，由于逻辑量子比特稀缺，这种开销是难以承受的。此外，现有方法通常依赖于 MH 算法本身并不具备的特定对称性或群结构。

方法论
作者提出了一种 MH 算法量子步算子的新构造方法，完全避免了相干算术运算。其方法论的核心在于对扩展状态空间上的 MH 过程进行重新表述。

1. 边空间上的对偶核：作者不再在状态空间 $S$ 上操作，而是在有向边空间 $S^2$（状态对 $(x, y)$）上定义了一个对偶马尔可夫核。在此框架中，状态 $(x, y)$ 代表一个“尾”$x$ 和一个“头”$y$。

   • 提议：提议步骤 $T$ 在保持尾 $x$ 固定的同时生成一个新的头 $z$，实现 $(x, y) \to (x, z)$ 的转换。
   • 接受/拒绝：接受步骤 $A$ 作用于边。如果接受，边翻转为 $(z, x)$；如果拒绝，边保持为 $(x, z)$。
   • 可逆性：关键在于，这种表述使得拒绝步骤变得可逆（通过将拒绝的提议存储在头中），从而允许整个过程通过幺正动力学进行编码，而无需“样本遗忘”或不可逆操作。

2. 基于预言机的量子步算子：该构造依赖于两个量子预言机：

   • $O_T$：一个提议预言机，用于制备提议移动的叠加态。
   • $O_A$：一个接受预言机，根据接受矩阵 $A$ 对边执行概率翻转。
     作者证明，对偶核 $P = TA$的量子步算子及其时间反演$P^\star = AT$可以通过对$O_T$和$O_A$ 进行常数次调用构建而成。

3. 厄米化与量子化：由于对偶核 $P$ 通常不可逆，作者采用了一种厄米化程序。他们将 $P$ 和 $P^\star$ 的编码结合到一个可逆扩张判别式的对称投影幺正编码（SPUE）中。这使得量子化行走谱定理的应用成为可能。

4. 采样过程：生成的量子化行走算子 $W$ 在编码范围内拥有一个唯一的 1-特征向量，该向量对应于原始 MH 链的平稳分布。通过使用量子相位估计投影到该特征向量，随后对预言机进行反计算，即可从目标分布 $\pi$ 中提取样本。

主要贡献

• 无需算术的可逆逻辑：本文提出了一种 MH 核的 Szegedy 量化方法，无需相干计算转移概率或拒绝率。它仅依赖于提议和接受预言机。
• 恒定的量子比特开销：该构造需要固定数量的辅助量子比特（主要构造为 3 个，替代的受控 SWAP 方法为 1 个），无论接受概率计算的复杂度如何。这与之前的方法形成对比，在那些方法中，辅助量子比特的数量随算术运算的精度或复杂度而增加。
• 保留二次加速：作者证明，所得量子化行走的谱隙属于 $\Omega(\sqrt{\delta})$，其中 $\delta$ 是经典 MH 链的谱隙，从而保留了理论上的二次加速。
• 对偶核表述：在边空间 $S^2$ 上引入对偶核，提供了一种机制，使 MH 中不可逆的拒绝步骤变为可逆，从而促进了幺正编码。

结果

• 理论界限：作者证明了所构造的行走算子的角间隙为 $\Omega(\sqrt{\delta})$。他们确立了可逆扩张 $PP^\star$ 的谱隙至少为 $\delta/2$（对于一般接受矩阵）或等于 $\delta$（对于 Glauber 选择），从而确保了二次放大的有效性。
• 资源效率：论文中的表 I 比较了逻辑量子比特的需求。所提出的方法对于主要构造需要 $4m + 3$ 个量子比特（其中 $m = \lceil \log_2 n \rceil$ 是状态空间的位数），对于替代方法则需要 $2m + 1$ 个。这显著低于之前的方法（例如 Childs 等人需要 $5pd + du$ 个量子比特）。
• 数值验证：作者提供了开源实现，并对应用于双势阱的 Metropolis-调整朗之万算法（MALA）进行了数值模拟。使用 27 个量子比特（每个状态寄存器 6 位），他们验证了所实现的行走算子表现出比经典过程大二次方的谱隙，与理论界限相符。

意义
本文声称，其构造是唯一一种避免了矩阵元素或转移概率相干计算的 MH 核 Szegedy 量化方法。通过最小化可逆算术所需的量子比特数量（将其减少为常数），这项工作表明 MH 量子行走可以在没有不可承受算法开销的情况下实现。这使得 MCMC 模拟的二次加速对于近期容错量子计算机更加可行，特别是对于分子动力学和机器学习中的应用，其中接受步骤较为复杂。作者将此定位为迈向马尔可夫链蒙特卡洛算法全面二次量子加速的渐进步骤，证明了小实例可以进行数值分析，且该方法可扩展至具有相对于原子数量呈线性量子比特扩展的实际系统。