# Measurement-based uncomputation of
quantum circuits for modular arithmetic

Alessandro Luongo  Centre for Quantum Technologies, National University of
Singapore, Singapore Inveriant Pte. Ltd., Singapore  Antonio Michele Miti
Department of Mathematics, Sapienza Università di Roma, Rome, Italy  Varun
Narasimhachar  A*STAR Quantum Innovation Centre (Q.InC), Institute of High
Performance Computing (IHPC), Agency for Science, Technology and Research
(A*STAR), Singapore.  Adithya Sireesh  School of Informatics, University of
Edinburgh, Scotland, United Kingdom  Corresponding author<EMAIL_ADDRESS>
###### Abstract

Measurement-based uncomputation (MBU) is a technique used to perform
probabilistic uncomputation of quantum circuits. We formalize this technique
for the case of single-qubit registers, and we show applications to modular
arithmetic. First, we present formal statements for several variations of
quantum circuits performing non-modular addition: controlled addition,
addition by a constant, and controlled addition by a constant. We do the same
for subtraction and comparison circuits. This addresses gaps in the current
literature, where some of these variants were previously unexplored. Then, we
shift our attention to modular arithmetic, where again we present formal
statements for modular addition, controlled modular addition, modular addition
by a constant, and controlled modular addition by a constant, using different
kinds of plain adders and combinations thereof. We introduce and prove a “MBU
lemma” in the context of single-qubit registers, which we apply to all
aforementioned modular arithmetic circuits. Using MBU, we reduce the Toffoli
count and depth by $10\%$ to $15\%$ for modular adders based on the
architecture of [VBE96], and by almost $25\%$ for modular adders based on the
architecture of [Bea02]. Our results have the potential to improve other
circuits for modular arithmetic, such as modular multiplication and modular
exponentiation, and can find applications in quantum cryptanalysis.

##  1 Introduction

Consider a quantum circuit $U_{f}$ computing a Boolean function
$f:\\{0,1\\}^{n}\to\\{0,1\\}^{m}$ between bit strings. When $f$ is invertible
(meaning that $f$ is injective and $n=m$) we say that $U_{f}$ computes $f$
_in-place_ if it performs the mapping

$U_{f}:\ket{x}_{n}\mapsto\ket{f(x)}_{m}$ (1)

for any bit string $x\in\\{0,1\\}^{n}$, where we use the subscripts to denote
the number of qubits in a quantum register. An in-place implementation is not
always possible. In the most general case, one needs to compute $f$ _out-of-
place_ , meaning that the circuit $U_{f}$ realises the following mapping

$U_{f}:\ket{x}_{n}\ket{0}_{m}\mapsto\ket{x}_{n}\ket{f(x)}_{m}~{}.$ (2)

A realistic implementation of the above gate will, in principle, involve a
number $k$ of auxiliary qubits which get mapped in a _garbage_ state
$\ket{g(x)}$ as follows:

$\widetilde{U}_{f}:\ket{x}_{n}\ket{0}_{m}\ket{0}_{k}\mapsto\ket{x}_{n}\ket{f(x)}_{m}\ket{g(x)}_{k}.$
(3)

The auxiliary qubits are entangled with the other registers and must be
uncomputed, i.e. restored to their original value, in order to get a
reversible out-of-place implementation of $f$. Such uncomputation can be
achieved in several ways. A first solution, due to [Ben73], simply prescribes
copying the output $\ket{f(x)}_{m}$ into an auxiliary $m$-qubit register via a
set of $m$ CNOT gates and then apply $\widetilde{U}_{f}^{\dagger}$. Therefore,
one can implement $U_{f}$ as in figure 1.

Figure 1: Bennet’s garbage uncomputation.

This strategy doubles the resource cost of the reversible computation of $f$,
also requiring $m$ more ancillary qubits. Alternatively, one could look for an
out-of-place implementation of the garbage function $U_{g}$, seeing $g$ as a
function of $x$ and $f(x)$. When this unitary is available, one can implement
$U_{f}$ as in figure 2.

Figure 2: Garbage gate uncomputation.

In principle, invoking the garbage circuit $U_{g}$ can be quite resource
intensive. Therefore, it is necessary to develop techniques to optimize the
synthesis of quantum circuits and their uncomputation.

#### Arithmetic Circuits.

Effective implementations of binary arithmetic are fundamental to many quantum
algorithms, such as quantum algorithms for factoring [Sho94, GE21] and
discrete logarithm [Eke18], quantum walks [Chi02], and for algorithms that
construct oracles for Grover’s search and quantum phase estimation, e.g.
[Ber+19, Dor+22, Agg+17]. Arithmetic operations like (modular) addition,
subtraction, and comparison (by a constant) have been extensively studied,
resulting in numerous implementation strategies, each with its own tradeoffs.
Many circuits for arithmetic are based on the plain addition circuit defined
by the operation
$\ket{x}_{n}\ket{y}_{n}\xmapsto{\mathsf{Q_{ADD}}}\ket{x}_{n}\ket{x+y}_{n+1}$
for two $n$-qubit quantum registers. Other primitives can be derived by
composing these circuits for addition. However, there are often more efficient
ways to build arithmetic primitives. Broadly, these quantum circuits are
designed for both quantum-quantum arithmetic functions, i.e., circuits of the
form $\ket{x}\ket{y}\xmapsto{\mathsf{U}}\ket{x}\ket{f(x,y)}$, and quantum-
classical arithmetic functions, i.e., circuits of the form
$\ket{x}\xmapsto{\mathsf{U}(a)}\ket{x}\ket{f(x,a)}$.

In the computation of our function $f$, intermediate values may need to be
appropriately uncomputed. For example, any _ripple carry_ addition algorithm,
analogously to the _schoolbook_ addition method, requires computing the carry
bitwise starting from the least significant bits of the two addends.

However, this process leaves carry bits in memory, which need to be uncomputed
from the rest of the registers to ensure the correctness of the computation.
Efficient quantum arithmetic circuits are pivotal for advancing quantum
computing, underpinning numerous key algorithms. This also involves finding
cheaper ways of performing uncomputation on qubits storing
garbage/intermediate computations.

###  1.1 Main results

In this work, we improve quantum circuits for modular arithmetic using
measurement-based uncomputation, specifically focusing on quantum modular
adders. In section 2, we begin by formalizing previously known circuits for
addition and defining in a theorem the resources required for their
implementation. For all the adders we consider [Cuc+04, VBE96, Dra00, Gid18],
we also cover the possible cases for (controlled) addition, subtraction and
comparison (by a constant). While these constructions can be easily derived,
we could not find records of many of them in previous literature, e.g.,
(controlled) comparator by a constant, controlled modular addition, etc. We
offer a modular and composable framework to construct these arithmetic
circuits from other known arithmetic primitives. We also show a construction
for a controlled adder using just a single ancilla by modifying the CDKPM
adder (theorem 2.12). In section 3, we consider various tradeoffs for
combining the results presented in the previous section to form a quantum
circuit that performs a (controlled) modular addition (by a constant). In
particular, we show how two different adder architectures (the CDKPM adder
[Cuc+04] and Gidney adder [Gid18]) can be combined, leading to better space-
time tradeoffs compared to using either adder individually within the modular
adder architecture (see theorem 3.6). These tradeoffs are particularly
important when running quantum algorithms in early error-corrected settings.
In section 4, we discuss the proof of the measurement-based uncomputation
lemma, which we present below. This technique was already known in the
literature [Gid18, KSS21, Gid19], but to the best of our knowledge, it has not
been formalized as a plug-and-play result. While MBU can be generalized to
uncomputation of multi-qubit registers, for modular arithmetic we can use the
following lemma.

######  Lemma (Measurement-based uncomputation lemma).

Let $g:\,\\{0,1\\}^{n}\to\\{0,1\\}$ be a function, and let $U_{g}$ be a self-
adjoint $(n+1)$-qubit unitary that maps
$U_{g}\ket{x}_{n}\ket{b}_{1}=\ket{x}_{n}\ket{b\oplus g(x)}_{1}$. There is an
algorithm performing the mapping
$\sum_{x}\alpha_{x}\ket{x}_{n}\ket{g(x)}_{1}\mapsto\sum_{x}\alpha_{x}\ket{x}_{n}\ket{0}_{1}$
using $U_{g}$, $2$ $\mathsf{H}$ gates, and $1$ $\mathsf{NOT}$ gate with $1/2$
probability. It also involves one single-qubit computational basis measurement
and a single $\mathsf{H}$ gate.

Applying the MBU lemma leads to gate costs expressed _“in expectation”_. The
expected value is calculated based on a Bernoulli distribution with a
probability $p=\frac{1}{2}$. This is because, for any quantum state
$\sum_{x}\alpha_{x}\ket{x}_{n}\ket{g(x)}_{1}$, if $g(x)\in\\{0,1\\}$, when the
last register is measured in the $X$ basis, there is an equal probability of
obtaining a $\ket{0}$ or $\ket{1}$ state. The remainder of section 4 is
dedicated to deriving formal statements for modular addition circuits
optimized by MBU. While table 1 presents our results for modular addition
(section 4.1), we also share resource counts for controlled modular addition
(section 4.2), modular addition by a constant (section 4.3), and controlled
modular addition by a constant (section 4.4). For example, for the controlled
modular adder derived from [Cuc+04], MBU can reduce the $\mathsf{Tof}$
(Toffoli) count by $n+\frac{1}{2}$ gates in expectation (compare proposition
3.4 with proposition 3.10). The minimum number of $\mathsf{Tof}$ gates is
achieved by proposition 3.11 using $2n+2$ ancilla qubits. For modular addition
by a constant, MBU reduces the $\mathsf{Tof}$ count by $n$ gates in
expectation (compare proposition 3.15 with theorem 4.11), leading to a
$16.7\%$ improvement on the original circuit. We obtain similar improvements
for controlled modular addition by a constant. We also show a way to perform a
double-sided comparison (theorem 4.13), i.e. to see if a given register’s
value is contained within two other register’s values. This circuit is a prime
candidate for MBU, leading to a nearly $25\%$ reduction in the cost of the
circuit.

width=  Logical Qubits Toffoli CNOT,CZ X w/o MBU with MBU w/o MBU with MBU w/o
MBU with MBU (5 adder) VBE [VBE96] $4n+2$ $20n+10$ $16n+8$ $20n+2|p|+22$
$16n+2|p|+18$ $|p|+2$ $|p|+2.5$ (4 adder) VBE $4n+2$ $16n+4$ $14n+4$
$20n+2|p|+18$ $17n+2|p|+15.5$ $2|p|+1$ $2|p|+1.5$ CDKPM [Cuc+04] $3n+2$ $8n$
$7n$ $16n+2|p|+4$ $14n+2|p|+3.5$ $2|p|+1$ $2|p|+1.5$ Gidney [Gid18] $4n+2$
$4n$ $3.5n$ $26n+2|p|+4$ $22.75n+2|p|+3.5$ $2|p|+1$ $2|p|+1.5$ CDKPM+Gidney
$3n+2$ $6n$ $5.5n$ $21n+2|p|+4$ $17.75n+2|p|+3.5$ $2|p|+1$ $2|p|+1.5$ Logical
Qubits $\mathsf{QFT}_{n+1}$ $\mathsf{PCQFT}_{n+1}$ - w/o MBU with MBU w/o MBU
with MBU - - Draper [Dra00] $2n+2$ $10$ $8$ $1$ $1$ Draper (Expect) $2n+2$ $8$
$6$ $1$ $1$

Table 1: Cost of modular addition using different plain adder circuits in the
VBE architecture of modular addition. We denote by $|p|$ the Hamming weight of
the bit string of the number $p$ expressed in binary expansion.
$\mathsf{PCQFT}$ stands for “partially-classical” quantum Fourier transform,
where each controlled rotation in the $\mathsf{QFT}$ is replaced by a
classically controlled rotation. Every row in this table corresponds to a
theorem in our manuscript. Results with MBU are considered “in expectation.”.
Here, Draper (Expec) represents the repeated use of the Draper addition
circuit. In expectation, the cost of the first $\mathsf{QFT}$ and last
$\mathsf{IQFT}$ become negligible compared to the rest of the circuit.

Our work has the potential to improve quantum circuits for modular
multiplication, modular exponentiation, and quantum circuits for cryptographic
attacks [Wan+24, VBE96, Wan+24a]. We leave this research for future work. The
interested reader can access 111https://github.com/AdithyaSireesh/mbu-
arithmetic the code for symbolic computation of some of the statements
presented in this work.

###  1.2 Related works

This section reviews recent progress in quantum circuits for modular
arithmetic, with a focus on optimizing size and depth. Then, we turn our
attention to previous applications of measurement-based uncomputation. Early
proposals for quantum addition [Cuc+04, VBE96, Dra+04], some of which are
employed in fault-tolerant algorithms with state-of-the-art resource estimates
[GE21, Lit23, Gou+23], were inspired by classical circuits for addition, with
an emphasis on minimizing the $\mathsf{T}$ count and/or the $\mathsf{Tof}$
(Toffoli) count, and the number of ancilla qubits. Subsequent approaches have
explored more quantum-specific methods of performing arithmetic [Zal06, Dra00,
Bea02, Yua+23]. A nice quantum-specific way to perform a modular addition into
a quantum register $\ket{x}_{n}$ was developed by Zalka [Zal06]. It involves
only a single non-modular addition (with modulus $p$) as long as $\ket{x}_{n}$
is prepared in a _coset state_ : $\sum_{c=0}^{2^{k}-1}\ket{x+c\cdot p}_{n+k}$.
The overhead here is that the size of the padding (i.e. the value of $k$ of
extra qubits required) for the coset state grows logarithmically in the number
of additions that are to be performed (See [Gid19] for more details). All
these arithmetic circuits listed previously (and many others) serve as
building blocks for more complex operations such as modular addition,
multiplication, and exponentiation, to name a few. Another survey on quantum
adders can be found in [Tak09]. The interested reader is encouraged to read
[Wan+24a] for a comprehensive literature review.

#### Measurement-Based Uncomputation (MBU).

Measurement-based uncomputation (MBU) was developed to efficiently address the
challenge of uncomputing boolean functions. MBU is a technique used to perform
uncomputation in a probabilistic manner [Gid18]. This technique involves
measuring the qubits to be uncomputed on the $X$ basis. Depending on the
outcome of the measurement, either the uncomputation circuit is executed, or
it is determined that the uncomputation has already been completed, thereby
reducing the overall quantum resource requirements.

MBU has been employed in several cases [Gid18, KSS21, Gid19, Gid19b] to
improve the resource counts of uncomputation. In particular, Gidney applied
this strategy to addition circuits in [Gid18]. Starting from a Ripple Carry
Addition (RCA) algorithm (see section 2 for details), they manage to reduce
the $\mathsf{T/Tof}$ gate cost by replacing every $\mathsf{Tof}$ gate with a
temporary logical-$\mathsf{AND}$ gate (equivalent to a $\mathsf{Tof}$ gate).
While a $\mathsf{Tof}$ gate performs the mapping
$\ket{x}_{1}\ket{y}_{1}\ket{t}_{1}\xmapsto{\mathsf{Tof}}\ket{x}_{1}\ket{y}_{1}\ket{x\cdot
y\oplus t}_{1}$, the logical-$\mathsf{AND}$ gate uses an ancilla qubit to
execute the $\mathsf{Tof}$ gate as follows:

$\ket{x}_{1}\ket{y}_{1}\ket{t}_{1}\ket{0}_{1}\xmapsto{\mathsf{Tof}}\ket{x}_{1}\ket{y}_{1}\ket{t}_{1}\ket{x\cdot
y}_{1}\xmapsto{\mathsf{CNOT}}\ket{x}_{1}\ket{y}_{1}\ket{x\cdot y\oplus
t}_{1}\ket{x\cdot y}_{1}~{}.$

Since the $\mathsf{Tof}$ gates come in pairs (the $\mathsf{Tof}$ gates used in
the RCA computation must also be uncomputed), MBU is used to avoid performing
a $\mathsf{Tof}$ gate for the uncomputation, replacing it with an $X$ basis
measurement followed by a classically controlled $\mathsf{C\text{-}Z}$ gate.
In [Gid19], MBU is used to construct the coset state more effectively. In the
QROM lookup circuits introduced in [Bab+18, Gid19b], MBU is used to construct
a highly efficient unlookup (uncomputation of lookup) operation. For an
address register $\ket{a}_{n}$, a lookup table performs the operation

$\ket{a}_{n}\xmapsto{\mathsf{Lookup}}\ket{a}_{n}\ket{\ell_{a}},$ (4)

where $\ell_{a}$ is the lookup value associated with address $a$. An address
register of size $n$ qubits corresponds to a lookup table of $L=2^{n}$
elements, making the cost of performing a lookup $L=2^{n}$ Toffolis. After
$\ell_{a}$ has been used in the computation, it must be uncomputed. Naively
performing the uncomputation would cost the same as the lookup. However, by
combining unary encoding with MBU, it is possible to reduce the cost of the
uncomputation to just $\sqrt{L}$ [Bab+18, Gid19b] gates.

Other works study the more general problem of reversibly computing a chain of
functions $x_{0}\xmapsto{f_{1}}x_{1}=f_{1}(x_{0})\xmapsto{f_{2}}\cdots
x_{m-1}=f_{m-1}(x_{m-2})\xmapsto{f_{m}}x_{m}=f_{m}(x_{m-1})$ through the use
of pebbling games [Ben89]. Pebbling games offer a way to perform these
computations reversibly and find effective ways of studying space-time
tradeoffs of various strategies to uncompute intermediate results. In the case
of chains of unitaries $\\{\mathsf{U}_{f_{i}}\\}_{i=1}^{m}$, spooky pebble
games were introduced by Gidney [Gid19a], which allowed $X$ basis quantum
measurements as an additional operation in pebbling games. The measurements
may result in a phase applied to the states in the superposition, which is
then tracked and corrected at a later time in the computation.

###  1.3 Notation and convention

We assume basic knowledge of quantum computing; we refer the interested reader
to [NC11]. As in [Cuc+04], we denote the quantum registers by capital letters
$A,B,C$, etc. Each register is encoded with several qubits; we denote by
$A_{i}$ the $i$-th qubit of register $A$. Each qubit can be understood as a
memory location; if not differently stated, we will assume that in qubit
$A_{i}$ is initially stored the value $a_{i}$. We represent the state of a $n$
qubit register $A$ as $\ket{a}_{n}$. In principle, applying a quantum gate to
a given register affects the values stored in its qubit; we denote by
$A_{i}\leftarrow x$ the storing of value $x\in\\{0,1\\}$ in the $i$-th
component of register $A$ as the result of a certain quantum circuit. Where
necessary, we put the number of qubits in a register as a subscript following
the ket representing the register’s state, e.g. $\ket{x}_{n}$ for an $n$-qubit
register. For an $n$ bit string $\mathbf{x}=x_{n-1}x_{n-2}\dots
x_{0}\in\\{0,1\\}^{n}$ we shall often equate it with the decimal number $x$
encoded in binary by $\mathbf{x}$. We denote with $a|_{n}$ the $n$ bit string
encoding the number $a\in\\{-2^{n},\dots,0,1,\dots,2^{n}-1\\}$ in the $2$’s
complement notation (see remark A.4 in the appendix). For a number
$a\in\mathbb{N}$, $|a|$ denotes the Hamming weight of the binary
representation of $a$. The interested reader is referred to [Von93] or [HH10]
and appendix A for further details on bit strings operations.

#### Quantum computing.

We recall the definition of the following single-qubit gates.

$\mathsf{X}=\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}$,
$\mathsf{Z}=\begin{bmatrix}1&0\\\ 0&-1\end{bmatrix}$,
$\mathsf{S}=\begin{bmatrix}1&0\\\ 0&\mathrm{i}\end{bmatrix}$,
$\mathsf{T}=\begin{bmatrix}1&0\\\ 0&e^{\mathrm{i}\pi/4}\end{bmatrix}$ .

We denote by $\mathsf{C}_{i}\text{-}\mathsf{R}_{j}(\theta_{k})$ the rotation
by $\theta_{k}=2\pi/2^{k}$ of qubit $j$ controlled by qubit $i$ (See figure
3). We can eventually use register names indexed by its qubits: e.g.
$\mathsf{C}_{X_{j}}\text{-}\mathsf{R}_{Y_{i}}(\theta_{k})$ performs a
controlled rotation between the $j$-th qubit in the register $X$ and targets
the $i$-th qubits in the register $Y$. We define the function
$\mathbf{1}[\mathsf{condition}]$ to be $1$ if $\mathsf{condition}$ is true,
otherwise is $0$. In the case of a $\mathsf{QFT}$ based adder by a constant,
we use $\mathsf{PCQFT_{a,n}}$ to denote a classically controlled set of
rotation gates that need to be applied in order to perform the required
addition in the phase.

Figure 3: Quantum Controlled Rotation Gate. We show both the circuit
representation and the corresponding unitary matrix of the controlled
rotation. The $i$ and $j$ correspond to the two qubits involved in the
controlled rotation.

Let $y\in\\{0,1\\}^{n}$. The state obtained after applying the quantum Fourier
transform (see e.g. [NC11]) $\mathsf{QFT}$ to the state $\ket{y}$ is given by

$\ket{\phi(y)}_{n}:=\mathsf{QFT}_{n}\ket{y}_{n}=\frac{1}{2^{n/2}}\sum_{x}e^{2\pi\mathrm{i}xy/2^{n}}\ket{x}_{n}.$

We denote by $\mathsf{QFT}_{n}$ the quantum Fourier transform acting on a $n$
qubits register and by $\mathsf{IQFT}_{n}$ its inverse.

Let $\mathsf{Q}$ be a quantum circuit composed of $m$ gates $\mathsf{Q}_{j}$
from a gateset
$\mathcal{G}=\\{\mathcal{G}_{1},\mathcal{G}_{2},\ldots,\mathcal{G}_{K}\\}$.
Define the gate count
$c_{i}:=|\\{j\in[m]\mid\mathsf{Q}_{j}=\mathcal{G}_{i}\\}|$ for $i\in[K]$. We
represent the gate counts of $\mathsf{Q}$ as

$\mathsf{count}(\mathsf{Q})=\\{(\mathcal{G}_{i},c_{i})\mid i\in[K]\\}.$

######  Remark 1.1 (Circuit size of QFT [NC11]).

A $\mathsf{QFT}_{m}$ has a circuit size of

$\mathsf{count}(\mathsf{QFT}_{m})=\\{(\mathsf{H},m)\\}\cup\\{(\mathsf{C\text{-}R}(\theta_{i}),m+1-i)\mid
i\in[1,m+1]\\}.$

#### Boolean arithmetic.

In this paragraph, we will review some basic definitions of bit string
arithmetic. Denote by $\mathbf{x}=x_{n-1}\dots x_{0}\in\\{0,1\\}^{n}$ a
$n$-bit string i.e. a string of $n$ binary numbers. Further facts about the
bit string representation of integers are reported in appendix A. We consider
the following four operations on the set of $n$-bits string.

######  Definition 1.2 (Bit string addition).

We call _bit string addition_ the binary operator

$+:~{}\\{0,1\\}^{n}\times\\{0,1\\}^{n}\to\\{0,1\\}^{n+1}~{},(\mathbf{x},\mathbf{y})\mapsto\mathbf{s}$

defined bit-wise by $s_{i}=x_{i}\oplus y_{i}\oplus c_{i},$ where the bit
$c_{i}$, called $i$-th carry, is defined recursively by

$\displaystyle c_{0}$ $\displaystyle=0$ $\displaystyle c_{i}$
$\displaystyle=\textrm{maj}(x_{i-1},y_{i-1},c_{i-1})=x_{i-1}y_{i-1}\oplus
x_{i-1}c_{i-1}\oplus y_{i-1}c_{i-1}~{}.$ (5)

The function maj is a logic gate called _majority_ , which gives $1$ whenever
at least two of the three entries are different than $0$.

######  Definition 1.3 (Bit string $1$’s complement).

We call _$1$ ’s complement_ the operator defined bit-wise by
$(\overline{\mathbf{x}})_{i}=x_{i}\oplus 1$ as

$\overline{~{}\cdot~{}}:~{}\\{0,1\\}^{n}\to\\{0,1\\}^{n}~{},\mathbf{x}\mapsto\overline{\mathbf{x}}.$

######  Definition 1.4 (Bit string $2$’s complement).

We call _$2$ ’s complement_ the operator defined as
$\overline{\overline{\mathbf{x}}}=\overline{\mathbf{x}}+\mathbf{1}$, where
$\mathbf{1}$ denotes the $n$ bits string $0\,\dots 0\,1$ as

$\overline{\overline{~{}\cdot~{}}}:~{}\\{0,1\\}^{n}\to\\{0,1\\}^{n}~{},\mathbf{x}\mapsto\overline{\overline{\mathbf{x}}}.$

######  Definition 1.5 (Bit string subtraction).

We call _bit string subtraction_ the binary operator

$-:~{}\\{0,1\\}^{n}\times\\{0,1\\}^{n}\to\\{0,1\\}^{n+1}~{},(\mathbf{x},\mathbf{y})\mapsto\overline{\left(\overline{\mathbf{x}}+\mathbf{y}\right)}~{}.$

The string $\mathbf{d}=\mathbf{x}-\mathbf{y}$ is given bit-wise by
$d_{i}=x_{i}\oplus y_{i}\oplus b_{i}$, where the bit $b_{i}$, called $i$-th
borrow, is defined recursively by

$\displaystyle b_{0}$ $\displaystyle=0$ $\displaystyle b_{i+1}$
$\displaystyle=\textrm{maj}(x_{i}\oplus 1,y_{i},b_{i})~{}.$ (6)

Naming convention for theorems and propositions. As a guideline, we use
“proposition” to refer to statements already present in the literature; in
cases where we are unaware of a formal proof in the literature, we provide
one. We use “theorem” to denote facts first stated and proven in this
manuscript (to the best of our knowledge). We use the convention “operation
name - subroutine variant used (if any) - additional descriptors (if any)” to
name theorems and propositions. For example, “Comparator - CDKPM - using half
a subtractor” represents a quantum comparator operation based on a subroutine
variant by authors CDKPM, using a partial subtraction circuit.

##  2 Quantum adders

######  Definition 2.1 (Quantum addition).

We define a _quantum adder_ as any unitary gate implementing the $n$-bit
strings addition (see definition 1.2) according to the following circuit

The initial extra qubit, prepared in $\ket{0}$, in the second register is
needed to take into account the possible overflow. Note that by the theory of
bit string additions (see appendix A and section 1.3), such a circuit
implements both the addition of unsigned integers, interpreting the bit string
$x$ with the corresponding decimal number, and the addition of signed
integers, interpreting the two entries in the 2’s complement convention.
Several quantum implementations of bit string addition have been discussed in
the literature. Due to their significant role as the fundamental components of
quantum arithmetic, we recollect four of them for the sake of completeness.

Procedure | Toff. Count | Ancillas | CNOT | Ref.
---|---|---|---|---
VBE plain adder [VBE96] | $4n$ | $n$ | $4n+4$ |  prop. 2.2
CDKPM plain adder [Cuc+04] | $2n$ | $1$ | $4n+1$ |  prop. 2.3
Gidney plain adder [Gid18] | $n$ | $n$ | $6n-1$ |  prop. 2.4
| $\mathsf{QFT}_{n+1}$ | Ancillas |  | Ref.
Draper [Dra00] | $3$ | $0$ | $-$ |  prop. 2.5
Table 2: Gate count and logical qubits count for plain adders.

#### VBE implementation

One of the first implementations of a quantum adder had been proposed by
Vedral, Barenko and Ekert (VBE) in [VBE96]. Such a circuit is built out of the
auxiliary unitary gates $\mathsf{CARRY}$ and $\mathsf{SUM}$ (see figure 4)
computing the carry and the sum on a single bit.

Figure 4: CARRY and SUM gate decomposition for the VBE adder [VBE96]. The
CARRY gate performs the mapping
$\ket{c_{k},x_{k},y_{k},c_{k+1}}\mapsto\ket{c_{k},x_{k},y_{k}\oplus
x_{k},c_{k+1}\oplus\textrm{maj}(x_{k},y_{k},c_{k})}$ where maj is defined in
equation (5) of section 1.3. The SUM gate performs the mapping
$\ket{c_{k},x_{k},y_{k}}\mapsto\ket{c_{k},x_{k},y_{k}\oplus c_{k}\oplus
x_{k}}$

The VBE implementation is subsumed by the following proposition.

######  Proposition 2.2 (VBE plain adder [VBE96]).

There is a circuit implementing an $n$-bit quantum addition as per definition
2.1 using $n$ ancilla qubits and $4n$ $\mathsf{Tof}$ gates.

###### Proof.

The sought circuit is given by figure 5 together with the definition of the
gates $\mathsf{CARRY}$ and $\mathsf{SUM}$ in figure 4.

Figure 5: Adder circuit based on Vedral et al. [VBE96]

  1. 1.

The circuit is initiated in the state

$\displaystyle\ket{c}_{n}\ket{x}_{n}\ket{y}_{n+1}=\ket{c_{0},x_{0},y_{0},\dots
c_{i},x_{i},y_{i},c_{i+1},\dots c_{n-1},x_{n-1},y_{n-1},y_{n}}$

where $c_{i}=0$ for any $0\leq i\leq n$.

  2. 2.

The first part of the circuit consists of a chain of $n$ carry gates. The
$i$-th gate computes the carry $c_{i+1}$ through the recursive equation (5)
storing its value in register $C_{i+1}$. At last, it computes the most
significant bit of the result $x+y$, expressed by the carry $c_{n}=y_{n}$,
storing it in the qubit $Y_{n}$, added to take into account the possible
overflow. More precisely, the state after the chain of the $n$ different CARRY
gates is:

$\displaystyle C_{0}$ $\displaystyle\leftarrow 0,$ $\displaystyle\vdots$
$\displaystyle C_{i}$
$\displaystyle\leftarrow\textrm{maj}(x_{i-1},y_{i-1},c_{i-1})$ $\displaystyle
X_{i}$ $\displaystyle\leftarrow x_{i}$ $\displaystyle Y_{i}$
$\displaystyle\leftarrow x_{i}\oplus y_{i}$ $\displaystyle\vdots$
$\displaystyle Y_{n}$ $\displaystyle\leftarrow
y_{n}\oplus\textrm{maj}(x_{n-1},y_{n-1},c_{n-1})~{}.$

  3. 3.

The central $\mathsf{CNOT}$ computes the second most significant bit of the
sum, namely

$\displaystyle Y_{n-1}$ $\displaystyle\leftarrow s_{n-1}=x_{n-1}\oplus
y_{n-1}\oplus c_{n-1}~{}.$

  4. 4.

The last part of the circuit consists of a chain of $n-1$
$\mathsf{CARRY}^{\dagger}$ and $n$ $\mathsf{SUM}$ gates. Inverses of the
$\mathsf{CARRY}$ gate appear to restore every qubit of the temporary register
$C$ to its initial state $|0\rangle$. In particular, $C_{i}\leftarrow 0$ only
after $B_{i}\leftarrow a_{i}\oplus b_{i}\oplus c_{i}$.

∎

#### CDKPM implementation

A subsequent advancement over the VBE implementation was proposed by Cuccaro,
Draper, Kutin, and Petrie Moulton (CDKPM) in [Cuc+04]. Their strategy greatly
improves the use of ancillary qubits, requiring only one ancilla in contrast
to the linearly many qubits required by the VBE adder. Moreover, this circuit
enjoys a smaller depth, uses fewer gates and requires less space. The CDKPM
implementation is based on the two auxiliary gates $\mathsf{MAJ}$ (majority)
and $\mathsf{UMA}$(unmajority and add). The $\mathsf{MAJ}$ gate is given in
figure 6; it computes the majority function of three bits in place (See
equation (5) in section 1.3), while the $\mathsf{UMA}$, given in figure 7
gate, restores the original values and writes the sum to the output as shown
in figure 9.

Figure 6: Majority gate ($\mathsf{MAJ}$) as described in Cuccaro et al.
[Cuc+04] The $\mathsf{MAJ}$ gate performs the mapping
$\ket{c_{k},y_{k},x_{k}}\mapsto\ket{c_{k}\oplus x_{k},y_{k}\oplus
x_{k},\textrm{maj}(x_{k},y_{k},c_{k})}$ where the function maj is defined in
equation (5).  Figure 7:  Unmajority gate (2 $\mathsf{CNOT}$ version and 3
$\mathsf{CNOT}$ version) as described in Cuccaro et al. [Cuc+04]. The
$\mathsf{UMA}$ gate performs the mapping
$\ket{x_{i},y_{i},c_{i}}\mapsto\ket{a_{i}\oplus c_{i}\oplus
x_{i}y_{i},x_{i}\oplus y_{i}\oplus c_{i}\oplus x_{i}y_{i},c_{i}\oplus
x_{i}y_{i}}$. The operator is not self-adjoint, $(\mathsf{UMA})^{\dagger}$
performs the mapping $\ket{c_{k},y_{k},x_{k}}\mapsto\ket{c_{k}\oplus
x_{k},c_{k}\oplus y_{k},\textrm{maj}(x_{k},y_{k}\oplus 1,c_{k})}$.  Figure 8:
CDKPM ripple-carry adder of [Cuc+04]. The corresponding significant bits of
$a=a_{0}a_{1}\cdots a_{n-1}$ and $b=b_{0}b_{1}\cdots b_{n-1}$ are intertwined
with each other. The register $b$ is extended by a single qubit to account for
the last carry bit in the addition Figure 9: The combination of MAJ (majority)
and UMA (unmajority) gates. Observe that $[(c_{i}\oplus x_{i})(y_{i}\oplus
x_{i})]=x_{i}\oplus\textrm{maj}(x_{i},y_{i},c_{i})$ where the majority
function maj is given in equation (5) of section 1.3.

######  Proposition 2.3 (CDKPM plain adder [Cuc+04]).

There is a circuit implementing an $n$-bit quantum addition as per definition
2.1 using $1$ ancilla qubit and $2n$ $\mathsf{Tof}$ gates.

###### Proof.

The sought circuit is given in figure 8. The first qubit $C_{0}$ is an ancilla
prepared in the state $c_{0}=0$, and the last qubit $Y_{n}$ is the extra qubit
meant to take into account the possible sum overflow. The circuit consists of
a sequence of $n$ $\mathsf{MAJ}$ gates, a central $\mathsf{CNOT}$ copying the
most significant carry in the register $Y_{n}$ and a final sequence of
$\mathsf{UMA}$ gates. The combination of $\mathsf{MAJ}$ and $\mathsf{UMA}$
gates is shown in figure 9. ∎

#### Gidney implementation

A variant of the CDKPM adder was proposed by Gidney [Gid18] (shown in figure
13). The implementation involves replacing $\mathsf{Tof}$ gates in the
$\mathsf{MAJ}$ blocks by a temporary logical-$\mathsf{AND}$ stored in an
ancilla qubit. This increases the number of ancillas by $n$: one for each of
the $n$ $\mathsf{MAJ}$ blocks. In the $\mathsf{UMA}$ blocks, the uncomputation
of the $\mathsf{Tof}$ gate is performed by a measurement and classically
controlled $\mathsf{C}$-$\mathsf{Z}$ gate (using MBU). We show a block of
Gidney’s original contruction below.

Figure 10:  The temporary logical-$\mathsf{AND}$ construction of Gidney
[Gid18]. Here, the decomposition is using $\mathsf{T}$ gates, however, we
consider just consider each temporary logical-$\mathsf{AND}$ gate implemented
using a $\mathsf{Tof}$ gate in our paper.  Figure 11:  Uncomputation of the
temp logical-$\mathsf{AND}$ by Gidney [Gid18]. Here the circuit uses no
$\mathsf{T}$ gates. It instead includes an $\mathsf{H}$ gate, a computation
basis measurement and a classically controlled $\mathsf{C\text{-}Z}$ gate.
Figure 12: Adder block in Gidney’s adder [Gid18] Figure 13: Gidney’s
logical-$\mathsf{AND}$ adder. The qubit $C_{0}$ starts in the state $\ket{0}$
and doesn’t change value throughout the computation, therefore it can be
omitted to reduce the ancilla count by $1$ [Gid18].

######  Proposition 2.4 (Gidney adder [Gid18]).

There is a circuit implementing an $n$-bit quantum adder as per definition 2.1
using $n$ ancilla qubits and $n$ $\mathsf{Tof}$ gates.

###### Proof.

An adder block in the temp logical-$\mathsf{AND}$ adder is constructed as
shown in figure 12. The full circuit is shown in figure 13, it uses $n$
$\mathsf{MAJ}$ blocks, $(n-1)$ $\mathsf{UMA}$ blocks, and $2$ additional
$\mathsf{CNOT}$s. We require $1$ less $\mathsf{UMA}$ block with respect to the
CDKPM implementation because the final $\mathsf{MAJ}$ block computes the most
significant carry bit $c_{n}$ which also happens to the be most significant
bit of the addition $s_{n}=(x+y)_{n}$. We only use the two additional
$\mathsf{CNOT}$’s for restoring the values of $x_{n-1}$ and computing the
second most significant bit of the sum i.e. $s_{n-1}=(x+y)_{n-1}$. ∎

#### Draper implementation

While the implementations described in the previous sections use essentially
classical algorithms for addition and convert them to reversible quantum
circuits, Draper [Dra00] came up with a quantum-specific way of addition using
$\mathsf{QFT}$ gates.

Figure 14: Draper’s plain adder [Dra00]. It performs the operation
$\ket{x}_{n}\ket{\phi(y)}_{n+1}\xmapsto{\mathsf{\Phi_{ADD}}}\ket{x}_{n}\ket{\phi(x+y)}_{n+1}$.
See figure 3 for the definition of the gates in the figure. Initially,
$y_{n}=\ket{0}$ to account for the overflow of the addition

######  Proposition 2.5 (Draper’s plain adder [Dra00]).

Let $x\in\\{0,1\\}^{n},y\in\\{0,1\\}^{n}$ be two bit strings stored in
register $X$ and $Y$ of size $n$ and $n+1$ respectively (the most significant
bit of register $Y$ is set to 0). Also, let
$\ket{\phi(y)}_{n+1}:=\mathsf{QFT}_{n+1}\ket{y}_{n+1}$. There is a circuit
$\mathsf{\Phi_{ADD}}$ performing the operation

$\ket{x}_{n}\ket{\phi(y)}_{n+1}\xmapsto{\mathsf{\Phi_{ADD}}}\ket{x}_{n}\ket{\phi(x+y)}_{n+1}$

using zero ancilla qubits, and
$\mathsf{count}(\mathsf{\Phi_{ADD}})=\\{(\mathsf{C\text{-}R}(\theta_{1}),n)\\}\cup\\{(\mathsf{C\text{-}R}(\theta_{i}),n+2-i)\mid
i\in[2,n+1]\\}~{}.$

###### Proof.

We denote as $\phi_{i}(y)$ the $i$-th qubit of $\phi(y)$. For $\phi_{i}(y)$,
the following operations are performed in Draper’s circuit (see figure 14).
Consider
$\widetilde{U}_{i}=\mathsf{C}_{X_{0}}\text{-}\mathsf{R}_{Y_{i}}(\theta_{1})\mathsf{C}_{X_{1}}\text{-}\mathsf{R}_{Y_{i}}(\theta_{2})\cdots\mathsf{C}_{X_{0}}\text{-}\mathsf{R}_{Y_{i}}(\theta_{i+1})$,
the unitary acting on $\ket{\phi_{i}(y)}_{1}$. The transformation on
$\ket{\phi_{i}(y)}_{1}$ is as follows:

$\displaystyle\ket{x}_{n}\ket{\phi_{i}(y)}_{1}$
$\displaystyle\xmapsto{\widetilde{U}_{i}}\mathsf{C}_{X_{0}}\text{-}\mathsf{R}_{Y_{i}}(\theta_{1})\mathsf{C}_{X_{1}}\text{-}\mathsf{R}_{Y_{i}}(\theta_{2})\cdots\mathsf{C}_{X_{0}}\text{-}\mathsf{R}_{Y_{i}}(\theta_{i+1})\ket{x}_{n}\left[\ket{0}+\exp\left(\frac{2\pi\mathrm{i}y}{2^{i+1}}\right)\ket{1}\right]$
$\displaystyle=\ket{x}_{n}\left[\ket{0}+\left(\prod_{j=0}^{i}\exp\left(\frac{2\pi\mathrm{i}x_{j}}{2^{i-j+1}}\right)\right)\exp\left(\frac{2\pi\mathrm{i}y}{2^{i+1}}\right)\ket{1}\right]$
$\displaystyle=\ket{x}_{n}\left[\ket{0}+\exp\left(2\pi\mathrm{i}\sum_{j=0}^{i}\frac{x_{j}}{2^{i-j+1}}\right)\exp\left(\frac{2\pi\mathrm{i}y}{2^{i+1}}\right)\ket{1}\right]$
$\displaystyle=\ket{x}_{n}\left[\ket{0}+\exp\left(\frac{2\pi\mathrm{i}}{2^{i+1}}\sum_{j=0}^{i}2^{j}x_{j}\right)\exp\left(\frac{2\pi\mathrm{i}y}{2^{i+1}}\right)\ket{1}\right]$
$\displaystyle=\ket{x}_{n}\left[\ket{0}+\exp\left(\frac{2\pi\mathrm{i}}{2^{i+1}}\sum_{j=0}^{n-1}2^{j}x_{j}\right)\exp\left(\frac{2\pi\mathrm{i}y}{2^{i+1}}\right)\ket{1}\right]$
$\displaystyle=\ket{x}_{n}\left[\ket{0}+\exp\left(\frac{2\pi\mathrm{i}x}{2^{i+1}}\right)\exp\left(\frac{2\pi\mathrm{i}y}{2^{i+1}}\right)\ket{1}\right]$
$\displaystyle=\ket{x}_{n}\left[\ket{0}+\exp\left(\frac{2\pi\mathrm{i}(x+y)}{2^{i+1}}\right)\ket{1}\right]$
$\displaystyle=\ket{x}_{n}\ket{\phi_{i}(x+y)}_{1}~{}.$

We see that the $i^{th}$ qubit of the target register $\ket{\phi(y)}_{n+1}$,
that is $\ket{\phi_{i}(y)}_{1}$, now holds the $i^{th}$ qubit of the Fourier
transformed sum i.e. $\ket{\phi_{i}(x+y)}_{1}$. Hence, generalising the above
result on the entire state of the target register, we conclude that the Draper
adder performs the operation

$\ket{x}_{n}\ket{\phi(y)}_{n+1}=\ket{x}_{n}\bigotimes_{j=0}^{n}\ket{\phi_{j}(y)}_{1}\mapsto\ket{x}_{n}\bigotimes_{j=0}^{n}\ket{\phi_{j}(x+y)}_{1}=\ket{x}_{n}\ket{\phi(x+y)}_{n+1}~{}.$

The $\mathsf{\Phi_{ADD}}$ circuit on $n$ qubits has the same structure as a
$\mathsf{QFT}$ circuit, excluding a $\mathsf{C\text{-}R}(\theta_{1})$ gate and
all the $\mathsf{H}$ gates. Therefore, the gate count of the
$\mathsf{\Phi_{ADD}}$ circuit is:

$~{}\mathsf{count}(\mathsf{\Phi_{ADD}})=\\{(\mathsf{C\text{-}R}(\theta_{1}),n)\\}\cup\\{(\mathsf{C\text{-}R}(\theta_{i}),n+2-i)\mid
i\in[2,n+1]\\}~{}.$

∎

######  Remark 2.6.

Resource-wise, $\mathsf{\Phi_{ADD}}$ is bounded above by the cost of a
$\mathsf{QFT}_{n+1}$ gate.

In Draper’s original circuit, he considers the register
$\ket{\phi(y)}_{n+1}=\mathsf{QFT}_{n+1}\ket{y}$ to be prepared beforehand, and
the final output to be in the state
$\ket{\phi(x+y)}_{n+1}=\mathsf{QFT}_{n+1}\ket{x+y}_{n+1}$ after the addition.
However, to stay consistent with definition 2.1, we must take into account the
cost of the $\mathsf{QFT}_{n+1}$ to prepare $\ket{\phi(y)}_{n+1}$, and the
cost of the $\mathsf{QFT}_{n+1}$ to return back to the computation basis at
the end of the addition. Hence, we derive the following corollary.

######  Corollary 2.7 (Draper’s QFT-adder).

Let $x\in\\{0,1\\}^{n},y\in\\{0,1\\}^{n}$ be two bit strings stored in
register $X$ and $Y$ of size $n$ and $n+1$ respectively (the most significant
bit of register $Y$ is set to 0). There is a circuit implementing a quantum
adder as per definition 2.1 using $n$ ancilla qubits. The circuit gate cost is
bounded above by the cost of $3\mathsf{QFT}_{n+1}$ circuits.

###  2.1 Controlled addition

######  Definition 2.8 (Controlled addition).

We define a _controlled quantum adder_ as any unitary gate implementing the
$n$ strings addition controlled on a qubit $\ket{c}$ according to the
following circuit

Procedure | Tof Count | Ancillas | CNOT | Ref.
---|---|---|---|---
CDKPM | $3n$ | $1$ | $4n+1$ |  thm. 2.12
Gidney | $2n$ | $n+1$ | $7n-1$ |  prop. 2.11
| Tof Count | Ancillas | $\mathsf{QFT}_{n+1}$ | Ref.
Draper | $n$ | $1$ | $3$ |  thm. 2.14
Table 3: Controlled addition by a constant

The theorem below gives a general recipe to perform a controlled addition
given any adder.

######  Theorem 2.9 (Controlled adder - with $n$ extra ancillas and $2n$ extra
$\mathsf{Tof}$ gate).

Let $\mathsf{Q_{ADD}}$ be a quantum circuit that performs an $n$-bit quantum
addition as per definition 2.1 using $s$ ancillas, and $r$ $\mathsf{Tof}$
gates. Then, there is a circuit implementing a controlled quantum adder as per
definition 2.8 using $n+s$ ancilla qubits and $r+2n$ $\mathsf{Tof}$ gates.

###### Proof.

We first initialize a circuit in the state

$\displaystyle\ket{c}_{1}\ket{x}_{n}\ket{y}_{n}\ket{0}_{s+n+1}$
$\displaystyle~{}.$ Now, we use a sequence of $n$ $\mathsf{Tof}$ gates to load
a controlled version of the addend $x$ i.e.
$\displaystyle\ket{c}_{1}\ket{x}_{n}\ket{y}_{n}\ket{0}_{s+n+1}$
$\displaystyle\xmapsto{\mathsf{Load}}\ket{c}_{1}\ket{x}_{n}\ket{y}_{n}\ket{c\cdot
x}_{n}\ket{0}_{s+1}.$ We can now perform the required addition using $c\cdot
x$ as our addend $\displaystyle\ket{c}_{1}\ket{x}_{n}\ket{y}_{n}\ket{c\cdot
x}_{n}\ket{s+1}$
$\displaystyle\xmapsto{\mathsf{Q_{ADD}}}\ket{c}_{1}\ket{x}_{n}\ket{y+c\cdot
x}_{n+1}\ket{c\cdot x}_{n}\ket{0}_{s}~{}.$ We finally unload $c\cdot x$ using
$n$ $\mathsf{Tof}$ gates $\displaystyle\ket{c}_{1}\ket{x}_{n}\ket{y+c\cdot
x}_{n+1}\ket{c\cdot x}_{n}\ket{0}_{s+1}$
$\displaystyle\xmapsto{\mathsf{Unload}}\ket{c}_{1}\ket{x}_{n}\ket{y+c\cdot
x}_{n}\ket{0}_{n+s}~{}.$

∎

The loading of $c\cdot x$ is performed in a register initially in the
$\ket{0}_{n}$ state. This can be executed with just a temporary
logical-$\mathsf{AND}$, and therefore can be uncomputed using measurements as
in the case of the Gidney plain adder (proposition 2.4). This leads to the
following corollary.

######  Corollary 2.10 (Controlled adder - $n$ extra ancillas and $n$ extra
$\mathsf{Tof}$ gates).

Let $\mathsf{Q_{ADD}}$ be a quantum circuit that performs an $n$-bit quantum
addition as per definition 2.1 using $s$ ancillas, and $r$ $\mathsf{Tof}$
gates. Then, there is a circuit implementing a controlled quantum adder as per
definition 2.8 using $n+s$ ancilla qubits and $r+n$ $\mathsf{Tof}$ gates.

Although theorem 2.9 and corollary 2.10 can be used with any general adder,
Gindey [Gid18] adapted his temporary logical-$\mathsf{AND}$ construction to
give an adder that uses only an additional $n$ $\mathsf{Tof}$ gates, and a
single extra ancilla. We present his construction below.

######  Proposition 2.11 (Controlled adder - Gidney - with 1 extra ancilla
[Gid18]).

There is a circuit implementing an $n$-bit controlled quantum addition as per
definition 2.8 using $n+1$ ancilla qubits and $2n$ $\mathsf{Tof}$ gates.

###### Proof.

Figure 15 is taken from Gidney’s construction of a controlled adder building
block. Here, we can isolate what happens in the case of a single
$\mathsf{MAJ}-\mathsf{UMA}$ pair, and show what is the resultant state. Apart
from the $\mathsf{Tof}$ gates of the $n$ $\mathsf{MAJ}$ blocks, we also
require a $\mathsf{Tof}$ gate per $\mathsf{UMA}$ block to perform the
controlled addition, leading to $2n$ $\mathsf{Tof}$ gates in total to execute
a controlled adder in this case. ∎

Figure 15: The controlled adder building block by Gidney [Gid18]

We now show a version of the CDKPM adder that can perform controlled addition
with a single ancilla qubit.

######  Theorem 2.12 (Controlled adder - CDKPM - with $1$ ancilla).

There is a circuit implementing an $n$-bit controlled quantum addition as per
definition 2.8 using $1$ ancilla qubit and $3n$ $\mathsf{Tof}$ gates.

###### Proof.

Controlled addition can be achieved by slightly modifying the CDKPM circuit
(see figure 8) substituting the UMA gates with their controlled version given
by figure 16.

Figure 16:  Controlled Unmajority gate.

Overall, the consecutive application of $\mathsf{MAJ}$ and
$\mathsf{C\text{-}UMA}$ gates acts as figure 17, thus determining the sought
implementation of a controlled addition.

Figure 17: The combination of MAJ (majority) and $c-\textrm{UMA}$ (controlled
unmajority) gates.

∎

While the Draper adder (as defined in corollary 2.7 employing three
$\mathsf{QFT}$’s) fits into the general framework of corollary 2.10, an
alternate construction can be derived using only a single ancilla. The
symmetries in the circuit can be exploited to avoid controls on every gate in
the controlled Draper. Only the central $\mathsf{\Phi_{ADD}}$ gate would need
to be controlled, while the the quantum Fourier transforms at the beginning
and the end of the circuit remain uncontrolled.

######  Theorem 2.13 (Controlled adder - Draper).

Let $x\in\\{0,1\\}^{n},y\in\\{0,1\\}^{n}$ be two bit strings, and
$c\in\\{0,1\\}$ be a control. Also, let $\mathsf{Q_{QFT\text{-}ADD}}$ be the
Draper adder circuit described in corollary 2.7, performing the operation

$\ket{x}_{n}\ket{y}_{n}\xmapsto{\mathsf{Q_{QFT\text{-}ADD}}}\ket{x}_{n}\ket{x+y}_{n+1}.$

We can perform a controlled Draper adder $\mathsf{C\text{-}QFT_{ADD}}$ using a
$\mathsf{QFT}_{n+1}$, a single controlled $\mathsf{\mathsf{\Phi_{ADD}}}$
(performing
$\ket{c}_{1}\ket{x}_{n}\ket{\phi(y)}_{n+1}\xmapsto{\mathsf{C\text{-}\Phi_{ADD}}}\ket{c}_{1}\ket{x}_{n}\ket{\phi(y+c\cdot
x)}_{n+1}$), and an $\mathsf{IQFT}_{n+1}$

###### Proof.

Start with a quantum Fourier transform

$\displaystyle\ket{0}_{s+1}\ket{c}_{1}\ket{x}_{n}\ket{y}_{n}$
$\displaystyle\xmapsto{\mathsf{QFT}_{n+1}}\ket{0}_{s}\ket{c}_{1}\ket{x}_{n}\ket{\phi(y)}_{n+1}~{}.$
Then, one performs a $\mathsf{C\text{-}\Phi_{ADD}}$
$\displaystyle\ket{0}_{s}\ket{c}_{1}\ket{x}_{n}\ket{\phi(y)}_{n+1}$
$\displaystyle\xmapsto{\mathsf{C\text{-}\Phi_{ADD}}}\ket{0}_{s}\ket{c}_{1}\ket{x}_{n}\ket{\phi(c\cdot
x+y)}_{n+1}~{},$ followed by a $\mathsf{IQFT}_{n+1}$ gate to return the
required state back to the computation basis
$\displaystyle\ket{0}_{s}\ket{c}_{1}\ket{x}_{n}\ket{\phi(c\cdot x+y)}_{n+1}$
$\displaystyle\xmapsto{\mathsf{IQFT}_{n+1}}\ket{0}_{s}\ket{c}_{1}\ket{x}_{n}\ket{c\cdot
x+y}_{n+1}~{}.$

∎

Below, we show a way to execute the $\mathsf{C\text{-}\Phi_{ADD}}$ (as
introduced in theorem 2.13) using a single ancilla and $n$ extra
$\mathsf{Tof}$ gates.

######  Theorem 2.14 (Controlled adder - Draper - with 1 ancilla).

Let $x\in\\{0,1\\}^{n},y\in\\{0,1\\}^{n}$ be two bit strings, and
$c\in\\{0,1\\}$ be a control. Also, let

$\mathsf{Q_{QFT\text{-}ADD}}=(\mathbf{I_{n}}\otimes\mathsf{IQFT_{n+1}})\mathsf{\Phi_{ADD}}(\mathbf{I_{n}}\otimes\mathsf{QFT_{n+1}})$

be the circuit described in corollary 2.7 (Draper’s adder), performing a
quantum addition as per definition 2.1. We can perform a controlled Draper
adder $\mathsf{C\text{-}Q_{QFT\text{-}ADD}}$ using a circuit of cost bounded
by $2\mathsf{QFT}_{n+1}$, and a $\mathsf{C\text{-}\Phi_{ADD}}$ gate. The
circuit requires only a single ancilla.

###### Proof.

Following up from the above theorem 2.13, we find a construction for
$\mathsf{C\text{-}\Phi_{ADD}}$, requiring only a single ancilla. We first
notice that all gates in $\mathsf{\Phi_{ADD}}$ commute. Therefore, the order
in which they are performed is irrelevant. Secondly, the main difference
between $\mathsf{\Phi_{ADD}}$ and $\mathsf{C\text{-}\Phi_{ADD}}$ is that any
controlled rotation $\mathsf{C\text{-}R}(\theta_{i})$ (for any $i\in[n]$), now
becomes a double controlled rotation $\mathsf{CC\text{-}R}(\theta_{i})$ gate:

$\displaystyle\ket{c_{1}}_{1}\ket{c_{2}}_{1}\ket{t}_{1}\xmapsto{\mathsf{CC\text{-}R}(\theta_{i})}\exp(2\pi\mathrm{i}(c_{1}\cdot
c_{2}\cdot t)/2^{i})\ket{c_{1}}_{1}\ket{c_{2}}_{1}\ket{t}_{1}$

We can decompose any $\mathsf{CC\text{-}R}$ gate it into a temporary
logical-$\mathsf{AND}$, a single controlled rotation, followed by an
uncomputation of the logical-$\mathsf{AND}$:

$\displaystyle\left[\begin{aligned}
&\ket{c_{1}}_{1}\ket{c_{2}}_{1}\ket{0}_{1}\ket{t}_{1}\\\
&\xmapsto{\mathsf{Tof}}\ket{c_{1}}_{1}\ket{c_{2}}_{1}\ket{c_{1}\cdot
c_{2}}_{1}\ket{t}_{1}\\\
&\xmapsto{\mathsf{C\text{-}R}(\theta_{i})}\exp(2\pi\mathrm{i}(c_{1}\cdot
c_{2}\cdot t)/2^{i})\ket{c_{1}}_{1}\ket{c_{2}}_{1}\ket{c_{1}\cdot
c_{2}}_{1}\ket{t}_{1}\\\ &\xmapsto{\mathsf{Uncompute\
Tof}}\exp(2\pi\mathrm{i}(c_{1}\cdot c_{2}\cdot
t)/2^{i})\ket{c_{1}}_{1}\ket{c_{2}}_{1}\ket{0}_{1}\ket{t}_{1}\end{aligned}\right]$

Using the above decomposition, we can convert every $\mathsf{CC\text{-}R}$
into a temporary logical-$\mathsf{AND}$ \+ $\mathsf{C\text{-}R}$ (and finally
an uncomputation of the temporary logical-$\mathsf{AND}$).

$\displaystyle\ket{0}_{1}\ket{c}_{1}\ket{x}_{n}\ket{\phi(y)}_{n+1}$
$\displaystyle\xmapsto{\mathsf{Tof}}\ket{c\cdot
x_{i}}_{1}\ket{c}_{1}\ket{x}_{n}\ket{\phi(y)}_{n+1}~{}.$

We can now perform the required rotation gates that initially had $x_{i}$ as
the control, by using $c\cdot x_{i}$ as our control instead. Compared to
$\mathsf{\Phi_{ADD}}$, we require an extra $n(n+3)/2$ $\mathsf{Tof}$ for the
temp logical-$\mathsf{AND}$’s, $n(n+3)/2$ $\mathsf{H}$ gates and
$n(n+3)/4\text{ }\mathsf{C\text{-}R}(\theta_{1})$ gates in expectation (cost
of uncomputation of logical $\mathsf{AND}$s) in total for
$\mathsf{C\text{-}\Phi_{ADD}}$. We only require a single ancilla as the
ancilla is reset after every gate. The $\mathsf{Tof}$ cost can be made cheaper
by noticing that we can rearrange the order of the controlled rotation gates
in $\mathsf{C\text{-}\Phi_{ADD}}$ and group all gates that have a common
control $x_{i}$. This construction requires only an additional $n$
$\mathsf{Tof}$ gates (cost of logical $\mathsf{AND}$s), $n$ $\mathsf{H}$ gates
and $n/2\text{ }\mathsf{C\text{-}R}(\theta_{1})$ gates in expectation (cost of
uncomputation of the logical $\mathsf{AND}$s). ∎

###  2.2 Addition by a constant

######  Definition 2.15 (Addition by a constant).

We define a _quantum adder by a constant_ as any unitary gate implementing the
$n$ strings addition by a classically known constant $a\in\\{0,1\\}^{n}$
according to the following circuit

Such a gate can be obtained from any given quantum adder implementation
$\mathsf{Q_{ADD}}$ in several ways. In this section, we present a way to
perform addition by a constant using any circuit as per definition 2.1. We
also dive into more specific implementations.

Procedure | Tof Count | Ancillas | CNOT | Ref.
---|---|---|---|---
CDKPM | $2n$ | $n+1$ | $4n+1$ |  prop. 2.16
Gidney | $n$ | $2n$ | $6n-1$ |  prop. 2.16
| $\mathsf{QFT}_{n+1}$ | Ancillas | $\mathsf{\Phi_{ADD}}(a)$ | Ref.
Draper | $2$ | $0$ | $1$ |  prop. 2.17
Table 4: Additon by a constant

######  Proposition 2.16 (Adder by a constant [Cuc+04]).

Let $\mathsf{Q_{ADD}}$ be a quantum circuit that performs an $n$-bit quantum
addition as per definition 2.1 using $s$ ancillas, and $r$ $\mathsf{Tof}$
gates. Then, there is a circuit implementing

$\ket{0}_{1}\ket{x}_{n}\mapsto\ket{x+a}_{n+1}$

as per definition 2.1 using $n+s$ ancilla qubits and $r$ $\mathsf{Tof}$ gates

###### Proof.

This circuit can be obtained first by performing the mapping

$\ket{0}_{s+n+1}\ket{x}_{n}\xmapsto{\mathsf{Load}}\ket{a}_{n}\ket{0}_{s+1}\ket{x}_{n},$

using $|a|$ NOT gates (one on each qubits $i$ such that $a_{i}\neq 0$) and
treating the first $n+1$ qubits input as an ancillary channel. Then, we use
the adder circuit $\mathsf{Q_{ADD}}$, to perform the required addition

$\ket{a}_{n}\ket{0}_{s+1}\ket{x}_{n}\xmapsto{\mathsf{Q_{ADD}}}\ket{a}_{n}\ket{0}_{s}\ket{x+a}_{n+1}~{}.$

Finally, we uncompute the ancilla register storing $a$ by applying the
previous sequence of not gates again.

$\ket{a}_{n}\ket{0}_{s}\ket{x+a}_{n+1}\xmapsto{\mathsf{Unload}}\ket{0}_{s+n}\ket{x+a}_{n+1}~{}.$

The corresponding circuit is depicted in figure 18, keeping implicit the $s$
ancillary qubits required by $\mathsf{Q_{ADD}}$.

Figure 18: Addition by a constant value $a$. The unitary gate
$\mathsf{LOAD(a)}$ is a self-adjoint implementation of the mapping which load
and unload the value $a$.

∎

While proposition 2.16 is applicable to any adder that can perform the mapping
$\mathsf{Q_{ADD}}\ket{x}_{n}\ket{y}_{n}\mapsto\ket{x}_{n}\ket{x+y}_{n+1}$, in
the case of Draper’s $\mathsf{QFT}$ adder, there is a method to add constants
without requiring ancillas. This method was used by Beauregard [Bea02].

######  Proposition 2.17 (Adder by a constant - Draper [Bea02]).

There is a circuit implementing an $n$-bit addition by a constant as per
definition 2.15 using $0$ ancillas.

###### Proof.

Figure 19: $\mathsf{QFT}$-based addition by a constant [Bea02]

The complete proof directly follows from corollary 2.7. figure 19 details the
unitary gates that are required to perform the $\mathsf{QFT}$-based addition
by a constant, where $\mathsf{U}_{a,i}$ is given by

$\displaystyle\mathsf{U}_{a,i}$
$\displaystyle=\prod_{k=0}^{i}\mathsf{R}\left(a_{i}\theta_{i-k+1}\right)=\mathsf{R}\left(\sum_{k=0}^{i}a_{k}\theta_{i-k+1}\right)=\mathsf{R}\left(\frac{1}{2^{i+1}}\sum_{k=0}^{i}2^{k}a_{k}\right)~{}.$
(7)

We denote the $n$ qubit gate $\otimes_{i=0}^{n-1}\mathsf{U}_{a,i}$ as
$\mathsf{\Phi_{ADD}}(a)$ (because our rotation gates are determined by the
value of the bits of $a$). ∎

###  2.3 Controlled addition by a constant

######  Definition 2.18 (Controlled addition by a constant).

We define a _controlled quantum adder_ as any unitary gate implementing the
$n$ strings addition, by a classically known constant $a\in\\{0,1\\}^{n}$ and
controlled on a qubit $\ket{c}$, according to the following circuit

Procedure | Tof Count | Ancillas | CNOT | Ref.
---|---|---|---|---
CDKPM | $2n$ | $n+1$ | $4n+1+2|a|$ |  prop. 2.19
Gidney | $n$ | $2n$ | $6n-1+2|a|$ |  prop. 2.19
| $\mathsf{QFT}_{n+1}$ | Ancillas | $\mathsf{C\text{-}\Phi_{ADD}}(a)$ | Ref.
Draper | $2$ | $0$ | $1$ |  prop. 2.20
Table 5: Controlled addition by a constant ’$a$’

We now present a known construction that works with any adder to perform a
controlled addition by a constant as per definition 2.18

######  Proposition 2.19 (Controlled adder by a constant [VBE96]).

Let $\mathsf{Q_{ADD}}$ be a quantum circuit that performs an $n$-bit quantum
addition as per definition 2.1 using $s$ ancillas, and $r$ $\mathsf{Tof}$
gates. There is a circuit performing an $n$-bit controlled addition by a
constant as per definition 2.18, using $n+s$ ancillas, $r$ $\mathsf{Tof}$
gates and an additional $2|a|$ CNOTs.

###### Proof.

This circuit can be obtained first by performing the mapping

$\ket{c}_{1}\ket{0}_{n+s+1}\ket{x}_{n}\xmapsto{\mathsf{Load}}\ket{c}_{1}\ket{ca}_{n}\ket{0}_{s+1}\ket{x}_{n},$

using $|a|$ CNOT gates. Then, we use the adder circuit, leaving the registers
in the state

$\ket{c}_{1}\ket{ca}_{n}\ket{0}_{s+1}\ket{x}_{n}\xmapsto{\mathsf{Q_{ADD}}}\ket{c}_{1}\ket{ca}_{n}\ket{0}_{s}\ket{x+ca}_{n+1}~{}.$

Finally, one has to uncompute the register storing $a$, applying the previous
sequence of CNOT gates again. The corresponding circuit is depicted in figure
20 keeping implied the $s$ ancillary qubits required by $\mathsf{Q_{ADD}}$.

Figure 20: Controlled addition by a constant value $a$. The controlled unitary
gate $\mathsf{Load(a)}$ is a self-adjoint implementation of the mapping which
loads and unloads the value $c\cdot a$.

∎

Similarly to the previous section, one can adapt Draper’s implementation to
suitably implement the gate of definition 2.18.

######  Proposition 2.20 (Controlled adder by a constant - Draper [Bea02]).

There is a circuit performing an $n$-bit controlled addition by a constant as
per definition 2.18 with zero ancilla qubits.

###### Proof.

We reuse the construction of proposition 2.17 and add controls to every
rotation gate. The cost of this circuit depends on the binary representation
of $a$. We define as $\mathsf{C\text{-}\Phi_{ADD}}(a)$ the gate performing the
operation

$\ket{c}_{1}\ket{\phi(x)}_{n+1}\xmapsto{\mathsf{C\text{-}\Phi_{ADD}}(a)}\ket{c}_{1}\ket{\phi(c\cdot
a+x)}_{n+1}.$

∎

###  2.4 Subtraction

######  Definition 2.21 (Quantum subtraction).

We define a _quantum subtractor_ as any unitary gate implementing the $n$
strings subtraction (see definition 1.5) according to the following circuit

Due to the unitarity of the quantum adder gate and the uniqueness of the
adjoint, it follows that $(\mathsf{ADD})^{\dagger}$ implements a quantum
subtractor. Alternatively, one can implement a quantum subtractor directly
from the definition of bit-string subtractions.

######  Theorem 2.22.

The following two circuits implement a quantum subtractor.

(8)

(9)

###### Proof.

By definition, the gate $\bigoplus$ flips all bits of a given register
$\ket{r}$ namely producing the state $\ket{\overline{r}}$, i.e. the $1$’s
complement of the string $r$ (see definition 1.3). Therefore, the circuit 8
implements bit string subtraction as given by definition 1.5. On the other
hand, the second circuit in theorem 2.22 implements subtraction using the
$2$’s complement of the second addend as given by proposition A.1 in the
appendix. ∎

Interestingly, we recall that the gate performing addition by $1$, i.e. the
“increment by one” operator, enjoys a more specialized implementation [Gid15].

######  Remark 2.23 (Adjoint of Gidney Adder).

While a subtractor can be built using an adjoint of the adder, circuits
involving a measurement (e.g. logical-$\mathsf{AND}$ adder) are generally not
invertible. One way to invert the logical-$\mathsf{AND}$ adder is to swap the
roles of the computation (logical-$\mathsf{AND}$) and uncomputation (MBU
uncomputation of logical-$\mathsf{AND}$) of the logical-$\mathsf{AND}$’s in
the circuit.

###  2.5 Comparison

As expressed by proposition A.3 in appendix A, given a quantum subtractor, one
can easily obtain a string comparator reading the sign (i.e. the most
significant bit) of the difference.

######  Definition 2.24 (Quantum comparison).

We define a _quantum comparator_ as any unitary gate implementing the $n$
strings comparison according to the following circuit

where $\mathbf{1}[\mathsf{x>y}]$ coincides with the most significant bit of
$y-x$, i.e. is $1$ when $x>y$ and $0$ otherwise.

Procedure | Tof Count | Ancillas | CNOT | Ref.
---|---|---|---|---
CDKPM | $2n$ | $1$ | $4n+1$ |  prop. 2.27
Gidney | $n$ | $n$ | $6n+1$ |  prop. 2.28
| $\mathsf{QFT}_{n+1}$ | Ancillas | $-$ | Ref.
Draper | $6$ | $1$ | $-$ |  prop. 2.26
Table 6: Comparators

Due to the close link between the string subtraction and the string comparison
algorithm, it is possible to implement a quantum comparator by adapting the
implementations of quantum adder proposed in the previous section.

######  Proposition 2.25 (Comparator - using an adder and a subtractor
[VBE96]).

Let $\mathsf{Q_{ADD}}$ be a quantum circuit that performs an $n$-bit quantum
addition as per definition 2.1 using $s_{\mathsf{ADD}}$ ancillas, and
$r_{\mathsf{ADD}}$ $\mathsf{Tof}$ gates. Additionally, let $\mathsf{Q_{SUB}}$
be a quantum circuit that performs an $n$-bit quantum subtraction as per
definition 2.21 using $s_{\mathsf{SUB}}$ ancillas, and $r_{\mathsf{SUB}}$
$\mathsf{Tof}$ gates. Then, there is a circuit implementing an $n$-bit quantum
comparator as per definition 2.24 using
$s=1+\max(s_{\mathsf{ADD}},s_{\mathsf{SUB}})$ ancilla qubits and
$r=r_{\mathsf{ADD}}+r_{\mathsf{SUB}}$ $\mathsf{Tof}$ gates as well as an
additional $\mathsf{CNOT}$

###### Proof.

This circuit can be obtained first by performing the mapping

$\ket{0}_{s}\ket{x}_{n}\ket{y}_{n}\ket{t}_{1}\xmapsto{\mathsf{Q_{SUB}}}\ket{0}_{s-1}\ket{x}_{n}\ket{y-x}_{n+1}\ket{t}_{1}$

Here, the value most significant bit of $(y-x)$ i.e. $(y-x)_{n}$ gives us the
required comparator output $(y-x)_{n}=\mathbf{1}[x>y]$. Therefore, applying a
$\mathsf{CNOT}$ on the target register $T$ with the most significant qubit of
$\ket{y-x}$ as the control, we get

$\ket{0}_{s-1}\ket{x}_{n}\ket{y-x}_{n+1}\ket{t}_{1}\xmapsto{\mathsf{CNOT}}\ket{0}_{s-1}\ket{x}_{n}\ket{y-x}_{n+1}\ket{t\oplus\mathbf{1}[x>y]}_{1}~{}.$

We can now apply $\mathsf{Q_{ADD}}$ to return back to the required state

$\ket{0}_{s-1}\ket{x}_{n}\ket{y-x}_{n+1}\ket{t\oplus\mathbf{1}[x>y]}_{1}\xmapsto{\mathsf{Q_{ADD}}}\ket{0}_{s}\ket{x}_{n}\ket{y}_{n}\ket{t\oplus\mathbf{1}[x>y]}_{1}~{}.$

∎

The circuit described below is a component of the $\mathsf{QFT}$ modular
addition circuit described by Beauregard [Bea02], which is based on the Draper
$\mathsf{QFT}$ adder circuit (proposition 2.5).

######  Proposition 2.26 (Comparator - Draper/Beauregard [Bea02]).

Let $x\in\\{0,1\\}^{n},y\in\\{0,1\\}^{n}$ be two bit strings stored in
register $X$ and $Y$ of size $n$ and $n+1$ respectively (the most significant
bit of register $Y$ is set to 0). There is a circuit $\mathsf{Q_{COMP}}$
performing a quantum comparison as per definition 2.24 using $1$
$\mathsf{CNOT}$, $2$ $\mathsf{QFT}_{n+1}$, $2$ $\mathsf{IQFT}_{n+1}$, $1$
$\mathsf{\Phi_{SUB}}$ and $1$ $\mathsf{\Phi_{ADD}}$ gates, and a single
ancilla qubit.

###### Proof.

We can directly apply proposition 2.25 giving a comparator using an adder and
a subtractor. Start preparing the register in the Fourier space.

$\displaystyle\ket{x}_{n}\ket{y}_{n+1}\ket{t}$
$\displaystyle\xmapsto{\mathsf{QFT}_{n+1}}\ket{x}_{n}\ket{\phi(y)}_{n+1}\ket{t}~{}.$
Then, perform a $\mathsf{\Phi_{SUB}}$ on the $Y$ register (subtracting by
$x$), as the significant bit of this subtraction is 1 only when $x>y$.
$\displaystyle\ket{x}_{n}\ket{\phi(y)}_{n+1}\ket{t}$
$\displaystyle\xmapsto{\mathsf{\Phi_{SUB}}}\ket{x}_{n}\ket{\phi(y-x)}_{n+1}\ket{t}~{}.$
We now return back to the computational basis using a $\mathsf{IQFT}_{n+1}$
$\displaystyle\ket{x}_{n}\ket{\phi(y-x)}_{n+1}\ket{t}$
$\displaystyle\xmapsto{\mathsf{IQFT}_{n+1}}\ket{x}_{n}\ket{y-x}_{n+1}\ket{t}~{}.\
$ Controlling on and copying the most significant qubit of the difference i.e.
$(y-x)_{n}$, we compute the required comparison
$\displaystyle\ket{x}_{n}\ket{y-x}_{n+1}\ket{t}$
$\displaystyle\xmapsto{\mathsf{CNOT}}\ket{x}_{n}\ket{y-x}_{n+1}\ket{t\oplus\mathbf{1}[x>y]}_{1}~{}.$
The final set of operations described below, now return the value $y-x$ to its
original state $y$
$\displaystyle\ket{x}_{n}\ket{y-x}_{n+1}\ket{t\oplus\mathbf{1}[x>y]}_{1}$
$\displaystyle\xmapsto{\mathsf{QFT}}\ket{x}_{n}\ket{\phi(y-x)}_{n+1}\ket{t\oplus\mathbf{1}[x>y]}_{1}~{}\xmapsto{}$
$\displaystyle\xmapsto{\mathsf{\Phi_{ADD}}}\ket{x}_{n}\ket{\phi(y)}_{n+1}\ket{t\oplus\mathbf{1}[x>y]}_{1}~{}\xmapsto{}$
$\displaystyle\xmapsto{\mathsf{IQFT}}\ket{0}_{1}\ket{x}_{n}\ket{y}_{n}\ket{t\oplus\mathbf{1}[x>y]}_{1}~{}.$

∎

Although the comparator described in proposition 2.25 works for any adder and
subtractor, based on the type of adder used, there are more specific
constructions requiring fewer gates.

######  Proposition 2.27 (Comparator - CDKPM - using half a subtractor
[Cuc+04]).

There is a circuit implementing an $n$-bit quantum comparator as per
definition 2.24 using $1$ ancilla qubit and $2n$ $\mathsf{Tof}$ gates.

###### Proof.

The sought circuit is given by figure 21. Recall that the adjoint of a unitary
quantum adder performs a subtraction. Notice that the first part of the
circuit is one-half the adjoint of the CDKPM implementation of the adder.
Comparing the definition of the UMA gate, see figure 7, with the definition of
the borrowing $b_{k}$, given by equation (6) of definition 1.5, one can see
that the first sequence of $\textrm{UMA}^{\dagger}$ accumulate in the register
$X$ the value of the borrow, in particular $X_{n}\leftarrow(y-x)_{n}$. By
construction, see also proposition A.5, $(y-x)_{n}$ computes the overflow of
$y-x$ i.e. is $1$ whenever $x>y$. The subsequent CNOT copies the latter value
in the extra register $T$, and the following sequence of UMA gate uncomputes
the previous operation.

∎

The above comparator can also be executed using the temporary
logical-$\mathsf{AND}$ gate of Gidney, which consumes $n$ more ancillas (to
store the temporary logical and) in comparison to proposition 2.27

######  Proposition 2.28 (Comparator - Gidney - using half a subtractor).

There is a circuit implementing an $n$-bit quantum comparator as per
definition 2.24 using $n$ ancilla qubits and $n$ $\mathsf{Tof}$ gates.

Figure 21: Comparator circuit based on the CDKPM adder.

One can also easily realise a controlled implementation of the comparator
employing the previous addition circuits.

######  Definition 2.29 (Controlled quantum comparison).

We define a _controlled quantum comparator_ as any unitary gate implementing
the $n$ bits strings comparison according to the following circuit

######  Proposition 2.30 (Controlled comparator - CDKPM - using half a
subtractor [Cuc+04]).

There is a circuit implementing an $n$-bit controlled comparator as per
definition 2.29 using $0$ ancilla qubits and $2n+1$ $\mathsf{Tof}$ gates.

###### Proof.

The comparator is controlled by a qubit $\ket{c}_{1}$. From proposition 2.27,
we see that the output of the comparator is computed as the most significant
bit $(y-x)_{n}$ of the subtraction of $y$ and $x$. The $\mathsf{CNOT}$ that
copies the comparator value after the chain of $\mathsf{UMA}^{\dagger}$’s
needs to now be controlled, thus leading to an extra $\mathsf{Tof}$ gate. ∎

The previous quantum controlled comparator can also be executed using the
temporary logical-$\mathsf{AND}$ gate of Gidney, which consumes $n$ more
ancillas (to store the temporary logical AND) in comparison to proposition
2.30 but requires fewer $\mathsf{Tof}$ gates.

######  Proposition 2.31 (Controlled comparator - Gidney - using half a
subtractor).

There is a circuit implementing an $n$-bit controlled quantum comparator as
per definition 2.29 using $n+1$ ancilla qubits and $n+1$ $\mathsf{Tof}$.

When comparing registers, we note that they may not always be of equal size
$n$. When registers $x\in\\{0,1\\}^{n}$ and $y\in\\{0,1\\}^{n^{\prime}}$ with
$n<n^{\prime}$, one can circumvent this problem by padding the register
$\ket{x}_{n}$ with an extra $n^{\prime}-n$ qubits and perform the comparison
on two $n^{\prime}$ qubit registers. However, there is a slightly more
efficient solution available for the CDKPM and Gidney adders.

######  Remark 2.32.

Assume that $n^{\prime}=n+1$ without loss of generality. Let
$y_{[0,1,\cdots,n-1]}$ represent the first $n$ bits of $y$, notice that
$\mathbf{1}[x>y]\equiv\mathbf{1}[x>y_{[0,1,\cdots,n-1]}]\cdot(\mathsf{NOT}y_{n})$.
Therefore, the $\mathsf{CNOT}$ computing the required comparison now becomes a
$\mathsf{Tof}$ gate, with controls $\mathbf{1}[x>y_{[0,1,\cdots,n-1]}]$ and
$(\mathsf{NOT}y_{n})$. Thus using a single extra $\mathsf{Tof}$ gate with no
extra ancillas.

We now explore constructions for comparing a quantum register with a classical
value.

######  Definition 2.33 (Quantum comparison with a classical constant).

We define a _quantum comparator with a classical constant_ $a\in\\{0,1\\}^{n}$
as any unitary gate implementing the $n$ strings comparison with $a$ according
to the following circuit

where $\mathbf{1}[\mathsf{x<a}]$ coincides with the most significant bit of
$x-a$ i.e is $1$ when $x<a$ and $0$ otherwise.

######  Proposition 2.34 (Comparator by a classical constant).

Let $\mathsf{Q_{COMP}}$ be a circuit performing the $n$-bit comparator
operation as per definition 2.24 using $r$ $\mathsf{Tof}$ gates and $s$
ancillas. Then, there is a circuit implementing an $n$-bit comparator by a
classical constant as per definition 2.33 using the $r$ $\mathsf{Tof}$ gates
and $s+n$ ancillas, with an additional $2|a|$ NOT gates.

###### Proof.

Similar to the idea in proposition 2.16, we first use an $n$ qubit register to
load our constant $a$ into memory by applying $|a|$ NOT gates (one for each
bit $a_{i}\neq 0$), giving the state

$\ket{0}_{s+n}\ket{x}_{n}\ket{t}_{1}\xmapsto{\mathsf{Load}}\ket{0}_{s}\ket{a}_{n}\ket{x}_{n}\ket{t}~{}.$

Now, we apply the comparator circuit with inputs $\ket{a}\ket{x}$ on target
$\ket{t}$

$\ket{0}_{s}\ket{a}_{n}\ket{x}_{n}\ket{t}_{1}\xmapsto{\mathsf{Q_{COMP}}}\ket{0}_{s}\ket{a}_{n}\ket{x}_{n}\ket{t\oplus\mathbf{1}[a>x]}$

The ancilla is then uncomputed by applying the previous sequence of NOT gates
a second time

$\ket{0}_{s}\ket{a}_{n}\ket{x}_{n}\ket{t\oplus\mathbf{1}[x>y]}_{1}\xmapsto{\mathsf{Unload}}\ket{0}_{s+n}\ket{x}_{n}\ket{t\oplus\mathbf{1}[x<a]}_{1}~{}.$

∎

Similar to the construction in proposition 2.25, a comparator by a classical
constant can be constructed by using an adder and a subtractor, as shown
below.

######  Theorem 2.35 (Comparator with a classical constant - using an adder by
a constant and a subtractor by a constant).

Let $\mathsf{Q_{ADD}}(a)$ be a circuit performing an $n$-bit addition by a
constant as per definition 2.15, using $r_{\mathsf{ADD}}$ $\mathsf{Tof}$ gates
and $s_{\mathsf{ADD}}$ ancillas. Also, let $\mathsf{Q_{SUB}}(a)$ be a circuit
performing an $n$-bit subtraction by a constant as per definitions 2.15 and
2.21, using $r_{\mathsf{SUB}}$ $\mathsf{Tof}$ gates and $s_{\mathsf{SUB}}$
ancillas. Then, there is a circuit implementing an $n$-bit comparator by a
classical constant as per definition 2.33 using
$r=r_{\mathsf{ADD}}+r_{\mathsf{SUB}}$ $\mathsf{Tof}$ gates, an additional
$\mathsf{CNOT}$ gate and $s=1+\max(s_{\mathsf{ADD}},s_{\mathsf{SUB}})$ ancilla
qubits

###### Proof.

The idea is similar to proposition 2.25 giving a comparator using an adder and
a subtractor. ∎

Now, theorem 2.35 can be applied specifically to the case of the Draper adder
to give the theorem below.

######  Proposition 2.36 (Comparator by a classical constant -
Draper/Beauregard [Bea02]).

Let $x\in\\{0,1\\}^{n},a\in\\{0,1\\}^{n}$ be two bit strings. There is a
circuit implementing a comparator by a classical constant:

$\ket{x}_{n}\ket{t}_{1}\mapsto\ket{x}_{n}\ket{t\oplus\mathbf{1}[x<a]}_{1}.$

using a circuit with $1$ $\mathsf{CNOT}$, $2$ $\mathsf{QFT}_{n+1}$, $2$
$\mathsf{IQFT}_{n+1}$, $1$ $\mathsf{\Phi_{SUB}}(a)$ and $1$
$\mathsf{\Phi_{ADD}}(a)$ gates, and a single ancilla qubit.

###### Proof.

Using
$\mathsf{Q_{ADD}}=\mathsf{IQFT}_{n+1}\mathsf{\Phi_{ADD}}(a)\mathsf{QFT}_{n+1}$
and
$\mathsf{Q_{SUB}}=\mathsf{IQFT}_{n+1}\mathsf{\Phi_{SUB}}(a)\mathsf{QFT}_{n+1}$
in theorem 2.35, we require only a single ancilla. ∎

######  Definition 2.37 (Controlled comparison by a classical constant).

We define a _controlled quantum comparator with a classical constant_
$a\in\\{0,1\\}^{n}$ as any unitary gate implementing the $n$ strings
comparison with $a$ according to the following circuit

######  Theorem 2.38 (Controlled comparator by a classical constant - CDKPM -
using half a subtractor).

There is a circuit implementing an $n$-bit controlled comparator by a
classical constant as per definition 2.37 using $n+1$ ancilla qubits and $2n$
$\mathsf{Tof}$ gates

###### Proof.

The previous statement follows by using a comparator with classical constant
(proposition 2.34) and using an ancilla register for writing (controlled on
the register $\ket{c}$) the value of $a$ using $|a|$ CNOTs, which gets
uncomputed after using the comparator. ∎

######  Remark 2.39.

Given any circuit implementing the comparison $(x>y)$ as defined in definition
2.24 one can get the opposite comparison $(x\leq y)$ by simply postcomposing
the first circuit with an $\mathsf{X}$ gate acting on register $T$.

##  3 Quantum modular addition

In this section, we detail and build on the methods of Vedral et. al [VBE96]
for constructing modular adders as a suitable combination of the circuits for
addition, subtraction and comparison introduced in section 2.

######  Definition 3.1 (Modular addition).

Let $x\in\\{0,1\\}^{n},y\in\\{0,1\\}^{n}$ be two bit strings, and
$p\in\\{0,1\\}^{n}$ classically known with $0\leq x,y<p$. We define a _quantum
modular adder_ as any unitary gate implementing the $n$ strings _addition
modulo $p$_ according to the following circuit

The following implementation is a slight modification of [VBE96] and [Lit23].

######  Proposition 3.2 (Modular adder - Vedral’s architecture [VBE96]).

Let

  * •

$\mathsf{Q_{ADD}}$ be a quantum circuit that performs a quantum addition using
$s_{\mathsf{ADD}}$ ancillas, and $r_{\mathsf{ADD}}$ $\mathsf{Tof}$ gates,

  * •

$\mathsf{Q_{COMP}}(p)$ be a quantum comparator with a classical constant $p$
using $s_{\mathsf{COMP}}$ ancillas, $r_{\mathsf{COMP}}$ $\mathsf{Tof}$ gates,

  * •

$\mathsf{C\text{-}Q_{SUB}}(p)$ be a quantum circuit that performs a
(controlled) subtraction by a constant $p$ using $s_{\mathsf{C\text{-}SUB}}$
ancillas, and $r_{\mathsf{C\text{-}SUB}}$ $\mathsf{Tof}$ gates,

  * •

$\mathsf{Q_{COMP}^{\prime}}$: be a quantum comparator using
($s_{\mathsf{COMP}}^{\prime}$ ancillas, $r_{\mathsf{COMP}}^{\prime}$
$\mathsf{Tof}$ gates).

There is a circuit, $\mathsf{Q_{MODADD_{\text{p}}}}$, performing the $n$-bit
modular addition operation as per definition 3.1 using
$r=(r_{\mathsf{{ADD}}}+r_{\mathsf{{COMP}}}+r_{\mathsf{{C\text{-}SUB}}}+r_{\mathsf{{COMP}}}^{\prime})$
$\mathsf{Tof}$ gates and
$s=2+\max(s_{\mathsf{ADD}},s_{\mathsf{COMP}},s_{\mathsf{C\text{-}SUB}},s_{\mathsf{COMP}}^{\prime})$
ancillas.

###### Proof.

We start with a plain addition into our target

$\ket{0}_{s+1}\ket{x}_{n}\ket{y}_{n}\xmapsto{\mathsf{Q_{ADD}}}\ket{0}_{s}\ket{x}_{n}\ket{x+y}_{n+1}~{}.$

Using our comparator $\mathsf{Q_{COMP}}(p)$, we can perform a comparison of
the previous sum with the given modulus $p$

$\ket{0}_{s-1}\ket{x}_{n}\ket{x+y}_{n+1}\xmapsto{\mathsf{Q_{COMP}}(p)}\ket{0}_{s-1}\ket{x}_{n}\ket{x+y}_{n+1}\ket{\mathbf{1}[x+y<p]}~{}.$

When the comparator’s output is $0$, i.e. when $x+y\geq p$, we need to
subtract the modulus $p$ to compute the correct sum
$x+y\mathbin{\;\mathrm{mod}\;}p$. Therefore, we perform a controlled
subtraction of $p$ in the register currently storing $x+y$ (Note: We need to
flip, using an $\mathsf{X}$ gate, the value of the comparison qubit before
performing our controlled subtraction as pointed out in remark 2.39)

$\displaystyle\ket{0}_{s-1}\ket{x}_{n}\ket{x+y}_{n+1}\ket{1\oplus\mathbf{1}[x+y<p]}_{1}=\ket{0}_{s-1}\ket{x}_{n}\ket{x+y}_{n+1}\ket{\mathbf{1}[x+y\geq
p]}_{1}$
$\displaystyle\xmapsto{\mathsf{C\text{-}Q_{SUB}(p)}}\ket{0}_{s-1}\ket{x}_{n}\ket{x+y\mathbin{\;\mathrm{mod}\;}p}_{n+1}\ket{\mathbf{1}[x+y\geq
p]}_{1}~{}.$

Finally, we need to uncompute our previously computed output of the
comparator. We notice that $\mathbf{1}[x+y\geq
p]\equiv\mathbf{1}[x+y\mathbin{\;\mathrm{mod}\;}p<x]$ whenever $y<p$ strictly.
Namely, call $d=\mathbf{1}[x+y\geq p]$ then
$x+y\mathbin{\;\mathrm{mod}\;}p\equiv x+y-d\cdot p$ hence

$\mathbf{1}[x>x+y\mathbin{\;\mathrm{mod}\;}p]=\mathbf{1}[d\cdot p>y]=d~{}.$

Therefore, we can use $\mathsf{Q_{COMP}^{\prime}}$ on inputs $x$ and
$(x+y\mathbin{\;\mathrm{mod}\;}p)$ to perform the final step

$\displaystyle\ket{0}_{s-1}\ket{x}_{n}\ket{x+y\mathbin{\;\mathrm{mod}\;}p}_{n+1}$
$\displaystyle\ket{\mathbf{1}[x+y\geq p]}_{1}$
$\displaystyle\xmapsto{\mathsf{Q_{COMP}^{\prime}}}$
$\displaystyle\ket{0}_{s-1}\ket{x}_{n}\ket{x+y\mathbin{\;\mathrm{mod}\;}p}_{n+1}\ket{\mathbf{1}[x+y>p]\oplus\mathbf{1}[x+y\mathbin{\;\mathrm{mod}\;}p<x]}_{1}$
$\displaystyle=$
$\displaystyle\ket{0}_{s}\ket{x}_{n}\ket{x+y\mathbin{\;\mathrm{mod}\;}p}_{n+1}~{}.$

∎

Figure 22: Implementation of a modular adder using previous quantum adder
circuits.

######  Remark 3.3.

In principle, one can implement a subroutine computing
$x\mathbin{\;\mathrm{mod}\;}p$ for any given number $0\leq x<2p$ as follows

Therefore, a circuit computing $x+y\mathbin{\;\mathrm{mod}\;}p$ can be
alternatively given by

Proposition 3.2 gives an overview for constructing modular adders using any
available combination of adders, (controlled) subtractor (by a constant), and
comparators (by a constant). In the theorems below, we delve into specific
adder circuits used for modular addition and calculate concrete costs more
thoroughly.

######  Proposition 3.4 (Modular adder - CDKPM [Cuc+04]).

There is a circuit, $\mathsf{Q_{MODADD_{\text{p}}}}$, performing the $n$-bit
modular addition operation as per definition 3.1 using $n+3$ ancillas and $8n$
$\mathsf{Tof}$ gates.

###### Proof.

We employ proposition 3.2 with the following subroutines:

  * •

$\mathsf{Q_{ADD}}$: CDKPM plain adder (proposition 2.3);

  * •

$\mathsf{Q_{COMP}}(p)$: CDKPM half subtractor based constant comparator
proposition 2.27;

  * •

$\mathsf{C\text{-}Q_{SUB}}(p)$: CDKPM plain adder, more concretely, we use
$\mathsf{Q_{ADD}^{\dagger}}$ in theorem 2.19 for controlled constant
addition/subtraction (proposition 2.27);

  * •

$\mathsf{Q_{COMP}^{\prime}}$: CDKPM half subtractor based comparator
proposition 2.27.

From proposition 3.2, we know that the total $\mathsf{Tof}$ cost of performing
modular addition using the above selection of subroutines is
$r=(r_{\mathsf{{ADD}}}+r_{\mathsf{{COMP}}}+r_{\mathsf{{C\text{-}SUB}}}+r_{\mathsf{{COMP}}}^{\prime})=8n$
$\mathsf{Tof}$ gates. Similarly, the number of ancillas required is
$s=2+\max(s_{\mathsf{ADD}},s_{\mathsf{COMP}},s_{\mathsf{C\text{-}SUB}},s_{\mathsf{COMP}}^{\prime})=2+\max(1,n+1,n+1,1)=n+3$.

∎

The version presented above has essentially the same structure of [VBE96] but
enjoys some improvements. Namely, we use CDKPM’s adder (in proposition 2.3
instead of proposition 2.2), and we substitute the use of two adder circuits
for the comparator $\mathsf{Q_{COMP}^{\prime}}$ (proposition 2.25) with a
single comparator circuit. These changes are already known in the literature
(e.g. [Lit23]), but it is not often mentioned the use of $n$ ancilla qubits
for internal operations. If one has access to $2n$ ancillas, one can use
Gidney’s adder (proposition 2.4 instead of the CDKPM adder (i.e. proposition
2.3). This allows for a decrease in the number of $\mathsf{Tof}$ gates and
also the $\mathsf{Tof}$ depth.

######  Proposition 3.5 (Modular adder - Gidney [Gid18]).

There is a circuit, $\mathsf{Q_{MODADD_{\text{p}}}}$, performing the $n$-bit
modular addition operation as per definition 3.1 using $2n+3$ ancillas and
$4n$ $\mathsf{Tof}$ gates.

###### Proof.

The proof follows the same steps as proposition 3.4. We leverage proposition
3.2, with the following subroutines:

  * •

$\mathsf{Q_{ADD}}$: Gidney plain adder (proposition 2.4);

  * •

$\mathsf{Q_{COMP}}(p)$: Gidney half subtractor based constant comparator
proposition 2.28;

  * •

$\mathsf{C\text{-}Q_{SUB}}(p)$: Gidney plain adder, more concretely, we use
$\mathsf{Q_{ADD}^{\dagger}}$ in proposition 2.19 for controlled constant
addition/subtraction (proposition 2.27);

  * •

$\mathsf{Q_{COMP}^{\prime}}$: Gidney half subtractor based comparator
proposition 2.28.

From proposition 3.2, we know that the total $\mathsf{Tof}$ cost of performing
modular addition using the above selection of subroutines is
$r=(r_{\mathsf{{ADD}}}+r_{\mathsf{{COMP}}}+r_{\mathsf{{C\text{-}SUB}}}+r_{\mathsf{{COMP}}}^{\prime})=4n$
$\mathsf{Tof}$ gates. Similarly, the number of ancillas required is
$s=2+\max(s_{\mathsf{ADD}},n+s_{\mathsf{COMP}},n+s_{\mathsf{C\text{-}SUB}},s_{\mathsf{COMP}}^{\prime})=2+\max(n+1,2n+1,2n+1,n+1)=2n+3$.
∎

The above modular adder can be further modified to reduce the number of
ancillas. We propose to use the Gidney adder only for the first addition and
final comparison, and use the CDKPM adder for the constant subtraction and
constant comparison, thus giving us the following result.

######  Theorem 3.6 (Modular adder - Gidney + CDKPM).

There is a circuit, $\mathsf{Q_{MODADD_{\text{p}}}}$, performing the $n$-bit
modular addition operation as per definition 3.1 using $n+3$ ancillas and $6n$
$\mathsf{Tof}$ gates.

###### Proof.

The proof follows the same steps as the proof of proposition 3.4. In
particular:

  * •

$\mathsf{Q_{ADD}}$: Gidney plain adder (proposition 2.4);

  * •

$\mathsf{Q_{COMP}}(p)$: CDKPM half subtractor based constant comparator
proposition 2.27;

  * •

$\mathsf{C\text{-}Q_{SUB}}(p)$: CDKPM plain adder, more concretely, we use
$\mathsf{Q_{ADD}^{\dagger}}$ in proposition 2.19 for controlled constant
addition/subtraction (proposition 2.27);

  * •

$\mathsf{Q_{COMP}^{\prime}}$: Gidney half subtractor based comparator
(proposition 2.28).

From proposition 3.2, we know that the total $\mathsf{Tof}$ cost of performing
modular addition using the above selection of subroutines is
$r=(r_{\mathsf{{ADD}}}+r_{\mathsf{{COMP}}}+r_{\mathsf{{C\text{-}SUB}}}+r_{\mathsf{{COMP}}}^{\prime})=(n+2n+2n+n)=6n$
$\mathsf{Tof}$ gates. Similarly, the number of ancillas required is
$s=2+\max(s_{\mathsf{ADD}},n+s_{\mathsf{COMP}},n+s_{\mathsf{C\text{-}SUB}},s_{\mathsf{COMP}}^{\prime})=2+\max(n+1,n+1,n+1,n+1)=n+3$
ancillas. ∎

######  Proposition 3.7 (Modular adder - Draper/Beauregard [Bea02]).

There is a circuit, $\mathsf{Q_{MODADD_{\text{p}}}}$, performing the $n$-bit
modular addition operation as per definition 3.1 with a gate count of $3$
$\mathsf{QFT}$’s, $3$ $\mathsf{IQFT}$’s, $2$ $\mathsf{CNOT}$’s, $2$
$\mathsf{\Phi_{ADD}}$’s, $1$ $\mathsf{\Phi_{SUB}}$, $1$
$\mathsf{C\text{-}\Phi_{SUB}(p)}$, $1$ $\mathsf{\Phi_{ADD}(p)}$, $1$
$\mathsf{\Phi_{SUB}(p)}$ and $2$ ancillas.

###### Proof.

We leverage proposition 3.2, with the following subroutines:

  * •

$\mathsf{Q_{ADD}}$: Draper plain adder corollary 2.7;

  * •

$\mathsf{Q_{COMP}}(p)$: Draper’s comparator by a classical constant
proposition 2.36;

  * •

$\mathsf{C\text{-}Q_{SUB}}(p)$: Draper adder, more concretely, we use
$\mathsf{Q_{ADD}^{\dagger}}$ in proposition 2.20 and 2.13 for controlled
constant addition/subtraction;

  * •

$\mathsf{Q_{COMP}^{\prime}}$: Draper/Beauregard comparator proposition 2.26.

The $\mathsf{IQFT}$ of $\mathsf{Q_{ADD}}$ cancels with the $\mathsf{QFT}$ of
$\mathsf{Q_{COMP}}(p)$. We also find similar reductions for pairs the
$\mathsf{IQFT}$’s/$\mathsf{QFT}$’s of
$\mathsf{Q_{COMP}}(p)/\mathsf{C\text{-}Q_{SUB}}(p)$ and
$\mathsf{C\text{-}Q_{SUB}}(p)/\mathsf{Q_{COMP}^{\prime}}$. The total gate
count is therefore, $3$ $\mathsf{QFT}$’s, $3$ $\mathsf{IQFT}$’s, $2$
$\mathsf{CNOT}$’s, $2$ $\mathsf{\Phi_{ADD}}$’s, $1$ $\mathsf{\Phi_{SUB}}$, $1$
$\mathsf{C\text{-}\Phi_{SUB}(p)}$, $1$ $\mathsf{\Phi_{ADD}(p)}$ and $1$
$\mathsf{\Phi_{SUB}(p)}$. The number of ancillas required is $s=2$ ∎

###  3.1 Controlled modular addition

######  Definition 3.8 (Controlled modular addition).

We will denote controlled modular addition (with modulus $p$) as the following
circuit

A naive approach to creating a controlled modular adder is to add an extra
control to each gate of the four subroutines composing the modular adder
described in proposition 3.2. However, there is a more efficient approach
where only the first adder and final comparator need to be controlled. Such a
trick has been mentioned in [Lit23] without providing a proof.

######  Proposition 3.9 (Controlled modular adder).

Let

  * •

$\mathsf{C\text{-}Q_{ADD}}$ be a quantum circuit that performs a quantum
(controlled) addition using $s_{\mathsf{C\text{-}ADD}}$ ancillas, and
$r_{\mathsf{C\text{-}ADD}}$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{Q_{COMP}}(p)$ be a quantum comparator by a constant $p$, using
$s_{\mathsf{COMP}}$ ancillas, $r_{\mathsf{COMP}}$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{C\text{-}Q_{SUB}}(p)$ be a quantum circuit that performs a quantum
subtraction by a constant $p$, using $s_{\mathsf{C\text{-}SUB}}$ ancillas, and
$r_{\mathsf{C\text{-}SUB}}$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{C\text{-}Q_{COMP}^{\prime}}$: be a controlled quantum comparator
using ($s_{\mathsf{C\text{-}COMP}}^{\prime}$ ancillas,
$r_{\mathsf{C\text{-}COMP}}^{\prime}$ $\mathsf{Tof}$ gates).

There is a circuit $\mathsf{C\text{-}Q_{MODADD_{\text{p}}}}$, performing the
$n$-bit controlled modular addition operation as per definition 3.8, using
$r=(r_{\mathsf{{C\text{-}ADD}}}+r_{\mathsf{{COMP}}}+r_{\mathsf{{C\text{-}SUB}}}+r_{\mathsf{{C\text{-}COMP}}}^{\prime})$
$\mathsf{Tof}$ gates and
$s=2+\max(s_{\mathsf{C\text{-}ADD}},n+s_{\mathsf{COMP}},n+s_{\mathsf{C\text{-}SUB}},s_{\mathsf{C\text{-}COMP}}^{\prime})$
ancillas.

###### Proof.

In order to perform a controlled modular adder, start by first performing out
controlled addition of the addend $x$ into the target register

$\displaystyle\ket{0}_{s}\ket{c}_{1}\ket{x}_{n}\ket{y}_{n}\xmapsto{\mathsf{C\text{-}Q_{ADD}}}$
$\displaystyle\ket{0}_{s-1}\ket{c}_{1}\ket{x}_{n}\ket{c\cdot x+y}_{n+1}$ We
can now follow the step similar to the modular addition protocol, where we
perform a constant comparison
$\displaystyle\ket{0}_{s-1}\ket{c}_{1}\ket{x}_{n}\ket{c\cdot
x+y}_{n+1}\xmapsto{\mathsf{Q_{COMP}}(p)}$
$\displaystyle\ket{0}_{s-2}\ket{c}_{1}\ket{x}_{n}\ket{c\cdot
x+y}_{n+1}\ket{\mathbf{1}[c\cdot x+y<p]}_{1}$ Once again, similar to the
modular addition protocol, we perform a controlled subtraction of the modulus
$p$, controlled on our comparator’s output because if $(c\cdot x+y)\geq p$,
then the modulus $p$ needs to be subtract to reduce the sum
$\mathbin{\;\mathrm{mod}\;}p$. Note: We need to first flip the comparison
qubit, and then perform the controlled subtraction (see remark 2.39)
$\displaystyle\ket{0}_{s-2}\ket{c}_{1}\ket{x}_{n}\ket{c\cdot
x+y}_{n+1}\ket{\mathbf{1}[c\cdot x+y\geq p]}_{1}$
$\displaystyle\xmapsto{\mathsf{C\text{-}Q_{SUB}}(p)}$
$\displaystyle\ket{0}_{s-1}\ket{c}_{1}\ket{x}_{n}\ket{c\cdot
x+y\mathbin{\;\mathrm{mod}\;}p}_{n}\ket{\mathbf{1}[c\cdot x+y\geq p]}_{1}$ We
need to now uncompute the value initally computed by $\mathsf{Q_{COMP}}$. As
in the modular addition case, we need to find a comparison operation that is
equivalent to $d=\mathbf{1}[c\cdot x+y\geq p]$ (the qubit we wish to
uncompute/reset). Since $(c\cdot x+y\mathbin{\;\mathrm{mod}\;}p)=(c\cdot
x-c\cdot d\cdot p)$, one finds out that $c\cdot\mathbf{1}[c\cdot x+y\geq
p]\equiv\mathbf{1}[(c\cdot x+y)\mathbin{\;\mathrm{mod}\;}p<c\cdot x]$ and in
particular $d=c\cdot d$ since $(c\cdot x+y\geq p)$ is false whenever $c=0$
from the condition $y<p$. The only difference here compared to proposition 3.2
is that the comparator bit is only set for states with $c\cdot x+y\geq p$,
$\mathsf{AND}$ with the control bit set. The required operation is nothing but
a controlled comparison, with control $c$, inputs $x$ and $(c\cdot
x+y)\mathbin{\;\mathrm{mod}\;}p$
$\displaystyle\ket{0}_{s-1}\ket{c}_{1}\ket{x}_{n}\ket{c\cdot
x+y\mathbin{\;\mathrm{mod}\;}p}_{n}$ $\displaystyle\ket{\mathbf{1}[c\cdot
x+y\geq p]}_{1}$ $\displaystyle\xmapsto{\mathsf{C\text{-}Q_{COMP}^{\prime}}}$
$\displaystyle\ket{0}_{s}\ket{c}_{1}\ket{x}_{n}\ket{c\cdot
x+y\mathbin{\;\mathrm{mod}\;}p}_{n}~{}.$

∎

We will now explore some costs of controlled modular adders for a few specific
combinations of subroutines.

######  Proposition 3.10 (Controlled modular adder - CDKPM).

There is a circuit $\mathsf{C\text{-}Q_{MODADD_{\text{p}}}}$, performing the
$n$-bit controlled modular addition operation as per definition 3.8, using
$n+3$ ancillas and $9n+1$ $\mathsf{Tof}$ gates.

###### Proof.

We implement a controlled modular adder by using proposition 3.9 in
conjunction with the following subroutines:

  * •

$\mathsf{C\text{-}Q_{ADD}}$ be a quantum circuit that performs a quantum
(controlled) using a CDKPM adder with a single extra ancilla (theorem 2.12)
requiring $s_{\mathsf{C\text{-}ADD}}=2$ ancillas, and
$r_{\mathsf{C\text{-}ADD}}=3n$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{Q_{COMP}}(p)$ be a quantum comparator by a constant $p$ using
Controlled comparator - using half a CDKPM subtractor (theorem 2.38),
requiring $s_{\mathsf{COMP}}=n+1$ ancillas, $r_{\mathsf{COMP}}=2n$
$\mathsf{Tof}$ gates;

  * •

$\mathsf{C\text{-}Q_{SUB}}(p)$ be a quantum circuit that performs a quantum
subtraction by a constant $p$ using the CDKPM adder in proposition 2.16,
requiring $s_{\mathsf{C\text{-}SUB}}=n+1$ ancillas, and
$r_{\mathsf{C\text{-}SUB}}=2n$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{C\text{-}Q_{COMP}^{\prime}}$ be the quantum comparator described in
proposition 2.30: Controlled comparator - using half a CDKPM subtractor. This
subroutine requires $s_{\mathsf{C\text{-}COMP}}^{\prime}=1$ ancilla,
$r_{\mathsf{C\text{-}COMP}}^{\prime}=2n+1$ $\mathsf{Tof}$ gates.

There is a circuit $\mathsf{C\text{-}Q_{MODADD_{\text{p}}}}$, performing the
controlled modular addition operation as per definition 3.8, using
$r=(r_{\mathsf{{C\text{-}ADD}}}+r_{\mathsf{{COMP}}}+r_{\mathsf{{C\text{-}SUB}}}+r_{\mathsf{{C\text{-}COMP}}}^{\prime})=(3n+2n+2n+(2n+1))=9n+1$
$\mathsf{Tof}$ gates and
$s=2+\max(s_{\mathsf{C\text{-}ADD}},n+s_{\mathsf{COMP}},n+s_{\mathsf{C\text{-}SUB}},s_{\mathsf{C\text{-}COMP}}^{\prime})=2+\max(2,n+1,n+1,1)=n+3$
ancillas. ∎

######  Proposition 3.11 (Controlled modular adder - Gidney).

There is a circuit $\mathsf{C\text{-}Q_{MODADD_{\text{p}}}}$, performing the
$n$-bit controlled modular addition operation as per definition 3.8, using
$2n+3$ ancillas and $5n+1$ $\mathsf{Tof}$ gates.

###### Proof.

We implement a controlled modular adder by using proposition 3.9 in
conjunction with the following subroutines:

  * •

$\mathsf{C\text{-}Q_{ADD}}$ be a quantum circuit that performs a quantum
(controlled) using a Gidney adder with a single extra ancilla (proposition
2.11) requiring $s_{\mathsf{C\text{-}ADD}}=n+1$ ancillas, and
$r_{\mathsf{C\text{-}ADD}}=2n$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{Q_{COMP}}(p)$ be a quantum comparator by a constant $p$ using
Controlled comparator - using half a Gidney subtractor (proposition 2.31),
requiring $s_{\mathsf{COMP}}=2n+1$ ancillas, $r_{\mathsf{COMP}}=n$
$\mathsf{Tof}$ gates;

  * •

$\mathsf{C\text{-}Q_{SUB}}(p)$ be a quantum circuit that performs a controlled
quantum subtraction by a constant $p$ using the Gidney adder in proposition
2.16, requiring $s_{\mathsf{C\text{-}SUB}}=2n+1$ ancillas, and
$r_{\mathsf{C\text{-}SUB}}=n$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{C\text{-}Q_{COMP}^{\prime}}$ be the controlled quantum comparator
described in proposition 2.31: controlled comparator - using half a Gidney
subtractor. This subroutine requires $s_{\mathsf{C\text{-}COMP}}^{\prime}=n+1$
ancillas, $r_{\mathsf{C\text{-}COMP}}^{\prime}=n+1$ $\mathsf{Tof}$ gates.

According to proposition 3.9, there is a circuit performing the operation

$\ket{c}_{1}\ket{x}_{n}\ket{y}_{n}\xmapsto{\mathsf{C\text{-}Q_{MODADD}}}\ket{c}_{1}\ket{x}_{n}\ket{c\cdot
x+y\mathbin{\;\mathrm{mod}\;}p}_{n}$

using
$r=(r_{\mathsf{{C\text{-}ADD}}}+r_{\mathsf{{COMP}}}+r_{\mathsf{{C\text{-}SUB}}}+r_{\mathsf{{C\text{-}COMP}}}^{\prime})=(2n+n+n+(n+1))=5n+1$
$\mathsf{Tof}$ gates and
$s=2+\max(s_{\mathsf{C\text{-}ADD}},s_{\mathsf{COMP}},s_{\mathsf{C\text{-}SUB}},s_{\mathsf{C\text{-}COMP}}^{\prime})=2+\max(n+1,2n+1,2n+1,n+1)=2n+3$
ancillas. ∎

###  3.2 Modular addition by a constant

######  Definition 3.12 (Modular addition by a constant).

Let $x\in\\{0,1\\}^{n}$. Assume to know classically $p,a\in\\{0,1\\}^{n}$ with
$0\leq a,x<p$. We will denote modular addition by a constant $a$ (with modulus
$p$) with the following circuit

A simple way to perform a modular addition by a constant is by using a quantum
modular adder as given by definition 3.1.

######  Proposition 3.13 (Modular adder by a constant).

Let $\mathsf{Q_{MODADD_{p}}}$ be a quantum circuit that performs an $n$-bit
quantum modular addition as per definition 3.1, using $s$ ancillas, and $r$
$\mathsf{Tof}$ gates. Then, there is a circuit $\mathsf{Q_{MODADD_{p}}}(a)$
implementing an $n$-bit quantum modular addition by a constant as per
definition 3.12 using $n+s$ ancilla qubits and $r$ $\mathsf{Tof}$ gates, and
an additional $2|a|$ $\mathsf{NOT}$ gates.

###### Proof.

Similar to the proposition 2.16, We first take an unused $n$ qubit register,
and load the value $a$ using $|a|$ $\mathsf{NOT}$ gates

$\displaystyle\ket{0}_{s+n}\ket{x}_{n}\xmapsto{\mathsf{Load}}$
$\displaystyle\ket{0}_{s}\ket{a}_{n}\ket{x}_{n}$ We now perform the required
modular addition
$\displaystyle\ket{0}_{s}\ket{a}_{n}\ket{x}_{n}\xmapsto{\mathsf{Q_{MODADD}}}$
$\displaystyle\ket{0}_{s}\ket{a}_{n}\ket{x+a\mathbin{\;\mathrm{mod}\;}p}_{n}$
Finally, we unload the constant $a$
$\displaystyle\ket{0}_{s}\ket{a}_{n}\ket{x+a\mathbin{\;\mathrm{mod}\;}p}_{n}\xmapsto{\mathsf{Unload}}$
$\displaystyle\ket{0}_{s+n}\ket{x+a\mathbin{\;\mathrm{mod}\;}p}_{n}~{}.$

∎

The above construction works for any modular adder construction that performs
the operation
$\ket{x}_{n}\ket{y}_{n}\xmapsto{\mathsf{Q_{MODADD}}_{p}}\ket{x}_{n}\ket{y+x\mathbin{\;\mathrm{mod}\;}p}_{n}$.
However, when examining the VBE architecture, we can modify certain
subroutines to enable a different approach to performing constant modular
addition.

######  Theorem 3.14 (Modular adder by a constant - in VBE architecture).

Let

  * •

$\mathsf{Q_{ADD}(a)}$ be a quantum circuit that performs a constant quantum
addition using $s_{\mathsf{ADD}}$ ancillas, and $r_{\mathsf{ADD}}$
$\mathsf{Tof}$ gates;

  * •

$\mathsf{Q_{COMP}}(p)$ be a quantum comparator using $s_{\mathsf{COMP}}$
ancillas, $r_{\mathsf{COMP}}$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{C\text{-}Q_{SUB}}(p)$ be a quantum circuit that performs a
(controlled) subtraction by a constant $p$ using $s_{\mathsf{C\text{-}SUB}}$
ancillas, and $r_{\mathsf{C\text{-}SUB}}$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{Q_{COMP}^{\prime}}(a)$: be a constant quantum comparator using
($s_{\mathsf{COMP}}^{\prime}$ ancillas, $r_{\mathsf{COMP}}^{\prime}$
$\mathsf{Tof}$ gates).

there is a circuit $\mathsf{Q_{MODADD_{p}}}(a)$ implementing an $n$-bit
quantum modular addition by a constant as per definition 3.12 using
$r=(r_{\mathsf{{ADD}}}+r_{\mathsf{{COMP}}}+r_{\mathsf{{C\text{-}SUB}}}+r_{\mathsf{{COMP}}}^{\prime})$
$\mathsf{Tof}$ gates and
$s=2+\max(s_{\mathsf{ADD}},s_{\mathsf{COMP}},s_{\mathsf{C\text{-}SUB}},s_{\mathsf{COMP}}^{\prime})$
ancillas.

###### Proof.

The proof is very similar to the proof of the VBE modular adder architecture
(proposition 3.2). We start with an addition by a constant $a$ into our target

$\ket{0}_{s}\ket{x}_{n}\xmapsto{\mathsf{Q_{ADD}}(a)}\ket{0}_{s-1}\ket{x+a}_{n+1}~{}.$

Using our comparator $\mathsf{Q_{COMP}}(p)$, we can perform a comparison of
the previous sum with our modulus $p$

$\ket{0}_{s}\ket{x+a}_{n+1}\xmapsto{\mathsf{Q_{COMP}}(p)}\ket{0}_{s-2}\ket{x+a}_{n+1}\ket{\mathbf{1}[x+a<p]}_{1}~{}.$

When the comparator’s output is $0$, i.e. when $x+a\geq p$, we need to
subtract the modulus $p$ to compute the correct sum
$x+a\mathbin{\;\mathrm{mod}\;}p$. Therefore, we perform a controlled
subtraction of $p$ in the register currently storing $x+a$ (note: we need to
flip, using an $\mathsf{X}$ gate, the value of the comparison qubit before
performing our controlled subtraction):

$\ket{0}_{s-2}\ket{x+a}_{n+1}\ket{\mathbf{1}[x+a\geq
p]}_{1}\xmapsto{\mathsf{C\text{-}Q_{SUB}(p)}}\ket{0}_{s-1}\ket{x}_{n}\ket{x+a\mathbin{\;\mathrm{mod}\;}p}_{n}\ket{\mathbf{1}[x+a\geq
p]}_{1}~{}.$

We finally need to uncompute the comparator qubit. We notice that
$\mathbf{1}[x+a\geq p]\equiv\mathbf{1}[x+a\mathbin{\;\mathrm{mod}\;}p<a]$,
therefore, we can use $\mathsf{Q_{COMP}^{\prime}}(a)$ on inputs $a$ and
$(x+a\mathbin{\;\mathrm{mod}\;}p)$ to perform the final step

$\displaystyle\ket{0}_{s-1}\ket{x}_{n}\ket{x+a\mathbin{\;\mathrm{mod}\;}p}_{n}$
$\displaystyle\ket{\mathbf{1}[x+a\geq p]}_{1}$
$\displaystyle\xmapsto{\mathsf{Q_{COMP}^{\prime}}(a)}$
$\displaystyle\ket{0}_{s-1}\ket{x+a\mathbin{\;\mathrm{mod}\;}p}_{n}\ket{\mathbf{1}[x+a<p]\oplus\mathbf{1}[x+a\mathbin{\;\mathrm{mod}\;}p\geq
a]}_{1}$ $\displaystyle=$
$\displaystyle\ket{0}_{s}\ket{x+a\mathbin{\;\mathrm{mod}\;}p}_{n}~{}.$

∎

Given that we are adding by a constant, various ways exist to create more
cost-effective modular addition circuits by modifying the plain addition
implemented in the modular adder. Takahashi [Tak09] in 2009 was the first to
observe that the initial two operations in the VBE modular architecture could
be merged into a single operation when performing a constant modular addition.

######  Proposition 3.15 (Modular adder by a constant - in Takahashi
architecture [TTK09]).

Let

  * •

$\mathsf{Q_{SUB}(a)}$ be a quantum circuit that performs a constant quantum
subtraction using $s_{\mathsf{SUB}}$ ancillas, and $r_{\mathsf{SUB}}$
$\mathsf{Tof}$ gates;

  * •

$\mathsf{C\text{-}Q_{ADD}}(p)$ be a quantum circuit that performs a
(controlled) addition by a constant $p$ using $s_{\mathsf{C\text{-}ADD}}$
ancillas, and $r_{\mathsf{C\text{-}ADD}}$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{Q_{COMP}}(a)$ be a classical comparator using $s_{\mathsf{COMP}}$
ancillas, $r_{\mathsf{COMP}}$ $\mathsf{Tof}$ gates.

there is a circuit $\mathsf{Q_{MODADD_{p}}}(a)$ implementing an $n$-bit
quantum modular addition by a constant as per definition 3.12 using
$r=(r_{\mathsf{{SUB}}}+r_{\mathsf{{C\text{-}ADD}}}+r_{\mathsf{{COMP}}})$
$\mathsf{Tof}$ gates and
$s=1+\max(s_{\mathsf{SUB}},s_{\mathsf{C\text{-}ADD}},s_{\mathsf{COMP}})$
ancillas.

###### Proof.

To perform the unitary operation
$\ket{0}_{s}\ket{x}_{n}\xmapsto{\mathsf{Q_{MODADD}}_{p}(a)}\ket{x+a\pmod{p}}_{n}$,
we start subtracting $p-a$ (which is different from the first step of
proposition 3.2, where we add $a$)

$\displaystyle\ket{0}_{s-1}\ket{x}_{n}\xmapsto{\mathsf{Q_{SUB}(p-a)}}$
$\displaystyle\ket{0}_{s-1}\ket{x-(p-a)}_{n+1}=\ket{0}_{s-1}\ket{x+a-p}_{n+1}$
Now, we need to add back $p$ to those states whenever $x+a<p$. Notice that
$(x+a-p)_{n}$, i.e. the most significant bit of $x+a-p$ is $1$ only when
$x<(p-a)$. Controlled on $(x+a-p)_{n}$, we add back $p$
$\displaystyle\ket{0}_{s-1}\ket{x+a-p}_{n+1}\xmapsto{\mathsf{C\text{-}Q_{ADD}(p)}}$
$\displaystyle\ket{0}_{s-1}\ket{x+a\mathbin{\;\mathrm{mod}\;}p}_{n}\ket{\mathbf{1}[x+a<p]}_{1}~{}.$
Now, as we have seen many times before, we have to find an operation that
uncomputes $d=\mathbf{1}[x+a<p]$. We notice that
$\mathbf{1}[x+a<p]\equiv\mathbf{1}[x+a\mathbin{\;\mathrm{mod}\;}p\geq a]$
since $x+a\mathbin{\;\mathrm{mod}\;}p=x+a+(d-1)\cdot p$. Therefore, we can use
a constant comparator $(\cdot<a)$ followed by a NOT to perform the required
reset/uncomputation
$\displaystyle\ket{0}_{s-1}\ket{x+a\mathbin{\;\mathrm{mod}\;}p}_{n}\ket{\mathbf{1}[x+a<p]}$
$\displaystyle\xmapsto{\mathsf{Q_{COMP}(a)}}_{1}$
$\displaystyle\ket{0}_{s-1}\ket{x+a\mathbin{\;\mathrm{mod}\;}p}_{n}\ket{\mathbf{1}[x+a<p]\oplus\mathbf{1}[x+a\mathbin{\;\mathrm{mod}\;}p<a]}_{1}$
$\displaystyle=$
$\displaystyle\ket{0}_{s-1}\ket{x+a\mathbin{\;\mathrm{mod}\;}p}_{n}\ket{1}$
$\displaystyle\xmapsto{\mathsf{Q_{NOT}}}_{1}\ket{0}_{s}\ket{x+a\mathbin{\;\mathrm{mod}\;}p}_{n}~{}.$

∎

###  3.3 Controlled modular addition by a constant

######  Definition 3.16 (Controlled modular addition by a constant).

Given $x,a,p\in\\{0,1\\}^{n}$ (with $a,p$ classically known), and a control
$c\in\\{0,1\\}$ with $0\leq a,x<p$. We will denote controlled modular addition
by a constant $a$ (with modulus $p$) with the following circuit

A simple way to perform a controlled modular addition by a constant is by
using a quantum modular adder as per definition 3.1.

######  Theorem 3.17 (Controlled modular adder by a constant).

Let $\mathsf{Q_{MODADD_{p}}}$ be a quantum circuit that performs an $n$-bit
quantum modular addition as per definition 3.1 using $s$ ancillas, and $r$
$\mathsf{Tof}$ gates. Then, there is a circuit
$\mathsf{C\text{-}Q_{MODADD_{p}}}(a)$ implementing an $n$-bit controlled
quantum modular addition by a constant as per definition 3.16 using $n+s$
ancilla qubits and $r$ $\mathsf{Tof}$ gates, and an additional $2|a|$
$\mathsf{CNOT}$ gates.

###### Proof.

The technique is similar to what we have used in many previous cases when an
operation by a constant is involved. We first take an unused $n$ qubit
register, and load the value $a$ (controlled on $c$) using $|a|$
$\mathsf{CNOT}$ gates

$\displaystyle\ket{0}_{s+n}\ket{x}_{n}\xmapsto{\mathsf{Load}}$
$\displaystyle\ket{0}_{s}\ket{c\cdot a}_{n}\ket{x}_{n}~{}.$ We now perform the
required modular addition $\displaystyle\ket{0}_{s}\ket{c\cdot
a}_{n}\ket{x}_{n}\xmapsto{\mathsf{Q_{MODADD}}_{p}(a)}$
$\displaystyle\ket{0}_{s}\ket{c\cdot a}_{n}\ket{x+c\cdot
a\mathbin{\;\mathrm{mod}\;}p}_{n}~{}.$ We have to finally unload the constant
$a$ $\displaystyle\ket{0}_{s}\ket{c\cdot a}_{n}\ket{x+c\cdot
a\mathbin{\;\mathrm{mod}\;}p}_{n}\xmapsto{\mathsf{Unload}}$
$\displaystyle\ket{0}_{s+n}\ket{x+c\cdot
a\mathbin{\;\mathrm{mod}\;}p}_{n}~{}.$

∎

The above construction works for any modular adder construction that performs
the operation
$\ket{x}_{n}\ket{y}_{n}\xmapsto{\mathsf{Q_{MODADD}}_{p}}\ket{x}_{n}\ket{y+x}_{n}$.
However, if we look at the VBE architecture specifically, we can modify some
of the subroutines to provide a different method for performing a controlled
constant modular addition.

######  Proposition 3.18 (Controlled modular adder by a constant - in VBE
architecture [VBE96]).

Let

  * •

$\mathsf{C\text{-}Q_{ADD}(a)}$ be a quantum circuit that performs a controlled
constant addition using $s_{\mathsf{C\text{-}ADD}}$ ancillas, and
$r_{\mathsf{C\text{-}ADD}}$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{Q_{COMP}}(p)$ be a quantum comparator using $s_{\mathsf{COMP}}$
ancillas, $r_{\mathsf{COMP}}$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{C\text{-}Q_{SUB}}(p)$ be a quantum circuit that performs a
(controlled) subtraction by a constant $p$ using $s_{\mathsf{C\text{-}SUB}}$
ancillas, and $r_{\mathsf{C\text{-}SUB}}$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{C\text{-}Q_{COMP}^{\prime}}(a)$: be a controlled constant quantum
comparator using ($s_{\mathsf{C\text{-}COMP}}^{\prime}$ ancillas,
$r_{\mathsf{C\text{-}COMP}}^{\prime}$ $\mathsf{Tof}$ gates).

There is a circuit $\mathsf{C\text{-}Q_{MODADD_{p}}}(a)$ implementing an
$n$-bit controlled quantum modular addition by a constant as per definition
3.16 using
$r=(r_{\mathsf{{C\text{-}ADD}}}+r_{\mathsf{{COMP}}}+r_{\mathsf{{C\text{-}SUB}}}+r_{\mathsf{{C\text{-}COMP}}}^{\prime})$
$\mathsf{Tof}$ gates and
$s=2+\max(s_{\mathsf{C\text{-}ADD}},s_{\mathsf{COMP}},s_{\mathsf{C\text{-}SUB}},s_{\mathsf{C\text{-}COMP}}^{\prime})$
ancillas.

###### Proof.

The proof is very similar to the proof of the VBE modular adder architecture
(proposition 3.2). We start with a controlled addition by a constant $a$ into
our target

$\ket{0}_{s}\ket{c}_{1}\ket{x}_{n}\xmapsto{\mathsf{C\text{-}Q_{ADD}}(a)}\ket{0}_{s-1}\ket{x+c\cdot
a}_{n+1}~{}.$

Using our comparator $\mathsf{Q_{COMP}}(p)$, we can perform a comparison of
the previous sum with our modulus $p$

$\ket{0}_{s-1}\ket{c}_{1}\ket{x+c\cdot
a}_{n+1}\xmapsto{\mathsf{Q_{COMP}}(p)}\ket{0}_{s-2}\ket{c}_{1}\ket{x+c\cdot
a}_{n+1}\ket{\mathbf{1}[x+c\cdot a<p]}_{1}~{}.$

When the comparator’s output is 0, i.e. when $x+c\cdot a\geq p$, we need to
subtract the modulus $p$ to compute the correct sum $x+c\cdot
a\mathbin{\;\mathrm{mod}\;}p$. Therefore, we perform a controlled subtraction
of $p$ in the register currently storing $x+c\cdot a$ (Note: We need to flip,
using an $\mathsf{X}$ gate, the value of the comparison qubit before
performing our controlled subtraction )

$\ket{0}_{s-2}\ket{c}_{1}\ket{x+c\cdot a}_{n+1}\ket{\mathbf{1}[x+c\cdot a\geq
p]}_{1}\xmapsto{\mathsf{C\text{-}Q_{SUB}(p)}}\ket{0}_{s-1}\ket{c}_{1}\ket{x}_{n}\ket{x+c\cdot
a\mathbin{\;\mathrm{mod}\;}p}_{n}\ket{\mathbf{1}[x+c\cdot a\geq p]}_{1}$

We finally need to uncompute our previously computed output of the comparator.
We notice that $x\cdot\mathbf{1}[x+c\cdot a\geq
p]\equiv\cdot\mathbf{1}[x+c\cdot a\mathbin{\;\mathrm{mod}\;}p<c\cdot a]$
(similar to the proof of proposition 3.9), therefore, we can use
$\mathsf{Q_{C\text{-}COMP}^{\prime}}(a)$ on inputs $a$ and $(x+c\cdot
a\mathbin{\;\mathrm{mod}\;}p)$ to perform the final step

$\displaystyle\ket{0}_{s-1}\ket{c}_{1}\ket{x}_{n}\ket{x+c\cdot
a\mathbin{\;\mathrm{mod}\;}p}_{n}\ket{\mathbf{1}[x+c\cdot a\geq p]}_{1}$
$\displaystyle\xmapsto{\mathsf{Q_{C\text{-}COMP}^{\prime}}(a)}\ket{0}_{s-1}\ket{c}_{1}\ket{x+c\cdot
a\mathbin{\;\mathrm{mod}\;}p}_{n}$ $\displaystyle\ket{\mathbf{1}[x+c\cdot
a\geq p]\oplus c\cdot\mathbf{1}[x+c\cdot a\mathbin{\;\mathrm{mod}\;}p<c\cdot
a]}_{1}$ $\displaystyle=\ket{0}_{s}\ket{c}_{1}\ket{x+c\cdot
a\mathbin{\;\mathrm{mod}\;}p}_{n}$ $\displaystyle~{}.$

∎

A $\mathsf{QFT}$-based controlled constant modular adder was proposed by
Beauregard [Bea02], and works by combining the VBE architecture with Draper’s
$\mathsf{QFT}$ adder [Dra00] (proposition 2.5). We propose a slightly modified
proof below.

######  Proposition 3.19 (Controlled modular adder by a constant - Beauregard
[Bea02]).

There is a circuit $\mathsf{C\text{-}Q_{MODADD_{p}}}(a)$ implementing an
$n$-bit controlled quantum modular addition by a constant as per definition
3.16 with a gate count of $3$ $\mathsf{QFT}$’s, $3$ $\mathsf{IQFT}$’s, $2$
$\mathsf{CNOT}$’s, $1$ $\mathsf{C\text{-}\Phi_{ADD}}(a)$, $1$
$\mathsf{\Phi_{ADD}}(a)$, $1$ $\mathsf{\Phi_{SUB}}(a)$, $1$
$\mathsf{C\text{-}\Phi_{SUB}(p)}$, $1$ $\mathsf{\Phi_{ADD}(p)}$, $1$
$\mathsf{\Phi_{SUB}(p)}$ and $2$ ancillas.

###### Proof.

We use the following subroutines. Let

  * •

$\mathsf{C\text{-}Q_{ADD}(a)}$ be Draper’s controlled adder by a constant
(proposition 2.20), using $0$ ancillas;

  * •

$\mathsf{Q_{COMP}}(p)$ be a quantum comparator based on proposition 2.36,
using $1$ ancilla;

  * •

$\mathsf{C\text{-}Q_{SUB}}(p)$ be a quantum circuit that performs a controlled
subtraction by a constant based on proposition 2.20 using $0$ ancillas;

  * •

$\mathsf{C\text{-}Q_{COMP}^{\prime}}(a)$: be a controlled quantum comparator
by a constant as derived in theorem 2.38 using $1$ ancilla.

Note that adjacent $\mathsf{QFT}$s and $\mathsf{IQFT}$s can cancel out. The
total gate count is therefore, $3$ $\mathsf{QFT}$’s, $3$ $\mathsf{IQFT}$’s,
$2$ $\mathsf{CNOT}$’s, $1$ $\mathsf{C\text{-}\Phi_{ADD}}(a)$, $1$
$\mathsf{\Phi_{ADD}}(a)$, $1$ $\mathsf{\Phi_{SUB}}(a)$, $1$
$\mathsf{C\text{-}\Phi_{SUB}(p)}$, $1$ $\mathsf{\Phi_{ADD}(p)}$ and $1$
$\mathsf{\Phi_{SUB}(p)}$. The number of ancillas required is $s=2$ ∎

In proposition 3.19, the modular addition circuit is based on a single
controlled $\mathsf{QFT}$ adder. For completeness, we also share Beauregard’s
[Bea02] original circuit in figure 23 which uses two controls, and also uses a
slightly different set of gates..

Figure 23: Quantum Fourier Transform modular adder by a constant. Here
$\ket{\phi(x)}$ is made of $n+1$ qubits instead of $n$ qubits, in order to
account for the initial overflow from adding $a$.

##  4 Measurement-based uncomputation speed-ups

We are now prepared to present the proof of the MBU lemma and its applications
to modular arithmetic. The MBU algorithm for uncomputing a single qubit is the
circuit that can be found in figure 24. Recall that MBU has already been
introduced in [Gid18] (for the special case of $\mathsf{Tof}$ gates) but here
we formalize this method for the single-qubit uncomputation of any unitary.
Attempts at generalization of MBU to perform multi-qubit computation has been
already treated in the literature, see e.g. [Gid19b].

Figure 24: A circuit for measurement-based uncomputing the unitary $U_{g}$.

######  Lemma 4.1 (Measurement-based uncomputation lemma).

Let $g:\,\\{0,1\\}^{n}\to\\{0,1\\}$ be a function, and let $U_{g}$ be a self-
adjoint $(n+1)$-qubit unitary that implements $g$ as follows:

$U_{g}\ket{x}_{A}\ket{b}_{G}=\ket{x}_{A}\ket{b\oplus g(x)}_{G}.$

There is an algorithm performing the mapping

$\sum_{x}\alpha_{x}\ket{x}_{A}\ket{g(x)}_{G}\mapsto\sum_{x}\alpha_{x}\ket{x}_{A}\ket{0}_{G}$

using with $1/2$ probability $U_{g}$, $2$ $\mathsf{H}$ gates, and $1$
$\mathsf{NOT}$ gate. It also involves one single-qubit computational basis
measurement and a single $\mathsf{H}$ gate.

###### Proof.

The algorithm is described in figure 24. We first apply the Hadamard gate on
the register $G$ and measure it in the computational basis. Since
$g(x)\in\\{0,1\\}$, the resulting outcomes is $0$ or $1$ with equal
probabilities. If we obtain $0$, we successfully uncomputed the register,
leaving the registers in the state $\sum_{x}\alpha_{x}\ket{x}_{A}\ket{0}_{G}$.
On the other hand, if we get the outcome $1$, the state at this point is
$\sum_{x}\alpha_{x}(-1)^{g(x)}\ket{x}_{A}\ket{1}_{G}.$ We then apply another
Hadamard to $G$, followed by $U_{g}$. This performs a phase kickback, leaving
the quantum computer in the state

$\sum_{x}\alpha_{x}(-1)^{g(x)}\ket{x}_{A}\frac{\ket{0\oplus
g(x)}_{G}-\ket{1\oplus g(x)}_{G}}{\sqrt{2}}=\sum_{x}\alpha_{x}(-1)^{g(x)\oplus
g(x)}\ket{x}_{A}\ket{-}_{G}.$

Applying on $G$ another Hadamard and a NOT gate results in the final state
$\sum_{x}\alpha_{x}\ket{x}_{A}\ket{0}_{G}$. ∎

###  4.1 Modular addition

Figure 25: Implementation of a MBU modular addition. The double dotted lines
represents the uncomputation of the ancilla, controlled on the measurement
value.

######  Theorem 4.2 (MBU modular adder - VBE architecture).

Let

  * •

$\mathsf{Q_{ADD}}$ be a quantum circuit that performs a quantum addition using
$s_{\mathsf{ADD}}$ ancillas, and $r_{\mathsf{ADD}}$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{Q_{COMP}}(p)$ be a quantum comparator using $s_{\mathsf{COMP}}$
ancillas, $r_{\mathsf{COMP}}$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{C\text{-}Q_{SUB}}(p)$ be a quantum circuit that performs a
(controlled) subtraction by a constant $p$ using $s_{\mathsf{C\text{-}SUB}}$
ancillas, and $r_{\mathsf{C\text{-}SUB}}$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{Q_{COMP}^{\prime}}$: be a quantum comparator using
($s_{\mathsf{COMP}}^{\prime}$ ancillas, $r_{\mathsf{COMP}}^{\prime}$
$\mathsf{Tof}$ gates).

There is a circuit, $\mathsf{Q_{MODADD_{\text{p}}}}$, performing the $n$-bit
modular addition operation as per definition 3.1 using
$r=\left(r_{\mathsf{{ADD}}}+r_{\mathsf{{COMP}}}+r_{\mathsf{{C\text{-}SUB}}}+\left(r_{\mathsf{{COMP}}}^{\prime}/2\right)\right)$
$\mathsf{Tof}$ gates in expectation and

$s=2+\max(s_{\mathsf{ADD}},s_{\mathsf{COMP}},s_{\mathsf{C\text{-}SUB}},s_{\mathsf{COMP}}^{\prime})$

ancillas.

###### Proof.

As seen in the modular adder - VBE architecture (proposition 3.2), the first
three subroutines perform the following mapping

$\displaystyle\ket{0}_{s}\ket{x}_{n}\ket{y}_{n}\xmapsto{\mathsf{Q_{ADD}},\mathsf{Q_{COMP}}(p),\mathsf{C\text{-}Q_{SUB}(p)}}\ket{0}_{s-1}\ket{x}_{n}\ket{x+y\mathbin{\;\mathrm{mod}\;}p}_{n}\ket{\mathbf{1}[x+y\geq
p]}_{1}.$

The comparator qubit storing $\mathbf{1}[x+y\geq p]$ is finally supposed to be
uncomputed using $\mathsf{Q_{COMP}^{\prime}}$. We can apply the MBU lemma on
the comparator qubit and the uncomputation subroutine
$\mathsf{Q_{COMP}^{\prime}}$, thus halving the cost of
$\mathsf{Q_{COMP}^{\prime}}$ in expectation. Therefore, we finally get a cost
of
$r=\left(r_{\mathsf{{ADD}}}+r_{\mathsf{{COMP}}}+r_{\mathsf{{C\text{-}SUB}}}+\left(r_{\mathsf{{COMP}}}^{\prime}/2\right)\right)$
$\mathsf{Tof}$ gates in expectation, and the same ancilla count at proposition
3.2. ∎

######  Theorem 4.3 (MBU modular adder - CDKPM).

There is a circuit, $\mathsf{Q_{MODADD_{\text{p}}}}$, performing the $n$-bit
modular addition operation as per definition 3.1 using $n+3$ ancillas and $7n$
$\mathsf{Tof}$ gates in expectation.

###### Proof.

For the CDKPM modular adder described in proposition 3.4, the following
subroutines are used:

  * •

$\mathsf{Q_{ADD}}$: CDKPM plain adder proposition 2.3;

  * •

$\mathsf{Q_{COMP}}(p)$: CDKPM half subtractor based constant comparator
proposition 2.27;

  * •

$\mathsf{C\text{-}Q_{SUB}}(p)$: CDKPM plain adder, more concretely, we use
$\mathsf{Q_{ADD}^{\dagger}}$ in proposition 2.19.

  * •

$\mathsf{Q_{COMP}^{\prime}}$: CDKPM half subtractor based comparator
proposition 2.27.

Now, applying theorem 4.2, we find that our expected $\mathsf{Tof}$ gate cost
is

$r=\left(r_{\mathsf{{ADD}}}+r_{\mathsf{{COMP}}}+r_{\mathsf{{C\text{-}SUB}}}+\left(r_{\mathsf{{COMP}}}^{\prime}/2\right)\right)=(2n+2n+2n+(2n/2))=7n$

and the ancilla count is $s=n+3$.

∎

######  Theorem 4.4 (MBU modular adder - Gidney).

There is a circuit, $\mathsf{Q_{MODADD_{\text{p}}}}$, performing the $n$-bit
modular addition operation as per definition 3.1 using $2n+3$ ancillas, $3.5n$
$\mathsf{Tof}$ gates in expectation.

###### Proof.

Assume to access the following subroutines are used:

  * •

$\mathsf{Q_{ADD}}$: Gidney plain adder proposition 2.4;

  * •

$\mathsf{Q_{COMP}}(p)$: Gidney half subtractor based constant comparator
proposition 2.28;

  * •

$\mathsf{C\text{-}Q_{SUB}}(p)$: Gidney plain adder, more concretely, we use
$\mathsf{Q_{ADD}^{\dagger}}$ in proposition 2.19.

  * •

$\mathsf{Q_{COMP}^{\prime}}$: Gidney half subtractor based comparator
proposition 2.28.

Now, applying theorem 4.2, we find that our expected $\mathsf{Tof}$ gate cost
is

$r=\left(r_{\mathsf{{ADD}}}+r_{\mathsf{{COMP}}}+r_{\mathsf{{C\text{-}SUB}}}+\left(r_{\mathsf{{COMP}}}^{\prime}/2\right)\right)=(n+n+n+(n/2))=3.5n$

and the ancilla count is $s=2n+3$ .

∎

######  Theorem 4.5 (MBU modular adder - Gidney + CDKPM).

There is a circuit, $\mathsf{Q_{MODADD_{\text{p}}}}$, performing the $n$-bit
modular addition operation as per definition 3.1 using $n+3$ ancillas, $5.5n$
$\mathsf{Tof}$ gates in expectation.

###### Proof.

For the Gidney+CDKPM modular adder described in theorem 4.5, the following
subroutines are used:

  * •

$\mathsf{Q_{ADD}}$: Gidney plain adder proposition 2.4;

  * •

$\mathsf{Q_{COMP}}(p)$: CDKPM half subtractor based constant comparator
proposition 2.27;

  * •

$\mathsf{C\text{-}Q_{SUB}}(p)$: CDKPM plain adder, more concretely, we use
$\mathsf{Q_{ADD}^{\dagger}}$ in proposition 2.19.

  * •

$\mathsf{Q_{COMP}^{\prime}}$: Gidney half subtractor based comparator
proposition 2.28.

Now, applying theorem 4.2, we find that our expected $\mathsf{Tof}$ gate cost
is

$r=\left(r_{\mathsf{{ADD}}}+r_{\mathsf{{COMP}}}+r_{\mathsf{{C\text{-}SUB}}}+\left(r_{\mathsf{{COMP}}}^{\prime}/2\right)\right)=(n+2n+2n+(n/2))=5.5n$

and the ancilla count is $s=n+3$ . ∎

######  Theorem 4.6 (MBU modular adder - Draper/Beauregard).

Let $x\in\\{0,1\\}^{n},y\in\\{0,1\\}^{n}$ be two bit strings, and
$p\in\\{0,1\\}^{n}$ classically known with $0\leq x,y<p$. There is a circuit,
$\mathsf{Q_{MODADD_{\text{p}}}}$, performing the modular addition operation as
per definition 3.1 with an expected gate count of $2.5$ $\mathsf{QFT}$’s,
$2.5$ $\mathsf{IQFT}$’s, $1.5$ $\mathsf{CNOT}$’s, $1.5$
$\mathsf{\Phi_{ADD}}$’s, $0.5$ $\mathsf{\Phi_{SUB}}$’s, $1$
$\mathsf{C\text{-}\Phi_{SUB}(p)}$, $1$ $\mathsf{\Phi_{ADD}(p)}$, $1$
$\mathsf{\Phi_{SUB}(p)}$ and $2$ ancillas.

###### Proof.

We leverage proposition 3.2, with the following subroutines:

  * •

$\mathsf{Q_{ADD}}$: Draper plain adder corollary 2.7;

  * •

$\mathsf{Q_{COMP}}(p)$: Draper’s comparator by a classical constant
proposition 2.36;

  * •

$\mathsf{C\text{-}Q_{SUB}}(p)$: Draper adder, more concretely, we use
$\mathsf{Q_{ADD}^{\dagger}}$ in proposition 2.20 and 2.13 for controlled
constant addition/subtraction;

  * •

$\mathsf{Q_{COMP}^{\prime}}$: Draper/Beauregard comparator proposition 2.26.

The $\mathsf{IQFT}$ of $\mathsf{Q_{ADD}}$ cancels with the $\mathsf{QFT}$ of
$\mathsf{Q_{COMP}}(p)$. We also find similar reductions for pairs the
$\mathsf{IQFT}$’s/$\mathsf{QFT}$’s of
$\mathsf{Q_{COMP}}(p)/\mathsf{C\text{-}Q_{SUB}}(p)$ and
$\mathsf{C\text{-}Q_{SUB}}(p)/\mathsf{Q_{COMP}^{\prime}}$. The expected gate
count is therefore, $2.5$ $\mathsf{QFT}$’s, $2.5$ $\mathsf{IQFT}$’s, $1.5$
$\mathsf{CNOT}$’s, $1.5$ $\mathsf{\Phi_{ADD}}$’s, $0.5$
$\mathsf{\Phi_{SUB}}$’s, $1$ $\mathsf{C\text{-}\Phi_{SUB}(p)}$, $1$
$\mathsf{\Phi_{ADD}(p)}$ and $1$ $\mathsf{\Phi_{SUB}(p)}$. The number of
ancillas required is $s=2$. ∎

###  4.2 Controlled modular addition

######  Theorem 4.7 (MBU controlled modular adder - VBE architecture).

Let

  * •

$\mathsf{C\text{-}Q_{ADD}}$ be a quantum circuit that performs a quantum
(controlled) addition using $s_{\mathsf{C\text{-}ADD}}$ ancillas, and
$r_{\mathsf{C\text{-}ADD}}$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{Q_{COMP}}(p)$ be a quantum comparator by a constant $p$, using
$s_{\mathsf{COMP}}$ ancillas, $r_{\mathsf{COMP}}$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{C\text{-}Q_{SUB}}(p)$ be a quantum circuit that performs a quantum
subtraction by a constant $p$, using $s_{\mathsf{C\text{-}SUB}}$ ancillas, and
$r_{\mathsf{C\text{-}SUB}}$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{C\text{-}Q_{COMP}^{\prime}}$: be a controlled quantum comparator
using ($s_{\mathsf{C\text{-}COMP}}^{\prime}$ ancillas and
$r_{\mathsf{C\text{-}COMP}}^{\prime}$ $\mathsf{Tof}$ gates).

There is a circuit $\mathsf{C\text{-}Q_{MODADD_{p}}}$ implementing an $n$-bit
controlled quantum modular addition as per definition 3.8 using
$r=\left(r_{\mathsf{{C\text{-}ADD}}}+r_{\mathsf{{COMP}}}+r_{\mathsf{{C\text{-}SUB}}}+\left(r_{\mathsf{{C\text{-}COMP}}}^{\prime}\right/2)\right)$
$\mathsf{Tof}$ gates in expectation and
$s=2+\max(s_{\mathsf{C\text{-}ADD}},s_{\mathsf{COMP}},s_{\mathsf{C\text{-}SUB}},s_{\mathsf{C\text{-}COMP}}^{\prime})$
ancillas.

###### Proof.

As seen in the controlled modular adder - VBE architecture (proposition 3.9),
the first three subroutines perform the following mapping

$\displaystyle\ket{0}_{s}\ket{c}_{1}\ket{x}_{n}\ket{y}_{n}\xmapsto{\mathsf{C\text{-}Q_{ADD}},\mathsf{Q_{COMP}}(p),\mathsf{C\text{-}Q_{SUB}(p)}}\ket{0}_{s-1}\ket{c}_{1}\ket{x}_{n}\ket{c\cdot
x+y\mathbin{\;\mathrm{mod}\;}p}_{n}\ket{\mathbf{1}[c\cdot x+y\geq p]}_{1}~{}.$

The comparator qubit storing $\mathbf{1}[c\cdot x+y\geq p]$ is finally
supposed to be uncomputed using $\mathsf{C\text{-}Q_{COMP}^{\prime}}$. We can
apply the MBU lemma here on the comparator qubit and the uncomputation
subroutine $\mathsf{C\text{-}Q_{COMP}^{\prime}}$, thus halving the cost of
$\mathsf{C\text{-}Q_{COMP}^{\prime}}$ in expectation. Therefore, we finally
get a cost of
$r=\left(r_{\mathsf{{C\text{-}ADD}}}+r_{\mathsf{{COMP}}}+r_{\mathsf{{C\text{-}SUB}}}+\left(r_{\mathsf{{C\text{-}COMP}}}^{\prime}/2\right)\right)$
$\mathsf{Tof}$ gates in expectation, and the same ancilla count as proposition
3.9. ∎

######  Theorem 4.8 (MBU controlled modular adder - CDKPM).

There is a circuit $\mathsf{C\text{-}Q_{MODADD_{p}}}$ implementing an $n$-bit
controlled quantum modular addition as per definition 3.8 using $n+3$ ancillas
and $8n+0.5$ $\mathsf{Tof}$ gates in expectation.

###### Proof.

For the controlled CDKPM modular adder described in proposition 3.10, the
following subroutines are used:

  * •

$\mathsf{C\text{-}Q_{ADD}}$ be a quantum circuit that performs a quantum
(controlled) using a CDKPM adder with a single extra ancilla (theorem 2.12)
requiring $s_{\mathsf{C\text{-}ADD}}=2$ ancillas, and
$r_{\mathsf{C\text{-}ADD}}=3n$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{Q_{COMP}}(p)$ be a quantum comparator by a constant $p$ using
Controlled comparator - using half a CDKPM subtractor (theorem 2.38),
requiring $s_{\mathsf{COMP}}=n+1$ ancillas, $r_{\mathsf{COMP}}=2n$
$\mathsf{Tof}$ gates;

  * •

$\mathsf{C\text{-}Q_{SUB}}(p)$ be a quantum circuit that performs a quantum
subtraction by a constant $p$ using the CDKPM adder in proposition 2.16,
requiring $s_{\mathsf{C\text{-}SUB}}=n+1$ ancillas, and
$r_{\mathsf{C\text{-}SUB}}=2n$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{C\text{-}Q_{COMP}^{\prime}}$ be the controlled quantum comparator
described in proposition 2.30: Controlled comparator - using half a CDKPM
subtractor. This subroutine requires $s_{\mathsf{C\text{-}COMP}}^{\prime}=1$
ancilla, $r_{\mathsf{C\text{-}COMP}}^{\prime}=2n+1$ $\mathsf{Tof}$ gates.

Now, applying theorem 4.2, we find that our expected $\mathsf{Tof}$ gate cost
is

$r=\left(r_{\mathsf{{C\text{-}ADD}}}+r_{\mathsf{{COMP}}}+r_{\mathsf{{C\text{-}SUB}}}+\left(r_{\mathsf{{C\text{-}COMP}}}^{\prime}/2\right)\right)=(3n+2n+2n+(2n+1)/2)=8n+0.5$

and the ancilla count is $s=n+3$. ∎

######  Theorem 4.9 (MBU controlled modular adder - Gidney).

There is a circuit $\mathsf{C\text{-}Q_{MODADD_{p}}}$ implementing an $n$-bit
controlled quantum modular addition as per definition 3.8 using $2n+3$
ancillas, $4.5n+0.5$ $\mathsf{Tof}$ gates in expectation.

###### Proof.

For the Gidney controlled modular adder described in proposition 3.11, the
following subroutines are used:

  * •

$\mathsf{C\text{-}Q_{ADD}}$ be a quantum circuit that performs a quantum
(controlled) using a Gidney adder with a single extra ancilla (proposition
2.11) requiring $s_{\mathsf{C\text{-}ADD}}=n+1$ ancillas, and
$r_{\mathsf{C\text{-}ADD}}=2n$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{Q_{COMP}}(p)$ be a quantum comparator by a constant $p$ using
Controlled comparator - using half a Gidney subtractor (proposition 2.31),
requiring $s_{\mathsf{COMP}}=2n+1$ ancillas, $r_{\mathsf{COMP}}=n$
$\mathsf{Tof}$ gates;

  * •

$\mathsf{C\text{-}Q_{SUB}}(p)$ be a quantum circuit that performs a controlled
quantum subtraction by a constant $p$ using the Gidney adder in proposition
2.16, requiring $s_{\mathsf{C\text{-}SUB}}=2n+1$ ancillas, and
$r_{\mathsf{C\text{-}SUB}}=n$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{C\text{-}Q_{COMP}^{\prime}}$ be the controlled quantum comparator
described in proposition 2.31: controlled comparator - using half a Gidney
subtractor. This subroutine requires $s_{\mathsf{C\text{-}COMP}}^{\prime}=n+1$
ancillas, $r_{\mathsf{C\text{-}COMP}}^{\prime}=n+1$ $\mathsf{Tof}$ gates.

Now, applying theorem 4.2, we find that our expected $\mathsf{Tof}$ gate cost
is

$r=\left(r_{\mathsf{{C\text{-}ADD}}}+r_{\mathsf{{COMP}}}+r_{\mathsf{{C\text{-}SUB}}}+\left(r_{\mathsf{{C\text{-}COMP}}}^{\prime}/2\right)\right)=(2n+n+n+(n+1)/2)=4.5n+0.5$

and the ancilla count is $s=2n+3$. ∎

###  4.3 Modular addition by a constant

######  Theorem 4.10 (MBU modular addition by a constant - VBE architecture).

Let

  * •

$\mathsf{Q_{ADD}(a)}$ be a quantum circuit that performs a constant quantum
addition using $s_{\mathsf{ADD}}$ ancillas, and $r_{\mathsf{ADD}}$
$\mathsf{Tof}$ gates;

  * •

$\mathsf{Q_{COMP}}(p)$ be a quantum comparator using $s_{\mathsf{COMP}}$
ancillas, $r_{\mathsf{COMP}}$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{C\text{-}Q_{SUB}}(p)$ be a quantum circuit that performs a
(controlled) subtraction by a constant $p$ using $s_{\mathsf{C\text{-}SUB}}$
ancillas, and $r_{\mathsf{C\text{-}SUB}}$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{Q_{COMP}^{\prime}}(a)$: be a constant quantum comparator using
($s_{\mathsf{COMP}}^{\prime}$ ancillas, $r_{\mathsf{COMP}}^{\prime}$
$\mathsf{Tof}$ gates).

there is a circuit $\mathsf{Q_{MODADD_{p}}}(a)$ implementing an $n$-bit
quantum modular addition by a constant as per definition 3.12 using
$r=\left(r_{\mathsf{{ADD}}}+r_{\mathsf{{COMP}}}+r_{\mathsf{{C\text{-}SUB}}}+\left(r_{\mathsf{{COMP}}}^{\prime}/2\right)\right)$
$\mathsf{Tof}$ gates and
$s=2+\max(s_{\mathsf{ADD}},s_{\mathsf{COMP}},s_{\mathsf{C\text{-}SUB}},s_{\mathsf{COMP}}^{\prime})$
ancillas.

###### Proof.

As seen in the constant modular adder in VBE architecture (theorem 3.14), the
first three subroutines perform the following mapping

$\displaystyle\ket{0}_{s}\ket{x}_{n}\xmapsto{\mathsf{Q_{ADD}}(a),\mathsf{Q_{COMP}}(p),\mathsf{C\text{-}Q_{SUB}}(p)}\ket{0}_{s-1}\ket{x}_{n}\ket{x+a\mathbin{\;\mathrm{mod}\;}p}_{n}\ket{\mathbf{1}[x+a\geq
p]}_{1}~{}.$

The comparator qubit storing $\ket{\mathbf{1}[x+a\geq p]}_{1}$ is finally
supposed to be uncomputed using $\mathsf{Q_{COMP}^{\prime}}(a)$. We can apply
the MBU lemma here on the comparator qubit and the uncomputation subroutine
$\mathsf{Q_{COMP}^{\prime}}(a)$, thus halving the cost of
$\mathsf{Q_{COMP}^{\prime}}(a)$ in expectation. Therefore, we finally get a
cost of
$r=\left(r_{\mathsf{{ADD}}}+r_{\mathsf{{COMP}}}+r_{\mathsf{{C\text{-}SUB}}}+\left(r_{\mathsf{{COMP}}}^{\prime}/2\right)\right)$
$\mathsf{Tof}$ gates in expectation, and the same ancilla count at theorem
3.14. ∎

######  Theorem 4.11 (MBU modular adder by a constant - in Takahashi
Architecture).

Let $x\in\\{0,1\\}^{n}$. Assume to know classically $p,a\in\\{0,1\\}^{n}$ with
$0\leq a,x<p$. Also, assume we have access to the following subroutines:

  * •

$\mathsf{Q_{SUB}(a)}$ be a quantum circuit that performs a constant quantum
subtraction using $s_{\mathsf{SUB}}$ ancillas, and $r_{\mathsf{SUB}}$
$\mathsf{Tof}$ gates;

  * •

$\mathsf{C\text{-}Q_{ADD}}(p)$ be a quantum circuit that performs a
(controlled) addition by a constant $p$ using $s_{\mathsf{C\text{-}ADD}}$
ancillas, and $r_{\mathsf{C\text{-}ADD}}$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{Q_{COMP}}(a)$ be a classical comparator using $s_{\mathsf{COMP}}$
ancillas, $r_{\mathsf{COMP}}$ $\mathsf{Tof}$ gates.

Then, there is a circuit $\mathsf{Q_{MODADD_{p}}}(a)$ implementing quantum
modular addition by a constant as per definition 3.12 using
$r=\left(r_{\mathsf{{SUB}}}+r_{\mathsf{{C\text{-}ADD}}}+\left(r_{\mathsf{{COMP}}}/2\right)\right)$
$\mathsf{Tof}$ gates in expectation and
$s=1+\max(s_{\mathsf{SUB}},s_{\mathsf{C\text{-}ADD}},s_{\mathsf{COMP}})$
ancillas.

###### Proof.

As seen in the Takashi constant modular adder (proposition 3.15), the first
two subroutines perform the following mapping

$\displaystyle\ket{0}_{s}\ket{x}_{n}\xmapsto{\mathsf{Q_{SUB}}(a),\mathsf{C\text{-}Q_{ADD}}(p)}$
$\displaystyle\ket{0}_{s-1}\ket{x}_{n}\ket{x+a\mathbin{\;\mathrm{mod}\;}p}_{n}\ket{\mathbf{1}[x+a<p]}_{1}~{}.$

The comparator qubit storing $\ket{\mathbf{1}[x+a<p]}_{1}$ is finally supposed
to be uncomputed using $\mathsf{Q_{COMP}}(a)$ and a NOT gate. We can apply the
MBU lemma here on the comparator qubit and the uncomputation subroutine
$\mathsf{Q_{COMP}}(a)$, thus halving the cost of $\mathsf{Q_{COMP}}(a)$ in
expectation. Therefore, we finally get a cost of
$r=\left(r_{\mathsf{{SUB}}}+r_{\mathsf{{C\text{-}ADD}}}+\left(r_{\mathsf{{COMP}}}/2\right)\right)$
$\mathsf{Tof}$ gates in expectation, and the same ancilla count at proposition
3.15. ∎

###  4.4 Controlled modular addition by a constant

######  Theorem 4.12 (MBU controlled modular adder by a constant - VBE
architecture).

Let

  * •

$\mathsf{C\text{-}Q_{ADD}(a)}$ be a quantum circuit that performs a controlled
addition by a constant using $s_{\mathsf{C\text{-}ADD}}$ ancillas, and
$r_{\mathsf{C\text{-}ADD}}$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{Q_{COMP}}(p)$ be a quantum comparator using $s_{\mathsf{COMP}}$
ancillas, $r_{\mathsf{COMP}}$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{C\text{-}Q_{SUB}}(p)$ be a quantum circuit that performs a
(controlled) subtraction by a constant $p$ using $s_{\mathsf{C\text{-}SUB}}$
ancillas, and $r_{\mathsf{C\text{-}SUB}}$ $\mathsf{Tof}$ gates;

  * •

$\mathsf{C\text{-}Q_{COMP}^{\prime}}(a)$: be a controlled constant quantum
comparator using ($s_{\mathsf{C\text{-}COMP}}^{\prime}$ ancillas,
$r_{\mathsf{C\text{-}COMP}}^{\prime}$ $\mathsf{Tof}$ gates).

There is a circuit $\mathsf{C\text{-}Q_{MODADD_{p}}}(a)$ implementing an
$n$-bit controlled quantum modular addition by a constant as per definition
3.16 using
$r=\left(r_{\mathsf{{C\text{-}ADD}}}+r_{\mathsf{{COMP}}}+r_{\mathsf{{C\text{-}SUB}}}+\left(r_{\mathsf{{C\text{-}COMP}}}^{\prime}/2\right)\right)$
$\mathsf{Tof}$ gates and
$s=2+\max(s_{\mathsf{C\text{-}ADD}},s_{\mathsf{COMP}},n+s_{\mathsf{C\text{-}SUB}},s_{\mathsf{C\text{-}COMP}}^{\prime})$
ancillas.

###### Proof.

As seen in the controlled modular adder by a constant in VBE architecture
(proposition 3.18), the first three subroutines perform the following mapping

$\displaystyle\ket{0}_{s}\ket{c}_{1}\ket{x}_{n}\xmapsto{\mathsf{C\text{-}Q_{ADD}}(a),\mathsf{Q_{COMP}}(p),\mathsf{C\text{-}Q_{SUB}}(p)}\ket{0}_{s-1}\ket{c}_{1}\ket{x}_{n}\ket{x+c\cdot
a\mathbin{\;\mathrm{mod}\;}p}_{n}\ket{\mathbf{1}[x+c\cdot a\geq p]}_{1}~{}.$

The comparator qubit storing $\ket{\mathbf{1}[x+c\cdot a\geq p]}_{1}$ is
finally supposed to be uncomputed using
$\mathsf{C\text{-}Q_{COMP}^{\prime}}(a)$. We can apply the MBU lemma here on
the comparator qubit and the uncomputation subroutine
$\mathsf{C\text{-}Q_{COMP}^{\prime}}(a)$, thus halving the cost of
$\mathsf{C\text{-}Q_{COMP}^{\prime}}(a)$ in expectation. Therefore, we finally
get a cost of
$r=\left(r_{\mathsf{{C\text{-}ADD}}}+r_{\mathsf{{COMP}}}+r_{\mathsf{{C\text{-}SUB}}}+\left(r_{\mathsf{{C\text{-}COMP}}}^{\prime}/2\right)\right)$
$\mathsf{Tof}$ gates in expectation, and the same ancilla count at proposition
3.18. ∎

###  4.5 Two-sided comparison

The following result (stating directly the complexity with and without using
MBU) checks if a register $\ket{x}$ has a value in the range specified by two
other quantum registers $\ket{y}$ and $\ket{z}$. Compared to a non-MBU
implementation, we save $25\%$ for the $\mathsf{Tof}$ gate cost.

######  Theorem 4.13 (Two-sided comparator).

Let $x,y,z\in\\{0,1\\}^{n}$, and $t\in\\{0,1\\}$ Let us assume we have access
to $\mathsf{Q_{COMP}}$, with

$\ket{x}_{n}\ket{y}_{n}\ket{t}_{1}\xmapsto{\mathsf{Q_{COMP}}}\ket{x}_{n}\ket{y}_{n}\ket{t\oplus\mathbf{1}[x<y]}_{1}$

using $s_{\mathsf{COMP}}$ ancillas and $r_{\mathsf{COMP}}$ $\mathsf{Tof}$
gates. Let us assume we also have access to
$\mathsf{C\text{-}Q^{\prime}_{COMP}}$, with

$\ket{c}_{1}\ket{x}_{n}\ket{y}_{n}\ket{t}_{1}\xmapsto{\mathsf{C\text{-}Q^{\prime}_{COMP}}}\ket{c}_{1}\ket{x}_{n}\ket{y}_{n}\ket{t\oplus
c\cdot\mathbf{1}[x<y]}_{1}$

using $s^{\prime}_{\mathsf{C\text{-}COMP}}$ ancillas and
$r^{\prime}_{\mathsf{C\text{-}COMP}}$ $\mathsf{Tof}$ gates. Then, there is a
circuit that performs the operation $\mathsf{Q_{IN\\_RANGE}}$

$\ket{x}_{n}\ket{y}_{n}\ket{z}_{n}\ket{t}_{1}\xmapsto{\mathsf{Q_{IN\\_RANGE}}}\ket{x}_{n}\ket{y}_{n}\ket{z}_{n}\ket{t\oplus\mathbf{1}[x\in(y,z)]}_{1}$

using $s=1+s_{\mathsf{COMP}}$ ancillas and
$r=1.5r_{\mathsf{COMP}}+r^{\prime}_{\mathsf{C\text{-}COMP}}$ $\mathsf{Tof}$
gates.

###### Proof.

We begin by first checking if $y<x$

$\displaystyle\ket{0}_{s}\ket{x}_{n}\ket{y}_{n}\ket{z}_{n}\ket{t}_{1}\xmapsto{\mathsf{Q_{COMP}}}$
$\displaystyle\ket{0}_{s-1}\ket{x}_{n}\ket{y}_{n}\ket{z}_{n}\ket{\mathbf{1}[y<x]}\ket{t}_{1}$