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 and Rolf Landauer. The fundamental physical limits of computation. Scientific American, pages 48-56, July 1985.

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

Dik Bouwmeester et al. Experimental quantum teleportation. Nature, 390:575-579, 1997.

7

Michel Boyer, Gilles Brassard, Peter Hoyer, and Alain Tapp. Tight bounds on quantum searching. In T. Toffoli et al., editors, Proc. of the Workshop on Physics and Computation (PhysComp96), pages 36-43, Cambridge, MA, 1996. New England Complex Systems Institute.

8

Gilles Brassard, Peter Hoyer, and Alain Tapp. Quantum counting. Los Alamos preprint quant-ph/9805082, May 27 1998.

9

N. J. Cerf and S. E. Koonin. Monte Carlo simulation of quantum computation. In Proc. of IMACS Conf. on Monte Carlo Methods, 1997. Los Alamos preprint quant-ph/9703050.

10

Nicolas J. Cerf, Lov K. Grover, and Colin P. Williams. Nested quantum search and NP-complete problems. Los Alamos preprint quant-ph/9806078, June 23 1998.

11

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

12

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.

13

Isaac L. Chuang et al. Experimental realization of a quantum algorithm. Los Alamos preprint quant-ph/9801037, 1998.

14

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

15

David G. Cory, Amr F. Fahmy, and Timothy F. Havel. Nuclear magnetic resonance spectroscopy: An experimentally accessible paradigm for quantum computing. In T. Toffoli et al., editors, Proc. of the Workshop on Physics and Computation (PhysComp96), pages 87-91, Cambridge, MA, 1996. New England Complex Systems Institute.

16

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

17

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

18

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

19

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

20

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

21

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

22

Richard P. Feynman. Feynman Lectures on Computation. Addison-Wesley, Reading, MA, 1996.

23

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

24

Ian Gent. On the stupid algorithm for satisfiability. Technical Report APES-03-1998, Strathclyde University, 1998. Available at www.cs.strath.ac.uk/ apes/apereports.html.

25

Neil Gershenfeld, Isaac Chuang, and Seth Lloyd. Bulk quantum computation. In T. Toffoli et al., editors, Proc. of the Workshop on Physics and Computation (PhysComp96), page 134, Cambridge, MA, 1996. New England Complex Systems Institute.

26

Lov K. Grover. Quantum computers can search arbitrarily large databases by a single query. Los Alamos preprint quant-ph/9706005, Bell Labs, 1997.

27

Lov K. Grover. Quantum mechanics helps in searching for a needle in a haystack. Physical Review Letters, 78:325-328, 1997.

28

Serge Haroche and Jean-Michel Raimond. Quantum computing: Dream or nightmare? Physics Today, 49:51-52, August 1996.

29

Tad Hogg. Quantum computing and phase transitions in combinatorial search. J. of Artificial Intelligence Research, 4:91-128, 1996. Available online at http://www.jair.org/abstracts/hogg96a.html.

30

Tad Hogg. A framework for structured quantum search. Physica D, 120:102-116, 1998. Los Alamos preprint quant-ph/9701013.

31

Tad Hogg. Highly structured searches with quantum computers. Physical Review Letters, 80:2473-2476, 1998. Available online at http://publish.aps.org/eprint/gateway/eplist/aps1997oct30_002.

32

Tad Hogg, Bernardo A. Huberman, and Colin Williams. Phase transitions and the search problem. Artificial Intelligence, 81:1-15, 1996. See also http://www.parc.xerox.com/dynamics/www/specialIssueIntro.html.

33

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

34

Tad Hogg and Mehmet Yanik. Local search methods for quantum computers. Los Alamos preprint quant-ph/9802043, Xerox, 1998.

35

Peter Hoyer. Efficient quantum transforms. Los Alamos preprint quant-ph/9702028, February 1997.

36

Scott Kirkpatrick and Bart Selman. Critical behavior in the satisfiability of random boolean expressions. Science, 264:1297-1301, 1994.

37

A. Yu. Kitaev. Quantum measurements and the Abelian stabilizer problem. Los Alamos preprint quant-ph/9511026, November 20 1995.

38

Emanuel Knill, Raymond Laflamme, and Wojciech H. Zurek. Resilient quantum computation. Science, 279:342-345, 1998.

39

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, Boston, 1994. International Press.

40

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

41

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

42

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.

43

Remi Monasson and Riccardo Zecchina. The entropy of the k-satisfiability problem. Phys. Rev. Lett., 76:3881-3885, 1996.

44

Christopher Monroe and David Wineland. Future of quantum computing proves to be debatable. Physics Today, 49:107-108, November 1996.

45

A. Nijenhuis and H. S. Wilf. Combinatorial Algorithms for Computers and Calculators. Academic Press, New York, 2nd edition, 1978.

46

E. M. Palmer. Graphical Evolution: An Introduction to the Theory of Random Graphs. Wiley Interscience, NY, 1985.

47

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.

48

P. Shor. Scheme for reducing decoherence in quantum computer memory. Physical Review A, 52:2493-2496, 1995.

49

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, Los Alamitos, CA, November 1994. IEEE Press.

50

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

51

Barbara M. Terhal and John A. Smolin. Single quantum querying of a database. Los Alamos preprint quant-ph/9705041 v4, IBM, Nov. 14 1997.

52

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

53

Allen Van Gelder and Yumi K. Tsuji. Incomplete thoughts about incomplete satisfiability problems. In Proc. of 2nd DIMACS Challenge, 1993.

54

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