Discovering state-of-the-art quantum circuits with large language models

用大语言模型发现先进量子电路（Discovering state-of-the-art quantum circuits with large language models）

Andi Gu Email:  andigu@g.harvard.edu Affiliation:  Harvard Quantum Initiative for Science and Engineering, Cambridge, MA 02138, USA Affiliation:  Department of Physics, Harvard University, Cambridge, MA 02138, USA Affiliation:  Anthropic STEM Fellows Program    Alek H. Kemeny Affiliation:  Anthropic    Susanne F. Yelin Affiliation:  Harvard Quantum Initiative for Science and Engineering, Cambridge, MA 02138, USA Affiliation:  Department of Physics, Harvard University, Cambridge, MA 02138, USA    Mikhail D. Lukin Affiliation:  Harvard Quantum Initiative for Science and Engineering, Cambridge, MA 02138, USA Affiliation:  Department of Physics, Harvard University, Cambridge, MA 02138, USA Affiliation:  QuEra Computing, 1380 Soldiers Field Road, Boston, MA 02135, USA

Abstract

摘要

Significant efforts are currently being directed toward the implementation of large-scale quantum information processors, but realizing useful quantum advantage also requires the development of efficient quantum algorithms. While for many practical problems the dominant resource costs are associated with a small set of computational primitives, optimizing them in the quantum setting presents unique challenges, including a reversibility constraint absent from ordinary classical computation. Here we introduce an evolutionary framework in which large language models (LLMs) propose circuit designs and an independent evaluator verifies and scores them. We apply this framework to tasks spanning numerical computation, chemistry, optimization, quantum simulation, and number theory. In seven of the eight tasks, the discovered circuits significantly reduce both Toffoli and qubit counts relative to the state of the art. In the eighth, the search discovers a new reversible architecture for prime-field modular inversion. By handling reversibility differently, the architecture makes divsteps—a classical algorithm previously impractical for reversible integer arithmetic—viable and substantially improves the Toffoli–qubit trade-off for modular inversion. These results open the door for evaluator-guided LLM co-design of new algorithmic structures for quantum computation.

大规模量子信息处理器的实现正投入大量努力，但实现有用的量子优势还需要高效量子算法。对许多实际问题，主导资源成本集中在少数计算原语上，而在量子设定下优化它们面临独特挑战，包括普通经典计算所没有的可逆性约束。本文提出进化框架：大语言模型（LLM）提议电路设计，独立评估器验证并打分。我们将其应用于跨越数值计算、化学、优化、量子模拟与数论的任务。八项任务中七项，发现的电路相对当时最优显著同时降低 Toffoli 数与量子比特数。第八项中，搜索发现素数域模逆的新可逆架构。通过不同方式处理可逆性，该架构使 divsteps——一种先前对可逆整数算术不实用的经典算法——变得可行，并显著改善模逆的 Toffoli–量子比特权衡。这些结果为评估器引导的 LLM 协同设计量子计算新算法结构打开大门。

Computational primitives based on classical function evaluation play a central role in a wide range of quantum algorithms. Such primitives include decoding routines for optimization [1], numerical functions for quantum simulation [2], arithmetic routines for number theory [3], and quantum read-only memory (QROM), which coherently loads classically specified data into quantum registers [4]. To operate on quantum data, these functions must be compiled into circuits that can be executed coherently on quantum hardware. This imposes two constraints absent from ordinary classical programs. First, because the input may be in superposition, the circuit cannot inspect an intermediate value and select an ordinary classical control-flow path. Data-dependent behavior is instead expressed through controlled operations within a fixed gate sequence, so every branch contributes to the circuit’s cost even if it applies only to some inputs. Second, the computation must be reversible: intermediate information cannot simply be overwritten or discarded. Temporary values must eventually be uncomputed, returning their qubits to their initial state and preventing residual information from remaining entangled with the output. Until they are uncomputed, these values occupy additional qubits. At the same time, when bounded error is permitted, machinery needed only for rare or atypical inputs can sometimes be omitted, reducing resource requirements while keeping the failure probability controlled. Efficient coherent compilation is of major practical importance, and recent reductions in resource requirements have come from coordinated changes to arithmetic algorithms, data representations, and their reversible implementation [5, 6]. Such redesigns are difficult for general quantum circuits because directly testing correctness can require exponentially expensive classical simulation or fully operational large-scale quantum processors. Automated circuit optimizers therefore typically preserve correctness by restricting the search to predefined equivalence-preserving rewrites [7], limiting them to variations of a fixed design.

基于经典函数求值的计算原语在广泛量子算法中起核心作用，包括优化中的译码例程 [1]、量子模拟中的数值函数 [2]、数论中的算术例程 [3]，以及把经典指定数据相干装入量子寄存器的量子只读存储器（QROM） [4]。要作用于量子数据，这些函数必须编译成可在量子硬件上相干执行的电路。这施加了普通经典程序没有的两条约束。其一，输入可能处于叠加，电路不能检查中间值再选择普通经典控制流；数据依赖行为须通过固定门序列内的受控运算表达，因此每个分支都计入电路成本，即使只对部分输入生效。其二，计算必须可逆：中间信息不能简单覆盖或丢弃；临时值最终须反计算，使量子比特回到初态，并防止残留信息与输出纠缠。在反计算之前，这些值占用额外量子比特。同时，在允许有界误差时，仅服务于稀有或非典型输入的机制有时可省略，从而在控制失败概率的前提下降低资源需求。高效相干编译具有重大实践意义；近期资源下降往往来自算术算法、数据表示及其可逆实现的协同改动 [5, 6]。对一般量子电路，此类重设计困难，因为直接测正确性可能需要指数代价的经典模拟或已运行的大规模量子处理器。自动电路优化器因此通常把搜索限制在预定义的保等价改写 [7]，从而只能得到固定设计的变体。

Here we introduce a framework that pairs large language model (LLM) proposals with an independent evaluator that verifies and scores each candidate. We focus on a class of quantum circuits that compute a classical function $f$: for an arbitrary input $\ket{\psi}=\sum_{x,y}\alpha_{x,y}\ket{x}\ket{y}$, the circuit must act as $\ket{\psi}\longmapsto\sum_{x,y}\alpha_{x,y}\ket{x}\ket{y\oplus f(x)}$, where $\ket{x}$ and $\ket{y}$ are computational-basis states of the input and output registers, respectively. By linearity, this coherent action is correct if the circuit performs the required map on every computational-basis input: $\ket{x}\ket{y}\longmapsto\ket{x}\ket{y\oplus f(x)}$. This basis-state reduction makes candidate circuits amenable to programmatic evaluation, since every allowed operation maps a computational-basis state to another computational-basis state, possibly changing its phase, but never creating a superposition [8]. The action of a candidate on any chosen input can therefore be simulated by tracking a bit string and its phase, rather than $2^{n}$ amplitudes. Resource accounting is also simple: we use the Toffoli count $T$ and the peak qubit count $Q$, and rank circuits by their product, the $TQ$-cost. Together, these properties let us build an efficient, programmatic evaluator that checks the correctness and resource cost of any candidate circuit design.

我们提出将大语言模型（LLM）提案与独立评估器配对的框架：评估器验证并给每个候选打分。关注计算经典函数 $f$ 的一类量子电路：对任意输入 $\ket{\psi}=\sum_{x,y}\alpha_{x,y}\ket{x}\ket{y}$，电路须实现 $\ket{\psi}\longmapsto\sum_{x,y}\alpha_{x,y}\ket{x}\ket{y\oplus f(x)}$，其中 $\ket{x}$、$\ket{y}$ 分别为输入与输出寄存器的计算基态。由线性性，该相干作用正确当且仅当电路对每个计算基输入执行所需映射：$\ket{x}\ket{y}\longmapsto\ket{x}\ket{y\oplus f(x)}$。这一基态归约使候选电路可用程序化评估，因为每个允许运算把计算基态映到计算基态，可改相位但从不制造叠加 [8]。因此候选对任一选定输入的作用可通过跟踪比特串及其相位模拟，而非 $2^{n}$ 振幅。资源核算也简单：用 Toffoli 数 $T$ 与峰值量子比特数 $Q$，按乘积 $TQ$ 成本排序。这些性质合起来让我们构建高效、可编程的评估器，检查任一候选电路设计的正确性与资源成本。

Figure 1: Overview of the circuit-discovery framework. (a) A hand-written task specification defines the circuit design task (for example, Reed–Solomon decoding) and is given to an LLM. The LLM proposes architecturally different approaches (algorithm families; here extended Euclidean, Berlekamp–Massey, and Peterson–Gorenstein–Zierler (PGZ) decoders), which are then developed and optimized in parallel. Strong candidates are periodically shared between families to allow for cross-pollination of useful ideas. (b) Conditional routing reduces the cost of coherent control flow: for instance, two controlled multiply-adds (MADDs) become inexpensive controlled swaps and one shared arithmetic block. (c) Branch decisions that a naïve reversible computation stores during the forward pass (red) can instead be decoded from the current state during uncomputation. (d) When an application permits bounded error, allowing rare failures on atypical, costly inputs reduces resource requirements.

图 1：电路发现框架概览。(a) 手写任务规格定义电路设计任务（例如 Reed–Solomon 译码）并交给 LLM。LLM 提出架构不同的路径（算法族；此处为扩展欧几里得、Berlekamp–Massey 与 Peterson–Gorenstein–Zierler (PGZ) 译码器），再并行发展与优化。强候选定期在族间共享，以便有用思想交叉授粉。(b) 条件路由降低相干控制流成本：例如两个受控乘加（MADD）变成便宜的受控交换与一个共享算术块。(c) 朴素可逆计算在正向过程存储的分支决策（红）可改为在反计算时从当前状态译出。(d) 当应用允许有界误差时，允许对非典型、昂贵输入的稀有失败可降低资源需求。

Each search begins from a hand-written task specification and a blank program; the specification states the required circuit behavior but provides no implementation guidance. The LLM proposes a candidate and iteratively revises it using evaluator feedback (Figure 1(a)). Previous work represents candidates as sequences of gates or predefined circuit blocks [9, 10], which can obscure the algorithmic structure of the circuit. Our framework instead lets the LLM propose and revise candidates through a high-level Python interface, where reusable functions and ordinary programming constructs make that structure explicit. This allows a single conceptual change to reorganize operations throughout the circuit, while the evaluator tests its consequences for correctness and resource cost. However, purely iterative refinement of a single candidate can remain tied to the architecture from which it began, resulting in convergence to local (but not necessarily global) optima. We therefore start with an ideation stage in which the LLM is prompted to propose several distinct algorithm families, each representing a different approach to the problem. Circuits within each family are optimized independently in parallel, allowing the search to explore different strategies rather than only variations of one design. Well-performing candidates are periodically shared between families so that an idea discovered in one approach can inform another.

每次搜索从手写任务规格与空白程序开始；规格陈述所需电路行为但不给实现指导。LLM 提出候选并用评估器反馈迭代修订（图 1(a)）。先前工作把候选表示为门序列或预定义电路块 [9, 10]，可能掩盖电路的算法结构。我们的框架让 LLM 经高层 Python 接口提案与修订，可复用函数与普通编程构造使结构显式。于是单一概念改动可重组整条电路的运算，评估器则检验其对正确性与资源成本的后果。然而纯迭代 refinement 单个候选可能束缚于起步架构，收敛到局部（未必全局）最优。因此我们先做构思阶段：提示 LLM 提出若干不同的算法族，各自代表不同解题路径。各族电路独立并行优化，使搜索探索不同策略而非单一设计的变体。表现好的候选定期跨族共享，使一族发现的思想可启发另一族。

Across eight diverse compilation tasks, the discovered circuits repeatedly exhibit three common principles of algorithm–circuit co-design. These principles address the features of coherent compilation described above: expressing data-dependent control flow, making intermediate computations reversible without retaining their entire history, and using a failure budget to remove circuit resources devoted to atypical cases (see Figure 1).

在八项多样编译任务上，发现的电路反复呈现算法—电路协同设计的三条共同原则。这些原则针对上文相干编译特征：表达数据依赖控制流、在不保留全部历史的前提下使中间计算可逆，以及用失败预算移除专用于非典型情形的电路资源（见图 1）。

Design principles

设计原则

One recurring principle in the circuits discovered by the search is to replace conditional arithmetic with conditional routing. A naïve coherent translation of a casewise classical algorithm includes a separately controlled arithmetic block for every branch. The discovered circuits instead use a representation in which the branches differ primarily in which values occupy particular computational roles. Relatively cheap controlled swaps then route the appropriate values into those roles, one unconditional arithmetic path performs the expensive work, and further routing places the results in their required registers. In this sense, where a classical program routes execution to the selected operation, the coherent circuit routes the selected data through a shared operation. The idea resembles bucket-brigade quantum random-access memory (QRAM) [11].

搜索发现的电路中一条反复出现的原则是用条件路由替代条件算术。朴素地把分情形经典算法相干翻译，会为每个分支包含单独受控的算术块。发现的电路改用一种表示：分支差异主要在于哪些值占据特定计算角色。相对便宜的受控交换把适当值路由进这些角色，一条无条件算术路径完成昂贵工作，再进一步路由把结果放到所需寄存器。在此意义上，经典程序把执行路由到所选操作，相干电路则把所选数据路由过共享操作。这一想法类似桶旅量子随机访问存储器（QRAM） [11]。

For example, consider four $n$-qubit fixed-point registers $c$, $x$, $y$, and $z$, together with a control qubit $b$. Suppose that we wish to perform

例如,考虑4个$n$-quit固定点登记册 $c$,$x$,$y$和$z$,以及一个控制quit $b$. 假设我们想表演

$$x\longmapsto\begin{cases}x+cy&\text{for }b=0,\
x+cz&\text{for }b=1,\end{cases} \tag{1}$$

while returning $c$, $y$, and $z$ unchanged. A naïve implementation uses two controlled multiply-adds. Conditional routing instead swaps $y$ and $z$ according to $b$, applies one uncontrolled multiply-add, and undoes the swap. For the standard schoolbook construction [12], this reduces the Toffoli count from $T_{\mathrm{naive}}(n)=3n^{2}+17n-2$ to $T_{\mathrm{routed}}(n)=(3n^{2}+17n-2)/2$, as shown in Figure 1(b).

同时使 $c$、$y$、$z$ 不变。朴素实现使用两次受控乘加。条件路由则按 $b$ 交换 $y$ 与 $z$，施加一次不受控乘加，再撤销交换。对标准课本构造 [12]，这把 Toffoli 数从 $T_{\mathrm{naive}}(n)=3n^{2}+17n-2$ 降到 $T_{\mathrm{routed}}(n)=(3n^{2}+17n-2)/2$，如图 1(b)。

More generally, conditional routing requires canonicalizing branch-dependent states into a representation on which the same expensive computation applies. Schematically, when the branch can be expressed as $U_{b}=R_{b}^{-1}KR_{b}$, the circuit need only control the inexpensive routing transformation $R_{b}$; the expensive kernel $K$ appears once and need not be controlled. Finding such a decomposition typically takes more than recognizing identical arithmetic in two branches: it exploits an equivalence in the required output so that apparently different updates become instances of the same computation. The difficulty lies less in the routing circuit than in determining which branch-dependent differences matter and which can be absorbed into a shared representation.

更一般地，条件路由要求把分支依赖状态规范化为同一昂贵计算适用的表示。示意上，当分支可写成 $U_{b}=R_{b}^{-1}KR_{b}$ 时，电路只需控制便宜的路由变换 $R_{b}$；昂贵内核 $K$ 出现一次且不必受控。找到这种分解通常不只是认出两分支中相同算术：它利用所需输出上的等价，使表面上不同的更新成为同一计算的实例。难点较少在路由电路本身，而在判定哪些分支依赖差异要紧、哪些可吸收进共享表示。

Reversibility creates a second challenge: reversing a conditional update requires knowing which branch was taken during the forward computation. A naïve implementation records each decision in a history stack whose size grows with the number of updates. But the branch decisions need not always be stored explicitly: different branches may leave distinguishable patterns in registers that remain available during uncomputation. As illustrated in Figure 1(c), the circuit can recover the branch bit from such a pattern, use it to select the appropriate inverse update, and then clear the recovered bit, so the register contents serve as an inexpensive record of the branch decisions. For example, suppose we have a register $g$ that begins at $g_{0}=0$. In round $j$, conditioned on some branch bit $b_{j}$, we add $2^{j}$, so that

可逆转性产生了第二个挑战:要逆转有条件的更新,需要知道在前期计算中采取了哪个分支. 一个天真的执行记录每个决定在一个历史堆栈中,其规模随着更新次数的增加而增加。 但是,分支机构的决定并不总是明确保存:不同的分支机构可能会在登记册中留下在不计算期间仍然可用的可区分的模式。 如图1(c)所示,电路可以从这种模式中回收分支位,使用它来选择适当的反向更新,然后清除回收位,因此寄存器内容充当分支决定的廉价记录. 例如,假设我们有一个始于$g_{0}=0$的登记簿$g$。 在$j$回合中,以某些分支位值$b_{j}$为条件,我们增加了$2^{j}$,这样,

$$g_{j+1}=g_{j}+b_{j}2^{j}. \tag{2}$$

For arbitrary values of $g_{j}$, there is no way to tell from $g_{j+1}$ which branch was taken. Globally, however, there is an important invariant: $g_{j}<2^{j}$, and therefore bit $j$ of $g_{j+1}$ must equal $b_{j}$. During uncomputation, the circuit can simply read this bit to recover $b_{j}$. The computation’s evolving state thus supplies the branch decisions in reverse order without a separate history stack. In general, finding such a decoder requires the forward algorithm, its data representation, and its uncomputation procedure to be designed together. Viewed locally, an update may be ambiguous, since either branch can appear to admit a valid predecessor. The ambiguity can disappear once the circuit is restricted to states reachable from the prescribed initialization, where a relation across the registers can distinguish histories that no single register can.

对于$g_{j}$的任意值,无法从$g_{j+1}$中分出哪个分支. 你说什么? 但是,在全球范围内,有一种重要的变异:$g_{j}<2^{j}$,因此,$g_{j+1}$的bit $j$必须等于$b_{j}$. 在不计算时,电路可以简单地读取这个位点以恢复$b_{j}$. 因此,计算正在演变的状态以反向顺序提供分支决定,而不另设历史堆栈。 一般来说,找到这样的解码器需要前方算法,其数据表示,及其不计算程序一起设计. 从本地角度看,更新可能含糊不清,因为任何一个分支似乎都承认有效的前身。 一旦电路被限制在从规定的初始化可达到的状态上,那么模糊性就可能消失,在这种状态下,登记册之间的一种关系可以区分任何单一登记册都无法区分的历史。

The third principle exploits the small but finite failure probability permitted by most quantum algorithms. Turning this failure budget into resource savings, however, is not automatic. One must first identify the rare inputs that determine worst-case resource requirements. Unlike a classical program, a quantum circuit must contain the gates and ancillas required by every supported path. A rare input can therefore determine the circuit’s Toffoli count or peak qubit count. Yet identifying such inputs is not enough: the circuitry supporting them may not be separable from the computation on typical inputs. The co-design task is to reorganize the computation so that the additional resources required by rare inputs are localized—for example, to extra iterations, stack entries, or arithmetic lanes. Those components can then be omitted while confining failure to the low-probability inputs that require them (Figure 1(d)). In what follows we show how these design principles result in significantly improved algorithmic circuits across a wide variety of quantum tasks.

第三项原则利用大多数量子算法允许的微小但有限的故障概率. 然而,将这一失败的预算转化为资源节约并不是自动的。 必须首先确定决定最坏情况所需资源的稀有投入。 与古典程序不同,量子电路必须包含每个支持路径所需的门和角. 因此,一个罕见的输入可以决定电路的Toffoli计数或峰值qubit计数. 然而,确定这种投入是不够的:支持这种投入的电路可能无法与典型投入的计算分开。 共同设计的任务是重组计算,以便稀有输入所需的额外资源能够本地化——例如,用于额外迭代、堆栈条目或算术道。 然后可以省略这些组件,同时将失败限制在需要的低概率输入(图1(d))。 接下来,我们展示这些设计原理如何 使算法电路大大改进 跨越各种各样的量子任务。

Reversible syndrome decoding for DQI

面向 DQI 的可逆伴随式译码

Decoded quantum interferometry (DQI) is a quantum algorithm that turns certain optimization problems into decoding problems for classical error-correcting codes, using quantum interference to favor better solutions. A central application is optimal polynomial intersection (OPI), a form of polynomial fitting over finite fields for which DQI offers a superpolynomial speedup over known classical algorithms. DQI achieves this by using a Reed–Solomon decoder as a subroutine within the quantum computation [1]. The decoder identifies the positions and values of errors from a collection of algebraic checks called syndromes. DQI requires this decoding to run coherently on a superposition of inputs, making the reversible decoder a dominant resource cost. [13] compiled DQI circuits for OPI over binary extension fields using reversible Reed–Solomon decoders based on the extended Euclidean algorithm.

译码量子干涉（DQI）是一种量子算法，把某些优化问题变成经典纠错码的译码问题，用量子干涉偏好更好解。核心应用之一是最优多项式交（OPI）——有限域上的一类多项式拟合，DQI 相对已知经典算法提供超多项式加速。DQI 通过在量子计算内把 Reed–Solomon 译码器当子程序实现这一点 [1]。译码器从称为伴随式的代数校验集合识别错误位置与值。DQI 要求该译码在输入叠加上相干运行，使可逆译码器成为主导资源成本。[13] 用基于扩展欧几里得算法的可逆 Reed–Solomon 译码器，为二元扩域上的 OPI 编译了 DQI 电路。

We study their primary Reed–Solomon instance, in which 70 syndrome values uniquely determine an error pattern containing at most 35 errors. Our search framework discovered a circuit that replaces their synchronized Euclidean solve with the Berlekamp–Massey (BM) recurrence. BM substantially reduces the arithmetic cost, but its updates overwrite intermediate values that a naïve reversible implementation would retain in a large history stack. The discovered circuit preserves BM’s arithmetic advantage while avoiding most of this storage (Figure 2).

我们研究其主要 Reed–Solomon 实例：70 个伴随式值唯一确定至多含 35 个错误的错误模式。我们的搜索框架发现的电路用 Berlekamp–Massey（BM）递推替换其同步欧几里得求解。BM 大幅降低算术成本，但其更新会覆盖中间值，朴素可逆实现须把它们保留在大历史栈中。发现的电路在保留 BM 算术优势的同时避免了大部分这类存储（图 2）。

Figure 2: Reversible Reed–Solomon decoding. (a) The synchronized extended-Euclidean construction of [13] requires approximately $1.9$ million Toffolis for the locator solve. (b) Berlekamp–Massey reduces this cost to approximately $140{,}000$ Toffolis but naïvely accumulates intermediate information (red). DIV forms $\alpha=\Delta/\delta$, MADD applies the multiply-add, and the flag marks the replace case. (c) Conditional routing preserves this arithmetic advantage while avoiding most history storage. Block widths are proportional to Toffoli count. (d) Locator construction as convolution with the syndrome sequence. The discrepancy $\Delta$ is the convolution at the next syndrome; a nonzero value requires updating the locator.

图2:Reversible Reed – Solomon解码. (a)同步扩展-Euclidean 构造 [13] 需要大约$1.9$万Toffoli用于定位解析. (b) Berlekamp - 梅西将这一成本降低到大约$140{,}000$ Toffolis,但天真地积累中间信息(红色). DIV形式为$\alpha=\Delta/\delta$ ,MADD应用乘法加法,旗标为替换大小写. (c) 有条件的路由保持这种算术优势,同时避免大多数历史存储。 块宽度与Toffoli计数成正比. (d) 定位器构造与综合症序列结合。 偏差$\Delta$是下一个综合征的演化;非零值需要更新定位器.

Reed–Solomon decoding amounts to determining which positions in the data contain errors. The $L$ error positions are encoded in a locator polynomial $\sigma(z)=\sum_{k=0}^{L}\sigma_{k}z^{k}$, whose roots identify those positions. To recover the locator coefficients, BM solves for the lowest-degree nonzero polynomial whose convolution (see Figure 2(d)) with the syndrome sequence vanishes:

Reed–Solomon解码等于确定数据中哪些位置含有错误. $L$错误位置被编码在一个定位器多号$\sigma(z)=\sum_{k=0}^{L}\sigma_{k}z^{k}$中,其根部识别这些位置. 为了恢复定位系数,BM解决了与综合征序列发生共化(见图2(d))而消失的低度非零倍数:

$$(S*\sigma)_{r}=\sum_{k=0}^{L}\sigma_{k}S_{r-k}=0,\qquad r=L+1,\ldots,70. \tag{3}$$

BM constructs the locator incrementally. At each round, the convolution evaluated at the next syndrome gives the discrepancy $\Delta$: if it vanishes, no correction is needed; otherwise, BM adjusts the locator coefficients and, when necessary, increases its degree.

BM逐渐构建定位器. 在每一回合,在下一轮综合征中评估的演化值给出了差异$\Delta$:如果消失,不需要纠正;否则,BM会调整定位系数,并在必要时提高其程度.

To make a correction without invalidating previous rounds of updates, BM retains an earlier polynomial $\tau$ as a correction template, together with its nonzero discrepancy $\delta$. When $\Delta\neq 0$, BM scales $\tau$ by $\alpha=\Delta/\delta$ and applies the correction $\sigma\leftarrow\sigma-\alpha\tau$. BM keeps the template until the current locator has accumulated enough information from subsequent syndromes to take over its role:

为了在不否定前几轮更新的情况下作出更正,BM保留了较早的多元$\tau$作为校正模板,同时保留其非零差异$\delta$. 当$\Delta\neq 0$时,BM以$\alpha=\Delta/\delta$表示$\tau$比例,并应用$\sigma\leftarrow\sigma-\alpha\tau$的校正. BM保留模板,直到当前定位器从后续综合征中积累足够的信息来接管其角色:

$$\displaystyle(\sigma-\alpha\tau,\tau,\delta) \\ \displaystyle\quad\text{(retain)}, \\ \displaystyle(\sigma-\alpha\tau,\sigma,\Delta) \\ \displaystyle\quad\text{(replace)}. \tag{4a}$$

The replace update in Equation 4b creates the main reversibility problem: it overwrites the previous template $\tau$ and discrepancy $\delta$. A naïve reversible implementation stores these displaced values so that the update can later be undone. Over repeated rounds, this accumulates a history of whole polynomials (Figure 2(b)).

Equation 4b中的替换更新产生了主要的可逆性问题:它覆盖了先前的模板$\tau$,与$\delta$存在差异. 可逆的天真执行储存了这些被置换的价值观,以便日后可以取消更新。 在反复的回合中,它积累了整个多名体的历史(图2(b))。

The discovered circuit avoids this polynomial history by exploiting a freedom in the decoding task: the locator is needed only up to a nonzero multiplicative factor, because rescaling leaves its roots unchanged. The circuit (Figure 2(c)) therefore implements a rescaled version of both branches of Equation 4, using simple conditional routing and a single shared update:

发现的电路通过在解码任务中利用自由来避免这种多名历史:定位器仅需要达到非零倍增因子,因为再缩放使其根基不变. 因此,电路(图2(c))采用简单的有条件路由和单一共享更新,对方程式4的两分支执行一个重级版本:

$$\displaystyle(\sigma-\alpha\tau,\tau,\delta) \\ \displaystyle\quad\text{(retain)}, \\ \displaystyle(\tau-\alpha^{-1}\sigma,\sigma,\Delta) \\ \displaystyle\quad\text{(replace)}. \tag{5a}$$

The result $\tau-\alpha^{-1}\sigma=-\alpha^{-1}(\sigma-\alpha\tau)$ differs from the locator in the unrescaled update only by the nonzero scale factor $-\alpha^{-1}$ and so has the same roots. Both branches can then use one shared arithmetic path without storing the displaced template $\tau$.

结果$\tau-\alpha^{-1}\sigma=-\alpha^{-1}(\sigma-\alpha\tau)$与未调整更新中的定位器不同,只有非零尺度系数$-\alpha^{-1}$,因此也有相同的根. 两个分支然后可以使用一个共享的算术路径,而无需存储被忽略的模板$\tau$ .

This resolves the history problem for the polynomial registers, but the discrepancies present a second reversibility problem. To uncompute a correction, the circuit must recover whichever discrepancy is no longer present after the update. The replace case of Equation 5b overwrites the stored value $\delta_{\mathrm{old}}$ with $\delta_{\mathrm{new}}=\Delta$, but the circuit can decode $\delta_{\mathrm{old}}$ from the constant coefficients of the updated locator registers. BM shifts the template by one power of $z$ every round, so $\tau$ has zero constant coefficient entering the round. Writing $\sigma_{0}$ and $\tau_{0}$ for the constant coefficients after the update gives $\delta_{\mathrm{old}}=\sigma_{0}\tau_{0}^{-1}\delta_{\mathrm{new}}$. This case thus adds no entry to the history stack. In fact, the circuit never stores $\delta$ at all: the same relation fixes $\delta$ in terms of the locator’s constant coefficient (Supplementary Information [SI] I.1). The retain update of Equation 5a is the exception: it keeps the previous discrepancy $\delta$, while the current discrepancy $\Delta$, which is needed to reverse the correction, remains only in a temporary register. Each retain update therefore stores $\Delta$ on the history stack. In the worst case, 35 stack entries (665 qubits) would be needed. Under the DQI input distribution, a second stack entry is required with probability $1.0\times 10^{-4}$, so the discovered circuit allocates only one stack entry (19 qubits instead of 665) and permits failure on these rare inputs.

这解决了多名登记簿的历史问题,但差异提出了第二个可逆转性问题。 为了校正,电路必须收回更新后已不存在的差额。 方程式5b的替换例将存储值XX 是不是$\delta_{\mathrm{old}}$ 覆盖为 $\delta_{\mathrm{new}}=\Delta$,但电路可以从更新的定位器登记册的恒定系数中解码 * $\delta_{\mathrm{old}}$. BM每回合以一个功率的$z$改变模板,因此$\tau$进入回合的恒系数为0. 在更新后为恒系数写入$\sigma_{0}$和$\tau_{0}$给出$\delta_{\mathrm{old}}=\sigma_{0}\tau_{0}^{-1}\delta_{\mathrm{new}}$ . 因此,本案没有增加历史堆栈条目。 事实上,电路从不存储$\delta$:同一关系用定位器的常数(补充信息[SI]I.1)来固定$\delta$. 保留更新的方程式5a是例外:它保留了先前的差异$\delta$,而目前的差异$\Delta$是逆转校正所需的,它只保留在一个临时登记册中. 因此,每个系统都保留更新,将$\Delta$存储在历史堆栈上。 在最坏的情况下,需要35个堆栈条目(665个qubits). 在DQI输入分布下,需要用概率为$1.0\times 10^{-4}$的第二个堆栈条目,因此发现的电路只分配一个堆栈条目(19个qubit而不是665个),并允许这些稀有输入失败.

Together, these transformations make the arithmetically efficient BM algorithm suitable for reversible computation.

这些转变加在一起,使得算术效率的BM算法适合可逆计算.

Reversible modular inversion

可逆模逆

Modular inversion is the task of finding $x$ such that $wx\equiv 1\pmod{p}$, given a nonzero input $w$ and a prime $p$. It is a central arithmetic subroutine in a range of quantum algorithms [14, 3]. A standard way to compute the inverse is through the extended Euclidean algorithm. Euclidean algorithms repeatedly simplify a pair of integers while preserving their greatest common divisor. By tracking how this divisor is expressed in terms of the original inputs, they also recover coefficients $\alpha,\beta$ satisfying $\alpha p+\beta w=1$, so $\beta$ is the inverse of $w$ modulo $p$.

模态反转是找到$x$的任务,这样,$wx\equiv 1\pmod{p}$得到非零输入的$w$和质值的$p$. 它是一系列量子算法[14,3]中的中央算术子例程. 计算反向的一个标准方法是通过延伸的欧几利得算法. 欧几利得算法在保留其最大的常见二维器的同时,反复简化一对整数. 通过跟踪这种divisor是如何用原始输入表达的,它们也回收了满足$\alpha p+\beta w=1$的$\alpha,\beta$系数,因此$\beta$是$w$ modulo $p$的逆差.

Divsteps is a variant of the Euclidean algorithm that replaces division with conditional additions, subtractions, and halving [15]. Starting from $f=p$ and $g=w$, the goal is to reduce the pair to $f=\pm 1$ and $g=0$ while preserving their greatest common divisor. The basic strategy is to hold the odd integer $f$ fixed while reducing $g$: if $g$ is even, it can be halved directly; if $g$ is odd, adding or subtracting $f$ first makes it even. These operations preserve the greatest common divisor because $f$ is odd. Holding $f$ fixed indefinitely, however, would leave only one integer being reduced, so the algorithm must periodically swap their roles. A small signed counter $z$ schedules these swaps without ever comparing $f$ and $g$: it roughly tracks how many more bits $f$ has than $g$, so a swap occurs once $g$ is likely the smaller of the two. This allows both integers to be reduced using only inexpensive arithmetic and control. Two auxiliary integers $f_{v}$ and $g_{v}$ track the input’s contribution in a scaled form: after $t$ steps, they satisfy $f_{v}w\equiv 2^{t}f\pmod{p}$ and $g_{v}w\equiv 2^{t}g\pmod{p}$. Thus, at termination, $ff_{v}$ gives the desired inverse up to the scaling factor $2^{t}$. The scaling keeps the coefficient updates free of division. Starting from $(z,f,g,f_{v},g_{v})=(0,p,w,0,1)$, each step applies one of three updates:

divsteps)是欧几利得算法的一个变种,它用有条件的加法,减法,并减半[15]. 从$f=p$和$g=w$开始,目标是在保留它们最大的共同分光器的同时,将对子减为$f=\pm 1$和$g=0$. 基本策略是将奇数整数$f$固定在减少$g$的同时:如果$g$是均匀的,可以直接将它减半;如果$g$是奇数,则增减$f$首先使其均匀. 由于$f$是奇数,这些操作保留了最大的常见的二极管. 然而,无限期地持有$f$将只减少一个整数,因此算法必须定期互换角色. 一个小型的签名计数器$z$列表 这些互换从未比较过$f$和$g$:它大致跟踪了$f$有多少比$g$更多的位数,所以一旦$g$很可能是两者中较小的位数,就发生了互换. 这使得只使用廉价的算术和控制就可以减少两个整数。 两个辅助整数$f_{v}$和$g_{v}$以缩放的形式跟踪输入的贡献:在$t$步骤之后,它们满足$f_{v}w\equiv 2^{t}f\pmod{p}$和$g_{v}w\equiv 2^{t}g\pmod{p}$. 因此,在终止时,$ff_{v}$给出了期望的逆比值,达到$2^{t}$。 缩放使系数更新不受分割。 从$(z,f,g,f_{v},g_{v})=(0,p,w,0,1)$开始,每个步骤适用三个更新中的一个:

$$\displaystyle(-z,\ g,\ (g-f)/2,\ 2g_{v},\ g_{v}-f_{v}) \\ \displaystyle\quad\text{for }z\geq 0,\ g\text{ odd}, \\ \displaystyle(z+1,\ f,\ (g+f)/2,\ 2f_{v},\ g_{v}+f_{v}) \\ \displaystyle\quad\text{for }z<0,\ g\text{ odd}, \\ \displaystyle(z+1,\ f,\ g/2,\ 2f_{v},\ g_{v}) \\ \displaystyle\quad\text{for }g\text{ even}. \tag{6a}$$

Classically, each update overwrites the current state. Reversing the computation, however, requires knowing which of the three updates was applied. A naïve implementation would store this choice at every step, accumulating a history stack alongside the arithmetic registers. The discovered circuit instead recovers decisions from the current arithmetic state. Some decisions are easy to recover from the updated registers, while others require a more involved decoding procedure. We label each update by two bits: $s$ records whether the step swaps the roles of $f$ and $g$, and $b$ records whether the incoming $g$ is odd. The updates in Equations 6a, 6b and 6c have labels $(s,b)=(1,1),(0,1),(0,0)$, respectively. The task during uncomputation is to recover these bits from the updated state.

经典中,每次更新都会覆盖当前状态. 但是,要推翻计算,就需要知道三个更新中哪一个已经适用。 一个天真的执行将把这种选择储存在每一个步骤上,在算术登记册旁边积累一个历史堆。 所发现的电路转而从目前的算术状态中恢复决定. 有些决定很容易从更新的登记册中收回,而另一些决定则需要更多的解码程序。 我们给每个更新贴上两个比特的标签:$s$记录步骤是否互换$f$和$g$的角色,$b$记录进球的$g$是否是奇数. 第6a、6b和6c条的更新分别有$(s,b)=(1,1),(0,1),(0,0)$的标签。 未计算期间的任务是从更新状态中回收这些位.

Figure 3: Making divsteps reversible with minimal overhead. (a) Excursion depth $j$ in one representative walk. Dots mark ambiguous decisions. We use a cutoff $j_{\mathrm{store}}=5$, so all ambiguous decisions with $j\geq 5$ are stored rather than decoded. The histogram shows the distribution of excursion depths over uniformly sampled walks: only 12.4% of ambiguous decisions reach $j\geq 5$. (b) Empirical stopping-time and history-size distributions. The discovered circuit assumes that every walk terminates between steps $499$ and $533$; this assumption fails with probability $\sim 10^{-5}$. It also allocates enough qubits to store at most 60 branch decisions, which is sufficient for all but a $2.4\times 10^{-6}$ fraction of walks.

图3:使潜水器可逆性最小,但间接费用最低。 点点标志着模棱两可的决定。 我们使用一个截断的$j_{\mathrm{store}}=5$,所以所有与$j\geq 5$的模棱两可的决定都是存储而不是解码的. 直方图显示了游览深度在统一抽样行走上的分布:只有12.4%的决定达到了$j\geq 5$. (b)经验性停止时间和历史大小分布. 发现的电路假设每个行走都会在$499$和$533$之间终止;这个假设以$\sim 10^{-5}$的概率失效. 它还分配了足够的qubit,最多可以存储60个分支决定,这除了一个$2.4\times 10^{-6}$部分的行走量外,都足够了.

For many steps, recovering $b$ and $s$ requires only a few observations about the updated registers. A swap (Equation 6a) always leaves a distinctive pattern in $f_{v}^{\prime}$. To see this, note that throughout the recurrence, $f_{v}$ is even and $g_{v}$ is odd. A swap sets $f_{v}^{\prime}=2g_{v}$, which has exactly one trailing zero bit, whereas a nonswap sets $f_{v}^{\prime}=2f_{v}$, which is divisible by four. Thus the updated coefficient identifies every swap, recovering both $s=1$ and $b=1$; otherwise, $s=0$, so the swap bit $s$ is always cheaply recoverable. For nonswaps, two further tests determine $b$. If $z^{\prime}\geq 1$, the incoming $g$ must have been even, since an odd value would have triggered a swap. If the step first reaches $g^{\prime}=0$, the incoming $g$ must instead have been odd, since halving a nonzero even integer cannot give zero. Together, these simple tests recover about two thirds of the decisions in a typical walk (the sequence of divsteps applied to one input). The only unresolved cases are nonterminating nonswaps with $z^{\prime}\leq 0$, where the circuit must determine whether the step added $f_{v}$ to $g_{v}$, that is, the bit $b$ in the update $(f_{v}^{\prime},g_{v}^{\prime})=(2f_{v},g_{v}+bf_{v})$.

对于许多步骤来说,恢复$b$和$s$只需要对更新后的登记册提出一些意见。 互换(第6a条)在$f_{v}^{\prime}$中总是留下一个独特的模式。 要看到这一点,请注意,在整个重现过程中,$f_{v}$是偶数的,$g_{v}$是奇数的. 互换设置$f_{v}^{\prime}=2g_{v}$, 它有一个正后方的零位位, 而非斯瓦普设置$f_{v}^{\prime}=2f_{v}$, 它被四位分隔 。 因此更新的系数可以确定每次互换,同时恢复$s=1$和$b=1$;否则,$s=0$,所以互换位点$s$是永远便宜可收回的. 对于非扫描剂,还有两项测试确定$b$。 如果$z^{\prime}\geq 1$, 进场的$g$必须是对等的, 因为奇数会触发互换 。 如果该步骤首先达到$g^{\prime}=0$ ,则收到的$g$必须是奇数,因为将非零整数减半不能给出零。 这些简单的测试一起在典型的行走中恢复了大约三分之二的决定(一个输入应用的跳跃顺序). 唯一未解决的案件是未与$z^{\prime}\leq 0$结束的无悬浮,其中电路必须确定该步骤是否将$f_{v}$添加到$g_{v}$,即更新后的$(f_{v}^{\prime},g_{v}^{\prime})=(2f_{v},g_{v}+bf_{v})$中的位值$b$.

Consider a swap followed by a sequence of these ambiguous nonswaps, which we call an excursion. Immediately after the swap, $f_{v}=2q$ for some odd $q$. On the $j$th step of the excursion, $f_{v}=2^{j-1}q$ (hence $f_{v}^{\prime}=2^{j}q$), where the excursion depth $j$ counts the initiating swap as step 1. Equivalently, $j$ is the number of trailing zero bits in the updated coefficient $f_{v}^{\prime}$. The update to $g_{v}$ becomes

考虑一个互换,然后是这些模糊不清的不擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦 在交换之后,$f_{v}=2q$立即为一些奇怪的$q$。 在游览的$j$第2步上,$f_{v}=2^{j-1}q$(即$f_{v}^{\prime}=2^{j}q$),其中的游览深度$j$将启动的互换算作第1步. 同理,$j$是更新系数$f_{v}^{\prime}$中后零位数的数量. 更新至$g_{v}$

$$g_{v}^{\prime}=g_{v}+b2^{j-1}q. \tag{7}$$

Note that this almost matches the binary-record construction in Equation 2. The only difference is the shared factor $q$: to recover $b$, we need to remove the factor $q$ from the update. Since $f_{v}^{\prime}=2^{j}q$ is known, we can recover $q$ by removing the trailing zero bits from $f_{v}^{\prime}$. To remove the same factor from both sides of the update, we multiply by $q^{-1}$ modulo $2^{j}$; this inverse exists because $q$ is odd. The update rule then becomes

请注意,这几乎与方程式2中的二进制记录构造相匹配. 唯一的区别是共享因子$q$:要恢复$b$,我们需要从更新中删除该因子$q$. 由于$f_{v}^{\prime}=2^{j}q$是已知的,我们可以通过去除$f_{v}^{\prime}$的末端零位来恢复$q$. 要从更新的两边去除相同的因子,我们乘以 是不是$q^{-1}$ modulo $2^{j}$;这种反向存在是因为$q$是奇数. 然后更新规则变成

$$g_{v}^{\prime}q^{-1}\bmod 2^{j}=(g_{v}q^{-1}\bmod 2^{j})+b2^{j-1}. \tag{8}$$

Crucially, in Appendix A, we show that $(g_{v}q^{-1}\bmod 2^{j})<2^{j-1}$. Therefore,

至关重要的是,我们在附录霄门中显示$(g_{v}q^{-1}\bmod 2^{j})<2^{j-1}$。 因此,

$$b=\operatorname{bit}_{j-1}\!\left(g_{v}^{\prime}q^{-1}\bmod 2^{j}\right), \tag{9}$$

where bit positions are counted from zero at the least significant (rightmost) bit. Every quantity on the right-hand side is determined by the updated registers, so the rule recovers the branch decision without access to the previous state. This recovery relies on a global invariant ensuring that earlier branch history cannot contaminate the deciding bit. The LLM identified this invariant, which links information accumulated across successive updates to the branch decisions needed during uncomputation, and developed it into a proof that the arithmetic state retains the information required for recovery [16].

中位点位置从 0 计数到最小值( 最右) 位。 右侧的每个数量都由更新的登记册决定,所以规则恢复分支的决定而不能访问之前的状态. 这种恢复依赖于全球变化因素,确保较早的分支历史不会污染决定的位点。 LLM发现了这种不常态,它将连续更新中积累的信息与分支在不计算时需要的决定联系起来,并将其发展成为计算状态保留恢复所需信息的证明[16].

For a given $j$, the rule in Equation 9 depends only on the lowest $j$ bits of $g_{v}^{\prime}$ and the lowest $j$ bits of $q$. Therefore, for each small value of $j$, we treat the decoding rule as a truth table mapping $2j$ input bits to a single bit $b$, and compile it directly into a Boolean circuit. For larger $j$, the decoder must inspect more bits and becomes increasingly expensive. Although every decision is recoverable in principle, decoding all of them does not give the cheapest circuit. A tunable cutoff $j_{\mathrm{store}}$ determines which ambiguous decisions are decoded and which are stored. At depths $j<j_{\mathrm{store}}$, the circuit uses a decoder; at depths $j\geq j_{\mathrm{store}}$, it writes the decision to a history stack. Increasing the cutoff spends more Toffolis on decoding while reducing the required history storage, giving a family of circuits that trade Toffoli count against qubit count (SI II).

对于给定的$j$,在方程式9中的规则只取决于$j$最小位值的$j$位值和$j$最小位值的$q$. 因此,对于$j$的每一个小值,我们把解码规则当作一个将$2j$输入比特映射到单个比特$b$的真人表,直接编译成布尔电路. 对于更大的$j$,解码器必须检查更多的位,并变得日益昂贵. 尽管每项决定原则上都可以收回,但对所有决定进行解码并不能给最便宜的线路。 可捕金枪鱼停产$j_{\mathrm{store}}$决定哪些决定是解码的,哪些是储存的。 在$j<j_{\mathrm{store}}$深度时, 电路使用解码器; 在$j\geq j_{\mathrm{store}}$深度时, 它将决定写成历史堆栈 。 增加截断会花费更多的托弗利斯进行解码,同时减少所需的历史存储量,使一个以托弗利计数与qubit计数(SI II)的电路家族得以交易.

Further savings are possible when the application permits a small failure probability. We use this failure budget to exclude rare, unusually demanding inputs through two resource limits: a fixed history-stack size and a fixed window of supported stopping times. The history-stack limit builds on the decoding trade-off. With $j_{\mathrm{store}}=5$, only $12.4\%$ of ambiguous decisions are written to the stack (Figure 3(a)). On average, the required stack size is 21 history qubits, but it can reach 263 in the worst case. We instead reserve 60 and allow the circuit to fail on rare inputs for which the stack overflows. Such overflows occur with probability $2.4\times 10^{-6}$ per inversion (Figure 3(b)), saving 203 history qubits relative to the worst case. The stopping-time limit addresses a separate cost. A fixed quantum circuit must schedule enough steps for every input it supports. Although 590 divsteps suffice even in the worst case, stopping times are concentrated in a much narrower range (Figure 3(b)). The discovered circuit therefore schedules 533 steps and tests for termination only from step 499 onward; inputs that terminate outside this window are allowed to fail.

如果申请允许少量故障概率,则有可能进一步节省费用。 我们利用这一失败预算,通过两个资源限制,即固定的历史存储大小和固定的支持停工时间窗口,排除了稀有、异常要求的投入。 历史堆积限制建立在解码权衡的基础上. 有了$j_{\mathrm{store}}=5$,只有$12.4\%$的模棱两可的决定被写到堆栈上(图3(a))。 平均来说,要求的堆栈大小是21个历史qubit,但在最坏的情况下可以达到263个. 相反,我们保留了60个,并允许电路在堆积过多的稀有投入上发生故障。 这种溢出现象的发生概率为$2.4\times 10^{-6}$反转(图3(b)),相对于最坏的情况,节省了203个历史方位。 停止时间限制涉及单独的费用。 一个固定的量子电路必须为其支持的每一个输入安排足够的步骤. 尽管即使在最坏的情况下,590个跳槽也足够了,但停留时间集中在更窄的范围内(图3(b))。 因此,发现的电路只将533个步骤和测试从499步骤上排出,以便终止;在此窗口外终止的输入允许失败。

Branch decoding and bounded resource allocation thus make divsteps practical for reversible modular inversion. A complete benchmark circuit built on this inversion (SI II) uses 4.0 million Toffolis and 935 qubits.

分支解码和限定的资源分配使得可逆模块反转的分解变得切实可行。 基于这个反转(SI II)的完整基准电路使用400万Toffoli和935qubits.

Discussion and outlook

讨论与展望

The DQI and modular inversion constructions illustrate how redesigning the representation and uncomputation of an algorithm can substantially reduce its quantum resource requirements. Similar gains arise across the other tasks studied here. For seven of the eight tasks, the discovered circuit uses both fewer Toffolis and fewer qubits than the corresponding baseline. Table 1 summarizes these improvements, and the Supplementary Information gives details for each task.

DQI和模块化的反演构建说明了重新设计一个算法的表示和不计算如何可以大幅降低其量子资源需求. 在此研究的其他任务也取得了类似成果。 对于8项任务中的7项,已发现的电路既使用较少的Toffoli斯,也使用较少的方格比特. 表1概述了这些改进,补充资料提供了每项任务的详细情况。

Task	Baseline $\boldsymbol{(T,Q)}$	Ours $\boldsymbol{(T,Q)}$	$\boldsymbol{G_{TQ}}$
Reed–Solomon DQI decoder	$(5.1{\cdot}10^{6},\,1{,}938)$	$(4.4{\cdot}10^{5},\,1{,}837)$	$12$
Hermitian DQI decoder	$(1.0{\cdot}10^{8},\,1.9{\cdot}10^{5})$†	$(9.3{\cdot}10^{5},\,2{,}395)$	—†
HHL rotation angle	$(1.6{\cdot}10^{4},\,300)$	$(1{,}348,\,115)$	$32$
Coulomb potential	$(6{,}355,\,252)$	$(1{,}140,\,142)$	$9.9$
Fixed-point Gaussian	$(2.4{\cdot}10^{4},\,362)$	$(1{,}583,\,139)$	$39$
Fe2S2 alias–Select	$(5.5{\cdot}10^{4},\,139)$	$(1.5{\cdot}10^{4},\,126)$	$4.1$
Nonabelian lattice-gauge simulation	$(1.3{\cdot}10^{6},\,1{,}927)$	$(1.7{\cdot}10^{5},\,1{,}859)$	$7.7$
Prime-field modular inversion	—‡	$(4.0{\cdot}10^{6},\,935)$	—

Table 1: Toffoli–qubit results across the eight compilation tasks, comparing baselines against our discovered circuits (see for details); $G_{TQ}=(TQ)_{\mathrm{baseline}}/(TQ)_{\mathrm{ours}}$. Where a baseline contains free parameters, we choose them to minimize its $TQ$-cost. HHL: Harrow–Hassidim–Lloyd.

** 任务**	** 基准** $\boldsymbol{(T,Q)}$	** 我们**	$\boldsymbol{G_{TQ}}$
Reed–Solomon DQI 解码器	$(5.1{\cdot}10^{6},\,1{,}938)$	$(4.4{\cdot}10^{5},\,1{,}837)$	$12$
隐士DQI解码器	第二十届	$(9.3{\cdot}10^{5},\,2{,}395)$	—†
HHL 旋转角度	$(1.6{\cdot}10^{4},\,300)$	$(1{,}348,\,115)$	$32$
国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际 December国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际国际	$(6{,}355,\,252)$	$(1{,}140,\,142)$	$9.9$
固定点	$(2.4{\cdot}10^{4},\,362)$	$(1{,}583,\,139)$	$39$
Fe2S2别名 - 选择	$(5.5{\cdot}10^{4},\,139)$	$(1.5{\cdot}10^{4},\,126)$	$4.1$
非亚贝利式梯形模拟	$(1.3{\cdot}10^{6},\,1{,}927)$	$(1.7{\cdot}10^{5},\,1{,}859)$	$7.7$
Pri谢谢。	—‡	$(4.0{\cdot}10^{6},\,935)$	. . . . . .

表1:Toffoli-qubit在8项汇编任务中的结果,将基线与我们发现的电路进行比较(详情参见);$G_{TQ}=(TQ)_{\mathrm{baseline}}/(TQ)_{\mathrm{ours}}$。 如果基准包含自由参数,我们选择这些参数以尽量减少其$TQ$ - 成本。 (原始内容存档于2018-03-27). Harrow–Hassidim–Lloyd.

A recurring source of these gains is the recovery of classical algorithmic efficiency under the constraints of quantum computation. In a naïve reversible implementation, coherent control and cleanup can introduce enough overhead to obscure the advantages of an efficient classical method. Our Berlekamp–Massey and divstep constructions show how jointly choosing the algorithm, representation, and uncomputation can recover those advantages. These results suggest that some apparent costs of quantum arithmetic reflect limitations of existing reversible constructions rather than of the algorithms themselves.

这些收益的一个经常性来源是在量子计算的限制下恢复古典算法效率. 在天真可逆的执行中,连贯的控制和清理可带来足够的间接费用,以掩盖高效的古典方法的优点。 我们的Berlekamp—Massey和Divstep构造表明,共同选择算法、代表性和不计算如何可以恢复这些优势。 这些结果表明,量子算术的一些表面成本反映了现有可逆构造的局限性,而不是算法本身的局限性.

Finding such constructions requires reasoning about choices whose benefits depend on one another. An arithmetic saving may become useful only after the associated control and uncomputation costs have also been reduced. A candidate design must therefore be carried through several unresolved mathematical and implementation problems before its resource advantage becomes apparent.

要找到这种构思,就必须对利益取决于彼此的选择进行推理。 只有在相关控制和不计算费用也减少之后,算术节约才可能有用。 因此,候选人的设计必须经过若干尚未解决的数学问题和执行问题,才能使其资源优势明显可见。

The framework is bounded by the choices that define each task. One is the objective that ranks circuits: we use the $TQ$-cost for a uniform comparison, but other objectives are equally reasonable. In practice, the relative importance of qubit count, depth, routing, and measurements depends on details such as hardware constraints, decoder performance, and error-correction architecture. The scoring function can be replaced with a hardware-appropriate combination of these resources, but determining that objective remains a matter of application and hardware judgment. The circuit interface defines a second boundary. Here, the required transformation is specified in a fixed computational basis, excluding optimizations whose advantage comes from changing the encoding itself. For example, coset representations can make modular addition cheaper by encoding each residue as a superposition of congruent integers, which avoids conventional comparisons and corrections at the cost of an exponentially small error [17, 18], but such encodings lie outside the present framework. More generally, the task boundary, input distribution, data representations, and accuracy target make a search well posed while also encoding assumptions about how the circuit is embedded in a larger algorithm (in particular, which states it receives and how its outputs are consumed).

框架以界定每项任务的选择为界。 一个是将电路排序的目标:我们使用$TQ$ - 成本进行统一比较,但其他目标同样合理. 在实践中,qubit计数,深度,路由和测量的相对重要性取决于硬件约束,解码器性能,以及错误校正架构等细节. 评分功能可以由这些资源的适合硬件的组合来取代,但确定目标仍然是应用和硬件判断的问题. 电路接口定义了第二个边界. 在这里,要求的转换是在固定的计算基础上指定的,不包括其优点来自于改变编码本身的优化. 例如,coset表达式可以使模块化的添加更便宜,将每个残留物编码为一致整数的叠加,这避免了常规的比较和校正,以一个指数化的小错误为代价[17,18],但这种编码不在现有框架之内. 更一般地说,任务边界,输入分布,数据表示和精度目标使得搜索的设置良好,同时对电路如何嵌入一个更大的算法(特别是,它接收到的是什么以及它的输出是如何消耗的)进行编码假设.

The same choices that bound the search also make reliable programmatic feedback possible: they specify what each candidate must preserve and which resource trade-offs the evaluator should reward. Within these boundaries, our results show that evaluator-guided LLM search can go beyond refining a fixed circuit to uncover new reversible algorithms and representations. Related approaches have produced new algorithms in combinatorics and linear algebra [19, 20]. These observations suggest a practical criterion for extending the approach: wherever a problem admits a sufficiently expressive task interface and its correctness and resource costs can be evaluated cheaply enough to sustain many rounds of search, the same evaluator-guided search may provide a route to new algorithms.

将搜索捆绑起来的相同选择也使得可靠的方案反馈成为可能:它们具体规定了每个候选人必须保留什么,以及评价者应该奖励何种资源权衡。 在这些界限内,我们的结果表明,评估师制导的LLM搜索可以超越精炼固定电路,发现新的可逆算法和表达. 相关方法在梳理学和线性代数中产生了新的算法[19,20]. 这些观察为扩展方法提出了一个实用标准:只要一个问题承认一个足够明确的任务界面,而且其正确性和资源成本可以便宜地评估,足以维持多轮搜索,那么同样的评估者指导的搜索可能为新的算法提供一条路径.

These results, together with related progress in reinforcement learning and LLM-guided discovery of quantum error-correcting codes and encoding circuits [21, 22, 23], create an opportunity for end-to-end co-design of fault-tolerant computation. Choices that are usually made separately—the algorithm and its logical circuit, the error-correcting code and its method for universal logic, the supply of magic states, and the physical execution architecture—strongly determine one another’s costs. A programmatic evaluator that propagates logical errors, resource demand, and hardware requirements across these layers could allow an LLM search to redesign them together, potentially discovering fault-tolerant algorithms and architectures that cannot be found by optimizing each layer in isolation.

这些成果,加上强化学习的相关进展和LLM引导发现量子误差校正码和编码电路[21,22,23],创造了一个端到端共设计容错计算的机会. 通常单独做出的选择——算法及其逻辑电路,校正错误的代码及其通用逻辑的方法,魔法状态的供给,以及物理执行架构——有力地决定了彼此的成本. 方案评价员通过这些层传播逻辑错误、资源需求和硬件要求,可以允许LLM搜索一起重新设计,有可能发现无法通过孤立地优化每一层而找到的容错算法和架构。

Acknowledgments

致谢

We thank Pablo Bonilla, Arjun Kar, Nazli Ugur Koyluoglu, Rohan Mehta, Varun Menon, and Vinay Ramasesh for feedback on the manuscript. AG conducted part of this work under the Anthropic STEM Fellows Program. Work at Harvard was supported by IARPA and the Army Research Office under the Entangled Logical Qubits program (Cooperative Agreement Number W911NF-23-2-0219) and by the National Science Foundation (NVQL grant PHY-2410716).

我们感谢Pablo Bonilla、Arjun Kar、Nazli Ugur Koyluoglu、Rohan Mehta、Varun Menon和Vinay Ramasesh对手稿的反馈。 AG在Anthropic STEM研究员方案下开展了这项工作的一部分。 哈佛大学的工作得到了IARPA和陆军研究办公室的支持,根据"Entangled Logical Qubits"方案(合作协议编号W911NF-23-2-0219)和国家科学基金会(NVQL grant PHY-2410716).

Methods

方法

A classical function cannot generally be applied directly within a quantum algorithm, because quantum evolution must be reversible. Instead, a function $f$ is embedded in a reversible map $\ket{x}\ket{y}\longmapsto\ket{x}\ket{y\oplus f(x)}$. A natural model for these subroutines is the kickmix circuit model of [8], which augments reversible classical computation with measurement-based uncomputation (MBU) and diagonal sign gates. Despite these additional operations, kickmix circuits remain efficiently classically simulable. This allows candidate circuits to be tested for their action on coherent quantum superpositions, providing the reliable correctness signal needed for evolutionary search.

一个古典函数一般不能直接在量子算法内应用,因为量子演化必须可逆. 相反,一个函数$f$嵌入了可逆的地图$\ket{x}\ket{y}\longmapsto\ket{x}\ket{y\oplus f(x)}$. 这些子例程的自然模型是[8]的 kickmix 电路模型,它用基于测量的不计算(MBU)和对角符号门来增强可逆的经典计算. 尽管增加了这些操作,但踢混合电路在古典上仍然是高效的仿真. 这样可以测试候选电路在连贯量子叠位上的行动,提供进化搜索所需的可靠正确性信号.

Circuits that implement the same specification can have very different time and space requirements. We use Toffoli count and peak qubit count as proxies for these costs. Toffoli gates require expensive non-Clifford resources, so their count tracks a large part of the logical work and often the runtime [24, 25]. The peak qubit count measures the data and ancillas that must coexist during execution and therefore approximates the required logical processor footprint [26]. The two resources also typically trade against each other: additional ancillas can avoid recomputation, while recycling ancillas can reduce space at the cost of additional gates. We multiply these quantities to obtain the $TQ$-cost, which provides a single objective for comparing such designs.

执行相同规格的电路可以有非常不同的时间和空间要求. 我们用Toffoli计数和峰值qubit计数作为这些费用的代名词. Toffoli大门需要昂贵的非克里福德资源,因此他们的计数轨迹是逻辑工作的一大部分,经常是运行时间[24,25]. 峰值qubit计数测量在执行期间必须共存的数据和角盘,因此大致相当于所需的逻辑处理器脚印[26]. 这两种资源也典型地举行了两次相互贸易:额外的香草可以避免重算,而再循环的香草可以减少空间,而代价是额外的门. 我们乘以这些数量以获得$TQ$成本,这为比较这种设计提供了单一的目标。

Together, the correctness tests and $TQ$-cost define a constrained optimization problem over circuit-generating programs. Motivated by recent advances in coding and reasoning agents and LLM-guided algorithmic discovery, we use an LLM to propose coordinated, task-specific redesigns within an evolutionary search [27, 28, 20].

正确性测试和$TQ$ - 成本共同定义了在电路生成程序上限制优化的问题. 受最近编码和推理代理以及LLM制导算法发现的进步的驱动,我们使用LLM在演化搜索中提出协调的,针对特定任务的重新设计[27,28,20].

Circuit model and validity

电路模型与有效性

A compilation task specifies a reversible action on computational-basis states: a permutation $\pi$ and, when needed, a Boolean phase $g$. A circuit may use $a$ ancilla qubits, but must return them to zero:

汇编任务规定了一个可逆计算基础的动作:一个演化$\pi$,以及在需要时的布尔阶段$g$。 电路可能使用$a$ angilla qubits,但必须返回到零:

$$V\ket{x}\ket{0^{a}}=(-1)^{g(x)}\ket{\pi(x)}\ket{0^{a}}. \tag{10}$$

Every ancilla must return to $\ket{0}$ because quantum operations must be unitary, and thus reversible. For a numerical approximation, the required output relation may instead specify an error bound; interface preservation, phase correctness, and ancilla uncomputation remain exact. We separately allow some circuits to fail on a bounded fraction of inputs drawn from a stated distribution; this fraction is the failure budget. Following [8], the kickmix model permits three classes of operation:

每个c必须返回$\ket{0}$,因为量子操作必须是单一的,因此是可逆的. 对于数字近似,需要的输出关系可能相反指定一个错误约束;接口保存,相位正确,以及ancilla不计算仍然准确. 我们分别允许某些电路在从所声明的分布中提取的限定部分输入上发生故障;这个部分是失败的预算. 之后[8], kickmix模式允许三类操作:

1. classical reversible gates: $X$, CNOT, Toffoli, and swap;
2. diagonal sign gates: $Z$, CZ, CCZ, and global sign flips; and
3. destructive $X$-basis measurements.

1. 古典可逆门:$X$、CNOT、Toffoli和互换;
   认真地指出: 2. 对角标志门: $Z$, CZ, CCZ, 和全局标志翻转;以及 2.
2. 破坏性的$X$-基准测量。

Before any measurement, the evolution of a computational-basis input is simple. Reversible gates update its stored bit string, while diagonal gates update only its sign, so the state remains of the form $(-1)^{\phi}\ket{x}$. A classical simulator therefore need only track the current bits $x$ and the sign $\phi$, rather than a full state vector. The operations apply phase kickback while mixing basis states, giving kickmix its name.

在任何测量之前,计算基础输入的演化是简单的. 逆转门更新其存储的位字符串,而对角门仅更新其标志,因此状态仍为$(-1)^{\phi}\ket{x}$. 因此, 这个经典模拟器只需要跟踪当前位的$x$和标志的$\phi$, 而不是完整的状态向量. 操作采用kickback阶段,而mixbasing表示,赋予kickmix名称.

To illustrate why uncomputation is costly, consider a temporary AND. A Toffoli computes $t=uv$ into an ancilla. After $t$ has been used, applying the same Toffoli again returns that qubit to zero:

为了说明为何不考虑费用高昂,可考虑采用临时性办法。 一个Toffoli计算$t=uv$ 成acilla. 在盏$t$被使用后,再次应用同样的Toffoli返回qubit为零:

$$\ket{u,v}\ket{0}\xrightarrow{\mathbf{Toffoli}}\ket{u,v}\ket{uv}\xrightarrow{\text{use }uv}\ket{u,v}\ket{uv}\xrightarrow{\mathbf{Toffoli}}\ket{u,v}\ket{0}. \tag{11}$$

Computing and uncomputing this temporary AND therefore costs two Toffolis.

电子计算和不计算这个临时费用,因此要花费两个Toffoli。

MBU, introduced by [29], replaces the second Toffoli with a destructive $X$-basis measurement and a cheap phase correction. Measuring $t$ produces a uniformly random outcome $r$ and releases the ancilla, which can be restored to $\ket{0}$:

由[29]引入的MBU,用破坏性的$X$−碱基测量和廉价的相位校正取代了第二款Toffoli. 测量$t$产生一个统一随机的结果$r$并释放 Acilla , 它可以还原为$\ket{0}$:

$$\ket{u,v}\ket{0}\xrightarrow{\mathbf{Toffoli}}\ket{u,v}\ket{uv}\xrightarrow{\text{use }uv}\ket{u,v}\ket{uv}\xrightarrow{\ X\text{-measure }r\ }(-1)^{ruv}\ket{u,v}\ket{0}\xrightarrow{\mathrm{CZ}\ \text{if }r=1}\ket{u,v}\ket{0}. \tag{12}$$

Because CZ is Clifford, the temporary AND is computed and cleared using only one Toffoli. By linearity, the same reasoning applies component by component when the retained bits are in superposition.

由于CZ是克利福德的,临时的和被计算和清除时只使用一个Toffoli. 按线性,当保留位处于叠加状态时,同一推理按组件应用组件.

More generally, suppose an ancilla contains a Boolean function $f(y)$ of retained basis data $y$. If $m$ records any earlier measurement outcomes, the simulator represents the ancilla’s destructive $X$-basis measurement by the transition

更一般地说,假设acilla包含一个布尔函数$f(y)$保留的基础数据$y$。 如果$m$记录任何早期的测量结果,模拟器代表了 ancilla 具有破坏性的$X$- 过渡时的测量基准

$$((y,f(y)),m,\phi)\longmapsto(y,mr,\phi\oplus rf(y)),\qquad\Pr(r=0)=\Pr(r=1)=\frac{1}{2}. \tag{13}$$

On a coherent input, the retained state is therefore

因此,根据一致的投入,保留状态是:

$$\sum_{y}\alpha_{y}(-1)^{rf(y)}\ket{y}. \tag{14}$$

When $r=1$, a classically conditioned diagonal circuit for $(-1)^{f(y)}$ cancels this sign.

当$r=1$ 时,一个经典条件的$(-1)^{f(y)}$的对角电路取消了这个标志.

For a fixed computational-basis input and a particular sequence of measurement outcomes $m$, we call the resulting evolution a computational-basis trajectory. A kickmix circuit may perform several such measurements. Their outcomes may be combined by classical XOR and may control diagonal corrections, but cannot control gates that change the stored basis string. Every measurement record therefore induces the same basis permutation:

对于固定的计算基输入和特定的计量结果序列$m$,我们称由此产生的演化为计算基轨. kickmix电路可进行若干次这样的测量。 它们的结果可能由经典的XOR结合,并可能控制对角校正,但不能控制改变存储的基字符串的门. 因此,每个测量记录都会产生同样的基质演化:

$$V_{m}\ket{x}=(-1)^{\phi(x,m)}\ket{\pi(x)}. \tag{15}$$

Exact coherent correctness additionally requires

准确无误的正确性还需要

$$\phi(x,m)=g(x) \tag{16}$$

for every allowed input and every record of nonzero probability. The measurement register then factors from the logical output. Allowing an outcome to control a basis-changing gate would instead make the permutation depend on the record and could leave the logical output correlated with the measurement environment.

用于每个允许的输入和每个非零概率的记录。 然后从逻辑输出中计数。 允许一个结果来控制一个改变基数的闸门,反而会使通量依赖于记录,并使逻辑输出与测量环境相关。

Validation and statistical guarantees

验证与统计保证

The circuits are ultimately applied to coherent superpositions, whereas the evaluator follows one computational-basis trajectory at a time. Each test must therefore capture enough information to determine the trajectory’s coherent action. For a basis input $x$ and measurement record $m$, the evaluator checks that the output matches the target, required inputs are unchanged, every ancilla has returned to $\ket{0}$, and the phase agrees with the target exactly. These checks compare the complete final state rather than only its classical output. An ancilla that retains input-dependent information can become entangled with the logical registers, while an incorrect sign can alter subsequent interference without changing any output bit. Resetting or tracing out a dirty ancilla is therefore not a substitute for uncomputing it.

电路最终被应用于连贯的叠加位置,而评估者一次遵循一个计算基轨迹. 因此,每个测试必须掌握足够的信息来确定轨迹的一致行动。 就基础输入$x$和测量记录$m$而言,评价人员检查产出是否与目标相符,所需投入是否不变,每份Acilla已返回$\ket{0}$,阶段与目标完全一致. 这些检查比较了完整的最终状态,而不仅仅是它的经典输出. 保留依赖输入信息的acilla可以与逻辑寄存器缠绕在一起,而不正确的符号可以改变后续的干扰而不改变任何输出位. 因此,重构或追查肮脏的血管不能代替不加以比较。

If every pair $(x,m)$ passes these tests, the measurement record factors from the logical output, and linearity extends agreement on every trajectory to any coherent input. For large input domains, however, the evaluator samples these trajectories rather than checking them all.

如果每对$(x,m)$通过这些测试,来自逻辑输出的测量记录因子和线性将每个轨迹的一致延伸至任何连贯的投入. 然而,对于大的输入领域,评估人员对这些轨迹进行抽样,而不是检查所有轨迹。

Consider a coherent input $\ket{\psi}=\sum_{x}\alpha_{x}\ket{x}$, with $\mathcal{D}(x)=|\alpha_{x}|^{2}$, and let $\mathcal{M}$ be the set of possible measurement records. After deferring the measurements, the candidate and target states can be written as

考虑以$\mathcal{D}(x)=|\alpha_{x}|^{2}$为单位的一致投入$\ket{\psi}=\sum_{x}\alpha_{x}\ket{x}$,并让$\mathcal{M}$成为一套可能的测量记录。 在推迟测量之后,候选人和目标国可以写成:

$$\ket{\Phi_{V}}=\frac{1}{\sqrt{|\mathcal{M}|}}\sum_{x,m}\alpha_{x}V_{m}\ket{x}\ket{m},\qquad\ket{\Phi_{U}}=\frac{1}{\sqrt{|\mathcal{M}|}}\sum_{x,m}\alpha_{x}U\ket{x}\ket{m}. \tag{17}$$

Let $B$ be the set of pairs $(x,m)$ on which $V_{m}\ket{x}\neq U\ket{x}$, and let

任 外 、 任 外 、 任 外

$$\varepsilon=\frac{1}{|\mathcal{M}|}\sum_{(x,m)\in B}|\alpha_{x}|^{2} \tag{18}$$

be the probability of $B$ under $\mathcal{D}$ and the uniform distribution over measurement records. Projecting onto the span of these defective trajectories gives

在$\mathcal{D}$下为$B$的概率和测量记录的统一分布。 投射到这些有缺陷的轨迹的间距上

$$\bigl\|\ket{\Phi_{V}}-\ket{\Phi_{U}}\bigr\|\leq 2\sqrt{\varepsilon}. \tag{19}$$

Consequently, the state fidelity is at least $(1-2\varepsilon)^{2}$. Any subsequent measurement distribution changes by at most $2\sqrt{\varepsilon}$ in total variation distance. We bound $\varepsilon$ by drawing $x$ from $\mathcal{D}$ and sampling every measurement outcome uniformly, exactly as in a basis trajectory. For a candidate fixed before the test draw, $k$ independent tests all pass with probability $(1-\varepsilon)^{k}$. Thus, if all $k$ tests pass, then with confidence $1-\delta$

因此,国家忠诚至少是$(1-2\varepsilon)^{2}$。 其后的测量分布变化最多为$2\sqrt{\varepsilon}$总变异距离. 我们通过从$\mathcal{D}$中抽取$x$来将$\varepsilon$捆绑起来,并按基准轨迹对每一项测量结果进行统一取样。 对于测试前固定的候选人,$k$独立测试均通过,概率为$(1-\varepsilon)^{k}$. 因此,如果$k$测试全部通过,那么有信心$1-\delta$

$$\varepsilon\leq 1-\delta^{1/k}\approx\frac{\ln(1/\delta)}{k}. \tag{20}$$

More generally, if a test with $k$ random samples accepts at most $b$ failures, a candidate with true failure probability $\varepsilon$ passes with probability

更一般地说,如果一个使用$k$随机样本的测试最多接受$b$失败,一个具有真实失败概率的候选人$\varepsilon$通过概率.

$$P_{k,b}(\varepsilon)=\sum_{j=0}^{b}\binom{k}{j}\varepsilon^{j}(1-\varepsilon)^{k-j}. \tag{21}$$

Cost model and scoring

成本模型与打分

We define the $TQ$-cost of a circuit by

我们用

$$TQ=\text{Toffoli count}\times\text{peak qubit count}, \tag{22}$$

where $T$ counts Toffoli and CCZ gates equally and $Q$ is the largest number of logical qubits allocated at once.

其中XXMAT81XX计算Toffoli和CCZ的闸门相等,而$Q$是一次分配的逻辑qubit数量最多的.

We weight space and time equally in this cost function for simplicity. In practice, their relative importance depends on the hardware and application. When qubits are scarce, for example, a cost of the form $(\text{qubit count})^{\kappa}\times\text{Toffoli count}$ with $\kappa>1$ may be more appropriate; resource estimates for factoring have used $\kappa$ between 1 and 3 [30, 6]. Either $T$ or $Q$ can also be replaced with other measures of time or space. In particular, when there is limited magic-state-factory throughput (as is typically the case), runtime is bottlenecked by the Toffoli count, motivating its widespread use as a time proxy [24, 25]. However, with enough factories to supply magic states in parallel, Toffoli depth rather than Toffoli count limits runtime. Similarly, for architectures with cheap cold storage for inactive qubits [31], $Q$ can be replaced by active volume [32], which counts only the qubits participating in logical operations.

为了简单起见,我们在这个成本函数中对空间和时间进行同等的加权。 在实践中,它们的相对重要性取决于硬件和应用. 例如,当qubit 稀缺时,使用$\kappa>1$的$(\text{qubit count})^{\kappa}\times\text{Toffoli count}$的表格成本可能更合适;用于保理的资源估计数在 1 到 3 [30, 6] 之间使用了$\kappa$。 $T$或$Q$也可以被其他时间或空间度量替代. 特别是当魔法-状态-因子吞吐量有限(典型的情况就是如此)时,运行时间被Toffoli计数(英语:Toffoli count)所瓶颈,激发其作为时间代用的广泛使用[24,25]. 然而,由于工厂足够平行地提供魔法状态,Toffoli深度而不是Toffoli计数限制运行时间. 同样,对于为不活跃的qubits而廉价冷存储的架构[31],$Q$可以被活动量[32]所取代,这只算参与逻辑操作的qubits.

The search is not tied to the specific form of the $TQ$-cost: it can run with any computable objective. A later case study illustrates the available trade-offs: the modular-inversion search (SI II) produces a family of circuits along a Toffoli–qubit frontier (SI II.1), and an objective that weights qubit count more heavily selects a lower-qubit member of that family.

搜索不与$TQ$ - cost 的具体形式绑定:它可以运行在任何可计算的目标上. 稍后的一项案例研究说明了现有的权衡:模块化反转搜索(SI II)在Toffoli-qubit边框(SI II.1)上产生了一组电路,以及一个以qubit计数的更重度量该家族中一个较低qubit成员的目标.

Evolutionary search

进化搜索

We encode each candidate as Python code that constructs a circuit. Functions, loops, and named registers preserve the organization of the computation, allowing the LLM to reason about arithmetic subroutines and their composition without reconstructing that structure from a flattened gate sequence. For example, changing a shared arithmetic routine changes every place where it is used, while reorganizing calls to that routine can change when intermediate values are computed, retained, and uncomputed. The representation thus makes coordinated changes expressible as revisions to the underlying algorithm.

我们把每个候选者编码为构建电路的Python代码. 函数,环路,和命名的登记册保留了计算的组织,使得LLM能够对算术子例程及其组成进行推理,而无需从一个扁平的门序列中重建这个结构. 例如,改变一个共享的算术常规会改变其使用的每一个地点,而如果中间值被计算、保留和未计算,重新组织到该常规的调用会改变。 因此,这种表述方式使得协调的变化可以作为对基本算法的修订来表示。

We search over these circuit-generating programs with OpenEvolve [33], using Claude Mythos 5 [28] to propose architectures and program rewrites. Each of the eight searches uses a fixed, hand-written task specification, and all share the same generic circuit-building interface. During ideation, the LLM receives only the specification, circuit model, and correctness criteria, and proposes several distinct circuit architectures. The LLM has no access to the evaluator beyond the feedback returned after each submission. Starting from a blank program, it chooses the algorithm, representation, and circuit structure and produces the discovered circuits without substantive human intervention.

我们用OpenEvolve[33]搜索这些电路生成程序,使用克劳德·神话5[28]提出架构和程序重写. 八次搜索都采用了固定的手写任务规格,都共享相同的通用电路建设接口. 在构思过程中,LLM只接收规格,电路模型,以及正确性标准,并提出了几种不同的电路架构. 除了每次提交后反馈之外,LLM无法接触评价人员。 从空白程序开始,它选择了算法,表示和电路结构,并在没有实质性人类干预的情况下产生已发现的电路.

Each architecture proposed during ideation founds a separate family of candidate programs. Later iterations improve descendants of the first working implementation. Keeping the families separate at first gives each approach time to mature, even if its earliest circuits are less efficient than those based on another approach. Periodically, leading programs are shared across families, allowing successful ideas from different approaches to combine.

设想期间提出的每个架构都发现 我们现在有一套不同的候选方案 后来的迭代改进了第一次工作 我们现在的工作 最初使家庭分开,使每种方法都有成熟的时间,即使其最早的电路效率低于基于另一种方法的电路。 定期在家庭之间分享主要方案,使不同方法的成功想法得以结合。

The search retains candidate programs and their evaluation results, tracking which family each belongs to and which earlier program it was derived from. It also saves feedback on failures and short notes in which the LLM records useful insights. These programs, results, and notes carry information between iterations; the sessions do not share a continuously growing conversation.

搜索保留了候选程序及其评价结果,追踪每个家庭属于哪个家庭,以及它从哪个早期的程序中衍生出来. 它还节省了对失败的反馈和短音,LLM记录了有用的见解. 这些程序、结果和说明在迭代之间传递信息;会议没有持续增加的对话。

Each iteration starts a new LLM agent session with the task specification, a parent program to improve, and its evaluation feedback. The agent also receives alternative programs from the archive and their resource costs, brief summaries of earlier attempts, and recorded insights where available. This context is limited; the agent never sees the complete search history. Within the session, it may rewrite the program, run drafts on test inputs, query a classical oracle for the required function on chosen inputs, and use the results to revise its design. It may also delegate focused subtasks to subagents. The iteration ends with submission of a revised program. The evaluator rejects a circuit that does not meet the task specification; a valid one is scored by its $TQ$-cost and considered for retention in its family. Thus the LLM is free to propose broad changes without having to judge their correctness: the evaluator supplies an independent test of every completed design. shows the ideation and rewrite calls and a concrete feedback-and-repair cycle for a small finite-field inversion task.

每个迭代开始一个新的LLM代理会话,其中包含任务规格,改进的母程序,及其评价反馈. 代理商还从档案及其资源成本中接收了替代程序、以往尝试的简要摘要,并记录了已有的见解。 此上下文是有限的;代理从不看到完整的搜索历史. 在会话内中,它可以重写程序,在测试输入上运行草稿,在所选输入上查询需要的函数的经典预告,并利用结果修改其设计. 它还可将重点分任务委托给分代理人。 重复以提交订正方案结束。 评价者拒绝不符合任务规格的电路;有效的电路按其$TQ$ - 成本计分,并考虑保留在家庭内。 因此,LLM可以自由提出大范围的修改,而不必判断其正确性:评估员对每一个完成的设计都提供独立的测试. 显示想法和重写调用,并显示一个具体的反馈和修复循环,用于一个小的有限场反演任务.

To decide which valid candidates remain available within each family, the search retains circuits with different trade-offs between Toffoli count and qubit count. We implement this selection with MAP-Elites [34], which divides the $(T,Q)$ resource plane into cells and keeps the circuit with the lowest $TQ$-cost in each cell. A space-efficient circuit can therefore remain available for later development even when its higher Toffoli count gives it a worse $TQ$-cost.

为了决定每个家族中仍然有哪些有效候选人,搜索保留了Toffoli计数和qubit计数之间有不同权衡的线路. 我们用 MAP-Elites [34] 执行这个选择,它将$(T,Q)$资源平面分割成单元格,并保持每个单元格中成本最低的$TQ$的电路. 因此,即使较高的Toffoli计数使其$TQ$成本更低,高空间效率的电路仍可用于以后的发展。

Because the families preserve alternatives, progress need not be monotonic in either resource. The Gaussian lineage in , for example, contains descendants that temporarily worsen Toffoli count or qubit count before reaching a region of lower $TQ$-cost. We report the lowest $TQ$-cost reached across all families at the end of the search.

由于家庭保留了其他选择,因此在这两种资源中都不必单调地取得进展。 例如, . 中的高斯血统包含一些后代,这些后代暂时使Toffoli计数或qubit计数恶化,然后到达一个较低的$TQ$ - 成本区域. 我们报告,在搜索结束时,所有家庭的费用最低。

References

参考文献

[1] S. P. Jordan, N. Shutty, M. Wootters, A. Zalcman, A. Schmidhuber, R. King, S. V. Isakov, and R. Babbush, Optimization by Decoded Quantum Interferometry, Nature 646 , 831 (2025) , arXiv:2408.08292 .

[2] R. Babbush, D. W. Berry, I. D. Kivlichan, A. Y. Wei, P. J. Love, and A. Aspuru-Guzik, Exponentially more precise quantum simulation of fermions in second quantization, New Journal of Physics 18 , 033032 (2016) .

[3] M. Roetteler, M. Naehrig, K. M. Svore, and K. Lauter, Quantum resource estimates for computing elliptic curve discrete logarithms, in Advances in Cryptology – ASIACRYPT 2017 , Lecture Notes in Computer Science, Vol. 10625 (2017) pp. 241–270, arXiv:1706.06752 .

[4] R. Babbush, C. Gidney, D. W. Berry, N. Wiebe, J. R. McClean, A. Paler, A. G. Fowler, and H. Neven, Encoding electronic spectra in quantum circuits with linear T complexity, Physical Review X 8 , 041015 (2018) .

[5] C. Chevignard, P.-A. Fouque, and A. Schrottenloher, Reducing the number of qubits in quantum factoring, in Advances in Cryptology – CRYPTO 2025, Part II , Lecture Notes in Computer Science, Vol. 16001 (2025) pp. 384–415.

[6] C. Gidney, How to factor 2048 bit RSA integers with less than a million noisy qubits (2025), arXiv:2505.15917 .

[7] Y. Nam, N. J. Ross, Y. Su, A. M. Childs, and D. Maslov, Automated optimization of large quantum circuits with continuous parameters, npj Quantum Information 4 , 23 (2018) .

[8] R. Babbush, A. Zalcman, C. Gidney, M. Broughton, T. Khattar, H. Neven, T. Bergamaschi, J. Drake, and D. Boneh, Securing elliptic curve cryptocurrencies against quantum vulnerabilities: Resource estimates and mitigations, PRX Quantum 7 , 031001 (2026) , arXiv:2603.28846 .

[9] Z. Liang, J. Cheng, R. Yang, H. Ren, Z. Song, D. Wu, X. Qian, T. Li, and Y. Shi, Unleashing the potential of LLMs for quantum computing: A study in quantum architecture design (2023), arXiv:2307.08191 [quant-ph] .

[10] A. Macarone-Palmieri and R. Lo Franco, Quantum circuit generation via test-time learning with large language models (2026), arXiv:2602.03466 [quant-ph] .

[11] V. Giovannetti, S. Lloyd, and L. Maccone, Quantum random access memory, Physical Review Letters 100 , 160501 (2008) , arXiv:0708.1879 .

[12] T. Häner, M. Roetteler, and K. M. Svore, Optimizing quantum circuits for arithmetic (2018a), arXiv:1805.12445 [quant-ph] .

[13] T. Khattar, N. Shutty, C. Gidney, A. Zalcman, N. Yosri, D. Maslov, R. Babbush, and S. P. Jordan, Verifiable quantum advantage via optimized DQI circuits (2025a), arXiv:2510.10967 .

[14] W. van Dam and G. Seroussi, Efficient quantum algorithms for estimating Gauss sums (2002), arXiv:quant-ph/0207131 .

[15] D. J. Bernstein and B.-Y. Yang, Fast constant-time GCD computation and modular inversion, IACR Transactions on Cryptographic Hardware and Embedded Systems 2019 , 340 (2019) .

[16] A. Gu, uncompute (2026).

[17] C. Zalka, Shor’s algorithm with fewer (pure) qubits (2006), arXiv:quant-ph/0601097 .

[18] C. Gidney, Approximate encoded permutations and piecewise quantum adders (2019), arXiv:1905.08488 .

[19] B. Romera-Paredes, M. Barekatain, A. Novikov, M. Balog, M. P. Kumar, E. Dupont, F. J. R. Ruiz, J. S. Ellenberg, P. Wang, O. Fawzi, P. Kohli, and A. Fawzi, Mathematical discoveries from program search with large language models, Nature 625 , 468 (2024) .

[20] A. Novikov, N. Vũ, M. Eisenberger, E. Dupont, P.-S. Huang, A. Z. Wagner, S. Shirobokov, B. Kozlovskii, F. J. R. Ruiz, A. Mehrabian, M. P. Kumar, A. See, S. Chaudhuri, G. Holland, A. Davies, S. Nowozin, P. Kohli, and M. Balog, AlphaEvolve: A coding agent for scientific and algorithmic discovery (2025), arXiv:2506.13131 .

[21] V. P. Su, C. Cao, H.-Y. Hu, Y. Yanay, C. Tahan, and B. Swingle, Discovery of optimal quantum codes via reinforcement learning, Physical Review Applied 23 , 034048 (2025) , arXiv:2305.06378 .

[22] J. Olle, R. Zen, M. Puviani, and F. Marquardt, Simultaneous discovery of quantum error correction codes and encoders with a noise-aware reinforcement learning agent, npj Quantum Information 10 , 126 (2024) , arXiv:2311.04750 [quant-ph] .

[23] G. Yan, S. Li, P. Ma, Q. Zhang, P. Ma, J. Wang, M.-H. Hsieh, and Y. Du, OmniQEC: Discovering practical quantum error-correcting codes by an AI scientist (2026), arXiv:2607.25865 [quant-ph] .

[24] A. G. Fowler, Time-optimal quantum computation (2012), arXiv:1210.4626 .

[25] C. Gidney and A. G. Fowler, Flexible layout of surface code computations using AutoCCZ states (2019), arXiv:1905.08916 .

[26] M. E. Beverland, P. Murali, M. Troyer, K. M. Svore, T. Hoefler, V. Kliuchnikov, G. H. Low, M. Soeken, A. Sundaram, and A. Vaschillo, Assessing requirements to scale to practical quantum advantage (2022), arXiv:2211.07629 .

[27] Anthropic, Claude Opus 5 system card (2026a).

[28] Anthropic, Claude Fable 5 & Claude Mythos 5 system card (2026b).

[29] C. Gidney, Halving the cost of quantum addition, Quantum 2 , 74 (2018) , arXiv:1709.06648 .

[30] C. Gidney and M. Ekerå, How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits, Quantum 5 , 433 (2021) , arXiv:1905.09749 .

[31] C. Gidney, M. Newman, P. Brooks, and C. Jones, Yoked surface codes, Nature Communications 16 , 4498 (2025) , arXiv:2312.04522 [quant-ph] .

[32] D. Litinski and N. Nickerson, Active volume: An architecture for efficient fault-tolerant quantum computers with limited non-local connections (2022), arXiv:2211.15465 .

[33] A. Sharma, OpenEvolve: an open-source evolutionary coding agent (2025).

[34] J.-B. Mouret and J. Clune, Illuminating search spaces by mapping elites (2015), arXiv:1504.04909 .

[35] T. Khattar, N. Shutty, C. Gidney, A. Zalcman, N. Yosri, D. Maslov, R. Babbush, and S. Jordan, Data for “Verifiable Quantum Advantage via Optimized DQI Circuits” (2025b).

[36] P. Wuille, safegcd-bounds: bounds on divsteps iterations in safegcd (2021), exact hull-threshold computation for divstep iteration bounds.

[37] S. Osorio Perez, E. M. Murairi, E. J. Gustafson, and H. Lamm, Primitive quantum gates for an SU(3) discrete subgroup: Σ ⁡ ( 72 × 3 ) \Sigma(72\times 3) (2025), arXiv:2511.17437 [hep-lat] .

[38] A. Schrottenloher, Optimized point addition circuits for elliptic curve discrete logarithms (2026), arXiv:2606.02235 [quant-ph] .

[39] S. Sakata, H. E. Jensen, and T. Høholdt, Generalized Berlekamp–Massey decoding of algebraic-geometric codes up to half the Feng–Rao bound, IEEE Transactions on Information Theory 41 , 1762 (1995) .

[40] H. Luo, Z. Yang, J. Luo, Z. Wang, Y. Su, X. Sun, L. Li, and T. Li, Quantum algorithm for elliptic curve discrete logarithms with space-efficient point addition (2026), arXiv:2607.13816v3 [quant-ph] .

[41] A. Gu and S. P. Jordan, Algebraic geometry codes and Decoded Quantum Interferometry (2025), arXiv:2510.06603 .

[42] E. Prange, The use of information sets in decoding cyclic codes, IRE Transactions on Information Theory 8 , 5 (1962) .

[43] R. T. Chien, Cyclic decoding procedures for Bose-Chaudhuri-Hocquenghem codes, IEEE Transactions on Information Theory 10 , 357 (1964) .

[44] G. D. Forney, Jr., On decoding BCH codes, IEEE Transactions on Information Theory 11 , 549 (1965) .

[45] This agrees with the decoder-stage estimate recomputed from the authors’ released code  [ 35 ] (5.0 million Toffolis, 1,885 qubits) within about 2 % 2% in Toffoli count; the qubit counts differ because the estimate takes stage-wise maxima while the composed circuit retains the Euclidean state during the scan.

[46] J. L. Massey, Shift-register synthesis and BCH decoding, IEEE Transactions on Information Theory 15 , 122 (1969) .

[47] Here a ≥ 0 a\geq 0 and 0 ≤ b ≤ 7 0\leq b\leq 7 .

[48] A. N. Skorobogatov and S. G. Vlăduţ, On the decoding of algebraic-geometric codes, IEEE Transactions on Information Theory 36 , 1051 (1990) .

[49] A. L. Toom, The complexity of a scheme of functional elements simulating the multiplication of integers, Doklady Akademii Nauk SSSR 150 , 496 (1963).

[50] M. Cenk and F. Özbudak, On multiplication in finite fields, Journal of Complexity 26 , 172 (2010) .

[51] H. Stichtenoth, Algebraic Function Fields and Codes , 2nd ed., Graduate Texts in Mathematics, Vol. 254 (Springer, Berlin, Heidelberg, 2009).

[52] J. Proos and C. Zalka, Shor’s discrete logarithm quantum algorithm for elliptic curves, Quantum Information and Computation 3 , 317 (2003) , arXiv:quant-ph/0301141 .

[53] B. C. developers, The safegcd implementation in libsecp256k1 explained .

[54] G. Banegas, D. J. Bernstein, I. van Hoof, and T. Lange, Concrete quantum cryptanalysis of binary elliptic curves, IACR Transactions on Cryptographic Hardware and Embedded Systems 2021 , 451 (2021) .

[55] We draw P P and Q Q independently and nearly uniformly from the points of the curve, omitting the cases on which the affine formulas are incomplete.

[56] An exact worst-case analysis guarantees that every nonzero input modulo p p terminates within 590 divsteps, compared with the circuit’s 533-step schedule  [ 36 ] . Within 533 scheduled steps, an excursion whose swap fires at counter value z = D z=D consumes 2 ​ D + 1 2D+1 steps and stores at most D − 3 D-3 decisions, so a walk can store at most ( 533 − 1 ) / 2 − 3 = 263 (533-1)/2-3=263 decisions. The hatching in Figure   3 (b) extends to this ceiling.

[57] W. J. Cody and W. M. Waite, Software Manual for the Elementary Functions , Prentice-Hall Series in Computational Mathematics (Prentice-Hall, Englewood Cliffs, NJ, 1980).

[58] A. W. Harrow, A. Hassidim, and S. Lloyd, Quantum algorithm for linear systems of equations, Physical Review Letters 103 , 150502 (2009) , arXiv:0811.3171 .

[59] I. D. Kivlichan, N. Wiebe, R. Babbush, and A. Aspuru-Guzik, Bounding the costs of quantum simulation of many-body physics in real space, Journal of Physics A: Mathematical and Theoretical 50 , 305301 (2017) , arXiv:1608.05696 .

[60] Y. Su, D. W. Berry, N. Wiebe, N. Rubin, and R. Babbush, Fault-tolerant quantum simulations of chemistry in first quantization, PRX Quantum 2 , 040332 (2021) , arXiv:2105.12767 .

[61] M. K. Bhaskar, S. Hadfield, A. Papageorgiou, and I. Petras, Quantum algorithms and circuits for scientific computing, Quantum Information and Computation 16 , 197 (2016) , arXiv:1511.08253 .

[62] T. Häner, M. Soeken, M. Roetteler, and K. M. Svore, Quantum circuits for floating-point arithmetic, in Reversible Computation (RC 2018) , Lecture Notes in Computer Science, Vol. 11106 (2018) pp. 162–174, arXiv:1807.02023 .

[63] Throughout this section, round denotes nearest-integer rounding, with half-integer ties away from zero. Because each result is accumulated modulo 2 n 2^{n} in an n n -bit register, we measure the error between a a and b b by the circular distance min m ∈ ℤ ⁡ | a − b + m ​ 2 n | \min_{m\in\mathbb{Z}}|a-b+m2^{n}| , so that values that differ only by wraparound count as close. Behavior outside the promised domain is unrestricted.

[64] D. W. Berry, C. Gidney, M. Motta, J. R. McClean, and R. Babbush, Qubitization of arbitrary basis quantum chemistry leveraging sparsity and low rank factorization, Quantum 3 , 208 (2019) , arXiv:1902.02134 .

[65] S. McArdle, A. Gilyén, and M. Berta, Quantum state preparation without coherent arithmetic, Physical Review Letters 136 , 240603 (2026) , arXiv:2210.14892 .

[66] Y. R. Sanders, D. W. Berry, P. C. S. Costa, L. W. Tessler, N. Wiebe, C. Gidney, H. Neven, and R. Babbush, Compilation of fault-tolerant quantum heuristics for combinatorial optimization, PRX Quantum 1 , 020312 (2020) , arXiv:2007.07391 .

[67] Z. Li and G. K.-L. Chan, Spin-projected matrix product states: Versatile tool for strongly correlated systems, Journal of Chemical Theory and Computation 13 , 2681 (2017) .

[68] S. Sharma, K. Sivalingam, F. Neese, and G. K.-L. Chan, Low-energy spectrum of iron-sulfur clusters directly from many-particle quantum mechanics, Nature Chemistry 6 , 927 (2014) , arXiv:1408.5080 .

[69] G. H. Low, R. King, D. W. Berry, Q. Han, A. E. DePrince, III, A. White, R. Babbush, R. D. Somma, and N. C. Rubin, Fast quantum simulation of electronic structure by spectral amplification, Physical Review X 15 , 041016 (2025) , arXiv:2502.15882 .

[70] A. J. Walker, An efficient method for generating discrete random variables with general distributions, ACM Transactions on Mathematical Software 3 , 253 (1977) .

[71] M. D. Vose, A linear algorithm for generating random numbers with a given distribution, IEEE Transactions on Software Engineering 17 , 972 (1991) .

[72] J. Lee, D. W. Berry, C. Gidney, W. J. Huggins, J. R. McClean, N. Wiebe, and R. Babbush, Even more efficient quantum computations of chemistry through tensor hypercontraction, PRX Quantum 2 , 030305 (2021) , arXiv:2011.03494 .

[73] H. Lamm, S. Lawrence, and Y. Yamauchi, General methods for digital quantum simulation of gauge theories, Physical Review D 100 , 034518 (2019) , arXiv:1903.08807 .

[74] M. Carena, H. Lamm, Y.-Y. Li, and W. Liu, Improved Hamiltonians for quantum simulations of gauge theories, Physical Review Letters 129 , 051601 (2022) , arXiv:2203.02823 [hep-lat] .

[75] The resource estimate of Osorio Perez et al. [37] uses a 10 3 10^{3} lattice. In this work, we use 4 3 4^{3} for ease of evaluation.

[76] E. J. Gustafson, Y. Ji, H. Lamm, E. M. Murairi, S. Osorio Perez, and S. Zhu, Primitive quantum gates for an SU(3) discrete subgroup: Σ ⁡ ( 36 × 3 ) \Sigma(36\times 3) , Physical Review D 110 , 034515 (2024) , arXiv:2405.05973 [hep-lat] .

Extended Data

扩展数据

b = Builder()
x = b.alloc_qubits(4)
h = b.alloc_qubits(4)
t = b.alloc_qubit()
b.ccx(x[0], x[1], t)
# four more products
b.cx(t, h[0])
b.free(t)
b.emit()

b = Builder()
x = b.alloc_qubits(4)
h = b.alloc_qubits(4)
t = b.alloc_qubit()
b.ccx(x[0], x[1], t)
# four more products
b.cx(t, h[0])
m = b.hmr(t)
b.cz(x[0], x[1], cond=m)
b.free(t)
b.emit()

Figure 1: Sample inputs and outputs for inversion in $\mathbb{F}_{2^{4}}$. (a) During ideation, the LLM is given the complete task specification but no prior implementation and returns distinct candidate architectures. (b) During evolution, the input additionally contains a selected parent program, its evaluator feedback, and limited archive context; the LLM returns a proposed rewrite. (c) One such rewrite computes the inverse with five nonlinear products but fails to return an ancilla to $\ket{0}$, so the evaluator rejects it. Seeing this feedback, the LLM adds MBU; the resulting circuit is valid with $T=5$, $Q=10$, and a $TQ$-cost of 50.

b=构建器()
x = b. alloc qubits(4)
h = b. aloc qubits(4)
t = b. alloc qubit( )
b.ccx(x[0],x[1],t)

• 另有4种产品*
  b.cx(t, h[0])
  b. 免费(t)
  3 号 3 号 5 号 5 号 5 号 5 号 6 号 5 号 5 号 5 号 5 号 5 号 5 号 5 号 5 号 5 号 5 号 5 号 5 号 5 号 5 号 5 号 6 号 5 号 5 5 号 6 号 5 5 号 5 号 5 号 5 4 号 5 号 5 4 号 5 号 5 5 号 5 5 5 号 5 5 型 4 4 4 4 号 型 4 型 型 5 4 型 型 5 4 型 4 4 型 型 型 型 4 4 型 4 4 型 4 4 型 型 5 4 型 5 型 型 型 型 型 5 型 型 5 型 型

b=构建器()
x = b. alloc qubits(4)
h = b. aloc qubits(4)
= = = = =
b.ccx(x[0],x[1],t)

• 另有4种产品应成为产品*
  b.c 她在2004年1月1日至2月1日期间完成了下列任务:
  m = b.hmr(t) (中文(简体) ).
  b.cz(x[0],似宜x[1],康德=m)
  b. 免费(t)
  b.emit( )

图1:在$\mathbb{F}_{2^{4}}$中用于倒置的投入和产出样本。 (a) 在设想期间,LLM得到了完整的任务规格,但没有事先执行,返回不同的候选结构。 (b) 在演化过程中,输入中还包含一个选定的母程序、其评价者的反馈和有限的档案上下文;LLM返回一个拟议的重写。 (c)) 一个这样的重写用五种非线性产品计算反向,但是没有将一个角片返回到$\ket{0}$,所以评价者拒绝. 看到这种反馈后,LLM会增加MBU;产生的电路与$T=5$,$Q=10$,以及$TQ$-成本为50.

extendeddatafigure]fig:gaussian-lineage

Figure 2: Search lineage for the Gaussian circuit in the resource plane. Each marker is a distinct valid circuit, colored by the iteration in which it was discovered; arrows point from each parent to its mutated child. Dashed curves are contours of constant $TQ$-cost, which decreases toward the lower left. The ring marks the discovered circuit at $T=1{,}583$ and $Q=139$.

扩展数据图]fig:gaussian-lineage

图2:资源平面中高斯电路的搜索线条. 每一个标记是不同的有效电路,其颜色由发现它时的迭代;箭头从每个父母指向其变异的孩子. 折叠曲线为恒定的$TQ$ - 成本的轮廓,向左下方下降。 该环标志在$T=1{,}583$和$Q=139$发现的电路.

Table 1: Main results across eight compilation tasks. Input/output gives the number of qubits in read-only input registers and target registers, respectively; a target may carry an initial value and be updated in place, and “—” denotes a task with no target register. The correctness columns give the error tolerance and the number of tests. The resource columns report Toffoli count $T$ and peak qubit count $Q$ for the baseline and discovered circuits; $G_{TQ}=(TQ)_{\mathrm{baseline}}/(TQ)_{\mathrm{ours}}$. HHL: Harrow–Hassidim–Lloyd.