Quantum Arithmetic

From Qwiki

The field of quantum arithmetic is the study of algorithms for performing arithmetic operations on quantum computers. Existing algorithms all work on qubits, although there is no particular reason why algorithms for qutrits or qudits would be harder to develop. Almost all of the existing algorithms (with the notable exception of the Draper Fourier-based adder) are direct, reversible analogs of known, classical Boolean algorithms, derived from integer addition.

There are numerous forms of integer adder circuits, with different total computational complexity, different circuit depth (time performance), and different communication requirements, which will result in widely varying performance on various quantum computer architectures. Many of these circuits have not been analyzed for particular architectures. Some circuits add a classical number to a quantum register which may already hold a superposition of values.

References

This (roughly chronological) list of quantum arithmetic papers is nearly comprehensive, and should be kept up to date as new papers are published, as long as the field remains small enough for that to be practical. Most of these papers are available on the arXiv, and most have been published in an archival journal or conference proceedings; the latter forms are generally preferred as they often differ from the arXiv form.

Richard P. Feynman, Feynman Lectures on Computation, pp. 189--190 has a description of a full adder using Toffoli gates, 1996.
Vlatko Vedral, Adriano Barenco and Artur Ekert, Quantum networks for elementary arithmetic operations, PRA 54, 147 (1996)
David Beckman and Amalavoyal N. Chari and Srikrishna Devabhaktuni and John Preskill, Efficient networks for quantum factoring, PRA 54, 1034 (1996)
Miquel, C. and Paz, J.P. and Perazzo, R., Factoring in a dissipative quantum computer, PRA 54, 2605 (1996)
Christof Zalka, Fast versions of Shor's quantum factoring algorithm, arXiv:9806084 (1998)
Phil Gossett, Quantum Carry-Save Arithmetic, arXiv:quant-ph/9808061 (1998)
Thomas G. Draper, Addition on a quantum computer, arXiv:quant-ph/0008033 (2000)
K. V. R. M. Murali and Neeraj Sinha and T. S. Mahesh and Malcom H. Levitt and K. V. Ramanathan and Anil Kumar, Quantum information processing by nuclear magnetic resonance: Experimental implementation of half-adder and subtractor operations using an oriented spin-7/2 system, PRA 66, 022313 (2002)
Austin G. Fowler and Simon J. Devitt and Lloyd C. Hollenberg, Implementation of Shor's algorithm on a linear nearest neighbor qubit array, QIC 4, 237 (2004)
Steve A. Cuccaro and Thomas G. Draper and Samuel A. Kutin and David Petrie Moulton, A new quantum ripple-carry addition circuit, arXiv:quant-ph/0410184 (2004)
Rodney Van Meter and Kohei M. Itoh, Fast Quantum Modular Exponentiation, PRA 71, 052320 (2005)
Yasuhiro Takahashi and Noboru Kunihiro, A linear-size quantum circuit for addition with no ancillary qubits, QIC 5(6), 440 (2005)
Dmitri Maslov and G. W. Dueck and D. M. Miller, Quantum circuit simplification and level compaction, arXiv:quant-ph/0604001
Thomas G. Draper and Samuel A. Kutin and Eric M. Rains and Krysta M. Svore, A Logarithmic-Depth Quantum Carry-Lookahead Adder, QIC 6, 351 (2006)
Rodney Van Meter and W. J. Munro and Kae Nemoto and Kohei M. Itoh, Distributed Arithmetic on a Quantum Multicomputer, Proc. Int. Symp. on Computer Architecture (ISCA) (2006)
Rodney Van Meter and W. J. Munro and Kae Nemoto and Kohei M. Itoh, Arithmetic on a Distributed-Memory Quantum Multicomputer, ACM J. Emerging Tech. in Computing Systems, to appear; arXiv:quant-ph/0607160 (2006)
Christof Zalka, Shor's Algorithm with Fewer (Pure) Qubits, arXiv:quant-ph/0601097 (2006)
Yasuhiro Takahashi and Noboru Kunihiro, A quantum circuit for Shor's algorithm using 2n + 2 qubits, QIC 6, 184 (2006)
Samuel A. Kutin, Shor's algorithm on a nearest-neighbor machine, arXiv:quant-ph/0609001

Additionally, work on classical, reversible circuits is definitely relevant.

W. C. Athas and L. J. Svensson, Reversible Logic Issues in Adiabatic CMOS, Proc. IEEE 1994 Workshop on Physics and Computing (1994)
J. W. Bruce and M. A. Thornton and L. Shivakumaraiah and P. S. Kokate and X. Li, Efficient adder circuits based on a conservative reversible logic gate, Proc. IEEE Computer Society Annual Symposium on VLSI (2002)

Finally, a recommended text on digital arithmetic.