Quantum Arithmetic Circuits: A Survey

Yasuhiro TAKAHASHI

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E92-A    No.5    pp.1276-1283
Publication Date: 2009/05/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E92.A.1276
Print ISSN: 0916-8508
Type of Manuscript: Special Section INVITED PAPER (Special Section on Frontier of Quantum Computing)
Category: 
Keyword: 
quantum circuits,  elementary arithmetic operations,  Shor's factoring algorithm,  

Full Text: PDF(227.3KB)>>
Buy this Article



Summary: 
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.