References

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).