Shtetl-Optimized

At least three people have now asked my opinion of the paper Mathematical Undecidability and Quantum Randomness by Paterek et al., which claims to link quantum mechanics with Gödelian incompleteness.  Abstract follows:

We propose a new link between mathematical undecidability and quantum physics. We demonstrate that the states of elementary quantum systems are capable of encoding mathematical axioms and show that quantum measurements are capable of revealing whether a given proposition is decidable or not within the axiomatic system. Whenever a mathematical proposition is undecidable within the axioms encoded in the state, the measurement associated with the proposition gives random outcomes. Our results support the view that quantum randomness is irreducible and a manifestation of mathematical undecidability.

Needless to say, the paper has already been Slashdotted.  I was hoping to avoid blogging about it, because I doubt I can do so without jeopardizing my quest for Obamalike equanimity and composure.  But similar to what’s happened several times before, I see colleagues who I respect and admire enormously—in this case, several who have done pioneering experiments that tested quantum mechanics in whole new regimes—making statements that can be so easily misinterpreted by a public and a science press hungry to misinterpret, that I find my fingers rushing to type even as my brain struggles in vain to stop them.

Briefly, what is the connection the authors seek to make between mathematical undecidability and quantum randomness?  Quantum states are identified with the “axioms” of a formal system, while measurements (technically, projective measurements in the Pauli group) are identified with “propositions.”  A proposition is “decidable” from a given set of axioms, if and only if the requisite measurement produces a determinate outcome when applied to the state (in other words, if the state is an eigenstate of the measurement).  From the simple fact that no one-qubit state can be an eigenstate of the σ_x and σ_z measurements simultaneously (in other words, the Uncertainty Principle), it follows immediately that “no axiom system can decide every proposition.”  The authors do some experiments to illustrate these ideas, which (not surprisingly) produce the outcomes predicted by quantum mechanics.

But does this have anything to do with “undecidability” in the mathematical sense, and specifically with Gödel’s Theorem?  Well, it’s not an illustration of Gödel’s Theorem to point out that, knowing only that x=5, you can’t deduce the value of an unrelated variable y.  Nor is it an illustration of Gödel’s Theorem to point out that, knowing only one bit about the pair of bits (x,y), you can’t deduce x and y simultaneously.  These observations have nothing to do with Gödel’s Theorem.  Gödel’s Theorem is about statements that are undecidable within some formal system, despite having definite truth-values—since the statements just assert the existence of integers with certain properties, and those properties are stated explicitly.  To get this kind of undecidability, Gödel had to use axioms that were strong enough to encode the addition and multiplication of integers, as well as the powerful inference rules of first-order logic.  By contrast, the logical deductions in the Paterek et al. paper consist entirely of multiplications of tensor products of Pauli matrices.  And the logic of Pauli matrix multiplication (i.e., is this matrix in the subgroup generated by these other matrices or not?) is, as the authors point out, trivially decidable.  (The groups in question are all finite, so one can just enumerate their elements—or use Gaussian elimination for greater efficiency.)

For this reason, I fear that Paterek et al.’s use of the phrase “mathematical undecidability” might mislead people.  The paper’s central observation can be re-expressed as follows: given an N-qubit stabilizer state |ψ〉, the tensor products of Pauli matrices that stabilize |ψ〉 form a group of order 2^N.  On the other hand, the total number of tensor products of Pauli matrices is 4^N, and hence the remaining 4^N-2^N tensor products correspond to “undecidable propositions” (meaning that they’re not in |ψ〉’s stabilizer group).  These and other facts about stabilizer states were worked out by Gottesman, Knill, and others in the 1990s.

(Incidentally, the paper references results of Chaitin, which do interpret variants of Gödel’s Theorem in terms of axiom systems “not containing enough information” to decide Kolmogorov-random sentences.  But Chaitin’s results don’t actually deal with information in the technical sense, but rather with Kolmogorov complexity.  Mathematically, the statements Chaitin is talking about have zero information, since they’re all mathematical truths.)

So is there a connection between quantum mechanics and logic?  There is—and it was pointed out by Birkhoff and von Neumann in 1936.  Recall that Paterek et al. identify propositions with projective measurements, and axioms with states.  But in logic, an axiom is just any proposition we assume; otherwise it has the same form as any other proposition.  So it seems to me that we ought to identify both propositions and axioms with projective measurements.  States that are eigenstates of all the axioms would then correspond to models of those axioms.  Also, logical inferences should derive some propositions from other propositions, like so: “any state that is an eigenstate of both X and Y is also an eigenstate of Z.”  As it turns out, this is precisely the approach that Birkhoff and von Neumann took; the field they started is called “quantum logic.”

Update (Dec. 8): I’ve posted an interesting response from Caslav Brukner, and my response to his response.

Follow

A year ago, a group of CS theorists—including Eli Ben-Sasson, Andrej Bogdanov, Anupam Gupta, Bobby Kleinberg, Rocco Servedio, and your humble blogger, and fired up by the evangelism of Sanjeev Arora, Christos Papadimitriou, and Avi Wigderson—agreed to form a committee to improve Wikipedia’s arguably-somewhat-sketchy coverage of theoretical computer science.  One year later, our committee of busy academics has done, to a first approximation, nothing.

In considering this state of affairs, I’m reminded of the story of Wikipedia’s founding.  Before Wikipedia there was Nupedia, where the articles had to be written by experts and peer-reviewed.  After three years, Nupedia had produced a grand total of 24 articles.  Then a tiny, experimental adjunct to Nupedia—a wiki-based peanut gallery where anyone could contribute—exploded into the flawed, chaotic, greatest encyclopedia in the history of the world that we all know today.

Personally, I’ve never understood academics (and there are many) who sneer at Wikipedia.  I’ve been both an awestruck admirer of it and a massive waster of time on it since shortly after it came out.  But I also accept the reality that Wikipedia is fundamentally an amateur achievement.  It will never be an ideal venue for academics—not only because we don’t have the time, but because we’re used to (1) putting our names on our stuff, (2) editorializing pretty freely, (3) using “original research” as a compliment and not an accusation, and (4) not having our prose rewritten or deleted by people calling themselves Duduyat, Raul654, and Prokonsul Piotrus.

So this Thanksgiving weekend, at the suggestion of my student Andy Drucker, I’m going to try an experiment in the spirit of Wikipedia.  I’m going to post our wish-list of theoretical computer science topics, and invite you—my interested, knowledgeable readers—to write some articles about them.  (Of course you’re welcome to add your own topics, not that you’d need permission.)  Don’t worry if you’re not an expert; even some stubs would be helpful.  Let us know in the comments section when you’ve written something.

Thanks, and happy Thanksgiving!

Research areas not defined on Wikipedia

• Property testing
• Quantum computation (though Quantum computer is defined)
• Algorithmic game theory
• Derandomization
• Sketching algorithms
• Propositional proof complexity (though Proof complexity is defined)
• Arithmetic circuit complexity
• Discrete harmonic analysis
• Streaming algorithms
• Hardness of approximation

Research areas ill-defined on Wikipedia

• Algorithmic mechanism design — extend beyond 4 sentences, and create link from Mechanism design article of Wikipedia
• Circuit complexity
• Online Algorithms

Basic terms not defined on Wikipedia

• Sparsest cut
• Metric embedding — also create link from Embedding article on Wikipedia
• Price of anarchy
• Combinatorial auction
• Glauber dynamics
• Locally testable code
• Locally decodable code (but the closely related Private information retrieval is defined)
• Average case complexity
• Worst case complexity
• Polynomial identity testing
• Unique games conjecture
• Primal-dual approximation algorithm

Basic terms ill-defined on Wikipedia

• Conductance (probability) — extend beyond 3 sentences
• Probabilistically checkable proofs
• Polynomial-time hierarchy
• Algorithms for matrix multiplication
• Max-flow min-cut
• Zero knowledge proof
• Model of computation
• List-decoding

Well-known theoretical computer scientists without Wikipedia pages

• No, I’m not going to make that list … but you can.

Update (11/30): A big shout-out and thank-you to those theorists, such as David Eppstein, who’ve actually been contributing to Wikipedia and not just theorizing about it!

Follow

1. There’s now a popular article by Lisa Zyga at physorg.com, about my paper with John Watrous on quantum computing with closed timelike curves. On the whole, I think Zyga did an excellent job at getting the facts (such as they are) correct.

2. Challenged ballots in the Coleman vs. Franken race: you be the judge!

3. One of the unfortunate things about not updating your blog often, I find, is that people assume you’re still obsessed with the last thing you blogged about, weeks after you’ve all but forgotten about it.  As it happens, I’ve now fully recovered from the joy of the election, and am back to my normal angst-ridden equilibrium.  On the other hand, I’ve not yet recovered from the STOC deadline.

4. My quest to become more obamalike in temperament is now officially a failure.   I should try it again sometime.

Follow

On balance? I’ll take it.

Follow

(Assuming you’re eligible?)

An argument I came up with a while ago is that, in an election with N voters, the probability of your vote swaying the outcome could be expected to scale like 1/√N—but the utility to the world if your vote does sway the outcome could be expected to scale like N.  Under those assumptions, the expected utility of your vote for the world scales like √N (or -√N, depending which candidate you vote for).  So if you care about the world even ~1/√N as much as you care about yourself, you should probably vote, even though your vote almost certainly won’t change the outcome.  Indeed, the case is even stronger in the US (at least if you live in a swing state), both because the electoral college amplifies the probability of your vote mattering (see the Majority-Is-Stablest Theorem), and because of the US’s disproportionate influence on the world.

A version of the above argument was discovered independently by Peter Norvig, who—appropriately for an applied rather than theoretical computer scientist—plugs in some actual numbers, rather than considering the asymptotics as the number of voters goes to infinity.  Norvig finds an expected value of your vote to the United States of about $1 million (or $6 trillion divided by a 1 in 6 million chance of your vote mattering).  Another version of the argument was given by Andrew Gelman, who points out that other people’s votes are actually not well-modeled by unbiased coin flips (unless you live in Florida, I guess)—but that even under a more realistic prior, your vote still has a constant expected value to society (i.e., it doesn’t decrease with the number of voters N).

I’m aware, of course, that the above is merely a nerdy, rational argument, of a sort that’s probably never actually convinced anyone in the entire history of the world, with the possible exception of Robin Hanson.  So let me raise the stakes a little.  Let me give you an emotional argument.

Did you see WALL-E?  My favorite scene in that predictably-excellent movie—a scene I confess almost brought me to tears—actually had nothing to do with WALL-E or his robo-love-interest EVE.  It was the scene aboard the spaceship Axiom, where the leaf symbol starts flashing overhead, indicating that the earth is once again able to support life, and the fat, coddled human passengers actually have to make a decision about whether to return to earth or not.  For the first time in 700 years, the spaceship’s course is not on autopilot.  Like children away from their parents, the humans face the terrifying realization that there’s no longer any higher authority to tell them what to do.  Or rather, their robot masters are trying to tell them what to do, but the humans are not obliged to listen.

See?  Just like an election.

Your vote almost certainly won’t change the outcome; indeed, thanks to the wonders of technology, there’s probably no way to verify it’ll even be counted.  But on the one day when that leaf is flashing … to have to tell posterity you were too busy finishing a problem set?

Naturally, I also think I know which way you should vote.  But even if you’re one of the humans who thinks the spaceship carrying the last remnant of humanity should remain floating in space—since although (and here I’m embellishing the movie) the spaceship’s power will soon run out, leaving all the humans dead, it’s conceivable that the power could be extended a few years by drilling a nearby asteroid (drill, baby, drill!)—even if that’s your belief system, still I think you should vote.  Why?  Because of my newfound Zen-like equanimity, combined with the belief that your candidate’s going to lose anyway.

Then, after you’ve voted, go into the comments section and ask me a question about what’s new in computational complexity.  As a commenter on my last post helpfully opined, it’s time to start tending my garden again.

Yes We Can.  Prove We Can’t.

Follow

Update (10/27): Peter Norvig at Google points me to his Election FAQ, for those who feel they haven’t yet spent enough time reading about the election.  I’ve just been perusing it, and it’s an unbelievably good source of information—reaching the same conclusions as I did on just about every particular, yet also calm, reasoned, and professional.

1. That’s my mom at an Obama office in Sarasota, FL.  For once, I find myself kvelling to strangers about her.

2. I’m at FOCS’2008 in Philadelphia right now.  Yesterday morning I gave a tutorial on The Polynomial Method in Quantum and Classical Computing, and was delighted by how many people showed up — I wouldn’t have woken up for my talk.  (And before you ask: yes, the PowerPoint slides for this talk include photographs of both Bill Ayers and Joe the Plumber.)

3. Here’s the FOCS conference program — tons of good stuff, as you can see for yourself.  If there’s a talk you want to know more about, say so in the comments section and I’ll try to find someone who attended it.

Note: I was a program committee member, and therefore know much more than usual about the talks—but my objectivity and license as a “journalist” are also severely compromised.  If unvarnished opinion is what you seek, ask my friend and roommate Rahul Santhanam, who’s also reporting live from the conference over at Lance’s blog.  (As you can see, we CS theorists manage our conflicts of interest roughly as well as the Alaska governor’s office…)

4. I apologize that I haven’t had much to say recently.  Against my better judgment, I find myself transfixed by the same topic everyone else is transfixed by, and it’s hard to find anything to say about it that hasn’t been said better by others.  If you want to enter my world, don’t read Shtetl-Optimized; read Andrew Sullivan or FiveThirtyEight.com.  Following the election is, of course, not all that different from following a football game, except for the added dash of excitement that the future of civilization might hinge on the outcome.

(Years congruent to 0 mod 4 are pretty much the only times when I understand what it’s like to be a sports fan.  Speaking of which, I heard there was some sort of “World’s Series” in Philadelphia last night—probably in basketball—and something called the “Phillies” won?  I might be wrong, though.  Maybe it was the “Flyers” … or is that a volleyball team?  Keep in mind, I only lived in this area for the first 15 years of my life.)

5. For a congenital pessimist like me, I confess it’s been difficult to deal with the fact that my team (I mean the Democrats, not the Eagles or whatever they’re called) is winning.  I simply don’t know how to react; it’s so far outside my emotional range.  Since when has the universe worked this way?  When did reason and levelheadedness start reaping earthly rewards, or incompetence start carrying a cost?  I’m sure Nov. 4 will bring something to console me, though: maybe Al Franken will lose the Senate race in Minnesota, or the homophobe proposition will pass in California…

6. Writing blog posts in numbered lists is easier; I should do it more often.  I don’t have to pretend all the little things I want to say are part of an overarching narrative, rather than standing in the relation “and that reminds me of … which in turn reminds me of…”

7. There’s another psychological question inspired by the election that’s fascinated me lately: how does one become more obamalike in temperament?

I’ve written before about Obama’s penchant for introspection and respect for expertise, which of course are qualities with which I strongly identify.  But Obama also has a crucial quality I lack: as the whole world has marveled, nothing rattles him.  Placed for two years under the brightest glare on earth, besieged by unexpected events, he simply sticks to a script, Buddha-like in his emotional control (although not in his quest for power in the temporal world).  His nerves are of carbon nanotube fiber.

When he briefly slipped behind after the Republican convention, I panicked: I felt sure he’d lose if he didn’t completely change his approach.  Sean Carroll recommended chilling out.  I now face the indignity of admitting that I was wrong while a physicist was right.

What struck me most, during the debates, was how again and again Obama would pass up the chance to score points—choosing instead to let his opponent impale himself with his own words, and use his time to hammer home his message for the benefit of any voters just emerging from their caves.  (As an example, consider his pointed refusal in the third debate to say anything bad about Palin—the subtext being, “isn’t it obvious?”)  It’s almost as if he thought his goal was winning the election, not proving the other guy wrong.

I have (to put it mildly) not always exhibited the same prudent restraint, least of all on this blog.  So for example, whenever there’s been bait dangling in front of me in the comments section, I’ve tended to bite, often ending up with a hook through my cheek.

But no more.  As the first exercise in my newfound quest for the Zen-like equanimity and balance of our soon-to-be-president, I now present to you two excerpts from the comments on my previous post, with no reaction whatsoever from me.

Have you considered the possibility that, in the same way a logical deduction is being equated with truth, understanding a thing is just an illusion? If a thing is logical, that only means that it appeals to the reasoning facility of the brain, not that it’s the truth.

Mathematics is just a place where it becomes clear how a human may think. Computers only go for the calculable. And the mathematical truths a computer can produce are at most countable infinite. But there are uncountable infinite truths.

Follow

I’m seeking a talented student for summer of 2009, to work with me in developing and experimenting with a new open-source web application.  I’m open to students from anywhere, though MIT students will receive special consideration for funding reasons.

The web app — tentatively called “Worldview Manager” — is intended to help people ferret out hidden contradictions in their worldviews.  Think of a kindly, patient teacher in a philosophy seminar who never directly accuses students of irrationality, but instead uses Socratic questioning to help them clarify their own beliefs.

The idea is extremely simple (as of course it has to be, if this app is to attract any significant number of users).  The user selects a topic from a list, which might include the following at the beginning:

Climate Change
The Singularity
Libertarianism
Computational Complexity
Interpretation of Quantum Mechanics
Quantum Computing
Gay Rights
Israel
Gifted Education
Foundations of Mathematics
Strong AI and Philosophy of Mind
Utilitarian Ethics
Animal Rights
Art and Aesthetics

Users will also be able to contribute their own topic files.  (The above list is biased toward those topics about which I feel like I could write a topic file myself.)

After choosing a topic, the user will be presented with a sequence of statements, one at a time and in a random order.  For example, if the topic is Foundations of Mathematics, the statements might include the following:

Math is a cultural construct.
Math privileges male, linear thinking over female, intuitive thinking.
The Continuum Hypothesis is either true or false, even if humans will never know which.
There’s a sense in which integers, real numbers, and other mathematical objects “existed” before humans were around to name them, and will continue to exist after humans are gone.

The user can indicate her level of agreement with each statement by dragging the cursor.

Now the topic file, in addition to the statements themselves, will also contain lists of pairs or sometimes triples of statements that appear (at least to the writer of the topic file) to be in “tension” with one another.  From time to time, the program will search the user’s previous responses for beliefs that appear to be in tension, point out the tension, and give the user the opportunity to adjust one or more beliefs accordingly.  For example, the user might get a message like the following:

You indicated substantial agreement with the statement

If a scientific consensus on climate change existed, then society would have to act accordingly.

and also substantial agreement with the statement

The so-called “consensus” on climate change simply reflects scientists’ liberal beliefs, and therefore does not necessitate action.

These views would seem to be in tension with each other.  Would you like to adjust your belief in one or both statements accordingly?

That’s about all there is to it.  No Bayesianism, no advanced math of any kind (or at least none that the user sees).

As you may have gathered, the writing of topic files is not a “value-neutral” activity: the choice of statements, and of which statements are in tension with which other ones, will necessarily reflect the writer’s interests and biases.  This seems completely unavoidable to me.  The goal, however, will be to adhere as closely as is practical to Wikipedia’s NPOV standard.  And thus, for example, any well-written topic file ought to admit “multiple equilibria”; that is, multiple points of view that are genuinely different from one another but all more-or-less internally consistent.

The student’s responsibilities for this project will be as follows:

• Write, debug, and document the web app.  This sounds straightforward, but it’ll be important to get the details right.  I’m not even sure which development tools would be best—e.g., whether we should use Java or JavaScript, do all computation on the server side, etc.—and will rely on you to make implementation decisions.
• Write topic files.  I can create many of the files myself, but it would be great if you could pitch in with your own ideas.
• Help run experiments with real users.
• Help write up a paper about the project.

If there’s time, we could also add more advanced functionality to Worldview Manager.  Your own ideas are more than welcome, but here are a few possibilities:

• Present statements to the user in a non-random order that more rapidly uncovers tensions.
• Allow users to register for accounts, and save their “worldviews” to work on later.
• Give users the ability to compare worldviews against their friends’, with large disagreements flagged for special consideration.
• Give users the ability to use a local search or backtrack algorithm to decrease the total “tension” in their worldviews, while changing their stated beliefs by the minimum possible amount.
• Enable adaptive follow-up questions.  That is, once two beliefs in tension have been uncovered, the user can be queried more specifically on how she wants to resolve the apparent contradiction.

I’m looking for someone smart, curious, enthusiastic, and hard-working, who has experience with the development of web applications (a work sample is requested).  Grad students, undergrads, high school students, nursery school students … it’s what you can do that interests me.

I expect the internship to last about three months, but am flexible with dates.  Note that in the year or so since I started at MIT, I’ve already worked with six undergraduate students, and three of these interactions have led or will lead to published papers.

If you’re interested, send a cover letter, cv, and link to a work sample to aaronson at csail mit edu.  If you want to tell me why the Worldview Manager idea is idiotic and misguided, use the comments section as usual.

Update (10/15): In a somewhat related spirit, Eric Schwitzgebel at UC Riverside points me to a study that he and a colleague are conducting, on whether professional philosophers respond differently than laypeople to ethical dilemmas.  Shtetl-Optimized readers are encouraged to participate.

Follow

Today Sean Carroll emailed various bloggers, defying us to participate in the DonorsChoose Blogger Challenge 2008.  Here’s how it works: we (the bloggers) pick projects that we like in underfunded public schools.  Then we beg our readers to donate small amounts of money to make those projects happen.  Any blogger whose readers can’t or won’t contribute is revealed as weak, pathetic, and inadequate—as are the readers themselves.

Now, do I seem like the sort of pusillanimous coward who would back down from such a direct challenge to his bloghood?  Who would cede the moral high ground to a physicist?

I do?

Then let the word echo from the mountaintops and RSS feeds.  I, Scott Aaronson, am now seeking to raise up to $7000 for public school teachers trying to:

• Help “gifted” students, meaning those blessed with the gifts of awkwardness, alienation, and solitude.  (Note that in the US, less than 0.02% of the federal education budget goes to this lucky group.)
• Teach evolution.
• Buy Art Spiegelman’s Maus (the acclaimed graphic novel about the Holocaust, and an astonishingly un-P.C. work for the classroom).
• Buy Twain’s Huckleberry Finn, the classic and oft-censored howl against doofosity.

Twain, incidentally, was the one who wrote that “in the first place, God made idiots. That was for practice. Then He made school boards.”  The genius of DonorsChoose is that it bypasses those pinnacles of God’s handiwork, letting you route money directly to deserving teachers.

So: if, in your time reading Shtetl-Optimized, you’ve enjoyed one entry, I ask you to go here and donate $10 to a featured project of your choice.  If you’ve enjoyed ten entries, I ask you to donate $25 (you get the bulk discount).  If you’ve enjoyed every entry (!), I ask you to donate $50 (that’s the Platinum Elite Package).

If you’re currently a student or Wall Street broker, you can of course scale down your donation appropriately.

And no, this won’t save the world or even swing the election.  But … sniff … maybe Sean Carroll will finally respect me.

Update (Oct. 6): Thanks so much, everyone!  So far we’ve raised $2,049 (counting my own small contribution).

Follow

Here’s what I saw the last time I went to Intrade (yes, I’ve been checking about 200,000 times per day):

I understand that in this situation, the Constitution dictates that the selection of a President goes to the IEEE 754R Technical Committee.

Joke-Killing Explanation for Non-Nerds: NaN is “Not a Number,” an error code in floating-point arithmetic for expressions like 0/0.  Evidently there’s a bug in Intrade’s script to add the expected electoral college votes.

Follow

Alright, no more politics for a while.  I’m sick of it.

Given the relative success of Open thread #1, I thought I’d give you the readers a second opportunity to ask about whatever’s on your minds, except politics.  Quantum complexity classes and painting elephants are definitely fair game.

(Update: One question at a time, please!)

(Update: Thanks for the questions, everyone!  The open thread is now closed.  We’ll do this again!)

Follow