From: Damien Broderick (d.broderick@english.unimelb.edu.au)
Date: Fri Dec 22 2000 - 04:51:26 MST
Quantum theorist David Deutsch
says in a recent e-list post:
========================================
I have recently been citing game-playing as a good application of Grover's
quantum search algorithm. Both in my *Frontiers* article and in the *Edge*
interview (see my web site, url below), I said that a
Grover's-algorithm-based quantum chess-playing program would "outclass" the
best existing players such as Deep Blue.
I was wrong. Scott Aaronson at UC Berkeley has drawn my attention to some
comments by Richard Cleve last year (in quant-ph/9906111) pointing out that
chess and chess-like games (with a fixed number of choices per move,
especially if this number is small) are not very suitable for speedup by
Grover searching. At best one would expect a speedup by a moderate, *fixed*
factor.
This does not rule out quantum chess-playing algorithms altogether, just
algorithms based on Grover-accelerated brute-force searching. But there is
now no special reason to expect better quantum chess algorithms to exist.
http://www.qubit.org/people/david/David.html
--------------------------------
I have a vague memory of some people here making this point a while back.
Damien Broderick
This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 15:32:31 MST