WorksPhysics and Astronomy
Ancilla-free optimal quantum adder
Abstract
We construct an exact -bit quantum adder with gates and depth that requires no ancillary qubits. The circuit uses only , 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 gates and 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 gates. Both the gate count and circuit depth are asymptotically optimal.
Introduction
An -bit quantum adder implements
for , 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 -bit adder over bounded-arity gates requires gates and 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 , CNOT, and Toffoli gates and is therefore classically reversible.
Theorem 1. With all-to-all connectivity, there is an exact -bit quantum adder using , CNOT, and Toffoli gates and 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 gates and depth using ancillary qubits. Takahashi, Tani, and Kunihiro [8] reduced the ancillary space to 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 gates and 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 to while preserving its controls :
where is the control register and all bit arithmetic is over : 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 and partition the data into consecutive blocks , . The first index identifies the block and the second the position within it; controls the transition into that position, except that is absent. We use three steps: local ladders send to ; endpoint updates replace by ; and interior corrections replace the remaining by . 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 only when all controls in that block are one. Their product is the propagation control . Write and within this procedure. The endpoints themselves follow a ladder:
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 , which sends back to , into two operations that square to the identity:
Four additions between the endpoints and a borrowed register apply each factor and restore that register. Applying and then 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 for the original value of . Complement this bit, then add the conjunction into it. The resulting value satisfies . 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 lets us compute it from products of the original and encoded flags.
The remaining controls provide conditional space [9, 10]. Every term added to contains , so the update vanishes when . When , complementing these controls gives zero bits for the calculation. Echoes using zero tests apply the calculation only when , and two reads cancel the initial values of the borrowed data. A walk with stops needs such bits. Taking 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 and depth over .
The extra size factor comes from doing linear work at each of recursion levels. Each block needs conditional space because its walk can visit all earlier endpoints, so the blocks must remain large.
To remove this factor, we decompose into two weighted forest maps of height . Their edges connect endpoints, with propagation products as weights. Each block now follows a walk of only stops, so conditional space per block suffices and we can take . 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 gates and 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 within blocks: identifies the block, and 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 . The indicator is one exactly when every bit of is zero. Gate sequences are listed in execution order. Matrix products act on column vectors from right to left.
We count gates from 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 -controlled and a -bit incrementer each have size and depth , using one borrowed dirty bit. CNOT ladders, CNOT fanout (adding one source bit to several targets), and the common-control updates on disjoint pairs have linear size and logarithmic depth without additional wires. A negative control tests for zero. We obtain it by applying 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 in (2) runs the Toffoli updates in increasing order of . It acts on data bits and controls, using gates and depth . 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 on its input wires with size and depth gives an -bit adder on its two input registers with size and depth .
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 and for . Its inverse is the XOR prefix map. Let denote the ladder on whose transition is controlled by , and write . Starting from , run the following seven stages:
To see how the ladder computes the carry information, let , and let be the carry entering position in integer addition, with . The usual carry recurrence implies that satisfies
Thus stage 3 computes , and stage 4 XORs into , leaving . To restore , we next erase its carry information. Stage 5 uses the complemented controls in . The identity over gives
Stage 6 now restores , and stage 7 leaves , 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 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 , let be the 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 , where and are lower-triangular matrices given by Set and for . Moreover, .
Proof. We first check that each factor squares to the identity. For , compute the entries modulo :
Thus . The same calculation on coordinates gives . It remains to check that the product is . For , Pascal’s identity gives
where binomial coefficients outside their usual range are zero. Row zero is , so . ◻
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 and partition the data into consecutive blocks of size :
For general , take and adjust to bits. The same construction and asymptotic bounds apply to this partition. Each column in the figure is a block. Its bottom wire is the endpoint; positions form the interior. The colours track each data wire from its input , through the local output , to the final output .
The control for connects positions and within . For , connects the preceding endpoint to the first position; is absent. Local ladders omit the incoming controls. The recursive construction uses , ; the linear-size construction uses , .
Figure 1. The block framework with and , so . Each column represents one block, with its endpoint at the bottom. Arrows show propagation dependencies.
Local ladders. In panel 1, each column is processed independently: run within , using only . The blue outputs are
The block circuits have disjoint supports and run in parallel. If a local ladder has size and depth , the total size is and the depth is . We may use recursive local ladders or run their Toffoli gates directly in order. The direct implementation uses exactly Toffoli gates and has depth .
Endpoint update. In panel 2, only the bottom entries change from blue to green. Write and within this procedure. These endpoints form a ladder of their own:
Thus this step implements . The circuit evaluates each from the original block controls. It may temporarily modify those controls and borrow interior data, but it must restore both, leaving the interiors at . Its size and depth include all control evaluation and restoration. The following sections give two implementations of this step.
Interior correction. In panel 3, each corrected endpoint supplies the missing contribution to the next block’s interior. Block is already correct. For , follow the three parts of Figure 2. First undo the local ladder on positions , recovering . Next add to the first bit with one Toffoli gate. Finally, run the interior ladder forward again. It carries this incoming contribution through the block, giving
Figure 2. Interior correction for and . 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 and depth .
Lemma 5 (Block reduction). For the partition above, suppose the local ladders have ancilla-free implementations of size and depth . Suppose the endpoint update has size and depth , using only existing wires and restoring the controls and all borrowed interior data. Then has an ancilla-free implementation satisfying The incrementer correction in § 4.3 reduces the last depth term to .
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 , with . We work with the inverse map
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
The circuit evaluates these products from the original controls.
We have only borrowed interior bits for this update. We therefore decompose 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 , this gives
with zeros above the diagonal. Define in the same way using . In a matrix product, the weights from to and from to multiply to , independent of . The identities of Lemma 4 therefore give
Applying and then implements .
Using a borrowed register.
We focus on ; the construction for is the same with both Pascal indices decreased by one and coordinate zero fixed. Write . Our goal is to apply through additions between and the borrowed , restoring afterwards. We already have . For the cancellation, we also use the fixed backward shift
Thus, in , the output of row is added at position . This shift makes the echo work through the identity . For ,
The two weights cover the full interval from to and both contain . Since , their product is . For the second equality, add the terms and, when , . The enlarged sum is zero by Pascal’s rule and the calculation in Lemma 4. Removing these terms leaves . All other entries vanish. Decreasing the Pascal indices gives the same two identities for .
These identities give a circuit using borrowed interior bits for , disjoint from the endpoints:
The state expressions use the initial values of . In the second addition, removes the dependence on the first change to . In the third, the two copies of cancel and leaves the desired . The last addition restores because . 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 , the first addition is
with coordinate zero unchanged. It is enough to construct this addition while preserving and restoring the controls and temporary data. The other additions exchange the registers or redirect row to position .
Parallel walks along the chain
To compute the control products in (18), we separate each block’s last control from its remaining controls. Write
The block control is . 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
Call the new value . If , then ; if , then . Thus, on every input,
Figure 3 implements this encoding with one and one multi-controlled . The latter borrows and restores an interior bit . All blocks run in parallel, so has size and depth . It preserves and is its own inverse.
Figure 3. Using as a dirty flag for . The filled control on tests that all its bits are one. The multi-controlled borrows and restores .
To compute the sum for in (18), follow the chain . We call this a walk, with a stop at each earlier endpoint . The contribution from is controlled by
We therefore need to perform
For example, the three Pascal coefficients before the diagonal in row are odd, so its update is
The same physical wires hold before and afterwards. We therefore first compute and store it in borrowed data. This lets us keep while encoding the controls, then compute and combine the two products.
Computing before encoding.
To keep these products while changes the controls, borrow a word of interior data. Position corresponds to stop . We will add into and later cancel the initial value of this borrowed bit. For example, the three additions for the walk from are , , and .
We still need space to compute the products before adding them to . Every term added to contains , so the update is zero when . When , all bits of are one. Complementing them therefore gives 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 , the borrowed word , and two borrowed bits . The borrowed data are disjoint from , the endpoints, and the controls.
Figure 4. The chain construction with , . The orange wire has original value and encoded value . The green word contains positions . The borrowed bit above each block is used for zero tests. Below the endpoints are borrowed interior data: , the word of bits, and . The highlighted walk for visits .
When starts at zero, a circuit uses it to copy and compute all their running products, written . 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 bits and gates and depth. We take for a sufficiently large fixed , so the copies, products, and sums below fit inside , and the borrowed data fit inside the blocks. preserves all inputs outside 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 . Each level takes a constant number of gate layers.
The calculation above assumes that starts at zero. The echo in Figure 6 makes it take effect only when , while restoring on every input. Complement and toggle by . Run , add into , and reverse . Toggle by the same zero test and repeat these three operations, then undo the complements of . If , the zero test changes between the two calculations. Their contributions therefore add once, regardless of the initial value of . If , the zero test leaves unchanged. Both calculations then make the same addition, so they cancel even though began with nonzero bits. Thus the circuit performs
and restores . Call the parallel application of these circuits to all blocks .
Figure 6. Computing before encoding. The circuit for block adds into the borrowed word . computes the running products in when it starts at zero. An uncontrolled complements its word, and each open control tests the entire word for zero. The zero tests borrow and restore . All wires except return to their initial values.
Computing after encoding.
The first stage has added to the borrowed word and restored . We can therefore apply and read the encoded bits . Compute their running products with the same tree, then combine them with and in the sum
When starts at zero, let copy the encoded bits, , and into it, form the products, and compute this sum into its last position. Its products and sum take gates and depth. It preserves every bit outside .
The encoding leaves unchanged. The same echo can therefore still test whether its original bits were all one, the case . Figure 7 replaces by and each word addition by a Toffoli gate from to . When , the two additions give ; when , they cancel. Denote the parallel application of these circuits by . It performs , preserving and restoring . We can then apply to return the controls to their original values.
Figure 7. Computing with after encoding. The circuit for block adds to using the same dirty echo. The bracketed word includes the position used for . computes (23) in that position when starts at zero. The borrowed data and are preserved; all temporary calculations are reversed.
Combining and .
It remains to cancel the initial values in . Figure 8 runs the four stages twice. Suppose first that . The first changes to , and the first uses this value in its sum. The second restores , and the second uses its original value. Thus the two sums cancel the unknown initial values in . At stop , with , the contributions before applying the Pascal coefficient are
Here denotes its initial value. When , both stages leave unchanged, and every desired term is zero. This gives (18) while preserving and restoring all controls and borrowed bits.
Figure 8. The complete circuit for . Read from left to right. is the parallel application of Figure 6, and that of Figure 7. Each reads original controls; each reads encoded controls. The two reads of cancel its initial values and retain the products . The words 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 walks has at most stops, giving gates for copies, products, and sums. CNOT fanout trees copy shared inputs to the walks with gates and depth. The additions controlled by the same use the common-control circuit from the preliminaries, with linear size and logarithmic depth. The zero tests on and the constant number of encoding calls use gates and depth. The other additions in (17) exchange the registers or redirect their outputs, and changes the fixed Pascal selections.
Lemma 6 (Recursive endpoint circuit). For a sufficiently large fixed and , Step 2 has size and depth . 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 changes
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 and depth .
Figure 9. The incrementer correction used for the larger recursive blocks. The two bundled wires each contain bits, and the CNOTs act bitwise. The increment and its inverse act on the little-endian word , 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 as in Lemma 6, and take to be the largest power of two satisfying . Set
For the finitely many smaller sizes, use the direct ladder. Then , , and . Adjust for the remainder as in § 3. Its length lies between and , leaving enough interior data for its borrowed source bit.
The endpoint update now has size and depth . Run the local ladders recursively in parallel and use the interior correction above. The resulting bounds are
At each level, the blocks partition the data, so the work outside recursive calls is . At each level, the block size falls to its square root, up to a constant factor. It reaches constant size after levels, giving size . Along a branch, the logarithms of the block sizes decrease geometrically, so the depths sum to . 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 stops. Shortening the walks to 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 stops. We now shorten the walks to stops. The same circuit then needs only 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 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 . For , let be the largest integer such that divides , and write
Thus is the value of the lowest set bit in the binary expansion of . It determines the interval crossed by an edge. Both maps fix coordinate zero; for , define
To check that their product is , fix , set , and write for . The indices in the sum for are . For , we have , so
The second term of each pair is the first term of the next pair, so these terms cancel modulo . The last term cancels the extra term in , leaving , as required by (13). When is odd, and the sum is empty; already gives this update.
Figure 10 shows the two maps as forests: has an edge , and has an edge whenever the successor is at most . Each edge carries weight . 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 .
To apply the Pascal identities along a path, we need consecutive indices for its vertices. We call these indices grades. In , give vertex grade equal to its distance from the root. In , use 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 on the left has grades , while on the right has grades . Each path is therefore a ladder indexed by consecutive grades, with vertices drawn from possibly nonconsecutive endpoints. Its step from to is controlled by , the conjunction of all controls in blocks . Successive edge intervals are disjoint and concatenate, so the weight of a path is
The edge labels and products beneath the orange paths in Figure 10 illustrate this correspondence.
Figure 10. The two forests on endpoints , with . Green labels give the grade 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 , and define its factor by an identity diagonal and
All other entries below the diagonal are zero. Define in the same way with both grades decreased by one, setting its entries below the diagonal to zero when . 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
The parity of each binomial coefficient determines whether its path contribution is added. To apply , apply the two factors for and then those for , using followed by in each case.
Reusing the borrowed-register additions
For a forest factor , we use the four additions in (17) to apply and restore the borrowed . The identity follows again from . It remains to check for the same backward shift used in § 4.1.
For , expand . In , a nonempty directed path can start only at an even vertex. The contributing indices lie on the path from to , excluding , and vertex is a child of . In , a nonempty directed path can end only at a positive even vertex. Here the contributing vertices lie on the path after , including , and is the odd predecessor of . In both cases , and the possible grades range from to . The weights multiply to , since the repeated factor satisfies . Thus, on a nonempty path ,
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 , 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 . As before, we describe ; the other additions exchange the registers or redirect row to position .
Parallel walks from the blocks
The four-addition echo leaves us with the same task as before: implement
while restoring all temporary data. Here contains the block endpoints and is a borrowed register of interior bits. We first take for the outward forest. Expanding the update gives, for each endpoint,
where the sum runs over nonempty directed paths . In the left forest of Figure 10, these sources are the ancestors of other than itself. Each term uses the source bit , controlled by the product of edge weights along the path from to , namely . The Pascal coefficient depends only on the grades, so the circuit knows in advance which terms to include.
For example, when , the highlighted path in the left forest of Figure 10 contains vertices , with grades , respectively. Their endpoint updates are
For , walk along . The edge controls are , , and . 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 , walk along . Skip the addition at because , but retain the edge control : at , add . The walk adds to , and the root is unchanged. Each block has its own walk from vertex 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 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
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 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 contains . For example, with ,
If any control chosen for conditional space in is zero, the whole change vanishes. If all chosen controls are one, complementing them provides zero space. A walk now has only stops, so we need only such bits in each block. For the outward walks, the space in is used only to compute .
Figure 11 shows the bits used by the circuit. Take , assuming . 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 . The words , with one bit per stop, and the bits are borrowed from interior data, disjoint from and the endpoints. They may start in arbitrary states and will be restored. The bit is drawn above because it controls the use of .
Figure 11. The layout for , , and . Green bits form . The four bottom positions are , with physical coordinates . Blue positions are chosen at larger intervals; orange positions are chosen at . The grey positions in are left unchanged. The words , the bits , and are existing interior data, all restored by the circuit.
Encoding the interval products.
Let name four distinct control positions in . 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 , and its children use the pairs in . To see how the circuit works, consider the case where the root’s two bits enter at zero. First compute
Complement those four child bits, run the two child circuits, and then compute
The next layer repeats these gates: the call on uses the pairs in , and the call on uses those in . At a one-block interval , use and add the conjunction of the controls outside all chosen positions into . 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 . The root pair is shown after its initial complements, on the branch where it enters at zero. Each box continues the recursion on , 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:
Apply the following formula separately within each maximal dyadic interval, writing for its right endpoint. At the interval , choose the two positions , where
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 at . The interval inherits that pair and chooses in its other half. Its two children then inherit the pairs in and choose the pairs in . The interval starts with the pair in , and its children choose the pairs in . For the walk , the intervals , , and therefore have their encoded bits at , , and , respectively. When , these are positions , , and .
Figure 13. The chosen positions for : inherited positions in blue, newly chosen positions in orange. Each is one physical bit index in . The highlighted intervals supply the walk .
Write for the encoding. For an interval and its from (33), define
The parenthesized factor is one when . Here is a product of original delegate values, while is read after encoding. These quantities satisfy
To see why needs at most four controls, follow the chosen pairs down the tree. An internal interval ending at 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 inherits exactly . 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 .
If any of these original controls is zero, both and 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 . There are internal calls and size- work at each leaf. Hence has size and depth , where . 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 . The position for is again the last bit of , namely . Inside , the circuits now form their products along the forest paths.
For the walk , the three edge controls have the representations in (34)–(35). Before encoding, copies their original delegates into and computes
After encoding, copies the encoded bits and computes by the same products with in place of . Together with copies of , they give
In general, along , define
The word lists these products in walk order, and
Each original edge product uses at most four delegates. With only stops, these running products take gates and depth. Both compute into from unchanged outside inputs; leaves the position for untouched. Their inverses restore all temporary copies and products.
The circuits for and use the same zero-test echoes as in Figure 6 and Figure 7. Each is restored before every encoding or decoding, so and its inverse always see the correct control values. The two calls to each stage in Figure 8 restore and cancel its initial values by (24). At stop , the remaining contribution is
when its Pascal coefficient is odd. If any original control in 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 to source vertex . Its source bit is fixed at , and each visited vertex specifies an endpoint to change. At a stop , add when is odd. This interval contains , so the conditional space is . The running products are and , formed along the path from to . Different walks may reach the same endpoint, so we first store their contributions separately. Give each stop a borrowed bit . Here computes its individual terms in separate positions of and adds each term to its , controlled by . We then add the parity of the borrowed bits belonging to each endpoint. For example, the three walks from give
Add these three bits to , run their circuits again to restore them, and add the three bits to 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 . Each box runs the complete circuit with 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 , use as the source and in place of an update to . Every nonempty path ends at a positive index. For , omit terms whose source has grade zero and decrease both grades by one when selecting the additions.
Each walk has at most stops. The copies and running products in use at most bits of . For outward walks, uses at most bits, including ; for inward walks its separate terms use at most bits. All fit in positions and take gates and depth per walk. Copying shared inputs and adding the inward parities take 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 , each of the updates has size and depth . It uses 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 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 , let , and take to be the next power of two at least . Use the partition of § 3, with full blocks after . For the finitely many small sizes with , use the direct ladder. Otherwise , , and
The second inequality leaves enough unchanged control positions for in each block.
The borrowed data also fit inside the existing blocks. Let be the total number of stops in all walks. The dirty register , the words , the inward buffers, and the bits need at most
bits for sufficiently large . 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 and their depth is . The endpoint update uses sixteen calls to Lemma 7, each of size and depth . Finally, the direct interior correction of Figure 2 uses gates and 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 size bound for bounded-arity gates. The highest sum bit depends on all 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 . 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]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]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]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]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]Draper, T. G. (2000). Addition on a Quantum Computer. https://doi.org/10.48550/arXiv.quant-ph/0008033
- [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]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]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]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]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]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]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]Vandaele, V. (2026). Asymptotically Optimal Quantum Circuits for Comparators and Incrementers. https://doi.org/10.48550/arXiv.2603.12917













