**1**- P. W. Shor, in
*Proc. 35th Annual Symposium on the Foundations of Computer Science*, edited by S. Goldwasser (IEEE Computer Society Press, Los Alamitos, California, 1994), p. 124. **2**- A more technically detailed description of the Shor algorithm may be found in: A. Ekert and R. Jozsa, ``Shor's quantum algorithm for factorizing numbers,'' Rev. Mod. Phys. 1995, to appear.
**3**- A. M. Odlyzko, ``The future of integer factorization,'' AT&T Bell Laboratories preprint 1995.
**3'**- R. Rivest, A. Shamir and L. Adleman, ``On digital signatures and public-key cryptosystems,'' MIT Laboratory for Computer Science, preprint MIT/LCS/TR-212, 1979.
**4**- D. Atkins, M. Graff, A. K.
Lenstra and P. C. Leyland, in
*Advances in Cryptology - ASIACRYPT '94*, Eds. J. Pieprzyk and R. Safavi-Naini, Lecture Notes in Comp. Sci. 917 (Springer Verlag, Berlin, 1995), p. 263. **5**- D. P. DiVincenzo, presented at
*Quantum Computation 1994*, Villa Gualino, Turin, Italy, October 1994, unpublished. **6**- D. P. DiVincenzo, ``Quantum computation,'' Science, to appear 1995.
**7**- R. W. Keyes, IBM J. Res. Develop.
**32**, 24 (1988). **8**- The seminal paper in reversible computation:
R. Landauer, IBM J. Res. Develop.
**3**, 183 (1961). **9**- This paper describes the history of reversible
computation: C. H. Bennett, IBM J. Res. Develop.
**32**, 16 (1988). **10**- T. Toffoli, in
*Automata, Languages and Programming*, Eds. J. W. de Bakker and J. van Leeuwen (Springer-Verlag, New York, 1980) p. 632. **11**- E. Fredkin and T. Toffoli, Int. J. Theor. Phys.
**21**, 219 (1982). **12**- C. H. Bennett, IBM J. Res. Develop.
**17**, 525 (1973). **13**- C. H. Bennett, SIAM J. Comput.
**18**, 766 (1989). **14**- A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. Smolin and H. Weinfurter, ``Elementary gates for quantum computation,'' submitted to Phys. Rev. A 1995.
**15**- D. P. DiVincenzo, Phys. Rev. A
**51**, 1015 (1995). **16**- D. Deutsch, Proc. Roy. Soc. Lond. A
**425**, 73 (1989). **17**- A. Barenco, D. Deutsch and A. Ekert,
Phys. Rev. Lett.
**74**, 4083 (1995). **18**- T. Sleator and H. Weinfurter, Phys. Rev. Lett.
**74**, 4087 (1995). **19**- D. Deutsch, A. Barenco and A. Ekert, Proc. Roy.
Soc. Lond. A
**449**, 669 (1995). **20**- S. Lloyd, ``Almost any quantum logic gate is universal,'' Los Alamos National Laboratory preprint.
**21**- P. W. Shor, presented at
*Quantum Computation 1994*, Villa Gualino, Turin, Italy, October 1994, unpublished. **22**- D. P. DiVincenzo, private communication and work presented at
*Quantum Computation 1995*, Villa Gualino, Turin, Italy, June 1995, unpublished. **23**- D. Coppersmith, ``An approximate Fourier transform useful in quantum factoring,'' IBM Research Report RC19642 (1994).
**24**- R. Cleve, ``A note on computing Fourier transforms by quantum programs,'' unpublished.
**25**- In fact, we must be careful that the discrete Fourier
transform yields sufficient resolution to extract the multiple of
the inverse period from . This is always possible provided
the number of bits
**k**in the first quantum register satisfies . **26**- Since the period
**r**is not known beforehand, we require for the Fourier transform step to yield sufficient resolution [1,2]. **27**- I. L. Chuang, R. Laflamme, P. Shor and W. H. Zurek, ``Quantum computers, factoring and decoherence,'' Report LA-UR-95-241 (1995).
**28**- R. Jozsa, Proc. R. Soc. Lond. A
**435**, 563 (1991). **29**- D. Deutsch and R. Jozsa, Proc. R. Soc. Lond. A
**439**, 554 (1992). **30**- A. C.-C. Yao, ``Quantum circuit complexity,'' preprint.
**31**- C. H. Bennett, E. Bernstein, G. Brassard and U. V. Vazirani, ``Strengths and weaknesses of quantum computing,'' preprint.
**32**- W. G. Unruh, Phys. Rev. A
**51**, 992 (1995). **33**- S. Lloyd, Science
**261**, 1569 (1993). **34**- J. I. Cirac and P. Zoller, Phys. Rev. Lett.
**74**, 4091 (1995). **35**- T. Pellizzari, S. A. Gardiner, J. I. Cirac and P. Zoller, ``Decoherence, continuous observation and quantum computing: a cavity QED model,'' preprint.
**36**- Q. A. Turchette, C. J. Hood, W. Lange, H. Mabuchi and H. J. Kimble, ``Measurement of conditional phase shifts for quantum logic,'' Caltech preprint.
**37**- R. Hughes, presented at
*Quantum Computation 1995*, Villa Gualino, Turin, Italy, June 1995, unpublished. **38**- G. H. Hardy and E. M. Wright,
*An introduction to the theory of numbers*(Oxford, Clarendon Press, 1979).

Wed Aug 23 11:54:31 IDT 1995