Re: How long IF IT IS A DRAW?

From: Keith Ramsay (kramsay_at_aol.com)
Date: 09/20/04 

Date: 19 Sep 2004 22:01:12 -0700

Guy Macon <http://www.guymacon.com> wrote in message news:<10kpflogk4fqe44@news.supernews.com>...
[...]
| Let's guess that it will take our quantum computer one second to
| search one node. That's 10 in 2 seconds, 100 in 3 seconds, 1000
| in 4 seconds, 10,000 in 5 seconds, 100,000 in 6 seconds, and
| 10^60 in a minute. Not enough? Take two minutes and search
| 10^120 positions. or take all day and search 10^86400 positions.

You're reasoning as though your quantum computer was able to search an
exponentially growing number of nodes, and there's no reason to think
that this would be possible.

There is a sense in which a quantum computer with N qubits is able
to "do 2^N things at once". But probably not in the sense of being
able to do in one step or in N steps any task that a classical
computer can do in 2^N steps.

The things for which we have a quantum algorithm that would in
principle run quickly, but where we don't have a classical algorithm
that also would run quickly, all have special properties that finding
the optimum move in a game doesn't have. You can't simply farm out
portions of the problem to parallel universes; the result has to be
obtained by interference effects, in which the quantum amplitudes for
answers you don't want get phase cancellation, and the amplitude for
the answer you do want gets reinforced.

For the problem of factoring an integer we have a scheme for doing
this, and also for performing a search in a list. But the kind of
tree search needed to determine the best move in a game of perfect
information is a PSPACE complete problem, meaning that any problem
that can be solved with storage space bounded by some polynomial
in the length of the description of the problem, can be reduced
(within time bounded by a polynomial in the length of the problem)
to a problem of determining the best move in a game of perfect
information of this kind.

We know that anything that can be solved by a quantum computer in
polynomial time lies in PSPACE. A quantum computer can be simulated
by a classical computer in a polynomially limited space, by computing
amplitudes and adding them up. But there's no reason to think that
the class QP of problems that can be solved by a quantum computer in
polynomial time is anything like as broad a class as PSPACE.
 
Here's what David Deutsch says on his page
http://www.qubit.org/people/david/Articles/Frontiers.html
about the idea of being able to use a quantum speedup for searching
the chess tree:

#This was a bad example. Scott Aaronson at UC Berkeley has since
#drawn my attention to some comments by Richard Cleve
#(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 no special reason to expect
#better quantum chess algorithms to exist.

I would be rather surprised if reason to expect superior quantum
chess algorithms had emerged in the past few years.

Keith Ramsay

Relevant Pages

  • Re: Quantum computer using using artificial atoms.
    ... "Surrogate Factoring" is Snake Fur. ... > If quantum computers can work, then there are algorithms that can do ... There have been other mechanical factoring ideas. ... > What a quantum computer can do, a gp computer with the appropriate ...
    (sci.crypt)
  • Re: Quantum Computer Algorithms
    ... A quantum computer is similar, except that it can do a couple of extra ... A "nondeterministic Turing machine" and a "quantum computer" ... The difference is that while a nondeterministic Turing machine is a totally ... Just as nondeterministic algorithms are sequences of operations that can be ...
    (sci.physics.research)
  • Re: Quantum Computer Algorithms
    ... A quantum computer is similar, except that it can do a couple of extra ... A "nondeterministic Turing machine" and a "quantum computer" ... The difference is that while a nondeterministic Turing machine is a totally ... Just as nondeterministic algorithms are sequences of operations that can be ...
    (sci.physics.relativity)
  • Quantum algorithms and complexity of computation
    ... Keith Ramsay wrote: ... > | Let's guess that it will take our quantum computer one second to ... > exponentially growing number of nodes, and there's no reason to think ... > #algorithms altogether, ...
    (sci.math)
  • Re: Re: programming bomb-testing experiment on a regular computer
    ... you need a quantum computer. ... Everything is beyond YOUR capability, as you are so fond of showing ... and unless you can give some specific reason why it would ... variation in result, and then somehow make the signal have less ...
    (talk.origins)