Read Factoring Humanity for Free Online

he’d learned that Heather was pregnant.
    “So,” Professor Papineau had said, “the interference patterns that result when a single photon passes through two slits might be proof of the existence of multiple universes. But what, you may ask, does this have to do with computing?” He beamed at his seminar students.
    “Well, remember our example of Kyle coming to work. In one universe, he walks around the east side of Queen’s Park; in the other, he walks around the west side. Now, Kyle, suppose your boss had asked you to solve two problems before you came into work, and—having never overcome your student ways—you’ve left them both to the last moment. There’s time to puzzle out the answer to just one of them in your head as you walk to work. Let’s say that if you went down the west side, you’d spend your time solving problem A, and if you went down the east side, you’d spend your time solving problem B. Is there any way without slowing down or taking the journey around the Parliament Buildings twice that by the time you got to work, you’d have the answers to both problems?”
    Kyle was sure he’d had a blank expression.
    “Anyone?” asked Papineau, bushy eyebrows raised.
    “I’m surprised you think Graves would come up with even one answer,” said D’Annunzio.
    Snickers from several students. Papineau smiled.
    “Well, there is a way,” said the professor. “You know the old saying, ‘Two heads are better than one’? Well, if our Kyle—the one from this universe who went down the west side and who solved problem A—could join back up with the other Kyle—the one from the parallel universe who went down the east side and solved problem B—then he’d have both answers.”
    A hand went up.
    “Glenda?”
    “But when talking about the photon and the slits, you said the only way the two universes could rejoin is if there was no way to tell which slit the photon had taken in each universe.”
    “Exactly. But if we could devise a method by which it made no difference whatsoever which way Kyle went in this universe—indeed, a method by which Kyle himself didn’t know which way he had gone, and no one saw him during his journey— then, at the end of it all, the two universes might stitch back together. But in the rejoined universe, Kyle would know the answer to both problems, even though he’d really only had time to solve one of them.”
    Papineau grinned at the class.
    “Welcome,” he said, “to the world of quantum computing.” He paused. “Of course, there were really more than two possible universes for Kyle—he could have stayed home, he could have driven to work, he could have taken a cab. Likewise, it’s possible to envision the lightbulb experiment with dozens or even hundreds of slits. Well, suppose each of the photons coming off the lightbulb represented a single bit of information. Remember, all computing is done with glorified abacuses; we actually move things around in order to compute, whether it’s pebbles or atoms or electrons or photons. But if each of those things could simultaneously be in multiple places at once, across parallel universes, extraordinarily complex computing problems could be solved very, very quickly.
    “Consider, for instance, the factoring of numbers. How do we do that? Essentially by trial and error, although there are a few tricks that help. If we want to determine the factors of eight, we start dividing numbers into it. We know that one goes evenly into eight—it goes evenly into every whole number. What about two? Yes, it’s a factor: it goes in four times. Three? No—it doesn’t go in evenly. Four? Yes, it goes in twice. That’s how we do it: by brute-force computing, testing every possible factor in turn. But as numbers get bigger, the number of factors they have get bigger. Earlier this year, a network of sixteen hundred computers succeeded in finding all the factors of a 129-digit number—the largest number ever factored. The