A Classical-Quantum Adder with Constant Workspace and Linear Gates

Craig Gidney · 2025

Read A Classical-Quantum Adder with Constant Workspace and Linear Gates by Craig Gidney (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-23079.txt.

Introduction

Craig Gidney designs a quantum circuit that adds a known classical number into a quantum register, in this 2025 paper. Such adders are workhorses inside larger quantum algorithms, notably those that run modular arithmetic. A 2004 design handled quantum-plus-quantum addition cheaply, but the classical case stayed open.

Gidney's first adder uses only three clean spare qubits, no matter the size of the numbers, with gate cost growing in a straight line. A second version trims the gate count further by borrowing dirty spare qubits. Applying either adder under the control of another qubit costs nothing extra, which suits the big algorithms that need them.

Catalog record

CREATORCraig Gidney
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE15 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-23079

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Classical-Quantum Adder with Constant Workspace and Linear Gates Craig Gidney Abstract In 2004, Cuccaro et al found a quantum-quantum adder with O ⁡ ( n ) O(n) gate cost and O ⁡ ( 1 ) O(1) ancilla qubits. Since then, it’s been an open question whether classical-quantum adders can achieve the same asymptotic complexity. These costs are particularly relevant to modular arithmetic circuits, which often offset by the classically known modulus. In this paper, I construct an adder that uses 3 clean ancillae and 4 ​ n ± O ⁡ ( 1 ) 4n\pm O(1) Toffoli gates to add a classical offset into a quantum register. I also present an adder with a Toffoli cost of 3 ​ n ± O ⁡ ( 1 ) 3n\pm O(1) that uses 2 clean ancillae and n − 2 n-2 dirty ancillae. I further show that applying the presented adders conditioned on a control qubit requires no additional workspace or Toffolis. Data availability : Code and assets created for this paper are available on Zenodo [ Gid25 ] . 1 Introduction The first quantum adder circuits needed \Theta(n) gates and \Theta(n) workspace qubits [ VBE96 ] . In 2004, Cuccaro et al found a way to eliminate the workspace, while preserving the \Theta(n) gate count, by temporarily moving carry information into the qubits of the offset register [ Cuc+04 ] . However, this can’t work for classical-quantum adders where the offset is stored in bits instead of qubits. Extending the Cuccaro result to the classical-quantum case has remained an open problem since 2004. There was some progress on the problem, between 2004 and now. In 2015, I found a solution for the special case where the offset is 1 [ Gid15 ] . In 2016, Häner et al found a divide-and-conquer classical-quantum adder that used 1 dirty qubit and \Theta(n\lg n) gates [ HRS17 ] . But reaching the asymptotic limit of \Theta(n) gates remained unsolved. In this paper I finally close the remaining asymptotic gap, achieving an \Theta(n) gate count under the constraint of O(1) ancilla qubits. The new construction is based on three key ideas: 1. The ripple carry process of an addition can be streamed with constant workspace by eagerly “venting” carry qubits (measuring them in the X basis as part of a measurement based uncomputation [ Gid19a ] ). This venting process leaves behind phasing tasks that correspond to applying a Z gate to some of the carries of the addition. 2. The vented phasing tasks can be resolved later by interleaving phase flips and Häner et al’s construction for xoring carries into a secondary register [ HRS17 ] . 3. Dirty workspace (e.g. the secondary register targeted by the carry-xor) can be provided by splitting the addition into two halves, with each half borrowing the other as dirty workspace. The paper is structured as follows. In Section 2 , I explain the construction of the adder and some variants. In Section 3 , I summarize the results. 2 Construction 2.1 Notation The bit at index k of an integer x is referred to as x_{k} (for example x_{0} is the even-vs-odd bit): x_{k}=\lfloor x/2^{k}\rfloor\bmod 2 (1) The bitwise xor of x and y is written x\oplus y : x\oplus y=\sum_{k=0}^{\infty}(x_{k}+y_{k}-2x_{k}y_{k})2^{k} (2) (Use the 2-adic metric to get the above sum to converge when x or y are negative.) The bitwise complement of x is written \sim x : \sim x=-1\oplus x=-1-x (3) The majority of three bits is the most common bit value among the three: \displaystyle\text{maj}(a,b,c) \displaystyle=\lfloor(a+b+c)/2\rfloor (4) \displaystyle=((a\oplus c)\cdot(b\oplus c))\oplus c The “carry” of an addition is the extra bit flips that occur due to propagating carries (including from the carry input bit c_{0} ). It’s the xor between the actual result of the addition and the xor of its two inputs: \text{carry}(x,d,c_{0})=x\oplus d\oplus(x+d+c_{0}) (5) Lastly, this paper uses some non-standard circuit notation defined in Figure 1 . Figure 1: Non-standard circuit notation in this paper. Left: Bit-inverted controls. A black box containing the text " Z\oplus b " means the control’s required value is inverted when the bit b is True. Middle: Controlling with a ZZ operator. Conditioning on a multi-qubit parity operator, like ZZ , is shown as black boxes to the side of the control line indicating each of the Z terms. Right: Controlling with the intersection of two ZZ operators. When an operation has two parity controls, terms from one are placed to the left of the control line while terms from the other are placed to the right. I prefer parity controls over CNOT gates because accessing ZZ is notably cheaper than doing CNOTs when compiling into lattice surgery. 2.2 Streaming Addition by Venting Carries When performing an addition x^{\prime}=x+d+c_{0} (6) the first carry bit c_{0} is given as an input, and each subsequent carry bit c_{k} is the majority of the previous carry bit and bits from the two values being added: c_{k+1}=\text{maj}(x_{k},d_{k},c_{k}) (7) After c_{k} is computed, a bit of the sum x^{\prime}_{k}=x_{k}\oplus d_{k}\oplus c_{k} can be computed. Then one of the input bits can be uncomputed (because x_{k}=x^{\prime}_{k}\oplus d_{k}\oplus c_{k} ) and the next carry bit c_{k+1} can be computed. At this point c_{k} becomes unwanted garbage. Getting rid of this carry garbage is a key obstacle in most quantum adder designs. An important property that carries satisfy is that the carries produced when computing a sum are reproduced by adding the same offset into the bitwise complement of the sum: \displaystyle\text{carry}(\sim x^{\prime},d,c_{0}) (8) \displaystyle=\Big(\sim x^{\prime}\Big)\oplus d\oplus\Big(\sim x^{\prime}+d+c_{0}\Big) \displaystyle=\Big(\sim(x+d+c_{0})\Big)\oplus d\oplus\Big(\sim(x+d+c_{0})+d+c_{0}\Big) \displaystyle=\Big(\sim(\text{carry}(x,d,c_{0})\oplus x\oplus d)\Big)\oplus d\oplus\Big(-1-(x+d+c_{0})+d+c_{0}\Big) \displaystyle=\Big(-1\oplus\text{carry}(x,d,c_{0})\oplus x\oplus d\Big)\oplus d\oplus\Big(-1-x\Big) \displaystyle=-1\oplus\text{carry}(x,d,c_{0})\oplus x\oplus d\oplus d\oplus-1\oplus x \displaystyle=\text{carry}(x,d,c_{0}) Because of Equation 8 , each carry qubit is a Z-basis function of values available after the addition completes (the carries are “Z-redundant”). Measuring a Z-redundant qubit q in the X basis produces a 50/50 random result, where the |+\rangle result means q ’s value was deleted with no consequences and the |-\rangle result means q ’s value was deleted but an unwanted phase flip Z_{q} occurred just before the deletion [ Gid19a ] . The deletion is completed by eventually correcting the unwanted phase flip. Therefore, one way to get carry garbage out of qubits is by converting the garbage into unwanted phase flips by measuring the qubits in the X basis. Throughout the paper I refer to this conversion process, from Z-redundant qubits into unwanted phasing tasks, as “venting”. An adder based on venting carries is shown in Figure 2 . This adder leaves behind unwanted phasing tasks, but only requires two clean ancilla qubits of workspace. Figure 2: An n=6 example of an adder that vents carries in order to only use 2 clean ancilla and n\pm O(1) Toffolis. Performs \text{target}\rightarrow(\text{target}+d+\text{carry}_{\text{in}})\bmod 2^{n} , except that completing the addition requires performing phase flips based on the vented values m_{0},\dots,m_{n-3} . If m_{k} is true, then a phase flip by \text{carry}(\sim\text{target}^{\prime},d,\text{carry}_{\text{in}})_{k+1} is needed, where \text{target}^{\prime} is the value of the target register after the addition. Click here to open this circuit, specialized to d=43 , in Quirk. 2.3 Phasing by Carries In [ HRS17 ] , Häner et al describe a “carry-xor” circuit that performs g\rightarrow g\oplus\text{carry}(x,d,c_{0}) . It xors the carries

Read the complete text