Can Schrodinger's Cat Factor Numbers?

Suppose we wish to factor a 500-bit number N (assumed to be a product 
of 2 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?


Postscript: The little note above, posted on the physics and math internet 
newsgroups on 19 February 1994, is rather out of date but, in view of 
subsequent events, it provides an interesting example of how some ideas 
are "in the air" at certain times. Apparently the field of "quantum 
computing" really came to life around May of 1994 when Peter Shor 
circulated a pre-print of a paper about factoring large integers by 
exploiting a superposition of quantum states. (The paper was first formally
presented at a seminar in November 1994 and published in early 1995.) In a 
review of the history of quantum computing, Daniel Gottesman describes the 
impact of Shor's paper this way:

  "The history of the study of quantum information can be divided 
   into three eras. In the earliest, 'Pre-Shor', era (before 1994), 
   quantum computation was an obscure field, of interest only to a 
   few people. The years 0-3 Post-Shor (1994-1997) were marked by 
   explosive growth in the community and rapid scientic progress, 
   including the discovery of Shor’s and Grover’s algorithms, the 
   invention of quantum error correction and fault-tolerant quantum
   computation, and breakthroughs in quantum cryptography and the 
   experimental realization of quantum computers."

In a brief history of quantum computing, Jacob West wrote:

  "Feynman was among the first to produce an abstract model in 1982 
   that showed how a quantum system could be used to do computations...
   Later, in 1985, Deutsch realized that Feynman's assertion could 
   eventually lead to a general purpose quantum computer and published 
   a crucial theoretical paper showing that any physical process, in 
   principle, could be modeled perfectly by a quantum computer... After 
   Deutsch published this paper, the search began to find interesting 
   applications for such a machine.  Unfortunately, all that could be 
   found were a few rather contrived mathematical problems, until Shor 
   circulated in 1994 a preprint of a paper in which he set out a method
   for using quantum computers to crack an important problem in number 
   theory, namely factorization.  He showed how an ensemble of 
   mathematical operations, designed specifically for a quantum computer,
   could be organized to enable such a machine to factor huge numbers 
   extremely rapidly, much faster than is possible on conventional 
   computers.  With this breakthrough, quantum computing transformed 
   from a mere academic curiosity directly into a national and world 
   interest."

  "Early investigators in this field were naturally excited by the 
   potential of such immense computing power, and soon after realizing
   its potential, the hunt was on to find something interesting for a 
   quantum computer to do. Peter Shor, a research and computer scientist
   at AT&T's Bell Laboratories in New Jersey, provided such an application
   by devising the first quantum computer algorithm.  Shor's algorithm 
   harnesses the power of quantum superposition to rapidly factor very 
   large numbers (on the order ~10200 digits and greater) in a matter 
   of seconds."

It seems that my little note on whether Schrodinger's Cat can factor numbers
appeared on the internet just prior to the explosion of interest and activity
in this topic. It would be interesting to know what other precursors appeared 
in public at around that time.

Despite the (albeit remote) possibility that my little note might have 
prompted some of the activity in this field, I must admit that I've always 
been skeptical about whether quantum superpositions could really be used
to solve otherwise computationally intractible problems. I have the
vague sense that there is some principle analogous to the second law
of thermodynamics that would make such things impossible. All the schemes
I've seen for performing quantum computation remind me very much of
descriptions of Maxwell's Demon, examining his surroundings and making
informed choices to preferentially filter certain physical processes,
thereby violating the second law. It's possible to describe very plausible-
sounding demons, and even to construct extremely simple "working models"
of them, but there are always obstacles (not always trivial to identify)
that interfere (so to speak) with turning them into practical devices.
As I understand it, some researchers recently succeeded in using billions
of carefully controlled molecules to infer that 15 is the product of 3
and 5. It will be interesting to see if this leads to techniques for
actually solving realistic problems.

Another related coincidence is that I posted an message on the internet
in early 1995 describing a method of factoring the integer N based on the
Fourier analysis of a sequence 1, b, b^2, b^3, ... modulo N. At the time
I was unaware that this algorithm was already known, and coincidentally it
forms the basis of Shor's quantum factoring algorithm. We might almost say
these ingredients existed in "superposition" in the minds of several 
different people at the same time. Ironically, the only follow-up comment
my message received was from someone saying it was a useless idea.

By the way, while searching the internet archives to find the original date
of my post on quantum factoring, I noticed there had been a few follow-up
messages back in February of 1994. John Baez pointed out the 1985 paper 
by Deutsch. Paul Reiser posted a reply to me, saying

  "I think your understanding of the wave function is not right. 
   The fact 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."

This led a few other people to say that the states could actually "be there"
if one subscribes to the many-worlds interpretation. I replied on Feb 21:

'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 who responded.'