\begin{thebibliography}{10}

\bibitem{barenco95}
Adriano Barenco, David Deutsch, and Artur Ekert.
\newblock Conditional quantum dynamics and logic gates.
\newblock {\em Physical Review Letters}, 74:4083--4086, 1995.

\bibitem{benioff82}
P.~Benioff.
\newblock Quantum mechanical hamiltonian models of {Turing} machines.
\newblock {\em J. Stat. Phys.}, 29:515--546, 1982.

\bibitem{bennett92}
Charles~H. Bennett.
\newblock Quantum cryptography: Uncertainty in the service of privacy.
\newblock {\em Science}, 257:752--753, 1992.

\bibitem{bernstein92}
Ethan Bernstein and Umesh Vazirani.
\newblock Quantum complexity theory.
\newblock In {\em Proc. 25th ACM Symp. on Theory of Computation}, pages 11--20,
  1993.

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

\bibitem{cerny93}
Vladimir Cerny.
\newblock Quantum computers and intractable ({NP}-complete) computing problems.
\newblock {\em Physical Review A}, 48:116--119, 1993.

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

\bibitem{chuang95}
I.~L. Chuang, R.~Laflamme, P.~W. Shor, and W.~H. Zurek.
\newblock Quantum computers, factoring and decoherence.
\newblock {\em Science}, 270:1633--1635, 1995.

\bibitem{cirac95}
J.~I. Cirac and P.~Zoller.
\newblock Quantum computations with cold trapped ions.
\newblock {\em Physical Review Letters}, 74:4091--4094, 1995.

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

\bibitem{deutsch85}
D.~Deutsch.
\newblock Quantum theory, the {Church-Turing} principle and the universal
  quantum computer.
\newblock {\em Proc. R. Soc. London A}, 400:97--117, 1985.

\bibitem{deutsch89}
D.~Deutsch.
\newblock Quantum computational networks.
\newblock {\em Proc. R. Soc. Lond.}, A425:73--90, 1989.

\bibitem{dirac58}
P.~A.~M. Dirac.
\newblock {\em The Principles of Quantum Mechanics}.
\newblock Oxford, 4th edition, 1958.

\bibitem{divincenzo95}
David~P. DiVincenzo.
\newblock Quantum computation.
\newblock {\em Science}, 270:255--261, 1995.

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

\bibitem{drexler92}
K.~Eric Drexler.
\newblock {\em Nanosystems: Molecular Machinery, Manufacturing, and
  Computation}.
\newblock John Wiley, NY, 1992.

\bibitem{eigler90}
D.~M. Eigler and E.~K. Schweizer.
\newblock Positioning single atoms with a scanning tunnelling microscope.
\newblock {\em Nature}, 344:524--526, 1990.

\bibitem{ekert95}
Artur Ekert and Richard Jozsa.
\newblock Shor's quantum algorithm for factorising numbers.
\newblock {\em Rev. Mod. Phys.}, 1995.
\newblock to appear.

\bibitem{feynman86}
R.~P. Feynman.
\newblock Quantum mechanical computers.
\newblock {\em Foundations of Physics}, 16:507--531, 1986.

\bibitem{feynman85}
Richard~P. Feynman.
\newblock {\em {QED}: The Strange Theory of Light and Matter}.
\newblock Princeton Univ. Press, NJ, 1985.

\bibitem{freuder92}
Eugene~C. Freuder and Richard~J. Wallace.
\newblock Partial constraint satisfaction.
\newblock {\em Artificial Intelligence}, 58:21--70, 1992.

\bibitem{garey79}
M.~R. Garey and D.~S. Johnson.
\newblock {\em A Guide to the Theory of NP-Completeness}.
\newblock W. H. Freeman, San Francisco, 1979.

\bibitem{gent95b}
Ian~P. Gent and Toby Walsh.
\newblock The {TSP} phase transition.
\newblock Technical Report 95-178, Dept. of Computer Science, Univ. of
  Strathclyde, April 1995.

\bibitem{golub83}
G.~H. Golub and C.~F.~Van Loan.
\newblock {\em Matrix Computations}.
\newblock John Hopkins University Press, Baltimore, MD, 1983.

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

\bibitem{hogg95b}
Tad Hogg.
\newblock Refining the phase transitions in combinatorial search.
\newblock {\em Artificial Intelligence}, 81:127--154, 1996.

\bibitem{hogg95e}
Tad Hogg, Bernardo~A. Huberman, and Colin Williams.
\newblock Phase transitions and the search problem.
\newblock {\em Artificial Intelligence}, 81:1--15, 1996.

\bibitem{hogg94a}
Tad Hogg and Colin~P. Williams.
\newblock The hardest constraint problems: A double phase transition.
\newblock {\em Artificial Intelligence}, 69:359--377, 1994.

\bibitem{jozsa92}
Richard Jozsa.
\newblock Computation and quantum superposition.
\newblock In {\em Proc. of the Physics of Computation Workshop}. IEEE Computer
  Society, October 2-4 1992.

\bibitem{karlin75}
Samuel Karlin and Howard~M. Taylor.
\newblock {\em A First Course in Stochastic Processes}.
\newblock Academic Press, NY, 2nd edition, 1975.

\bibitem{kimber92}
Don Kimber.
\newblock An introduction to quantum computation.
\newblock Technical report, Xerox PARC, February 1992.

\bibitem{kirkpatrick83}
S.~Kirkpatrick, C.~D. Gelatt, and M.~P. Vecchi.
\newblock Optimization by simulated annealing.
\newblock {\em Science}, 220:671--680, 1983.

\bibitem{landauer91}
Rolf Landauer.
\newblock Information is physical.
\newblock {\em Physics Today}, 44(5):23--29, May 1991.

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

\bibitem{lloyd93}
Seth Lloyd.
\newblock A potentially realizable quantum computer.
\newblock {\em Science}, 261:1569--1571, 1993.

\bibitem{lloyd95}
Seth Lloyd.
\newblock Quantum-mechanical computers.
\newblock {\em Scientific American}, 273(4):140--145, October 1995.

\bibitem{mackworth92}
Alan Mackworth.
\newblock Constraint satisfaction.
\newblock In S.~Shapiro, editor, {\em Encyclopedia of Artificial Intelligence},
  pages 285--293. Wiley, 1992.

\bibitem{margolus90}
Norman Margolus.
\newblock Parallel quantum computation.
\newblock In W.~H. Zurek, editor, {\em Complexity, Entropy and the Physics of
  Information}, pages 273--287. Addison-Wesley, New York, 1990.

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

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

\bibitem{motwani95}
Rajeev Motwani and Prabhakar Raghavan.
\newblock {\em Randomized Algorithms}.
\newblock Cambridge University Press, 1995.

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

\bibitem{pemberton95}
Joseph~C. Pemberton and Weixiong Zhang.
\newblock Epsilon-transformation: Exploiting phase transitions to solve
  combinatorial optimization problems.
\newblock {\em Artificial Intelligence}, 81:297--325, 1996.

\bibitem{prosser95}
Patrick Prosser.
\newblock An empirical study of phase transitions in binary constraint
  satisfaction problems.
\newblock {\em Artificial Intelligence}, 81:81--109, 1996.

\bibitem{schrag95}
Robert Schrag and James Crawford.
\newblock Implicates and prime implicates in random {3-SAT}.
\newblock {\em Artificial Intelligence}, 81:199--222, 1996.

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

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

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

\bibitem{sleator95}
Tycho Sleator and Harald Weinfurter.
\newblock Realizable universal quantum logic gates.
\newblock {\em Physical Review Letters}, 74:4087--4090, 1995.

\bibitem{smith95}
Barbara~M. Smith and Martin~E. Dyer.
\newblock Locating the phase transition in binary constraint satisfaction
  problems.
\newblock {\em Artificial Intelligence}, 81:155--181, 1996.

\bibitem{svozil94b}
K.~Svozil.
\newblock Quantum computation and complexity theory {I}.
\newblock {\em Bulletin of the European Association of Theoretical Computer
  Sciences}, 55:170--207, 1995.

\bibitem{unruh94}
W.~G. Unruh.
\newblock Maintaining coherence in quantum computers.
\newblock {\em Physical Review A}, 41:992, 1995.

\bibitem{williams92}
Colin~P. Williams and Tad Hogg.
\newblock Exploiting the deep structure of constraint problems.
\newblock {\em Artificial Intelligence}, 70:73--117, 1994.

\bibitem{wolfram91}
Stephen Wolfram.
\newblock {\em Mathematica: A System for Doing Mathematics by Computer}.
\newblock Addison-Wesley, NY, 2nd edition, 1991.

\bibitem{zhang95}
Weixiong Zhang and Richard~E. Korf.
\newblock A unified view of complexity transitions on the travelling salesman
  problem.
\newblock {\em Artificial Intelligence}, 81:223--239, 1996.

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

\end{thebibliography}
