Schrödinger’s cash
There’s an article in this week’s New Scientist by Justin Mullins about unforgeable quantum money. By the standards of “quantum mechanics journalism,” the article is actually really good; I’d encourage you to read it if you want to know what’s going on in this area. In particular, Mullins correctly emphasizes that the point of studying quantum money is to understand quantum mechanics better, not to mint practical QCash anytime soon (to do the latter, you’d first have to solve the minor problem of the money decohering within microseconds…).
My main quibble is just that I think the article overstates my own role! In my Complexity’09 paper, the main thing I showed is that secure quantum money that anyone can verify is possible, assuming the counterfeiters only have black-box access to the device for verifying the money. I also showed that, to get quantum money that anyone can verify, you have to make computational assumptions. (By contrast, Stephen Wiesner’s scheme from the 1960s, in which only the bank could verify the money, was information-theoretically secure.) But in terms of coming up with actual candidate quantum money schemes (as well as breaking those schemes!), the other members of the “quantum money club”—Andy Lutomirski, Avinatan Hassidim, David Gosset, Ed Farhi, Peter Shor—have been more active than me.
Two other quibbles:
(1) Mullins writes: “Then last year, Aaronson proposed a new approach that does away with the banknote and concentrates instead on the stream of information that represents quantum cash.” In Wiesner’s scheme, too, I think it was pretty clear that the “banknote with qubits stuck to it” was just a fun way to tell the story…
(2) The article does a good job of explaining the distinction between information-theoretic and computational security. But it doesn’t stress that, with the latter, we can’t actually prove that any of the “hard problems” are hard, without also proving P≠NP! (I’ll admit that the importance of this point is slightly hard to convey in a popular article, possibly because many people, or so I’m told, go about their lives without proving anything.) The best we can do is show that, if you could solve this problem, then you could also solve this other problem that people have studied for a long time. But in the case of quantum money, we don’t even know how to do that—which is what we meant when we wrote in our ICS paper that “it seems possible that public key quantum money intrinsically requires a new mathematical leap of faith.”
Considered as research topics in complexity theory, uncloneable quantum money, copy-protected quantum software, and so on are almost as wide-open today as public-key encryption was in the 1970s. That is, we don’t have a compelling intuition as to whether these tasks are possible at all: all quantum mechanics does is open up the possibility of them, which wasn’t there in the classical world. Unfortunately, in the case of quantum money, most of the ideas we’ve had for realizing the possibility have turned out to be insecure—often for non-obvious reasons. Assuming quantum money is possible, we don’t know what the right protocols are, what types of math to base them on, or how to argue for their security. So if you’re not impressed by the results we have, why don’t you try your hand at this quantum money business? Maybe you’ll have better luck than we did.
(Addendum: I also have a PowerPoint presentation on quantum money, which ironically goes into more detail than my Complexity paper.)
Follow
Comment #1 April 15th, 2010 at 8:21 pm
Great post. I really like these problems, and I suspect there are a ton more that we haven’t even thought of yet. Our blind computation paper came out of a (failed) attempt to do copy protected software.
I keep swinging backwards and forwards between whether I think it is possible or not. One day I think I have an impossibility proof, the next I think I have a scheme. Infuriating, but fun and interesting none the less.
As regards the leap needed, I don’t know for sure, but I feel MBQC is probably part of the answer.
Comment #2 April 15th, 2010 at 8:33 pm
I won’t be working on quantum copy protection any time soon. However, if you can come up with a quantum way of enforcing the terms of the GPL then I might be interested 🙂
Comment #3 April 15th, 2010 at 8:45 pm
Yes, I know DRM is evil. But until we have to upgrade our brains with DRM chips, there is a pretty obvious problem with media DRM.
Comment #4 April 16th, 2010 at 5:58 am
You know, I was only half joking in my last post. Of course, you can’t possibly enforce all copyleft clauses via quantum theory. In particular, open-source would be ruled out unless all programs were orthogonal in a known basis, which would make it impossible to enforce anything else. However, perhaps you could enforce a sharealike clause on its own by making it possible to copy a state, but only by including a license to make more copies in each copy.
Comment #5 April 16th, 2010 at 6:23 am
Your post got me to reading about the history of counterfeiting, which got me reading about the history of money. So this quote from Wikipedia is pretty tangential to quantum money:
“Coins were typically minted by governments in a carefully protected process, and then stamped with an emblem that guaranteed the weight and value of the metal. It was, however, extremely common for governments to assert the value of such money lay in its emblem and thus to subsequently debase the currency by lowering the content of valuable metal.”
Which is marginally interesting (especially since fiat money as we now know it only came about in the past couple hundred years), but a few minutes later I read this:
“In the 1990s, the portrait of Chairman Mao Zedong was placed on the banknotes of the People’s Republic of China to combat counterfeiting, as he was recognised better than the generic designs on the renminbi notes.”
What this suggests, to me, is that faces of gods or rulers were first put on coins in part as a natural “public-key anti-counterfeiting system”; it relies on the increased processing that the human brain does when it sees a face to detect small differences between legitimate and counterfeit coins.
Comment #6 April 16th, 2010 at 7:47 pm
I don’t understand the motivation for quantum money. The basic analogy — uncloneable quantum banknotes — seems stupid. Is there a better story?
Why should we be willing to make a new mathematical leap of faith? Complexity theorists are too willing to build towers on shaky foundations.
“Assuming quantum money is possible, we don’t know what the right protocols are, what types of math to base them on, or how to argue for their security. So if you’re not impressed by the results we have, why don’t you try your hand at this quantum money business? Maybe you’ll have better luck than we did.”
There are many unsolved problems. That by itself does not give motivation.
Comment #7 April 16th, 2010 at 11:07 pm
Sandra, I’m not too interested in quantum money either. For me, the ultimate goal is to build a quantum computer and algorithms/software for it. If building a quantum computer is like the Apollo 11 mission, quantum money seems to me the equivalent of designing really cool sunglasses for the astronauts.
Comment #8 April 17th, 2010 at 12:20 pm
Of course this is not about quantum “money” at all, money being any commodity that people can stash away (from water bottles, sheep or pieces of supernova-forged metal). It is either about quantum warehouse recipes that are about real money or it’s about quantum “fiat money” that no-one is supposed to counterfeit except the usual suspects.
I predict the existence of the new dictum “not worth a Quantum Continental” in finitely many of our possible futures.
Comment #9 April 17th, 2010 at 2:16 pm
Sandra T.:
“There are many unsolved problems. That by itself does not give motivation.”
Based on the above two sentences, I’m guessing you’re not a theoretical computer scientist? 🙂
Seriously, let me give you my personal perspective: quantum money and quantum software copy-protection are interesting not because of the possible applications (which are remote and not even all that interesting to me), but because they’re good testing-grounds for basic philosophical questions about the nature of quantum mechanics. One of the central properties of classical information is that you can copy it an unlimited number of times—e.g., if you tell someone something, you have no idea how many of their friends they’re going to repeat it to. It’s such an obvious property that it seems weird even to state it explicitly. But then in quantum mechanics, it’s not true!
OK, you might say, so we know the No-Cloning Theorem—but is it really all that important? After all, you might have some uncloneable state |ψ⟩, but if you know how |ψ⟩ was prepared, then you can just run the preparation procedure again to copy it. And if you don’t know how |ψ⟩ was prepared—well then, who cares about copying it? It’s not a useful state to you anyway.
Ah, but is that really true? Or is it conceivable that there could exist a “precious and irreplaceable” quantum state—a state |ψ⟩ which we could measure in such a way as to learn or verify something useful, but couldn’t measure in such a way as to produce more copies of |ψ⟩? A state |ψ⟩ that you could imagine a civilization storing in a special high-security vault, to prevent it from decohering—and that would be taken out only on a few special occasions, when it needed to be measured? A quantum Ark of the Covenant, if you will?
Actually, now that I think about it, maybe that’s a better story than quantum money…
Comment #10 April 17th, 2010 at 3:48 pm
I’m quite willing to believe that such unclonable verifiers exist in the quantum domain. But don’t such things already exist, to a very good approximation, classically. (For instance, isn’t a van Gogh painting a verifier that is essentially impossible to clone.)
It’s the same problem that afflicts quantum cryptography. An important contribution to theory, but of little practical utility because you can achieve almost as good security in the classical domain using much cheaper and much less fragile classical states
Comment #11 April 17th, 2010 at 4:10 pm
I think you should call your unclonable states “white elephants”, precious, but impossibly expensive to keep alive.
Comment #12 April 17th, 2010 at 8:35 pm
rrtucci: Van Gogh paintings are actually a terrible example — paintings can be, and are, forged all the time! There are regularly paintings that sell for millions of dollars, until their value plummets when it’s discovered that they were merely the work of some schmoe and not a famous person.
It’s conceivable that quantum paintings, on the other hand, could genuinely be unforgeable—you could measure them in different bases to experience their beauty from exp(n) possible angles, but it would be computationally intractable to determine, from the measurement results, how to prepare another state with the same behavior. Admittedly, we don’t actually know whether this sort of thing is possible or not … which is why we’re, y’know, researching it.
Comment #13 April 18th, 2010 at 8:53 am
There are these kinds of CS problems where you have a working communications protocol to solve some task if all the agents cooperate, but you want to design a protocol where it’s not worth for any agent not to cooperate. I don’t really know much of these kinds of problems, but see eg. “http://gilkalai.wordpress.com/2010/01/26/michael-schapira-internet-routing-distributed-computation-game-dynamics-and-mechanism-design-ii/”. I wonder if these quantum objects you all are searching (“quantum money”, but not as actual money, just simialr schemes) could be used as building blocks helping such protocols, supposing of course that both quantum computers and these objects exist.
Comment #14 April 18th, 2010 at 4:12 pm
I wonder about these arguments that “quantum money is not very interesting or realistic, but it’s interesting because it’s a good testing ground for fundamental philosophical questions”. So why does the community work on quantum money, then? Why not just study those fundamental philosophical questions directly?
I’m not a theoretical computer scientist, either.
(I also wonder about allowing a news reporter to write an article hyping quantum money as though it could be useful, if you believe it is unlikely to be useful. Shouldn’t the first comment one makes to the reporter be “this will probably never be useful, but it’s an interesting philosophical puzzle?”)
Comment #15 April 18th, 2010 at 4:36 pm
Sandra T.:
The more practical and less philosophical answer to your question is that the whole problem is we don’t know what types of things quantum communication may be good for. Quantum money and quantum copy protection are metaphors that researchers use to describe the mathematics they are studying. They may or may not relate to applications that turn out to be practical. The metaphors are not mere window dressing, either. If they are good, they will inspire people to think in different and hopefully better ways about quantum information, which is the kind of thing that leads to figuring out a useful way to apply it.
The example that is so painfully relevant that I hate to even bring it up is quantum cryptography. The quantum money protocol described by Stephen Wiesner eventually became quantum cryptography. I rather think quantum cryptography itself is overrated, but it is a genuine practical application. You can go out and buy a pair of quantum communication nodes and they will more-or-less do what it says on the tin.
Comment #16 April 19th, 2010 at 9:23 am
Scott: Quantum computer is based on the superposition of states. In the Many Worlds interpretation, there is no superposition of states. It says that we have many many worlds and in World A, the state of the bit is in that of bit 0 and in World B, the state of the same bit is in that of bit 1. So, do you think that quantum computers rule out the Many Worlds interpretation or you would tell me that the Many Worlds Interpretation can actually explain the operation of quantum bits?
Comment #17 April 19th, 2010 at 10:16 am
AnonCSProf:
I wonder about these arguments that “quantum money is not very interesting or realistic, but it’s interesting because it’s a good testing ground for fundamental philosophical questions”. So why does the community work on quantum money, then? Why not just study those fundamental philosophical questions directly?
My personal answer: because the philosophical questions, as stated, are too vague to study directly! I see quantum computing and information, not merely as helping us address what used to be considered philosophical questions, but as helping us make precise what those questions even mean.
I also wonder about allowing a news reporter to write an article hyping quantum money as though it could be useful, if you believe it is unlikely to be useful. Shouldn’t the first comment one makes to the reporter be “this will probably never be useful, but it’s an interesting philosophical puzzle?”
I think that was the first comment I made to the reporter! Certainly it’s a comment I repeated over and over, and I was delighted to see that it actually got reflected in the story.
Look, I made zero effort to contact reporters about quantum money. They called me … and when they did, I repeatedly stressed how comically remote from practicality it was (while also answering the question of how my colleagues and I ended up studying it!).
So what else would you have had me do? Run away and hid like Grisha Perelman? As you know, that’s also not a guarantee against sensationalized news stories… 🙂
Comment #18 April 20th, 2010 at 2:50 am
“Quantum money and quantum copy protection are metaphors that researchers use to describe the mathematics they are studying.”
And part of their attraction is that they naturally lead to whimsical generalization. It’s a short step from quantum money to quantum investment, a quantum subprime financial crisis, and a quantum lawsuit by a quantum SEC against quantum Goldman Sachs for quantum securities fraud. It sounds like a joke, but we are really talking about topics like information, communication, and decision theory in a quantum framework, and from that perspective I can imagine even that last bit of whimsy leading to theoretically valuable work.
Comment #19 April 20th, 2010 at 8:13 am
Scott, I have a ton of respect for research on “money that can’t be cloned”, and the closely related problem of “experiments that can’t be simulated” (e.g., your linear optics project).
A respectful question—which I ask solely because it might have an interesting answer—is how much of these ideas remain valid if Ashtekar and Schilling’s view turns out to be correct, that “The linear structure of quantum mechanics is, primarily, only a technical convenience“?
Obviously, the proof technology would have to be upgraded … but the key ideas of “money that can’t be cloned”, and “experiments that can’t be simulated” IMHO may well survive … and perhaps they would even survive in a form that offers us (in your phrase) “a more compelling intuition” of what’s going on, than linear QM theory has so far given us.
One path by which this intuition is evolving in simulation theory—both classical and quantum—is a dawning recognition of the practical advantages for simulation of pulling-back onto simulation state-spaces of larger dimension (the canonical example being pullback of three Euler angles onto four quaternion variables).
From this point-of-view, the linear structure of Hilbert spaces would arise from an Ashtekar-and-Schilling quest to efficiently simulate the physical processes we see in our universe: the real quantum state-space having a non-Euclidean geometry, but for simulation purposes it being technically convenient—irresistibly convenient—to pullback quantum dynamics back onto a larger linear space … even at the expense of requiring that fictional QM simulation space to have extravagantly many dimensions.
As for the real geometry of QM, we don’t yet know it … but the string theorists are trying to guess it.
From this point of view, fundamental research—both theoretical and experimental—relating to “money that can’t be cloned” and “experiments that can’t be simulated” can be regarded as a promising avenue of investigation into key questions relating to the state-space geometry of QM.
That’s *one* way to read articles on these topics, anyway!
Comment #20 April 20th, 2010 at 11:37 am
John: Everything remains valid, regardless of your beliefs about the foundations of QM (unless, of course, quantum mechanics were actually overturned, which would be much more interesting than quantum money).
Comment #21 April 21st, 2010 at 2:49 am
Scott, Thanks for the honest and impassioned response. I appreciate that you took the time to respond. I respect your position and find your arguments compelling. I’m convinced!
Evan, You write: “I rather think quantum cryptography itself is overrated, but it is a genuine practical application.” This is an ill-fated example to list. I am a cryptographer, and I would say that quantum cryptography solves a problem that almost no one has [1], and does so at great cost. (Have you seen the companies trying to sell $50,000 quantum encryptors? It’s a bad joke.) Calling quantum cryptography “overrated” is a bit of an understatement. And why is it overrated? Because it’s been overhyped, and because (in retrospect) quantum crypto researchers haven’t done a great job of being upfront about the practical reasons why quantum cryptography is basically irrelevant in most practical settings when they wrote research papers on the subject. Basically, the people who tend to be most excited about quantum cryptography these days are physicists, and the people who tend to be the least impressed are practitioners.
I’m much more sympathetic to arguments like the ones that Scott has presented, that we don’t know the right questions to ask and it’s important to ask fundamental questions.
I do have a gripe with the names the field has chosen. When experts choose names like “quantum money” and write serious papers about the subject, non-experts take them at their word and assume they’re being serious and are seriously talking about serious protocols for money that could someday be practically useful. (This is especially problematic when people write papers whose introduction motivate the work by talking about the need for provably secure primitives that do not rely upon unproven complexity-theoretic assumptions, or whatever.) To this outsider, it looks like the field is to some extent allowing these misconceptions to spread, and profiting from them, similarly to what has happened with quantum cryptography. In this respect, I worry the field is unnecessarily creating a potential credibility problem for itself. If the field is going to use serious-sounding names whimsically, I think it would behoove the quantum community to find a better way to convey that fact to outsiders.
[1] See, e.g.,
http://www.mail-archive.com/cryptography@metzdowd.com/msg00828.html
and the comments after this interview:
http://hackreport.net/2006/12/13/quantum-cryptography-its-some-kind-of-magiq/
and
http://www.mail-archive.com/cryptography@metzdowd.com/msg07680.html
http://www.mail-archive.com/cryptography@metzdowd.com/msg07758.html
http://www.mail-archive.com/cryptography@metzdowd.com/msg07761.html
http://dooooooom.blogspot.com/2007/06/quantum-cryptography-is-expensive-and.html
http://leitl.org/oldcontent/docs/public_html/tt/msg22079.html
http://www.derkeiler.com/Newsgroups/sci.crypt/2003-10/2158.html
Comment #22 April 21st, 2010 at 8:40 am
Hmmm … I guess “foundations of quantum mechanics” means different things to different folks.
In particular, is the statement “the state-space of quantum mechanics is a Hilbert space” best regarded—in descending order of certainty—as an axiom so natural as to be irreplaceable; as a well-established law of nature; as a good working approximation in practical calculations; or as a mere technical convenience?
I used to embrace “a well-established law of nature”, but have pretty much switched over to “a good working approximation” … this view was impressed upon me by (1) the geometric view of dynamics pioneered by folks like Arnol’d, Mac Lane, Ashtekar and Schilling, Berezin (and many others), coupled with (2) the otherwise inexplicable success of modern quantum simulation codes.
It appears to be a rule of nature that every state-space that arises from thermodynamical processes has a non-trivial geometry … from protein conformation all the way up to space-time itself.
Until proven otherwise, why should the state-space of QM be any different? After all, didn’t it too arise thermodynamically, in the Big Bang?
The key phrase is “until proven otherwise” … that’s why technologies—both experimental and mathematical—for demonstrating that the state-space of QM is a Hilbert space are so very interesting.
It appears (to me) that the mathematical and physical evidence for QM being necessarily a Hilbert-space theory is not really all that strong … especially since today’s QM simulation codes are astoundingly accurate, and yet (upon inspection) none of them fully embrace linear Hilbert-space orthodoxy.
Comment #23 April 21st, 2010 at 9:34 am
John, if the state space of QM is not a Hilbert space, that would overturn quantum mechanics, and be the most exciting development in physics in almost a century.
At present, we don’t even have sensible toy theories that agree with quantum mechanics on known experiments, which are based on anything other than Hilbert space. (Where “sensible” means respecting locality, causality, conservation of probability, etc.)
Comment #24 April 21st, 2010 at 1:58 pm
Scott, if “sensible” means “respecting locality, causality, conservation of probability, etc.”, then is Hilbert-space QM a sensible theory sensu stricto?
I’m just making the mild observation that (linear) QM field theory has some pretty severe defects with regard to locality and causality. So is Hilbert space linearity a safeguard against even worse problems … or is the linearity itself a contributing cause?
Without intending to formally develop a viable non-Hilbert state-space, haven’t today’s quantum simulationists have come a long way toward creating such a theory de facto?
As Mac Lane has pointed out, “mechanics developed by the treatment of many specific problems.” He was referring to classical mechanics, but perhaps QM will prove to be no different.
Comment #25 April 21st, 2010 at 3:17 pm
John,
That is one great figure! Where can I get the T Shirt?
Comment #26 April 22nd, 2010 at 3:35 am
Raoul, t-shirts are ephemeral … but a simple, tasteful tattoo would endure. 🙂
Consulting my database for the aesthetic viewpoint on geometric quantum mechanics, I find Karl Hofmann’s Notices of the {AMS} article “Commutative diagrams in the fine arts”, David Henderson and Diana Taimina’s Mathematical Intelligencer article “Crocheting the hyperbolic plane”, and Taimina’s book Crocheting Adventures with Hyperbolic Planes.
Golly … I see Taimina’s book was this year’s winner of Diagram Prize … which some British literary folk seem to think is more prestigious even than the Booker!
These works provide an interesting cognitive perspective on the geometric ideas in Abhay Ashtekar and Troy A. Schilling’s article “Geometrical Formulation of Quantum Mechanics” (arXiv:gr-qc/9706069v1). This ideas are well-summarized by the wonderful introduction to Taimina’s book (the introduction itself was written by Bill Thurston):
“Our brains are complicated devices, with many specialized modules working behind the scenes to give us an integrated understanding of the world. Mathematical concepts are abstract, so it ends up that there are many different ways that they can sit in our brains.”
A given mathematical concept might be primarily a symbolic equation, a picture, a rhythmic pattern, a short movie—or best of all, an integrated combination of several different representations. These non-symbolic mental models for mathematical concepts are extremely important, but unfortunately, many of them are hard to share.
Mathematics sings when we feel it in our whole brain. People are generally inhibited about even trying to share their personal mental models. People like music, but they are afraid to sing. You only learn to sing by singing.
Vladimir Arnol’d has written in a similar vein:
“Our brain has two halves: one half is responsible for the multiplication of polynomials and languages, and the other half is responsible for orientation of figures in space and all the things important in real life. Mathematics is geometry when you have to use both halves.”
Perhaps the best single reason to study geometric quantum mechanics, therefore, is to understand better what geometers like Taimina, Thurston, and Arnol’d, Mac Lane, Grothendieck, etc. are talking about … and thus (slowly and incompletely) come to understand QM in their integrated cognitive style, within their geometric framework, and do practical QM calculations via their powerful mathematical toolset.
The point is simply that geometric quantum mechanics definitely is beautiful, useful, and fun … and as for whether it is right physically … well … that’s a question for the future!
——–
@article{Hofmann:2002kx, Author = {Karl Heinrich Hofmann}, Journal = {Notices of the {AMS}}, Number = {6}, Pages = {663–668}, Title = {Commutative Diagrams in the Fine Arts}, Volume = {49}, Year = {2002}}
@article{Henderson:01, Author = {D. Henderson and D. Taimina}, Journal = {Mathematical Intelligencer}, Number = 2, Pages = {17–18}, Title = {Crocheting the hyperbolic plane}, Volume = 23, Year = 2001}
@article{Lui:1997eu, Author = {Lui, S. H.}, Journal = {Notices Amer. Math. Soc.}, Number = {4}, Pages = {432–438}, Title = {An interview with {V}ladimir {A}rnol’d}, Volume = {44}, Year = {1997}}
Comment #27 April 22nd, 2010 at 12:28 pm
In a couple hundred million years the {brain, eyes} system has evolved great power for recognizing patterns. Good figures allow this power to be used for more abstract models. My favorite example concerns the family of bessel functions, which, like many undergrads, I once did not grok. A sketch in (I think) Magnus and Oberhettinger, “Formulas and Theorems for the Functions of Math Physics” *, instantly shows how they work, and moves you across the “everything is easy once you know it” divide.
* http://www.amazon.com/s/ref=nb_sb_noss?url=search-alias%3Daps&field-keywords=functions+of+mathematical+physics&x=0&y=0
Comment #28 April 22nd, 2010 at 8:05 pm
Basically, the people who tend to be most excited about quantum cryptography these days are physicists, and the people who tend to be the least impressed are practitioners.
I am neither a cryptography practitioner nor a physicist, I’m a mathematician. I would be the first to agree that quantum key distribution solves a problem that almost no one has, and that commercialization of this technique is at best an obscure market and at worst snake oil. I agree that there has been a lot of hype.
Nonetheless, I think that it’s really interesting that quantum key distribution does something that previously seemed impossible. (Namely, it achieves communication secrecy even if the eavesdropper has unlimited computational resources.) It may sometimes happen that one of the most interesting tools in the toolbox is also one of the least useful. For the time being. When a tool is so interesting, it might well be useful later for an unforeseen reason.
Besides, this tension between what is useful and what is fascinating is not a new thing in applied mathematics. One clear example is in error-correcting codes, where there are a lot of beautiful constructions using algebra and number theory, but in the end simpler or less elegant constructions are almost always the most useful. Is it a waste of time to study algebraic geometry over finite fields if you are a coding theorist? I don’t design cell phones, so I am not qualified to say, but again, speaking as a mathematician, I think that some coding theorists should learn about it.
Or, does algebraic geometry over finite fields create a credibility problem for coding theory? Does quantum key distribution create a credibility problem for quantum computation? Maybe, but not because of mathematicians. There isn’t much incentive among mathematicians to spew that kind of hype. (We have plenty of incentive for other kinds of hype and bad behavior, but not that kind.) Hype in quantum computation also bugs me, but it also seems alien to a mathematical audience, alien enough that I don’t think that it makes me look bad.
If one defines mathematicians to be people who prove theorems, then Scott also is one. I don’t mean to speak for him, but I think that he could say the same as me.
Comment #29 April 22nd, 2010 at 11:42 pm
Greg’s definition of a Mathematician misses a major point:
1. A mathematician’s job is using math to solve problems, useful or otherwise. This often involves proving theorems.
2. A PURE mathematician’s jobs job is proving theorems, possibly useful, but preferably not. The stylish take pride in never having solved a problem, G.H. Hardy being the standard bearer.
Guess which camp Newton, Gauss, Riemann, Euler, Laplace, Knuth, etc, are in?
In an unfortunate coup 100 odd years ago, the Pure cult, by proving more and more theorems about less and less, took over the establishment. They kept the funding provided by teaching calculus to future scientists and engineers, who have been complaining from day one that math profs can’t calculate the Laplace Transform of a cosine.
Comment #30 April 23rd, 2010 at 3:37 am
In the writings of geometers, one one often finds vigorous disagreement with the statement “mathematicians are people who prove theorems.”
Here is Vladimir Arnol’d speaking of René Thom:
“I was always delighted by the way in which Thom discussed mathematics, using sentences obviously having no strict logical meaning at all. While I was never able to completely free myself from the straitjacket of logic, I was forever poisoned by the dream of the irresponsible mathematical speculation with no exact meaning. `One can always find imbeciles to prove theorems’ was, according to Thom’s students, his principle. “
In Sergei Novikov we find:
“The percentage of good things that may be done rigorously is going to zero; the number of good theorems is increasing, but the ratio is going down rapidly.”
Mac Lane explains at greater length:
Analysis is full of ingenious changes of coordinates, clever substitutions, and astute manipulations. In some of these cases, one can find a conceptual background. When so, the ideas so revealed help us understand what’s what. We submit that this aim of understanding is a vital aspect of mathematics.
In his discussion of quantum money, when Scott asks for “a compelling intuition”, my own reading of that passage (which possibly differs *greatly* from the meaning that Scott intended) is an expression of a Mac Lane-style desire for a broader thematic grasp of “what’s what” in quantum informatioon theory, similar to the broader thematic grasp that pioneering algebraic geometers like Arnol’d, Novikov, Thom, Mac Lane, Grothendieck (and many more) have long been seeking.
Obviously, it is not necessary that everyone agree with the geometers’ point-of-view, or with any other single point-of-view. In fact, universal agreement on thematic questions would indicate that mathematics/science was slipping into bad health … because healthy ecosystems are diverse ecosystems.
———–
@article{***, Author = {Lui, S. H.}, Journal = {Notices Amer. Math. Soc.}, Number = {4}, Pages = {432–438}, Title = {An interview with {V}ladimir {A}rnol’d}, Volume = {44}, Year = {1997}}
@incollection{***, Address = {Berlin}, Author = {Novikov, Sergei}, Booktitle = {Mathematical research today and tomorrow ({B}arcelona, 1991)}, Pages = {13–28}, Publisher = {Springer}, Series = {Lecture Notes in Math.}, Title = {R\^ole of integrable models in the development of mathematics}, Volume = {1525}, Year = {1992}}
@book{***, Address = {New York}, Author = {Mac Lane, Saunders}, Publisher = {Springer-Verlag}, Title = {Mathematics, form and function}, Year = {1986}}
Comment #31 April 24th, 2010 at 11:18 am
Scott,
I was wondering if you could clear something up that hit me quite hard this morning. Why doesn’t the proof by Baker, Gill, and Solovay that any solution to the P versus NP question not relativize actually settle the question? Couldn’t one think (for example) having an oracle to solve the Subset Sum problem in an attempt to solve 3SAT. If we suppose that the Subset Sum problem has a polynomial time solution then we run into the contradiction set up by Baker et al – so it must have an exponential run time.
I know I’m wrong. I just don’t know how.
Comment #32 April 24th, 2010 at 1:16 pm
Ross: Don’t worry, you’re indeed wrong. 🙂 The BGS proof that there exists an oracle relative to which P≠NP really doesn’t say much—all it says (informally) is that if you have a black box that recognizes solutions to a combinatorial search problem, and the only way to gain information about the problem is to call the black box on various candidate solutions, then an NP machine can find a solution exponentially faster than a P machine (which is limited to trial-and-error).
But NP-complete problems, like Subset Sum and 3SAT, are emphatically not black boxes. They have structure, arising from the actual clauses and variables—and indeed, algorithms like DPLL and simulated annealing can and do exploit that structure to do somewhat better than brute-force search (e.g., to achieve more moderate exponential runtimes). BGS says nothing about algorithms that exploit the structure of NP-complete problems, even though understanding such algorithms is the whole substance of the P vs. NP question.
The message of BGS, if you like, is that in the case of P vs. NP, there’s not going to be any clever way around a detailed consideration of problem structure, analogous to how Turing’s self-reference argument avoided really “understanding the structure” of the halting problem.
Comment #33 April 25th, 2010 at 11:50 am
That’s all BGS is saying? Okay, I think that’s where my problem was stemming. I haven’t read the paper and am still relying on gaining understanding from second-hand sources. My understanding previous to your explanation was that they showed how to transform any oracle where P=NP into an oracle where P!=NP. This is why I thought it showed that Sumset Sum (for example) must be an exponential time problem (to avoid contradiction). I now understand that they showed results in both directions and that this highlighted for the TCS community the fact that relativizing proof techniques can’t be used (at least independently) to decide the problem.
Thanks for getting back so quickly.
Comment #34 May 10th, 2010 at 1:39 pm
search problem, and the only way to gain information about the problem is to call the black box on various candidate solutions, then an NP machine can find a solution exponentially faster than a P machine (which is limited to cars sale previous to your explanation was that they showed how to transform any oracle where P=NP into an oracle where P!=NP. This is why I thought it showed that Sumset Sum (for example) must be an
Comment #35 May 13th, 2010 at 1:11 pm
@ Scott Aaronson
Hi, I’m afraid it’s nothing related to the present post, but do you plan to say something about this?
http://arxiv.org/PS_cache/hep-th/pdf/0612/0612036v3.pdf
http://arxiv.org/PS_cache/arxiv/pdf/0809/0809.4685v4.pdf
Best,
Comment #36 May 13th, 2010 at 5:00 pm
I saw someone mention the Many Worlds interpretation so I thought maybe I could smuggle in a question on that here. I’m a computer scientist so I don’t claim to understand quantum mechanics or any interpretation thereof very well. Fortunately, I feel Scott and others here tend to discuss the topic in terms that a computer scientist (but layman quantum-wise) can relate to (at least some of the time!) 😉 OK so the question is:
What does the existence/realization of “many worlds” in the many worlds interpretation add? Consider the following transformation of the “many worlds interpretation” (MWI) into a theory I will call “The random world interpretation” (RWI): In all situations where MWI asserts that the universe “spawns” into multiple universes with different configuration, the RWI interpretation asserts that the universe randomly selects one of the potential universes with probability proportional to the number of such universes asserted to be created by MWI, and that universe comes to exist. There’s no multiple universes, no brancing or anything – just random selection.
To me it seems, that if the multiple universes claimed to exist by MWI are inaccessible from each other, it seems that there’s no difference compared to the RWI interpretation. Further, RWI is much easier for me to digest since I already accepted that some processes are truly random.
I’m sure there’s something I have overlooked. Maybe the the “spawing” happens in a way that can’t be mapped to a probability distribution? Maybe it is super continuous (but I think that would cause similar problems for MWI itself – I can’t visualize the sort of continouos tree structure this would imply) and that the many worlds posited to exist by MWI really do add something. I also sometimes get the feeling that some MWI-people don’t truly think all these universes really exist (whatever it means for something totally inaccessible to you “to exist) but that it is just a way to explain it. Other times I get the feeling that they really do believe they exist and that also seems to make sense given the name of the interpretation. Further, if they don’t believe them to exist, it becomes even harder to see what they add to the explanation and how the view differs from what all the old quantum guys, say, Schrödinger thought about it all along?
Maybe someone could recommend a down-to-earth yet not dumbing-down book on the subject?
Comment #37 May 13th, 2010 at 6:57 pm
OK to put things more bluntly 😉
My view on this is that the nice property of MWI that sets it apart from the Copenhagen Interpretation that a measurement isn’t any different than any other interaction. Your brain/consciousness doesn’t trigger a magical collapse of a wave function of a wave function, but clearly as it interacts with an object its own probability distribution (in layman’s terms) becomes more and more connected to that of the object being observed.
But this crucial property of the theory has nothing to do with the “many worlds” part of the theory – the crucial part is the relative-states / entanglement part of the interpretation which doesn’t imply anything about “spawning” or the existence of multiple worlds, whatever it might mean.
Then MWI happens to have this unrelated and unfortunate other interpretation in it, namely the part of the many worlds. I view this as a way of interpreting randomness and probabilities in general. It has no special place in the other part (the relative-state part) of the interpretation. It might as well belong in an interpretation of classical probability theory where it is saying that there’s some sort of physical reality to the probability trees used there.
I have two points on this:
First, it isn’t an interpretation of randomness that appeals much to me.
Secondly, no matter what one things of this, it really ought to be separate (dare I say untangled?) from the interpretation. There should be one interpretation called “the relative state interpretation” and one called “the many worlds interpretation of randomness”. It is the former that is important as an alternative to the Copenhangen interpretation – not the latter. To make matters worse, much of the controversy about MWI really derives from the latter! Are you uncomfortable with thought experiments like quantum suicide or whatever quack things people come up with? Just abolish the “many worlds” part of the interpretation and stick to the relative state part of it. You can go to bed safely in the knowledge that there’s not some copy of you being tortured by Dr. Evil – and you can be sure that all the quacks that comitted quantum suicide really are dead! 😉
Comment #38 May 14th, 2010 at 6:26 am
This claims that long-lasting quantum entanglement figures into photosynthesis:
http://arstechnica.com/science/news/2010/02/photosynthesis-uses-quantum-interactions-to-process-light.ars
Comment #39 May 14th, 2010 at 9:11 pm
@37: gravity allows closed timelike curve (well… theorically) so that P/gravity=P/CTC=PSPACE, a bit (!) larger than NP-complete problems. The puzzle with your answer is that it seems to have nothing to do with singularities. Or it has?
http://www.scottaaronson.com/democritus/lec19.html
Comment #40 May 20th, 2010 at 5:51 pm
@Martin
Your interpretation seems very close to
http://en.wikipedia.org/wiki/Relational_quantum_mechanics
(sorry for the delay, I mentionned it a couple of day ago but it’s still “awaiting moderation.”)