Can Schrodinger's Cat Factor Numbers?
Kevin Brown
large primes). We construct a hard-wired division circuit that outputs
the remainder R of N when divided by an input D. We know that if N is
composite then it has a divisor of 250 bits or less, so our circuit only
needs to handle 250-bit inputs.
If we flip a fair coin 250 times and use the results to set the input bits,
then the probability of finding a factor is roughly 1/(2^250). This is just
equivalent to randomly guessing a number between 1 and sqrt(N). Not very
efficient.
But suppose we perform 250 "Schrodinger's Cat" experiments in a giant sealed
room, and connect the results to the inputs of our division circuit (which
is also contained in the sealed room). Now instead of a 1/(2^250) chance
that the remainder is zero, quantum theory tells us that the remainder
(from our perspective outside the sealed room) is the linear superposition
of all 2^250 possible outcomes, one of which is R=0.
I suppose as soon as we observe the result, it takes on just one of the
2^250 possible outcomes, and the probability of the outcome R=0 is just
1/(2^250), so nothing has been gained.
But the idea that, in the unobserved room, the R=0 condition is actually
THERE seems very tantalizing. Is it conceivable that some sort of feedback
amplification could be used to enhance the R=0 outcome? We know that
seemingly mutually exclusive outcomes of quantum processes can actually
interfere with each other, as in the "two-slit experiments". Could we
similarly detect interference effects of the R=0 outcome on the other
possible outcomes?
I assume this question has been throughly studied, but I couldn't find an
answer in the sci.physics or sci.math FAQs. I suspect that there is no way
to extract the R=0 outcome from all the others at a rate higher than
1/(2^250), but I'm not sure. Can someone enlighten me?
SJ. Brewster
possibility, though I can't remember the details: someone on
rec.arts.sf.written might know.
--
Steve.B...@Bristol.ac.uk
./;'./../';./.'././;.';./.;'/../.;.'/.;'/.';.'.';./';./.;'/.'/..'./;';/.
.;'.'.;'/.';//';'/';/''/./'..';'/'./';/.'/;';'/;'/;/'/./.;'/;'.//..';'.;
./;/';//.';'./'.'/;'/./;';.'//''@/;'/.';@'/.;/'/';/';'/'/;';';.../;;;;;'
././.;/;/''/././.;/';'';;'/././;'/;'./;'./;'./;'.'./';/'./';'/./;;';'.//
(ASCII random dot stereogram courtesy of the rtfm.mit.edu archive. Stare
at the @'s and relax your eyes.)
Trevor Blackwell
> But suppose we perform 250 "Schrodinger's Cat" experiments in a giant sealed
> room, and connect the results to the inputs of our division circuit (which
> is also contained in the sealed room). Now instead of a 1/(2^250) chance
> that the remainder is zero, quantum theory tells us that the remainder
> (from our perspective outside the sealed room) is the linear superposition
> of all 2^250 possible outcomes, one of which is R=0.
> I suppose as soon as we observe the result, it takes on just one of the
> 2^250 possible outcomes, and the probability of the outcome R=0 is just
> 1/(2^250), so nothing has been gained.
> But the idea that, in the unobserved room, the R=0 condition is actually
> THERE seems very tantalizing. Is it conceivable that some sort of feedback
> amplification could be used to enhance the R=0 outcome? We know that
> seemingly mutually exclusive outcomes of quantum processes can actually
> interfere with each other, as in the "two-slit experiments". Could we
> similarly detect interference effects of the R=0 outcome on the other
> possible outcomes?
In fact, you can factor numbers this way, if you become "Schrodinger's
Experimenter". You arrange for the 250 experiments to be done, and the
binary representation is tested to be a factor. If it is not a factor,
a cynanide capsule is released and you die.
Any findings you report will definitely be that you found a factor.
--
--
Trevor Blackwell t...@das.harvard.edu (617) 495-8912
(info and words of wit in my .plan)
Disavowal: My opinions.
SUSIM Project
that the wave function of the 250 Schroedinger's Cats is a superposition
of states does not mean that the R=0 outcome is "THERE". It only means
that the probability of it being measured to be "THERE" is 1 in 2^250.
There's a big difference. - Paul Reiser -
Larry Edwards
Actually I thought that there was an interpretation (the "many worlds"
interpretation) which basically says that the r=0 outcome is "there" along
with all the others. Well this is totally outside my field so I probably am
wrong, but that was my impression.
Larry Edwards
john baez
>Actually I thought that there was an interpretation (the "many worlds"
>interpretation) which basically says that the r=0 outcome is "there" along
>with all the others. Well this is totally outside my field so I probably am
>wrong, but that was my impression.
You're basically right, but rather than sinking into the metaphysical
quagmire of what "there" means, we can stick with the practical question
of whether one can use quantum mechanics to build machines that do
better at solving NP problems than regular computers can, at least on
average. There has been research on this and David Deutsch is the one
most famous for studying it.
Quantum theory: the Church-Turing principle and
the universal quantum computer. _Proc. Roy. Soc._
A, 400: 97-117 (1985)
Quantum Theory as a Universal Physical Theory,
_Int. J. Theoretical Phys._ 24: 1-41 (1985)
However, some of his ideas have been seriously contested and I don't
have references to the whole debate.
SUSIM Project
the different worlds are not "connected" and can't be amplified. At least
thats what I think it would say. The many worlds interpretation is an
attempt to clarify a situation in which the wave function is assumed to
be "real" instead of a bookkeeping method of organizing physical results
and predictions. (Which is what it really is, which is why the many-
worlds interpretation is wrong) (in my opinion) - Paul Reiser -
Roger Firestone
The "many worlds" interpretation of quantum mechanics has so far never
been shown to have any observable difference from the "one world"
interpretation (outside of science fiction stories, of which there
have been several inventive examples). Even if multiple worlds are
splitting off all the time, we seem to go on living in only one of
them, with no communication among the others. When the quantum wave
function collapses, we never measure anything that would distinguish
the two cases. I'd pin my hopes for factorization on my old
acquaintance in Georgia, rather than on 250 cats...
--
The Next Challenge - Public Access Unix in Northern Va. - Washington D.C.
703-803-0391 To log in for trial and account info.
Kevin Brown
PR> superposition of states does not mean that the R=0 outcome is "THERE".
PR> It only means that the probability of it being measured to be "THERE"
PR> is 1 in 2^250.
I think there is reality in the superposition of states, regardless of
whether one subscribes to the "many worlds" interpretation (about which I'm
agnostic). For example, in the two-slit experiment we observe results that
indicate actual interference between the two possible "events", i.e., the
photon passing through the left slit or passing through the right slit.
The actual state is evidently a linear superposition of what we would
classically regard as separate and mutually exclusive "realistic events",
provided that our interaction with the process does not distinguish between
these two events.
The point is that we can interact with a quantum process in such a way that
the result is influenced by more than one of the possible "realistic events"
leading up to the measured outcome. (If this were not the case, there
would be nothing "un-classical" about quantum physics.)
The question is whether it is possible to contrive a measurement or
interaction with the 250 cats such that the outcome is influenced by the
"realistic event" R=0 and its associated trial divisor. Clearly we would
have to be more clever than just checking to see if R=0. As I said in my
original post, a direct observation of the outcome would presumably have
only 1/2^250 chance of being R=0, just as a direct observation of the
two-slit experiment would give just a probability of 1/2 that the photon
passed through the left slit.
But if we repeatedly fire photons through the slits, and restrict our
interaction to just the collector screen behind the slits, we find a pattern
of interference that reveals the superimposed wave functions. The purpose
of my post was to ask if it might be possible to produce an analagous
interference effect between the 2^250 possible "realistic events" of the
250-cat experiment, and thereby derive some information about the divisor.
Thanks to all those who responded, particularly for the references.
Scott Coon
I'm tempted to ask for more specifics about _why_ you think this "is what it
really is", but I'll just mention that David Deutsch has an interesting article
in _Quantum Concepts in Space and Time_ (editors: Penrose & Isham; Oxford
University Press, 1986) where he discusses reasons for believing in the
many-worlds interpretation and outlines an experiment (not, of course, one we
can do right now :) ) that would conclusively demonstrate whether it was
correct. He also has quite a bit to say about just how "connected" the
universes are.
Scott Coon
co...@math.uiuc.edu
note followup line