Friend-of-the-blog Dorit Aharonov asked me to advertise the QStart Conference, which will be held at Hebrew University of Jerusalem June 24-27 of this year, to celebrate the opening of Hebrew University’s new Quantum Information Science Center. Speakers include Yakir Aharonov, Jacob Bekenstein, Hans Briegel, Ed Farhi, Patrick Hayden, Ray Laflamme, Elon Lindenstrauss, Alex Lubotzky, John Martinis, Barbara Terhal, Umesh Vazirani, Stephanie Wehner, Andrew Yao … and me, your humble blogger (who will actually be there with Lily, on her first trip abroad—or for that matter, beyond the Boston metropolitan area). Dorit tells me that the conference should be of interest to mathematicians, physicists, chemists, philosophers, and computer scientists; that registration is open now; and that student travel support is available. Oh, and if you’re one of the people who think quantum computing is bunk? As displayed on the poster above, leading QC skeptic Gil Kalai is a co-organizer of the conference.
Archive for the ‘Announcements’ Category
Update: I submitted the following response to the comments over on Lubos’s blog. Since it has some bits of general interest, I thought I’d crosspost it here while it awaits Lubos’s moderation.
Since Lubos “officially invited” me to respond to the comments here, let me now do so.
1. On “loopholes” in quantum mechanics: I completely agree with Lubos’s observation that the actual contents of my book are “conservative” about the truth of QM. Indeed, I predict that, when Lubos reads his free copy, he’ll agree with (or at least, have no objections to) the vast majority of what’s in the book. On the other hand, because I was guest-blogging about “the story of me and Lubos,” I found it interesting to highlight one area of disagreement regarding QM, rather than the larger areas of agreement.
2. On Gene Day’s patronizing accusation that I don’t “get the basics of QM or even comprehend the role of mathematics in physics”: his misreading of what I wrote is so off-base that I don’t know whether a response is even necessary. Briefly, though: of course two formulations of QM are mathematically equivalent if they’re mathematically equivalent! I wasn’t asking why we don’t use different mathematical structures (quaternions, the 3-norm, etc.) to describe the same physical world. I was asking why the physical world itself shouldn’t have been different, in such a way that those other mathematical structures would have described it. In other words: if you were God, and you tried to invent a theory that was like QM but based on those other structures, would the result necessarily be less “nice” than QM? Would you have to give up various desirable properties of QM? Yes? Can you prove it? The ball’s in your court, Mr. Day — or else you can just read my book!
3. On Lord Nelson’s accusation that I’m a “poseur”: on reflection, someone who only knew me from blog stunts like this one could easily be forgiven for getting that impression! So it might be worth pointing out for the record that I also have a “day job” outside the blogosphere, whose results you can see here if you care.
4. On my political views: I wish to clarify for Tom Vonk that I despise not only “Communists,” but the ideology of Communism itself. One of the formative experiences of my life occurred when I was an 8-year-old at Wingate Kirkland summer camp, and all the campers had to relinquish whatever candy they’d brought into a communal “bunk trunk.” The theory was that all the campers, rich and poor alike, would then share the candy equally during occasional “bunk parties.” What actually happened was that the counselors stole the candy. So, during a meeting of the entire camp, I got up and gave a speech denouncing the bunk trunk as Communism. The next day, the camp director (who had apparently been a fellow-traveler in the 1950s) sat with me at lunchtime, and told me about a very evil man named Joe McCarthy who I was in danger of becoming like. But the truth was that I’d never even heard of McCarthy at that point — I just wanted to eat candy. And I’d give exactly the same speech today.
Like (I suppose) several billion of the world’s people, I believe in a dynamic market-based capitalist society, and also in strong environmental and other regulations to safeguard that society’s continued existence. And I don’t merely believe in that as a cynical compromise, since I can’t get the “dictatorship of the proletariat” that I want in my heart of hearts. Were I emperor of the world, progressive capitalism is precisely what I would institute. In return, perhaps, for paying a “candy tax” to keep the bunk functioning smoothly, campers could keep their remaining candy and eat or trade it to their heart’s delight.
5. On climate change: I’m not a professional climatologist, but neither is Lubos, and nor (correct me if I’m wrong) is anyone else commenting here. Accordingly, I refuse to get drawn into a debate about ice cores and tree rings and hockey sticks, since my experience is that such debates tend to be profoundly unilluminating when not conducted by experts. My position is an incredibly simple one: just like with the link between smoking and cancer, or the lack of a link between vaccines and autism, or any other issue where I lack the expertise to evaluate the evidence myself, I’ll go with what certainly looks like an overwhelming consensus among the scientists who’ve studied the matter carefully. Period. If the climate skeptics want to win me over, then the way for them to do so is straightforward: they should ignore me, and try instead to win over the academic climatology community, majorities of chemists and physicists, Nobel laureates, the IPCC, National Academies of Science, etc. with superior research and arguments.
To this, the skeptics might respond: but of course we can’t win over the mainstream scientific community, since they’re all in the grip of an evil left-wing conspiracy or delusion! Now, that response is precisely where “the buck stops” for me, and further discussion becomes useless. If I’m asked which of the following two groups is more likely to be in the grip of a delusion — (a) Senate Republicans, Freeman Dyson, and a certain excitable string-theory blogger, or (b) virtually every single expert in the relevant fields, and virtually every other chemist and physicist who I’ve ever respected or heard of — well then, it comes down to a judgment call, but I’m 100% comfortable with my judgment.
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.
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.)
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!
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.
Kai von Fintel
Anne Whiston Spirn
Members of the MIT Open Access Working Group
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.
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:
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.