From: Eliezer S. Yudkowsky (sentience@pobox.com)
Date: Mon Sep 14 1998 - 12:30:40 MDT
Michael Nielsen wrote:
>
> Unfortunately, a no-go theorem of Bennett, Bernstein, Brassard and
> Vazirani shows that this is not possible in general. Generally, their
> lower bound shows that a quantum computer needs to access the list
> ~sqrt(2^n) times. Better than the classical result by a quadratic factor,
> but not an exponential improvement.
How is "quantum computer" being defined in this instance? Can this quantum
computer simulate physical reality in polynomial time?
Let's say that we send a a photon through a single half-silvered mirror and
then recombine the path, then send the twin ghost-photons down a series of 32
levels of half-silvered mirrors, sending the superimposed pair to 4 billion
destinations. One of these destinations contains a half-silvered-mirror setup
that synchronizes the two phases, and all the others contain a
half-silvered-mirror setup that causes the two eigenstates to cancel out. At
measurement, the photon appears in the unique destination. It seems to me
that this physical search will cover 2^n physical targets in O(n) time.
--
sentience@pobox.com Eliezer S. Yudkowsky
http://pobox.com/~sentience/AI_design.temp.html
http://pobox.com/~sentience/sing_analysis.html
Disclaimer: Unless otherwise specified, I'm not telling you
everything I think I know.
This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 14:49:34 MST