The physicists and the wagon
[Here’s a little fable that I wrote today, while listening to a talk “showing” that a fault-tolerant quantum computer would need at least 100 physical qubits for every logical qubit. Physicists are welcome to shoot back with counter-fables, as are closet computer scientists like His Holiness.]
Update: The Pontiff has accepted my challenge and posted a counter-fable to his blog. I’ve replied in his comments section with a counter-counter-fable.
One day a group of physicists ran excitedly into the computer science building. “Guess what?” they cried. “You know how you’re always trying to prove lower bounds, but you almost never succeed? Well, today we proved a lower bound!”
“What did you prove?” asked the computer scientists.
“We proved that to pull a wagon through a forest, you need at least five oxen. It’s physically impossible to do it with four oxen or less, regardless of what other resources you have.”
“How did you prove that?”
“Well, we looked up the strength of a typical ox, the weight of a typical wagon, the size of every forest in a 30-mile radius…”
“Yeah, but what if you had an ox the size of a Brontosaurus? Or what if the forest was only two feet across? Or what if the wagon weighed less than a fingernail?”
The physicists snickered. “These are clearly unphysical assumptions. As long as you stay within a realistic region of parameter space, our impossibility proof is airtight.”
“Ah, but how do you know there couldn’t be some completely different method of pulling wagons — maybe even a method that’s not ox-based at all?”
“Look, we physicists are interested in the real world, not complexity-theory la-la land. And at least in the real world, when people want to pull wagons, oxen are what they use.”
The physicists weren’t heard from again until almost a decade later, when they once again barged into the CS building. “Guess what?” they cried. “We just discovered a loophole in the famous Five-Ox Theorem — the one we published years ago in Nature!”
“What’s the loophole?”
“Elephants! If you had an elephant pulling the wagon, you wouldn’t need any oxen at all. With hindsight it’s almost obvious, but what a paradigm shift it took!”
The computer scientists stared blankly.
“You see,” said the physicists. “This is why we never trust so-called impossibility proofs.”
Follow
Comment #1 June 19th, 2006 at 7:07 pm
I would like to point out that in your story, a computer scientist would apparently feel totally happy refering to mythical pink elephants even if they do or do not exist. I think we call people like that “crazy.” Of course, when we discover that those pink elephants actually do exist and have real physical effects (I’ve always suspected them of causing ficticious forces), then you are no longer crazy. That is the nature of the scientific method, I’m pretty sure.
Comment #2 June 19th, 2006 at 7:19 pm
“Have you ever seen a real impossiblity proof?” the computer scientist asked. The physicists all stared around blanky. “Yeah, neither have I.”
Unfortunately the computer scientist is the moral analogue of a Bigfoot hunter.
Comment #3 June 19th, 2006 at 7:30 pm
Fabulous.
Comment #4 June 19th, 2006 at 7:33 pm
a computer scientist would apparently feel totally happy refering to mythical pink elephants even if they do or do not exist. I think we call people like that “crazy.”
Dave: Believing in mythical pink elephants is crazy, but what’s crazy about bringing them up as a counterexample to a proposed argument? (Indeed, that’s exactly what you just did. 🙂 )
Comment #5 June 19th, 2006 at 7:45 pm
Unfortunately the computer scientist is the moral analogue of a Bigfoot hunter.
Arrow’s Theorem … Turing’s Undecidability Theorem … Parity is not in AC0 … Bell’s Theorem … the No-Cloning Theorem … the Kochen-Specker Theorem … Holevo’s Theorem … the impossibility of quantum bit commitment …
Oh no, it’s BIGFOOT! And he’s come with clearly-stated formal assumptions under which the claimed impossibility holds!
(Incidentally, the above list should make it clear that some physicists — I call them “honorary computer scientists” — have understood perfectly well what an impossibility proof is.)
Comment #6 June 19th, 2006 at 8:07 pm
Don’t all of your impossibility proofs have pink elephants? (You really should have colored your animals in the story, I mean, whose ever heard of an uncolored elephant? [Joke about SU(3) self-censored.])
Of course I agree with you that listening to a physicist explain why he or she believes in such in such can be quite an excruciating experience. However, if I have to bet, I’m sorry, but I’m going to bet on the physicist. Just because he or she can’t rigorously prove they are beating the market with their hedge fund model based on path integrals doesn’t mean he’s not onto something.
Comment #7 June 19th, 2006 at 8:34 pm
Dave: I really don’t have a problem with physicists not proving anything, as long as they don’t claim to be proving things!
Incidentally, to make money at a hedge fund, you only have to beat the other traders. But to show that fault-tolerant QC requires 100 physical qubits for every logical qubit, you have to beat every possible encoding scheme with 99 qubits, including schemes that no one has ever thought of. That’s the key difference as I see it.
Comment #8 June 19th, 2006 at 8:43 pm
“Can we get along here? Can we all get along?” Rodney King, 1991
Comment #9 June 19th, 2006 at 10:44 pm
> Just because he or she can’t rigorously prove they are beating the market with their hedge fund model based on path integrals doesn’t mean he’s not onto something.
I think Dave is onto something.
Comment #10 June 19th, 2006 at 11:24 pm
Some people here seem to believe that, unlike proofs in physics, mathematical proofs are HUNDRED PER CENT tight. Well, just because 10/1000/10^n people, after reading a certain paper, spotted no errors in it, does not warrant that the errors aren’t there. Not to mention that all of you might be hypnotized by a pink elephant, who just for the fun of it, makes you think you are computer scientists.
Comment #11 June 20th, 2006 at 12:08 am
The kind of issue that I have seen is more like the following:
*The physicists, reasoning about average oxen, taking the limit approaching 0 of the derivative of a function that is only defined for integral values, and then approximating its value by the first few terms of a divergent series determine that at least 4.1 oxen are required.
*The computer scientists then prove rigorously that at least 4 oxen are required.
* The physicists then tweak the calculation by taking a few more terms to determine that the predicted value was really 4 in the first place and credit the computer scientists’ proof as “supporting evidence” for their prediction.
Comment #12 June 20th, 2006 at 12:23 am
Oh, Scott and I have no problem getting along. I mean without Scott, who would cite my lunatic papers 😉
Scott you just need a dictionary! When a (good) physicist says “prove” you should substitute the words “we are 99.99% percent sure that under these conditions, when we run this experiment these will be your results. And if they’re not, please call us.”
I must say I’ve been trying to think of a way of showing that you need 100 physical qubits for every one logical qubit and the question doesn’t even make any sense. To do what, exactly? All such statements are a function of what accuracy you desire for your quantum computation. There is no magical number of qubits because it varies with your desired accuracy. Further if you increase the accuracy of the physical manipulations, you will need less encoding. Unless the result is derived from fundamental physics (either from quantum arguments alone, like for instance, establishing upper bounds on the threshold or from arguments from basic physical theories) I don’t see how such an argument could be made to work.
Also, I’d like to note that physicists are a widely varying species, some of whom have even been known to actually venture into the relms of mathematics and do some interesting work (Math. Res. Lett. 1, 769 (1994))
Comment #13 June 20th, 2006 at 2:27 am
There was a recent post at Cosmic Variance on the importance of negative results.
There were two things that surprised me in the post.
One was the apparent need to explain the point of negative results, such as avoiding useless efforts and revealing what precisely are the obstacles that one has to overcome.
The other was the fact that several types of negative results such as “this particular approach does not work,” “we handwave an argument to the effect that all approaches that satisfy an unspecified set of assamptions do not work,” and “all approaches that satisfy the following set of assumptions are rigorously proved not to work” were all discussed together as if there was no significant difference between them.
Comment #14 June 20th, 2006 at 5:20 am
Scott you just need a dictionary! When a (good) physicist says “prove” you should substitute the words “we are 99.99% percent sure that under these conditions, when we run this experiment these will be your results. And if they’re not, please call us.”
Dave: Where do I find this dictionary, and does it also include the physicist daffynitions of the words “must”, “necessary”, “always”, “only”, and “impossible”?
Also, I’d like to note that physicists are a widely varying species, some of whom have even been known to actually venture into the relms of mathematics and do some interesting work
Yeah, I pointed that out in another comment. In addition to the honorary computer scientists, there are also the honorary mathematicians.
Comment #15 June 20th, 2006 at 5:36 am
Some people here seem to believe that, unlike proofs in physics, mathematical proofs are HUNDRED PER CENT tight. Well, just because 10/1000/10^n people, after reading a certain paper, spotted no errors in it, does not warrant that the errors aren’t there.
Personally, I’m less interested in the difference between 100% and 98% confidence in a proof, as in the difference between 98% confidence and total confusion as to what’s even being proved. (“This is true unless there’s some counterexample we haven’t thought of yet.”)
Comment #16 June 20th, 2006 at 9:48 am
And here is an old fable about sheep instead of oxen. Once upon a time an engineer, a physicist and a mathematician were traveling on a train across Scotland. The engineer spotting a black sheep on a hill, declared:
“Now we know that all Scottish sheep are black”
The physicist:
“No, now we know that some of the Scottish sheep are black”
The mathematician:
“You are both wrong. Now we know that there is at least one sheep in Scotland, which is black at least from one side.”
Comment #17 June 20th, 2006 at 10:04 am
Yeah, that’s a classic.
Comment #18 June 20th, 2006 at 10:30 am
I’m fairly new to the exciting game of impossibility proofs. So I guess that it must be an old pun that it should be impossible to prove that impossibility proofs don’t work.
But they seem to be circumvented fairly often. You don’t even have to ride a pink elephant to do that. 🙂
Comment #19 June 20th, 2006 at 11:10 am
But [impossibility proofs] seem to be circumvented fairly often.
Since there still seems to be some confusion over terminology, let me lay it out as explicitly as I can.
if (impossibility proof is valid) {
if (its conditions hold) {
you can’t do what it says is impossible
} else {
maybe you can
}
} else {
you shouldn’t have called it a “proof” in the first place
}
Comment #20 June 20th, 2006 at 11:45 am
Well the dictionary does not exist as a physical object but is more of a flavor or a essence which is transmitted to physics students the moment they get their Ph.D. (Surprisingly a B.S. does not confer the contents of the dictionary to your aura. Ironic?)
Comment #21 June 20th, 2006 at 2:00 pm
Incidentally, to make money at a hedge fund, you only have to beat the other traders.
Not even! In many markets, all the traders make money–of course, the suppliers and end users of the underlying instrument have much more real risk. Hedge funds are notorious for charging a flat 2% fee and a 20% commission on profits, so they’re well-insulated.
When hedge funds crash, they lose credibility; so, after making a handsome 2% on huge sums of squandered money, the managers start new funds with new names and try again. It’s only legal because the funds have become prominent only recently and the law hasn’t caught up.
Comment #22 June 20th, 2006 at 9:33 pm
It’s true, It’s true. We’re so lame!
But when computer scientists prove a theorem, they prove it like this:
[Hunches forward, talks nasally]
Dee-da-dee, a-dee-da-dee-da-dee-da-dee.
When a physicist proves a theorem, they prove it like this:
[Leans back, as though his elbow were on the windowsill]
Do, do, ch. Do-be-do, do-be-do-be-do.
Comment #23 June 20th, 2006 at 11:25 pm
Scott, you are a lousy programmer
if (impossibility proof is valid) {
….if (its conditions hold) {
………you can’t do what it says is impossible
….else {
…….. maybe you can
….}
} else {
….you shouldn’t have called it a “proof” in
….first place
}
If the proof is valid and the conditions hold, it will always be true that “you can’t do what it says is impossible”
Comment #24 June 20th, 2006 at 11:51 pm
OOps, I didn’t make myself too clear in the 11:25 post. What I meant is that the program is a tautology, and does not perform any useful operations
Comment #25 June 21st, 2006 at 1:04 am
Ah, the occupational hazards of blogging. People who don’t understand the difference between a program and an assertion, publicly accusing you of being a lousy programmer…
Comment #26 June 21st, 2006 at 11:59 am
How much do you people have to write. Its like Bla Bla and Bla
Comment #27 June 21st, 2006 at 1:05 pm
How much do you people have to write. Its like Bla Bla and Bla
Could we get a grammar check on aisle five?
Comment #28 June 21st, 2006 at 5:47 pm
Scott says:
“Since there still seems to be some confusion over terminology, let me lay it out as explicitly as I can.
if (impossibility proof is valid) {
if (its conditions hold) {”
I was alluding to the conditions. I think string theory circumvents some impossibility proof for QFT’s. While QM impossibility for local hidden variable theories holds.
CS/math proofs are clear about conditions of course. You make that condition very clear. 🙂
Comment #29 June 21st, 2006 at 5:54 pm
Perhaps the QM example was bad since it is based on observations IIRC. Oh well, we can’t all work from first principles.
Comment #30 June 21st, 2006 at 7:03 pm
I think that this is the first time that I see two people discuss using the medium of fables.
Comment #31 June 21st, 2006 at 8:47 pm
First time? This is the only way mathematicians in different fields can ever communicate. Probably even more true for a computer scientist and a physicist.
Comment #32 June 25th, 2006 at 8:26 pm
Here’s a joke I was reminded of when reading the original tale (not Dave’s rejoinder). I got this out of a great little novel about a kid with Asperger’s syndrome called The Curious Incident of the Dog in the Night-time by Mark Haddon (that’s the book not the kid). Anyway, here’s the ‘joke,’ best quoted with an additional line from the book:
“There are three men on a train. One of them is an economist and one of them is a logician and one of the is a mathematician. And they have just crossed the border into Scotland (I don’t know why they are going to Scotland) and they see a brown cow standing in a field from the window of the train (and the cow is standing parallel to the train).
And the economist says, ‘Look, the cows in Scotland are brown.’
And the logician says, ‘No. There are cows in Scotland of which one at least is brown.’
And the mathematician says, ‘No. There is at least on cow in Scotland, of which one side appears to be brown.’
And it is funny because economists are not real scientists, and because logicians think more clearly, but mathematicians are best.”
Comment #33 June 25th, 2006 at 10:03 pm
Ian: Read the other comments first! Leonid had an extremely similar joke.
Comment #34 June 26th, 2006 at 1:11 pm
Indeed, I do see it now – very similar joke. Unfortunately, reading every post is a luxury not afforded me. Children, dogs, yardwork, “community” stuff, etc. – and once in awhile, actual paying work – seem to get in the way. sigh…
Comment #35 September 14th, 2006 at 1:34 pm
Hmm – I think I’m getting the whole twist in the tale thing. The “physicists” are like every prover of a profound theorem of classical complexity theory. And the “computer scientist” is like Feynman and/or Deutsch. Shouldnt the story end with: The physicists look around sheepishly, then say “we’ll call the task of pulling a cart with oxen a problem in OCP, and that of pulling the cart with elephants ECP”