Skip to main content

Quantum Computing for English Majors

The poet who discovered Shor’s algorithm answers questions about quantum computers and other mysteries

Credit:

Alfred Pasieka Getty Images

This article was published in Scientific American’s former blog network and reflects the views of the author, not necessarily those of Scientific American


Peter Shor is a poet. Here is a limerick he wrote with his wife, Jennifer:

If computers that you build are quantum,  Then spies of all factions will want 'em.  Our codes will all fail,  And they'll read our email,  Till we've crypto that's quantum, and daunt 'em.

Shor is better known as the mathematician who in 1994 discovered (invented?) Shor’s algorithm, a quantum-computational method for factoring numbers that helped boost the field of quantum computers to a new energy level. I’ve long thought that quantum computing might falsify my end-of-science thesis. It could lead to deep theoretical insights into the nature of matter and mind and the links between the two. Or it could lead to a gigantic leap forward in artificial intelligence. Or both. Or neither. I was thus delighted last fall when Shor and I swapped comments during a discussion of The End of Science on Sabine Hossenfelder’s blog. I asked if he would answer a few questions for my blog, and here is the result. — John Horgan


On supporting science journalism

If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.


Horgan: Did you become a mathematician because you didn’t think you could make a living as a poet?

Shor: No. I've been writing poetry occasionally since high school, but I never considered making a career of it. This question undoubtedly originated from a sentence that used to be on my web page. My wife and I wrote a limerick about quantum computing for a poetry contest that Science News was running.  When it didn't win, I posted the limerick on the web, and linked to it with the sentence "You can see why I chose a career as a scientist rather than as a poet." That sentence was a joke. Since then, I've posted a few less frivolous poems on my website and removed that sentence.

Horgan:In 1993 I argued in The Death of Proof that computer proofs and other developments were undermining the concept of traditional mathematical proofs. Just how wrong was I

Shor: Computer proofs really haven't undermined the concept of traditional mathematical proofs, at least not yet (although in 1993, some mathematicians were certainly afraid that they would). There are at least two reasons mathematicians look for proofs:

a) to ensure that the things they claim are actually true,

b) to gain more understanding into mathematics.

Computer proofs are generally satisfactory for the first reason above, but very few of them, if any, provide us any real understanding. There are certainly lots of computer-aided proofs now, where computers have helped in performing long calculations without error, or with elaborate case analyses.  But coming up with most mathematical proofs requires actual understanding of the underlying mathematics, and computers don't have that today. So computers can help mathematicians who understand the underlying mathematics by performing infeasibly long calculations and case analyses, but although they have been very useful for these purposes, most of the time they cannot come up with proofs by themselves.

It's possible that sometime far in the future, mathematics will be dominated by incomprehensible computer proofs. This might lead to “The End of Mathematics,” or at least of mathematics as carried out by human mathematicians. But we're nowhere near that point.

Horgan: Please explain the Shor algorithm to me, keeping in mind that in college I majored in English and took only one math course.

Shor: This is hard.

There are several aspects of quantum mechanics that make quantum computers more powerful than digital computers. One of these is the superposition principle, which says that a quantum system can be in more than one state at the same time. Another one of these is interference; a third is the exponentially large size of the state space of a quantum mechanical system.

It turns out that with a small amount of number theory, you can show that if you can find the period with respect to of the sequence xr(mod N), you will be able to factor N. This isn't very useful for a classical algorithm, because if is an exponentially large number, the period is exponentially long.  However, quantum computers can process an exponential amount of data that is in superposition. So they can put the entire sequence into their memory in superposition. Now, one of the things quantum computers can do with this sequence is take its Fourier transform, which lets them find the period of the sequence. 

One might think of this as a computational diffraction grating. Diffraction gratings use a periodic structure to separate light into its different component colors, and they do this through interference. The factoring algorithm works in a similar way.

Horgan: Thanks, I have a faint albeit probably illusory glimmer of understanding! What is the biggest popular fallacy about quantum computing? What is the most annoying trope or metaphor used by journalists to explain it?

Shor: The biggest popular fallacy about quantum computers is probably that they are just like classical computers, only faster. In fact, they are quite different. There are some problems that quantum computers seem to be exponentially faster than classical computers at, like factoring. There are other problems that quantum computers don't speed up at all, like sorting. So asking "which is better, a classical computer or a quantum computer" is like asking "which is a better transportation device, a boat or a car." It really depends on what you want to do with it.

Horgan: The National Academy of Sciences reports that “it is still too early to be able to predict the time horizon for a practical quantum computer,” and IEEE Spectrum claims we won’t see “useful” quantum computers “in the foreseeable future.” Are these critiques fair? Will quantum computers ever live up to their hype?

Shor: The NAS report was prepared by a committee of experts who spent a great deal of time thinking about possible different ways of achieving quantum computation, the various roadblocks for these methods, and about the difficulties of making a working quantum computer, and I think they give a fair appraisal of the difficulties of the task. 

The IEEE Spectrum article gives a much more pessimistic assessment. It was written by one physicist who has had a negative view of quantum computers since the very beginning of the field. Briefly, he believes that making quantum computers fault-tolerant is a much more difficult task than it is generally believed to be. (Let me note that it is generally believed to be extremely difficult, but that it is theoretically possible if you have accurate enough quantum gates and a large but not impossible amount of overhead.) I don't believe that his arguments are justified.

Horgan: Scott Aaronson said on this blog that “ideas from quantum information and computation will be helpful and possibly even essential for continued progress on the conceptual puzzles of quantum gravity.” Do you agree?

Shor: I want to partially agree. I think it's quite possible that quantum information and computation will be crucial ingredients in the ultimate theory of quantum gravity. In fact, I think that these ingredients have already made some advances in understanding quantum gravity. On the other hand, using quantum information ideas has become something of a fad in a certain community of physicists thinking about quantum gravity. In my opinion, some of these physicists really understand quantum information and are writing interesting papers. But some others have a very superficial understanding of quantum information, and I don’t think there is much substance to the papers they are writing. I am sure that this will get sorted out eventually, but right now it’s very difficult for people to tell which of these papers have interesting ideas in them. 

Horgan: John Wheeler suggested that quantum mechanics plus information theory, which he called the “it from bit,” might explain reality. Your take?

Shor: John Wheeler and this idea of "it from bit" certainly was very influential. Many of John Wheeler's students tried to pursue his vision, and were among the researchers who made the first discoveries in the fields of quantum information and quantum computation.  This has now turned into a large and fruitful subfield of physics.  

Is this what John Wheeler envisioned when he said "it from bit"? I don't know.  I think he would be very pleased by what has come from this, but I also don’t think that we have made much progress on his original motivation of "explaining reality"; this may be more of a job for philosophers than for physicists.

Horgan: Do you agree with Sabine Hossenfelder that physicists’ obsession with beauty has led them astray?

Shor: I think that the physicists have been led astray, but I would disagree that what led them astray is their obsession with beauty. Rather, I think that what has led theoretical physicists astray is that they are no longer grounded in experiment, and so can’t use the methods that let them make so much progress in the previous century.

Mathematicians also do research that is not grounded in experiments, but they have had centuries to figure out that a good way to cope with this is to use proofs, and not to trust anything that isn't actually proved rigorously. They learned this over the years by trial and error, discovering that if you try to do mathematics without relying on rigor, you are likely to be led astray by your intuition.  The culture of physics doesn't have this constraint. 

While the fact that they aren't constrained by needing rigorous proofs has helped physicists make remarkable contributions to several fields of mathematics much more quickly than mathematicians (for example, the Dirac delta function in the theory of distributions and the replica method in statistical mechanics), it has also occasionally led them astray.

High-energy physicists are now trying to produce new physics without either experiment or proof to guide them, and I don't believe that they have adequate tools in their toolbox to let them navigate this territory.

My impression, although I may be wrong about this, is that in the past, one way that physicists made advances is by coming up with all kinds of totally crazy ideas, and keeping only the ones that agreed with experiment. Now, in high energy physics, they're still coming up with all kinds of totally crazy ideas, but they can no longer compare them with experiments, so which of their ideas get accepted depends on some complicated sociological process, which results in theories of physics that may not bear any resemblance to the real world. This complicated sociological process certainly takes beauty into account, but I don't think that's what is fundamentally leading physicists astray. I think a more important problem is this sociological process leads high-energy physicists to collectively accept ideas prematurely, when there is still very little evidence in favor of them.  Then the peer review process leads the funding agencies to mainly fund people who believe in these ideas when there is no guarantee that they are correct, and any alternatives to these ideas are for the most part neglected.

For a concrete example, Susskind's theory of complementarity, which addressed the black hole information loss paradox, was accepted for many years, until four physicists published the AMPS paper (named after its authors' initials) showing that Susskind complementarity was not compatible with fundamental principles of quantum information theory. So in this case, the sociological process led most physicists to converge on a single theory that ultimately turned out to be wrong. The AMPS paper proposed an alternative crazy theory, “firewalls” but luckily for science, it does not seem to be universally accepted yet.

Horgan: Michael Nielsen suggests that agnosticism is the best stance when it comes to attempts to interpret quantum mechanics, or explain what it means. Do you agree? Or do you have a favorite interpretation? 

Shor: I agree with Michael. There are some times when thinking about quantum mechanics using the Copenhagen interpretation will help you figure things out, and there are other times when the many-worlds interpretation is more useful for figuring things out. Since these two interpretations give the exact same predictions, it doesn't matter which one you use. So you should use whichever gives you the best intuition for the problem you're working on.

Horgan: Might human consciousness be fundamentally quantum, as Roger Penrose and others have suggested?

Shor: It seems very unlikely to me.

Horgan: Could Godel’s theorem be a clue to the nature of consciousness, as Douglas Hofstadter has proposed

Shor: Again, this seems very unlikely to me.

Horgan: Nielsen and Patrick Collison warn in a recent essay in The Atlantic that science has entered a period of stagnation. Do you agree?

Shor: I wouldn't call it stagnation. They argue that advances in science are costing more and more, but we still seem to be making progress.

Horgan: What’s the biggest flaw of The End of Science? Do you agree with David Deutsch that science is infinite?

Shor: I think the biggest flaw of The End of Science is your argument that science is coming to an end because nobody sees any fundamental discoveries on the horizon. Fundamental discoveries in science, that change the foundations of a field, by their very nature cannot be predicted.  Taking an example from The End of Science, you consider the field of neuroscience, and speculate that we will never make any progress on figuring out how the brain works because it's too complicated. It's true that we currently have only the vaguest idea about how the brain works, and that we currently don't see any road to improving our knowledge. However, this doesn't really mean anything, as fundamental discoveries in science can come out of nowhere and be completely unpredictable.

Horgan: Point taken. Martin Rees argues that superintelligent machines might give science new life, by solving problems that have stymied humans. Do you agree?

Shor: If superintelligent machines solve problems that have stymied humans, but do it in such a way that their solutions are also completely incomprehensible to humans, I don't know whether I would want to call the result "science". 

Horgan: What’s your utopia?

Shor: In my utopia, we would not have large amounts of money being spent to discredit science. The start of this anti-science movement seems to have been rooted in self-interest by large corporations, trying to convince people of things like "tobacco doesn't cause cancer," "coal doesn't cause global warming," "DDT doesn't kill birds." But now, probably encouraged by creationism, it has spread to all of science. For example, the fact that there is widespread anti-science sentiment has let the anti-vaccination movement arise, which I don't believe has any large corporate sponsors and which most organized religions don't support; this movement is currently undoing some of the great success we have had towards eliminating disease.

Further Reading:

Mind-Body Problems (free online book, also available as Kindle e-book and paperback)

The Horgan Surface and the Death of Proof

Okay, Maybe Proofs Aren't Dying After All

How William Thurston (RIP) Helped Bring About "The Death of Proof"

Who Discovered the Mandelbrot Set?

Was I Wrong about The End of Science?

Is Science Hitting a Wall?

Beauty Does Not Equal Truth, in Physics or Elsewhere

Bayes's Theorem: What's the Big Deal?

See also Q&As with Scott AaronsonDavid AlbertDavid ChalmersNoam ChomskyDavid DeutschGeorge EllisMarcelo GleiserRobin HansonNick HerbertJim HoltSabine HossenfelderStuart KauffmanChristof KochGarrett LisiChristian ListTim MaudlinPriyamvada NatarajanNaomi OreskesMartin ReesCarlo RovelliRupert SheldrakeLee SmolinSheldon SolomonPaul SteinhardtPhilip TetlockTyler VolkSteven Weinberg,  Edward WittenPeter WoitStephen Wolfram and Eliezer Yudkowsky.