Scott Aaronson: Quantum Computing since Democritus

Guest blog by the man who is Shtetl-Optimized

It's an exquisite, delicious, life-changing honor to be invited to guest-blog on Luboš Motl's Reference Frame. In terms of The Big Bang Theory, imagine Sheldon (to whom Luboš likes to compare himself) inviting Howard Wolowitz to guest-post. Lo, how far the brilliant string theorist has condescended!

On the other hand, I confess that finding myself on Luboš's blog, with the freedom to write whatever I please, feels a little like finding myself in front of an open mic at the Republican National Convention. One part of me feels a moral obligation to seize this rare opportunity and say something like the following:

CONSERVATIVE LUBOŠ FANS: GET OUT OF YOUR BUBBLE! GLOBAL WARMING IS A REAL PROBLEM! IT'S HAPPENING, HUMAN ACTIVITY IS A MAJOR CAUSE, AND THE CONSEQUENCES ARE SERIOUS! EVEN LUBOŠ'S OWN STRING-THEORIST HEROES, LIKE ED WITTEN AND BRIAN GREENE, BELIEVE SO! VIRTUALLY EVERY SERIOUS SCIENTIST DOES — AT SOME LEVEL, ONE SUSPECTS, EVEN LUBOŠ HIMSELF! BUT HE CAN'T ADMIT IT, BECAUSE HE ASSOCIATES CONCERN ABOUT GLOBAL WARMING – OR ANY OTHER "LEFTY" CAUSE – WITH THE EVIL COMMUNISTS WHO OPPRESSED CZECHOSLOVAKIA IN HIS CHILDHOOD! BUT SOME US DESPISE COMMUNISTS EVERY BIT AS MUCH AS LUBOŠ DOES, BUT ALSO RECOGNIZE THAT THEY'RE NOT THE ONLY EVIL THE WORLD HAS EVER KNOWN! ONE HOPES LUBOŠ WILL EVENTUALLY COME TO THAT REALIZATION AS WELL!

But enough of this. I don't want to abuse my host's hospitality. Luboš invited me here, not to dispute his views on climate change, but rather to promote my new book Quantum Computing Since Democritus (published by Cambridge University Press and available now in Europe, on April 30^th in North America, and wherever and whenever on Kindle). So promoting my book is exactly what I'll do—by first telling you the story (such as it is) of my interaction with Luboš, and then explaining how that story relates to the book.




While I've never had the privilege of meeting Luboš in person (those who have tell me he's a perfect gentleman), he and I have ... exchanged pleasantries online. Regulars on the science blogosphere might remember that six years ago, I wrote a tongue-in-cheek blog post recounting my visit to the string theory group at Stanford, and claiming that my "allegiances" in the battle between string theory and loop quantum gravity were now open for sale to the highest bidder. ("Fly me to an exotic enough location, put me up in a swank enough hotel, and the number of spacetime dimensions can be anything you want it to be...")

Luboš, either oblivious to my post's lack of seriousness or deliberately ignoring it (it can be hard to tell), offered up the following wonderful Lubošian response:

It is absolutely impossible for me to hide how intensely I despise people like Scott Aaronson ... He's the ultimate example of a complete moral breakdown of a scientist. It is astonishing that the situation became so bad that the people are not only corrupt and dishonest but they proudly announce this fact on their blogs ... [Scott is] a corrupt piece of moral trash. My anger may be quiet but it is unyielding. It's not just him: the Academia is literally flooded by intellectual prostitutes.

Fortunately, Luboš's opinion of me seemed gradually to improve in the ensuing years (I guess it would be hard for it to worsen). For example, in his comments disputing my take on the so-called "PBR Theorem"—I considered the theorem simple and unsurprising but still well worth knowing, while Luboš considered it "garbage" and "crackpot"—Luboš at least upgraded me from "moral trash" to a "mad engineer." (Once again, the irony seemed lost on Luboš: I've never met a real engineer who considered me anything other than a hyper-abstract pure mathematician. I guess if you live in Manhattan, Brooklyn seems like a primitive wilderness.)




Later, Luboš and I discovered that we shared a common enemy, in the countless armchair physicists who notice the profound conflict between their intuitions about how the world should work, and quantum mechanics' description of how it does work—and immediately conclude that the problem must lie with quantum mechanics. Luboš and I were united against the entanglement-denier Joy Christian, and again against the trivial errors of Ross Anderson and Robert Brady. The latter alliance even led Luboš to compliment me, to which I responded as follows:

Luboš says he’s sure my "thinking engines" are good enough to see eye-to-eye with him! Callooh! Callay! This might be the single greatest compliment I’ve ever received.

And Luboš, in return for your generous compliment, I have some good news. As a result of major life changes—getting married, having a baby, etc.—I have abandoned my previous materialistic, money-grubbing ways. I’m now strictly a man of principle. And as such, no amount of money could ever induce me to abandon my total, principled commitment to Loop Quantum Gravity.

OK, OK, I’m kidding about the last part. In fact, I have a much better appreciation now for the achievements of string theory than I did back in 2006, partly due to a meeting in Florence where Brian Greene spent 4 hours explaining them to me and others. I came away genuinely impressed, convinced that string theory and especially AdS/CFT are unequivocally a step forward in our understanding of the universe, even though we have a great deal more to learn. I’m not ready to say that alternative ideas like LQG are garbage and have nothing worthwhile to contribute, let alone that global warming is a sham, but maybe Lubošification is a process that will happen to me one step at a time.

Granted, I'm not quite as radical (or rather, conservative) as Luboš on the quantum mechanics issue. I believe we still have a great deal to understand about ordinary, nonrelativistic QM in finite-dimensional Hilbert spaces—and as strong evidence for that claim, I cite the half-century that elapsed after QM's discovery before anyone asked the simple, profound question of whether or not it requires exponential resources to simulate on a digital computer. I believe it's at least possible that QM is only an approximation to a deeper theory, and that even wild speculations along those lines could deserve a hearing. I believe that philosophical arguments about the "meaning" of QM can be fun in moderation, and that mathematical theorems seeking to clarify QM's meaning can be illuminating—even if those theorems "merely make rigorous what we should've known all along." On all these questions, my impression is that Luboš disagrees.

On one crucial point, though, I stand shoulder to shoulder with Luboš. I believe that in science, the ratchet of progress only turns in one direction. If quantum mechanics is ever superseded, there's every reason to expect that its successor will be even more alien to human concepts, and less acceptable to the world's a-priori thinkers. (Has it ever been otherwise in the history of physics?) Likewise, if future generations do achieve a deeper understanding of QM than ours has managed, the path to that understanding will have to go "all the way through QM and out the other end." It certainly won't come from people suffering from infantile delusions about Bell's Theorem being wrong, or quantum phenomena being explainable by some doofus classical model that somehow escaped everyone's notice for the last century. Nor will it come from the aggressive ignoramuses whose interest in quantum-mechanical experiments starts and ends with the question of how to explain the experiments away. Instead progress will come, as it always has, from the scientists trying as hard as possible to turn the ratchet forward—maybe by pushing the known laws of physics up to Planck-scale energies (like Luboš and the other string theorists), or maybe by pushing the frontier of knowledge in other directions (like the ultimate limits of computation, to pick one random example).

And that, finally, brings me to my book. If one likes, Quantum Computing Since Democritus is my 400-page answer to a claim Luboš often makes: that nonrelativistic quantum mechanics has been completely understood since the 1920s, that all that's left is some grunt-work for engineers. To anyone who thinks that quantum computing is "merely" a cool application of century-old physics, that it doesn't raise any new questions about how our universe works—Quantum Computing Since Democritus is my answer.

In my book, quantum computing emerges as a particular kind of gadfly: one that doesn't challenge any aspect of quantum mechanics as (say) Luboš understands it, but that does spur us to ask a whole new set of questions about it. What kinds of questions? Well, here's a small sampling of what the book addresses:

1. "Why is quantum mechanics the way it is?" More precisely: what goes wrong if we try to base QM (say) on real numbers or quaternions rather than complex numbers, or conservation of 3-norm rather than conservation of 2-norm?
2. Can quantum computers solve NP-complete problems in polynomial time? Conversely, can quantum computers be simulated in the class NP? In other words, even assuming it's hard to simulate a quantum computer classically, is there at least a short classical proof that a QC produces such-and-such an output, which can be verified in classical polynomial time? Pending breakthroughs in theoretical computer science (like a proof of P≠NP), what kind of evidence can we give for or against these possibilities?
3. Is there anything "beyond" quantum computing? More precisely: is there any natural class of problems that generalizes what a quantum computer can do, but only "slightly" rather than "dramatically"? If there is, then can we find a hypothetical framework for physics that "slightly" generalizes quantum mechanics, and which would let us solve the problems in that class?
4. Can mathematical tools from quantum computing be used to solve problems about classical computing—much as complex numbers are often indispensable even for proving theorems solely about integers or real numbers?
5. Read anything written about quantum computing for a popular audience (or sometimes even a technical audience), and you'll probably find some claim of the flavor that a mere n qubits can store a whopping ~2ⁿ classical bits. In what sense is that actually true? How should we even define the "amount of information" in a quantum state? If we require that the information be "accessible via measurement," or "available to do useful computational work" (whatever that means), do we still find that the amount of information increases exponentially with the number of qubits? Are there problems that we can solve, or are there mathematical truths that we can verify, with help from a reasonable-sized quantum state but not with help from a reasonable-sized classical string? (Assuming we have a quantum computer available in both cases?)
6. Why does David Deutsch (one of the originators of QC) think that a scalable quantum computer would be a powerful demonstration of the truth of the many-worlds interpretation? What are the counterarguments to Deutsch's position?
7. How powerful would a quantum computer become if we augmented it with a closed timelike curve? Or what about "postselection" (the ability to measure a qubit and simply condition on the outcome being, say, |1〉)? Would a quantum computer interact with these sorts of powers differently than a classical computer would?

But the book is about much more than the above questions—indeed, half of it isn't even about quantum computing per se, but about what I view as the broad intellectual backdrop to QC. Among other things, the book covers set theory, first-order logic, Gödel's Theorem, Turing machines and computability, the P versus NP problem, modern cryptography, computational learning theory, interactive proofs, and all sorts of philosophical debates. In the last two chapters, I even venture ever-so-slightly onto Luboš's turf, sharing some thoughts about cosmology, holography, the black hole information problem, and firewalls, especially as they relate to quantum computing.

(The unusually-wide scope what I was trying to suggest with the strange title. Democritus, with whom the book really does start, was a Greek atomist known to his contemporaries as "the Laughing Philosopher"; he might have been the first human being to articulate what we'd recognize today as a scientific worldview.)

In terms of level, Quantum Computing Since Democritus has way too much math to be a "popular" book, but it's also too breezy and informal to be a textbook. So who's the intended audience? Basically, the sort of person who reads this blog! (Or my blog, or books like Lenny Susskind's The Theoretical Minimum or Roger Penrose's The Road to Reality.) I wrote the book for people who want to see part of the current scientific landscape from one researcher's heavily-biased vantage point—and who want that researcher to talk to them the same way he'd talk to a colleague in a different field.

So, I hope I've convinced you to give Quantum Computing Since Democritus a try. If I haven't, then maybe effusive reviews from three of the world's top quantum computing theorists will help seal the deal.

"Scott Aaronson has written a beautiful and highly original synthesis of what we know about some of the most fundamental questions in science: What is information? What does it mean to compute? What is the nature of mind and of free will? Highly recommended."

Michael Nielsen, Author of Reinventing Discovery, (Princeton University Press, 2011)"

I laughed, I cried, I fell off my chair - and that was just reading the chapter on Computational Complexity. Aaronson is a tornado of intellectual activity: he rips our brains from their intellectual foundations; twists them through a tour of physics, mathematics, computer science, and philosophy; stuffs them full of facts and theorems; tickles them until they cry `Uncle'; and then drops them, quivering, back into our skulls. Aaronson raises deep questions of how the physical universe is put together and why it is put together the way it is. While we read his lucid explanations we can believe - at least while we hold the book in our hands - that we understand the answers, too."

Seth Lloyd, Massachusetts Institute of Technology, Author of Programming the Universe, (Vintage, 2007)

"Not since Richard Feynman's Lectures on Physics has there been a set of lecture notes as brilliant and as entertaining. Aaronson leads the reader on a wild romp through the most important intellectual achievements in computing and physics, weaving these seemingly disparate fields into a captivating narrative for our modern age of information. Aaronson wildly runs through the fields of physics and computers, showing us how they are connected, how to understand our computational universe, and what questions exist on the borders of these fields that we still don't understand. This book is a poem disguised as a set of lecture notes. The lectures are on computing and physics, complexity theory and mathematical logic and quantum physics. The poem is made up of proofs, jokes, stories, and revelations, synthesizing the two towering fields of computer science and physics into a coherent tapestry of sheer intellectual awesomeness."

Dave Bacon, Google

In summary, I hope to have written a book from which anyone can learn something new about quantum mechanics—from my mom, to a precocious high-school student, to my computer-science colleagues, to (yes) my gracious host LM. Speaking of which: as a burying-the-hatchet gesture, I hereby offer Luboš a complimentary copy of my book, if he gives me an address to send it to. No letter-bombs, I promise.