Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences

Quantum Arithmetic Circuits: A Survey

Yasuhiro Takahashi

Published Jan 1, 2009• 35 citations
Publisher

Abstract

Quantum circuits for elementary arithmetic operations are important not only for implementing Shor's factoring algorithm on a quantum computer but also for understanding the computational power of small quantum circuits, such as linear-size or logarithmic-depth quantum circuits. This paper surveys some recent approaches to constructing efficient quantum circuits for elementary arithmetic operations and their applications to Shor's factoring algorithm. It covers addition, comparison, and the quantum Fourier transform used for addition.

DOI
10.1587/transfun.e92.a.1276

Related papers

Quantum networks for elementary arithmetic operations

Vlatko Vedral, Adriano Barenco, ARTUR K. EKERT

Quantum computers require quantum arithmetic. We provide an explicit construction of quantum networks effecting basic arithmetic operations: from addition to modular exponentiation. Quantum modular exponentiation seems to be the most difficult (time and space consuming) part of Shor's quantum factorizing algorithm. We show that the auxiliary memory required to perform this operation in a reversible way grows linearly with the size of the number to be factorized. \textcopyright{} 1996 The American Physical Society.

arXiv:quant-ph/9511018•Physical Review A•Jul 1, 1996•811 citations

Circuit for Shor's algorithm using 2n+3 qubits

Stéphane Beauregard

We try to minimize the number of qubits needed to factor an integer of n bits using Shor's algorithm on a quantum computer. We introduce a circuit which uses 2n+3 qubits and O(n^3 lg(n)) elementary quantum gates in a depth of O(n^3) to implement the factorization algorithm. The circuit is computable in polynomial time on a classical computer and is completely general as it does not rely on any property of the number to be factored. Keywords: Factorization, quantum circuits, modular arithmetics

arXiv:quant-ph/0205095•May 15, 2002•18 citations

The quantum Fourier transform on a linear nearest neighbor architecture

Yasuhiro Takahashi, Noboru Kunihiro, Kazuo Ohta

We show how to construct an efficient quantum circuit for computing a good approximation of the quantum Fourier transform on a linear nearest neighbor architecture. The constructed circuit uses no ancillary qubits and its depth and size are $O(n)$ and $O(n\log n)$, respectively, where $n$ is the length of the input. The circuit is useful for decreasing the size of Fowler et al.'s quantum circuit for Shor's factoring algorithm on a linear nearest neighbor architecture.

Quantum Information and Computation•May 1, 2007•37 citations

A comprehensive study of quantum arithmetic circuits

Siyi Wang, Xiufan Li, Wei Lee +3 more

In recent decades, the field of quantum computing has experienced remarkable progress. This progress is marked by the superior performance of many quantum algorithms compared with their classical counterparts, with Shor's algorithm serving as a prominent illustration. Quantum arithmetic circuits, which are the fundamental building blocks in numerous quantum algorithms, have attracted much attention. Despite extensive exploration of various designs in the existing literature, researchers remain keen to develop novel designs and improve existing ones. In this review article, we aim to provide a systematically organized and easily comprehensible overview of the current state of the art in quantum arithmetic circuits. Specifically, this study covers fundamental operations such as addition, subtraction, multiplication, division and modular exponentiation. We delve into the detailed quantum implementations of these prominent designs and evaluate their efficiency considering various objectives. We also discuss potential applications of the presented arithmetic circuits and suggest future research directions.This article is part of the theme issue 'Emerging technologies for future secure computing platforms'.

arXiv:2406.03867•Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences•Jan 16, 2025•11 citations

Quantum Arithmetic on Galois Fields

Stéphane Beauregard, Gilles Brassard A, José M. Fernandez

In this paper we discuss the problem of performing elementary finite field arithmetic on a quantum computer. Of particular interest, is the controlled-multiplication operation, which is the only group-specific operation in Shor's algorithms for factoring and solving the Discrete Log Problem. We describe how to build quantum circuits for performing this operation on the generic Galois fields GF($p^k$), as well as the boundary cases GF($p$) and GF($2^k$). We give the detailed size, width and depth complexity of such circuits, which ultimately will allow us to obtain detailed upper bounds on the amount of quantum resources needed to solve instances of the DLP on such fields.

arXiv:quant-ph/0301163•Jan 29, 2003•18 citations

Quantum-Fourier-transform-based quantum arithmetic with qudits

Archimedes Pavlidis, Emmanuel G. Floratos

We present some basic integer arithmetic quantum circuits, such as adders and multiplier-accumulators of various forms, which operate on multilevel qudits. The integers to be processed are represented in an alternative basis after they have been Fourier transformed. Several arithmetic circuits operating on Fourier-transformed integers have appeared in the literature for two-level qubits. Here we extend these techniques to multilevel qudits, as they may offer some advantages relative to qubit implementations. The arithmetic circuits presented here can be used as basic building blocks for higher level algorithms such as quantum phase estimation, quantum simulation, quantum optimization, etc. Detailed decomposition is given down to elementary two-level single- and two-qudit gates as such gates are the most appropriate for physical implementation. A complexity analysis is given after this decomposition step and it is shown that the depth of the circuits is linear in the number of qudits employed and quadratic in the dimension of each qudit while their quantum cost is quadratic in the number of the qudits and quadratic in the dimension.

arXiv:1707.08834•Physical Review A•Mar 16, 2021•46 citations
Quantum circuits for elementary arithmetic operations are important not only for implementing Shor's factoring algorithm on a quantum computer but also for understanding the computational power of small quantum circuits, such as linear-size or logarithmic-depth quantum circuits. This paper surveys some recent approaches to constructing efficient quantum circuits for elementary arithmetic operations and their applications to Shor's factoring algorithm. It covers addition, comparison, and the quantum Fourier transform used for addition.
Quantum computers require quantum arithmetic. We provide an explicit construction of quantum networks effecting basic arithmetic operations: from addition to modular exponentiation. Quantum modular exponentiation seems to be the most difficult (time and space consuming) part of Shor's quantum factorizing algorithm. We show that the auxiliary memory required to perform this operation in a reversible way grows linearly with the size of the number to be factorized. \textcopyright{} 1996 The American Physical Society.
We try to minimize the number of qubits needed to factor an integer of n bits using Shor's algorithm on a quantum computer. We introduce a circuit which uses 2n+3 qubits and O(n^3 lg(n)) elementary quantum gates in a depth of O(n^3) to implement the factorization algorithm. The circuit is computable in polynomial time on a classical computer and is completely general as it does not rely on any property of the number to be factored. Keywords: Factorization, quantum circuits, modular arithmetics
We show how to construct an efficient quantum circuit for computing a good approximation of the quantum Fourier transform on a linear nearest neighbor architecture. The constructed circuit uses no ancillary qubits and its depth and size are O(n)O(n)O(n) and O(nlog⁡n)O(n\log n)O(nlogn), respectively, where nnn is the length of the input. The circuit is useful for decreasing the size of Fowler et al.'s quantum circuit for Shor's factoring algorithm on a linear nearest neighbor architecture.
In recent decades, the field of quantum computing has experienced remarkable progress. This progress is marked by the superior performance of many quantum algorithms compared with their classical counterparts, with Shor's algorithm serving as a prominent illustration. Quantum arithmetic circuits, which are the fundamental building blocks in numerous quantum algorithms, have attracted much attention. Despite extensive exploration of various designs in the existing literature, researchers remain keen to develop novel designs and improve existing ones. In this review article, we aim to provide a systematically organized and easily comprehensible overview of the current state of the art in quantum arithmetic circuits. Specifically, this study covers fundamental operations such as addition, subtraction, multiplication, division and modular exponentiation. We delve into the detailed quantum implementations of these prominent designs and evaluate their efficiency considering various objectives. We also discuss potential applications of the presented arithmetic circuits and suggest future research directions.This article is part of the theme issue 'Emerging technologies for future secure computing platforms'.
In this paper we discuss the problem of performing elementary finite field arithmetic on a quantum computer. Of particular interest, is the controlled-multiplication operation, which is the only group-specific operation in Shor's algorithms for factoring and solving the Discrete Log Problem. We describe how to build quantum circuits for performing this operation on the generic Galois fields GF(pkp^kpk), as well as the boundary cases GF(ppp) and GF(2k2^k2k). We give the detailed size, width and depth complexity of such circuits, which ultimately will allow us to obtain detailed upper bounds on the amount of quantum resources needed to solve instances of the DLP on such fields.
We present some basic integer arithmetic quantum circuits, such as adders and multiplier-accumulators of various forms, which operate on multilevel qudits. The integers to be processed are represented in an alternative basis after they have been Fourier transformed. Several arithmetic circuits operating on Fourier-transformed integers have appeared in the literature for two-level qubits. Here we extend these techniques to multilevel qudits, as they may offer some advantages relative to qubit implementations. The arithmetic circuits presented here can be used as basic building blocks for higher level algorithms such as quantum phase estimation, quantum simulation, quantum optimization, etc. Detailed decomposition is given down to elementary two-level single- and two-qudit gates as such gates are the most appropriate for physical implementation. A complexity analysis is given after this decomposition step and it is shown that the depth of the circuits is linear in the number of qudits employed and quadratic in the dimension of each qudit while their quantum cost is quadratic in the number of the qudits and quadratic in the dimension.