fwd: Quantum chess-playing algorithms? Probably not.

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