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²⁵⁰. This is just equivalent to randomly guessing a number between 1 and the square root of N, which is obviously 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²⁵⁰ 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²⁵⁰ possible outcomes, one of which is R = 0. Of course, when we observe the result, it exhibits just one of the 2²⁵⁰ possible outcomes, and the probability of the outcome R = 0 is just 1/2²⁵⁰, so nothing has been gained.

However, 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 scientific 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.

Judging from this, it seems that my little note on whether Schrodinger's Cat can factor numbers appeared on the internet just about 3 months prior to the initial explosion of interest and activity in this topic. It would be interesting to know what other precursors appeared in public at around that time. I suppose it’s even conceivable that my little note prompted some of the activity in this field, especially since some of the individuals involved were also participants in the same internet newsgroups. (Regarding how long Shor worked on developing his algorithm, he recently recalled that "I thought about it on and off for maybe a year, and worked on it moderately hard for a month or two when I saw that it actually might work." Asked if he recalled the Feb 24 Usenet discussion of this subject, which was about three months before his preprint came out, he said “I did read newsgroups occasionally back then, but I don't recall that discussion at all, which probably means I missed it.”)

Having said that, I must admit that I've always been unsure about whether quantum superpositions could really be used to solve otherwise computationally intractable problems. I have the vague sense that there might be 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 scaling them up and turning them into practical devices. It will be interesting to see if this leads to techniques for actually solving realistic problems.

Another related coincidence is that I posted a 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², b³, ... 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 on my internet message describing this factoring method 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 Schrödinger’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²⁵⁰. 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²⁵⁰ 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 analogous interference effect between the 2²⁵⁰ possible "realistic events" of the 250-cat experiment, and thereby derive some information about the divisor.

Thanks to all who responded.

Return to MathPages Main Menu