Shtetl-Optimized

On Sunday afternoon, Dana, Lily, and I were in Copley Square in Boston for a brunch with friends, at the Mandarin Oriental hotel on Boylston Street.  As I now recall, I was complaining bitterly about a number of things.  First, I’d lost my passport (it’s since been found).  Second, we hadn’t correctly timed Lily’s feedings, making us extremely late for the brunch, and causing Lily to scream hysterically the entire car ride.  Third, parking (and later, locating) our car at the Prudential Center was a logistical nightmare.  Fourth, I’d recently received by email a profoundly silly paper, claiming that one of my results was wrong based on a trivial misunderstanding.  Fifth … well, there were other things that were bothering me, but I don’t remember what they were.

Then the next day, maybe 50 feet from where we’d been, the bombs went off, three innocent human beings lost their lives and many more were rendered permanently disabled.

Drawing appropriate morals is left as an exercise for the reader.

Update (Friday, 7AM): Maybe the moral is that you shouldn’t philosophize while the suspects are still on the loose. Last night (as you can read anywhere else on the web) an MIT police officer was tragically shot and killed in the line of duty, right outside the Stata Center, by one of the marathon bombers (who turn out to be brothers from Chechnya). After a busy night—which also included robbing a 7-Eleven (visiting a 7-Eleven that was coincidentally also robbed—no novelist could make this stuff up), carjacking a Mercedes two blocks from my apartment, and randomly throwing some more pressure-cooker bombs—one of the brothers was killed; the other one escaped to Watertown. A massive hunt for him is now underway. MIT is completely closed today, as is Harvard and pretty much every other university in the area—and now, it seems, all stores and businesses in the entire Boston area. The streets are mostly deserted except for police vehicles. As for us, we heard the sirens through much of the night, but didn’t know what they were about until this morning. Here’s hoping they catch the second asshole soon.

Another Update (Friday, 9AM): As the sorry details emerge about these Tsarnaev brothers, it occurs to me that there’s another moral we can draw: namely, we can remind ourselves that the Hollywood image of the evil criminal genius is almost entirely a myth. Yes, evil and genius have occasionally been found in the same person (as with a few of the Nazi scientists), but it’s evil and stupidity that are the far more natural allies. Which is the most optimistic statement I can think to make right now about the future of the human race.

Yet More Updates (Friday, 3PM): The whole Boston area is basically a ghost town now, with the streets empty on a beautiful spring day and the sound of helicopters filling the air.  I was just up on my roofdeck to watch, and never saw anything like it.  I can’t help thinking that it sets a terrible precedent to give a couple doofus amateur terrorists the power to shut down an entire metropolitan area.  Meanwhile, Andrew Sullivan points to a spectacularly stupid tweet by one Nate Bell:

I wonder how many Boston liberals spent the night cowering in their homes wishing they had an AR-15 with a hi-capacity magazine?

This sounds like a gun nut projecting his own disturbed psychology onto other people.  I’m not actually scared, but if I was, owning a gun would do nothing whatsoever to make me less scared (quite the contrary).  What would make me think I could win a gunfight against a frothing lunatic—or that I’d want to find out?  When it comes to violence, the only thing that calms my nerves is a democratic state having a near-monopoly on it.

What else?  It was chilling to watch the Tsarnaev brothers’ aunt, the one in Toronto, babble incoherently on TV about how wonderful her nephews were (a striking contrast to the remorseful uncle in Maryland).  If it emerges that anyone else in this family (including the parents, or the older brother’s wife) had any foreknowledge about the killing spree, then I very much hope they’ll face justice as well.

In other news, Lily had an eventful day too: she finally figured out how to squeeze her toy ball with her hands.

Follow

On Wednesday, I gave a fun talk with that title down the street at Microsoft Research New England.  Disappointingly, no one in the audience did seem to think quantum computing was bunk (or if they did, they didn’t speak up): I was basically preaching to the choir.  My PowerPoint slides are here.  There’s also a streaming video here, but watch it at your own risk—my stuttering and other nerdy mannerisms seemed particularly bad, at least in the short initial segment that I listened to.  I really need media training.  Anyway, thanks very much to Boaz Barak for inviting me.

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

In 7+ years of blogging, one lesson I’ve learned is to go easy on the highly-personal stuff.  But sometimes one does need to make an exception.  Lily Rebecca Aaronson was born today (Jan. 20), at 6:55am, to me and Dana, weighing 3.3kg.  (After seeing her placenta, the blog category “Adventures in Meatspace” never seemed more appropriate.)  I’m blogging from the postpartum ward, which has free wifi and excellent food—we’ll probably stay here as long as they’ll let us.

Given that her parents are both complexity theorists, one question people will have is whether Lily demonstrates any early aptitude in that field.  All I can say is that, so far, she’s never once confused quantum computing with classical exponential parallelism, treated relativization as acting on a complexity class rather than on its definition, or made any other mathematical mistake that I can see.  (She has, on the other hand, repeatedly mistaken her hand for food.)

Follow

I’m in Edinburgh this week to visit my wonderful old friends Elham Kashefi and Rahul Santhanam, and to give a series of talks.  It’s my first visit to my “ancestral homeland,” and as you can see above, I’ve enjoyed visiting my namesake monument and eating some freshly-ground haggis.

Earlier today, I was delighted to meet the matrix-multiplication-exponent-lowerer and unwilling Shtetl-Optimized celebrity Andrew Stothers, and to treat him to lunch.  (I’d promised to buy Andrew a beer if I was ever in Edinburgh, to apologize for the blog-circus I somehow dragged him into, but he only wanted a diet Coke.)  I’m now convinced that Andrew’s not publicizing his lowering of ω was mostly a very simple matter of his not being in contact with the theoretical computer science community.  One factor might be that, here at U. of Edinburgh, the math and CS buildings are on different campuses two miles away from each other!

I apologize for the light-to-nonexistent blogging.  To tide you over until I have time to post something real, here are some extremely-interesting quantum information papers that appeared on the arXiv just recently: A multi-prover interactive proof for NEXP sound against entangled provers by Tsuyoshi Ito and my postdoc Thomas Vidick, and Bell’s Theorem Without Free Will by Tobias Fritz.

Follow

A few months ago, I got a surprise call from Subra Suresh, director of the National Science Foundation, who told me I was going to share this year’s Alan T. Waterman Award with Robert Wood of Harvard.  (At first I assumed it was a telemarketing call, since pretty much no one calls my office phone; I use my iPhone exclusively and have trouble even operating my desk phone.)  Dr. Suresh explained that this was the first time the Waterman would ever be awarded to two people the same year, but that the committee was unanimous in supporting both me and Rob.  Looking up my co-winner, I quickly learned that Rob was a leader in the field of robot bees (see here for video)—and that his work, despite having obvious military applications, had been singled out by Sean Hannity as the latter’s #1 example of government waste (!).  That fact, alone, made me deeply honored to share the award with Rob, and eager to meet him in person.

Happily, I finally got to do that this past Thursday, at the Waterman award ceremony in Washington DC.  The festivities started in the morning, with talks by me and Rob to the National Science Board.  (I just performed my usual shtick.  I was hoping Rob would bring some actual RoboBees, but he said he no longer does that due to an unfortunate run-in with airport security.)  Then, after lunch and meetings at the NSF, it was back to the hotel to change into a tux, an item I’d never worn before in my life (not even at my wedding).  Fortunately, my dad was there to help me insert the cufflinks and buttons, a task much more complicated than anything I was allegedly getting the award for.  Then Dana and I were picked up by a limo, to begin the arduous mile-long journey from Dupont Circle to the State Department for the awards dinner.

Besides me and Rob, there were three other awardees that night:

• Leon Lederman, the 89-year-old Nobel physicist whose popular book (The God Particle) I enjoyed as a kid, received the Vannevar Bush Award.
• Lawrence Krauss, physicist and popular science writer, and National Public Radio’s science desk shared the National Science Board Public Service Award.  Some readers of science blogs might recognize Lawrence Krauss from his recent brouhaha over literally nothing with the philosopher of science David Albert.  (For whatever it’s worth, I have little to add to Sean Carroll’s diplomatic yet magisterial summary of the issues over on Cosmic Variance.)

Speaking of diplomacy, the awards dinner was held in the “diplomatic reception rooms” on the top floor of the State Department’s Harry S. Truman Building.   These were pretty awesome rooms: full of original portraits of George Washington, Ben Franklin, etc., as well as antique furniture pieces like a desk that Thomas Jefferson allegedly used while writing the Declaration of Independence.  I could easily eat dinner there on a regular basis.

Carl Wieman, the Nobel physicist and Associate Director for Science at the White House Office of Science and Technology Policy, read out a congratulatory message from President Obama.  I feel certain the President remembered I was the same dude he shook hands with a while back.

Anyway, cutting past dinner and dessert, here was my short acceptance speech:

Thanks for this honor, and huge congratulations to my co-winners, wherever in the alphabet they might lie [a reference to my getting called up before Rob Wood, simply because Aaronson<Wood lexicographically].  I like to describe my research, on the limits of quantum computers, as the study of what we can’t do with computers we don’t have.  Why would I or anyone else study such a bizarre thing?  Mostly because we’re inspired by history.  In the 1930s, before electronic computers even existed, a few people like Alan Turing were already trying to understand mathematically what such devices would or wouldn’t be able to do.  Their work ultimately made possible the information age.  Today, we don’t know exactly where curiosity about (say) quantum computers or the P versus NP question is going to lead, but I’m grateful to live in a country that’s able to support this kind of thing.  I thank the NSF and the Obama administration for supporting basic science even in difficult times.  I thank Subra Suresh (my former dean at MIT), and my phenomenal program officer Dmitry Maslov.  I thank the teachers and mentors to whom I owe almost everything, including Chris Lynch, Bart Selman, Avi Wigderson, and Umesh Vazirani.  I thank my wonderful colleagues at MIT—including my department head Anantha Chandrakasan, who’s here now—and my students and postdocs.  I thank my collaborators, and the entire theory of computing and quantum information communities, which I’m so proud to be part of.  I thank my students in 6.045 for understanding why I had to miss class today.  Most of all, I thank four people who are here with me now—my mom, dad, and my brother David, who’ve always believed in me, whether justified or not, and my wife, Dana Moshkovitz Aaronson, who’s enriched my life ever since she came into it three years ago.  Thank you.

The next day, I had the privilege of giving a quantum computing talk to more than 100 students at the Thomas Jefferson High School for Science and Technology in nearby Alexandria, VA.  Visiting TJ had special meaning for me, since while I was suffering through high school, TJ was my “dream school”: I wished my parents lived in the DC area so that I could go there.  I told the TJ students never to forget just how good they had it.  (To this day, when I meet fellow American-raised scientists, and they tell me they’re surprised I had such an unhappy time in high school, since they themselves had a great time, I always ask them which high school they went to.  In a large fraction of cases, the answer turns out to be TJ—and when it isn’t, it’s often the Bronx High School of Science or another similar place.)  As should surprise no one, the students had vastly more detailed questions about my talk than did the National Science Board (for example, they wanted to know whether I thought progress in group theory would lead to new quantum algorithms).

Without doubt, the most surreal aspect of this trip was the contrast between what was going on in my “real” and “virtual” lives.  Again and again, I’d be shaking hands with the Undersecretary of Defense, Director of the National Institute of Prestigiousness, etc. etc., and warmly accepting these fine people’s congratulations.  Then I’d sneak away for a minute to moderate my blog comments on my iPhone, where I’d invariably find a fresh round of insults about my “deeply ignorant lesser brain” from entanglement denier Joy Christian.

Perhaps the funniest contrast had to do with a MathOverflow question that I posted just before I left for DC, and which was quickly answered, just as I had hoped.  During the limo ride back from the dinner, I got the following polite inquiry from a blog commenter calling himself “Mike”:

Hey Scott, I’m wondering how you got the courage to post that question on [MathOverflow]. In truth it wasn’t that hard of a question and if you have trouble solving it then…well, no offense, but you see what I mean. Reputation matters.

As I contemplated Mike’s question, a profound sense of peace came over me.  Probably for the first time in my life, I realized just how lucky I really am.  I’m lucky that I feel free to ask naïve, simpleminded questions, toss out speculations, and most importantly, admit when I don’t know something or made a mistake, without worrying too much about whether those actions will make me look foolish before the “Mikes” of the world.  If I want to work on a problem myself, I can do that; if I prefer giving the problem out to others, I can do that as well.  Let Mike, with his greater wisdom, sit in judgment of me for my failure to see all the answers that no doubt are obvious to him.  I don’t mind.  In science, like in everything else, I’ll continue being an unabashed doofus—partly because it seems to work OK, but mostly just because it’s the only way I know.

Thanks so much to all of you for your support.

Follow

I’m blogging from Machu Picchu, the famed summer home of the Inca emperors, nestled so deeply in the Andean mountains of Peru that the Spanish conquistadores never managed to find and destroy it. (I’m in Peru to attend the LATIN’2012 conference next week. It’s a business trip, I swear!)

I’ll be happy to post photos later if anyone wants.  In the meantime, this just seemed like as good a time as any to break radio silence.

Follow

Last week I was in Vancouver, to give talks at the University of British Columbia and at the American Association for the Advancement of Science annual meeting.  As part of that visit, on Friday afternoon, John Preskill, John Martinis, Michael Freedman and I accepted a gracious invitation to tour the headquarters of D-Wave Systems in Burnaby (a suburb of Vancouver).  We started out in a conference room, where they served us cookies and sodas.  Being the mature person that I am, the possibility of the cookies being poisoned at no point crossed my mind.

Then we started the tour of D-Wave’s labs.  We looked under a microscope at the superconducting chips; we saw the cooling systems used to get the chips down to 20 millikelvin.  In an experience that harked back to the mainframe era, we actually walked inside the giant black cubes that D-Wave was preparing for shipment.  (The machines are so large partly because of the need for cooling, and partly to let engineers go in and fix things.)  Afterwards, D-Wave CTO Geordie Rose gave a 2-hour presentation about their latest experimental results.  Then we all went out to dinner.  The D-Wave folks were extremely cordial to us and fielded all of our questions.

In spite of my announcement almost a year ago that I was retiring as Chief D-Wave Skeptic, I thought it would be fitting to give Shtetl-Optimized readers an update on what I learned from this visit.  I’ll start with three factual points before moving on to larger issues.

Point #1: D-Wave now has a 128-(qu)bit machine that can output approximate solutions to a particular NP-hard minimization problem—namely, the problem of minimizing the energy of 90-100 Ising spins with pairwise interactions along a certain fixed graph (the “input” to the machine being the tunable interaction strengths).  So I hereby retire my notorious comment from 2007, about the 16-bit machine that D-Wave used for its Sudoku demonstration being no more computationally-useful than a roast-beef sandwich.  D-Wave does have something today that’s more computationally-useful than a roast-beef sandwich; the question is “merely” whether it’s ever more useful than your laptop.  Geordie presented graphs that showed D-Wave’s quantum annealer solving its Ising spin problem “faster” than classical simulated annealing and tabu search (where “faster” means ignoring the time for cooling the annealer down, which seemed fair to me).  Unfortunately, the data didn’t go up to large input sizes, while the data that did go up to large input sizes only compared against complete classical algorithms rather than heuristic ones.  (Of course, all this is leaving aside the large blowups that would likely be incurred in practice, from reducing practical optimization problems to D-Wave’s fixed Ising spin problem.)  In summary, while the observed speedup is certainly interesting, it remains unclear exactly what to make of it, and especially, whether or not quantum coherence is playing a role.

Which brings me to Point #2.  It remains true, as I’ve reiterated here for years, that we have no direct evidence that quantum coherence is playing a role in the observed speedup, or indeed that entanglement between qubits is ever present in the system.  (Note that, if there’s no entanglement, then it becomes extremely implausible that quantum coherence could be playing a role in a speedup.  For while separable-mixed-state quantum computers are not yet known to be efficiently simulable classically, we certainly don’t have any examples where they give a speedup.)  Last year, as reported on this blog, D-Wave had a nice Nature paper that reported quantum tunneling behavior in an 8-qubit system.  However, when I asked D-Wave scientist Mohammad Amin, he said he didn’t think that experiment provided any evidence for entanglement between qubits.

The “obvious” way to demonstrate entanglement between qubits would be to show a Bell inequality violation.  (We know that this can be done in superconducting qubits, as the Schoelkopf group at Yale among others reported it a couple years ago.)  Meanwhile, the “obvious” way to demonstrate a role for quantum coherence in the apparent speedup would be gradually to “turn down” the system’s coherence (for example, by adding an interaction that constantly measured the qubits in the computational basis), and check that the annealer’s performance degraded to that of classical simulated annealing.  Unfortunately, the D-Wave folks told us that neither experiment seems feasible with their current setup, basically because they don’t have arbitrary local unitary transformations and measurements available.  They said they want to try to demonstrate 2-qubit entanglement, but in the meantime, are open to other ideas for how to demonstrate a quantum role in the apparent speedup with their existing setup.

Point #3: D-Wave was finally able to clarify a conceptual point that had been bugging me for years.  I—and apparently many others!—thought D-Wave was claiming that their qubits decohere almost immediately (so that, in particular, entanglement would almost certainly never be present during the computation), but that the lack of entanglement didn’t matter, for some complicated reason having to do with energy gaps.  I was far from alone in regarding such a claim as incredible: as mentioned earlier, there’s no evidence that a quantum computer without entanglement can solve any problem asymptotically faster than a classical computer.  However, that isn’t D-Wave’s claim.  What they think is that their system decoheres almost immediately in the energy eigenbasis, but that it doesn’t decohere in the computational basis—so that, in particular, there would be entanglement at intermediate stages.  If so, that would be perfectly fine from the standpoint of the adiabatic algorithm, which doesn’t need coherence in the energy eigenbasis anyway (after all, the whole point is that, throughout the computation, you want to stay as close to the system’s ground state as possible!).  I understand that, given their knowledge of decoherence mechanisms, some physicists are extremely skeptical that you could have rapid decoherence in the energy basis without getting decoherence in the computational basis also.  So certainly the burden is on D-Wave to demonstrate that they maintain coherence “where it counts.”  But at least I now understand what they’re claiming, and how it would be compatible (if true) with a quantum speedup.

Let me now move on to three broader questions raised by the above points.

The first is: rather than constantly adding more qubits and issuing more hard-to-evaluate announcements, while leaving the scientific characterization of its devices in a state of limbo, why doesn’t D-Wave just focus all its efforts on demonstrating entanglement, or otherwise getting stronger evidence for a quantum role in the apparent speedup?  When I put this question to Mohammad Amin, he said that, if D-Wave had followed my suggestion, it would have published some interesting research papers and then gone out of business—since the fundraising pressure is always for more qubits and more dramatic announcements, not for clearer understanding of its systems.  So, let me try to get a message out to the pointy-haired bosses of the world: a single qubit that you understand is better than a thousand qubits that you don’t.  There’s a reason why academic quantum computing groups focus on pushing down decoherence and demonstrating entanglement in 2, 3, or 4 qubits: because that way, at least you know that the qubits are qubits!  Once you’ve shown that the foundation is solid, then you try to scale up.  So, please support D-Wave if it wants to spend money to show Bell inequality violations, or other “smoking-gun” evidence that its qubits are working together coherently.  You’re welcome, D-Wave!

The second question is one that I’ve encountered many times on the blogosphere: who cares how D-Wave’s system works, and whether it does or doesn’t exploit quantum coherence, as long as it solves practical problems faster?  Sure, maybe what D-Wave is building is really a series of interesting, useful, but still basically “classical” annealing devices.  Maybe the word “quantum” is functioning here as the stone in a stone soup: attracting money, interest, and talented people to build something that, while neat, ultimately doesn’t much depend on quantum mechanics at all.  As long as D-Wave’s (literal!) black box solves the problem instances in such-and-such amount of time, why does it matter what’s inside?

To see the obtuseness of this question, consider a simple thought experiment: suppose D-Wave were marketing a classical, special-purpose, $10-million computer designed to perform simulated annealing, for 90-bit Ising spin glass problems with a certain fixed topology, somewhat better than an off-the-shelf computing cluster.  Would there be even 5% of the public interest that there is now?  I think D-Wave itself would be the first to admit the answer is no.  Indeed, Geordie Rose spoke explicitly in his presentation about the compelling nature of (as he put it) “the quantum computing story,” and how it was key to attracting investment.  People don’t care about this stuff because they want to find the ground states of Ising spin systems a bit faster; they care because they want to know whether or not the human race has finally achieved a new form of computing.  So characterizing the device matters, goddammit!  I pride myself on being willing to adjust my opinions on just about anything in response to new data (as I’ve certainly done in D-Wave’s case), but the insistence that black boxes must be opened and explanations provided is something I’ll carry to the grave.

Finally, given the skeptical-yet-positive tone of this post, some people will wonder whether I now regret my earlier, more unmitigated D-Wave skepticism.  The answer is no!  Asking questions is my job.  I’ll give D-Wave credit whenever it answers some of the questions—as it did on this visit!—and will shift my views accordingly.  But I’ll also neither stop asking nor apologize for asking, until the evidence for a quantum speedup becomes clear and indisputable (as it certainly hasn’t yet).  On the other hand, I do regret the snowballing nastiness that developed as a combined result of my and other skeptics’ statements, D-Wave’s and its supporters’ statements, and the adversarial nature of the blogosphere.  For the first time, I find myself really, genuinely hoping—with all my heart—that D-Wave will succeed in proving that it can do some (not necessarily universal) form of scalable quantum computation.  For, if nothing else, such a success would prove to the world that my $100,000 is safe, and decisively refute the QC skeptics who, right now, are getting even further under my skin than the uncritical D-Wave boosters ever did.

Follow

(Credit for most of the photos: Dana)

I was going to write a whole long essay about

• the differences between going to the zoo and visiting an ancestral environment of humanity, where elephants have grazed for millions of years;
• the weird sense of familiarity, as if you’re seeing how the surface of the earth is “supposed” to look, how it did look before humans started converting it into KFCs and parking lots;
• how to tell whether an elephant charging your jeep is serious about wanting to trample you or, much more likely, just warning you to go away (apparently, it has to do with whether its ears are straight back or flapping);
• the “airport” at Lake Naivasha (a strip of dirt in a grassy field filled with zebras, and a guy on a bicycle who shoos the zebras off the strip before a plane lands);
• Britain’s failure, to this day, to issue any sort of apology for its detention, torture, and murder of tens of thousands of Kenyans during the waning years of its colonial rule in the 1950s;
• the near-destruction by poaching, over the last century, of many of the majestic animal populations you see above;
• the heroism of Richard Leakey (past director of the Kenya Wildlife Service) in overcoming decades of bureaucratic inertia to initiate a crackdown, where rangers were authorized to “poach the poachers,” shooting them on sight (!);
• how, after Leakey almost-singlehandedly saved Kenya’s wild elephants, he lost both of his legs when his plane crashed (widely suspected to be due to sabotage), and was forced from his job months later;
• the benefits of safari tourism in creating a serious economic incentive for conservation, but also the drawbacks (e.g., all the jeeps making it harder for the cheetahs to hunt);
• the large, obvious, anything-but-“theoretical” changes being wrought by global warming on the rainfall in Kenya’s game parks (which changes are killing the trees, thereby eliminating the lions’ hiding places and making it harder for them to hunt—hey, at least the zebras are happy);
• the Maasais’ innovative uses for cow dung; the resulting immature jokes on my part (homeowner to roofer: “this roof you sold me is shit!”);
• my growing fascination, over the course of the trip, with the lesser-known corners of Mammalia (elands, dik-diks, kudus, waterbucks, topis, rock hyraxes); how this might mirror my fascination with lesser-known complexity classes like AWPP, QMA(2)/qpoly, SBP, C₌P, and BPP_path;
• how parts of the African savannah have better cellphone reception than my office in Stata;
• how it’s indeed possible to catch up on Jon Stewart and The Big Bang Theory over wifi, from a tent in the Maasai Mara, while hippos bellow loudly in the river below, and elephants graze and crocodiles sun themselves on the other side.

But then I never got around to writing that essay.  So enjoy the photos, and ask in the comments if you want me to say something else.

Follow

Ho³!  Home with family for the holidays and looking for something to do?  Then check out the archives of our 6.893 Philosophy and Theoretical Computer Science course blog.  The course just ended last week, so you can find discussions of everything from the interpretation of quantum mechanics to Occam’s Razor to the Church-Turing Thesis to strong AI, as well as links to student projects, including Criticisms of the Turing Test and Why You Should Ignore (Most of) Them, Barwise Inverse Relation Principle, Bayesian Surprise, Boosting, and Other Things that Begin with the Letter B, and an interactive demonstration of interactive proofs.  Thanks to my TA Andy Drucker, and especially to the students, for making this such an interesting course.

Follow