⚛️ quantum physics

The Practicality of Randomized Quantum Linear Systems Solvers

本文表明，尽管随机量子线性系统求解器比块编码方法具有更浅的电路，但由于非克利福德门（non-Clifford gate）的需求过高，对于早期的容错设备而言在实际中仍然是不可行的，即便随机泰勒展开核比乘积公式（product formulas）要高效得多。

原作者： Siddharth Hariprakash, Roel Van Beeumen, Katherine Klymko, Daan Camps

发布于 2026-07-29

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Siddharth Hariprakash, Roel Van Beeumen, Katherine Klymko, Daan Camps

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

想象一下，你正试图解开一个巨大的、纠缠不清的数学结，这些问题规模宏大，以至于任何常规计算机都无法在合理的时间内将其理顺。这就是量子计算的世界——在这个领域，科学家们构建机器，利用微小粒子的奇特规则来解决这些不可能的谜题。他们想要解决的最著名的谜题类型之一被称为“线性系统”，这本质上是一个巨大的数字网格，你需要从中找到隐藏在其中的特定答案。为了破解这些代码，研究人员经常使用一种叫做“哈密顿量模拟”（Hamiltonian simulation）的技术，这就像是运行一部关于量子系统随时间变化的电影，以观察会发生什么。长期以来，实现这一目标的最佳方法需要构建极其深层且复杂的电路，就像试图用叠叠乐积木搭建一座摩天大楼而不让它倒塌一样。但最近，一个新想法出现了：如果我们不一次性盖好整座摩天大楼呢？如果我们只是对建筑进行许多随机、快速的快照，然后将它们平均化，并希望得到的图像足够清晰呢？这种“随机化”的方法承诺会更加简单，更容易在早期的量子计算机上构建。

然而，由劳伦斯伯克利国家实验室和 BlueQubit Inc. 的 Siddharth Hariprakash 及其团队开展的一项新研究，决定对这个充满前景的想法进行终极测试。他们不仅仅是在研究理论；他们进行了大量的数学运算，以确定实现这一目标究竟需要多少资源——比如时间、计算能力。这就像是在检查一辆被宣称可以开到月球的汽车的油表。研究人员绘制了一张详细的旅程地图，计算了实现清晰答案所需的每一个步骤。他们的发现是一个现实的警示：虽然随机方法确实更易于构建，但事实证明它极其低效。他们发现，即使对于一个微小的、简单的题目（一个 4x4 的数字网格），该方法也需要惊人的操作量——大约 $10^{15}$ 个非 Clifford 门才能得到一个好的答案。为了让你有个直观的概念，这个数字如此巨大，以至于在当前或不久的将来几乎是不可能实现的。

该论文对比了两种不同的获取这些量子系统“快照”的方法。一种方法是遵循严格的食谱（称为乘积公式，Product Formula），另一种则是通过掷骰子来决定下一步行动（称为随机泰勒展开，Random Taylor Expansion）。研究人员发现，“掷骰子”的方法实际上是这两个糟糕选项中较好的那一个，它比严格的食谱方法所需的资源少约十倍。但关键在于，即使是较好的方法仍然非常昂贵，以至于在处理现实世界的问题时并不实用。这项研究表明，虽然这些随机方案很巧妙且在理论上是成立的，但它们所要求的巨大工作量意味着它们可能并不是我们期望在早期量子计算时代获得的“灵丹妙药”。作者提供了一个清晰的、非渐近性的（这意味着他们不仅仅是在做最后的猜测，而是计算出了精确的数字）证明，表明对于这些特定问题，成本实在太高了。

随机求解器的故事

让我们深入了解作者实际做了什么。他们正在研究一种特定类型的量子算法，用于求解线性方程组。想象你有一个巨大的、复杂的机器（矩阵），你想知道当你输入特定的输入时会发生什么。目标是找到输出，但由于这台机器过于复杂，你无法仅仅运行一次。

研究人员专注于一种“随机化”的方法。与其完美地运行机器，这种方法尝试通过进行多次随机采样来近似答案。这就像是试图猜测体育场里所有人的平均身高。你可以测量每一个人（这很难且耗时很长），或者你可以随机询问几个人，猜测他们的高度，然后取这些猜测的平均值。人们曾希望通过进行足够的随机猜测，无需过于复杂的设置就能得到正确答案。

论文将这个过程分解为三个主要步骤，作者对这些步骤进行了极度精确的分析：

食谱（傅里叶级数）： 首先，他们必须弄清楚如何将数学问题转化为一系列用于采样的随机“时间”。他们使用了一种叫做傅里叶级数的数学技巧来近似矩阵的逆。可以把这想象成创建一个食谱，告诉你在哪些随机时刻进行观察。作者精确计算了需要多少种“配料”（级数项）以及测量需要多么精确才能获得良好的近似。他们发现，即使对于小规模问题，也需要大量的这些配料。
快照（哈密顿量模拟）： 接下来，对于每个选定的随机时间，量子计算机必须模拟该系统。这是最困难的部分。作者研究了两种进行此类模拟的方法：
- 乘积公式 (PF)： 这就像是将一段漫长的旅程分解成小的固定步骤。你走一小段，停一下，再走一小段，以此类推。这是一种非常结构化的移动方式。
- 随机泰勒展开 (RTE)： 这更加混乱。它就像是通过掷骰子来决定走多少步以及往哪个方向走。它引入了第二层随机性。
平均值（采样）： 最后，你从这些快照的结果中提取数据并进行平均，从而得到最终答案。你进行的快照越多，就越接近真实答案。

大揭秘：成本太高了

论文最重要的部分是对“成本”的计算。在量子计算领域，成本是以“门”（gates）来衡量的，即计算机执行的基本操作。作者精确计算了在达到一定准确度的情况下，解决一个问题需要多少个门。

他们发现，成本的增长速度惊人。即使对于一个微小的矩阵（一个条件数/难度系数为 100 的 4x4 矩阵），该方法也需要大约 $10^{15}$ （即 1 后面跟着 15 个零）个非 Clifford 门才能收敛。这个数字远远超出了我们今天甚至在不久的将来能够制造出的任何量子计算机的处理能力。这就像是用牙签去建造一座横跨大洋的桥梁；数学证明在理论上是可能的，但材料并不具备。

作者还对比了两种模拟方法（PF 和 RTE）。他们发现，随机泰勒展开 (RTE) 方法明显优于乘积公式 (PF)。具体来说，RTE 需要大约**一个数量级（10 倍）**更少的门即可达到相同的准确度。然而，即便有了这 10 倍的改进，总门数仍然高得离谱。论文明确指出，这两种方法对于当前的或近期的硬件来说都不具备实用性。

这对未来意味着什么

这篇论文并不仅仅是在说“这很难”；它为我们提供了一张关于“为什么难”的清晰地图。主要的瓶颈在于问题的“条件数”（condition number）。随着问题变得越来越难（条件数上升），所需的门数量会以四次方增长。这意味着，如果你将问题的难度翻倍，你就需要 16 倍的资源。这种缩放规律使得随机化方法在处理科学家真正想要解决的问题时，成本变得异常高昂。

作者非常谨慎地表示，他们的结果是基于显式计算和模拟，而非仅仅是猜测。他们在随机矩阵上测试了他们的数学模型，发现其预测与模拟的现实情况完全吻合。这让我们对他们的结论充满信心：虽然随机化量子算法的想法很巧妙，并且降低了电路的复杂度，但所需的大量采样量使得它在近期解决线性系统问题时并不切实际。

最后，这篇论文起到了至关重要的现实检验作用。它将一个充满前景、备受关注的想法与物理学和工程学的硬性数字进行了对比。结果显示，虽然随机化方法是一项引人入胜的理论研究，但它并不是早期量子计算机的“银弹”。作者建议，如果我们想要取得进展，可能需要寻找不同的拆解问题的方法，例如先利用经典计算机来简化问题，或者寻找不需要如此大量随机样本的新数学技巧。但就目前而言，通过简单的随机量子捷径来解决这些复杂线性系统的梦想，依然只是一个梦想，等待着硬件或算法设计的突破来实现。

技术摘要：随机量子线性系统求解器的实用性

问题陈述
本研究旨在解决量子线性系统（QLS）问题：即在给定状态制备算子 $|\psi\rangle$ 和 $|\phi\rangle$ 的情况下，估计形式为 $\langle \phi | A^{-1} | \psi \rangle$ 的标量属性，其中 $A$ 是一个 $N \times N$ 的厄米算符。虽然现有的量子线性代数方法通常依赖于块编码（block-encoding）和量子奇异值变换（QSVT），但这些方法通常需要深层的、相干的电路，这对于近期的容错硬件而言具有挑战性。为了缓解这一问题，研究者提出了随机化算法，将该问题重新表述为结合经典采样与浅层哈密顿模拟子程序的形式。然而，该领域之前的研究主要仅提供了渐近复杂度界限，使得显式的、端到端的资源需求（包括经典预处理和采样开销）尚不明确。

方法论
作者对一种结合了傅里叶级数逼近与哈密顿模拟的随机量子算法进行了详细的非渐近分析。其工作流程由三个主要阶段组成：

经典预处理（傅里叶级数构建）：
反函数 $f(x) = x^{-1}$ 在定义域 $D_\kappa$ （排除零点处的奇异性）上通过积分表示进行逼近。作者采用了混合离散化方案：
- 截断（Truncation）： 将无限积分范围截断为有限边界 $(y_{max}, z_{max})$ 。
- 离散化（Discretization）： 使用高斯-勒让德（Gauss-Legendre）规则处理振荡的 $y$ 积分，并使用梯形法则处理快速衰减的 $z$ 积分。由此产生一个具有系数 $\alpha_s$ 和时间 $t_s$ 的傅里叶级数 $F(A) \approx A^{-1}$ 。
- 采样（Sampling）： 将傅里叶系数归一化以形成概率分布，从而允许算法在经典端采样特定的傅里叶时间 $t_j$ 。
量子处理（哈密顿模拟）：
对于每个采样的时刻 $t_j$ ，算法使用 Hadamard 测试来估计 $\langle \phi | e^{-iAt_j} | \psi \rangle$ 。作者分析了实现受控时间演化算子 $e^{-iAt_j}$ 的两种不同子程序：
- 乘积公式（Product Formula, PF）： 使用二阶 Trotter-Suzuki 分解来逼近演化过程。
- 随机泰勒展开（Random Taylor Expansion, RTE）： 使用基于截断泰勒级数的线性算子组合（LCU）方法，引入了第二层随机化，其中单个幺正算子被进行采样。
经典后处理：
Hadamard 测试的结果通过 $N_S$ 次采样进行平均，以收敛到目标标量值。总误差被分解为傅里叶逼近误差、采样误差和模拟偏差。

核心贡献
本文做出了四项主要贡献，使其区别于以往的渐近性处理：

显式非渐近误差界限： 作者为实现目标误差 $\epsilon$ 所需的所有算法参数（截断限制、离散节点、采样计数）推导出了严格的、非渐近的界限。这包括傅里叶项数量（ $J, K$ ）和归一化因子（ $N_y, N_z$ ）的显式公式。
两种核函数的资源估算： 该工作为两种子程序——乘积公式（PF）和随机泰勒展开（RTE）提供了详细的门计数公式。它分析了高概率收敛（通过 Hoeffding 不等式）和均方根误差（RMSE）收敛。
权衡分析： 研究明确表征了样本数（ $N_S$ ）与单样本门深度（ $N_{CP}$ ）之间的权衡。它展示了通过调整参数（例如 Trotter 阶数 $r$ 或 RTE 段数）如何转移采样复杂度与电路深度之间的负担。
数值验证： 理论界限在小规模随机厄米矩阵（ $N=4$ 和 $N=16$ ）上得到了经验验证，确认了误差界限和收敛率的有效性。

结果

可扩展性： 两种子程序的总非 Clifford 门复杂度缩放均为 $\tilde{O}(\kappa^4 / \epsilon^2)$ （其中 $\kappa$ 是条件数）。这种 $\kappa^4$ 的缩放是由样本复杂度 $\tilde{O}(\kappa^2)$ 与单样本模拟成本 $\tilde{O}(\kappa^2)$ 的乘积产生的。
实用性： 分析表明，即使对于中等规模的问题，资源需求也是极其高昂的。对于一个 $\kappa = 100$ 且目标误差 $\epsilon \sim 10^{-3}$ 的 $4 \times 4$ 实例，算法需要大约 $10^{15}$ 个受控 Pauli 旋转才能收敛。
PF 与 RTE 对比：
- RTE 效率： 研究发现 RTE 子程序在总门预算方面比 PF 更高效。虽然由于较大的方差预因子（缩放为 $e^{2/c_{RTE}}$ ），RTE 需要多出约一个数量级的样本，但其单样本门成本显著更低（在测试实例中低了约 85 倍），因为它避免了 PF Trotter 步骤中对 Pauli 稀疏度 $L$ 的线性依赖。
- 最优配置： 最优 RTE 配置（当 $c_{RTE} \approx 2$ 时）所产生的总门预算仅为 PF 所需预算的约 6%，尽管两者对于当前硬件而言仍不切实际。
维度无关性： 傅里叶逼近误差界限被证明与希尔伯特空间维度 $N$ 无关，仅取决于条件数和 Pauli 权重。

意义与主张
本文声称通过提供第一个针对随机化 QLS 求解器的显式、端到端资源估算，弥补了渐近性提议与硬件实现之间的鸿沟。作者得出结论，虽然随机化方案具有结构性优势（例如将量子比特宽度减少至 $\log(N)+1$ 以及降低单次采样的电路深度），但此类方案的实用性受到了质疑。

$\kappa^4$ 的缩放和巨大的预因子使得这些方法在处理具有科学意义的问题时，即便是在近期或早期容错设备上也是不可行的。作者指出，虽然 RTE 相对于 PF 更加高效，但绝对门预算仍然高得令人生畏。这项工作表明，未来的改进需要寻找具有更弱 $\kappa$ 相关性的替代积分表示、经典预处理或更低方差的采样分布，但就目前而言，显式界限表明这些随机化方法尚不足以成为求解线性系统的相干块编码方法的有效替代方案。

随机求解器的故事

大揭秘：成本太高了

这对未来意味着什么

技术摘要：随机量子线性系统求解器的实用性

类似论文