QUANTUM NETWORKS FOR ELEMENTARY ARITHMETIC OPERATIONS

Quantum computers require quantum arithmetic. We provide an explicit c onstruction of quantum networks effecting basic arithmetic operations: from addition to modular exponentiation. Quantum modular exponentiati on seems to be the most difficult (time and space consuming) part of S hor'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.