Quantum networks for elementary arithmetic operations

TLDR

Quantum computers rely on quantum arithmetic, with modular exponentiation being the most resource‑intensive component of Shor’s algorithm. The paper presents an explicit construction of quantum networks that perform basic arithmetic operations, ranging from addition to modular exponentiation. The authors design quantum circuits that implement these operations reversibly, enabling efficient arithmetic. They find that the auxiliary memory needed for reversible modular exponentiation scales linearly with the number’s size. © 1996 The American Physical Society.

Abstract

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.