A year ago, I relinquished my dictatorial control of the Complexity Zoo, accepting an offer from John Stockton to convert the Zoo into wiki format. Unfortunately, the wiki site has been down for days and shows no signs of coming back anytime soon. So for now, I’ve put the old Zoo back up at www.complexityzoo.com. I’ve learned my lesson: in times of crisis, it takes a leader with an iron fist to keep the trains running on time and the animals in their cages.
John Baez is back on the scene, with an account of his recent visit to our quantum computing group at Waterloo. Among other things, he gives a lucid explanation of how, while it’s generally impossible to keep information from leaking out of a computer, it is possible to arrange things so that the information that does leak is irrelevant to the computation. Baez links to the papers that prove this is true for quantum computing as well as classical, but complains that “most of it speaks the language of ‘error correction’ rather than thermodynamics.” Question for the audience: can the fault-tolerance theorems be reproved more physicsly? (“We now define a PHYSICAL SYSTEM called the concatenated Steane code…”)
Baez’s semi-conversion to the Church of Knill, Laflamme, and Zurek (or the Shul of Aharonov and Ben-Or) has inspired me to propose a far-reaching hypothesis:
While it’s generally impossible to explain computer science concepts to physicists so that they understand them on your terms, it is sometimes possible to explain them so that they understand on their terms.
Naturally, it helps if the physicist in question is Baez.