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

EFFICIENT QUANTUM CIRCUITS FOR ARITHMETIC OPERATIONS AND THEIR APPLICATIONS

Yasuhiro Takahashi

Published Mar 24, 2008• 0 citations
OpenAlex

Abstract

This thesis focuses on constructing efficient quantum circuits for arithmetic operationsand applying them to Shor’s factoring algorithm to answer the question: Whatwould be sufficient computational resources for a quantum computer to be able toperform Shor’s factoring algorithm for a large input number? The answers to theproblem would contribute to our understanding of the computational power of smallquantum circuits such as logarithmic-depth quantum circuits. Moreover, the answerswould be useful for analyzing the detailed relationships between the computationalpower of a quantum computer and the security of cryptosystems and for designinga new cryptosystem that is secure against a quantum computer. First, I constructa linear-size quantum circuit for addition with no ancillary qubits. This is an affirmativeanswer to Cuccaro et al.’s question. Then, using the circuit, I construct alogarithmic-depth quantum circuit for addition with few qubits and apply it to constructingan O(n2 log n)-depth O(n3 log n)-size quantum circuit for Shor’s algorithmwith 2n+O(n/ log n) qubits, where n is the length of the number to be factored. Thenumber of qubits is less than that in any other O(n2 log n)-depth quantum circuit everconstructed for Shor’s algorithm. Then, I construct a quantum circuit for comparisonwith uninitialized ancillary qubits and apply it to constructing an O(n3)-depthO(n3 log n)-size quantum circuit for Shor’s algorithm with 2n+2 qubits. The numberof qubits is less than that in any other quantum circuit ever constructed for Shor’salgorithm. Lastly, on a linear nearest neighbor architecture, I construct a small-sizequantum circuit for the quantum Fourier transform and apply it to constructing anO(n3)-depth O(n3 log n)-size quantum circuit for Shor’s algorithm with 2n+4 qubits.The size is less than that of any other quantum circuit ever constructed for Shor’salgorithm on a linear nearest neighbor architecture.

Related papers

Quantum Arithmetic Circuits: A Survey

Yasuhiro Takahashi

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.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2009•34 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•36 citations

A quantum circuit for Shor's factoring algorithm using 2n+2 qubits

Yu Takahashi, Noboru Kunihiro

We construct a quantum circuit for Shor's factoring algorithm that uses 2n+2 qubits, where n is the length of the number to be factored. The depth and size of the circuit are O(n^3) and O(n^3\log n), respectively. The number of qubits used in the circuit is less than that in any other quantum circuit ever constructed for Shor's factoring algorithm. Moreover, the size of the circuit is about half the size of Beauregard's quantum circuit for Shor's factoring algorithm, which uses 2n+3 qubits.

Quantum Information and Computation•Mar 1, 2006•49 citations

A fast quantum circuit for addition with few qubits

Yasuhiro Takahashi, Noboru Kunihiro

We show how to construct a fast quantum circuit for computing the sum of two $n$-bit binary numbers with few qubits. The constructed circuit uses $O(n/\log n)$ ancillary qubits and its depth and size are $O(\log n)$ and $O(n)$, respectively. The number of ancillary qubits is asymptotically less than that in Draper et al.'s quantum carry-lookahead adder, and the depth and size are asymptotically the same as those of Draper et al.'s. Moreover, we show that the circuit is useful for constructing an efficient quantum circuit for Shor's factoring algorithm.

Quantum Information and Computation•Jul 1, 2008•44 citations

Quantum addition circuits and unbounded fan-out

Yasuhiro Takahashi, Seiichiro Tani, Noboru Kunihiro

We first show how to construct an $O(n)$-depth $O(n)$-size quantum circuit for addition of two $n$-bit binary numbers with no ancillary qubits. The exact size is $7n-6$, which is smaller than that of any other quantum circuit ever constructed for addition with no ancillary qubits. Using the circuit, we then propose a method for constructing an $O(d(n))$-depth $O(n)$-size quantum circuit for addition with $O(n/d(n))$ ancillary qubits for any $d(n) = \Omega(\log n)$. If we are allowed to use unbounded fan-out gates with length $O(n^{\varepsilon})$ for an arbitrary small positive constant $\varepsilon$, we can modify the method and construct an $O(e(n))$-depth $O(n)$-size circuit with $o(n)$ ancillary qubits for any $e(n) = \Omega(\log^* n)$. In particular, these methods yield efficient circuits with depth $O(\log n)$ and with depth $O(\log^* n)$, respectively. We apply our circuits to constructing efficient quantum circuits for Shor's discrete logarithm algorithm.

arXiv:0910.2530•Quantum Information and Computation•Sep 1, 2010•174 citations

Low-depth quantum architectures for factoring

Aram W. Harrow, Paul Pham

Quantum computing is a new field which combines computer science and quantum physics. Its most famous result, Shor's factoring algorithm, would enable us to one day compromise the widely-used RSA cryptosystem if we are able to design efficient quantum architectures. Studying the depth of these architectures would allow us to solve this human problem within a human lifetime. Toward that end, we contribute two hybrid factoring architectures in poly-logarithmic and sub-logarithmic depths, which are both exponential improvements over previous known works. We also present an improved procedure for generating quantum Fourier states useful for quantum compiling. Finally, we invent a new circuit resource called coherence which upper bounds the error-correcting effort needed in a future quantum computer. We use this to characterize a better time-space tradeoff for factoring as well as to provide configurable-depth factoring architectures.

•Jan 1, 2013•0 citations
This thesis focuses on constructing efficient quantum circuits for arithmetic operationsand applying them to Shor’s factoring algorithm to answer the question: Whatwould be sufficient computational resources for a quantum computer to be able toperform Shor’s factoring algorithm for a large input number? The answers to theproblem would contribute to our understanding of the computational power of smallquantum circuits such as logarithmic-depth quantum circuits. Moreover, the answerswould be useful for analyzing the detailed relationships between the computationalpower of a quantum computer and the security of cryptosystems and for designinga new cryptosystem that is secure against a quantum computer. First, I constructa linear-size quantum circuit for addition with no ancillary qubits. This is an affirmativeanswer to Cuccaro et al.’s question. Then, using the circuit, I construct alogarithmic-depth quantum circuit for addition with few qubits and apply it to constructingan O(n2 log n)-depth O(n3 log n)-size quantum circuit for Shor’s algorithmwith 2n+O(n/ log n) qubits, where n is the length of the number to be factored. Thenumber of qubits is less than that in any other O(n2 log n)-depth quantum circuit everconstructed for Shor’s algorithm. Then, I construct a quantum circuit for comparisonwith uninitialized ancillary qubits and apply it to constructing an O(n3)-depthO(n3 log n)-size quantum circuit for Shor’s algorithm with 2n+2 qubits. The numberof qubits is less than that in any other quantum circuit ever constructed for Shor’salgorithm. Lastly, on a linear nearest neighbor architecture, I construct a small-sizequantum circuit for the quantum Fourier transform and apply it to constructing anO(n3)-depth O(n3 log n)-size quantum circuit for Shor’s algorithm with 2n+4 qubits.The size is less than that of any other quantum circuit ever constructed for Shor’salgorithm on a linear nearest neighbor architecture.
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.
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.
We construct a quantum circuit for Shor's factoring algorithm that uses 2n+2 qubits, where n is the length of the number to be factored. The depth and size of the circuit are O(n^3) and O(n^3\log n), respectively. The number of qubits used in the circuit is less than that in any other quantum circuit ever constructed for Shor's factoring algorithm. Moreover, the size of the circuit is about half the size of Beauregard's quantum circuit for Shor's factoring algorithm, which uses 2n+3 qubits.
We show how to construct a fast quantum circuit for computing the sum of two nnn-bit binary numbers with few qubits. The constructed circuit uses O(n/log⁡n)O(n/\log n)O(n/logn) ancillary qubits and its depth and size are O(log⁡n)O(\log n)O(logn) and O(n)O(n)O(n), respectively. The number of ancillary qubits is asymptotically less than that in Draper et al.'s quantum carry-lookahead adder, and the depth and size are asymptotically the same as those of Draper et al.'s. Moreover, we show that the circuit is useful for constructing an efficient quantum circuit for Shor's factoring algorithm.
We first show how to construct an O(n)O(n)O(n)-depth O(n)O(n)O(n)-size quantum circuit for addition of two nnn-bit binary numbers with no ancillary qubits. The exact size is 7n−67n-67n−6, which is smaller than that of any other quantum circuit ever constructed for addition with no ancillary qubits. Using the circuit, we then propose a method for constructing an O(d(n))O(d(n))O(d(n))-depth O(n)O(n)O(n)-size quantum circuit for addition with O(n/d(n))O(n/d(n))O(n/d(n)) ancillary qubits for any d(n)=Ω(log⁡n)d(n) = \Omega(\log n)d(n)=Ω(logn). If we are allowed to use unbounded fan-out gates with length O(nε)O(n^{\varepsilon})O(nε) for an arbitrary small positive constant ε\varepsilonε, we can modify the method and construct an O(e(n))O(e(n))O(e(n))-depth O(n)O(n)O(n)-size circuit with o(n)o(n)o(n) ancillary qubits for any e(n)=Ω(log⁡∗n)e(n) = \Omega(\log^* n)e(n)=Ω(log∗n). In particular, these methods yield efficient circuits with depth O(log⁡n)O(\log n)O(logn) and with depth O(log⁡∗n)O(\log^* n)O(log∗n), respectively. We apply our circuits to constructing efficient quantum circuits for Shor's discrete logarithm algorithm.
Quantum computing is a new field which combines computer science and quantum physics. Its most famous result, Shor's factoring algorithm, would enable us to one day compromise the widely-used RSA cryptosystem if we are able to design efficient quantum architectures. Studying the depth of these architectures would allow us to solve this human problem within a human lifetime. Toward that end, we contribute two hybrid factoring architectures in poly-logarithmic and sub-logarithmic depths, which are both exponential improvements over previous known works. We also present an improved procedure for generating quantum Fourier states useful for quantum compiling. Finally, we invent a new circuit resource called coherence which upper bounds the error-correcting effort needed in a future quantum computer. We use this to characterize a better time-space tradeoff for factoring as well as to provide configurable-depth factoring architectures.