betaFeedback

WorksPhysics and Astronomy

Exact verification of Givens rotation circuits for efficient quantum phase estimation of iron-sulfur clusters

Abstract

Givens rotations with angles stored in quantum registers account for much of the cost of published quantum phase estimation algorithms based on double-factorized tensor hypercontraction and spectral amplification. These rotations create superpositions and cannot be verified directly by the basis-state evaluators used to optimize classical reversible circuits. We give an exact verification method that separates out a fixed Clifford change of basis and tracks basis states and phases in the remaining circuit. Integer conditions establish correctness of the full coherent action, including measurement-based uncomputation and restoration of the phase-gradient resource state. Under our interpretation of Low et al.'s angle grid and rotation convention, simplifying the adders lowers the rotation cost relative to the published accounting; fusing the two additions into one masked addition gives an additional saving. We verify both implementations exhaustively at every precision used in the published walks and prove the fused circuit correct for all widths. For benchmarks including FeMoco and other iron-sulfur clusters, replacing only the rotation term lowers total phase-estimation Toffoli counts by 9.5-14.3% under the published error budget, with the walk operator unchanged.

Introduction

Computing the ground-state energy of an active-space model of a metalloenzyme cofactor, such as the iron–molybdenum cofactor (FeMoco) of nitrogenase or an iron–sulfur cluster, is the flagship application of fault-tolerant quantum chemistry [1, 2, 3, 4, 5, 6]. The standard algorithm is quantum phase estimation (QPE) [7] on a qubitized walk operator [8, 9]. Its Toffoli cost is the number of walk steps multiplied by the number of Toffolis per step. The step count grows with the normalization λ\lambda of the Hamiltonian’s block encoding. The lowest published estimates that we know of, by Low et al. [6], combine a double-factorized tensor-hypercontraction (DFTHC) representation with block-invariant symmetry shifts (BLISS) [10] and spectral amplification (SA). Under the error budget used in their Table V, they reach 3.99×1073.99 \times10^{7} Toffolis for the Fe2_2S2_2 cluster of Li and Chan [11] and 1.00×1091.00 \times10^{9} Toffolis for the 76-orbital FeMoco model of Li et al. [2]. For the latter, they state 8.6 hours on 4.5 million physical qubits alongside the preprint’s 9.99×1089.99 \times10^{8} Toffolis (Appendix F).

In this work, 44–72% of the Toffolis of each published step implement networks of Givens rotations whose angles are loaded from a lookup table into quantum registers. Two questions about these rotations bear directly on the published costs. The first is their price. Low et al.’s totals, their cost breakdown and the costing code released with their paper [12] charge 2brot2b_{\mathrm{rot}} Toffolis per rotation, where brotb_{\mathrm{rot}} is the angle precision, but an equation, a table and a passage of their appendices charge brotb_{\mathrm{rot}}. The lower count is the price of a single phase-gradient addition, which applies a single Pauli rotation. That rotates only one of the two Majorana operators of each mode, whereas their select step needs both, and we show that one signed addition of the angle register, if nothing else reads the angle register or alters the phase-gradient register, cannot implement a Givens rotation (Sec. II A, Appendix A.§ 2.2.1). Our baseline is therefore the 2brot2b_{\mathrm{rot}} of their totals and code, and every improvement claimed below is relative to it; if a complete Givens rotation could be done for brotb_{\mathrm{rot}} Toffolis, our constructions would not improve on it, but we know of no such construction.

The second question is verification. A coherent circuit that is wrong on a small fraction of inputs can spoil a computation that applies it 10410^{4} to a few 10510^{5} times, so a cheaper rotation is useful only if it is verified exactly. Basis-state evaluators follow one computational basis state at a time, exhaustively when the input space is small and by sampling otherwise. Gu et al. [13] used such an evaluator in an evolutionary search to score circuits proposed by a large language model (LLM) and written in the kickmix circuit model [14]. Such evaluation is exact for circuits that map basis states to basis states up to a sign, which a Givens rotation does not. Gu et al. note this limitation and, for their chemistry task, the same Fe2_2S2_2 cluster, optimized the sparse Pauli representation [8, 15] instead, reducing the data-dependent part of its walk step from about 55 000 to 15 000 Toffolis.

Our first result extends exhaustive verification to these rotations. Theorem 1 gives four integer conditions for circuits with a fixed change of basis, a basis-permuting core with Z4\mathbb{Z}_{4} phases, and a phase-gradient resource state. The conditions are necessary and sufficient for implementing the target diagonal action in the transformed basis when every rescaled measurement branch must match exactly, including its global phase. The certificate combines standard ingredients: Z4\mathbb{Z}_{4} phases extend sign tracking, the phase-gradient state is an eigenvector of modular addition, and measurement-based uncomputation erases temporaries. After factoring out a fixed change of basis, these ingredients give a complete certificate for a class that contains rotations by loaded angles, their controlled versions and Givens rotations. The class includes exact circuits that a comparison with the textbook adder’s output rejects: the two cheapest rotation circuits below leave the gradient register in a different state on 3/8 of all basis inputs and are correct only because a phase compensates (Sec. III B).

Our second result prices the rotations exactly (Figure 1). A Clifford change of basis diagonalizes the two commuting Pauli rotations of a Givens rotation [16]. With a quantum angle register, the two phase-gradient additions then become one addition masked by a parity qubit. On our reading, Low et al.’s randomized rounding already places every angle on a 2brot−12^{b_{\mathrm{rot}}-1} grid, and the rotation is 2π2\pi-periodic in that angle, so the top angle bit never has to be read. With the top of the arithmetic replaced by Clifford phases [17, 18], the rotation costs 2brot−52^{b_{\mathrm{rot}}}-5 Toffolis. Using two simplified adders on the same grid already costs 2brot−42^{b_{\mathrm{rot}}}-4, so four of the five Toffolis saved per rotation are an accounting correction and one is the fusion (Table I). Every construction on this ladder is verified exhaustively at brot=15b_{\mathrm{rot}}=15, the precision of the Fe2_2S2_2 and FeMoco-76 walks; the rotations with simplified adders and the fused circuit are verified at every width the published walks use, up to 2382^{38} basis states, and the fused one is proved for every width.

The fused Givens rotation

Figure 1. The fused Givens rotation. (a) The three steps from a Givens rotation priced as two additions to an exhaustively checkable circuit. (b) The circuit for G(2πv/2b)G(2\pi v/2^b) on adjacent Jordan–Wigner modes pp, qq. The Clifford unitary F=HpSp†CNOT⁡p→qF = H_pS_p^\dagger\operatorname{CNOT}_{p\to q} turns G(θ)G(\theta) into ∣0⟩⟨0∣q⊗1+∣1⟩⟨1∣q⊗eiθZp\lvert0\rangle\langle0\rvert_q \otimes1 + \lvert1\rangle\langle1\rvert_q \otimes e^{i\theta Z_p}. In the transformed basis, b−1b-1 temporary logical ANDs (∧\wedge) form the masks mi=q∧vim_i = q \wedge v_i; one ripple-carry addition with b−2b-2 temporary-AND carries adds ±m\pm m into the phase-gradient register ∣Gb⟩\lvert G_b\rangle (minus when zp=1z_p=1, through CNOT layers from pp), with the two top gradient bits replaced by S±1S^{\pm1} gates on the bit and carry that would enter them; the top mask bit enters only as the phase CZ⁡(q,vb−1)\operatorname{CZ}(q,v_{b-1}). Masks and carries are erased by XX-basis measurements with CZ fix-ups (MX\mathcal{M}_X). The angle bit vbv_b, worth 2π2\pi on Low et al.’s grid, is never touched. With b=brot−1b=b_{\rm rot}-1 the circuit uses 2brot−52b_{\rm rot}-5 Toffolis, 2brot−52b_{\rm rot}-5 measurements and 2brot−52b_{\rm rot}-5 temporary qubits at peak; the inverse rotation flips the sign. Appendix B lists every gate.

The formulas in Low et al.’s released code reproduce the published costs of all 14 walk steps exactly. We change only the rotation term, giving a matched comparison with the walk operator, λeff\lambda_{\mathrm{eff}}, the number of steps and the error budget unchanged. Toffoli counts fall by 9.5–14.3% for the eight systems under their Table 5 error budget and by 6.1–12.9% for the six of their statistical one, and the fusion accounts for 1.9–2.9 and 1.2–2.6 percentage points of these. For Fe2_2S2_2, phase estimation with σPEA=1\sigma_{\mathrm{PEA}}=1 mHa then needs 3.60×1073.60 \times10^7 Toffolis (3.06×1073.06 \times10^7 with the statistical budget’s σPEA=1.4\sigma_{\mathrm{PEA}}=1.4 mHa); for FeMoco-76, our transcription of the published surface-code model gives 7.81 h instead of 8.71 h on the same hardware. Two readings of Low et al.’s appendix, the angle grid and the angle convention, are assumptions; if either fails, the fused construction one bit wider applies and saves 3 rather than 5 Toffolis per rotation, 2 from simplified adders and 1 from the fusion.

Systembrotb_{\mathrm{rot}}Toffolis per stepSaving (%)QPE Toffolis
Fe2_2S2_2164 814 → 4 4347.9 (1.6)3.33 → 3.06 × 107^7
Fe4_4S4_41811 493 → 10 7936.1 (1.2)1.81 → 1.70 × 108^8
FeMoco-541712 930 → 11 8708.2 (1.6)3.11 → 2.86 × 108^8
FeMoco-761617 588 → 16 0888.5 (1.7)1.00 → 0.92 × 109^9
CPD11712 897 → 11 7578.8 (1.8)4.82 → 4.39 × 108^8
XVIII-56138 554 → 7 45412.9 (2.6)1.72 → 1.50 × 108^8

Table 5.

The fused circuit was developed in interactive sessions with an LLM coding agent (see Acknowledgments), without an automated search. Its correctness at every width is derived in Appendix A2, and the evaluator independently verifies the circuit at each width in use. Whether the evaluator can drive a search, as the kickmix evaluator did for Gu et al., remains open (Sec. VI).

For Fe2_2S2_2, we also compare our estimates with the one implied by Gu et al.’s optimized sparse walk for the same integrals (§ 1.2 B). The two estimates use different representations with different approximation errors. Their difference of almost two orders of magnitude comes from the representation and the associated walk (DFTHC with BLISS and spectral amplification), rather than from either circuit optimization.

Givens rotations with quantum angles

The rotation and its published cost

The DFTHC+BLISS+SA walk of Low et al. applies, in each of its two SEL calls, a basis rotation URotU_{\mathrm{Rot}} and its inverse, each a chain of N−1N-1 Givens rotations on adjacent Jordan–Wigner modes of NN spatial orbitals [6], Appendix B5, with the N−1N-1 angles loaded from a lookup table into quantum registers. A walk step therefore contains 4(N−1)4(N-1) rotations. On adjacent modes p,qp,q,

G(θ)=exp⁡[−iθ2(XpYq−YpXq)]=e−iθ2XpYqeiθ2YpXq,(1)G(\theta)=\exp\left[-\frac{i\theta}{2}\left(X_pY_q-Y_pX_q\right)\right]=e^{-i\frac{\theta}{2}X_pY_q}e^{i\frac{\theta}{2}Y_pX_q}, \tag*{(1)}

a product of two commuting Pauli rotations with the same angle, which rotates the Majorana vector of the pair by θ\theta. Each factor can be applied as one addition of the angle register into a phase-gradient register ∣Gb⟩=2−b/2∑ye−2πiy/2b∣y⟩\lvert G_b\rangle=2^{-b/2}\sum_y e^{-2\pi i y/2^b}\lvert y\rangle, which multiplies the state by e2πiT/2be^{2\pi i T/2^b} when TT is added. Low et al. use such additions (their App. B7), and their counts correspond to brotb_{\mathrm{rot}} Toffolis per brotb_{\mathrm{rot}}-bit addition. Their App. B5 (“each URotU_{\mathrm{Rot}} can be implemented with 2(N−1)brot2(N-1)b_{\mathrm{rot}} Toffoli gates”), their Sec. IV (≈4(N−1)brot\approx4(N-1)b_{\mathrm{rot}} per application of SEL), their Table III (4brot(N−1)4b_{\mathrm{rot}}(N-1) per SEL), the “Select Toffolis” of their Tables X and XII (8(N−1)brot8(N-1)b_{\mathrm{rot}} per step), the totals of their Tables V and XI, and the select cost of their released code [12], 4(N−1)brot4(N-1)b_{\mathrm{rot}} per SEL call, all charge 2brot2b_{\mathrm{rot}} per Givens rotation, two additions. This is our baseline.

Their Eq. (B46) and Table IX instead charge 2(N−1)brot2(N-1)b_{\mathrm{rot}} for the forward and reverse rotations of a SEL call together, and their App. D states that discretizing the angles that “realize the Majorana rotation from γ000\gamma_{000} to γu00\gamma_{u00}” leads to “a Toffoli cost of (N−1)bbits(N-1)b_{\mathrm{bits}}”: one addition per Givens rotation. The same count follows from their description in App. B5 of U(u⃗)U(\vec{u}) as “comprised of N−1N-1 different arbitrary single-qubit rotations” and O(N)O(N) Clifford gates with U†γ00xU=γ~0xU^\dagger\gamma_{00x}U=\tilde{\gamma}_{0x}. A single-qubit rotation between Clifford gates is one Pauli rotation eiϕPe^{i\phi P}, which is what one signed addition of the angle register applies. But Low et al. build URotU_{\mathrm{Rot}} from Givens rotations (their App. B5 and Eq. (B46)), and their Eq. (B21) requires it to rotate both Majorana operators γ00x\gamma_{00x}, x=0,1x=0,1, which their select step applies (their App. B6). A Givens rotation is the product of two Pauli rotations, one for each of the two sets of Majorana operators indexed by xx [Eq. (1)]; a single one, such as eiϕXpYqe^{i\phi X_pY_q}, rotates the operators of one set and commutes with those of the other, so a chain of them, one per angle, satisfies Eq. (B21) for one value of xx only. Appendix A3 gives the general argument for a single rotation: one signed addition of the angle register, if no other gate reads the angle register or alters the gradient register, cannot implement G(θ)G(\theta), under any change of basis, with any other ancillas and up to any global phase. If a complete Givens rotation could be done for brotb_{\rm rot} Toffolis, the FeMoco-76 step would cost 10 129 Toffolis instead of 14 629, and the constructions below would not improve on it; we know of no construction at that price.

Diagonalization by a Clifford change of basis

The Clifford unitary F=HpSp†CNOT⁡p→qF = H_pS_p^\dagger\operatorname{CNOT}_{p\to q} maps the generator of Eq. (1) to −2Zp∣1⟩⟨1∣q-2Z_p\lvert1\rangle\langle1\rvert_q, so

FG(θ)F†=∣0⟩⟨0∣q⊗1+∣1⟩⟨1∣q⊗eiθZp(2)F G(\theta) F^\dagger= \lvert0\rangle\langle0\rvert_q \otimes1 + \lvert1\rangle\langle1\rvert_q \otimes e^{i\theta Z_p} \tag*{(2)}

as derived in Appendix A 2. This is the familiar decomposition of a Givens rotation into CNOTs around a controlled rotation [16], here applied to the rotations of a basis-change network [19, 20]. With a quantum angle register the controlled rotation is a single phase-gradient addition of the angle masked by qq [21, 22]: the control costs b−1b-1 temporary ANDs, and the sign (−1)zp(-1)^{z_p} costs two sets of CNOTs that turn the addition into a subtraction. The mask ANDs read the angle register, so the single-addition restriction of Appendix A 3 does not apply.

The angle grid

Low et al.’s randomized rounding [6 App. D] stores each angle as v=x+Bv=x+B, with x=⌊2brot−1θ/2π⌋x=\lfloor2^{b_{\rm rot}-1}\theta/2\pi\rfloor and BB a random bit that is 11 with probability equal to the fractional part, so every angle is a multiple of 2π/2brot−12\pi/2^{b_{\rm rot}-1} and the rounding is unbiased. (Their prose describes xx as “the first brot−1b_{\rm rot}-1 bits” and BB as “the last bit”; only the stated formula 2π(x+B)/2brot−12\pi(x+B)/2^{b_{\rm rot}-1} gives unbiased rounding, and we follow it.) A brotb_{\rm rot}-bit register is needed only because vv can equal 2brot−12^{b_{\rm rot}-1}, which is the angle 2π2\pi. We read θ\theta as the angle by which URotU_{\rm Rot} rotates the Majorana vector, as their App. D describes the angles (“θ~∈[0,2π)N−1\tilde{\theta}\in[0,2\pi)^{N-1} that realize the Majorana rotation”) and as in Eq. (1); then GG is exactly 2π2\pi-periodic (Appendix A 2), the circuit never reads the top bit, and it runs on the 2b2^b grid with b=brot−1b=b_{\rm rot}-1. A larger register that stores xx and BB separately can store (x+B) mod 2b(x+B)\bmod2^b instead, which changes classical data only. No further bit can be dropped, since G(θ+π)=ZpZqG(θ)G(\theta+\pi)=Z_pZ_qG(\theta).

The fused circuit and the cost ladder

The two most significant qubits of a phase-gradient register form an eigenstate of addition modulo 4, so instead of computing the last carry the circuit applies S±1S^{\pm1} to the bit and the carry that would enter them, and the top mask bit becomes the phase CZ⁡(q,vb−1)\operatorname{CZ}(q,v_{b-1}); this leaves b−2b-2 carries, as in the usual (b−2)(b-2)-Toffoli phase-gradient rotation [17, 18]. Every temporary is erased by an XX-basis measurement and a CZ⁡\operatorname{CZ} fix-up [17], which is correct on both outcomes when the temporary still equals the AND of its inputs when it is measured (Appendix A § 2.1).

The circuit of Figure 1b uses (b−1)+(b−2)=2b−3(b-1)+(b-2)=2b-3 Toffolis, 2brot−52b_{\mathrm{rot}}-5 on Low et al.’s grid.

In Table I, two additions with full adders on a 2brot2^{b_{\mathrm{rot}}} grid reproduce Low et al.’s 2brot2^{b_{\mathrm{rot}}}; on their actual 2brot−12^{b_{\mathrm{rot}}-1} grid they cost 2brot−22b_{\mathrm{rot}}-2; with simplified adders, 2brot−42b_{\mathrm{rot}}-4; fused, 2brot−52b_{\mathrm{rot}}-5. We call the first four Toffolis per rotation, 16(N−1)16(N-1) per walk step, the accounting correction, and the fifth, 4(N−1)4(N-1) per step, the fusion. For Fe2_2S2_2 the correction lowers the step from 3 924 to 3 620 Toffolis and the fusion from 3 620 to 3 544. The combined saving is the reduction from the published costs. Each construction is verified exhaustively at brot=15b_{\mathrm{rot}}=15, and the rotations with simplified adders and the fused rotations on the 2brot−12^{b_{\mathrm{rot}}-1} grid at every width in use (Sec. III).

Exact verification beyond classical functions

Verification conditions

Gu et al.’s evaluator follows one computational-basis trajectory at a time, which is exact for kickmix circuits: reversible classical gates, sign gates, and XX-basis measurements whose outcomes control only sign corrections [13, 14]. The rotations above leave that model in three ways: the change of basis FF is Clifford but not classical, the core uses SS and S†S^\dagger, and the phase-gradient register holds a fixed resource state rather than a classical input.

We consider circuits of the form V=F†CFV=F^\dagger C F, where FF is a fixed unitary on some of the qubits of a control register cc (a Clifford unitary in all our applications), and the core CC is built from XX, CNOT, CZ, ZZ, SS, S†S^\dagger, temporary logical ANDs (one Toffoli each) and their measurement-based uncomputation (an XX-basis measurement of the AND target, a CZ on its inputs when the outcome is 1, and a reset). CC acts on cc, on a bb-qubit resource register yy (b≥2b\geq2) prepared in ∣Gb⟩\lvert G_b\rangle, and on temporaries prepared in ∣0⟩\lvert0\rangle.

Each core gate maps a computational basis state to a single basis state times a power of ii, and measurement outcomes control only diagonal Clifford corrections. On a basis input the core therefore produces a definite output for each measurement record, which a classical simulator can follow.

For a record rr of the MM measurements, let VrV_r denote the corresponding branch of VV, rescaled by 2M/22^{M/2}. For an integer-valued function T(c)T(c), set DT=∑ce2πiT(c)/2b∣c⟩⟨c∣D_T=\sum_c e^{2\pi iT(c)/2^b}\lvert c\rangle\langle c\rvert.

Theorem 1 (Exact verification). For circuits of the form described above, the following conditions on every basis input ∣c,y,0⟩\lvert c,y,0\rangle, y∈Z2by\in\mathbb{Z}_{2^b}, are necessary and sufficient for

VrF†∣c⟩∣Gb⟩∣0⟩V_rF^\dagger\lvert c\rangle\lvert G_b\rangle\lvert0\rangle
=e2πiT(c)/2bF†∣c⟩∣Gb⟩∣0⟩=e^{2\pi iT(c)/2^b}F^\dagger\lvert c\rangle\lvert G_b\rangle\lvert0\rangle

to hold for every record rr and every basis state cc: (a) at every uncomputation, the measured temporary equals the AND of its two inputs; (b) at the end, the temporaries are ∣0⟩\lvert0\rangle and cc is unchanged; (c) the core maps ∣c,y⟩↦ik(c,y)∣c,πc(y)⟩\lvert c,y\rangle\mapsto i^{k(c,y)}\lvert c,\pi_c(y)\rangle with each πc\pi_c a bijection of Z2b\mathbb{Z}_{2^b}; (d) πc(y)−y+2b−2k(c,y)≡T(c)(mod2b)\pi_c(y)-y+2^{b-2}k(c,y)\equiv T(c)\pmod{2^b}. By linearity, each rescaled branch acts as F†DTFF^\dagger D_TF on arbitrary, possibly entangled, control inputs, returns ∣Gb⟩\lvert G_b\rangle and the temporaries unchanged, and acts as the identity on external registers.

The proof is in Appendix A § 2.1. The criterion does not require FF to be Clifford; in our application this choice makes Eq. (2) a short Pauli computation (Appendix A § 2.2). Conditions (c) and (d) give the phase e2πiT(c)/2be^{2\pi iT(c)/2^b} on ∣Gb⟩\lvert G_b\rangle, while (a) makes both normalized measurement branches agree. If a record need only match up to a record-dependent global phase, (a) and (d) can be relaxed (Appendix A § 2.1); a temporary computed as a NAND, for example, fails (a) on every input but changes only the sign of some branches. The class covers rotations eiθPe^{i\theta P} of a Pauli string PP by a loaded angle (with FF mapping PP to Z1Z_1), their controlled versions (through

ConstructionToffolisbrot=15b_{\mathrm{rot}}=15Fe2_2S2_2 stepChecked
Full adders, 2brot2^{b_{\mathrm{rot}}} grida^{a}2brot2b_{\mathrm{rot}}303 924b=15b=15
Full adders2brot−22b_{\mathrm{rot}}-2283 772b=15b=15
Simplified adders2brot−42b_{\mathrm{rot}}-4263 620b=17b=17
Fused2brot−52b_{\mathrm{rot}}-5253 544b=17bb=17^{b}
Simplified adders, 2brot2^{b_{\mathrm{rot}}} grid2brot−22b_{\mathrm{rot}}-2283 772b=17b=17
Fused, 2brot2^{b_{\mathrm{rot}}} gridc^{c}2brot−32b_{\mathrm{rot}}-3273 696b=17bb=17^{b}

Table 1. TABLE I. Exact constructions of a Givens rotation with a quantum angle on the 2brot−12^{b_{\mathrm{rot}}-1} and 2brot2^{b_{\mathrm{rot}}} grids: Toffolis per rotation, the value at brot=15b_{\mathrm{rot}}=15, the resulting Fe2_2S2_2 walk step (76 rotations), and the largest gadget width bb checked exhaustively (every smaller width was checked too); a rotation at precision brotb_{\mathrm{rot}} uses b=brot−1b=b_{\mathrm{rot}}-1 on the 2brot−12^{b_{\mathrm{rot}}-1} grid and b=brotb=b_{\mathrm{rot}} on the 2brot2^{b_{\mathrm{rot}}} grid. Unless marked otherwise, rows use Low et al.’s 2brot−12^{b_{\mathrm{rot}}-1} grid. The rows that are not fused use two half-angle additions. The simplified adders replace arithmetic on the two most significant gradient qubits with Clifford phase gates. a^{a}Low et al.’s count. b^{b}Also proved for every bb (Appendix A § 2.2). c^{c}The fallback if the grid or the angle convention were one bit finer: 2 Toffolis from simplified adders and 1 from the fusion.

mask ANDs), Givens rotations, and products of commuting rotations that share a change of basis. For a Givens rotation, c=(p′,q′,v)c=(p',q',v) collects the system qubits in the transformed basis and the angle register, and T(c)=(−1)p′⊕inv⁡q′(v mod 2b)T(c)=(-1)^{p'\oplus\operatorname{inv}q'}(v\bmod2^b), with inv⁡=0\operatorname{inv}=0 for the forward and 1 for the inverse form, gives DT=D(θ)D_T=D(\theta) of Eq. (2) or its inverse. Appendix A 2 checks (a)–(d) for the fused circuit at arbitrary width; the exhaustive runs below establish them independently at each width used.

What the certificate adds

The four checks in Theorem 1 form a complete certificate after factoring out a fixed change of basis. First, an operation that creates superpositions is verified by following basis states of its core. The change-of-basis identity is established once (Appendix A 2, checked numerically in Table II). At b=14b=14, the fused rotation’s core acts on 56 qubits with 2252^{25} measurement records. The check follows one classical trajectory per basis input, 2322^{32} in all, covering every record at once in 49 s on five processor cores.

CheckScopeResult
Fused rotation, statevector: gadget vs G(2πv/2b)G(2\pi v/2^b), all vv in superposition with random data, every outcome recordb=2b=2–55deviation ≤3.0×10−15\le3.0 \times10^{-15}
Fused rotation, statevector: 4-mode network U†MUU^\dagger M U for M=Z0,X0,Y0M=Z_0, X_0, Y_0b=3b=3deviation ≤1.8×10−17\le1.8 \times10^{-17}
Bit-plane simulator vs statevector, same coreb=2b=2–55deviation ≤2.8×10−15\le2.8 \times10^{-15}
Fused rotation, conditions (a)–(d) of Theorem 1 and counts, every basis stateb=2b=2–1717; 22b+42^{2b+4} states eachno mismatch; 2b−32^b-3 Toffolis
Rotations with full or simplified adders, same conditions, every basis stateb=2b=2–1515; b=2b=2–1717no mismatch; 2b2^b; 2b−22^b-2
Comparison with the textbook adder (gradient register ends in y+Ty+T with phase +1+1) for the three cores, every basis stateb=2b=2–1414full adders: never violated; simplified, fused: violated on 3/8
Change-of-basis identity F†DvF=G(2πv/2b)F^\dagger D_v F=G(2\pi v/2^b) for all vv, and 2π2\pi periodicityfused b=11b=11, 14–17; full and simplified adders: all bbdeviation ≤1.3×10−15\le1.3 \times10^{-15}
Negative controls: grid one bit too fine, no CZ fix-ups, no top-bit SS, no top-mask CZb=14b=14 and 16all detected
Walk-step networks: all 4(N−1)4(N-1) positions, random and edge angles, two stepsthe eight systems of Table IV and Fe4_4S4_4 of Table V, N=20N=20–150deviation ≤6.0×10−15\le6.0 \times10^{-15}

Table II. Checks, forward and inverse forms except the negative controls (forward). Deviations are maximum absolute differences of state amplitudes (statevector rows) or matrix elements (change-of-basis and network rows).

Second, the specification is relational, not functional. Conditions (c) and (d) say exactly that ∣Gb⟩|G_b\rangle is an eigenvector of the core’s phase-permutation with eigenvalue e2πiT(c)/2be^{2\pi iT(c)/2^b}; they do not prescribe the classical map y↦πc(y)y\mapsto\pi_c(y). For the circuits in Table I, the full-adder rotation leaves the gradient register in y+T(c)y+T(c) with phase +1+1 on every basis input, but the simplified and fused rotations do so on only 5/8 of the inputs, at every width b=2,…,14b=2,\ldots,14; on the other 3/8 a phase in Z4\mathbb{Z}_4 compensates a different gradient value, while (d) holds everywhere (Appendix C). An evaluator that compares outputs with a fixed reference, such as the textbook full-adder output, would reject both exact circuits unless its reference were rewritten for each construction. Condition (d) needs no reference. The circuits’ SS gates also lie outside the kick-mix gate set.

Third, under the branch-wise convention a failed condition is an error of the branch operators (Theorem 1): a circuit that passes is exact, and one that fails differs from the target on some input and record, if only by a record-dependent global phase, as for the NAND temporary above.

Exhaustive runs

We implemented the check in a bit-plane simulator that holds one packed plane per qubit and two planes for the phase modulo 4, and applies each gate to 2242^{24} basis states at once with integer operations (Appendix C). For the fused circuit it ran over every (b+1)(b+1)-bit angle value, every gradient basis state, both values of each system qubit, forward and inverse: 22b+42^{2b+4} basis states for each width b=2,…,17b=2,\ldots,17, or 2.7×10112.7\times10^{11} at b=17b=17, which took 62 minutes on seven processor cores. No width shows a phase mismatch, a measurement branch that differs, a gradient map that is not a bijection, a dirty ancilla, a changed angle or system qubit, or a touch of the bit vbv_b, and Toffolis, measurements and peak temporaries are exactly 2b−32b-3 (Figure 2a and Table II). The same evaluator verifies the rotations with full or simplified adders of Table I, two half-angle additions into a (b+1)(b+1)-qubit gradient register, with full adders (2b2b Toffolis) for b≤15b\leq15 and with simplified adders (2b−22b-2) for b≤17b\leq17. Four deliberate faults in the fused circuit are each detected on millions of basis states: a target grid one bit too fine, dropped CZ fix-ups, dropped top-bit SS phases, and a dropped top-mask CZ (Figure 2b). For b≤5b\leq5 a statevector simulator with every measurement-outcome sequence enumerated confirms the full gadget against G(2πv/2b)G(2\pi v/2^b) for all vv at once (3.0×10−153.0\times10^{-15}) and, on four outcome sequences per run, agrees with the bit-plane simulator.

Figure 2. Verification of the fused rotation. (a) Basis states checked exhaustively at each width bb, all with zero phase and zero measurement-branch mismatches; red bars are the widths the published walks use, b=brot−1∈{11,12,14,15,16,17}b=b_{\mathrm{rot}}-1\in\{11,12,14,15,16,17\}, with $2^b-3=19$ to 31 Toffolis. (b) Negative controls on one batch of 2242^{24} basis states at b=14b=14 and $b=16; every fault is caught, while the correct gadget gives zero. Phase mismatches count basis states, branch mismatches count (basis state, measurement) pairs. (c) All 4(N−1)4(N-1) Givens positions of a walk step for each system of Table V, composed in the Majorana representation from the verified gadget unitaries: largest deviation from the exact network, of URot†URotU_{\mathrm{Rot}}^\dagger U_{\mathrm{Rot}} from the identity, of the rotated vector from f(θ)f(\theta), and of each gadget from a Gaussian unitary commuting with ZpZqZ_pZ_q (the check of Eq. (B21) of Ref. [6] is exactly zero); the dashed line is the 10−1210^{-12} tolerance the checks assert.

Each gadget equals a Givens rotation exactly. We compose the gadgets to check the network conventions: the order of URotU_{\mathrm{Rot}}, the inverse gadgets in URot†U_{\mathrm{Rot}}^\dagger, and Low et al.’s eq:B21, which requires URotU_{\mathrm{Rot}} to rotate both Majorana operators of a mode by the same unit vector. Givens rotations are fermionic Gaussian unitaries [20, 23], so a walk step’s 4(N−1)4(N-1) rotations compose as 2N×2N2N\times2N orthogonal matrices. For each system, at its own NN and grid, the network built from the verified gadget unitaries matches the exact network, URot†U_{\mathrm{Rot}}^\dagger undoes URotU_{\mathrm{Rot}}, the two sets of Majorana operators are rotated identically, and the rotated vector equals the spherical-coordinate map v=f(θ)v=f(\theta) of this gate convention (Low et al. do not write ff out), all to 6×10−156\times10^{-15} or better (Figure 2c).

Scope of verification

The verification covers the rotations, 44–72% of each walk step; the lookups, reflections and swaps that make up the other 28–56% are taken from Low et al.’s cost formulas and are neither built nor verified here. Exactness matters because QPE applies the walk coherently 10410^4 to a few 10510^5 times. Gu et al. validated their Fe2_2S2_2 circuit, whose input space of 72 qubits is too large to enumerate, on every table row and 2242^{24} random inputs with sampled measurement records [13]. By their own bounds this gives a defect probability ε≤ln⁡(1/δ)/k≈2.7×10−7\varepsilon\leq\ln(1/\delta)/k\approx2.7\times10^{-7} at confidence 1−δ=0.991-\delta=0.99, and hence a state error per application of at most 2ε≈1.0×10−32\sqrt{\varepsilon}\approx1.0\times10^{-3}, for inputs drawn from their test distribution rather than the states QPE produces; it does not bound the error of 10510^5 coherent applications. For a gadget small enough to enumerate, here 2b+32b+3 qubits besides temporaries, Theorem 1 removes that gap; extending this verification to the rest of the walk is open.

Fe2S2: the matched estimate and a cross-representation comparison

Low et al. and Gu et al. both use the Fe2_2S2_2 active space of Li and Chan, 30 electrons in 20 spatial orbitals [11, 24], which we take from the authors’ public repository.

The DFTHC+BLISS+SA walk step

With N=20N=20 spatial orbitals, DFTHC rank R=14R=14, B=15B=15 basis vectors and C=5C=5 copies per rank, and λeff=6.469\lambda_{\mathrm{eff}}=6.469 Ha, Low et al. report 3 924 Toffolis and 463 logical qubits per step under their Table 5 budget (σPEA=1\sigma_{\mathrm{PEA}}=1 mHa). The formulas of their released code reproduce both numbers exactly, and uniquely within our scan (Appendix D), with the bit precisions of their tbl:X, (bcoeff,brot)=(11,15)(b_{\mathrm{coeff}}, b_{\mathrm{rot}}) = (11, 15), and block exponents (1,3,1,3)(1, 3, 1, 3) for its four QROAM (select-swap) lookups. The step contains 4(N−1)=764(N - 1) = 76 Givens rotations, 2 280 Toffolis or 58.1% (Figure 3b). Using simplified adders on the 2142^{14} grid lowers it to 3 620 Toffolis and the fused rotation to 3 544, an aggregate reduction of 9.7%, of which the fusion contributes 1.9 percentage points (76 Toffolis, or 2.1% of the 3 620-Toffoli step). Over the unchanged 10 162 steps, phase estimation then needs 3.99×1073.99 \times10^{7}, 3.68×1073.68 \times10^{7} and 3.60×1073.60 \times10^{7} Toffolis. In the surface-code model Low et al. use (Appendix F), four AutoCCZ(15,23) magic-state factories [25] at code distance 23 run these circuits in 0.318, 0.294 and 0.288 h on the same 1.35 million physical qubits; the failure probability falls from 0.086 to 0.077. Under their statistical budget (their tbl:XI, σPEA=1.4\sigma_{\mathrm{PEA}} = 1.4 mHa, a different factorization with brot=16b_{\mathrm{rot}} = 16) the cost falls from 3.33×1073.33 \times10^{7} to 3.12×1073.12 \times10^{7} and 3.06×1073.06 \times10^{7} Toffolis (Table V).

Figure 3. Fe2_2S2_2 [30e, 20o]. (a) The two factors of the QPE cost, walk steps and Toffolis per step, for the sparse Pauli walk of Gu et al. (data-dependent part only) and the DFTHC+BLISS+SA walk of Low et al. without and with the fused rotations; dotted lines are constant total Toffolis. Filled markers: σPEA=1\sigma_{\mathrm{PEA}} = 1 mHa; open markers: Low et al.’s statistical budget, σPEA=1.4\sigma_{\mathrm{PEA}} = 1.4 mHa. The two representations differ in their approximations (§ 1.2 B); the circuit-level changes move a point vertically. (b) One DFTHC+BLISS+SA walk step rebuilt from Low et al.’s formulas (their Table V budget) with their rotation cost, with simplified adders on their grid, and with the fused rotations; only the 76 Givens rotations change.

Comparison with the sparse Pauli walk

Gu et al. map the 40 spin-orbitals to 40 qubits and keep Pauli terms with ∣wℓ∣≥10−4|w_{\ell}| \ge10^{-4} Ha, sampled by an alias table [26]. Expanding the Hamiltonian in Majorana monomials, each of which is one Pauli string for any Jordan–Wigner ordering, we find 233 000 nonzero terms and exactly their L=41 052L = 41\,052 after truncation (796 with two Majorana operators, 40 256 with four; Appendix E). Gu et al. do not state the normalization; we find λ=∑ℓ∣wℓ∣=133.465\lambda= \sum_{\ell}|w_{\ell}| = 133.465 Ha (137.260 Ha without truncation), so QPE to σPEA=1\sigma_{\mathrm{PEA}} = 1 mHa needs ⌈πλ/2σPEA⌉=209 647\lceil\pi\lambda/2\sigma_{\mathrm{PEA}}\rceil= 209\,647 walk steps. Their optimized circuit is reported as 1.5×1041.5 \times10^{4} Toffolis and 126 qubits; its components sum to 14 978 Toffolis. It is only the data-dependent part of a step, the alias lookup, the selected Pauli operator and its erasure, without the uniform-state preparations and the reflection. Multiplied by the step count it gives 3.14×1093.14 \times10^{9} Toffolis, and at least 3.04×1093.04 \times10^{9} for any count that rounds to 1.5×1041.5 \times10^{4}; the same estimate for their baseline is 1.15×10101.15 \times10^{10}.

These resource estimates use different representations and approximations, so they do not give a matched comparison of circuits: the 10−410^{-4} Ha cut discards 3.8 Ha of 1-norm, whose effect on the energy is not assessed, while Low et al. estimate their factorization error at 0.013 mHa; a tighter cut would raise λ\lambda and the sparse cost. The sparse figure omits part of the walk step, so it understates that walk’s cost, and we did not try to improve Gu et al.’s circuit. In Table III and Figure 3a, a DFTCH+BLISS+SA step costs fewer Toffolis than the data-dependent part alone of the optimized sparse step, and QPE needs 20.6 times fewer steps, so the published DFTCH+BLISS+SA estimate is already lower than the sparse one by a factor of 79. Our rotations give a further reduction by a factor of 1.11, for an overall factor of about 87 (at least 84, given the rounding of Gu et al.’s count). Of the factor of 20.6 in walk steps, 7.6 comes from the smaller normalization of DFTHC with BLISS, Λ=17.53\Lambda= 17.53 Ha against λ=133.47\lambda= 133.47 Ha, and 2.7 from spectral amplification. Their combined effect is larger than the circuit-level reductions within one walk: factors of 3.7 for the sparse subroutine of Ref. [13] and 1.11 here.

Routeλ\lambda (Ha)StepsToffolis/stepQubitsQPE ToffolisQPE TQTQRun timePhys. qubits
Sparse walk, baseline [13]133.465209 64755 0001391.15×10101.15 \times10^{10}1.6×10121.6 \times10^{12}108 h1.13 M
Sparse walk, LLM-optimized [13]133.465209 64714 9781263.14×1093.14 \times10^{9}4.0×10114.0 \times10^{11}29.4 h1.05 M
DFTHC+BLISS+SA [6]6.46910 1623 9244633.99×1073.99 \times10^{7}1.85×10101.85 \times10^{10}0.318 h1.35 M
+ simplified adders6.46910 1623 6204633.68×1073.68 \times10^{7}1.70×10101.70 \times10^{10}0.294 h1.35 M
+ fused rotations (this work)6.46910 1623 5444633.60×1073.60 \times10^{7}1.67×10101.67 \times10^{10}0.288 h1.35 M

Table III. Phase estimation for Fe2_2S2_2 [30e, 20o] to σPEA=1\sigma_{\mathrm{PEA}} = 1 mHa from the same integrals. The sparse and DFTHC+BLISS+SA rows are stated resource estimates under different representations and approximation errors, not a matched comparison (§ 1.2 B). Sparse rows: Gu et al.’s per-step Toffolis for the data-dependent part only (component sum 14 978 for the optimized circuit, reported 55 000 for the baseline) and qubits, times the step count from our λ\lambda. DFTHC+BLISS+SA rows: Low et al.’s published step, the same with simplified adders on their angle grid, and with the fused rotations; these three are matched. Run times and physical qubits: the surface-code model of Low et al. with four CCZ factories and their layout rule (Appendix F); for the sparse rows they follow from the reported qubit counts and are model estimates, not bounds. TQTQ: Toffolis times logical qubits, Gu et al.’s figure of merit, here for the whole estimation.

FeMoco and the other benchmark systems

Low et al. report eight systems under the error budget of their Table V: Fe2_2S2_2 and Fe4_4S4_4 clusters [11], FeMoco with 54 orbitals [1, 2], a model of the compound I intermediate of cytochrome P450 (CPD1) [27], and a ruthenium CO2_2-fixation catalyst (XVIII) with 56, 100 and 150 orbitals [3]. For every one of them, a scan over the bit precisions and QROAM block sizes finds exactly one parameter set for which the formulas of their released code give their published Toffolis and logical qubits per step, and it uses the bit precisions of their Tables X and XII (Table IV). Their brotb_{\mathrm{rot}} values are 12, 15, 16 and 17, so the fused rotation runs at widths 11, 14, 15 and 16, all verified exhaustively. A step has 4(N−1)4(N - 1) rotations, so it saves 20(N−1)20(N - 1) Toffolis whatever brotb_{\mathrm{rot}} is. The aggregate saving, 9.5–14.3%, is largest where Givens rotations dominate the step and brotb_{\mathrm{rot}} is small; the fusion accounts for 1.9–2.9 percentage points of it.

Our transcription of the surface-code model agrees to within 3% with the two physical estimates that Low et al. state: 8.71 h on 4.37 million physical qubits at d=27d = 27 for FeMoco-76 (they give 8.6 h and 4.5 million), and 2.73 h on 3.22 million at d=27d = 27 for FeMoco-54 (they give 2.7 h and 3.2 million). On the same factories and code distances the run times fall in proportion to the Toffoli counts: for FeMoco-76 from 8.71 h to 7.99 h with simplified adders and to 7.81 h with the fused rotations, and for the largest catalyst model from 24.6 h to 21.9 h (Figure 4b). The failure probability falls with the run time, from 0.079 to 0.071 for FeMoco-76.

Figure 4. All eight systems of Low et al. under their Table V error budget. (a) Saving per walk step relative to the published step, split into the accounting correction (simplified adders on their angle grid, 4 Toffolis per rotation) and the fusion (1 Toffoli per rotation); the number on each bar is the aggregate. (b) Run time of phase estimation in our transcription of their surface-code model with four CCZ factories, on the factory type and code distance chosen for Low et al.’s circuit; diamonds are the run times Low et al. state.

Low et al.’s Table XI gives a second set of estimates for six of the systems, with an error budget that combines the factorization and rounding errors statistically and allows σPEA=1.4\sigma_{\mathrm{PEA}} = 1.4 mHa; they caution that it is not directly comparable to prior work. The formulas in their released code reproduce the costs of all six walk steps exactly (Appendix D). The saving there is 6.1–12.9% (Table V), of which the fusion accounts for 1.2–2.6 percentage points; the width b=17b = 17 that Fe4_4S4_4 needs was verified separately, for the fused rotation and the rotation with simplified adders, on 2382^{38} basis states each. For Fe2_2S2_2 this budget gives the lowest cost in either convention, 3.06×1073.06 \times10^{7} Toffolis.

We keep Low et al.’s logical qubit counts throughout. The fused rotation needs 2brot−52b_{\mathrm{rot}} - 5 temporaries at peak, 19 to 31; their tbl:IX budgets brotb_{\mathrm{rot}} temporaries for the additions, and their released code none for SEL. Low et al. size temporary space by the largest temporary requirement of a step, which for these systems is the outer alias lookup’s 47 to 106 qubits, released before the rotations run, and the rotation’s temporaries fit in it. Counting them separately instead would add brot−5=7b_{\mathrm{rot}} - 5 = 7 to 13 logical qubits relative to tbl:9 (at most 2.2%, for Fe2_2S2_2) or 2brot−52b_{\mathrm{rot}} - 5 relative to the code at most 5.4%), and would change no run time in Table 4. These estimates do not include qubit savings from the angle register, which needs one bit fewer per angle, or the gradient register, which needs one qubit fewer.

SystemNN(bcoeff,brot)(b_{\mathrm{coeff}}, b_{\mathrm{rot}})GivensToffolis per stepSaving (%)QPE Toffolis(ℓ1,ℓ2)(\ell_1,\ell_2), ddRun timePhys. qubits
Fe2_2S2_2 [30e, 20o]20(11, 15)58.1%3 924 → 3 5449.7 (1.9)3.99 → 3.60 × 107^7(15,23), 230.318 → 0.288 h1.35 M
Fe4_4S4_4 [54e, 36o]36(13, 17)64.7%7 356 → 6 6569.5 (1.9)1.73 → 1.57 × 108^8(15,23), 251.38 → 1.25 h2.31 M
FeMoco [54e, 54o]54(9, 16)66.5%10 203 → 9 14310.4 (2.1)3.42 → 3.07 × 108^8(15,23), 272.73 → 2.45 h3.22 M
FeMoco [113e, 76o]76(9, 15)61.5%14 629 → 13 12910.3 (2.1)1.00 → 0.90 × 109^9(17,25), 278.71 → 7.81 h4.37 M
CPD1 [63e, 58o]58(10, 15)71.7%9 535 → 8 39512.0 (2.4)4.91 → 4.32 × 108^8(15,23), 273.92 → 3.45 h3.26 M
XVIII [64e, 56o]56(7, 12)68.7%7 685 → 6 58514.3 (2.9)2.06 → 1.77 × 108^8(15,23), 271.65 → 1.41 h2.72 M
XVIII [100e, 100o]100(8, 16)70.2%18 041 → 16 06111.0 (2.2)1.07 → 0.95 × 109^9(15,25), 299.27 → 8.25 h5.89 M
XVIII [150e, 150o]150(9, 16)69.7%27 367 → 24 38710.9 (2.2)2.83 → 2.52 × 109^9(17,25), 2924.6 → 21.9 h8.68 M

Table 4.

Discussion

Theorem 1 gives exact, complete verification when the non-classical parts of a circuit consist of a fixed change of basis (Clifford in all our applications), phases in Z4\mathbb{Z}_4, and a resource state that is an eigenstate of the core’s permutations. This structure recurs in fault-tolerant algorithms: in rotations by loaded angles, in the basis rotations of double-factorized and tensor-hypercontracted walks [3, 4, 6, 21], and in the controlled rotations of state-preparation trees. Gates whose change of basis is itself controlled, such as controlled Majorana selections, would need an extension of the theorem.

The change in the published costs is mostly a correction of their accounting, and the fused circuit contributes about 2% of a walk step. The estimates depend on the following assumptions. (1) The baseline is the 2brot2b_{\mathrm{rot}} per rotation of Low et al.’s totals and released code (Sec. II A). (2) The 25-Toffoli rotation relies on two readings of Low et al.’s appendix: the 2brot−12^{b_{\mathrm{rot}}-1} grid and the Majorana-rotation convention for θ\theta. If either fails, the angle lives on a 2brot2^{b_{\mathrm{rot}}} grid, on which our negative control shows the circuit would be wrong; the same fused construction at b=brotb = b_{\mathrm{rot}} then applies, at 2brot−32b_{\mathrm{rot}} - 3 Toffolis,

TABLE IV. The eight benchmark systems of Low et al. [6] under their Table V error budget, σPEA=1 mHa\sigma_{\mathrm{PEA}} = 1\,\mathrm{mHa} with ⌈πλeff/2σPEA⌉\lceil\pi\lambda_{\mathrm{eff}}/2\sigma_{\mathrm{PEA}}\rceil steps, unchanged. For each system a scan over brot∈[10,20]b_{\mathrm{rot}} \in[10,20], bcoeff∈[5,16]b_{\mathrm{coeff}} \in[5,16] and four QROAM exponents in [0,7][0,7] finds exactly one parameter set for which the formulas of their released code (Appendix D) give their published Toffolis and logical qubits per step, and it has their stated (bcoeff,brot)(b_{\mathrm{coeff}},b_{\mathrm{rot}}). Saving: aggregate, relative to the published step, and in parentheses the fusion’s part, in percentage points. Run times: four AutoCCZ(ℓ1,ℓ2\ell_1,\ell_2) factories, with the factory type and code distance dd that the model chooses for Low et al.’s circuit kept for ours (Appendix F); physical qubits are the same for both.

TABLE V. Low et al.’s statistical budget (their Table XI, σPEA=1.4 mHa\sigma_{\mathrm{PEA}} = 1.4\,\mathrm{mHa}), all six walk steps rebuilt exactly. Saving as in Table IV; QPE Toffolis without and with the fused rotations.

and the saving per step falls from 20(N−1)20(N-1) to 12(N−1)12(N-1), 8(N−1)8(N-1) from simplified adders and 4(N−1)4(N-1) from the fusion, or 5.7–8.6% under Low et al.’s Table V budget (6.2% for FeMoco-76, 5.8% for Fe2_2S2_2). (3) The surface-code model follows Low et al. in treating Clifford gates and measurements as free; our rotation uses 2brot−52b_{\mathrm{rot}}-5 measurements with classically controlled CZ per rotation, and at four factories each Toffoli takes at least 28.75 μs28.75\,\mu\mathrm{s}, well above the 10 μs10\,\mu\mathrm{s} reaction time, so feed-forward never binds. (4) As in Low et al., the trial state is assumed to have unit ground-state overlap and its preparation [28] is not costed.

The rotation savings can be combined with more factories, concurrent Toffolis or a tighter sum-of-squares gap, all of which leave the rotation network unchanged. The evaluator also offers a possible fitness function for circuit search: it is a few hundred lines of code and checks 2362^{36} basis states in 14 minutes on five processor cores. We have not run such a search. Applying an LLM-guided search such as that of Gu et al. [13] to the complete DFTHC+BLISS+SA walk step, using this evaluator for its non-classical parts and the kickmix evaluator for the measurements with classically controlled CZ per rotation, and at four factories each Toffoli takes at least 28.75 μs28.75\,\mu\mathrm{s}, well above the 10 μs10\,\mu\mathrm{s} reaction time, so feed-forward never binds. (4) As in Low et al., the trial state is assumed to have unit ground-state overlap and its preparation [28] is not costed.

The rotation savings can be combined with more factories, concurrent Toffolis or a tighter sum-of-squares gap, all of which leave the rotation network unchanged. The evaluator also offers a possible fitness function for circuit search: it is a few hundred lines of code and checks 2362^{36} basis states in 14 minutes on five processor cores. We have not run such a search. Applying an LLM-guided search such as that of Gu et al. [13] to the complete DFTHC+BLISS+SA walk step, using this evaluator for its non-classical parts and the kickmix evaluator for the measurements, would test whether exact verification of quantum-angle rotations can lead to further circuit improvements.

Conclusion

Exhaustive basis-state testing verifies not only classical reversible circuits but every circuit of the form described in Sec. III A on phase-gradient resource states. The four verification conditions are sufficient and, under the branch-wise convention, necessary. This class includes the Givens rotations with quantum angles that account for 44–72% of the Toffolis in Low et al.’s walks. We verify each construction on the angle grid that, on our reading, their walk already uses. A rotation with simplified adders costs 2brot−42b_{\mathrm{rot}} - 4 Toffolis per rotation and a fused masked addition costs 2brot−52b_{\mathrm{rot}} - 5, compared with 2brot2b_{\mathrm{rot}} in their totals and released code.

We reproduce the published costs of all 14 walk steps exactly. Replacing the rotations lowers the phase-estimation cost by 9.5–14.3% under Low et al.’s Table V budget and 6.1–12.9% under the statistical budget, with the walk operator unchanged. For Fe2_2S2_2, the resulting cost is 3.60×1073.60 \times10^7 Toffolis (3.06×1073.06 \times10^7 under the statistical budget). For FeMoco-76, our transcription of the surface-code model gives 7.81 h instead of 8.71 h on the same hardware.

Acknowledgments

Claude (Anthropic) assisted with circuit development, verification and analysis code, and manuscript drafting. OpenAI Codex assisted with subsequent manuscript revision. The authors directed the work and checked the results using the verification procedures and analysis scripts described in this paper. The authors take responsibility for the content of the manuscript.

Data availability

The Fe2_2S2_2 integrals of Li and Chan are available at https://github.com/zhendongli2008/Active-space-model-for-Iron-Sulfur-Clusters, and the resource-estimation code of Low et al. is available in Ref. [12]. The circuit implementations, verification and analysis scripts, and numerical results supporting this work are available from the authors on request.

Verification and circuit analysis

Verification criterion

We use the notation of Theorem 1, with b≥2b \ge2 and the resource state

∣Gb⟩=2−b/2∑y=02b−1e−2πiy/2b∣y⟩|G_b\rangle= 2^{-b/2}\sum_{y=0}^{2^b-1}e^{-2\pi i y/2^b}|y\rangle

Proof of Theorem 1. Sufficiency. At each measurement, write the state as ∑zαz∣z¬t⟩∣t(z)⟩\sum_z \alpha_z |z_{\neg t}\rangle|t(z)\rangle. Projection onto ∣±⟩|\pm\rangle contributes 2−1/2(±1)t(z)2^{-1/2}(\pm1)^{t(z)} to each term. By (a), t(z)=a(z)∧b′(z)t(z)=a(z)\wedge b'(z), so the CZ correction cancels the sign for outcome −- . After resetting tt, both branches equal the coherently uncomputed state times 2−1/22^{-1/2} and have probability 1/21/2. Induction over the measurements shows that every rescaled branch follows the outcome-0 map used by the evaluator.

By (b) and (c), that map sends ∣c,y,0⟩|c,y,0\rangle to ik(c,y)∣c,πc(y),0⟩i^{k(c,y)}|c,\pi_c(y),0\rangle. Condition (d) gives

ik(c,y)e−2πiy/2b=e−2πi(πc(y)−T(c))/2b.i^{k(c,y)}e^{-2\pi i y/2^b}=e^{-2\pi i(\pi_c(y)-T(c))/2^b}.

Relabelling y′=πc(y)y'=\pi_c(y) in the resource-state sum therefore gives Cr∣c⟩∣Gb⟩∣0⟩=e2πiT(c)/2b∣c⟩∣Gb⟩∣0⟩C_r|c\rangle|G_b\rangle|0\rangle=e^{2\pi iT(c)/2^b}|c\rangle|G_b\rangle|0\rangle for every rescaled core branch CrC_r. Conjugation by FF yields the claimed action of VrV_r; linearity extends it to arbitrary inputs, including those entangled with other registers.

Necessity. On a basis input z=(c,y,0)z=(c,y,0) the core follows the same basis-state trajectory for every record: measurement outcomes affect only phases, and each measured temporary is reset. Let ej(z)e_j(z) be the value of t⊕(a∧b′)t\oplus(a\wedge b') at measurement jj. Projection onto ∣−⟩|-\rangle and the CZ correction together contribute (−1)ej(z)(-1)^{e_j(z)} relative to outcome ++, so

Cr∣z⟩=(−1)r⋅e(z)ik(z)∣w(z)⟩,C_r|z\rangle=(-1)^{r\cdot e(z)}i^{k(z)}|w(z)\rangle,

where ww and kk are independent of rr. For each fixed cc, the target state has 2b2^b nonzero amplitudes on the states ∣c,y′,0⟩|c,y',0\rangle. The input resource state has exactly 2b2^b terms; if y↦w(c,y)y\mapsto w(c,y) were not injective, the output would have fewer than 2b2^b nonzero amplitudes. Thus w(c,y)=(c,πc(y),0)w(c,y)=(c,\pi_c(y),0) for a bijection πc\pi_c, which gives (b) and (c). Comparing amplitudes for r=0r=0 gives ik(c,y)e−2πiy/2b=e2πi(T(c)−πc(y))/2bi^{k(c,y)}e^{-2\pi i y/2^b}=e^{2\pi i(T(c)-\pi_c(y))/2^b}, which is (d). Comparing with a record whose only outcome is 11 at measurement jj gives (−1)ej(c)=1(-1)^{e_j(c)}=1, which is (a). ▫

If equality is required only up to a record-dependent global phase, (b) and (c) remain unchanged, while (a) allows each ej(z)e_j(z) to be an input-independent bit eje_j and (d) allows an input-independent additive constant t0t_0. The same argument then gives Vr=(−1)r⋅ee2πit0/2bF†DTFV_r=(-1)^{r\cdot e}e^{2\pi i t_0/2^b}F^\dagger D_TF. Our evaluator uses the stricter branch-wise conditions, which all circuits in this paper satisfy.

Givens rotations and the fused circuit

For adjacent Jordan–Wigner qubits p,qp,q, let K=XpYq−YpXqK=X_pY_q-Y_pX_q, so G(θ)=e−iθK/2G(\theta)=e^{-i\theta K/2} as in Eq. (1). Conjugation by CNOTp→q\mathrm{CNOT}_{p\to q} sends KK to Yp(Zq−1)Y_p(Z_q-1); the subsequent Sp†S_p^\dagger and HpH_p send YpY_p to ZpZ_p. Thus

FKF†=Zp(Zq−1)=−2Zp∣1⟩⟨1∣q,FKF^\dagger=Z_p(Z_q-1)=-2Z_p|1\rangle\langle1|_q,

which gives Eq. (2) for every real θ\theta. Also, KK vanishes on ∣00⟩,∣11⟩\lvert00\rangle,\lvert11\rangle and acts as −2σy-2\sigma_y on span⁡{∣01⟩,∣10⟩}\operatorname{span}\{\lvert01\rangle,\lvert10\rangle\}. Hence G(θ)=1⊕eiθσyG(\theta)=1\oplus e^{i\theta\sigma_y} in these two subspaces, so G(θ+2π)=G(θ)G(\theta+2\pi)=G(\theta) and G(θ+π)=ZpZqG(θ)G(\theta+\pi)=Z_pZ_qG(\theta). This is the Majorana-angle convention used in all our checks and read from Low et al.’s App. D. The angle register holds v=∑i=0bvi2iv=\sum_{i=0}^{b}v_i2^i.

For the circuit in Figure 1b (listed in Appendix B), take b≥2b\ge2 and v∈[0,2b+1)v\in[0,2^{b+1}). In the transformed basis, set c=(p′,q′,v)c=(p',q',v), s=(−1)p′⊕inv⁡s=(-1)^{p'\oplus\operatorname{inv}}, and T(c)=sq′(v mod 2b)T(c)=s q'(v\bmod2^b). We check conditions (a)–(d) of Theorem 1 directly. The masks are mi=q∧vim_i=q\land v_i for i≤b−2i\le b-2, computed by b−1b-1 ANDs and erased at the end; qq and vv are never written, so (a) holds for the masks, and M=∑i≤b−2mi2i=q(v mod 2b−1)M=\sum_{i\le b-2}m_i2^i=q(v\bmod2^{b-1}). The signed addition complements every gradient qubit by CNOTs from pp (and an XX in the inverse form) exactly when s=−1s=-1, runs Gidney’s ripple-carry adder [17] on the low b−2b-2 bits, and complements again. The adder computes the carries ci+1=MAJ⁡(mi,yi,ci)c_{i+1}=\operatorname{MAJ}(m_i,y_i,c_i) for i=0,…,b−3i=0,\ldots,b-3 as the AND of mi⊕cim_i\oplus c_i and yi⊕ciy_i\oplus c_i, writes the sum bits while it erases the carries in reverse order, and each carry equals the AND of its restored inputs when it is measured, so (a) holds for the carries. The two top gradient qubits are only complemented and restored.

On a basis state, let Mlow=M mod 2b−2M_{\mathrm{low}}=M\bmod2^{b-2} and let c=cb−2c=c_{b-2} be the carry out of the low b−2b-2 bits. For s=+1s=+1 the low bits become ylow+Mlow−2b−2cy_{\mathrm{low}}+M_{\mathrm{low}}-2^{b-2}c, so y′−y=Mlow−2b−2cy'-y=M_{\mathrm{low}}-2^{b-2}c; for s=−1s=-1 the adder acts on the complement yˉ\bar y, cc is the carry of yˉlow+Mlow\bar y_{\mathrm{low}}+M_{\mathrm{low}}, and complementing back gives y′−y=−(Mlow−2b−2c)y'-y=-(M_{\mathrm{low}}-2^{b-2}c). Either way y′−y=s(Mlow−2b−2c)y'-y=s(M_{\mathrm{low}}-2^{b-2}c), and y↦y′y\mapsto y' is a bijection because the adder is reversible, which is (c). The phase gates are SsS^s on mb−2m_{b-2} and on cc (step 5 of Appendix B) and CZ⁡(q,vb−1)\operatorname{CZ}(q,v_{b-1}), so k≡s(mb−2+c)+2qvb−1≡s(mb−2+c+2qvb−1)(mod4)k\equiv s(m_{b-2}+c)+2qv_{b-1}\equiv s(m_{b-2}+c+2qv_{b-1})\pmod4. Hence

y′−y+2b−2k≡s(Mlow+2b−2mb−2+2b−1qvb−1)=sq(v mod 2b)(mod2b),y'-y+2^{b-2}k\equiv s\left(M_{\mathrm{low}}+2^{b-2}m_{b-2}+2^{b-1}qv_{b-1}\right) =sq(v\bmod2^b)\pmod{2^b},

which is (d). Condition (b) holds because every temporary is erased and the system and angle qubits are only read. Theorem 1 therefore gives the action DTD_T in the transformed basis, with ∣Gb⟩\lvert G_b\rangle and all temporaries restored. Equation (2) and the 2π2\pi periodicity above then give G(2πv/2b)G(2\pi v/2^b) in the forward form and G(2πv/2b)†G(2\pi v/2^b)^\dagger in the inverse form. The bit vbv_b is never read. The b−1b-1 mask ANDs and 2b−32b-3 carry ANDs require 2b−32b-3 Toffolis and 2b−32b-3 measurements. All masks and carries are alive at the top of the adder, so the peak temporary count is also 2b−32b-3. For b=2b=2 there are no carries, Mlow=0M_{\mathrm{low}}=0, y′=yy'=y, and k=s(m0+2qv1)k=s(m_0+2qv_1), giving the same result. Under the angle-grid convention of Section II, substituting this circuit with b=brot−1b=b_{\mathrm{rot}}-1 for each of Low et al.’s 4(N−1)4(N-1) rotations leaves the walk unchanged and saves 5 Toffolis per rotation, or 20(N−1)20(N-1) per step.

Restriction on a single addition

Let b≥2b\ge2 and θj=2πj/2b\theta_j=2\pi j/2^b. Let PP be a Hermitian operator with P2=1P^2=1 on p,qp,q and a ancilla qubits, κ\kappa a real number, ∣α⟩,∣β⟩\lvert\alpha\rangle,\lvert\beta\rangle fixed ancilla states, and W1,W2W_1,W_2 linear maps that do not depend on θ\theta (for these the branch operators of a circuit with measurements). There is no function cc without zeros such that ⟨β∣W2eiκθjPW1∣α⟩=c(θj)G(θj)\langle\beta\lvert W_2e^{i\kappa\theta_jP}W_1\lvert\alpha\rangle=c(\theta_j)G(\theta_j) for j=0,…,2b−1j=0,\ldots,2^b-1.

Since eiκθP=cos⁡(κθ)P+isin⁡(κθ)Pe^{i\kappa\theta P}=\cos(\kappa\theta)P+i\sin(\kappa\theta)P, the left side is cos⁡(κθ)A+sin⁡(κθ)A′\cos(\kappa\theta)A+\sin(\kappa\theta)A' with A,A′A,A' independent of θ\theta, and so is its conjugate by FF. By Eq. (2), FG(θ)F†=D(θ)FG(\theta)F^\dagger=D(\theta), whose matrix elements in the computational basis of (q,p)(q,p) include 11, eiθe^{i\theta} and e−iθe^{-i\theta}. Equality would put the three functions j↦c(θj)j\mapsto c(\theta_j), c(θj)eiθjc(\theta_j)e^{i\theta_j}, c(θj)e−iθjc(\theta_j)e^{-i\theta_j} in the span of j↦cos⁡(κθj),sin⁡(κθj)j\mapsto\cos(\kappa\theta_j),\sin(\kappa\theta_j), which has dimension at most two. Since cc has no zeros, a linear relation among them is one among 1,eiθj,e−iθj1,e^{i\theta_j},e^{-i\theta_j}, which are distinct characters of Z2b\mathbb{Z}_{2^b} for 2b≥42^b\ge4 and hence linearly independent; a contradiction.

A signed addition of the angle register into ∣Gb⟩\lvert G_b\rangle, with the sign set by the parity of a set SS of qubits through CNOTs onto the gradient register (as in Figure 1b), is of this form when no other gate reads the angle register or acts on the gradient register: on each angle value it applies eiκθZSe^{i\kappa\theta Z_S}, conjugated by the surrounding gates, and leaves ∣Gb⟩\lvert G_b\rangle in place. This restriction does not apply to circuits in which other gates read the angle register, Clifford or not, such as the mask ANDs and the CZ⁡(q,vb−1)\operatorname{CZ}(q,v_{b-1}) in Figure 1b, or alter the resource state, for instance by swapping ∣Gb⟩\lvert G_b\rangle with a uniform superposition under control of qq.

Gate-by-gate listing

With p,qp,q the system qubits, v0,…,vbv_0,\ldots,v_b the angle register, y0,…,yb−1y_0,\ldots,y_{b-1} the gradient register (least significant first) and inv⁡∈{0,1}\operatorname{inv}\in\{0,1\}:

  1. Change of basis: CNOT⁡p→q\operatorname{CNOT}_{p\to q}, Sp†S_p^\dagger, HpH_p.

  1. Masks: for i=0,…,b−2i=0,\ldots,b-2, mi←AND⁡(q,vi)m_i\leftarrow\operatorname{AND}(q,v_i) into a fresh temporary.

  1. Sign: for every j<bj<b, CNOT⁡p→yj\operatorname{CNOT}_{p\to y_j}, and XyjX_{y_j} if inv⁡=1\operatorname{inv}=1.

  1. Carries (for b>3b>3): c1←AND⁡(m0,y0)c_1\leftarrow\operatorname{AND}(m_0,y_0); for i=1,…,b−3i=1,\ldots,b-3: CNOT⁡ci→mi\operatorname{CNOT}_{c_i\to m_i}, CNOT⁡ci→yi\operatorname{CNOT}_{c_i\to y_i}, ci+1←AND⁡(mi,yi)c_{i+1}\leftarrow\operatorname{AND}(m_i,y_i), CNOT⁡ci→ci+1\operatorname{CNOT}_{c_i\to c_{i+1}}, CNOT⁡ci→mi\operatorname{CNOT}_{c_i\to m_i}, CNOT⁡ci→yi\operatorname{CNOT}_{c_i\to y_i}.

  1. Top two bits: SS on cb−2c_{b-2} and on mb−2m_{b-2}, each followed by CZ⁡(p,⋅)\operatorname{CZ}(p,\cdot), and by ZZ if inv⁡=1\operatorname{inv}=1 (this gives S±1S^{\pm1} with the sign of the addition); for b=2b=2 only the m0m_0 term.

  1. Erase carries and write sums (for b≥3b\ge3; nothing for b=2b=2): for i=b−3,…,0i=b-3,\ldots,0: for i≥1i\ge1 apply CNOT⁡ci→mi\operatorname{CNOT}_{c_i\to m_i}, CNOT⁡ci→yi\operatorname{CNOT}_{c_i\to y_i}, CNOT⁡ci→ci+1\operatorname{CNOT}_{c_i\to c_{i+1}}; erase

ci+1c_{i+1} by an XX measurement with a CZCZ fix-up on the two AND inputs, which at this point hold mi⊕cim_i \oplus c_i and yi⊕ciy_i \oplus c_i; for i≥1i \ge1 undo the two CNOTs on mim_i and yiy_i; then CNOT⁡mi→yi\operatorname{CNOT}_{m_i\to y_i} and, for i≥1i \ge1, CNOT⁡ci→yi\operatorname{CNOT}_{c_i\to y_i}.

  1. Undo the sign step 3.

  1. Top mask bit: CZ⁡(q,vb−1)\operatorname{CZ}(q,v_{b-1}).

  1. Erase masks: for i=b−2,…,0i=b-2,\ldots,0, XX measurement of mim_i with CZ⁡(q,vi)\operatorname{CZ}(q,v_i) fix-up.

  1. Inverse change of basis: HpH_p, SpS_p, CNOT⁡p→q\operatorname{CNOT}_{p\to q}.

Toffolis: (b−1)+(b−2)=2b−3(b-1)+(b-2)=2b-3. The qubit vbv_b appears nowhere. The rotations with full or simplified adders of Table I replace steps 2–9 by two signed additions of the bb-bit angle into a (b+1)(b+1)-qubit gradient register, one with its sign set by zpz_p and one by zp⊕zqz_p\oplus z_q, each with bb carries (full adder) or b−1b-1 carries and Clifford phase gates on the two most significant gradient qubits (simplified adder).

Evaluator

For a core with control register c=(p′,q′,v)c=(p',q',v) and gradient register yy, the evaluator runs all 22b+12^{2b+1} pairs (v,y)(v,y) for each (p′,q′)(p',q') and each direction, in batches of 2242^{24} basis states with one packed bit plane per qubit and two planes for the phase modulo 4. It checks conditions (a)–(d) of Theorem 1, that vbv_b is never acted on, and the counts of ANDs, measurements and live temporaries. Because (a) makes both outcomes of each measurement give the same state, the simulator follows the outcome-0 trajectory and evaluates (a) on it, which by induction over the measurements covers every record. The change-of-basis identity is also checked numerically for every vv, with the phases taken from the run. For b≤5b\le5 the bit-plane simulator was cross-checked against a statevector simulator running the same core with explicit measurements (four outcome sequences each, including all-0 and all-1), and that statevector simulator checks the full gadget against GG with every outcome sequence; four negative controls test the evaluator itself. These controls exercise failures of (a) and (d); none targets (b) or (c). The network checks use the 2N×2N2N\times2N Majorana transformation Rac=14tr⁡(γcU†γaU)R_{ac}=\frac{1}{4}\operatorname{tr}(\gamma_cU^\dagger\gamma_aU) of each gadget unitary on its two modes, with a residual that measures any non-Gaussian part. The exhaustive runs of the fused circuit take 49 s (b=14b=14), 195 s (b=15b=15) and 833 s (b=16b=16) on five cores and 3727 s (b=17b=17) on seven; those of the rotations with full or simplified adders take 26 minutes in all for b≤16b\le16 on six cores, and 5449 s for the rotation with simplified adders at b=17b=17 on ten.

The comparison with the textbook adder in Sec. III B runs the same enumeration for the full-adder, simplified and fused cores and counts basis inputs on which the gradient register does not end in y+T(c)y+T(c) with phase +1+1. For every b=2,…,14b=2,\ldots,14 the count is zero for the full-adder core and exactly 3/83/8 of all inputs (3/43/4 of those with q′=1q'=1) for the simplified and fused cores, while condition (d) holds on every input of all three. For the fused core this follows from the calculation in Appendix A2: the gradient register changes only in its low b−2b-2 bits, by s(Mlow−2b−2c)s(M_{\mathrm{low}}-2^{b-2}c), which equals T(c)T(c) modulo 2b2^b only when −c≡mb−2+2qvb−1(mod4)-c\equiv m_{b-2}+2qv_{b-1}\pmod4.

Walk-step reconstruction

Low et al. give the Toffolis and qubits of each subroutine of a D F T H C+BLISS+SA walk step as formulas in NN, (R,B,C)(R,B,C), the bit precisions and the block sizes 2k2^k of the QROAM lookups (their App. B7 and Tables VII–IX); their Table III works them out for FeMoco-54. The Givens rotations enter as 4(N−1)brot4(N-1)b_{\mathrm{rot}} per SEL call, 8(N−1)brot8(N-1)b_{\mathrm{rot}} per step (two SEL calls, each with UrotU_{\mathrm{rot}} and Urot†U^\dagger_{\mathrm{rot}}). The version of record revised two formulas of the preprint: the inner QROAM output gains a sign qubit, b2=⌈log⁡(B+1)⌉+bk2+1b_2=\lceil\log(B+1)\rceil+b_{k2}+1 (their Eq. (B36) and Table VIII, against ⌈log⁡(B+1)⌉+bk2\lceil\log(B+1)\rceil+b_{k2} in the preprint), and the inner index register no longer stores cc, which removes ⌈log⁡C⌉\lceil\log C\rceil qubits (their Eq. (B39)); their Table III still uses the preprint’s values. Their released code [12] implements the two versions as the classes SpinFreeData_V1 and SpinFreeData, with ⌈log⁡2B⌉\lceil\log_2 B\rceil in place of ⌈log⁡2(B+1)⌉\lceil\log_2(B+1)\rceil, which differ only when BB is a power of two, and without the sign qubit in the qubit count; the select cost is the same in both. We transcribe the preprint’s formulas and the two classes (Table VI) and, for each system, scan brot∈[10,20]b_{\mathrm{rot}}\in[10,20], bcoeff∈[5,16]b_{\mathrm{coeff}}\in[5,16] and four QROAM exponents in [0,7][0,7], about 5×1055\times10^5 combinations, for exact agreement with the published Toffolis and qubits. Seven of the eight entries of their Table V rebuild exactly with SpinFreeData_V1; the eighth, CPD1, whose entry is unchanged from the preprint and which their driver script builds without the V1 option, rebuilds with SpinFreeData. All six entries of their Table XI, also unchanged from the preprint, rebuild exactly with SpinFreeData; for FeMoco-76 there, with B=64B=64, only its ⌈log⁡2B⌉\lceil\log_2 B\rceil reproduces the entry. Each rebuild has the stated bit precisions and is the only one in the scan, except for Fe2_2S2_2 in their Table XI, where two sets of block exponents give the same costs. The preprint’s Table 5 [6] rebuilds with the preprint’s formulas, which also reproduce the totals of their Table III, 9997 Toffolis and 1131 qubits for FeMoco-54 with the parameters stated there. The fused rotation changes only the 8(N−1)brot8(N-1)b_{\mathrm{rot}} term, to 4(N−1)(2brot−5)4(N-1)(2b_{\mathrm{rot}}-5).

SubroutineToffolis per stepFe2S2\mathrm{Fe}_2\mathrm{S}_2SubroutineToffolis per stepFe2S2\mathrm{Fe}_2\mathrm{S}_2
Outer uniform state8⌈log⁡2L⌉8\lceil\log_2 L\rceil56Inner QROAM inv., swaps2⋅2k4(B+1)2\cdot2^{k_4}(B+1)64
Outer alias QROAM, unary⌈L/2k1⌉\lceil L/2^{k_1}\rceil45Inner uniform states16⌈log⁡2(B+1)⌉16\lceil\log_2(B+1)\rceil64
Outer alias QROAM, swaps2k1b12^{k_1}b_136RPREP angle QROM, unary2(N+RB)2(N+RB)460
Outer alias inv., compareb1b_118RPREP erasure fix-up2(R+B)2(R+B)58
Outer alias inv., unary⌈L/2k5⌉\lceil L/2^{k_5}\rceil12SEL Givens rotations8(N−1)brot8(N-1)b_{\mathrm{rot}}2280
Outer alias inv., swaps2k52^{k_5}8SEL spin controlled swaps4N4N80
Inner QROAM, unary2RC⌈(B+1)/2k2⌉2RC\lceil(B+1)/2^{k_2}\rceil280SEL Majorana control2⋅72\cdot714
Inner QROAM, swaps2⋅2k2b22\cdot2^{k_2}b_2256Reflection T2T_2⌈log⁡2(B+1)⌉+bk2+1\lceil\log_2(B+1)\rceil+b_{k_2}+116
Inner QROAM inv., compare2b22b_232Walk reflection⌈log⁡2L⌉+⌈log⁡2(B+1)⌉+bk1+bk2+2\lceil\log_2 L\rceil+\lceil\log_2(B+1)\rceil+b_{k_1}+b_{k_2}+235
Inner QROAM inv., unary2(N+⌈RC/2k4⌉)2(N+\lceil RC/2^{k_4}\rceil)110
Total (Low et al.: 3924)3924With fused rotations, 4(N−1)(2brot−5)=19004(N-1)(2b_{\mathrm{rot}}-5)=19003544

Table VI. One DFTHC+BLISS+SA walk step for Fe2S2\mathrm{Fe}_2\mathrm{S}_2, from the formulas of Low et al.’s released code (SpinFreeData_V1) with (N,R,B,C)=(20,14,15,5)(N,R,B,C)=(20,14,15,5), bk1=bk2=bcoeff=11b_{k_1}=b_{k_2}=b_{\mathrm{coeff}}=11, brot=15b_{\mathrm{rot}}=15 and QROAM exponents (k1,k2,k4,k5)=(1,3,1,3)(k_1,k_2,k_4,k_5)=(1,3,1,3); L=N+RC=90L=N+RC=90, b1=⌈log⁡2L⌉+bk1=18b_1=\lceil\log_2 L\rceil+b_{k_1}=18, b2=⌈log⁡2B⌉+bk2+1=16b_2=\lceil\log_2 B\rceil+b_{k_2}+1=16. Outer PREP and the reflections run once per step, inner PREP, RPREP and SEL twice.

The logical qubit count is the sum of persistent registers, 2N2N system qubits and the largest temporary register. The persistent registers are the uniform-state register, ⌈log⁡2L⌉+2\lceil\log_2 L\rceil+2; the alias-sampling output, b1+bk1b_1+b_{k1}; the inner QROAM output and indices, (⌈log⁡2B⌉+bk2)+bk2+⌈log⁡2R⌉+2(\lceil\log_2 B\rceil+b_{k2})+b_{k2}+\lceil\log_2 R\rceil+2 in SpinFreeData_V1; the inner uniform-state register, ⌈log⁡2(B+1)⌉+2\lceil\log_2(B+1)\rceil+2; the rotation angles, (N−1)brot(N-1)b_{\mathrm{rot}}; and the phase-gradient register, brotb_{\mathrm{rot}}. For Fe2_2S2_2 these are 9+29+32+6+285+15=3769+29+32+6+285+15=376. The largest temporary is the outer alias QROAM’s, (⌈log⁡2L⌉−2)+2k1b1+⌈log⁡2⌈L/2k1⌉⌉=5+36+6=47(\lceil\log_2 L\rceil- 2) + 2^{k_1}b_1 + \lceil\log_2\lceil L/2^{k_1}\rceil\rceil= 5 + 36 + 6 = 47, so the total is 376+40+47=463376 + 40 + 47 = 463, as published. The full scan results and reconstructed parameters are available from the authors on request, together with the verification and analysis scripts.

Sparse Fe2S2 Hamiltonian

With aj=(γ2j+iγ2j+1)/2a_j = (\gamma_{2j} + i\gamma_{2j+1})/2, the spin-orbital Hamiltonian ∑hpqσapσ†aqσ+12∑(pq∣rs)apσ†aqτ†asτarσ\sum h_{pq}^{\sigma}a_{p\sigma}^{\dagger}a_{q\sigma} + \frac{1}{2}\sum(pq|rs)a_{p\sigma}^{\dagger}a_{q\tau}^{\dagger}a_{s\tau}a_{r\sigma}, read from the FCIDUMP file with PySCF [29], is expanded into sorted Majorana monomials, with signs from reordering and γ2=1\gamma^2 = 1. Each monomial is one Pauli string up to a phase for any Jordan–Wigner ordering, so LL and λ\lambda do not depend on the ordering. Two checks: the coefficients of two- and four-Majorana monomials are purely imaginary and real (residual 5×10−185 \times10^{-18}), and a random 15α/15β15\alpha/15\beta determinant has the same energy from the expansion and from the integrals (2×10−122 \times10^{-12} Ha). The count of terms above the cut is 41 276 at 0.99×10−40.99 \times10^{-4} Ha, 41 052 at 10−410^{-4} Ha and 40 736 at 1.01×10−41.01 \times10^{-4} Ha, so the agreement with Gu et al. pins the cut.

Surface-code model

We transcribe the model of Lee et al. [4] as released in OpenFermion [30], which Low et al. state they use: surface-code patches [31] at physical error rate p=10−3p = 10^{-3} and a 1 μs1\,\mu\mathrm{s} cycle, ⌈1.5nlog⁡⌉\lceil1.5n_{\log}\rceil patches of 2(d+1)22(d+1)^2 physical qubits for nlog⁡n_{\log} logical qubits, two-level AutoCCZ magic-state factories [25] labelled by their code distances (ℓ1,ℓ2)(\ell_1,\ell_2), a per-patch per-cycle failure 0.1(100p)(d+1)/20.1(100p)^{(d+1)/2}, and a total failure budget of 0.10.1. With nF=4n_{\mathrm{F}} = 4 factories each Toffoli takes τ/nF\tau/n_{\mathrm{F}}, where τ\tau is the factory’s time per CCZ state, and the layout minimizes physical qubits times run time over factory types and odd distances. For fixed-hardware comparisons the factory type, factory count and dd chosen for Low et al.’s circuit are kept, and run time and failure are recomputed for ours.

The factories that appear are AutoCCZ(15,23), with a footprint of 138 240 physical qubits, τ=115 μs\tau= 115\,\mu\mathrm{s} and a failure of 1.5×10−101.5 \times10^{-10} per CCZ state; AutoCCZ(15,25), 151 424, 125 μs125\,\mu\mathrm{s} and 6.3×10−116.3 \times10^{-11}; AutoCCZ(17,25), 237 952, 125 μs125\,\mu\mathrm{s} and 1.1×10−111.1 \times10^{-11}; and AutoCCZ(17,27), 188 160, 135 μs135\,\mu\mathrm{s} and 2.0×10−122.0 \times10^{-12}. A run with nTofn_{\mathrm{Tof}} Toffolis takes nTofτ/nFn_{\mathrm{Tof}}\tau/n_{\mathrm{F}}, uses ⌈1.5nlog⁡⌉×2(d+1)2+nF×(footprint)\lceil1.5n_{\log}\rceil\times2(d+1)^2 + n_{\mathrm{F}} \times(\text{footprint}) physical qubits, and fails with probability nTofpCCZ+0.1(100p)(d+1)/2×(patches)×(cycles)n_{\mathrm{Tof}}p_{\mathrm{CCZ}} + 0.1(100p)^{(d+1)/2} \times(\text{patches}) \times(\text{cycles}). For FeMoco-76 the model selects four AutoCCZ(17,25) at d=27d = 27: 31.25 μs\mu\mathrm{s} per Toffoli, 8.71 h, 4.37 million qubits and failure 0.079 for Low et al.’s 1.00×1091.00 \times10^9 Toffolis. Our qubit count is 2.9% below their 4.5 million and our run time 1.3% above their 8.6 h, which their text gives together with the preprint’s 9.99×1089.99 \times10^8 Toffolis; we did not find the source of these differences, and all comparisons are made inside the model. Within the footprint of their FeMoco-76 layout the model’s fastest layout is 7.52 h with five AutoCCZ(17,27) factories for their circuit and 5.21 h with six AutoCCZ(15,25) for ours, but only because the shorter run lets the smaller factory meet the failure budget, at 0.098; we use no result that depends on this threshold. The fastest layouts within a fixed footprint search factory counts 1–80, all factory types and odd d≤59d \le59, with a run time of ∑max⁡(tr,τ/nF)\sum\max(t_r,\tau/n_{\mathrm{F}}) per Toffoli and reaction time tr=10 μst_r = 10\,\mu\mathrm{s}.

References

  1. [1]M. Reiher, N. Wiebe, K. M. Svore, D. Wecker, and M. Troyer, Elucidating reaction mechanisms on quantum computers, Proc. Natl. Acad. Sci. USA 114, 7555 (2017).
  2. [2]Z. Li, J. Li, N. S. Dattani, C. J. Umrigar, and G. K.-L. Chan, The electronic complexity of the ground-state of the FeMo cofactor of nitrogenase as relevant to quantum simulations, J. Chem. Phys. 150, 024302 (2019).DOI
  3. [3]V. von Burg, G. H. Low, T. Håner, D. S. Steiger, M. Reiher, M. Roetteler, and M. Troyer, Quantum computing enhanced computational catalysis, Phys. Rev. Research 3, 033055 (2021).DOI
  4. [4]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).DOI
  5. [5]S. Lee, J. Lee, H. Zhai, Y. Tong, A. M. Dalzell, A. Kumar, P. Helms, J. Gray, Z.-H. Cui, W. Liu, M. Kastoryano, R. Babbush, J. Preskill, D. R. Reichman, E. T. Campbell, E. F. Valeev, L. Lin, and G. K.-L. Chan, Evaluating the evidence for exponential quantum advantage in ground-state quantum chemistry, Nat. Commun. 14, 1952 (2023).DOI
  6. [6]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, Phys. Rev. X 15, 040116 (2025), arXiv:2502.15882.DOI
  7. [7]A. Y. Kitaev, Quantum computations: algorithms and error correction, Russ. Math. Surv. 52, 1191 (1997).DOI
  8. [8]R. Babbush, C. Gidney, D. W. Berry, N. Wiebe, J. McClean, A. Paler, A. Fowler, and H. Neven, Encoding electronic spectra in quantum circuits with linear T complexity, Phys. Rev. X 8, 041015 (2018).DOI
  9. [9]G. H. Low and I. L. Chuang, Hamiltonian simulation by qubitization, Quantum 3, 163 (2019).
  10. [10]I. Loaiza and A. F. Izmaylov, Block-invariant symmetry shift: Preprocessing technique for second-quantized Hamiltonians to improve their decompositions to linear combination of unitaries, J. Chem. Theory Comput. 19, 8201 (2023).arxiv.org/abs/2304.13772
  11. [11]Z. Li and G. K.-L. Chan, Spin-projected matrix product states: Versatile tool for strongly correlated systems, J. Chem. Theory Comput. 13, 2681 (2017).
  12. [12]N. C. Rubin, Fast quantum simulation of electronic structure by spectral amplification: tensor factorizations and resource estimation code, Zenodo (2025), cost formulas in spin_free_block_encoding_costs.py.
  13. [13]A. Gu, A. H. Kemeny, S. F. Yelin, and M. D. Lukin, Discovering state-of-the-art quantum circuits with large language models (2026), arXiv:2610.22367 [quant-ph].arxiv.org/abs/2610.22367
  14. [14]R. Babbush, A. Zalcman, C. Gidney, M. Broughton, T. Khattar, H. Neven, T. Bergamaschi, J. Drake, and D. Boneh, Securing elliptic curve cryptosecurities against quantum vulnerabilities: Resource estimates and mitigations, PRX Quantum 7, 031001 (2026), arXiv:2603.28846.arxiv.org/abs/2603.28846
  15. [15]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).DOI
  16. [16]J. M. Arrazola, O. Di Matteo, N. Quesada, S. Jahangiri, A. Delgado, and N. Killoran, Universal quantum circuits for quantum chemistry, Quantum 6, 742 (2022).DOI
  17. [17]C. Gidney, Halving the cost of quantum addition, Quantum 2, 74 (2018).DOI
  18. [18]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).DOI
  19. [19]I. D. Kivlichan, J. M. McClean, N. Wiebe, C. Gidney, A. Aspuru-Guzik, G. K.-L. Chan, and R. Babbush, Quantum simulation of electronic structure with linear depth and connectivity, Phys. Rev. Lett. 120, 110501 (2018).DOI
  20. [20]Z. Jiang, K. J. Sung, K. K. Kchedzhi, V. N. Smelyanskiy, and S. Boixo, Quantum algorithms to simulate many-body physics of correlated fermions, Phys. Rev. Applied 9, 044036 (2018).
  21. [21]A. Caesura, C. L. Cortes, W. Pol, S. Sim, M. Steudtner, G.-L. R. Anselmetti, M. Degroote, N. Moll, R. Santagati, M. Streif, and C. S. Tautermann, Faster quantum chemistry simulations on a quantum computer with improved tensor factorization and active volume compilation, PRX Quantum 6, 030337 (2025).DOI
  22. [22]A. Caesura, C. L. Cortes, W. Pol, S. Sim, M. Steudtner, G.-L. R. Anselmetti, M. Degroote, N. Moll, R. Santagati, M. Streif, and C. S. Tautermann, Erratum: Faster quantum chemistry simulations on a quantum computer with improved tensor factorization and active volume compilation [PRX Quantum 6, 030337 (2025)], PRX Quantum 7, 049901 (2026).DOI
  23. [23]B. M. Terhal and D. P. DiVincenzo, Classical simulation of noninteracting-fermion quantum circuits, Phys. Rev. A 65, 032325 (2002).DOI
  24. [24]S. Sharma, K. Sivaglingam, F. Neese, and G. K.-L. Chan, Low-energy spectrum of iron–sulfur clusters directly from many-particle quantum mechanics, Nat. Chem. 6, 927 (2014).DOI
  25. [25]C. Gidney and A. G. Fowler, Flexible layout of surface code computations using AutoCCZ states (2019), arXiv:1905.08916.arxiv.org/abs/1905.08916
  26. [26]A. J. Walker, An efficient method for generating discrete random variables with general distributions, ACM Trans. Math. Softw. 3, 253 (1977).DOI
  27. [27]J. J. Goings, A. White, J. Lee, C. S. Tautermann, M. Degroote, C. Gidney, T. Shiozaki, R. Babbush, and N. C. Rubin, Reliably assessing the electronic structure of cytochrome P450 on today’s classical computers and tomorrow’s quantum computers, Proc. Natl. Acad. Sci. USA 119, e2205331119 (2022).DOI
  28. [28]D. W. Berry, Y. Tong, T. Khattar, A. White, T. I. Kim, G. H. Low, S. Boixo, Z. Ding, L. Lin, S. Lee, G. K.-L. Chan, R. Babbush, and N. C. Rubin, Rapid initial state preparation for the quantum simulation of strongly correlated molecules, PRX Quantum 6, 020327 (2025).DOI
  29. [29]Q. Sun et al., Recent developments in the PySCF program package, J. Chem. Phys. 153, 024109 (2020).
  30. [30]J. R. McClean et al., OpenFermion: the electronic structure package for quantum computers, Quantum Sci. Technol. 5, 034014 (2020).arxiv.org/abs/1710.07629
  31. [31]A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, Surface codes: Towards practical large-scale quantum computation, Phys. Rev. A 86, 032324 (2012).DOI

Paper details

vlnc:W_au4992zh
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Claude, Codex

View statement
Looking for related papers…
Contents