Quantum algorithms and complexity of computation

From: Theo van der Storm (thstorm_at_wanadoo.nl)
Date: 09/20/04 

Date: Mon, 20 Sep 2004 19:55:08 +0200

Keith Ramsay wrote:
> 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

Thank you for an excellent contribution to the discussion.
The level of optimism displayed in this group was running a bit out of
control, wasn´t it?

Theo

Relevant Pages

  • Re: How long IF IT IS A DRAW?
    ... You're reasoning as though your quantum computer was able to search an ... and there's no reason to think ... #algorithms altogether, ... chess algorithms had emerged in the past few years. ...
    (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)
  • 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.relativity)
  • 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)