Re: How fast will a quantum computer be?
Thu, 24 Sep 1998 13:56:48 -0700

--On Thursday, September 24, 1998, 7:02 PM +0200 "Anders Sandberg" <> wrote:

> Hal Finney <> writes:

>> A problem like you are describing can be thought of as a search problem.
>> You want to search through a list of candidate values for one which
>> satisfies a certain criterion (in this case, being a CAD specification
>> of a spaceship, etc.).

> ...
>> In your case, if your classical computer would take 2 to the power of
>> 1 billion possibilities to calculate, the quantum computer would
>> take the square root of that, which means halving the exponent.  This
>> is 2 to the power of 500 million possibilities.

> Of course, now we are talking about a brute force quantum search. What
> would be interesting to think of is quantum genetic algorithms or
> other methods that make use of the redundancies in the problem.

Yes, and there is another way to reduce the problem search space too that I was thinking of, which is to test not every single possible sequence of 0s and 1s as a file, but to use a language of command statements, or something. I'm not sure how to put it, it's easier to understand in language... suppose you wanted to write a book in this fashion, by generating random sequences of letters and looking at every single possibility you come up with, and returning the one that best fits the criteria of being "a good book". Rather then test every single sequence of letters, it would be more economical to test every possible seqeucne of english words. Of course the futher you go in this direction, the more you restrict youself. I may very well want a sequence in a book that says "So he took a peice of paper and scribbled the letters 'djfkl;jaffaff' across it, that was when I realized he was illiterate". An algorithm considering only english words would not be able to come up with that sentence. But anyway, a genetic algorithm would work a lot better you're right, and also some way to limit the results to legal code would speed it up.

> --
> -----------------------------------------------------------------------
> Anders Sandberg Towards Ascension!
> GCS/M/S/O d++ -p+ c++++ !l u+ e++ m++ s+/+ n--- h+/* f+ g+ w++ t+ r+ !y

Zeb Haradon
my web page: