Designing more efficient quantum circuits with Claude
打开互动全文版(逐段中英对照 + 针对本篇提问)→量子计算机需要精心设计的电路,才能在有限且易受噪声影响的硬件上运行有用的算法,而减少量子比特和门数量对实际应用至关重要。本文报告称,仅向 Claude 提供来自化学、优化、物理模拟和数论的八个计算原语的纯语言规格说明,Claude 便与一个自动评估器形成闭环协作——该评估器检查正确性并按量子比特-门成本为设计打分。Claude 在很大程度上自主发现了新颖的电路设计,其使用的量子比特和门数量均少于此前发表的最佳算法,部分情况下甚至少一个数量级以上;这些改进源于新的结构与数学洞见,而非微调。示例包括:针对椭圆曲线点加法的模逆运算提出了一种新方法,通过从数字本身解码分支信息来避免存储该信息;以及一项重新设计,使某领先优化算法中成本最高的一步便宜约 12 倍。作者总结道,AI 如今已能帮助重新设计量子电路,有望使实用的量子应用更早到来。
Quantum computers require carefully designed circuits to run useful algorithms on limited, noise-prone hardware, and reducing qubit and gate counts is essential for practical applications. This article reports that Claude, given only plain-language specifications for eight computational primitives from chemistry, optimization, physics simulation, and number theory, worked in a closed loop with an automated evaluator that checked correctness and scored designs on qubit-gate cost. Largely on its own, Claude discovered novel circuit designs that used both fewer qubits and fewer gates than the best previously published algorithms, in some cases by an order of magnitude or more, with improvements arising from new structural and mathematical insights rather than fine-tuning. Examples include a new approach to modular inversion for elliptic-curve point addition, which avoids storing branch information by decoding it from the numbers themselves, and a redesign making the costliest step of a leading optimization algorithm about 12x cheaper. The authors conclude that AI can now help redesign quantum circuits, potentially bringing practical quantum applications closer.
量子计算机需要精心设计的电路,才能在有限的硬件上运行有用的算法。我们向 Claude 提供了八个此类电路的平实语言规范,这些电路来自化学、优化、物理模拟和数论领域,并提供了一个自动评估器来检查和评分每个设计。Claude 在很大程度上独立工作,找到了比已发表的最佳电路更优的设计,在某些情况下提升了一个数量级甚至更多。这种改进大幅减少了有用应用所需的量子资源,因此实用的量子计算机可能比之前预期的更早到来。
Quantum computers will need carefully designed circuits to run useful algorithms on limited hardware. We gave Claude plain-language specifications for eight such circuits, drawn from chemistry, optimization, physics simulation, and number theory, along with an automated evaluator that checks and scores each design. Working largely on its own, Claude found designs that improve on the best published circuits, in some cases by an order of magnitude or more. Such improvements substantially reduce the quantum resources that useful applications require, so practical quantum computers could arrive sooner than previously anticipated.
这项工作由 Andi Gu 领导,是 Anthropic 的 STEM 研究员计划的一部分,由 Anthropic 的量子物理学家 Alek Kemeny 指导,并与 Susanne Yelin(哈佛大学)和 Mikhail Lukin(哈佛大学和 QuEra Computing)合作完成。请在 arXiv 上阅读完整论文。
This work was led by Andi Gu as part of Anthropic’s STEM Fellows Program, with mentorship from Alek Kemeny, a quantum physicist at Anthropic, in collaboration with Susanne Yelin (Harvard University) and Mikhail Lukin (Harvard University and QuEra Computing). Read the full paper on arXiv.
与经典计算机将信息存储在值为 0 或 1 的比特中不同,量子计算机将信息存储在 _量子比特_ 中,量子比特可以由单个原子、超导电路或光子构建。这些量子比特利用 _叠加_ 等量子现象——叠加允许量子系统同时处于多个状态的组合——以可能使化学、材料科学和数论等领域的某些问题变得可处理的方式处理信息,即使这些问题对传统计算机来说过于困难。
Unlike classical computers, which store information in bits whose value is either 0 or 1, quantum computers store information in _qubits,_ which can be built from single atoms, superconducting circuits, or particles of light. These qubits make use of quantum phenomena such as _superposition_—which allows a quantum system to exist in a combination of states at once—in order to process information in ways that could make certain problems in fields like chemistry, materials science, and number theory tractable, even when they are too hard for traditional computers.
迄今为止,该领域已构建的量子计算机只有数百到数千个量子比特——太少,无法运行许多承诺比经典计算机具有实际优势的算法。而且这些量子比特对环境噪声高度敏感,例如热、振动甚至宇宙射线。微小的扰动就能推动量子比特的状态,这些微小的错误会累积起来,直到计算机给出错误答案。
The quantum computers the field has built to date only have hundreds to thousands of qubits—too few to run many of the algorithms that promise practical advantages over classical computers. And these qubits are highly sensitive to environmental noise, such as heat, vibration, and even cosmic rays. A tiny disturbance can nudge a qubit’s state, and these small errors pile up until the computer gives the wrong answer.
鉴于量子比特和计算时间都是稀缺资源,研究人员一直在重新设计量子算法,以使用更少的量子比特并在更短的时间内完成计算。一个说明性的例子是模拟 FeMoco,这是固氮酶核心的铁硫簇,固氮酶是细菌用来将空气中的氮转化为氨的酶。了解其工作原理可以帮助科学家设计更好的工业催化剂——制造商用来加速化学反应的物质。
Given that both qubits and computing time are scarce resources, researchers have been working to redesign quantum algorithms to use fewer qubits and complete computations in less time. An illustrative example is simulating FeMoco, the iron–sulfur cluster at the heart of nitrogenase, the enzyme that bacteria use to turn nitrogen from the air into ammonia. Understanding how it works could help scientists design better industrial catalysts—the substances manufacturers use to speed up chemical reactions.
2017 年,研究人员估计,一台量子计算机需要大约 50 万亿个 Toffoli 门来计算 FeMoco 的基态能量——即其最稳定构型的能量,化学家需要这一能量来预测 FeMoco 的反应方式。(与普通计算机类似,量子计算机通过对量子比特应用一长串称为门的简单操作来工作。Toffoli 门是运行成本最高的门之一,因此计算 Toffoli 门的数量是估算计算所需时间的标准方法。)
In 2017, researchers estimated that a quantum computer would need about 50 trillion Toffoli gates to compute FeMoco’s ground-state energy—the energy of its most stable configuration, which chemists need in order to predict how FeMoco reacts. (Similar to ordinary computers, quantum computers work by applying a long sequence of simple operations, called gates, to their qubits. The Toffoli gate is one of the most expensive gates to run, so counting Toffoli gates is a standard way to estimate how long a computation will take.)
通过一系列算法进展,估计的门数已降至约 3.4 亿——减少了约 15 万倍,相当于在一台拥有约 300 万个物理量子比特的未来机器上计算几个小时。1
Through a series of algorithmic advances, the estimated number of gates has come down to about 340 million—a roughly 150,000-fold reduction, corresponding to a few hours of computation on a future machine with about three million physical qubits.1
这些减少主要来自重新设计执行计算的电路,而非来自制造更好的硬件。Claude 已被证明特别擅长优化经典算法,因此我们想看看,如果只给 Claude 每个电路必须计算的内容的平实语言描述,它是否也能对量子算法做同样的事情。
These reductions largely came from redesigning the circuits that carry out the computation, rather than from making better hardware. Claude has proven particularly adept at optimizing classical algorithms, so we wanted to see whether it could do the same for quantum algorithms if it were given only a plain-language description of what each circuit must compute.
Claude 异常适合这项任务,原因有几个。首先,量子算法被实现为量子_电路_。这些电路由门序列组成,如上文提到的 Toffoli 门。重要的是,这些电路可以用代码描述,因此我们可以利用 Claude 的编码能力,将电路设计作为普通程序来编写、运行和修改。其次,我们最感兴趣优化的那类(相当常见的)量子算法可以高效地进行正确性测试,因为每个输入都给出一个确定的输出,普通计算机可以检查。这意味着我们可以让一个外部评估程序验证 Claude 的提议。最后,我们可以给 Claude 一个清晰、客观的分数来改进:使用的量子比特数乘以门数,这可以作为电路运行所需时间的代理指标。
Claude is unusually well suited to this task, for several reasons. First, quantum algorithms are implemented as quantum _circuits_. These are composed of sequences of gates, like the Toffoli gates mentioned above. Importantly, these circuits can be described in code, so we can make use of Claude’s coding capabilities to write, run, and revise circuit designs as ordinary programs. Second, the (fairly common) class of quantum algorithms we were most interested in optimizing can be tested efficiently for correctness, as each input gives one definite output that an ordinary computer can check. This means we could have an external evaluator program validate Claude’s proposals. Finally, we can give Claude a clear, objective score to improve: the number of qubits used, multiplied by the number of gates, which serves as a proxy for how long the circuit would take to run.
我们发现 Claude Mythos 5 可以成功地在闭环中工作:提出电路设计,从评估程序接收反馈和分数,并利用该反馈改进下一次尝试,轮次之间无需人工输入(见图 1)。在八个计算原语——即构建更大量子算法的基本例程——上,涵盖化学、优化、量子模拟、数论和数值计算,Claude 发现了新颖的设计,这些设计使用的量子比特和门数均少于之前发表的最佳算法(图 2)。
We found that Claude Mythos 5 could successfully work in a closed loop, proposing a circuit design, receiving feedback and a score from the evaluator program, and using that feedback to improve its next attempt, with no human input between rounds (see Figure 1). Across eight computational primitives—the basic routines that larger quantum algorithms are built from—for chemistry, optimization, quantum simulation, number theory, and numerical computing, Claude discovered novel designs that used both fewer qubits and fewer gates than the best previously published algorithms (Figure 2).
在每一个案例中,改进都源于发现了关于问题的新结构与数学洞见,而非对现有设计进行微调。例如,在为模拟硫化铁分子编译量子线路时,Claude 注意到该分子的对称性和重复结构意味着某些结果可以只计算一次并重复使用,而不必对系统的每个部分重新计算。在其他案例中,它发现现有线路包含了一些代价高昂的组件,而这些组件仅用于处理极其罕见的输入,于是它重新设计了线路,去掉了这些组件。
In each case, the improvement resulted from uncovering new structural and mathematical insights about the problem, rather than from fine-tuning existing designs. For example, when compiling a circuit for simulating an iron-sulfide molecule, Claude noticed that the molecule's symmetries and repeating structure meant that some results could be calculated once and reused, rather than recomputed for every part of the system. In other cases, it found that existing circuits included costly components that were needed to handle only extremely rare inputs, and it redesigned them without those components.
下面我们介绍 Claude 的两项发现。第一项是一种执行模逆运算的新方法,模逆是椭圆曲线计算中代价最高的一步算术运算。第二项使一种领先的量子优化算法中代价最高的一步便宜了约 12 倍。
Below, we describe two of Claude's discoveries. The first is a new way to perform modular inversion, a bit of arithmetic that is the most expensive step in elliptic-curve calculations. The second makes the costliest step of a leading quantum optimization algorithm about 12x cheaper.
这些结果表明,AI 如今可以帮助重新设计量子线路,而这是让量子算法运行得更快、更简便的关键一步。更快的线路设计可以让量子计算机本应解决的问题——从设计新药物和更好的电池,到寻找更清洁的化肥制造方法——更早地变得触手可及。
These results suggest that AI can now help redesign quantum circuits, a key step in making quantum algorithms faster and easier to run. Faster circuit design could bring the problems quantum computers are meant to solve—from designing new medicines and better batteries to finding cleaner ways of making fertilizer—within reach sooner.
**闭环量子线路优化。** Claude 用 Python 设计新的实现,随后将其发送给程序化评估器。评估器检查所提出的实现是否正确,然后根据其所需的量子比特数和门数进行评分。这些信息随后被发送回 Claude,Claude 利用它来改进自己的实现。图中展示的代码和数值仅作示意。
Closed-loop quantum circuit optimization. Claude designs new implementations in Python, which are then sent to a programmatic evaluator. The evaluator checks whether the proposed implementation is correct, then scores it on the number of qubits and gates it requires. This information is then sent to Claude, which uses it to improve its implementation. The code and values shown are illustrative.
设计量子电路涉及两个普通编程没有的约束。第一个是量子电路不能像普通程序那样做出“如果-那么”决策。普通程序可以检查一个值,然后只运行两段代码中的一段。但量子计算机同时运行在许多输入的叠加态上,其中一些输入会运行第一段代码,而另一些会运行第二段代码,因此电路在每次运行时都必须包含这两段代码的操作。
Designing a quantum circuit involves two constraints that ordinary programming doesn’t have. The first is that a quantum circuit can’t make “if-then” decisions the way an ordinary program can. An ordinary program can check a value and then run only one of two pieces of code. But a quantum computer runs on a superposition of many inputs at once, some of which would run the first piece of code and some of which would run the second, so the circuit has to include the operations for both every time it runs.
第二个是量子电路不能丢弃信息。普通程序在完成临时工作后可以覆盖或删除它;在量子计算机中,这种中间信息不能简单地擦除,因为量子电路的每一步都必须是可逆的。将信息保留在原处也不是选项,因为残留的临时工作会破坏最终结果。丢弃信息的唯一方法是通过反向运行创建它的计算来“逆计算”它,代价是额外的门。这两个约束使得量子电路在运行时间和量子比特上都比经典电路昂贵得多。
The second is that a quantum circuit can’t discard information. An ordinary program can overwrite or delete its scratch work once it’s completed it; in a quantum computer, such intermediate information can’t simply be erased, because every step of a quantum circuit must be reversible. Leaving that information in place isn’t an option, either, because leftover scratch work would corrupt the final result. The only way to discard information is to “uncompute” it by running the computation that created it in reverse, at the cost of additional gates. Both of these constraints make quantum circuits far more expensive, in both runtime and qubits, than their classical counterparts.
这一约束迫使在空间(即量子比特)和时间之间进行艰难的权衡。在一个极端,量子电路可以在中间结果被使用后立即逆计算它们。这释放了量子比特,但如果以后再次需要这些结果,电路必须重新计算它们,这增加了门并增加了运行时间。在另一个极端,电路可以保留中间结果直到不再需要它们。这避免了重复工作,但可能需要更多的量子比特。
This constraint forces a difficult trade-off between space (i.e., qubits) and time. At one extreme, a quantum circuit can uncompute intermediate results as soon as they have been used. This frees up qubits, but if those same results are needed again later, the circuit must recompute them, which adds gates and increases the runtime. At the other extreme, the circuit can retain intermediate results until they’re no longer needed. This avoids repeating work, but it can require many more qubits.
这就是为什么量子电路设计是对 Claude 能力的一个特别有趣的测试。电路可以写成普通代码,但改进它们需要模型在一组与普通编程截然不同的约束下进行推理。
This is what makes quantum circuit design an especially interesting test of Claude’s capabilities. The circuits can be written as ordinary code, but improving them requires the model to reason under a set of constraints quite unlike those of ordinary programming.
我们交给 Claude 的第一个任务是点加法,即在数学曲线(椭圆曲线)上把两个点组合成第三个点的规则。点加法是椭圆曲线上离散对数问题量子算法的核心步骤:给定一个起始点以及它自身相加 _n_ 次的结果,求出 _n_。对于大型曲线,普通计算机无法在合理时间内解决这个问题,但足够大的量子计算机可以。
The first task we gave Claude was point addition, a rule for combining two points on a mathematical curve (an elliptic curve) to produce a third. Point addition is the core step in quantum algorithms for the discrete logarithm problem on elliptic curves: given a starting point and the result of adding it to itself _n_ times, find _n_. For large curves, ordinary computers can't solve this problem in any reasonable amount of time, but a sufficiently large quantum computer could.
这些算法会多次执行点加法,包括反向执行,而这些加法构成了其大部分量子比特和运行时间开销。这类问题——易于计算、极难逆转——正是最早被证明量子计算机能比普通计算机提供指数级加速的问题之一。因此,点加法已成为该领域的标准基准之一。这使得它成为对 Claude 的一项严苛考验。于是,我们要求它规划出点加法真正需要多少量子比特以及多少门。
These algorithms perform point addition many times over, including in reverse, and these additions account for most of their qubit and runtime costs. Problems like this—easy to compute, extremely hard to reverse—were among the first where quantum computers were shown to offer an exponential speedup over ordinary ones. For these reasons, point addition has become one of the field's standard benchmarks. This made it a demanding test for Claude. So, we asked it to map out how few qubits, as well as how few gates, point addition really needs.
我们给 Claude 提供了一段简短的说明。其中解释了点加法的数学规则,以及评估器将如何检查每个所提电路的正确性,并根据其使用的量子比特数和门数进行评分。它还指示 Claude 并行探索多种方法。在仅有人类极少输入(仅限于初始说明和偶尔提示其更广泛地思考)的情况下工作 53 小时后,Claude 得出了该问题的一种全新方法。
We gave Claude a one-paragraph brief. It explained the mathematical rule for point addition, and how the evaluator would check each proposed circuit for correctness and score it on the number of qubits and gates it used. It also instructed Claude to explore several approaches in parallel. After working for 53 hours with minimal human input (limited to the initial brief and occasional prompts to think more broadly), Claude arrived at a completely new approach to the problem.
点加的大部分开销来自一个单独的步骤,称为**模逆**。椭圆曲线算术使用的数字在达到固定上限时会回绕。模逆是除法在回绕意义下的版本:给定整数 \(a\),求 \(x\) 使得 \(ax \equiv 1 \pmod{p}\)。普通计算机可以使用一种称为 **divsteps** 的方法高效地执行这一操作。Divsteps 从一对数字开始,并在多轮迭代中反复简化它们。在每一轮中,divsteps 检查当前的一对数字,并有条件地交换、相加、相减或减半。在此过程中,它只保留刚好足够的信息,以便在最后产生模逆。
Most of the cost of point addition comes from a single step, called _modular inversion_. Elliptic-curve arithmetic uses numbers that wrap back around when they reach a fixed limit. Modular inversion is the wraparound version of division: given an integer _a_, find _x_ such that \(ax \equiv 1 \pmod{p}\). Ordinary computers can perform this operation efficiently using a method called _divsteps_. Divsteps starts with a pair of numbers and repeatedly simplifies them over many rounds of iteration. In each round, divsteps examines the current pair of numbers and conditionally swaps, adds, subtracts, or halves them. Along the way, it preserves just enough information to produce the modular inverse at the end.
尽管 divsteps 在普通计算机上取得了成功,但由于上述可逆性约束,它尚未产生实用的量子电路。每次迭代中所选操作的记录称为**分支信息**,这类草稿信息在传统程序中可以直接丢弃。相比之下,量子电路必须保留该记录,以便计算可以反向运行。因此,divsteps 的直接量子版本被迫累积很长的分支信息历史,这需要大量额外的量子比特来存储。
Despite its success on ordinary computers, divsteps had not yet produced a practical quantum circuit, because of the reversibility constraint described above. The record of which operation was chosen at each iteration, called _branch information_, is the kind of scratch work that a traditional program can simply discard. In contrast, a quantum circuit has to retain that record so the computation can be run backward. A straightforward quantum version of divsteps is therefore forced to accumulate a long history of branch information, which requires an enormous number of additional qubits to store.
Claude 认识到,这种 divsteps 方法对于量子电路可能很有前景,但前提是必须找到一种方法,避免存储完整的历史记录。它有了一个想法:也许记录根本不需要存储。Claude 推理认为,通过仔细检查每次迭代后的那对数字,可能可以直接推断(或“解码”)分支信息。本质上,数字本身就会存储记录。然后,电路就可以在不需要任何额外量子比特的情况下反向运行。
Claude recognized that this divsteps approach could be promising for quantum circuits, but only if there were a way around needing to store the full history. It had an idea: perhaps the record didn’t need to be stored at all. Claude reasoned that it might be possible to directly infer (or “decode”) the branch information by carefully inspecting the pair of numbers after each iteration. In essence, the numbers themselves would store the record. The circuit could then be run backward without needing any extra qubits.
为了测试这个想法,Claude 探索了一些简单的候选规则来执行解码。这些早期规则在小规模测试用例上有效,但当 Claude 在完整问题规模(256 位数字)上测试时,它们失败了。
To test this idea, Claude explored a number of simple candidate rules for performing the decoding. These early rules worked on small test cases, but they failed when Claude tested them at the full problem size, on 256-bit numbers.
Claude 随后尝试了一种更理论化的方法。它没有猜测和测试规则,而是着手从数学上理解 divsteps 为何会如此行为。它证明了一系列关于迭代过程的结果,包括几个新的代数恒等式。从这些恒等式中,Claude 推导出了一个精确的解码规则公式,该公式能够正确地从数字对中恢复分支信息。然后,它检查了这个公式,首先通过大规模数值模拟运行,然后在 Lean 中形式化该声明。在完成全面验证后,Claude 产生了第一个无需存储分支历史的可逆 divsteps 实现。
Claude then tried a more theoretical approach. Rather than guessing and testing rules, it set out to understand mathematically why divsteps behaves the way it does. It proved a series of results about the iteration process, including several new algebraic identities. From these identities, Claude derived a precise formula for the decoding rule that would correctly recover the branch information from the numerical pairs. It then checked the formula, first by running it through large-scale numerical simulations, and then formalizing the claim in Lean. With the full validation complete, Claude produced the first reversible implementation of divsteps with no stored branch history.
解码可以节省量子比特,但会耗费时间。因此,作为进一步的改进,Claude 寻找了存储分支信息比解码分支信息更划算的情形。通过改变电路存储而非解码分支信息的阈值,Claude 在两种极端之间产生了一个新的设计族。与之前最小的设计相比,该设计族中的一个电路多用了 12% 的量子比特,但门数减少了 17 倍。更一般地说,这些新设计扩展了帕累托前沿,提供了此前无法获得的量子比特数与运行时间的组合(表 1)。
Decoding saves qubits, but it costs time. So, as a further refinement, Claude looked for situations in which it would be cheaper to store the branch information than to decode it. By varying the threshold at which the circuit stores rather than decodes the branch information, Claude produced a new family of designs between the two extremes. Compared with the smallest previous design, one circuit in the family uses 12% more qubits but 17x fewer gates. More generally, the new designs expand the Pareto frontier, offering combinations of qubit count and runtime that weren't available before (Table 1).
优化问题处于众多任务的核心,包括调度、物流和材料设计。一个优化问题给出一组相互竞争的约束条件,并要求给出尽可能多地满足这些约束的解。针对这类问题,人们已经提出了许多量子算法,但其中大多数算法相较于普通计算机只能带来有限或不确定的收益。解码量子干涉测量(Decoded quantum interferometry,DQI)是最有希望提供**超多项式量子加速**的候选方案之一——这种优势会随着问题规模增大而迅速扩大。
Optimization problems are at the heart of a wide range of tasks, including scheduling, logistics, and materials design. An optimization problem presents a set of competing constraints and asks for the solution that satisfies as many of them as possible. Many quantum algorithms have been proposed for problems like these, but most promise only modest or uncertain gains over ordinary computers. Decoded quantum interferometry (DQI) is one of the strongest candidates for offering a _superpolynomial quantum speedup_—an advantage that rapidly widens as the problems get larger.
当量子计算机完成一次计算时,读取其量子比特只会产生一个答案,该答案是从它们以叠加态持有的各种可能性中随机选出的。DQI 的工作原理是制备一个量子态,使得好的解比坏的解更有可能被读出。要做到这一点,需要使用纠错解码器,它从紧凑的摘要中恢复出一份简短的“错误”列表。这是该算法中开销最大的一步。因此,如果我们能做出更快的解码器,也就能更快地执行 DQI。
When a quantum computer finishes a computation, reading out its qubits produces just one answer, selected at random from the possibilities they were holding in superposition. DQI works by preparing a quantum state in which good solutions are more likely to be read out than bad ones. Doing this involves using an error-correcting decoder, which recovers a short list of “errors” from a compact summary. This is the most expensive step in the algorithm. So, if we could make a faster decoder, we could also perform DQI faster.
提出 DQI 的研究者在一个名为**最优多项式交集**(optimal polynomial intersection,OPI)的问题上演示了该方法,这是曲线拟合的一种基于网格的版本(图 3)。设想一个网格,其中每个位置 _x_ 都包含若干个可接受的 _y_ 值。目标是找到一条简单曲线(低次多项式),使其尽可能多地穿过各个 _x_ 位置上的可接受方格。DQI 使用一种特定类型的解码器——Reed-Solomon 解码器——来求解这一优化问题。
The researchers who introduced DQI demonstrated it on a problem called _optimal polynomial intersection_ (OPI), a grid-based version of curve fitting (Figure 3). Imagine a grid in which each position _x_ contains several acceptable values of _y_. The goal is to find a simple curve (a low-degree polynomial) that passes through an acceptable square for as many _x_ positions as possible. DQI tackles this optimization problem using a specific type of decoder, called a Reed-Solomon decoder.
Reed-Solomon 解码从上述对错误的紧凑摘要出发,这种摘要被称为**校验子**(syndrome)。解码器的任务是根据这一摘要推断出数据中错误发生的位置及其具体内容。此前最先进的量子电路使用扩展欧几里得算法来处理这些校验子,该算法是一系列除法与交换操作,其步骤数量和顺序取决于所给定的具体输入。此时量子电路的约束再次显现:普通程序可以针对每个输入走不同的路径,而量子电路同时处理大量输入,必须用单一固定的门序列来处理所有输入。为应对这一点,此前的设计不得不将计算拉伸到比任何单个输入所需都多得多的迭代轮次,并且必须在每一轮执行所有操作,即使这样做并不必要。
Reed-Solomon decoding starts from the compact summary of errors mentioned above, which is known as a _syndrome_. The decoder's job is to infer, from this summary, where in the data the errors occurred and what they were. The previous state-of-the-art quantum circuit processed these syndromes using the extended Euclidean algorithm, a sequence of divisions and swaps in which the number and order of steps depend on the particular input it's given. Here, the constraints of quantum circuits reemerge: while an ordinary program can follow a different path for every input, a quantum circuit, working on many inputs at once, has to handle all of them with a single fixed sequence of gates. To manage this, the previous design had to stretch the computation over many more rounds of iteration than any single input would need, and had to run every operation in every round, even when doing so was unnecessary.
改进这一解码器可以大幅缩短 DQI 的运行时间。Google Quantum AI 研究人员的估算表明,在世界上最强大的超级计算机之一 Frontier 上求解某个特定的 OPI 问题大约需要三个月,而在未来运行 DQI 的量子计算机上大约只需一小时。这一小时中的大部分时间将花在 Reed-Solomon 解码上。
Improving this decoder could substantially reduce DQI's runtime. Estimates by researchers at Google Quantum AI imply that solving one particular OPI problem would take about three months on Frontier, one of the world's most powerful supercomputers, compared with roughly an hour on a future quantum computer running DQI. Most of that hour would be spent on Reed-Solomon decoding.
因此,我们让 Claude 为解码步骤设计一个更高效的量子电路。Claude 很快得出结论:扩展欧几里得算法并不适合量子电路。于是,它围绕另一种名为 Berlekamp-Massey 解码的解码方法来组织电路,该方法逐个读取校验子(错误摘要),并逐步推导出最简单的规则,根据列表中前面的数字来预测每一个数字。一旦找到该规则,错误便随之显现。与扩展欧几里得算法不同,Berlekamp-Massey 在每一轮执行相同类型的步骤,并且总是运行相同数量的轮次,这契合量子电路单一固定的门序列,最终为 Claude 提供了一个高效得多的构建基础。
So, we asked Claude to design a more efficient quantum circuit for the decoding step. Claude quickly concluded that the extended Euclidean algorithm was a poor fit for a quantum circuit. Instead, it organized its circuit around a different decoding method, known as Berlekamp-Massey decoding, which reads through syndromes (summaries of errors) one at a time and gradually works out the simplest rule that predicts each number in the list based on the ones that came before it. Once that rule is found, it reveals the errors. Unlike the extended Euclidean algorithm, Berlekamp-Massey performs the same kind of step in every round and always runs the same number of rounds, which suits a quantum circuit's single fixed sequence of gates, ultimately giving Claude a much more efficient foundation to build on.
改用 Berlekamp-Massey 算法后,电路不再需要针对不同输入走不同路径。但使其可逆又带来了另一个挑战,这次是由上文讨论的逆计算约束导致的。在每一轮中,电路都会计算一些只需短暂使用的临时值,但这些信息不能简单地删除:为了在之后进行逆计算,电路必须能够恢复这些信息。
Switching to Berlekamp-Massey removed the need for the circuit to take different paths for different inputs. But making it reversible introduced another challenge, this time as a result of the uncomputing constraint discussed above. In every round, the circuit calculates temporary values that it needs only briefly, but this information can't simply be deleted: to uncompute it later, the circuit has to be able to recover that information.
存储这些信息将代价高昂到难以承受。因此,Claude 采用了与处理 divsteps 时相同的方法:它找到了一种从电路当前状态重建大部分信息的方式,从而无需存储这些信息。然而,少数异常值无法通过这种方式恢复,必须被保存下来。
Storing this information would have been prohibitively expensive. So Claude took the same kind of approach as it had for divsteps: it found a way to reconstruct most of this information from the circuit's current state, so it didn't need to be stored. However, a few exceptional values couldn't be recovered in this way and had to be saved.
为最坏情况(即在 35 个不同轮次中都出现异常值)预留足够内存将需要 665 个量子比特。于是,Claude 编写了一个高速模拟器,并运行了 4.03 亿次样本解码,以测量这些异常实际发生的频率。几乎每次运行最多只需要保存一个值。因此,Claude 的电路只为保存一个值预留了空间,即 19 个量子比特。大约每 10,000 次运行中有一次需要更多空间并失败,这远在该任务允许的错误率范围内。这些改进用少量固定的量子比特和门替代了大规模的最坏情况预留(图 4)。
Setting aside enough memory for the worst possible case, in which an exceptional value arises in 35 different rounds, would take 665 qubits. Instead, Claude wrote a high-speed simulator and ran 403 million sample decodings to measure how often these exceptions actually occurred. Almost every run needed to save one value at most. So Claude's circuit sets aside room for just one saved value, or 19 qubits. About one run in 10,000 needs more than that and fails, which is well within the error rate the task allows. These improvements replaced large, worst-case reserves with a small, fixed number of qubits and gates (Figure 4).
这些优化共同将解码器中的门数量相对于 Google 之前的构造减少了 12 倍。这一改进来自在三个层面对计算进行重新设计:不同的方法(用 Berlekamp-Massey 解码替代扩展欧几里得算法)、不同的电路架构(重建临时值而非存储它们),以及不同的资源预算(精确测量电路真正需要多少内存和计算)。任何单一改动本身都不足以实现这一目标,但它们结合在一起,使 DQI 中最昂贵的步骤成本降低了略超过一个数量级。
Together, these optimizations reduced the number of gates in the decoder by a factor of 12 relative to Google's previous construction. The improvement came from redesigning the computation at three levels: a different method (replacing the extended Euclidean algorithm with Berlekamp-Massey decoding), a different circuit architecture (reconstructing temporary values instead of storing them), and a different resource budget (measuring precisely how much memory and computation the circuit really needed). No single change would have been enough on its own, but together, they make the most expensive step of DQI just a little over an order of magnitude cheaper.
科学进步常常源于将理论想法变得实用。实现这一点的主要方式之一是让曾经被认为不切实际的过程变得足够快速和廉价,从而能够执行。量子电路设计就是一个典型例子:上文描述的 FeMoco 估计中 150,000 倍的下降花费了许多研究团队八年时间,每一步通常代表数月的工作。相比之下,Claude 的椭圆曲线设计是单次 53 小时运行的结果。
Scientific progress often comes from making theoretical ideas practical. One of the main ways this happens is by making a process that was once thought to be impractical fast and cheap enough to carry out. Quantum circuit design is a prime example: the 150,000-fold drop in the FeMoco estimate described above took many research groups eight years, with each step typically representing months of work. By contrast, Claude's elliptic-curve design was the result of a single 53-hour run.
我们的结果表明,AI 可以支持电路设计工作,产生使有用的量子计算更接近真实硬件能力的实现。如果 AI 能加速这项工作,有用的量子计算可能会更早到来。
Our results suggest that AI can support the work of circuit design, producing implementations that bring useful quantum computations closer to the capabilities of real hardware. If AI can speed up that work, useful quantum computing could arrive sooner.
尽管 Claude 在这些任务上表现令人鼓舞,我们也观察到一些局限性。在早期实验中,Claude 天生保守。它反复质疑明显的改进,有时会继续双重甚至三重检查已经得到充分支持的结果。这种谨慎有时很有价值:例如,它促使 Claude 编写 Lean 证明来验证其 divsteps 设计。但它也表现为倾向于偏好现有的、众所周知的方法,而非更新颖的方法。
Despite Claude's encouraging performance on these tasks, we also observed some limitations. In our early experiments, Claude was conservative by nature. It repeatedly second-guessed apparent improvements, and sometimes continued to double- and even triple-check results that were already well supported. This caution was sometimes valuable: for example, it prompted Claude to write Lean proofs to verify its divsteps design. But it also manifested in a tendency to prefer existing, well-known approaches to more novel ones.
我们采取了两步来缓解这个问题。首先,我们的设置要求 Claude 提出几种性质不同的方法,并并行开发它们。其次,我们偶尔也提示 Claude 扩大搜索范围。这些干预成功地让 Claude 追求更雄心勃勃的想法。例如,椭圆曲线结果并非来自削减现有设计的门数,而是来自探索一种以前不可能的可逆模逆方法,然后推导出使其实用所需的数学结果。一旦有了想法,Claude 就自主开发了该方法、实现了它并验证了其正确性。
We took two steps to mitigate this. First, our setup required Claude to propose several qualitatively different approaches, and to develop them in parallel. Second, we also occasionally prompted Claude to broaden its search. These interventions succeeded in getting Claude to pursue more ambitious ideas. The elliptic-curve result, for example, didn't come from shaving gates off of a pre-existing design but from exploring a method of doing reversible modular inversion that hadn't been possible previously, and then deriving the mathematical results needed to make it practical. Once it had come up with the idea, Claude developed the approach, implemented it, and verified its correctness autonomously.
电路设计只是构建有用量子计算机的一部分。由于量子比特非常脆弱,机器还必须在运行时捕获并修复自身的错误,这依赖于许多其他组件,从纠错码到快速解码器再到硬件本身的控制。这些组件都相互影响,但为了管理复杂性,每个组件通常单独设计。它们中的许多都具有使电路设计非常适合 Claude 的特征:设计可以写成代码、检查正确性,并根据其成本评分。
Circuit design is only one part of building a useful quantum computer. Because qubits are so fragile, the machine must also catch and fix its own errors as it runs, and that depends on many other components, ranging from error-correcting codes to fast decoders to control of the hardware itself. These components all affect one another, but to manage complexity, each is usually designed separately. Many of them share the characteristics that made circuit design a good fit for Claude: a design can be written as code, checked for correctness, and scored by its cost.
这引出了一个耐人寻味的可能性。AI 不必单独设计每个组件,而是可以从算法一直到硬件,对所有组件进行联合优化,从而构建一台针对特定问题量身定制的、完整的纠错量子计算机。此类设计还可以告诉硬件构建者,对于给定应用而言哪些能力最为重要。这可能使设计催化剂和理解新材料等问题,进入首批容错机器的能力范围之内。
This raises an intriguing possibility. Rather than designing each component on its own, AI could optimize all of them jointly, from the algorithm down to the hardware, to build an entire error-corrected quantum computer tailored to a specific problem. Such designs could also tell hardware builders which capabilities matter most for a given application. That could put problems such as designing catalysts and understanding new materials within reach of the first fault-tolerant machines.