betaFeedback

WorksPhysics and Astronomy

Ancilla-free optimal quantum adder

Abstract

We construct an exact nn-bit quantum adder with O(n)O(n) gates and O(log⁡n)O(\log n) depth that requires no ancillary qubits. The circuit uses only XX, CNOT, and Toffoli gates under all-to-all connectivity and is classically reversible. Our construction accelerates the controlled ladder underlying addition. Grouping the data into blocks and use existing control qubits as conditional workspace gives a recursive construction with O(nlog⁡log⁡n)O(n\log\log n) gates and O(log⁡n)O(\log n) depth. We then coordinate inter-block propagation via two short-path forest operations to cut the per-block workspace requirement, yielding a nonrecursive implementation with O(n)O(n) gates. Both the gate count and circuit depth are asymptotically optimal.

Introduction

An nn-bit quantum adder implements

ADD⁡n:(a,b)⟼(a,a+b mod 2n),\begin{equation} \operatorname{ADD}_n:\quad (a,b) \longmapsto (a,a+b\bmod 2^n), \tag*{(1)} \end{equation}

for 0≤a,b<2n0\le a,b<2^n, coherently on arbitrary superpositions. Quantum addition is a fundamental building block of quantum algorithms. It underlies modular arithmetic in algorithms for factoring and discrete logarithms [1, 2], phase rotations in fault-tolerant quantum chemistry simulation [3], and arithmetic oracles for block-encoding structured matrices [4]. These algorithms call addition many times, so the cost of each addition affects the gate count, depth, and ancillary space of the full algorithm. Reducing these costs together is therefore a basic problem in quantum circuit design.

Any exact nn-bit adder over bounded-arity gates requires Ω(n)\Omega(n) gates and Ω(log⁡n)\Omega(\log n) depth, since the most significant output bit depends on all lower input bits. Our construction attains both bounds without ancillary qubits. The circuit uses only XX, CNOT, and Toffoli gates and is therefore classically reversible.

Theorem 1. With all-to-all connectivity, there is an exact nn-bit quantum adder using O(n)O(n) XX, CNOT, and Toffoli gates and O(log⁡n)O(\log n) depth, with no ancillary qubits.

Related works

Ripple-carry adders pass carry information from one bit to the next, giving linear size and depth with little workspace. Cuccaro et al. [6] used one ancillary qubit, and Takahashi, Tani, and Kunihiro [8] achieved both bounds without ancillary qubits. Draper’s Fourier-based adder [5] also avoids ancillary qubits and uses controlled phase rotations.

Carry-lookahead adders compute carry information in parallel, using additional workspace to reduce depth. Draper et al. [7] gave an adder with O(n)O(n) gates and O(log⁡n)O(\log n) depth using O(n)O(n) ancillary qubits. Takahashi, Tani, and Kunihiro [8] reduced the ancillary space to O(n/log⁡n)O(n/\log n) with the same size and depth bounds.

To reduce depth without ancillary qubits, Remaud and Vandaele [11] accelerated the CNOT and Toffoli ladders in ripple-carry addition. Their adder uses O(nlog⁡n)O(n\log n) gates and O(log⁡2n)O(\log^2 n) depth over classical reversible gates. Remaud [12] further related ripple-carry and carry-lookahead adders through Toffoli ladders.

Main techniques

Our starting point is a standard reduction that performs addition using two controlled ladders and CNOT circuits of linear size and logarithmic depth [11, 12]. § 2 recalls this reduction. It leaves us with the task of accelerating the controlled ladder, which maps the data xx to yy while preserving its controls pp:

Tn:(p,x)⟼(p,y),y0=x0,yi=xi+piyi−1(1≤i<n),\begin{equation} \mathcal T_n:(p,x)\longmapsto(p,y),\qquad y_0=x_0,\quad y_i=x_i+p_i y_{i-1}\quad(1\le i<n), \tag*{(2)} \end{equation}

where p=(p1,…,pn−1)p=(p_1,\ldots,p_{n-1}) is the control register and all bit arithmetic is over F2\mathbb F_2: addition is XOR and multiplication is AND. In the direct implementation, each update uses the preceding output, so the gates run one after another. We reduce the depth by computing these contributions in parallel.

We separate propagation within blocks from propagation between blocks. For clarity, assume n=(r+1)bn=(r+1)b and partition the data into r+1r+1 consecutive blocks Bj=(xj,1,…,xj,b)B_j=(x_{j,1},\ldots,x_{j,b}), 0≤j≤r0\le j\le r. The first index identifies the block and the second the position within it; pj,tp_{j,t} controls the transition into that position, except that p0,1p_{0,1} is absent. We use three steps: local ladders send xx to zz; endpoint updates replace zj,bz_{j,b} by yj,by_{j,b}; and interior corrections replace the remaining zj,tz_{j,t} by yj,ty_{j,t}. The first step is a smaller ladder problem. The third simply undoes the local ladder on the interior, adds the incoming contribution to its first bit, and runs the interior ladder again; Figure 2 shows the circuit. We therefore focus on the second step. A contribution from the preceding endpoint reaches the end of block BjB_j only when all controls in that block are one. Their product is the propagation control πj\pi_j. Write ζj=zj,b\zeta_j=z_{j,b} and ηj=yj,b\eta_j=y_{j,b} within this procedure. The endpoints themselves follow a ladder:

η0=ζ0,ηj=ζj+πjηj−1,πj=∏t=1bpj,t(1≤j≤r).\begin{equation} \begin{aligned} \eta_0&=\zeta_0,\qquad \eta_j=\zeta_j+\pi_j\eta_{j-1},\\ \pi_j&=\prod_{t=1}^{b}p_{j,t}\quad(1\le j\le r). \end{aligned} \tag*{(3)} \end{equation}

No extra qubits are available for the endpoint update, so we borrow existing interior bits and restore them afterwards. These bits may start with arbitrary values. We use repeated additions to cancel their initial values while keeping the desired update; we call this an echo. To make this cancellation possible, the Pascal decomposition splits the inverse endpoint map JJ, which sends η\eta back to ζ\zeta, into two operations that square to the identity:

J=Q1Q0,Q02=Q12=I.\begin{equation} J=Q_1Q_0,\qquad Q_0^2=Q_1^2=I. \tag*{(4)} \end{equation}

Four additions between the endpoints and a borrowed register apply each factor and restore that register. Applying Q1Q_1 and then Q0Q_0 gives the required endpoint map.

To compute these additions, we use one control wire in each block as a dirty flag, meaning that its initial value is arbitrary. Write mim_i for the original value of pi,bp_{i,b}. Complement this bit, then add the conjunction χi=∏t=1b−1pi,t\chi_i=\prod_{t=1}^{b-1}p_{i,t} into it. The resulting value fi=1+mi+χif_i=1+m_i+\chi_i satisfies πi=mifi\pi_i=m_if_i. To update an endpoint, we walk through the earlier endpoints and add their controlled contributions. The controls along any part of this walk form an interval product. The identity πi=mifi\pi_i=m_if_i lets us compute it from products of the original and encoded flags.

The remaining controls provide conditional space [9, 10]. Every term added to ζi\zeta_i contains πi\pi_i, so the update vanishes when χi=0\chi_i=0. When χi=1\chi_i=1, complementing these controls gives zero bits for the calculation. Echoes using zero tests apply the calculation only when χi=1\chi_i=1, and two reads cancel the initial values of the borrowed data. A walk with rr stops needs O(r)O(r) such bits. Taking r,b=Θ(n)r,b=\Theta(\sqrt n) gives a linear-size, logarithmic-depth endpoint update. For these larger blocks, an incrementer correction keeps the interior step logarithmic in depth. Running the local ladders recursively then gives the following result.

Theorem 2. With all-to-all connectivity, the controlled ladder and quantum addition admit exact ancilla-free circuits of size O(nlog⁡log⁡n)O(n\log\log n) and depth O(log⁡n)O(\log n) over {X,CNOT,Toffoli}\{X,\mathrm{CNOT},\mathrm{Toffoli}\}.

The extra size factor comes from doing linear work at each of O(log⁡log⁡n)O(\log\log n) recursion levels. Each block needs O(r)O(r) conditional space because its walk can visit all rr earlier endpoints, so the blocks must remain large.

To remove this factor, we decompose JJ into two weighted forest maps of height O(log⁡r)O(\log r). Their edges connect endpoints, with propagation products as weights. Each block now follows a walk of only O(log⁡r)O(\log r) stops, so O(log⁡r)O(\log r) conditional space per block suffices and we can take b=Θ(log⁡n)b=\Theta(\log n). The local ladders and interior corrections then both run directly in logarithmic depth, eliminating recursion. A forest path is a ladder on possibly nonconsecutive endpoints. Each edge crosses a dyadic interval, whose length is a power of two and whose starting point is a multiple of that length. Its control is the product over that interval. We extend the one-block encoding to represent each such interval by one encoded bit and a constant number of original controls. The same Pascal factors, borrowed-register additions, and conditional-space circuit then implement the endpoint update with O(n+rlog⁡r)O(n+r\log r) gates and O(log⁡n)O(\log n) depth. This gives Theorem 1.

Preliminaries

Notation and elementary circuits

We specify each reversible circuit by its action on tuples of bits. Its action on arbitrary quantum states then follows by linearity. We use single indices for the overall ladder and pairs (j,t)(j,t) within blocks: j∈{0,…,r}j\in\{0,\ldots,r\} identifies the block, and t∈{1,…,b}t\in\{1,\ldots,b\} the position within it. Registers are ordered by concatenating their blocks, and arithmetic registers start at the least significant bit. All logarithms are base two. In bit expressions, ++ means XOR and multiplication means AND, so the arithmetic is over F2\mathbb F_2. The indicator [H=0][H=0] is one exactly when every bit of HH is zero. Gate sequences are listed in execution order. Matrix products act on column vectors from right to left.

We count gates from {X,CNOT,Toffoli}\{X,\mathrm{CNOT},\mathrm{Toffoli}\} and assume all-to-all connectivity. Gates in one layer must have disjoint supports, so no wire is used by two gates in the same layer. Borrowed bits provide temporary workspace on existing input wires. A dirty borrowed bit may initially have any value and may be entangled with other registers. The circuit must restore it on arbitrary quantum states, including these entangled inputs.

We handle long control products and increments with the following known circuits [13 Lemmas 1–3 and Theorem 4]. A kk-controlled XX and a kk-bit incrementer each have size O(k)O(k) and depth O(log⁡(k+1))O(\log(k+1)), using one borrowed dirty bit. CNOT ladders, CNOT fanout (adding one source bit to several targets), and the common-control updates ti←ti+cuit_i\leftarrow t_i+c u_i on disjoint pairs (ui,ti)(u_i,t_i) have linear size and logarithmic depth without additional wires. A negative control tests for zero. We obtain it by applying XX to the control wire before and after the controlled gate. An inverse circuit is obtained by reversing its gates, with the same size and depth.

The simplest implementation of Tn\mathcal T_n in (2) runs the Toffoli updates xi←xi+pixi−1x_i\leftarrow x_i+p_i x_{i-1} in increasing order of ii. It acts on nn data bits and n−1n-1 controls, using n−1n-1 gates and depth n−1n-1. We use this direct implementation when the data register is small enough.

Reduction to a controlled ladder

To build the adder, we use two controlled ladders together with linear-size, logarithmic-depth CNOT circuits. We recall the reduction used in ripple-carry addition [8, 11].

Lemma 3 (Ladder-to-adder reduction). An implementation of Tn\mathcal T_n on its 2n−12n-1 input wires with size S(n)S(n) and depth D(n)D(n) gives an nn-bit adder on its two input registers with size 2S(n)+O(n)2S(n)+O(n) and depth 2D(n)+O(log⁡(n+1))2D(n)+O(\log(n+1)).

Proof. The first ladder computes the carry information in the first register. The remaining stages use it to form the sum in the second register and restore the first. Define the difference map by (ΔA)0=A0(\Delta A)_0=A_0 and (ΔA)i=Ai+Ai−1(\Delta A)_i=A_i+A_{i-1} for i≥1i\ge1. Its inverse is the XOR prefix map. Let TB\mathcal T_B denote the ladder on AA whose transition ii is controlled by Bi−1B_{i-1}, and write Bˉi=1+Bi\bar B_i=1+B_i. Starting from (A,B)=(a,b)(A,B)=(a,b), run the following seven stages:

1.B←B+A;2.A←ΔA;3.A←TBA;4.B←B+A;5.A←TBˉ−1A;6.A←Δ−1A;7.B←B+A.\begin{equation} \begin{array}{rll} 1.&B\leftarrow B+A;&2.\quad A\leftarrow\Delta A;\\ 3.&A\leftarrow\mathcal T_B A;&4.\quad B\leftarrow B+A;\\ 5.&A\leftarrow\mathcal T_{\bar B}^{-1}A;&6.\quad A\leftarrow\Delta^{-1}A;\\ 7.&B\leftarrow B+A.& \end{array} \tag*{(5)} \end{equation}

To see how the ladder computes the carry information, let ρi=ai+bi\rho_i=a_i+b_i, and let cic_i be the carry entering position ii in integer addition, with c0=0c_0=0. The usual carry recurrence ci+1=aibi+ρicic_{i+1}=a_i b_i+\rho_i c_i implies that ui=ai+ciu_i=a_i+c_i satisfies

u0=a0,ui=ai+ai−1+ρi−1ui−1(1≤i<n).\begin{equation} u_0=a_0,\qquad u_i=a_i+a_{i-1}+\rho_{i-1}u_{i-1}\quad(1\le i<n). \tag*{(6)} \end{equation}

Thus stage 3 computes A=uA=u, and stage 4 XORs uu into BB, leaving B=ρ+uB=\rho+u. To restore AA, we next erase its carry information. Stage 5 uses the complemented controls in BB. The identity (1+ρi+ui)ui=ρiui(1+\rho_i+u_i)u_i=\rho_i u_i over F2\mathbb F_2 gives

A0=a0,Ai=ui+(1+ρi−1+ui−1)ui−1=ai+ai−1(i≥1).A_0=a_0,\qquad A_i=u_i+(1+\rho_{i-1}+u_{i-1})u_{i-1} =a_i+a_{i-1}\quad(i\ge1).

Stage 6 now restores A=aA=a, and stage 7 leaves B=ρ+cB=\rho+c, the sum bits. This uses two ladder calls. The difference and prefix maps have linear size and logarithmic depth. Complementing the controls takes two parallel XX layers, and the remaining updates are parallel CNOT layers. All stages use the two input registers, with no additional wires. ◻

Pascal matrices

The endpoint update must restore all borrowed bits. We will do this with echoes built from operations that square to the identity. The Pascal matrices give two such operations whose product is the inverse ladder when all controls are one. We first prove this uncontrolled identity, then insert the propagation controls in § 4.1.

Lemma 4 (Pascal factorization). For m≥1m\ge1, let LL be the m×mm\times m matrix with ones on its diagonal and immediately below it, and zeros elsewhere. This is the inverse ladder with all controls equal to one. Then, modulo 22, L=P1P0, L=P_1P_0, where P0P_0 and P1P_1 are lower-triangular matrices given by (P0)ij=(ij) mod 2(0≤j≤i<m),(P1)ij=(i−1j−1) mod 2(1≤j≤i<m). \begin{aligned} (P_0)_{ij}&=\binom{i}{j}\bmod2 &&(0\le j\le i<m),\\ (P_1)_{ij}&=\binom{i-1}{j-1}\bmod2 &&(1\le j\le i<m). \end{aligned} Set (P1)00=1(P_1)_{00}=1 and (P1)i0=0(P_1)_{i0}=0 for i>0i>0. Moreover, P02=P12=IP_0^2=P_1^2=I.

Proof. We first check that each factor squares to the identity. For 0≤j≤i<m0\le j\le i<m, compute the entries modulo 22:

(P02)ij=∑k=ji(ik)(kj)=(ij)∑k=ji(i−jk−j)=2i−j(ij)=[i=j].\begin{aligned} (P_0^2)_{ij} &=\sum_{k=j}^{i}\binom{i}{k}\binom{k}{j}\\ &=\binom{i}{j}\sum_{k=j}^{i}\binom{i-j}{k-j} =2^{i-j}\binom{i}{j}=[i=j]. \end{aligned}

Thus P02=IP_0^2=I. The same calculation on coordinates 1,…,m−11,\ldots,m-1 gives P12=IP_1^2=I. It remains to check that the product is LL. For i≥1i\ge1, Pascal’s identity gives

(P1P0)ij≡∑k=0i−1(i−1k)(k+1j)=∑k=0i−1(i−1k)((kj)+(kj−1))≡[i−1=j]+[i=j](mod2),\begin{aligned} (P_1P_0)_{ij} &\equiv\sum_{k=0}^{i-1}\binom{i-1}{k}\binom{k+1}{j}\\ &=\sum_{k=0}^{i-1}\binom{i-1}{k} \left(\binom{k}{j}+\binom{k}{j-1}\right)\\ &\equiv[i-1=j]+[i=j]\pmod2, \end{aligned}

where binomial coefficients outside their usual range are zero. Row zero is (1,0,…,0)(1,0,\ldots,0), so P1P0=LP_1P_0=L. ◻

A block framework

We first run a ladder inside each block, ignoring the control from the preceding block. This computes the contributions from within each block. We then update the endpoints and use them to supply the missing contributions to the interiors. Figure 1 shows these three steps. Assume n=(r+1)bn=(r+1)b and partition the data into r+1r+1 consecutive blocks of size bb:

Bj=(xj,1,…,xj,b),0≤j≤r.B_j=(x_{j,1},\ldots,x_{j,b}),\qquad 0\le j\le r.

For general nn, take r=⌈n/b⌉−1r=\lceil n/b\rceil-1 and adjust B0B_0 to n−rbn-rb bits. The same construction and asymptotic bounds apply to this partition. Each column in the figure is a block. Its bottom wire (j,b)(j,b) is the endpoint; positions 1,…,b−11,\ldots,b-1 form the interior. The colours track each data wire from its input xj,tx_{j,t}, through the local output zj,tz_{j,t}, to the final output yj,ty_{j,t}.

The control pj,tp_{j,t} for t≥2t\ge2 connects positions t−1t-1 and tt within BjB_j. For j≥1j\ge1, pj,1p_{j,1} connects the preceding endpoint to the first position; p0,1p_{0,1} is absent. Local ladders omit the incoming controls. The recursive construction uses r=Θ(n)r=\Theta(\sqrt n), b=Θ(n)b=\Theta(\sqrt n); the linear-size construction uses r=Θ(n/log⁡n)r=\Theta(n/\log n), b=Θ(log⁡n)b=\Theta(\log n).

Figure 1. The block framework with r=3r=3 and b=4b=4, so n=16n=16. Each column represents one block, with its endpoint at the bottom. Arrows show propagation dependencies.

  1. Local ladders. In panel 1, each column is processed independently: run Tb\mathcal T_b within BjB_j, using only pj,2,…,pj,bp_{j,2},\ldots,p_{j,b}. The blue outputs are

    zj,1=xj,1,zj,t=xj,t+pj,tzj,t−1(2≤t≤b).\begin{equation} z_{j,1}=x_{j,1},\qquad z_{j,t}=x_{j,t}+p_{j,t}z_{j,t-1} \quad(2\le t\le b). \tag*{(9)} \end{equation}

    The block circuits have disjoint supports and run in parallel. If a local ladder has size Sloc(b)S_{\mathrm{loc}}(b) and depth Dloc(b)D_{\mathrm{loc}}(b), the total size is (r+1)Sloc(b)(r+1)S_{\mathrm{loc}}(b) and the depth is Dloc(b)D_{\mathrm{loc}}(b). We may use recursive local ladders or run their Toffoli gates directly in order. The direct implementation uses exactly n−r−1n-r-1 Toffoli gates and has depth b−1b-1.

  2. Endpoint update. In panel 2, only the bottom entries change from blue to green. Write ζj=zj,b\zeta_j=z_{j,b} and ηj=yj,b\eta_j=y_{j,b} within this procedure. These endpoints form a ladder of their own:

    η0=ζ0,ηj=ζj+πjηj−1,πj=∏t=1bpj,t(1≤j≤r).\begin{equation} \eta_0=\zeta_0,\qquad \eta_j=\zeta_j+\pi_j\eta_{j-1},\qquad \pi_j=\prod_{t=1}^{b}p_{j,t}\quad(1\le j\le r). \tag*{(10)} \end{equation}

    Thus this step implements (p,ζ)↦(p,η)(p,\zeta)\mapsto(p,\eta). The circuit evaluates each πj\pi_j from the original block controls. It may temporarily modify those controls and borrow interior data, but it must restore both, leaving the interiors at zj,tz_{j,t}. Its size SendS_{\mathrm{end}} and depth DendD_{\mathrm{end}} include all control evaluation and restoration. The following sections give two implementations of this step.

  3. Interior correction. In panel 3, each corrected endpoint supplies the missing contribution to the next block’s interior. Block B0B_0 is already correct. For j≥1j\ge1, follow the three parts of Figure 2. First undo the local ladder on positions 1,…,b−11,\ldots,b-1, recovering xj,1,…,xj,b−1x_{j,1},\ldots,x_{j,b-1}. Next add pj,1yj−1,bp_{j,1}y_{j-1,b} to the first bit with one Toffoli gate. Finally, run the interior ladder forward again. It carries this incoming contribution through the block, giving

    yj,t=zj,t+yj−1,b∏u=1tpj,u,1≤t<b.\begin{equation} y_{j,t}=z_{j,t} +y_{j-1,b}\prod_{u=1}^{t}p_{j,u}, \qquad 1\le t<b. \tag*{(11)} \end{equation}

    Figure 2. Interior correction for b=4b=4 and j≥1j\ge1. Undo the two interior gates, add the incoming contribution, and replay the two gates. Both endpoints and all controls are preserved.

    The circuit leaves both endpoints and all controls unchanged and needs no borrowed bits. Each block uses its incoming endpoint and leaves its outgoing endpoint to the next block, so all corrections run in parallel, giving total size O(n)O(n) and depth O(b)O(b).

Lemma 5 (Block reduction). For the partition above, suppose the local ladders have ancilla-free implementations of size Sloc(b)S_{\mathrm{loc}}(b) and depth Dloc(b)D_{\mathrm{loc}}(b). Suppose the endpoint update has size SendS_{\mathrm{end}} and depth DendD_{\mathrm{end}}, using only existing wires and restoring the controls and all borrowed interior data. Then Tn\mathcal T_n has an ancilla-free implementation satisfying S(n)≤(r+1)Sloc(b)+Send+O(n),D(n)≤Dloc(b)+Dend+O(b). \begin{aligned} S(n)&\le(r+1)S_{\mathrm{loc}}(b) +S_{\mathrm{end}}+O(n),\\ D(n)&\le D_{\mathrm{loc}}(b) +D_{\mathrm{end}}+O(b). \end{aligned} The incrementer correction in § 4.3 reduces the last depth term to O(log⁡(b+1))O(\log(b+1)).

The recursive construction

The block framework leaves us with the endpoint update in Step 2 of § 3. We first reduce this update to additions between the endpoint register and a borrowed register. We then compute these additions in parallel inside the blocks, restoring all controls and borrowed interior data.

Reducing the endpoint ladder to additions

Recall that the endpoints must satisfy ηi=ζi+πiηi−1\eta_i=\zeta_i+\pi_i\eta_{i-1}, with η0=ζ0\eta_0=\zeta_0. We work with the inverse map

J:η⟼ζ,ζ0=η0,ζi=ηi+πiηi−1(1≤i≤r),\begin{equation} J:\eta\longmapsto\zeta,\qquad \zeta_0=\eta_0,\quad \zeta_i=\eta_i+\pi_i\eta_{i-1}\quad(1\le i\le r), \tag*{(13)} \end{equation}

because its Pascal decomposition will let us restore the borrowed bits. Reversing its circuit gives the required update. For the controls between two endpoints, write

Π(j,i)=∏ν=j+1iπν(0≤j≤i≤r),Π(i,i)=1.\Pi(j,i)=\prod_{\nu=j+1}^{i}\pi_\nu \quad(0\le j\le i\le r),\qquad \Pi(i,i)=1.

The circuit evaluates these products from the original controls.

We have only borrowed interior bits for this update. We therefore decompose JJ into operations that square to the identity, so that an echo can apply each operation and restore the borrowed bits. The Pascal factorization gives this decomposition.

Pascal decomposition.

Weight each entry of the matrices in Lemma 4 by the control product between its indices. For P0P_0, this gives

(Q0)ij=((ij) mod 2)Π(j,i)(0≤j≤i≤r),\begin{equation} (Q_0)_{ij}=\left(\binom{i}{j}\bmod2\right)\Pi(j,i) \quad(0\le j\le i\le r), \tag*{(14)} \end{equation}

with zeros above the diagonal. Define Q1Q_1 in the same way using P1P_1. In a matrix product, the weights from jj to kk and from kk to ii multiply to Π(j,i)\Pi(j,i), independent of kk. The identities of Lemma 4 therefore give

J=Q1Q0,Q02=Q12=I.\begin{equation} J=Q_1Q_0,\qquad Q_0^2=Q_1^2=I. \tag*{(15)} \end{equation}

Applying Q1Q_1 and then Q0Q_0 implements J−1J^{-1}.

Using a borrowed register.

We focus on Q0Q_0; the construction for Q1Q_1 is the same with both Pascal indices decreased by one and coordinate zero fixed. Write Q0=I+AQ_0=I+A. Our goal is to apply I+AI+A through additions between ζ\zeta and the borrowed ZZ, restoring ZZ afterwards. We already have A2=(Q0+I)2=0A^2=(Q_0+I)^2=0. For the cancellation, we also use the fixed backward shift

(Du)i=ui+1(0≤i<r),(Du)r=0.(Du)_i=u_{i+1}\quad(0\le i<r),\qquad (Du)_r=0.

Thus, in DADA, the output of row ii is added at position i−1i-1. This shift makes the echo work through the identity ADA=AADA=A. For i>ji>j,

(ADA)ij≡Π(j,i)∑k=ji−1(ik)(k+1j)≡Π(j,i)(ij)=Aij(mod2).\begin{equation} \begin{aligned} (ADA)_{ij} &\equiv\Pi(j,i)\sum_{k=j}^{i-1} \binom{i}{k}\binom{k+1}{j}\\ &\equiv\Pi(j,i)\binom{i}{j}=A_{ij}\pmod2. \end{aligned} \tag*{(16)} \end{equation}

The two weights cover the full interval from jj to ii and both contain πk+1\pi_{k+1}. Since πk+12=πk+1\pi_{k+1}^2=\pi_{k+1}, their product is Π(j,i)\Pi(j,i). For the second equality, add the terms k=ik=i and, when j>0j>0, k=j−1k=j-1. The enlarged sum is zero by Pascal’s rule and the calculation in Lemma 4. Removing these terms leaves (i+1j)+(ij−1)≡(ij)(mod2)\binom{i+1}{j}+\binom{i}{j-1}\equiv\binom{i}{j}\pmod2. All other entries vanish. Decreasing the Pascal indices gives the same two identities for A=Q1−IA=Q_1-I.

These identities give a circuit using r+1r+1 borrowed interior bits for ZZ, disjoint from the endpoints:

(ζ,Z)→ζ←ζ+AZ(ζ+AZ,Z)→Z←Z+DAζ(ζ+AZ,Z+DAζ)→ζ←ζ+AZ(ζ+Aζ,Z+DAζ)→Z←Z+DAζ((I+A)ζ,Z).\begin{equation} \begin{aligned} (\zeta,Z) &\xrightarrow{\zeta\leftarrow\zeta+AZ} (\zeta+AZ,Z)\\ &\xrightarrow{Z\leftarrow Z+DA\zeta} (\zeta+AZ,Z+DA\zeta)\\ &\xrightarrow{\zeta\leftarrow\zeta+AZ} (\zeta+A\zeta,Z+DA\zeta)\\ &\xrightarrow{Z\leftarrow Z+DA\zeta} ((I+A)\zeta,Z). \end{aligned} \tag*{(17)} \end{equation}

The state expressions use the initial values of ζ,Z\zeta,Z. In the second addition, A2=0A^2=0 removes the dependence on the first change to ζ\zeta. In the third, the two copies of AZAZ cancel and ADA=AADA=A leaves the desired AζA\zeta. The last addition restores ZZ because DA2=0DA^2=0. Thus four additions apply the factor and restore the borrowed register, whatever its initial state.

We have reduced the endpoint update to eight additions, four per factor. For A=Q0−IA=Q_0-I, the first addition is

ζi⟼ζi+∑j=0i−1((ij) mod 2)Π(j,i)Zj(1≤i≤r),\begin{equation} \zeta_i\longmapsto\zeta_i+ \sum_{j=0}^{i-1}\left(\binom{i}{j}\bmod2\right)\Pi(j,i)Z_j \quad(1\le i\le r), \tag*{(18)} \end{equation}

with coordinate zero unchanged. It is enough to construct this addition while preserving ZZ and restoring the controls and temporary data. The other additions exchange the registers or redirect row ii to position i−1i-1.

Parallel walks along the chain

To compute the control products in (18), we separate each block’s last control from its remaining controls. Write

Hi=(pi,1,…,pi,b−1),χi=∏t=1b−1pi,t,mi=pi,b.\begin{equation} H_i=(p_{i,1},\ldots,p_{i,b-1}),\qquad \chi_i=\prod_{t=1}^{b-1}p_{i,t},\qquad m_i=p_{i,b}. \tag*{(19)} \end{equation}

The block control is πi=miχi\pi_i=m_i\chi_i. We want to express this product using the last control’s value before encoding and its value afterwards. Use that wire as a dirty flag and apply

Ei:pi,b⟵pi,b+1+χi.\begin{equation} \mathcal E_i:\quad p_{i,b}\longleftarrow p_{i,b}+1+\chi_i. \tag*{(20)} \end{equation}

Call the new value fif_i. If mi=1m_i=1, then fi=χif_i=\chi_i; if mi=0m_i=0, then πi=0\pi_i=0. Thus, on every input,

fi=1+mi+χi,πi=mifi.\begin{equation} f_i=1+m_i+\chi_i,\qquad \pi_i=m_if_i. \tag*{(21)} \end{equation}

Figure 3 implements this encoding with one XX and one multi-controlled XX. The latter borrows and restores an interior bit wiw_i. All blocks run in parallel, so E=∏iEi\mathcal E=\prod_i\mathcal E_i has size O(rb)O(rb) and depth O(log⁡(b+1))O(\log(b+1)). It preserves HiH_i and is its own inverse.

Figure 3. Using pi,bp_{i,b} as a dirty flag for χi\chi_i. The filled control on HiH_i tests that all its bits are one. The multi-controlled XX borrows and restores wiw_i.

To compute the sum for ζi\zeta_i in (18), follow the chain i→i−1→⋯→0i\to i-1\to\cdots\to0. We call this a walk, with a stop at each earlier endpoint jj. The contribution from ZjZ_j is controlled by

Π(j,i)=M(j,i)F(j,i),M(j,i)=∏ν=j+1imν,F(j,i)=∏ν=j+1ifν.\begin{equation} \Pi(j,i)=M(j,i)F(j,i),\qquad M(j,i)=\prod_{\nu=j+1}^{i}m_\nu,\qquad F(j,i)=\prod_{\nu=j+1}^{i}f_\nu. \tag*{(22)} \end{equation}

We therefore need to perform

ζi⟼ζi+∑j=0i−1((ij) mod 2)M(j,i)F(j,i)Zj.\zeta_i\longmapsto\zeta_i+ \sum_{j=0}^{i-1}\left(\binom{i}{j}\bmod2\right) M(j,i)F(j,i)Z_j.

For example, the three Pascal coefficients before the diagonal in row 33 are odd, so its update is

ζ3⟼ζ3+M(2,3)F(2,3)Z2+M(1,3)F(1,3)Z1+M(0,3)F(0,3)Z0.\zeta_3\longmapsto\zeta_3+ M(2,3)F(2,3)Z_2+M(1,3)F(1,3)Z_1+M(0,3)F(0,3)Z_0.

The same physical wires hold mνm_\nu before E\mathcal E and fνf_\nu afterwards. We therefore first compute MM and store it in borrowed data. This lets us keep MM while encoding the controls, then compute FF and combine the two products.

Computing MM before encoding.

To keep these products while E\mathcal E changes the controls, borrow a word ai=(ai,1,…,ai,i)a_i=(a_{i,1},\ldots,a_{i,i}) of interior data. Position k=i−jk=i-j corresponds to stop jj. We will add M(j,i)M(j,i) into ai,ka_{i,k} and later cancel the initial value of this borrowed bit. For example, the three additions for the walk from 33 are m3m_3, m3m2m_3m_2, and m3m2m1m_3m_2m_1.

We still need space to compute the products before adding them to aia_i. Every term added to ζi\zeta_i contains πi=miχi\pi_i=m_i\chi_i, so the update is zero when χi=0\chi_i=0. When χi=1\chi_i=1, all bits of HiH_i are one. Complementing them therefore gives b−1b-1 zero bits for the calculation. We only need the calculation to take effect in this case. This is the conditional-space technique of Nie, Zi, and Sun and Khattar and Gidney [9, 10]. Figure 4 locates HiH_i, the borrowed word aia_i, and two borrowed bits ci,wic_i,w_i. The borrowed data are disjoint from ZZ, the endpoints, and the controls.

Figure 4. The chain construction with r=4r=4, b=64b=64. The orange wire pi,64p_{i,64} has original value mim_i and encoded value fif_i. The green word HiH_i contains positions 1,…,631,\ldots,63. The borrowed bit cic_i above each block is used for zero tests. Below the endpoints are borrowed interior data: ZiZ_i, the word aia_i of ii bits, and wiw_i. The highlighted walk for ζ3\zeta_3 visits 3,2,1,03,2,1,0.

When HiH_i starts at zero, a circuit UU uses it to copy mi,mi−1,…,m1m_i,m_{i-1},\ldots,m_1 and compute all their running products, written M(⋅,i)=(M(i−1,i),…,M(0,i))M(\cdot,i)=(M(i-1,i),\ldots,M(0,i)). Figure 5 shows the calculation. First combine adjacent intervals up a balanced AND tree. Then work down the tree, passing to each interval the product of the inputs that precede it. At each leaf, multiply this preceding product by the leaf’s own input. This gives every running product using O(i)O(i) bits and gates and O(log⁡(i+1))O(\log(i+1)) depth. We take b≥κrb\ge\kappa r for a sufficiently large fixed κ≥16\kappa\ge16, so the copies, products, and sums below fit inside HiH_i, and the borrowed data fit inside the blocks. UU preserves all inputs outside HiH_i and leaves its last position unused.

Figure 5. Computing all running products of four copied inputs. The upward tree computes each interval’s product. In the downward tree, a left child receives its parent’s preceding product and a right child also multiplies the left interval’s product. Multiplying at each leaf gives the four running products. All intermediate bits start at zero; the root preceding product is set to one by XX. Each level takes a constant number of gate layers.

The calculation above assumes that HiH_i starts at zero. The echo in Figure 6 makes it take effect only when χi=1\chi_i=1, while restoring HiH_i on every input. Complement HiH_i and toggle cic_i by [Hi=0][H_i=0]. Run UU, add ciM(⋅,i)c_iM(\cdot,i) into aia_i, and reverse UU. Toggle cic_i by the same zero test and repeat these three operations, then undo the complements of HiH_i. If χi=1\chi_i=1, the zero test changes cic_i between the two calculations. Their contributions therefore add M(⋅,i)M(\cdot,i) once, regardless of the initial value of cic_i. If χi=0\chi_i=0, the zero test leaves cic_i unchanged. Both calculations then make the same addition, so they cancel even though HiH_i began with nonzero bits. Thus the circuit performs

ai,k⟼ai,k+χiM(i−k,i)(1≤k≤i),a_{i,k}\longmapsto a_{i,k}+\chi_iM(i-k,i) \quad(1\le k\le i),

and restores Hi,ci,wiH_i,c_i,w_i. Call the parallel application of these circuits to all blocks M\mathcal M.

Figure 6. Computing MM before encoding. The circuit for block ii adds χiM(⋅,i)\chi_iM(\cdot,i) into the borrowed word aia_i. UU computes the running products in HiH_i when it starts at zero. An uncontrolled ⊕\oplus complements its word, and each open control tests the entire word for zero. The zero tests borrow and restore wiw_i. All wires except aia_i return to their initial values.

Computing FF after encoding.

The first stage has added χiM(⋅,i)\chi_iM(\cdot,i) to the borrowed word aia_i and restored HiH_i. We can therefore apply E\mathcal E and read the encoded bits fνf_\nu. Compute their running products F(j,i)F(j,i) with the same tree, then combine them with aia_i and ZZ in the sum

si=∑j=0i−1((ij) mod 2)ai,i−jF(j,i)Zj.\begin{equation} s_i=\sum_{j=0}^{i-1} \left(\binom{i}{j}\bmod2\right)a_{i,i-j}F(j,i)Z_j. \tag*{(23)} \end{equation}

When HiH_i starts at zero, let VV copy the encoded bits, aia_i, and Zi−1,…,Z0Z_{i-1},\ldots,Z_0 into it, form the products, and compute this sum into its last position. Its products and sum take O(i)O(i) gates and O(log⁡(i+1))O(\log(i+1)) depth. It preserves every bit outside HiH_i.

The encoding leaves HiH_i unchanged. The same echo can therefore still test whether its original bits were all one, the case χi=1\chi_i=1. Figure 7 replaces UU by VV and each word addition by a Toffoli gate from ci,sic_i,s_i to ζi\zeta_i. When χi=1\chi_i=1, the two additions give sis_i; when χi=0\chi_i=0, they cancel. Denote the parallel application of these circuits by F\mathcal F. It performs ζi↦ζi+χisi\zeta_i\mapsto\zeta_i+\chi_i s_i, preserving ai,Za_i,Z and restoring Hi,ci,wiH_i,c_i,w_i. We can then apply E−1\mathcal E^{-1} to return the controls to their original values.

Figure 7. Computing with FF after encoding. The circuit for block ii adds χisi\chi_i s_i to ζi\zeta_i using the same dirty echo. The bracketed word HiH_i includes the position used for sis_i. VV computes (23) in that position when HiH_i starts at zero. The borrowed data aia_i and ZZ are preserved; all temporary calculations are reversed.

Combining MM and FF.

It remains to cancel the initial values in aia_i. Figure 8 runs the four stages M,E,F,E−1\mathcal M,\mathcal E,\mathcal F,\mathcal E^{-1} twice. Suppose first that χi=1\chi_i=1. The first M\mathcal M changes aia_i to ai+M(⋅,i)a_i+M(\cdot,i), and the first F\mathcal F uses this value in its sum. The second M\mathcal M restores aia_i, and the second F\mathcal F uses its original value. Thus the two sums cancel the unknown initial values in aia_i. At stop jj, with k=i−jk=i-j, the contributions before applying the Pascal coefficient are

(ai,k+M(j,i))F(j,i)Zj+ai,kF(j,i)Zj=Π(j,i)Zj.\begin{equation} (a_{i,k}+M(j,i))F(j,i)Z_j+a_{i,k}F(j,i)Z_j =\Pi(j,i)Z_j. \tag*{(24)} \end{equation}

Here ai,ka_{i,k} denotes its initial value. When χi=0\chi_i=0, both stages leave ai,ζia_i,\zeta_i unchanged, and every desired term is zero. This gives (18) while preserving ZZ and restoring all controls and borrowed bits.

Figure 8. The complete circuit for (ζ,Z)↦(ζ+AZ,Z)(\zeta,Z)\mapsto(\zeta+AZ,Z). Read from left to right. M\mathcal M is the parallel application of Figure 6, and F\mathcal F that of Figure 7. Each M\mathcal M reads original controls; each F\mathcal F reads encoded controls. The two reads of aa cancel its initial values and retain the products MFMF. The words a,c,wa,c,w collect the borrowed bits of all blocks. This circuit will also be used for the forest walks.

Cost of the endpoint update.

Each of the rr walks has at most rr stops, giving O(r2)O(r^2) gates for copies, products, and sums. CNOT fanout trees copy shared inputs to the walks with O(r2)O(r^2) gates and O(log⁡(r+1))O(\log(r+1)) depth. The additions controlled by the same cic_i use the common-control circuit from the preliminaries, with linear size and logarithmic depth. The zero tests on HiH_i and the constant number of encoding calls use O(rb)O(rb) gates and O(log⁡(b+1))O(\log(b+1)) depth. The other additions in (17) exchange the registers or redirect their outputs, and Q1Q_1 changes the fixed Pascal selections.

Lemma 6 (Recursive endpoint circuit). For a sufficiently large fixed κ≥16\kappa\ge16 and b≥κrb\ge\kappa r, Step 2 has size O(rb+r2)O(rb+r^2) and depth O(log⁡(b+r+1))O(\log(b+r+1)). It uses only existing wires and restores all controls and borrowed interior data.

Recursion and resource bounds

The recursive construction uses large blocks, so the direct interior correction would take too much depth. Here we use the incrementer circuit in Figure 9 instead. Incrementing the little-endian word (yj−1,b,pj,1,…,pj,b)(y_{j-1,b},p_{j,1},\ldots,p_{j,b}) changes

pj,t+1⟼pj,t+1+yj−1,b∏u=1tpj,u,1≤t<b.\begin{equation} p_{j,t+1}\longmapsto p_{j,t+1} +y_{j-1,b}\prod_{u=1}^{t}p_{j,u}, \qquad 1\le t<b. \tag*{(25)} \end{equation}

The two CNOT layers add the old and new values of each control to the corresponding interior bit. Their original values cancel, leaving exactly the correction in (11). The inverse increment restores the incoming endpoint and all controls. Each incrementer borrows and restores the first interior bit. As before, different blocks use disjoint wires, so the corrections run in parallel with total size O(n)O(n) and depth O(log⁡(b+1))O(\log(b+1)).

Figure 9. The incrementer correction used for the larger recursive blocks. The two bundled wires each contain b−1b-1 bits, and the CNOTs act bitwise. The increment and its inverse act on the little-endian word (yj−1,b,pj,1,…,pj,b)(y_{j-1,b},p_{j,1},\ldots,p_{j,b}), each borrowing and restoring the first interior bit.

Each walk needs space proportional to its number of stops. We therefore choose blocks large enough to hold these calculations. Fix κ\kappa as in Lemma 6, and take r≥2r\ge2 to be the largest power of two satisfying κ(r+1)r≤n\kappa(r+1)r\le n. Set

b=⌈nr+1⌉.b=\left\lceil\frac{n}{r+1}\right\rceil.

For the finitely many smaller sizes, use the direct ladder. Then b≥κrb\ge\kappa r, r=Θ(n)r=\Theta(\sqrt n), and b=Θ(n)b=\Theta(\sqrt n). Adjust B0B_0 for the remainder as in § 3. Its length n−rbn-rb lies between b−rb-r and bb, leaving enough interior data for its borrowed source bit.

The endpoint update now has size O(n)O(n) and depth O(log⁡n)O(\log n). Run the local ladders recursively in parallel and use the interior correction above. The resulting bounds are

S(n)≤(r+1)S(b)+O(n),D(n)≤D(b)+O(log⁡(n+1)).\begin{equation} \begin{aligned} S(n)&\le(r+1)S(b)+O(n),\\ D(n)&\le D(b)+O(\log(n+1)). \end{aligned} \tag*{(26)} \end{equation}

At each level, the blocks partition the data, so the work outside recursive calls is O(n)O(n). At each level, the block size falls to its square root, up to a constant factor. It reaches constant size after O(log⁡log⁡n)O(\log\log n) levels, giving size O(nlog⁡log⁡n)O(n\log\log n). Along a branch, the logarithms of the block sizes decrease geometrically, so the depths sum to O(log⁡n)O(\log n). All borrowed wires are restored within each call. Lemma 3 gives the same bounds for addition, proving Theorem 2.

The remaining size factor comes from repeating linear work at every level. We used large blocks because each endpoint walked along a chain of up to rr stops. Shortening the walks to O(log⁡r)O(\log r) stops will let us use smaller blocks. We can then keep the circuit of Figure 8 and complete the construction without recursion.

The linear-size construction

The recursive construction needs large blocks because each walk can have up to rr stops. We now shorten the walks to O(log⁡r)O(\log r) stops. The same circuit then needs only O(log⁡r)O(\log r) conditional space per block, so logarithmic block size suffices. We can run the local ladders directly and remove the recursion.

We keep the three steps of § 3. For the endpoint update, decompose its inverse JJ into two forests, apply the Pascal identities along their paths, and reuse the borrowed-register additions from (17). To use these shorter walks, we need to encode the longer intervals crossed by forest edges. We also need to combine contributions from walks that reach the same endpoint.

From one ladder to two forests

We replace the chain of consecutive endpoints by two forests whose paths are short. Their maps will satisfy J=FinFoutJ=F_{\mathrm{in}}F_{\mathrm{out}}. For i>0i>0, let v2(i)v_2(i) be the largest integer kk such that 2k2^k divides ii, and write

λ(i)=2v2(i),Π(a,b)=∏ν=a+1bπν(0≤a<b≤r).\lambda(i)=2^{v_2(i)},\qquad \Pi(a,b)=\prod_{\nu=a+1}^{b}\pi_\nu\quad(0\le a<b\le r).

Thus λ(i)\lambda(i) is the value of the lowest set bit in the binary expansion of ii. It determines the interval crossed by an edge. Both maps fix coordinate zero; for i>0i>0, define

(Finu)i=ui+∑j>0j+λ(j)=iΠ(j,i)uj,(Foutu)i=ui+Π(i−λ(i),i)ui−λ(i).\begin{equation} \begin{aligned} (F_{\mathrm{in}}u)_i &=u_i+\sum_{\substack{j>0\\j+\lambda(j)=i}}\Pi(j,i)u_j,\\ (F_{\mathrm{out}}u)_i &=u_i+\Pi(i-\lambda(i),i)u_{i-\lambda(i)}. \end{aligned} \tag*{(27)} \end{equation}

To check that their product is JJ, fix i>0i>0, set t=v2(i)t=v_2(i), and write jk=i−2kj_k=i-2^k for 0≤k≤t0\le k\le t. The indices in the sum for FinF_{\mathrm{in}} are j0,…,jt−1j_0,\ldots,j_{t-1}. For k<tk<t, we have λ(jk)=2k\lambda(j_k)=2^k, so

Π(jk,i)(Foutu)jk=Π(jk,i)ujk+Π(jk+1,i)ujk+1.\Pi(j_k,i)(F_{\mathrm{out}}u)_{j_k} =\Pi(j_k,i)u_{j_k}+\Pi(j_{k+1},i)u_{j_{k+1}}.

The second term of each pair is the first term of the next pair, so these terms cancel modulo 22. The last term cancels the extra term Π(jt,i)ujt\Pi(j_t,i)u_{j_t} in (Foutu)i(F_{\mathrm{out}}u)_i, leaving ui+Π(i−1,i)ui−1=ui+πiui−1u_i+\Pi(i-1,i)u_{i-1}=u_i+\pi_i u_{i-1}, as required by (13). When ii is odd, t=0t=0 and the sum is empty; FoutF_{\mathrm{out}} already gives this update.

Figure 10 shows the two maps as forests: FoutF_{\mathrm{out}} has an edge i−λ(i)→ii-\lambda(i)\to i, and FinF_{\mathrm{in}} has an edge j→j+λ(j)j\to j+\lambda(j) whenever the successor is at most rr. Each edge a→ba\to b carries weight Π(a,b)\Pi(a,b). In the left forest, each nonzero vertex has one parent; in the right, each vertex has at most one successor. Following parents on the left clears one set bit at each step. Following successors on the right moves the lowest set bit to a higher position at each step. Both walks therefore take at most a logarithmic number of steps, and the forests have height at most h=⌈log⁡2(r+2)⌉h=\lceil\log_2(r+2)\rceil.

To apply the Pascal identities along a path, we need consecutive indices for its vertices. We call these indices grades. In FoutF_{\mathrm{out}}, give vertex ii grade did_i equal to its distance from the root. In FinF_{\mathrm{in}}, use hh minus its distance to the sink, the vertex with no successor. Every directed edge then increases the grade by one. The green row labels in Figure 10 show these grades. For example, the highlighted path 0→4→6→70\to4\to6\to7 on the left has grades 0,1,2,30,1,2,3, while 1→2→4→81\to2\to4\to8 on the right has grades 1,2,3,41,2,3,4. Each path is therefore a ladder indexed by consecutive grades, with vertices drawn from possibly nonconsecutive endpoints. Its step from aa to bb is controlled by Π(a,b)\Pi(a,b), the conjunction of all controls in blocks Ba+1,…,BbB_{a+1},\ldots,B_b. Successive edge intervals are disjoint and concatenate, so the weight of a path is

∏ℓ=1mΠ(vℓ−1,vℓ)=Π(v0,vm)for v0→v1→⋯→vm.\prod_{\ell=1}^{m}\Pi(v_{\ell-1},v_\ell)=\Pi(v_0,v_m) \quad\text{for }v_0\to v_1\to\cdots\to v_m.

The edge labels and products beneath the orange paths in Figure 10 illustrate this correspondence.

Figure 10. The two forests on endpoints 0,…,80,\ldots,8, with h=4h=4. Green labels give the grade did_i of every vertex in the corresponding row. The orange paths show the edges visited by one block’s walk in each forest. Their edge weights multiply to the conjunction over the full path interval. Each path is a ladder on its ordered vertices, which may be nonconsecutive endpoints.

We can now reuse Lemma 4 on each path. Fix either forest FF, and define its factor Q0Q_0 by an identity diagonal and

(Q0)ij=((didj) mod 2)Π(j,i)if there is a nonempty directed path j→i.\begin{equation} (Q_0)_{ij}=\left(\binom{d_i}{d_j}\bmod2\right)\Pi(j,i) \quad\text{if there is a nonempty directed path }j\to i. \tag*{(28)} \end{equation}

All other entries below the diagonal are zero. Define Q1Q_1 in the same way with both grades decreased by one, setting its entries below the diagonal to zero when dj=0d_j=0. There is at most one directed path between any two vertices. Matrix multiplication along this path is exactly the weighted Pascal calculation from § 4.1, so

F=Q1Q0,Q02=Q12=I.\begin{equation} F=Q_1Q_0,\qquad Q_0^2=Q_1^2=I. \tag*{(29)} \end{equation}

The parity of each binomial coefficient determines whether its path contribution is added. To apply J−1J^{-1}, apply the two factors for Fin−1F_{\mathrm{in}}^{-1} and then those for Fout−1F_{\mathrm{out}}^{-1}, using Q1Q_1 followed by Q0Q_0 in each case.

Reusing the borrowed-register additions

For a forest factor Q=I+AQ=I+A, we use the four additions in (17) to apply QQ and restore the borrowed ZZ. The identity A2=0A^2=0 follows again from Q2=IQ^2=I. It remains to check ADA=AADA=A for the same backward shift DD used in § 4.1.

For Q0Q_0, expand (ADA)ij=∑k=0r−1AikAk+1,j(ADA)_{ij}=\sum_{k=0}^{r-1}A_{ik}A_{k+1,j}. In FoutF_{\mathrm{out}}, a nonempty directed path can start only at an even vertex. The contributing indices kk lie on the path from jj to ii, excluding ii, and vertex k+1k+1 is a child of kk. In FinF_{\mathrm{in}}, a nonempty directed path can end only at a positive even vertex. Here the contributing vertices k+1k+1 lie on the path after jj, including ii, and kk is the odd predecessor of k+1k+1. In both cases dk+1=dk+1d_{k+1}=d_k+1, and the possible grades dkd_k range from djd_j to di−1d_i-1. The weights multiply to Π(k,i)Π(j,k+1)=Π(j,i)\Pi(k,i)\Pi(j,k+1)=\Pi(j,i), since the repeated factor πk+1\pi_{k+1} satisfies πk+12=πk+1\pi_{k+1}^2=\pi_{k+1}. Thus, on a nonempty path j→ij\to i,

(ADA)ij≡Π(j,i)∑d=djdi−1(did)(d+1dj)≡Π(j,i)(didj)=Aij(mod2),\begin{equation} \begin{aligned} (ADA)_{ij} &\equiv\Pi(j,i)\sum_{d=d_j}^{d_i-1} \binom{d_i}{d}\binom{d+1}{d_j}\\ &\equiv\Pi(j,i)\binom{d_i}{d_j}=A_{ij}\pmod2, \end{aligned} \tag*{(30)} \end{equation}

where the second equality is exactly the chain identity (16), with grades in place of indices. If there is no nonempty path, both entries are zero. For Q1Q_1, decrease both grades by one. The columns whose source has grade zero are zero on both sides. The same four-addition circuit therefore applies every forest factor.

The two forests contribute four factors. Sixteen additions suffice for the endpoint ladder, all reusing the same restored ZZ. As before, we describe ζ←ζ+AZ\zeta\leftarrow\zeta+AZ; the other additions exchange the registers or redirect row ii to position i−1i-1.

Parallel walks from the blocks

The four-addition echo leaves us with the same task as before: implement

(ζ,Z)⟼(ζ+AZ,Z),(\zeta,Z)\longmapsto(\zeta+AZ,Z),

while restoring all temporary data. Here ζ\zeta contains the block endpoints and ZZ is a borrowed register of r+1r+1 interior bits. We first take A=Q0−IA=Q_0-I for the outward forest. Expanding the update gives, for each endpoint,

ζi⟼ζi+∑j: j→i((didj) mod 2)Π(j,i)Zj,0≤i≤r,\zeta_i\longmapsto\zeta_i+ \sum_{j:\,j\to i} \left(\binom{d_i}{d_j}\bmod2\right)\Pi(j,i)Z_j, \qquad 0\le i\le r,

where the sum runs over nonempty directed paths j→ij\to i. In the left forest of Figure 10, these sources jj are the ancestors of ii other than ii itself. Each term uses the source bit ZjZ_j, controlled by the product of edge weights along the path from jj to ii, namely Π(j,i)\Pi(j,i). The Pascal coefficient depends only on the grades, so the circuit knows in advance which terms to include.

For example, when r=8r=8, the highlighted path in the left forest of Figure 10 contains vertices 7,6,4,07,6,4,0, with grades 3,2,1,03,2,1,0, respectively. Their endpoint updates are

ζ7⟼ζ7+π7Z6+Π(4,7)Z4+Π(0,7)Z0,ζ6⟼ζ6+Π(0,6)Z0,ζ4⟼ζ4+Π(0,4)Z0,ζ0⟼ζ0.\begin{equation} \begin{aligned} \zeta_7&\longmapsto\zeta_7+ \pi_7Z_6+\Pi(4,7)Z_4+\Pi(0,7)Z_0,\\ \zeta_6&\longmapsto\zeta_6+\Pi(0,6)Z_0,\\ \zeta_4&\longmapsto\zeta_4+\Pi(0,4)Z_0,\\ \zeta_0&\longmapsto\zeta_0. \end{aligned} \tag*{(31)} \end{equation}

For ζ7\zeta_7, walk along 7→6→4→07\to6\to4\to0. The edge controls are π7\pi_7, Π(4,6)\Pi(4,6), and Π(0,4)\Pi(0,4). At each stop, multiply the edge controls used so far. Use this product to control the addition of the source bit at that stop. All three Pascal coefficients are one. For ζ6\zeta_6, walk along 6→4→06\to4\to0. Skip the addition at 44 because (21)≡0(mod2)\binom21\equiv0\pmod2, but retain the edge control Π(4,6)\Pi(4,6): at 00, add Π(4,6)Π(0,4)Z0=Π(0,6)Z0\Pi(4,6)\Pi(0,4)Z_0=\Pi(0,6)Z_0. The walk 4→04\to0 adds Π(0,4)Z0\Pi(0,4)Z_0 to ζ4\zeta_4, and the root ζ0\zeta_0 is unchanged. Each block BiB_i has its own walk from vertex ii to the root, and we perform all walks in parallel.

These are the same running-product calculations as in § 4.2, now with at most hh stops. A forest edge can cross many blocks. Computing its weight by scanning those blocks separately for each walk would undo the saving from shorter paths. All edge intervals belong to

I={(j,i]⊆(0,r]:i−j=2k, j≡0(mod2k), k≥0}.\mathcal I=\{(j,i]\subseteq(0,r]:i-j=2^k, \ j\equiv0\pmod{2^k},\ k\ge0\}.

These are dyadic intervals: each has power-of-two length and starts at a multiple of that length. We encode them once and share their encoded bits among the walks. The construction of Nie, Zi, and Sun [9] extends the one-block identity (21). It represents each Π(j,i)\Pi(j,i) as the conjunction of one encoded bit and at most four selected original control bits. We call these selected controls its delegates.

We use conditional space inside each block for the same reason as in § 4.2: every term added to ζi\zeta_i contains πi=∏t=1bpi,t\pi_i=\prod_{t=1}^{b}p_{i,t}. For example, with r=8r=8,

Δζ7=π7(Z6+Π(4,6)Z4+Π(4,6)Π(0,4)Z0).\Delta\zeta_7=\pi_7\bigl( Z_6+\Pi(4,6)Z_4+\Pi(4,6)\Pi(0,4)Z_0\bigr).

If any control chosen for conditional space in B7B_7 is zero, the whole change vanishes. If all chosen controls are one, complementing them provides zero space. A walk now has only hh stops, so we need only O(h)O(h) such bits in each block. For the outward walks, the space in BiB_i is used only to compute ζi\zeta_i.

Figure 11 shows the bits used by the circuit. Take Hi=(pi,1,…,pi,6h+2)H_i=(p_{i,1},\ldots,p_{i,6h+2}), assuming b−4≥6h+2b-4\ge6h+2. The four control positions at the bottom of each block are for delegates. The first two can be chosen at a larger interval and passed to smaller intervals. The third and fourth are chosen at the one-block interval. Their physical indices are b−3,b−2,b−1,bb-3,b-2,b-1,b. The words aia_i, with one bit per stop, and the bits ci,wic_i,w_i are borrowed from interior data, disjoint from ZZ and the endpoints. They may start in arbitrary states and will be restored. The bit cic_i is drawn above BiB_i because it controls the use of HiH_i.

Figure 11. The layout for r=8r=8, b=64b=64, and h=4h=4. Green bits form HiH_i. The four bottom positions are D(i,1),…,D(i,4)D(i,1),\ldots,D(i,4), with physical coordinates (i,61),…,(i,64)(i,61),\ldots,(i,64). Blue positions are chosen at larger intervals; orange positions are chosen at BiB_i. The grey positions in B8B_8 are left unchanged. The words aia_i, the bits ci,wic_i,w_i, and ZZ are existing interior data, all restored by the circuit.

Encoding the interval products.

Let D(i,1),…,D(i,4)D(i,1),\ldots,D(i,4) name four distinct control positions in BiB_i. We first describe the recursion using these positions, then fix their coordinates. Each recursive call works on one interval and chooses two control bits there. Smaller calls omit positions already chosen at larger intervals. At an internal interval, the circuit tests the four bits chosen by its two children, complements them, runs the child circuits, and combines their encoded bits. This leaves the interval product in one encoded bit whenever its original delegates are all one.

Figure 12 shows two recursion layers on eight blocks. The root uses pD(1,1),pD(1,2)p_{D(1,1)},p_{D(1,2)}, and its children use the pairs in B3,B5B_3,B_5. To see how the circuit works, consider the case where the root’s two bits enter at zero. First compute

pD(1,2)⟵pD(1,2)+pD(3,1)pD(3,2)pD(5,1)pD(5,2).p_{D(1,2)}\longleftarrow p_{D(1,2)}+ p_{D(3,1)}p_{D(3,2)}p_{D(5,1)}p_{D(5,2)}.

Complement those four child bits, run the two child circuits, and then compute

pD(1,1)⟵pD(1,1)+pD(1,2)pD(3,1)pD(5,1).p_{D(1,1)}\longleftarrow p_{D(1,1)}+ p_{D(1,2)}p_{D(3,1)}p_{D(5,1)}.

The next layer repeats these gates: the call on (0,4](0,4] uses the pairs in B2,B4B_2,B_4, and the call on (4,8](4,8] uses those in B6,B7B_6,B_7. At a one-block interval BiB_i, use D(i,3),D(i,4)D(i,3),D(i,4) and add the conjunction of the controls outside all chosen positions into pD(i,3)p_{D(i,3)}. Before starting the root, complement its two chosen bits. Every other pair is complemented by its parent before its call begins.

Figure 12. Two layers of the interval encoding for r=8r=8. The root pair is shown after its initial complements, on the branch where it enters at zero. Each box B(j,i)\mathcal B(j,i) continues the recursion on (j,i](j,i], omitting positions chosen at larger intervals. Hats mark the values after encoding.

We now fix the positions. Use the four bottom controls in each block:

D(i,1)=(i,b−3),D(i,2)=(i,b−2),D(i,3)=(i,b−1),D(i,4)=(i,b).\begin{equation} \begin{aligned} D(i,1)&=(i,b-3),&\qquad D(i,2)&=(i,b-2),\\ D(i,3)&=(i,b-1),& D(i,4)&=(i,b). \end{aligned} \tag*{(32)} \end{equation}

Apply the following formula separately within each maximal dyadic interval, writing ss for its right endpoint. At the interval (j,i](j,i], choose the two positions D(k,t),D(k,t+1)D(k,t),D(k,t+1), where

(k,t)={(i,3),i−j=1,(j+1+i−j2[i<s], 1),i−j>1.\begin{equation} (k,t)= \begin{cases} (i,3),&i-j=1,\\[2pt] \bigl(j+1+\tfrac{i-j}{2}[i<s],\,1\bigr),&i-j>1. \end{cases} \tag*{(33)} \end{equation}

At intervals containing several blocks, an inherited pair lies in the first block. The formula places the new pair in the other half when that inherited pair is present; otherwise it uses the first block. This keeps the two pairs in different children.

For example, Figure 13 starts with the pair D(1,1),D(1,2)D(1,1),D(1,2) at (0,8](0,8]. The interval (0,4](0,4] inherits that pair and chooses D(3,1),D(3,2)D(3,1),D(3,2) in its other half. Its two children then inherit the pairs in B1,B3B_1,B_3 and choose the pairs in B2,B4B_2,B_4. The interval (4,8](4,8] starts with the pair in B5B_5, and its children choose the pairs in B6,B7B_6,B_7. For the walk 7→6→4→07\to6\to4\to0, the intervals (6,7](6,7], (4,6](4,6], and (0,4](0,4] therefore have their encoded bits at D(7,3)D(7,3), D(6,1)D(6,1), and D(3,1)D(3,1), respectively. When b=64b=64, these are positions (7,63)(7,63), (6,61)(6,61), and (3,61)(3,61).

Figure 13. The chosen positions for r=8r=8: inherited positions in blue, newly chosen positions in orange. Each D(i,t)D(i,t) is one physical bit index in BiB_i. The highlighted intervals supply the walk 7→6→4→07\to6\to4\to0.

Write E:p↦p^\mathcal E:p\mapsto\widehat p for the encoding. For an interval (j,i](j,i] and its (k,t)(k,t) from (33), define

m(j,i)=pD(k,t)pD(k,t+1)(pD(j+1,1)pD(j+1,2))[i<s],f(j,i)=p^D(k,t).\begin{equation} \begin{aligned} m(j,i)&=p_{D(k,t)}p_{D(k,t+1)} \bigl(p_{D(j+1,1)}p_{D(j+1,2)}\bigr)^{[i<s]},\\ f(j,i)&=\widehat p_{D(k,t)}. \end{aligned} \tag*{(34)} \end{equation}

The parenthesized factor is one when i=si=s. Here m(j,i)m(j,i) is a product of original delegate values, while f(j,i)f(j,i) is read after encoding. These quantities satisfy

Π(j,i)=m(j,i)f(j,i).\begin{equation} \Pi(j,i)=m(j,i)f(j,i). \tag*{(35)} \end{equation}

To see why mm needs at most four controls, follow the chosen pairs down the tree. An internal interval ending at ss inherits no positions; its new pair is in the first block of its left child. The left child inherits that pair, and the right child inherits none. An internal interval ending before ss inherits exactly D(j+1,1),D(j+1,2)D(j+1,1),D(j+1,2). Its new pair is in the first block of the right child, so each child inherits exactly one pair. Induction therefore gives at most two inherited positions at every interval. Together with its own two chosen positions, these are precisely the at most four controls in m(j,i)m(j,i).

If any of these original controls is zero, both Π(j,i)\Pi(j,i) and m(j,i)m(j,i) are zero. Otherwise, the call’s own pair enters at zero and all the omitted controls from larger intervals have value one. If any of the four child bits was zero before its complement, the call’s second bit stays zero, so its final gate does not act. If all four were one, both children enter with zero pairs, compute the products of their remaining controls, and the final gate multiplies their encoded values. At a leaf this is exactly the single conjunction gate. Thus, when the original delegates are all one, the first encoded bit gives the conjunction of all remaining controls. This proves (35) by induction. Each child circuit runs regardless of the other child’s values, so the identity holds for every interval below the root.

Only the four positions in (32) can change, so the encoding preserves HiH_i. There are O(r)O(r) internal calls and size-O(b)O(b) work at each leaf. Hence E\mathcal E has size O(N)O(N) and depth O(log⁡(N+1))O(\log(N+1)), where N=rbN=rb. The first controlled gate of an internal call can borrow its first chosen bit, and the last can borrow a child’s second chosen bit; these borrowed bits are restored. A leaf gate can borrow its own second chosen bit.

Computing the endpoint updates.

Use the complete circuit in Figure 8, now with shorter walks and the shared interval encoding E\mathcal E. The position for sis_i is again the last bit of HiH_i, namely (i,6h+2)(i,6h+2). Inside M,F\mathcal M,\mathcal F, the circuits U,VU,V now form their products along the forest paths.

For the walk 7→6→4→07\to6\to4\to0, the three edge controls have the representations in (34)–(35). Before encoding, UU copies their original delegates into H7H_7 and computes

M(6,7)=m(6,7),M(4,7)=m(6,7)m(4,6),M(0,7)=m(6,7)m(4,6)m(0,4).\begin{aligned} M(6,7)&=m(6,7),\\ M(4,7)&=m(6,7)m(4,6),\\ M(0,7)&=m(6,7)m(4,6)m(0,4). \end{aligned}

After encoding, VV copies the encoded bits and computes F(6,7),F(4,7),F(0,7)F(6,7),F(4,7),F(0,7) by the same products with ff in place of mm. Together with copies of a7,Za_7,Z, they give

s7=a7,1F(6,7)Z6+a7,2F(4,7)Z4+a7,3F(0,7)Z0.s_7=a_{7,1}F(6,7)Z_6+a_{7,2}F(4,7)Z_4+ a_{7,3}F(0,7)Z_0.

In general, along i=j0→j1→⋯→jti=j_0\to j_1\to\cdots\to j_t, define

M(jk,i)=∏ℓ=1km(jℓ,jℓ−1),F(jk,i)=∏ℓ=1kf(jℓ,jℓ−1).M(j_k,i)=\prod_{\ell=1}^{k}m(j_\ell,j_{\ell-1}),\qquad F(j_k,i)=\prod_{\ell=1}^{k}f(j_\ell,j_{\ell-1}).

The word M(⋅,i)M(\cdot,i) lists these products in walk order, and

si=∑k=1t((didjk) mod 2)ai,kF(jk,i)Zjk.s_i=\sum_{k=1}^{t} \left(\binom{d_i}{d_{j_k}}\bmod2\right) a_{i,k}F(j_k,i)Z_{j_k}.

Each original edge product m(jℓ,jℓ−1)m(j_\ell,j_{\ell-1}) uses at most four delegates. With only hh stops, these running products take O(h)O(h) gates and depth. Both U,VU,V compute into HiH_i from unchanged outside inputs; UU leaves the position for sis_i untouched. Their inverses restore all temporary copies and products.

The circuits for M\mathcal M and F\mathcal F use the same zero-test echoes as in Figure 6 and Figure 7. Each HiH_i is restored before every encoding or decoding, so E\mathcal E and its inverse always see the correct control values. The two calls to each stage in Figure 8 restore aia_i and cancel its initial values by (24). At stop jkj_k, the remaining contribution is

M(jk,i)F(jk,i)Zjk=Π(jk,i)Zjk,M(j_k,i)F(j_k,i)Z_{j_k}=\Pi(j_k,i)Z_{j_k},

when its Pascal coefficient is odd. If any original control in HiH_i was zero, every desired term is zero, and the zero-test echoes in both stages make no net change. This completes the outward update and restores all controls and borrowed bits.

For the inward forest, a block’s walk starts at a source and follows its successors. Attach BiB_i to source vertex i−1i-1. Its source bit is fixed at Zi−1Z_{i-1}, and each visited vertex specifies an endpoint to change. At a stop jj, add Π(i−1,j)Zi−1\Pi(i-1,j)Z_{i-1} when (djdi−1)\binom{d_j}{d_{i-1}} is odd. This interval contains BiB_i, so the conditional space is HiH_i. The running products are M(i−1,j)M(i-1,j) and F(i−1,j)F(i-1,j), formed along the path from i−1i-1 to jj. Different walks may reach the same endpoint, so we first store their contributions separately. Give each stop a borrowed bit vi,kv_{i,k}. Here VV computes its individual terms in separate positions of HiH_i and adds each term to its vi,kv_{i,k}, controlled by cic_i. We then add the parity of the borrowed bits belonging to each endpoint. For example, the three walks from B2,B3,B4B_2,B_3,B_4 give

v2,2←v2,2+Π(1,4)Z1,v3,1←v3,1+Π(2,4)Z2,v4,1←v4,1+π4Z3.\begin{aligned} v_{2,2}&\leftarrow v_{2,2}+\Pi(1,4)Z_1,\\ v_{3,1}&\leftarrow v_{3,1}+\Pi(2,4)Z_2,\\ v_{4,1}&\leftarrow v_{4,1}+\pi_4Z_3. \end{aligned}

Add these three bits to ζ4\zeta_4, run their circuits again to restore them, and add the three bits to ζ4\zeta_4 again. Their initial values cancel and the three desired terms remain, as Figure 14 shows. Group the bits by the endpoint they change and use CNOT trees for these parity additions.

Figure 14. Three inward walks contribute to ζ4\zeta_4. Each box runs the complete circuit with v2,2,v3,1,v4,1v_{2,2},v_{3,1},v_{4,1} as the bits to change, and restores its other bits. The first three CNOTs add their new parity; the last three add their original parity. All three borrowed bits are restored.

For Z←Z+DAζZ\leftarrow Z+DA\zeta, use ζj\zeta_j as the source and Zi−1Z_{i-1} in place of an update to ζi\zeta_i. Every nonempty path ends at a positive index. For Q1Q_1, omit terms whose source has grade zero and decrease both grades by one when selecting the additions.

Each walk has at most hh stops. The copies and running products in UU use at most 5h+15h+1 bits of HiH_i. For outward walks, VV uses at most 4h+24h+2 bits, including sis_i; for inward walks its separate terms use at most 5h+15h+1 bits. All fit in 6h+26h+2 positions and take O(h)O(h) gates and depth per walk. Copying shared inputs and adding the inward parities take O(rh)O(rh) gates and logarithmic depth. The encoding is run a constant number of times. We obtain the following bound.

Lemma 7 (Parallel path update). For either forest and either Pascal factor Q=I+AQ=I+A, each of the updates (ζ,Z)⟼(ζ+AZ,Z),(ζ,Z)⟼(ζ,Z+DAζ)(\zeta,Z)\longmapsto(\zeta+AZ,Z),\qquad (\zeta,Z)\longmapsto(\zeta,Z+DA\zeta) has size O(N+rh)O(N+rh) and depth O(log⁡(N+r+1)+h)O(\log(N+r+1)+h). It uses 6h+26h+2 control positions per block that the encoding leaves unchanged, one borrowed bit per stop for the outward forest and two for the inward forest, and two more borrowed bits ci,wic_i,w_i per walk. All controls and borrowed bits are restored, and the source register is preserved.

Completing the adder without recursion

Choose a sufficiently large fixed κ≥64\kappa\ge64, let L=⌈log⁡2(n+1)⌉L=\lceil\log_2(n+1)\rceil, and take bb to be the next power of two at least κL\kappa L. Use the partition of § 3, with r=⌈n/b⌉−1r=\lceil n/b\rceil-1 full blocks after B0B_0. For the finitely many small sizes with n≤2bn\le2b, use the direct ladder. Otherwise h≤Lh\le L, N=rb≤nN=rb\le n, and

rh≤nκ,b−4≥6h+2.rh\le\frac{n}{\kappa},\qquad b-4\ge6h+2.

The second inequality leaves enough unchanged control positions for HiH_i in each block.

The borrowed data also fit inside the existing blocks. Let q≤rhq\le rh be the total number of stops in all walks. The dirty register ZZ, the words aia_i, the inward buffers, and the bits ci,wic_i,w_i need at most

(r+1)+2q+2r≤5rh≤5nκ≤n2≤n−r−1(r+1)+2q+2r\le5rh\le\frac{5n}{\kappa} \le\frac n2\le n-r-1

bits for sufficiently large nn. The last quantity is the number of interior data bits. The two forests and their factors run sequentially, reusing the same restored allocation.

We can now finish the three steps of Figure 1. Run each local ladder directly: their total size is O(n)O(n) and their depth is O(b)=O(log⁡n)O(b)=O(\log n). The endpoint update uses sixteen calls to Lemma 7, each of size O(n+rh)=O(n)O(n+rh)=O(n) and depth O(log⁡n)O(\log n). Finally, the direct interior correction of Figure 2 uses O(n)O(n) gates and O(b)=O(log⁡n)O(b)=O(\log n) depth. There is only one partition and no recursive call. Lemma 3 gives the same bounds for addition, proving Theorem 1.

Every output bit in the second input register must participate in a gate, giving an Ω(n)\Omega(n) size bound for bounded-arity gates. The highest sum bit depends on all 2n2n input bits. Looking backward through one layer, each gate can increase the number of inputs that affect this bit by at most a constant factor. The depth is therefore Ω(log⁡n)\Omega(\log n). Our circuit attains both lower bounds, so its size and depth are asymptotically optimal.

Acknowledgments

Wei Zi acknowledges support from the National Natural Science Foundation of China (Grant No. 62602563) and the Guangdong Provincial Quantum Science Strategic Initiative (Grant No. GDZX2503001).

AI statement

We thank GPT-6 Pro for useful discussions that helped develop and verify the ideas in this paper. In particular, GPT-6 Pro found the forest decomposition that enabled us to achieve asymptotically optimal circuit size. We also used GPT-6.1 Sol (Codex) to assist with writing the manuscript and preparing LaTeX figures. We reviewed, edited, and verified all AI-assisted material and take full responsibility for the content of this paper.

References

  1. [1]Shor, P. W. (1997). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing, 26(5), 1484–1509. https://doi.org/10.1137/S0097539795293172
  2. [2]Häner, T., Jaques, S., Naehrig, M., Roetteler, M., & Soeken, M. (2020). Improved Quantum Circuits for Elliptic Curve Discrete Logarithms. Post-Quantum Cryptography, 12100, 425–444. https://doi.org/10.1007/978-3-030-44223-1_23
  3. [3]Jones, N. C., Whitfield, J. D., McMahon, P. L., Yung, M.-H., Van Meter, R., Aspuru-Guzik, A., & Yamamoto, Y. (2012). Faster quantum chemistry simulation on fault-tolerant quantum computers. New Journal of Physics, 14(11), 115023. https://doi.org/10.1088/1367-2630/14/11/115023
  4. [4]Sünderhauf, C., Campbell, E., & Camps, J. (2024). Block-encoding structured matrices for data input in quantum computing. Quantum, 8, 1226. https://doi.org/10.22331/q-2024-01-11-1226
  5. [5]Draper, T. G. (2000). Addition on a Quantum Computer. https://doi.org/10.48550/arXiv.quant-ph/0008033
  6. [6]Cuccaro, S. A., Draper, T. G., Kutin, S. A., & Moulton, D. P. (2004). A new quantum ripple-carry addition circuit. https://doi.org/10.48550/arXiv.quant-ph/0410184
  7. [7]Draper, T. G., Kutin, S. A., Rains, E. M., & Svore, K. M. (2006). A logarithmic-depth quantum carry-lookahead adder. Quantum Information and Computation, 6(4--5), 351–369. https://doi.org/10.26421/QIC6.4-5-4
  8. [8]Takahashi, Y., Tani, S., & Kunihiro, N. (2010). Quantum addition circuits and unbounded fan-out. Quantum Information and Computation, 10(9--10), 872–890. https://doi.org/10.26421/QIC10.9-10-12
  9. [9]Nie, J., Zi, W., & Sun, X. (2024). Quantum circuit for multi-qubit Toffoli gate with optimal resource. https://doi.org/10.48550/arXiv.2402.05053
  10. [10]Khattar, T., & Gidney, C. (2025). Rise of conditionally clean ancillae for efficient quantum circuit constructions. Quantum, 9, 1752. https://doi.org/10.22331/q-2025-05-21-1752
  11. [11]Remaud, M., & Vandaele, V. (2025). Ancilla-Free Quantum Adder with Sublinear Depth. Reversible Computation, 15716, 137–154. https://doi.org/10.1007/978-3-031-97063-4_11
  12. [12]Remaud, M. (2025). Quantum adders: on the structural link between the ripple-carry and carry-lookahead techniques. https://doi.org/10.48550/arXiv.2510.00840
  13. [13]Vandaele, V. (2026). Asymptotically Optimal Quantum Circuits for Comparators and Incrementers. https://doi.org/10.48550/arXiv.2603.12917

Paper details

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

views · 0

downloads · 0

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

  • Physics and Astronomy

GPT-6 Pro, Codex

View statement
Looking for related papers…
Contents