References

1

Adriano Barenco, David Deutsch, and Artur Ekert. Conditional quantum dynamics and logic gates. Physical Review Letters, 74:4083-4086, 1995.

2

P. Benioff. Quantum mechanical hamiltonian models of Turing machines. J. Stat. Phys., 29:515-546, 1982.

3

Charles H. Bennett. Quantum cryptography: Uncertainty in the service of privacy. Science, 257:752-753, 1992.

4

Ethan Bernstein and Umesh Vazirani. Quantum complexity theory. In Proc. 25th ACM Symp. on Theory of Computation, pages 11-20, 1993.

5

Andre Berthiaume, David Deutsch, and Richard Jozsa. The stabilization of quantum computations. In Proc. of the Workshop on Physics and Computation (PhysComp94), pages 60-62, Los Alamitos, CA, 1994. IEEE Press.

6

Vladimir Cerny. Quantum computers and intractable (NP-complete) computing problems. Physical Review A, 48:116-119, 1993.

7

Peter Cheeseman, Bob Kanefsky, and William M. Taylor. Where the really hard problems are. In J. Mylopoulos and R. Reiter, editors, Proceedings of IJCAI91, pages 331-337, San Mateo, CA, 1991. Morgan Kaufmann.

8

I. L. Chuang, R. Laflamme, P. W. Shor, and W. H. Zurek. Quantum computers, factoring and decoherence. Science, 270:1633-1635, 1995.

9

J. I. Cirac and P. Zoller. Quantum computations with cold trapped ions. Physical Review Letters, 74:4091-4094, 1995.

10

James M. Crawford and Larry D. Auton. Experimental results on the cross-over point in satisfiability problems. In Proc. of the 11th Natl. Conf. on Artificial Intelligence (AAAI93), pages 21-27, Menlo Park, CA, 1993. AAAI Press.

11

D. Deutsch. Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. R. Soc. London A, 400:97-117, 1985.

12

D. Deutsch. Quantum computational networks. Proc. R. Soc. Lond., A425:73-90, 1989.

13

P. A. M. Dirac. The Principles of Quantum Mechanics. Oxford, 4th edition, 1958.

14

David P. DiVincenzo. Quantum computation. Science, 270:255-261, 1995.

15

David P. DiVincenzo and John Smolin. Results on two-bit gate design for quantum computers. In Proc. of the Workshop on Physics and Computation (PhysComp94), pages 14-23, Los Alamitos, CA, 1994. IEEE Press.

16

K. Eric Drexler. Nanosystems: Molecular Machinery, Manufacturing, and Computation. John Wiley, NY, 1992.

17

D. M. Eigler and E. K. Schweizer. Positioning single atoms with a scanning tunnelling microscope. Nature, 344:524-526, 1990.

18

Artur Ekert and Richard Jozsa. Shor's quantum algorithm for factorising numbers. Rev. Mod. Phys., 1995. to appear.

19

R. P. Feynman. Quantum mechanical computers. Foundations of Physics, 16:507-531, 1986.

20

Richard P. Feynman. QED: The Strange Theory of Light and Matter. Princeton Univ. Press, NJ, 1985.

21

Eugene C. Freuder and Richard J. Wallace. Partial constraint satisfaction. Artificial Intelligence, 58:21-70, 1992.

22

M. R. Garey and D. S. Johnson. A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, 1979.

23

Ian P. Gent and Toby Walsh. The TSP phase transition. Technical Report 95-178, Dept. of Computer Science, Univ. of Strathclyde, April 1995.

24

G. H. Golub and C. F. Van Loan. Matrix Computations. John Hopkins University Press, Baltimore, MD, 1983.

25

Tad Hogg. Phase transitions in constraint satisfaction search. A World Wide Web page with URL ftp://parcftp.xerox.com/pub/dynamics/constraints.html, 1994.

26

Tad Hogg. Refining the phase transitions in combinatorial search. Artificial Intelligence, 81:127-154, 1996.

27

Tad Hogg, Bernardo A. Huberman, and Colin Williams. Phase transitions and the search problem. Artificial Intelligence, 81:1-15, 1996.

28

Tad Hogg and Colin P. Williams. The hardest constraint problems: A double phase transition. Artificial Intelligence, 69:359-377, 1994.

29

Richard Jozsa. Computation and quantum superposition. In Proc. of the Physics of Computation Workshop. IEEE Computer Society, October 2-4 1992.

30

Samuel Karlin and Howard M. Taylor. A First Course in Stochastic Processes. Academic Press, NY, 2nd edition, 1975.

31

Don Kimber. An introduction to quantum computation. Technical report, Xerox PARC, February 1992.

32

S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220:671-680, 1983.

33

Rolf Landauer. Information is physical. Physics Today, 44(5):23-29, May 1991.

34

Rolf Landauer. Is quantum mechanically coherent computation useful? In D. H. Feng and B-L. Hu, editors, Proc. of the Drexel-4 Symposium on Quantum Nonintegrability. International Press, 1994.

35

Seth Lloyd. A potentially realizable quantum computer. Science, 261:1569-1571, 1993.

36

Seth Lloyd. Quantum-mechanical computers. Scientific American, 273(4):140-145, October 1995.

37

Alan Mackworth. Constraint satisfaction. In S. Shapiro, editor, Encyclopedia of Artificial Intelligence, pages 285-293. Wiley, 1992.

38

Norman Margolus. Parallel quantum computation. In W. H. Zurek, editor, Complexity, Entropy and the Physics of Information, pages 273-287. Addison-Wesley, New York, 1990.

39

Steven Minton, Mark D. Johnston, Andrew B. Philips, and Philip Laird. Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems. Artificial Intelligence, 58:161-205, 1992.

40

David Mitchell, Bart Selman, and Hector Levesque. Hard and easy distributions of SAT problems. In Proc. of the 10th Natl. Conf. on Artificial Intelligence (AAAI92), pages 459-465, Menlo Park, 1992. AAAI Press.

41

Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

42

Wolfgang T. Muller, David L. Klein, Thomas Lee, John Clarke, Paul L. McEuen, and Peter G. Schultz. A strategy for the chemical synthesis of nanostructures. Science, 268:272-273, 1995.

43

Joseph C. Pemberton and Weixiong Zhang. Epsilon-transformation: Exploiting phase transitions to solve combinatorial optimization problems. Artificial Intelligence, 81:297-325, 1996.

44

Patrick Prosser. An empirical study of phase transitions in binary constraint satisfaction problems. Artificial Intelligence, 81:81-109, 1996.

45

Robert Schrag and James Crawford. Implicates and prime implicates in random 3-SAT. Artificial Intelligence, 81:199-222, 1996.

46

Bart Selman, Hector Levesque, and David Mitchell. A new method for solving hard satisfiability problems. In Proc. of the 10th Natl. Conf. on Artificial Intelligence (AAAI92), pages 440-446, Menlo Park, CA, 1992. AAAI Press.

47

T. C. Shen, C. Wang, G. C. Abeln, J. R. Tucker, J. W. Lyding, Ph. Avouris, and R. E. Walkup. Atomic-scale desorption through electronic and vibrational excitation mechanisms. Science, 268:1590-1592, 1995.

48

Peter W. Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In S. Goldwasser, editor, Proc. of the 35th Symposium on Foundations of Computer Science, pages 124-134. IEEE Press, November 1994.

49

Tycho Sleator and Harald Weinfurter. Realizable universal quantum logic gates. Physical Review Letters, 74:4087-4090, 1995.

50

Barbara M. Smith and Martin E. Dyer. Locating the phase transition in binary constraint satisfaction problems. Artificial Intelligence, 81:155-181, 1996.

51

K. Svozil. Quantum computation and complexity theory I. Bulletin of the European Association of Theoretical Computer Sciences, 55:170-207, 1995.

52

W. G. Unruh. Maintaining coherence in quantum computers. Physical Review A, 41:992, 1995.

53

Colin P. Williams and Tad Hogg. Exploiting the deep structure of constraint problems. Artificial Intelligence, 70:73-117, 1994.

54

Stephen Wolfram. Mathematica: A System for Doing Mathematics by Computer. Addison-Wesley, NY, 2nd edition, 1991.

55

Weixiong Zhang and Richard E. Korf. A unified view of complexity transitions on the travelling salesman problem. Artificial Intelligence, 81:223-239, 1996.

56

Langchi Zhu, Valeria Kleiman, Xiaonong Li, Shao Ping Lu, Karen Trentelman, and Robert J. Gordon. Coherent laser control of the product distribution obtained in the photoexcitation of HI. Science, 270:77-80, 1995.