I’m at the QIP (quantum information processing) 2005 workshop in Boston, which is being hosted by MIT.

I’m not going to be blogging the workshop, but might mention a few tidbits here and there.

In this morning’s session, Andrew Childs gave a talk about the dihedral hidden subgroup problem (DHSP).

This is an important problem: it’s likely to be hard on a classical computer, and it’s widely regarded as a good candidate for efficient solution on a quantum computer. It’s also connected to important problems in computer science, like finding the shortest vector in a lattice, which have cryptographic applications.

It’s a little difficult to give a brief and accessible overview of what the DHSP is about, but I can at least sketch what progress Andrew and his collaborators have made toward a fast quantum algorithm.

In the first part of his talk, Andrew showed that the DHSP can be reduced to performing a measurement to distinguish certain easily-prepared quantum states.

The difficulty of DHSP then lies in (a) figuring out whether there even exists a measurement which is capable of distinguishing those states, (b) if one does exist, figuring out what the best measurement is (or at least a pretty good one), and (c) figuring out whether or not that measurement can be implemented efficiently on a quantum computer.

Andrew answered part (a) and (b), explicitly constructing a measurement (the “pretty good measurement”) which he can prove is the best possible measurement for distinguishing those states.

Andrew has also made some progress on part c, but no efficient implementation yet exists. Nonetheless, solving part (a) and (b) does represent encouraging progress on this important problem.

Riley Perry has written a free introductory online book on quantum computing that he described to me as “quantum computing for dummies”.

It’s essentially an undergraduate text, and contains many of the topics (intro to quantum mechanics, basics of the quantum circuit model, Shor and Grover algorithms) that are essential to an understanding of quantum computing, as well as some more advanced topics.

I’ve only thumbed through it, but it looks to present many topics in a very clear and comprehensible way.

Asher Peres, one of the pioneers of quantum information theory, and a notable contributor to many other areas of physics, passed away a few days ago.

Asher was, among many other things, and in no particular order:

• Very kind and encouraging to a certain very young quantum information theorist he met at the Institute for Theoretical Physics in Santa Barbara in 1996.
• Passionate about physics, with a very independent point of view.
• The author of a wonderful textbook on the foundations of quantum mechanics, which I strongly recommend to anyone who’s taken a basic course in quantum physics.

  In 1994 I was doing my undergraduate thesis on Bell’s inequality and possible connections to quasidistribution functions. Excepting Bell’s orignal paper and some papers by Mermin, I was having a hard time finding much that was clear on Bell’s inequality, or its various more modern versions.

  Then Asher’s book arrived at our library.

  Revelation! Suddenly, all the key results of 30 years of work (several of those results due to Asher) were distilled into beautiful and simple explanations.

  The other parts of the book are just as good.

• One of the originators of the famous Peres-Horodecki criterion for deciding when a quantum state is entangled.
• One of the originators of quantum teleportation.

I didn’t know Asher all that well – we talked more than passingly on only a few occasions – but I have several warm memories of our interactions.

One was in 2000. I had posted a paper to the preprint archive entitled “On the units of bipartite entanglement: is sixteen ounces always equal to one pound?”

I had recently left a job at Caltech when I posted that paper. Caltech runs JPL, who at the time were still very embarassed by the loss of the Mars Lander, due to, of all things, a now-famous mistake in unit conversion.

Shortly after posting the paper, I got a little note in email from Asher that brightened my day and still makes me smile. I post it here because it seems to me very much in Asher’s voice as I knew it:

“Sixteen ounces? One pound?
Don’t people at Caltech know about SI units? Best regards, Asher”

I’m away for the next couple of days. Since comment spamming seems to be getting much worse, I’m turning off comments in the interim. I’ll probably install some kind of comment previewing when I get back.

On a more scientific note, while I enjoyed many of the talks at the workshop, one stood out for me by far: Ignacio Cirac’s.

Briefly, Cirac talked about a bundle of new methods he and others have been developing in order to simulate quantum systems on conventional classical computers.

Doing such simulations is extremely hard in general, and there are very few quantum systems we can simulate effectively.

This failure is important. The ability to simulate classical systems numerically started in the 1930s and 1940s with the advent of computers, and it has completely revolutionized our understanding of those systems. Because of the difficulty in simulating quantum systems, we’re still effectively stuck back in about the mid-40s with those systems, except in a few special cases.

Cirac talked about the new methods he and many others are developing, based on quantum information theory, for simulating such systems. The details are complex, but the idea is pretty simple: that to do such simulations effectively, the programs must take into account both the ordinary (essentially classical) degrees of freedom, as well as the entangled degrees of freedom.

This is a simple idea, but by pushing on it, people are starting to get some spectacular results. Cirac described a slew of systems that can now be understood using these techniques, and that were previously inaccessible numerically.

It’s early days yet, but if this success continues, it’ll certainly greatly enhance our understanding of complex quantum systems, and mark what may be the first major contribution of quantum information to another field of physics.

Back from Pisa.

Obligatory comments on the Tower: it leans, surprisingly much so. No, I didn’t drop anything from the top, although it is tempting. The best thing about the Tower isn’t actually going up to the top, although the view is good, and the inside of the Tower is interesting, if you haven’t seen that kind of thing before (which I hadn’t).

No, the best thing is the view of the Tower from outside, which is much more striking and unique. Best of all, it’s free, not 15 Euros, which is what a trip to the top costs.

Of course, as a third option, you can do what the couple ahead of me in line did. Namely, they paid their 30 Euros, and then decided on the second step up that the inside of the Tower made them claustrophobic, so they quit.

Another interesting event was in the Pisa airport cafe, where I sat down beside what turned out to be some kind of major Italian star, probably a soccer player. At least, he was about 22 or 23, didn’t have movie star good looks (then again, neither do a lot of male movie stars), and he was recognized by essentially every person who looked anywhere near him. I figure soccer is a good bet.

Pretty quickly a crowd started to gather, of people wanting autographs, photos, or just a chance to chat. He took it in extraordinarily good grace. Admittedly, there’s a lot of 23 year old men who wouldn’t find it overly taxing when young women come up and put their arms around them, asking for a photo. (In a few instances, the looks he got were absolutely smoldering.)

With that said, he dealt with all ages and all types with a lot of patience and good will, particularly the few who were tiresome. Outstanding in this category were the snot-nosed brat who complained and kept butting in, and the elderly grandmother who kept him occupied for a good 15-20 minutes, apparently SMSing messages to every single person she’d ever met. So far as I can tell, he was pretty much infinitely patient, and he certainly earned my admiration as a result, although I have no idea who he was.

I’m away in Pisa next week, for a conference. So I’ll be continuing my recent theme of silence. I’ve a bunch of posts I’d like to make, but they’re taking second place to some other priorities at the moment.

A few years back John Horgan published a provocative book “The End of Science”. Here’s Phil Anderson’s take on it. (Anderson, for those who don’t know, was probably the leading condensed matter physicist of the twentieth century.)

David Harris points me to Symmetry Magazine, now in its second issue.

More thoughtful commentary on the US elections from physicist Carl Caves.

Google Scholar. It doesn’t find everything – hardly surprising – but it did find interesting things I didn’t previously know about, on topics where I thought I knew the literature. Count me as impressed, and likely to use it further.

Via Patrick Nielsen Hayden and Dave Bacon.

Update: Well. Having just replied to a referee report, I can say that “Google Scholar” was exceedingly useful. Now it just needs to be linked to amazon.com’s “look inside a book”, wikipedia, MathWorld, and PlanetMath.

It also appears to be a great way of constructing reading lists: search for your topic of interest, and look to see what comes up first. Eventually, pagerank may be a better measure of impact and utility than citations. Describing potential problems caused by this is left as an exercise for the reader…

There’s lots of fun and exciting things about blogs. Yes, I know there’s lots of hype (“journalism as we know it is OVER!”), but there’s also something important there, and it’s worth thinking about what is worthwhile. Here’s a few thoughts.

Blogs are opening up communities. Let me give as an example one of the most abstract, technical, and, until very recently, isolated communities in existence: the quantum gravity community. Nowadays, if you’re interested in quantum gravity, you can go and look at blogs by people like John Baez, Jacques Distler, Peter Woit, or the String Coffee Table. The great thing about these blogs is that you can get something out of them even if you’re not part of the community of people who work on quantum gravity. You can figure out what’s bothering people in that community, what the real problems are, what’s exciting, what’s controversial, and so on.

A related point is that blogs are providing an excellent forum for folklore and for simple ways of understanding and organizing existing knowledge. It is unfortunately true that in any field there’s all kinds of folklore and ways of understanding that, ordinarily, you have to be part of that community to know, preferably via an apprenticeship (i.e., a PhD) to a master in that field.

A good example for me is my effort to learn various bits of condensed matter physics over the past few years. Often I’ll get stuck at some particular point, sometimes for months. I’ll talk to a condensed matter physicist, and they’ll say “Oh the way to understand that is [blah, blah, blah]”, and clear up my concern in five minutes. I’ll say “Is there anywhere that’s written down?”, and they’ll say “No, everyone just knows it”. Of course, by “everyone” they mean the people who are actually inside the condensed matter community. In the current academic publishing world, there’s all sorts of reasons this kind of informal folklore and understanding don’t get written up. This is fine if you’ve got the ear of experts in all sorts of fields, and can just go ask them to clear up your difficulties, but it’s a little discouraging for the rest of us.

I hope (and see some encouraging reasons to believe) that blogs will help alleviate this. The kind of thing I’m thinking of is, for example, Lance Fortnow’s regular “theorem of the month”, often accompanied by an explanation of the ideas used in the proof, or the significance of the result. If you’re deep inside the theoretical computer science community no doubt much of this stuff is well known to you. But if you’re outside, but interested, then Lance’s writings provide a window into that field that formerly didn’t exist.

Finally, blogs also humanize the experts. It’s fun to go visit the blog of renowned computer pioneer Dan Bricklin, and hear him gushing enthusiastically about things like the Segway, or talking about his photo hobby.

There’s a lot of ways in which our society has become more and more specialized over the past few centuries. This has always bugged me, but I now hope that blogs will help reverse that trend, helping create communities that are larger, more transparent, and more porous than before.

Update: In the comments Seb Paquet points to a great essay he wrote on this topic.