My day job
You’ve probably spent days, or even months, wondering why I don’t update this blog more often. What could possibly be more important to my career — besides napping, web surfing, napping again, or watching Jon Stewart?
So it’s time to come clean: besides my gig at Shtetl-Optimized, I also have a “day job,” most of which is actually performed at night. Greg Kuperberg, who used to be my most regular commenter before he went M.I.A., has a similar “day job.” If you don’t already know what this day job is, it’s a little hard to explain. We barely understand it ourselves. One thing I can say is that it involves the production of documents like the following:
S. Aaronson and G. Kuperberg, Quantum Versus Classical Proofs and Advice, quant-ph/0604056.
This paper studies whether quantum proofs are more powerful than classical proofs, or in complexity terms, whether QMA=QCMA. We prove two results about this question. First, we give a “quantum oracle separation” between QMA and QCMA. More concretely, we show that any quantum algorithm needs Ω(sqrt(2n/(m+1))) queries to find an n-qubit “marked state” |ψ>, even if given an m-bit classical description of |ψ> together with a quantum black box that recognizes |ψ>. We also prove a matching upper bound. Second, we show that, in the one previously-known case where quantum proofs seemed to help, classical proofs are basically just as powerful. In particular, Watrous gave a QMA protocol for verifying non-membership in finite groups. Under plausible group-theoretic assumptions, we give a QCMA protocol for the same problem. Even with no assumptions, our protocol makes only polynomially many queries to the group oracle. Both of our results apply equally to the problem of quantum versus classical advice — that is, of whether BQP/qpoly equals BQP/poly. We end with some conjectures about quantum versus classical oracles, and about the problem of achieving a classical oracle separation between QMA and QCMA.
Alright, suppose you’re King Arthur. Merlin, your staff wizard, claims to have solved a very hard math problem (a “Holy Grail,” so to speak) on which your entire kingdom depends. The problem might involve, say, the speed of an African swallow, or the best kind of oil in which to boil heretics — the details aren’t important.
Being suspicious of wizards, you want to check Merlin’s solution, but being a king, you don’t have much time to do it. You do, however, have a quantum computer at hand (why not?). Here’s the question: is there anything Merlin could convince you of by giving you a quantum-mechanical superposition, that he couldn’t convince you of by just communicating classically?
QMA, which stands for “Quantum Merlin Arthur,” is (basically) the class of problems for which Merlin could feasibly convince you of the answer by giving you a quantum state. QCMA, which stands for “Quantum Classical Merlin Arthur,” is the class of problems for which Merlin could feasibly convince you of the answer by just communicating classically. (Some people have suggested changing the acronym to CMQA, for “Classical Merlin Quantum Arthur,” since Arthur has the quantum computer while Merlin has to communicate classically.)
The key question is whether QMA and QCMA are equal. So, do Greg and I answer that question in our paper? Of course not — are you nuts?! All we do is get closer to answering it than anyone before. We do so by giving two new pieces of evidence: one suggesting that QMA and QCMA are equal, and another suggesting that they’re not. You might not realize it, but this represents Progress.
To those who aren’t “in the business,” all of this medieval quantum intrigue might raise a question: why do we bother? Why do we spend months writing papers that (if we’re lucky) maybe a hundred people will ever be aware of, and ten will ever understand? Well, Greg can answer for himself. As for me, I’ve always liked the answer once given by Bertrand Russell. And no, this isn’t my “serious” or “official” answer (nor was it Bertie’s), but it’s a fine response to anyone who has to ask.
…a word of advice to such of my hearers as may happen to be professors. I am allowed to use plain English because everybody knows that I could use mathematical logic if I chose. Take the statement: “Some people marry their deceased wives’ sisters.” I can express this in language which only becomes intelligible after years of study, and this gives me freedom. I suggest to young professors that their first work should be written in a jargon only to be understood by the erudite few. With that behind them, they can ever after say what they have to say in a language “understanded of the people.”
Follow
Comment #1 April 11th, 2006 at 12:00 am
My motivation: Even if it is an extremely obscure way to contribute to society, it seems like a less redundant contribution than if, for example, I wrote computer games. Beyond that, I do it because it’s fun.
Comment #2 April 11th, 2006 at 12:03 am
BTW, one reason that I stopped posting to this blog is that I felt guilty for not working on the paper. But since you mention it, among all of your web efforts, I give the Complexity Zoo an A+ and this blog a B-. The blog is okay, really, but did you cut the Zoo loose only for this?
Comment #3 April 11th, 2006 at 12:37 am
Even if it is an extremely obscure way to contribute to society, it seems like a less redundant contribution than if, for example, I wrote computer games. Beyond that, I do it because it’s fun.
Those are both excellent motivations.
In the end, if someone who’s running a medical clinic in India, suing gun companies, canvassing for the Democrats, etc. asks me to justify what I do, I don’t have a response.
If a sportswriter or casino manager or fashion designer asks me to justify what I do, I also don’t have a response, but for a different reason.
Comment #4 April 11th, 2006 at 12:41 am
But since you mention it, among all of your web efforts, I give the Complexity Zoo an A+ and this blog a B-.
Thanks! 🙂 What would I have to do to raise my grade — start blogging about LWPP and MAXSNP?
Comment #5 April 11th, 2006 at 1:12 am
canvassing for the Democrats
Since you mention it, an interesting story about Ed Witten (well, one of them) is that after he graduated from Brandeis with a history major, he worked for the McGovern campaign. Partly because this was such a disaster, he decided to try physics instead.
What would I have to do to raise my grade — start blogging about LWPP and MAXSNP?
You mean, other than going back to the Zoo project?
Making your blog great would take so much luck and hard work that it would be a Pyrrhic victory. John Baez is about as good at this as anyone and I rate his “This Week’s Finds” an A-. I doubt that you can match him at this game. Maybe if it were a group blog, you would have a shot at it. On the other hand, you are entitled to blog as part of what the military calls R&R.
On that note, I confess that I started a blog too in a moment of weakness. Click on my name and you will see. But it is described as a group blog. I do not have the energy to build it up on my own.
Comment #6 April 11th, 2006 at 1:22 am
In your paper, you write
“If we can’t decide whether two complexity classes are different, the usual next step is to construct a relativized world that separates them.”
Perhaps one might hope that the final step would be to separate the classes in the usual unrelativized world. So my question is, are there any historical examples where techniques yielding a relativized separation between two classes have led to, or have been extended in such a way as to provide, an unrelativized proof?
Comment #7 April 11th, 2006 at 1:43 am
Jon Yard: Are there any historical examples where techniques yielding a relativized separation between two classes have led to, or have been extended in such a way as to provide, an unrelativized proof?
Scott is more invested in this business than I am, but here is my answer anyway. The introduction to the paper is somewhat coy about just how hard it is to separate unrelativized complexity classes. Both QMA and QCMA contain P and are contained in PSPACE, and both inclusions are thought to be miles away from equalities. But no one can even prove that P = PSPACE. If you had your heart set on whether QMA = QCMA, you are in rather better shape if they actually are equal.
Our quantum oracle separation somewhat dampens that hope. I personally doubt that QMA = QCMA. The introduction is a little coy about that too, because we don’t want to come across as naive types who still cling to the random oracle hypothesis. (This is the evidently false hypothesis that a random oracle is a lot like the trivial oracle.) But I do not deny stuffing random oracle hypothesis Twinkies at night when no one can see.
Anyway, to get back to your question, there has been some progress in cashiering a relativized equality into an unrelativized one. People conjecture that P = BPP, and relativized equalities seem to have helped for this question.
Comment #8 April 11th, 2006 at 1:45 am
Sorry, no one can even prove that P does not equal PSPACE.
Comment #9 April 11th, 2006 at 2:35 am
So you ask yourself this question, do you? Twenty times a day? Do you wallow in self-doubt, torture yourself?
I certainly hope so, for the sake of your sanity. A fanatic wouldn’t.
Comment #10 April 11th, 2006 at 2:37 am
“relativized equalities seem to have helped for this question”
Greg, I don’t know what you mean. A relativized equality is trivial (as much so as the one between P and NP), and has absolutely no relevance to the question.
Comment #11 April 11th, 2006 at 2:43 am
So you ask yourself this question, do you? Twenty times a day? Do you wallow in self-doubt, torture yourself?
I do wallow in self-doubt, though often for reasons that have nothing to do with research. (What does that say about my sanity? 🙂 )
Comment #12 April 11th, 2006 at 2:55 am
Jon, I don’t know of any example, but there is a notion of positive relativization which is relevant here. Positive relativization for two classes C and D means that C^A = D^A for all A iff C = D. Of course the catch is in defining C^A & D^A; in known examples, the oracle access is rather restricted compared to the natural notion. “Structural Complexity 2” (Balcazar-Diaz-Gabarro) has a discussion.
Comment #13 April 11th, 2006 at 3:06 am
So my question is, are there any historical examples where techniques yielding a relativized separation between two classes have led to, or have been extended in such a way as to provide, an unrelativized proof?
Jon: The short answer is that there are almost no (nontrivial) unrelativized separations, period! So I think you’re asking for too much.
Perhaps the simplest argument for the value of oracle separations is the sheer number of people who have gone on wild gooses chases by ignoring them. An arXiv search will reveal claim after claim of polynomial-time quantum algorithms for NP-complete problems, by people who don’t get that Grover’s algorithm is optimal. Likewise, to me trying to prove QMA=QCMA without knowing the quantum oracle separation, or to find a quantum algorithm for Graph Isomorphism without knowing the black-box lower bounds, would be like trying to design a car engine without knowing the Second Law. But maybe I’m biased. 🙂
Comment #14 April 11th, 2006 at 3:17 am
John Baez is about as good at this as anyone and I rate his “This Week’s Finds” an A-.
In that case, I think your curve is too tough.
I doubt that you can match him at this game.
I didn’t realize I was competing with him! If you want to read about the mindblowing connections between category theory and nonabelian cohomology, you go to John’s blog. If you want to read about biting vaginas you go to mine.
Comment #15 April 11th, 2006 at 3:48 am
scott,
posting the same thing twice does not increase your grade.
Comment #16 April 11th, 2006 at 8:21 am
posting the same thing twice does not increase your grade.
That was Blogger’s fault, not mine. The server was down for a while, but I was finally able to log in and delete the second copy.
Comment #17 April 11th, 2006 at 11:17 am
cheshire cat: A relativized equality [of P and BPP] is trivial (as much so as the one between P and NP), and has absolutely no relevance to the question.
My point is that P = BPP relative to a random oracle. That result, or more precisely its proof, can be seen as a step towards the derandomization results that came later.
Comment #18 April 11th, 2006 at 11:25 am
Scott: In that case, I think your curve is too tough.
It is calibrated so as to produce a useful comparison of your blog, John’s postings, and the Complexity Zoo. John’s postings are very good and I don’t mean to denigrate them at all, but the Zoo is really great. Unfortunately, Wikification hasn’t done a whole lot for it, at least not yet.
Scott: I didn’t realize I was competing with [John Baez]!
I didn’t mean to suggest competition, only a comparison. But since you mention it, I don’t want to read about biting vaginas. That may have been a low point.
Comment #19 April 11th, 2006 at 12:37 pm
The plaintext abstract for your paper, both in this blog, and on the arxiv appears to say that your lower bound is Omega(2^n/(m+1)), whereas the actual pdf of your paper says Omega(sqrt(2^n/(m+1)), which I assume is your actual bound. Perhaps my browser is just not rendering squarroot signs for some reason.
Comment #20 April 11th, 2006 at 1:39 pm
The plaintext abstract for your paper, both in this blog, and on the arxiv appears to say that your lower bound is Omega(2^n/(m+1)), whereas the actual pdf of your paper says Omega(sqrt(2^n/(m+1))
Argh! That was a completely inexcusable error on my part. I just fixed it and submitted a replaced version to the arXiv. Thank you for pointing it out.
Comment #21 April 11th, 2006 at 2:08 pm
If someone who is running a medical clinic in India etc asks you to justify what you do, you can tell them that the world we live in is slightly better than it would otherwise be due to the efforts of hundreds of thousands of people like them who have done work that appears to be useful, and has been transformed beyond recognition by the appearently useless logic games of a few thousand people who explored fundamental issues in physics, math, etc.
Of course, your justification will be a misdirection, as the people who do what you do are basically doing it because it’s your nature to do so, and the people who run medical clinics are doing what it is their nature to do. Anyone who was actually trying to serve the good of humanity in a manner that came close to being efficient would spend more time investigating transhumanist issues, probably starting with http://www.nickbostrom.com or http://www.singinst.org, but possibly starting with http://www.crnano.org depending on their disposition.
You said…
“In the end, if someone who’s running a medical clinic in India, suing gun companies, canvassing for the Democrats, etc. asks me to justify what I do, I don’t have a response.
If a sportswriter or casino manager or fashion designer asks me to justify what I do, I also don’t have a response, but for a different reason.”
Comment #22 April 11th, 2006 at 2:15 pm
But since you mention it, I don’t want to read about biting vaginas. That may have been a low point.
Not only did that post get more comments than any other I’ve written, but the discussion was only incidentally about vaginas — really it was about natural selection itself. You’re welcome to give my blog a B-, but I give your grading system a C. 🙂
Comment #23 April 11th, 2006 at 3:14 pm
Scott,
Please don’t worry about canvassing. I’m going to show your paper to a number of my philosophy majors (who are quite worried with the state of the world) but secretly want to know the answer to various metaphysical, ontological, and rational-theologic questions. By going out and canvassing themselves, they can do the work that needs to get done, and support you in trying to make sense of the intersubjective notion of proof.
I think the problem of the quantification of resources needed to give a proof that one has in fact accomplished some cognitive task, however, does occupy a significant place in political philosophy. If anyone in the administration is thinking at all, there seems to be some evidence that they are followers of a certain kind of Platonism (see for example, this piece from Harper’s: http://www.lacosapizza.com/shorris.html). In this view, there are some people (Plato’s Guardians) who can “know the Forms” — they know what Justice IS, really. Because of the limits of lesser beings, they cannot do the cognitive work of knowing the Forms. However, is there any technology by which they could prove their superior knowledge, that doesn’t require an equal (and possibly impossible) effort on the part of those who don’t know?
The importance of the blog, I think, is this — you are influencing the search engine to pick out certain things as important. Bloggers are especially beloved by the search engines. That has a tremendous impact on the very meaning of terms in our world.
Comment #24 April 11th, 2006 at 3:21 pm
Please don’t worry about canvassing. I’m going to show your paper to a number of my philosophy majors (who are quite worried with the state of the world) but secretly want to know the answer to various metaphysical, ontological, and rational-theologic questions. By going out and canvassing themselves, they can do the work that needs to get done, and support you in trying to make sense of the intersubjective notion of proof.
Thanks, Drew! I’ll try to do my part by making sense of the intersubjective notion of proof.
Comment #25 April 11th, 2006 at 4:07 pm
“Not only did that post get more comments than any other I’ve written”
Always a good measure of quality.
Comment #26 April 11th, 2006 at 5:01 pm
The short answer is that there are almost no (nontrivial) unrelativized separations, period! So I think you’re asking for too much.
Scott: I guess I expected a negative answer here. However, I was hoping that there was at least one nontrivial example (like maybe some obscure circuit classes or something) where a conjectured separation was first proved with relativization, after which more clever arguments removed the relativization. I would have been happy with evidence that some relativized proof of equality extended to a nonrelativized one too. While this might be too much to “hope” for as well, I like Greg’s answer:
My point is that P = BPP relative to a random oracle. That result, or more precisely its proof, can be seen as a step towards the derandomization results that came later.
I guess derandomization can be viewed as weakening the power of the randomized oracle.
In Shannon theory, there are plenty of proofs that proceed by first assuming some extra resources like shared common randomness or an extra noiseless side channel, which are then shown not to increase some capacity. However, the arguments used to remove those resources are often next to trivial, like “the expectation of the fidelity over an ensemble of random codes is large, therefore there exists some deterministic code performing almost as well.” Of course, things are much more difficult if you want efficiently implementable codes..
Comment #27 April 11th, 2006 at 5:23 pm
Of course, your justification will be a misdirection, as the people who do what you do are basically doing it because it’s your nature to do so, and the people who run medical clinics are doing what it is their nature to do.
Maybe around Aristotle’s time “he does it because it’s in his nature to do so” would have been considered a serious argument when it concerns something as complex as running a medical clinic, but in 2006 it’s, frankly, embarrassing.
Anyone who was actually trying to serve the good of humanity in a manner that came close to being efficient would spend more time investigating transhumanist issues, probably starting with http://www.nickbostrom.com or http://www.singinst.org, but possibly starting with http://www.crnano.org depending on their disposition.
If you think Nick Bostrom’s patently ridiculous thought experiments do more good for humanity than a medical clinic in India you need to have your head examined. Ditto for the rest.
Sorry for the harsh tone, but something about the combination of confidence and philosophical naivitet that your post oozes of just struck a nerve.
Comment #28 April 11th, 2006 at 5:31 pm
Anonymous: I also disagree with much of what Michael said, but dude — stop being a troll.
Comment #29 April 11th, 2006 at 5:41 pm
Jon: Well, take any of the nonrelativizing collapses or separations that we know: IP=PSPACE, MIP=NEXP, MA_{EXP} is not in P/poly, PP doesn’t have linear size circuits…
For all of these, it’s easy to give an oracle relative to which the statement in question is true (as a simple example, IP^PSPACE = PSPACE^PSPACE). Trouble is, you can also give oracles relative to which the statements are false! (Though it’s much more difficult in the MA_{EXP} and PP cases.)
In any event, I don’t think you can say that the oracle results “led to” the unrelativized ones. But they were a central part of the context for discussing these issues in the first place.
Comment #30 April 11th, 2006 at 6:43 pm
For all of these, it’s easy to give an oracle relative to which the statement in question is true (as a simple example, IP^PSPACE = PSPACE^PSPACE). Trouble is, you can also give oracles relative to which the statements are false! (Though it’s much more difficult in the MA_{EXP} and PP cases.)
This touches upon why, or rather when, I think that oracles can still provide some evidence about about the real world, unrealistic though they may be. PSPACE is probably a blatantly unrealistic oracle. The random oracle is also unrealistic. However, the whole tenor of derandomization arguments is that a BPP machine is probably not smart enough to distinguish it from a pseudo-random ersatz generated in P. A PSPACE machine is smart enough to distinguish a random oracle from many other things, especially given that PSPACE = IP with respect to a trivial oracle, but not with respect to a random oracle.
Is a QMA machine smart enough to distinguish a random quantum oracle from a computed ersatz? It’s conceivable, because QMA is a fairly powerful class. But don’t hold your breath!
Comment #31 April 11th, 2006 at 6:44 pm
I tried to print the zoo for reading at bed, but it was too polluted by quantum related classes. Is there any way to filter this stuff out?
I don’t want to be a troll here, but… Well… I mean… Quantum computing disturbs me. If *it* is the future, stop the world, I wanna get off!
Comment #32 April 11th, 2006 at 6:52 pm
I tried to print the zoo for reading at bed, but it was too polluted by quantum related classes. Is there any way to filter this stuff out?
You can imagine, if you like, that the quantum classes are actually just strange classical classes that happen to involve unit vectors in 2^n-dimensional Hilbert space.
Comment #33 April 11th, 2006 at 9:27 pm
Scott: You can imagine, if you like, that the quantum classes are actually just strange classical classes that happen to involve unit vectors in 2^n-dimensional Hilbert space.
But that’s a terrible interpretation! It is just as gauche as the analogous interpretation of BPP – a strange deterministic classe that happens to involve unit vectors in a 2^n-dimensional ell^1 space.
I am not sure why osias feels disturbed by quantum complexity classes, but one germane point is that none of the quantum classes are known to be realistic, and even if quantum computers did exist, most of them still wouldn’t be realistic. Indeed given that PP = PostBQP, PP should be one of the “disturbing” ones, for whatever reason, except that it also has a classical definition. I.e. PP is defined by the preponderance of witnesses (which is not as unreasonable as calling BQP or BPP strange deterministic classes).
Comment #34 April 12th, 2006 at 5:02 am
Anonymous: I also disagree with much of what Michael said, but dude — stop being a troll.
You’re right. Reading it now I see that I went too far. Michael, my apologies.
I had a feeling even while writing it that what I was about to post wasn’t really kosher, but as I said, something just struck a nerve. I guess my past history of vehemently arguing with transhumanist didn’t help in forming a nice response.
Comment #35 April 12th, 2006 at 12:22 pm
I think some aspects of the Michael Vassar/Nick Bostrom stuff are clearly correct. The potential consequences of a nanotechnological arms race, for example, are obviously much greater than those of a medical clinic. The debatable part is whether there is anything people like us can do to influence the likelihood of such things. It seems to me that the political influence of scientists is now much less than what it was 50 years ago.
Comment #36 April 12th, 2006 at 12:56 pm
It seems to me that the political influence of scientists is now much less than what it was 50 years ago.
You think so? 🙂
Comment #37 April 12th, 2006 at 1:39 pm
Choosing 50 years may have been in some sense unfair of me. It seems a reasonable interpretation of history to say that the usual state of affairs is for scientists to be ignored, and that scientists temporarily gained an anomalous degree attention and influence upon inventing nuclear weapons.
Comment #38 April 12th, 2006 at 3:54 pm
Scott, did you delete a sentence from the sixth paragraph last night, or did I just dream that?
Comment #39 April 12th, 2006 at 5:16 pm
I think you dreamed it.
Comment #40 April 12th, 2006 at 6:28 pm
scott would you be so kind, if you have some spare time, to post a list of textbooks that you’ve read in math and cs?
Comment #41 April 12th, 2006 at 8:02 pm
or, even better, textbooks that graduate students in theory would benefit from reading
Comment #42 April 13th, 2006 at 7:21 am
I’m not Scott, but thought you might like some info anyway: Re math books (and some physics as well), Prof. Gerard ‘t Hooft has a nice list on his web site.
Comment #43 April 13th, 2006 at 1:38 pm
Anon:
No problem. Transhumanists can be annoying, like any other group, but Nick’s thought experiments are extremely practical, not patently ridiculous.
Do you really want a causual explanation of how the scientist and the clinician differ. Obviously I can’t give you one, but Aristotle would have known that there was one too.
I think scientists had some political influence in the late 17th century too, and maybe a bit in the late 18th century, but the 50s were anomylous.
My extremely thorough investigation of the field convinces me that scientists can have influence through non-political channels. Obviously encouraging research to focus on certain techniques rather than others is part of what I am talking about, though not the whole of it. Working for relatively responsible regimes rather than irresponsible ones is another bit. There’s a lot really.
Scott:
I’d really appreciate a response more than a defense.
Comment #44 April 13th, 2006 at 3:41 pm
I’d really appreciate a response more than a defense.
Sorry about that! A decent response will really deserve a blog entry of its own. For now, read this Crooked Timber post by Henry Farrell. It sums up many of my feelings about transhumanism as a secular religion — complete with sacred literature (science fiction novels), gurus (Ray Kurzweil), an afterlife (cryonics), and an End Times scenario culminating in a final “Rapture of the Nerds” (the singularity).
I’m well aware that this isn’t an argument against specific claims about nanotechnology, cryonics, etc. — it’s merely a cause for suspicion. In the 20th century, we saw at least three other examples of atheistic, “hyper-rational” ideologies that nevertheless had clear religious overtones: Marxism, Freudianism, and Objectivism.
I will say that I’ve found certain transhumanist sympathizers, like Robin Hanson and Nick Bostrom, much more interesting to read and argue with than Marxists, Freudians, or Objectivists. 🙂