Methods for Reducing Ancilla-Overhead in Block Encodings

量子计算机有望解决经典机器需要数千年才能完成的问题，但它们是出了名的脆弱。为了执行复杂的计算，这些机器依赖一种称为“块编码”（block encoding）的技术，该技术允许它们表示并非完全可逆的数学运算，而这对于模拟化学反应或求解微分方程等现实应用是必不可少的。可以将块编码想象成一种通过使用被称为“辅助比特”（ancillae）的额外辅助位，将一个复杂的、不可逆的计算隐藏在一个更大的、可逆的量子过程中的方法。这些辅助比特充当临时工作空间，允许量子计算机在不破坏量子力学基本定律的情况下操纵数据。然而，随着算法变得越来越复杂，它们对这些辅助比特的需求也越来越多。由于目前的量子硬件在能够容纳的量子比特数量上受到限制，这种对额外空间的需求造成了严重的瓶颈，经常迫使研究人员在运行计算与耗尽内存之间做出选择。

来自加州大学伯克利分校和匈牙利阿尔弗雷德·雷尼数学研究所的研究团队开发了两种新方法，可以大幅减少块编码所需的辅助比特数量。他们的工作从两个不同的角度解决了这个问题，第一种情况是在空间与时间之间进行权衡，第二种情况是在空间与精度之间进行权衡。第一种方法引入了一种在计算完成后“清理”工作空间的方式。在许多量子算法中，一旦使用了块编码，辅助比特就会保持在一种混乱的、纠缠的状态，无法被重复使用。研究人员设计了一种协议，可以将几乎所有的这些辅助比特相干地重置回干净的零状态，从而将它们释放出来供算法的后续部分使用。这个过程并非瞬时完成；它需要额外的计算步骤，实际上是用额外的计算时间来换取宝贵的额外空间资源。其结果是，只要计算不是完全精确但足够接近实际用途，该系统就可以仅使用单个辅助比特来执行相同的复杂操作，无论最初需要多少个辅助比特。

该研究工作的第二部分针对的是将许多块编码相乘的具体挑战，这是模拟物理系统随时间演化的常见要求。传统上，将大量的这类编码相乘需要随操作数量呈对数增长的辅助比特数量，这一需求很快就会超出可用硬件的承受能力。研究人员证明，对于精确、完美的乘法，这种对数级的需求是一个无法逾越的硬性限制。然而，他们表明，如果愿意接受极小的、受控的误差，这个限制是可以被打破的。他们引入了一种新的装置（gadget），可以利用恒定且少量的辅助比特执行这些乘法，而无论有多少个操作被链接在一起。这种压缩所引入的误差极其微小，并且随着辅助比特数量的轻微增加而迅速减小。这种方法对于那些单个步骤本身已经非常接近于“不做任何事”的模拟特别有效，这在物理模拟中是一个常见场景，即使用微小的时间步长来追踪渐进的变化。

为了确保这些压缩后的计算仍然有用，研究人员还展示了如何使用一种称为“无知振幅放大”（oblivious amplitude amplification）的技术。这种方法就像一个过滤器，可以提高计算成功的概率，有效地将一个可能经常失败的过程转变为几乎每次都成功的过程，即使是在使用压缩后的近似方法时也是如此。这些发现表明，通过仔细管理精度与资源使用之间的权衡，量子算法可以变得更加高效。这不仅仅是一个理论练习；这些方法直接适用于模拟哈密顿动力学（描述能量如何在系统中移动）以及求解量子微分方程（这对于模拟从流体力学到化学反应的一切事物都至关重要）。通过减少辅助比特的开销，这些技术可以让当前的及近未来的量子计算机能够处理那些此前因内存不足而无法触及的问题。