Shtetl-Optimized

Update (March 22): The Kindle edition of Quantum Computing Since Democritus is now available, for the low price of $15.40!  (Not factorial.)  Click here to get it from amazon.com, or here to get it from amazon.co.uk.  And let me know how it looks (I haven’t seen it yet).  Another Update: Just saw the Kindle edition, and the figures and formulas came out great!  It’s a product I stand behind with pride.

In the meantime, I regret to say that the marketing for this book is getting crasser and more exploitative by the day.

It seems like wherever I go these days, all anyone wants to talk about is Quantum Computing Since Democritus—the sprawling new book by Scott Aaronson, published by Cambridge University Press and available for order now.  Among leading figures in quantum information science—many of them well-known to Shtetl-Optimized readers—the book is garnering the sort of hyperbolic praise that would make Shakespeare or Tolstoy blush:

“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

“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?” —Michael Nielsen

“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

After months of overhearing people saying things like the above—in the halls of MIT, the checkout line at Trader Joe’s, the bathroom, anywhere—I finally had to ask in annoyance: “is all this buzz justified?  I mean, I’m sure the book is as deep, hilarious, and worldview-changing as everyone says it is.  But, after all, it’s based off lecture notes that have long been available for free on the web.  And Aaronson, being the magnanimous, open-access-loving saint that he is, has no plans to remove the online notes, even though he could really use the royalties from book sales to feed his growing family.  Nor does Cambridge University Press object to his principled decision.”

“No, you don’t understand,” they told me.  “Word on the street has it that the book is extensively updated for 2013—that it’s packed with new discussions of things like algebrization, lattice-based cryptography, the QIP=PSPACE theorem, the ‘quantum time travel controversy,’ BosonSampling, black-hole firewalls, and even the Australian models episode.  They say it took years of painstaking work, by Aaronson and his student Alex Arkhipov, to get the notes into book form: fixing mistakes, clarifying difficult points, smoothing out rough edges, all while leaving intact the original’s inimitable humor.  I even heard Aaronson reveals he’s changed his mind about certain things since 2006.  How could you not want such a labor of love on your bookshelf?”

Exasperated, I finally exclaimed: “But the book isn’t even out yet in North America!  Amazon.com says it won’t ship until April 30.”

“Sure,” one gas-station attendant replied to me, “but the secret is, it’s available now from Amazon.co.uk.  Personally, I couldn’t wait a month, so I ordered it shipped to me from across the pond.  But if you’re a less hardcore quantum complexity theory fan, and you live in North America, you can also preorder the book from Amazon.com, and they’ll send it to you when it arrives.”

Much as the hype still grated, I had to admit that I’d run out of counterarguments, so I looked into ordering a copy for myself.

Follow

I got back a couple days ago from John Preskill‘s 60th birthday symposium at Caltech.  To the general public, Preskill is probably best known for winning two bets against Stephen Hawking.  To readers of Shtetl-Optimized, he might be known for his leadership in quantum information science, his pioneering work in quantum error-correction, his beautiful lecture notes, or even his occasional comments here (though these days he has his own group blog and Twitter feed to keep him busy).  I know John as a friend, colleague, and mentor who’s done more for me than I can say.

The symposium was a blast—a chance to hear phenomenal talks, enjoy the California sun, and catch up with old friends like Dave Bacon (who stepped down as Pontiff before stepping down as Pontiff was cool).  The only bad part was that I inadvertently insulted John in my talk, by calling him my “lodestar of sanity.”  What I meant was that, for 13 years, I’ve known plenty of physicists who can be arbitrarily off-base when they talk about computer science and vice versa, but I’ve only ever known John to be on-base about either.  If you asked him a question involving, say, both Barrington’s Theorem and Majorana fermions, he’s one of the few people on earth who would know both, seem totally unfazed by your juxtaposing them, and probably have an answer that he’d carefully tailor to your level of knowledge and interest.  In a polyglot field like quantum information, that alone makes him invaluable.  But along with his penetrating insight comes enviable judgment and felicity of expression: unlike some of us (me), John always manages to tell the truth without offending his listeners.  If I were somehow entrusted with choosing a President of the United States, he’d be one of my first choices, certainly ahead of myself.

Anyway, it turned out that John didn’t like my use of the word “sane” to summarize the above: for him (understandably, in retrospect), it had connotations of being humorless and boring, two qualities I’ve never seen in him.  (Also, as I pointed out later, the amount of time John has spent helping me and patiently explaining stuff to me does weigh heavily against his sanity.)  So I hereby rename John my Lodestar of Awesomeness.

In case anyone cares, my talk was entitled “Hidden Variables as Fruitful Dead Ends”; the PowerPoint slides are here.  I spoke about a new preprint by Adam Bouland, Lynn Chua, George Lowther, and myself, on possibility and impossibility results for “ψ-epistemic theories” (a class of hidden-variable theories that was also the subject of the recent PBR Theorem, discussed previously on this blog).  My talk also included material from my old paper Quantum Computing and Hidden Variables.

The complete program is here.  A few highlights (feel free to mention others in the comments):

• Patrick Hayden spoke about a beautiful result of himself and Alex May, on “where and when a qubit can be.”  After the talk, I commented that it’s lucky for the sake of Hayden and May’s induction proof that 3 happens to be the next integer after 2.  If you get that joke, then I think you’ll understand their result and vice versa.
• Lenny Susskind—whose bestselling The Theoretical Minimum is on my to-read list—spoke about his views on the AMPS firewall argument.  As you know if you’ve been reading physics blogs, the firewall argument has been burning up (har, har) the world of quantum gravity for months, putting up for grabs aspects of black hole physics long considered settled (or not, depending on who you ask).  Lenny gave a typically-masterful summary, which for the first time enabled me to understand the role played in the AMPS argument by “the Zone” (a region near the black hole but outside its event horizon, in which the Hawking radiation behaves a little differently than it does when it’s further away).  I was particularly struck by Lenny’s comment that whether an observer falling into a black hole encounters a firewall might be “physics’ Axiom of Choice”: that is, we can only follow the logical consequences of theories we formulate outside black-hole event horizons, and maybe those theories simply don’t decide the firewall question one way or the other.  (Then again, maybe they do.)  Lenny also briefly mentioned a striking recent paper by Harlow and Hayden, which argues that the true resolution of the AMPS paradox might involve … wait for it … computational complexity, and specifically, the difficulty of solving QSZK (Quantum Statistical Zero Knowledge) problems in BQP.  And what’s a main piece evidence that QSZK⊄BQP?  Why, the collision lower bound, which I proved 12 years ago while a summer student at Caltech and an awestruck attendee of Preskill’s weekly group meetings.  Good thing no one told me back then that black holes were involved.
• Charlie Bennett talked about things that I’ve never had the courage to give a talk about, like the Doomsday Argument and the Fermi Paradox.  But his disarming, avuncular manner made it all seem less crazy than it was.
• Paul Ginsparg, founder of the arXiv, presented the results of a stylometric analysis of John Preskill’s and Alexei Kitaev’s research papers.  The main results were as follows: (1) John and Alexei are easily distinguishable from each other, due in part to the more latter’s “Russian” use of function words (“the,” “which,” “that,” etc.).   (2) Alexei, despite having lived in the US for more than a decade, is if anything becoming more “Russian” in his function word use over time. (3) Even more interestingly, John is also becoming more “Russian” in his function word use—a possible result of his long interaction with Alexei. (4) A joint paper by Kitaev and Preskill was indeed written by both of them.  (Update: While detained at the airport, Paul decided to post an online video of his talk.)

Speaking of which, the great Alexei Kitaev himself—the $3 million man—spoke about Berry curvature for many-body systems, but unfortunately I had to fly back early (y’know, 2-month-old baby) and missed his talk.  Maybe someone else can provide a summary.

Happy 60th birthday, John!

Two unrelated announcements.

1. Everyone who reads this blog should buy Sean Carroll’s two recent books: From Eternity to Here (about the arrow of time) and The Particle at the End of the Universe (about the Higgs boson and quantum field theory more generally).  They’re two of the best popular physics books I’ve ever read—in their honesty, humor, clarity, and total lack of pretense, they exemplify what every book in this genre should be but very few are.  If you need even more inducement, go watch Sean hit it out of the park on the Colbert Report (and then do it again).  I can’t watch those videos without seething with jealousy: given how many “OK”s and “y’know”s lard my every spoken utterance, I’ll probably never get invited to hawk a book on Colbert.  Which is a shame, because as it happens, my Quantum Computing Since Democritus book will finally be released in the US by Cambridge University Press on April 30th!  (It’s already available in the UK, but apparently needs to be shipped to the US by boat.)  And it’s loaded with new material, not contained in the online lecture notes.  And you can preorder it now.  And my hawking of Sean’s books is in no way whatsoever related to any hope that Sean might return the favor with my book.

2. Recent Turing Award winner Silvio Micali asks me to advertise the Second Cambridge Area Economics and Computation Day (CAEC’13), which will be held on Friday April 26 at MIT.  Anything for you, Silvio!  (At least for the next week or two.)

Follow

Today I break long radio silence to deliver some phenomenal news.  Two of the people who I eat lunch with every week—my MIT CSAIL colleagues Silvio Micali and Shafi Goldwasser—have won a well-deserved Turing Award, for their fundamental contributions to cryptography from the 1980s till today.  (I see that Lance just now beat me to a blog post about this.  Dammit, Lance!)

I won’t have to tell many readers of this blog that the names Goldwasser and Micali—or more often, the initials “G” and “M”—are as ubiquitous as Alice and Bob in modern cryptography, from the GGM construction of pseudorandom functions (discussed before on this blog), to the classic GMR paper that introduced the world to interactive proofs.  Besides that, Shafi and Silvio are known as two of the more opinionated and colorful characters of theoretical computer science—and as I learned last week, Silvio is also an awesome party host, who has perfect taste in sushi (as well as furniture and many other things).

I wish I could go on right now talking about Shafi and Silvio—and even more, that I could join the celebration that will happen at MIT this afternoon.  But I’m about to board a flight to LAX, to attend the 60th birthday symposium of longtime friend, extraordinary physicist, and sometime Shtetl-Optimized commenter John Preskill.  (I’ll also be bringing you coverage of that symposium, including slides from my talk there on hidden variables.)  So, leave your congratulations, etc. in the comments section, and I’ll see them when I land!

Follow

Good news, everyone!  Anindya De, Oded Regev, and my postdoc Thomas Vidick are launching an online theoretical computer science seminar series called TCS+, modeled after the successful Q+ quantum information seminars run by Daniel Burgarth and Matt Leifer.  The inaugural TCS+ lecture will be on Wednesday Feb. 6, at noon Eastern Standard Time.  Ronald de Wolf, longtime friend both of this blog and of its author, will be speaking on Exponential Lower Bounds for Polytopes in Combinatorial Optimization, his STOC’2012 Best Paper with Samuel Fiorini, Serge Massar, Sebastian Pokutta and Hans Raj Tiwary.  This is the paper that used ideas originally from quantum communication complexity to solve a 20-year-old problem in classical optimization: namely, to rule out the possibility of proving P=NP by reducing the Traveling Salesman Problem to certain kinds of linear programs.  Ronald previously gave the talk at MIT, and it rocked.  See Thomas’s blog for details about how to watch.

Follow

Scott Aaronson
Sasha Costanza-Chock
Kai von Fintel
Richard Holton
George Stephanopoulos
Anne Whiston Spirn

Members of the MIT Open Access Working Group

Follow

If the world ends today, at least it won’t do so without three identical photons having been used to sample from a probability distribution defined in terms of the permanents of 3×3 matrices, thereby demonstrating the Aaronson-Arkhipov BosonSampling protocol.  And the results were obtained by no fewer than four independent experimental groups, some of whom have now published in Science.  One of the groups is based in Brisbane, Australia, one in Oxford, one in Vienna, and one in Rome; they coordinated to release their results the same day.  That’s right, the number of papers (4) that these groups managed to choreograph to appear simultaneously actually exceeds the number of photons that they so managed (3).  The Brisbane group was even generous enough to ask me to coauthor: I haven’t been within 10,000 miles of their lab, but I did try to make myself useful to them as a “complexity theory consultant.”

Here are links to the four experimental BosonSampling papers released in the past week:

• Experimental BosonSampling by Broome et al. (Brisbane)
• Experimental Boson Sampling by Tillmann et al. (Vienna)
• Experimental Boson Sampling by Walmsley et al. (Oxford)
• Experimental boson sampling in arbitrary integrated photonic circuits by Crespi et al. (Italy)

For those who want to know the theoretical background to this work:

• My and Alex’s original 100-page BosonSampling paper (to appear soon in the journal Theory of Computing)
• The 10-page STOC’2011 version of our paper
• My PowerPoint slides
• Alex’s slides
• Theoretical Computer Science StackExchange question and answer
• Gil Kalai’s blog post
• Old Shtetl-Optimized post

For those just tuning in, here are some popular-level articles about BosonSampling:

• Larry Hardesty’s MIT News article (from last year)
• University of Queensland press release
• Victorian counting device gets speedy quantum makeover (this week, from New Scientist; the article is not bad except that it ought to credit Alex Arkhipov)
• New Form of Quantum Computation Promises Showdown with Ordinary Computers, by Adrian Cho (from Science)

I’ll be happy to answer further questions in the comments; for now, here’s a brief FAQ:

Q: Why do you need photons in particular for these experiments?

A: What we need is identical bosons, whose transition amplitudes are given by the permanents of matrices.  If it were practical to do this experiment with Higgs bosons, they would work too!  But photons are more readily available.

Q: But a BosonSampling device isn’t really a “computer,” is it?

A: It depends what you mean by “computer”!  If you mean a physical system that you load input into, let evolve according to the laws of physics, then measure to get an answer to a well-defined mathematical problem, then sure, it’s a computer!   The only question is whether it’s a useful computer.  We don’t believe it can be used as a universal quantum computer—or even, for that matter, as a universal classical computer.  More than that, Alex and I weren’t able to show that solving the BosonSampling problem has any practical use for anything.  However, we did manage to amass evidence that, despite being useless, the BosonSampling problem is also hard (at least for a classical computer).  And for us, the hardness of classical simulation was the entire point.

Q: So, these experiments reported in Science this week  have done something that no classical computer could feasibly simulate?

A: No, a classical computer can handle the simulation of 3 photons without much—or really, any—difficulty.  This is only a first step: before this, the analogous experiment (called the Hong-Ou-Mandel dip) had only ever been performed with 2 photons, for which there’s not even any difference in complexity between the permanent and the determinant (i.e., between bosons and fermions).  However, if you could scale this experiment up to about 30 photons, then it’s likely that the experiment would be solving the BosonSampling problem faster than any existing classical computer (though the latter could eventually solve the problem as well).  And if you could scale it up to 100 photons, then you might never even know if your experiment was working correctly, because a classical computer would need such an astronomical amount of time to check the results.

Follow

The Pennsylvania Governor’s School for the Sciences (PGSS) was an incredibly-successful summer program for gifted high school students in my birth-state of Pennsylvania.  PGSS ran from 1982 to 2009 and then was shuttered due to state budget cuts.  A group of alumni is now trying to raise enough private funds to restart the program (they need $100,000).  Please visit their site, watch their video, and make a small (or large) donation if you feel moved to.

In other news, I’ll be speaking at a workshop on Quantum Information Science in Computer and Natural Sciences, organized by Umesh Vazirani and Carl Williams, to be held September 28-29 at the University of Maryland College Park.  This workshop is specifically designed for computer scientists, mathematicians, physicists, and others who haven’t worked in quantum information, but who’d like to know more about current research in the area, and to look for connections between quantum information and their own fields.  Umesh writes:

Follow

Update (August 5): Sorry for the delay! Now that the Zoo is back up, my sense of urgency has decreased, but we still do need a long-term solution. Thanks so much to everyone who offered hosting. Alas, I was persuaded by the argument that it’s too complicated to have a wiki mirrored at multiple locations, so I should really choose one—and ideally it should be someplace where I retain control of the files, in case anything goes wrong again. Following the helpful directions of Eric Price, I set up a MediaWiki installation at http://scottaar.scripts.mit.edu/zoo. Is anyone interested in helping me transfer over the content from the qwiki Zoo?

Update (August 1): Thanks to the efforts of Gopal Sarma at Stanford, the Zoo is back up and running!!  However, I believe the only long-term solution is to get the Zoo mirrored at other locations.  I can then direct the domain complexityzoo.com to point to any of them that are currently up.  So, to all of those who volunteered to mirror the Zoo: thanks so much, and please go ahead and do so!  Let me know what you need for that (I can ask Gopal to get the source files).

As some of you have noticed, the Complexity Zoo (well, don’t bother clicking the link!) has been down for the past couple weeks.  Some Stanford students volunteered to host the Zoo years ago but then graduated, and these sorts of outages have been a frustrating reality since then.  So my co-zookeeper Greg Kuperberg and I are looking for a volunteer to help us get the Zoo back online.  The reward?  Eternal gratitude and a co-zookeeper title for yourself.  In principle, I could host the Zoo on my Bluehost account, but I don’t know how to set up the wiki software, and I’m not even sure how to retrieve the Zoo pages prior to its going down (Google Cache?).  If you’re interested or have ideas, leave a comment or send me an email.

Thanks!!

Follow

Tomorrow, at 9AM EST (or an hour before teatime in Britain), I’ll be giving an online talk on Quantum Money from Hidden Subspaces (see here for PowerPoint slides) at the Q+ hangout on Google+.  To watch the talk, go here, then click the “Play” button on the video that will be there tomorrow.  Abstract:

Forty years ago, Wiesner pointed out that quantum mechanics raises the striking possibility of money that cannot be counterfeited according to the laws of physics. We propose the first quantum money scheme that is (1) public-key, meaning that anyone can verify a banknote as genuine, not only the bank that printed it, and (2) cryptographically secure, under a “classical” hardness assumption that has nothing to do with quantum money. Our scheme is based on hidden subspaces, encoded as the zero-sets of random multivariate polynomials. A main technical advance is to show that the “black-box” version of our scheme, where the polynomials are replaced by classical oracles, is unconditionally secure. Previously, such a result had only been known relative to a quantum oracle (and even there, the proof was never published). Even in Wiesner’s original setting — quantum money that can only be verified by the bank — we are able to use our techniques to patch a major security hole in Wiesner’s scheme. We give the first private-key quantum money scheme that allows unlimited verifications and that remains unconditionally secure, even if the counterfeiter can interact adaptively with the bank. Our money scheme is simpler than previous public-key quantum money schemes, including a knot-based scheme of Farhi et al. The verifier needs to perform only two tests, one in the standard basis and one in the Hadamard basis — matching the original intuition for quantum money, based on the existence of complementary observables. Our security proofs use a new variant of Ambainis’s quantum adversary method, and several other tools that might be of independent interest.  Joint work with Paul Christiano.

Update: Here’s a YouTube video of the talk.

In unrelated news, Alistair Sinclair asked me to announce that UC Berkeley’s new Simons Institute for Theoretical Computer Science—you know, the thing Berkeley recently defeated MIT (among others) to get—is soliciting proposals for programs.  The deadline is July 15, so be sure to get your proposal in soon.

Follow

Yesterday brought the tragic news that Mihai Pătraşcu—who revolutionized the field of data structures since he burst onto the scene a decade ago—has passed away at the age of 29, after a year-and-a-half-long battle with brain cancer.  Mihai was not only an outstanding researcher but a fun-loving, larger-than-life personality in the computer science theory community.  For more information, see Lance and Bill’s or Michael Mitzenmacher’s blogs.

Mihai was an MIT CS PhD student (advised by Erik Demaine), who worked on the same floor as me for the first couple years I was here.  I’m still in shock over his loss—I hadn’t even known about the cancer before yesterday.   Mihai and I had pretty big disagreements, mostly over the viability of quantum computing, the “technical” versus “conceptual” theory debate, various things he wrote on his blog and various things I wrote on mine.  But it seems terribly stupid now to have let this stuff get in the way of collegiality.  I feel guilty for not trying to mend bridges with him when I had the chance.

Rest in peace, Mihai.

Follow