Two John-related announcements
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.
Follow
Comment #1 July 17th, 2006 at 2:07 am
A clarification, to head off the inevitable complaints: any “physicist” who attends QIP is in actuality a computer scientist.
Comment #2 July 17th, 2006 at 4:09 am
The same could be said about explaining anything to anyone.
Comment #3 July 17th, 2006 at 10:41 am
Yes, of course that’s right — Mark Twain said that “there are no dialogues, only intersecting monologues.” But if you really want to experience some tenuously-intersecting monologues, try telling a physicist that “by assumption, the model is as follows…”
Comment #4 July 17th, 2006 at 11:27 am
As Scott notes, computer scientists like to think in terms of logic and algorithms, while physicists like Baez prefer to think in terms of dynamical processes.
Isn’t geometry the mathematical arena in which these these two points of view strongly overlap?
Compare, e.g., Steven Smale’s Fourth and Sixth Problems for the 21st Century:
Smale Problem 3: Does P=NP? (see Smale’s original paper here).
Smale Problem 6: Finiteness of the number of relative equilibria in celestial mechanics (see Richard Montgomery’s review here).
The point being, that if computations are physical dynamical processes with geometric state spaces, then complexity questions like Smale Problem (3) can be attacked by the powerful geometric methods that were originally devised to attack dynamical questions like Smale Problem (6).
For me, the most enjoyable aspect of geometric complexity theory is the incredible animations … such pictorial representations are proving to be fruitful in the study of subriemannian quantum MOR geometries on Kahler spaces, which in turn are of great interest in engineering simulations of quantum systems.
There! That’s my promised once-a-week contribution to Scott’s excellent blog … and as promised, its mostly links to other work.
Thank you, Scott, for providing such wonderfully interesting and thought-provoking topics. And thanks also to “anonymous”, for provoking me to think about what makes a great blog great.
Comment #5 July 17th, 2006 at 12:28 pm
I can’t say that I find this explanation very satisfying. You could call it “physicists are from Mars, computer scientists are from Venus.” I was at Mike Freedman’s quantum computation conference in Santa Barbara a couple of months ago, and there were plenty of physicists there who understood quantum computation. There is also no shortage of computer scientists who aren’t prepared to accept QC. Yes, the physicists have somewhat different vocabulary. But it isn’t necessarily all that different. After all, Kitaev and Preskill are physicists, among others.
Either you are prepared to believe QC, or you aren’t. I think that everyone should be prepared to believe it, but there is always that outside chance that the believers are all wrong for some unkown reason. What can be said is that the skeptics have made little progress in finding the fundamental obstacle. The believers have made much more progress, even though their work is grossly incomplete. You see a lot of these same issues with string theory.
I agree, though, that it always helps to adapt to your audience’s terminology. But I think that it is a mistake to shoehorn your real ideas into someone else’s prior mode of thinking. Good ideas are observer-independent, and do not benefit from strained analogies.
Comment #6 July 17th, 2006 at 2:58 pm
“Either you are prepared to believe QC, or you aren’t. I think that everyone should be prepared to believe it,”
Better said: “Either you are prepered to believe it OR you are prepared to disbelieve it.” OR in the logic/CS sense, not XOR.
“but there is always that outside chance that the believers are all wrong for some unkown reason.”
ALL wrong? seems extremely unlikely. If the chance a single believer being wrong is
Comment #7 July 17th, 2006 at 5:34 pm
Re: The complexity zoo, I have to ask, what’s the deal with S2-EXP•PNP
Comment #8 July 17th, 2006 at 6:52 pm
ALL wrong? seems extremely unlikely. If the chance a single believer being wrong is
In the future, I will delete comments that calculate a joint probability using an unjustified independence assumption.
Comment #9 July 17th, 2006 at 6:54 pm
Re: The complexity zoo, I have to ask, what’s the deal with S2-EXP•PNP
I was wondering the same thing.
Comment #10 July 17th, 2006 at 7:02 pm
(Seriously: Samik Sengupta gave a rump session talk about it at a previous Complexity conference. See this paper.)
Comment #11 July 17th, 2006 at 7:16 pm
In the future, I will delete comments that calculate a joint probability using an unjustified independence assumption.
Did you know the odds of four golfers scoring a hole in one on the same hole in two hours? 1.89 quadrillion, according to a HARVARD MATHEMATICIAN.
It is important to appeal to authorities such as Harvard before handling numbers as large as a quadrillion.
Comment #12 July 18th, 2006 at 7:38 am
The relation between error correction and thermodynamics is an interesting question in both the classical and quantum cases. I don’t think one can really derive error correction from thermodynamics because the latter depends too much on the precise details of physical implementation whereas the former is designed to apply to abstract computing models, which might be implemented in any number of ways. Rather, error correction is based on a less-detailed, simplified set of “reasonable” assumptions that we hope capture enough of the physics to be meaningful.
I am reminded here of Hilbert’s sixth problem, which is to provide a rigorous mathematical axiomatization of all of physics. Any attempt at doing this seems fated to miss a lot of the details, but perhaps it would simultaneously give greater insight into structural properties of physical theories, and help adress problems like the above.
Comment #13 July 18th, 2006 at 1:19 pm
The relation between error correction and thermodynamics is an interesting question in both the classical and quantum cases.
Len Schulman’s nice work on dynamic cooling reminded me that thermodynamics is a set of universal truths that does shed light on quantum error correction. You can think of error correction as cooling the qubits to zero temperature.
However, quantum error correction is a very exotic physical system that does defy some of the natural intuition of thermodynamics, just as QC may defy the intuition of the “strong Church-Turing thesis”. In both cases, this prior intuition doesn’t seem to be particularly well supported.
What I always like to ask about thermodynamic objections to QEC is, why doesn’t the proposed objection also apply to classical error correction? Of course there are differences between CEC and QEC, but it is not so easy to sketch an argument that fundamentally depends on these differences.
Comment #14 July 18th, 2006 at 8:09 pm
“You can think of error correction as cooling the qubits to zero temperature.”
No, not zero temperature. Just a temperature low enough that the order parameter for the information you are storing is not disordered. (For example, you don’t need to keep your hard drive at absolute zero, you just need to keep it cold enough such that you don’t disorder the magnetic domains.)
Comment #15 July 18th, 2006 at 8:13 pm
clarification, to head off the inevitable complaints: any “physicist” who attends QIP is in actuality a computer scientist.
Shouldn’t that be: any “computer scientist” who attends QIP is actually a physicist?
Perhaps we need a new word to describe these strange hybrid beasts. “Computer physicist”? “Computer science physicist”? “Physicist computer scientist”? “Compuphysicist”?
Comment #16 July 21st, 2006 at 5:03 am
“the chance they are ALL wrong is less than 1/10^1000 ! ”
This is wrong ! It should be 1/10^1000 and not 1/10^1000 !
Comment #17 July 24th, 2006 at 11:41 pm
Scott, have you studied Smale’s mathematical model of a Turing machine and has it given you any new insights?
Comment #18 July 25th, 2006 at 1:12 am
Are you talking about the Blum-Shub-Smale model? If so, then yes — I’ve studied it with great interest. I haven’t yet found a use for it in my own work, but maybe that will change.
Comment #19 July 25th, 2006 at 2:23 am
“Are you talking about the Blum-Shub-Smale model?”
Yes but i think Smale calls it BCSS – doesn’t he?
“I haven’t yet found a use for it in my own work, but maybe that will change.”
Hmm….do you think that is because BCSS seems foreign?
Comment #20 July 25th, 2006 at 1:08 pm
Yes but i think Smale calls it BCSS – doesn’t he?
Right (the C is Cucker, who was a later coauthor).
“I haven’t yet found a use for it in my own work, but maybe that will change.”
Hmm….do you think that is because BCSS seems foreign?
No, not at all. It’s just because I haven’t done much involving arithmetic or algebraic complexity.