Quantum computers are not known to be able to solve NP-complete problems in polynomial time,
and can be simulated classically with exponential slowdown.

Scott, it’s your blog – but can’t we switch back to some QC or TCS topics?

I confess: after three years of staid, dignified posts about quantum computing and theoretical computer science, I somehow did the unthinkable, and let this once-respected blog become less about elucidating research than procrastinating from it. Many readers, or so they tell me, rely on Shtetl-Optimized to keep abreast of the latest theoretical insights. And rather than ask those readers whether they also rely on deep-fried Snickers bars for the Vitamin E in the peanuts, I have a moral obligation to serve them.

Fortunately for the theory-starved among you, a certain je ne sais quoi in the air last week has caused me to refocus my attention on research. The mysterious force affected not only me, but seemingly my entire floor of the Stata Center—giving rise to a carnival-like crescendo of increasingly-frantic theorizing that ended just as inexplicably as it began, around 6:59PM Thursday night.

So today, I’m proud to post something vaguely related to science once again. On the suggestion of Wim van Dam, I hereby announce another contest, with no prize or even possibly winner. Your task is simple:

Come up with a catchy name for growth rates of the form 2^{n^α}, 0<α<1.

The word “subexponential” is often used, but should not be, since we already use it for growth rates smaller than 2^{n^α} for all α>0.

This just in: Friend-of-the-blog Greg Kuperberg, who’s always more fun than a cinder block combined with a reprimand, informs me that 2^{n^α} growth rates already have a name: stretched exponentials. But

I’ve never heard that term in my life,

I don’t like it: it sounds like something bigger than exponential, not smaller, and

Having called 2^{√n} “subexponential” in his otherwise-great paper on a quantum algorithm for the Dihedral Hidden Subgroup Problem, for Greg to now lecture others on this issue seems like … stretching it.

So my and Wim’s challenge to the readerariat stands.

Almost two years ago, a reader named Lev R. won my Best Anthropicism Contest with the following gem:

why aren’t physicists too interested in computational complexity? because if they were, they’d be computer scientists.

As the champion, Lev won the right to ask any question and have me answer it on this blog. Here was Lev’s question:

I like your “Earth Day, Doomsday, and Chicken Little” post, but you dodged the big question. Will the world end (humans go extinct) anytime soon? Or do you think that despite our best efforts, we’ll somehow end up not destroying ourselves?

In general, I despise being asked to make predictions, even about infinitely less weighty topics — especially when there’s a chance of my being wrong, and people looking back Nelson-Muntz-like and saying “ha ha, Scott was wrong!” That’s one of only several reasons why I could never be a physicist.

An answerable question would be one that asked me to clear up a misconception, or render a moral judgment, or discuss the consequences of a given assumption. (Unanswerable: “When will we see useful quantum computers?” Answerable: “Didn’t that company in Vancouver already build one?”) Questions about relationships between complexity classes or other unsolved math problems are also fine. But as for the universe, how am I supposed to know what it’ll decide to do, among all the things it could do within reasonable bounds of physics and logic? How am I even supposed to have a prior? As a CS theorist, I’m trained to think not about what’s likely to happen, but about the very worst that could happen — within stated assumptions, of course. Among the practical consequences of this attitude, I never gamble and I never play the stock market (and not only because, while there are many things I want, almost none of them can be traded for money). I also don’t worry about being put out of a job by prediction markets. Where the Bayesian stops, and says “every question beyond these is trivial or meaningless,” that’s where I’m just getting started.

But despite everything I’ve said, after years of diligent research into the future of the human race — reading hundreds of trillions of books and articles about climate change, overpopulation, Peak Oil, nuclear proliferation, transhumanism, AI, and every other conceivably relevant topic (what do you think I was doing, writing CS papers?) — I am finally prepared, this somber April 1^{st}, to answer Lev’s question with the seriousness it deserves. Obviously my predictions can only be probabilistic, and obviously I can’t give you the deep reasons behind them — those would take years to explain. I shall therefore present the human future, circa 2100, in the form of a pie chart.

In a recent talk at MIT, Umesh Vazirani appealed to the famous Birthday Paradox to say that two random subsets of {1,…,N}, each of size o(√N), probably wouldn’t intersect each other. Of course we all understood what he meant, but it occurred to me that Umesh was actually appealing to the Birthday Unparadox: “If you put three people in a room, chances are no two of them will have the same birthday.”

Once I realized that, I started seeing unparadoxes everywhere I looked:

The Banach-Tarski Unparadox: If you cut an orange into five pieces using a standard knife, then put them back together, the result will have exactly the same volume as the original orange.

Braess’ Unparadox: If you add an extra lane to a highway, one possible result will be to decrease congestion.

Hempel’s Unparadox: If you observe a bunch of ravens and find that all of them are black, this might increase your likelihood for the statement “All ravens are black.”

Russell’s Unparadox: The set of all sets that contain themselves as a member, might or might not contain itself as a member (either way is fine).

In the spirit of my highly-successful Best Umeshism and Best Anthropicism contests (remember those?), I now open the floor to you: come up with the best unparadox! The winner will receive absolutely nothing. (If you have to ask what the point is, this contest isn’t for you.)

For those of you who’ve been living in a non-wifi-enabled cave, four days ago Stephen Wolfram awarded a $25,000 prize to a 20-year-old undergraduate named Alex Smith, for proving that a particular two-state, three-symbol Turing machine is universal. The prize was to celebrate the fifth anniversary of Wolfram’s paradigm-smashing, foundation-shaking masterpiece, A New Kind of Science. (More from Bill Gasarch’s blog, Nature, and Scientific American.)

Smith sounds like a swell guy who entered this contest for exactly the right reasons: he was at his parents’ place over summer break and had nothing better to do. He deserves the money, and I sincerely hope the CS theory community hasn’t heard the last from him.

Predictably, though, as soon as this story broke I started getting emails from journalists asking me about the far-reaching scientific implications of the new universality proof. In trying to give them an honest answer — one that wouldn’t be misunderstood, or spun to support a pre-existing storyline with which I disagreed — I inevitably came off like an ornery old sourpuss. From Scientific American:

Of course, there may be a reason the problem languished. “Finding the smallest universal [Turing machines] is a neat recreational pursuit,” quantum computation researcher Scott Aaronson of the Massachusetts Institute of Technology says, but “it’s no longer seen as connected to the central questions of the field.” …

“The impact of NKS on all the areas of computer science and physics I’m familiar with has been basically zero,” he says. “As far as I can tell, the main impact is that people now sometimes use the adjective ‘Wolframian’ to describe breathtaking claims for the trivial or well-known.” [Martin] Davis offers a sunnier take: “The book has a lot of beautiful pictures.”

And from Nature:

The solution isn’t hugely relevant to modern computer science, says Scott Aaronson, a computer scientist at the Massachusetts Institute of Technology (MIT) in Cambridge, Massachusetts. “Most theoretical computer scientists don’t particularly care about finding the smallest universal Turing machines,” he wrote in an e-mail. “They see it as a recreational pursuit that interested people in the 60s and 70s but is now sort of ‘retro’.”

Having partially degrumpified, in the remainder of this post I wish to offer something positive.

But first some background: a month after NKS came out, I wrote a review of it for the journal Quantum Information and Computation, in which I examined Wolfram’s claims about quantum mechanics and computational complexity, and explained what I saw as the problems with them. (Rather than rehash the review, I’ll just point you there if you’re interested.)

Today I’d like to celebrate the fifth anniversary of my critical review of NKS, by offering a $25 prize for stodgy, conventional work in the field of quantum complexity theory.

The Aaronson $25.00 Challenge

In NKS, Wolfram places himself among those computer scientists and physicists who doubt the possibility of quantum computers, not for any practical reason but as a consequence of their disbelieving quantum mechanics itself. As he writes on page 771:

Indeed within the usual formalism [of quantum mechanics] one can construct quantum computers that may be able to solve at least a few specific problems exponentially faster than ordinary Turing machines. But particularly after my discoveries in Chapter 9 ['Fundamental Physics'], I strongly suspect that even if this is formally the case, it will still not turn out to be a true representation of ultimate physical reality, but will instead just be found to reflect various idealizations made in the models used so far.

Here, then, is the challenge:

If a quantum computer can efficiently solve a problem, can it also efficiently convince Wolfram that the solution is correct? More formally, does every language in the class BQP admit an interactive protocol where the prover is in BQP and the verifier is in BPP?

In other words: can quantum computers always “show their work”? It’s obvious, for example, that if a quantum computer spit out the factors of a 5,000-digit number, you wouldn’t have to believe quantum mechanics (or even know what it was) to check whether the answer was right. I’m asking whether every problem solvable by a quantum computer has the same property. And to make things fair to the quantum computer, I’ll let it give not just a static proof but also an interactive protocol, by which a distrustful polynomial-time classical verifier could become convinced, to arbitrarily high confidence, that the quantum computer knows the right answer.

(An example for the uninitiated: suppose you had two graphs G and H, and suppose you picked one of the graphs at random, randomly permuted its vertices, and gave the result to a quantum computer. And suppose the quantum computer could unfailingly tell you which graph you started with. Clearly this should convince you that G and H are not isomorphic — since if they were isomorphic, then the quantum computer couldn’t have done better than guessing! And this is true even though you never received a proof of non-isomorphism that you could hand to someone else.)

I’ll award $25 either for a proof that every quantum computation can be “counter-Wolframized,” or for an oracle relative to which some quantum computation provably can’t be. If both problems are solved then I’ll award $25 for each. Every serious submission will be reviewed by a Prize Committee consisting of me. The Committee may also choose to award smaller prizes for partial results.

Note: Much as I’d like to “pull a Wolfram,” the beautiful question above was (to my knowledge) first asked by Daniel Gottesman, at a conference in February 2004. Also, the idea of a $25 prize was suggested to me by Mike Mosca.

Update (10/30): A commenter pointed me to this thread in the Foundations of Mathematics (FOM) mailing list, which contains an actual technical discussion of Smith’s universality proof. Of particular interest:

an argument by Vaughan Pratt that Smith’s universality proof is wrong,

a post from Wolfram himself, which, though written in his trademark way, comes the closest I’ve seen of anything by him to addressing actual hard questions about the definition of universality, and

this comment from John McCarthy: “In the 1950s I thought that the smallest possible (symbol-state product) universal Turing machine would tell something about the nature of computation. Unfortunately, it didn’t. Instead as simpler universal machines were discovered, the proofs that they were universal became more elaborate, and [so] did the encodings of information.”

In judging the correctness of Smith’s proof, the key question is what counts as “universality.” As I explained to the journalists who emailed me, the rules of Wolfram’s prize left a huge gray area by explicitly refusing to specify this. In particular: what kinds of input and output encodings are allowed? How do we make sure the real computational work is done by the Turing machine itself and not the encoding procedures? Does the tape have to be filled with 0’s initially, or can it be filled with other patterns, and if so which ones? Since the two-state Turing machine in question has no “halt” state, what external conditions can we impose to determine when the machine has halted?

Still, I decided not to make a fuss about such things in my original post, since it seemed clear from Smith’s writeup that (1) he was aware of these issues, and (2) there was some nontrivial sense in which he proved universality. I wasn’t going to lose sleep over which sense, for the simple reason that I’d never lost sleep over the (2,3) universality question itself!

So, my Best Anthropicism Contest elicited almost 50 submissions. Thanks so much to everyone who entered — if not for you, this tautological tug-of-war would’ve been something other than what it was!

To choose the winning entry, the first rule I adopted was that, when I did find the winning entry, conditions would have to be such as to make it the winning entry, since otherwise it wouldn’t be the winning entry in the first place, but rather a losing entry. Since that didn’t get me very far, I quickly fell back on other criteria.

First, the winning entry would have to be short — longwinded explanations were out right away.

Second, it would have to make sense.

Third, it would have to illustrate the anthropic principle specifically, not some sort of generic Zen wisdom.

That already killed most of the entries. Among the ones left, many dealt Hofstadterifically with the contest itself:

wolfgang: Applying the principle of mediocrity I have to conclude that it is unlikely that I will win this contest.

Matt Wedel: Oh, c’mon! Just give me the prize! If I wasn’t going to win, I’d be living in a different universe where I didn’t win. BUT — I’m not. So give me the prize.

MX: Why am I entering this contest? Because if I weren’t, I wouldn’t be me, I would be a being very similar to me living in a universe in which I did not enter this contest.

Other entries worked well as parody:

sockatume: How much wood could a woodchuck chuck if a woodchuck could chuck would? As much wood as a woodchuck could chuck if a woodchuck could chuck would, otherwise it wouldn’t be a woodchuck.

Bram Cohen: Why have all dates thus far come before January 1, 3000? Because the universe will cease to exist on that day.

In the end, though, I decided that what I was looking for wasn’t mere wit, but the real, genuine illusion of explanatory insight. And that’s why Lev R. takes the prize, with the following perspicacious pearl:

why aren’t physicists too interested in computational complexity? because if they were, they’d be computer scientists.

I arrived this morning in Prague for the 2006 Complexity conference. Soon I’ll have the photos to prove it. For now, though, I wish to blog neither about the breathtakingly beautiful city in which I find myself, nor about the meaty, succulent topic alluded to in my previous post, but instead about anthropicisms.

Inspired by Peter Woit’s almost-daily anti-anthropic broadsides, and in the spirit of my earlier Best Umeshism Contest, I hereby announce a new contest for Best Application of the Anthropic Principle. Here are a few samples to get the self-selected tautological ball rolling, not that it could do otherwise than roll:

Why do so many people seem to care about being remembered after they die? Because we only remember the ones who cared about being remembered.

Academics comprise only a tiny portion of humanity, so what are the chances of being an academic as opposed to someone else? Conditioned on asking such a question in the first place, pretty high.

Why is the moon round? Because if it were square, you wouldn’t be you — you would instead be a being extremely similar to you, except that he or she lives in a universe with a square moon.

Why am I a blogger? Because if I weren’t, you wouldn’t be reading this.

The rules are similar to the Best Umeshism Contest: up to three entries per person. Please include a name — despite the nature of the contest, “He Who Posted This” doesn’t count. Entries must be in by July 22nd. The winner (as chosen by me) gets to ask any question and have me answer it here.

As winner of the Best Umeshism Contest (remember that?), Peter Brooke earned the right to ask me any question and have me answer it on this blog. Without further ado, here is Peter’s question:

If it is assumed that God exists, what further, reasonable, conclusions can be made, or is that where logical inquiry must end? Reasonable means in the light and inclusive of present scientific understanding. Defend any assumptions and conclusions you make.

At least Peter was kind enough not to spring “Is there a God?” on me. Instead, like a true complexity theorist, he asks what consequences follow if God’s existence is assumed.

Alas, Peter didn’t say which God he has in mind. If it were Allah, or Adonai, or Zeus, or the Flying Spaghetti Monster, then I’d simply refer Peter to the requisite book (or in the case of the Spaghetti Monster, website) and be done. As it is, though, I can’t assume anything about God, except that

He exists,

He created the universe (if He didn’t, then it’s not He we’re talking about), and

He’s a He.

(Note for Miss HT Psych: the third assumption is a joke.)

So the only way I see to proceed is to start from known facts, and then ask what sort of God would be compatible with those facts. Though others might make different choices, the following facts seem particularly relevant to me.

About 700,000 children each year die of malaria, which can easily be prevented by such means as mosquito nets and the spraying of DDT. That number will almost certainly grow as global warming increases the mosquitoes’ range. As with most diseases, praying to God doesn’t seem to lower one’s susceptibility or improve one’s prognosis.

According to our best theories of the physical world, it’s not enough to talk about the probability of some future event happening. Instead you have to talk about the amplitude, which could be positive, negative, or even complex. To find the probability of a system ending up in some state, first you add the amplitudes for all the ways the system “could” reach that state. Then you take the absolute value of the sum, and lastly you take the square of the absolute value. For example, if a photon could reach a detector one way with amplitude i/2, and another way with amplitude -i/2, then the probability of it reaching the detector is |i/2 + (-i/2)|^{2} = 0. In other words, it never reaches the detector, since the two ways it could have reached it “interfere destructively” and cancel each other out. If we required the amplitudes to be positive or negative reals rather than complex numbers, there would be some subtle differences — for example, we could just square to get probabilities, instead of taking the absolute value first. But in most respects the story would be the same.

From 1942 to 1945, over a million men, women, and children died in one of four extermination complexes at Birkenau, or “Auschwitz II” (Auschwitz I was the smaller labor camp). Each complex could process about 2,500 prisoners at a time. The prisoners were ordered to strip and leave their belongings in a place where they could find them later. They were then led to an adjacent “shower room,” containing shower heads that were never connected to any water supply. Once they were locked inside, guards dropped pellets from small openings in the ceiling or walls. The pellets contained Zyklon B, a cyanide-based nerve agent invented in the 1920′s by the German Jewish chemist Fritz Haber. The guards then waited for the screams to stop, which took 3-15 minutes, depending on humidity and other factors. Finally, Sonderkommandos (prisoners who were sent to the gas chambers themselves at regular intervals) disposed of the bodies in the adjacent crematoria. With the arrival of 438,000 Hungarian Jews in 1944, the crematoria could no longer keep up, so the bodies were burned in open pits instead. Besides those killed at Auschwitz, another 1.6 million were killed at the four other death camps (Sobibor, Belzec, Treblinka, and Chelmno). In the USSR and Poland, another 1.4 million were shot in front of outdoor pits by the Einsatzgruppen; still others died through forced starvation and other means. Judged on its own terms, the extermination program was a spectacular success: it wiped out at least 2/3 of Russian and European Jewry and changed the demography of Europe. The Americans and British declined numerous opportunities to take in refugees, or to bomb the camps or the train tracks leading to them. Most of the perpetrators, except for a few top ones, returned to civilian life afterward and never faced trial. Millions of people today remain committed to the goal of a Judenrein planet; some, like my friend Mahmoud, are working to acquire nuclear weapons.

According to our best description of space and time, the faster an object is moving relative to you, the shorter that object will look in its direction of motion, and the slower time will pass for it as observed by you. In particular, if the object is moving at a fraction f of the speed of light, then it will contract, and time will slow down for it, by a factor of 1/(1-f^{2})^{1/2}. This does not mean, as some people think, that concepts like “distance” have no observer-independent meaning — only that we were using the wrong definition of distance. In particular, suppose an observer judges two events to happen r light-years apart in space and t years apart in time. Then the interval between the events, defined as r^{2}-t^{2}, is something that all other observers will agree on, even they disagree about r and t themselves. The interval can also be defined as r^{2}+(it)^{2}: in other words, as the squared Euclidean distance in spacetime between the events, provided we reinterpret time as an imaginary coordinate. (This is known as “Wick rotation.”)

When I was younger, my brother and I went to an orthodontist named Jon Kraut. Dr. Kraut was a jovial guy, who often saw me on weekends when I was home from college even though his office was officially closed. He was also an aviation enthusiast and licensed pilot. About a week ago, Kraut was flying a twin-engine plane to South Carolina with his wife, Robin, their three kids (ages 2, 6, and 8), and the kids’ babysitter. Kraut reported to the control tower that he was having problems with his left engine. The plane made one approach to the airport and was coming back to try to land again when it crashed short of the runway, killing the whole family along with the babysitter. On the scale of history, this wasn’t a remarkable event; I only mention it because I knew and liked some of the victims.

Now, based on the facts above, plus many others I didn’t mention, and “in the light … of present scientific understanding,” what can we say about God, assuming He exists? I think we can say the following.

First, that He’s created Himself a vale of tears, a theater of misery beyond the imagination of any horror writer. That He’s either unaware of all the undeserved suffering He’s wrought, or else unable or unwilling to prevent it. That in times of greatest need, He’s nowhere to be found. That He doesn’t answer the prayers of the afflicted, or punish evildoers in any discernible way. That He most likely doesn’t intervene in human affairs at all — though I wouldn’t want to argue with those who say He does intervene, but only for the worse.

Second, that He apparently prefers complex numbers to real numbers, and the L_{2} norm to the L_{1} norm.

Alright, we had 35 submissions for the Best Umeshism Contest, of which 23 were eligible (i.e., had a name and were posted by the deadline). After lengthy deliberation, the Shtetl-Optimized Executive Committee is pleased to announce a winner. But first, the runners-up:

If you’ve never broken the bed, you’re not experimenting enough. –Miss HT Psych

If you’ve never hit the ground while skydiving, you’re opening your parachute too early. –Ari

If you’ve never written a sentence fragment. –Andrew L.

If you win Scott’s contest, then you’ve probably spent too much time thinking of a good Umeshism. –Mohammad Mahdian

The following three anonymous entries also merited honorable mentions:

If you’ve never been fined $250,000, you’re paying too much for your DVDs.

If all your students graduate, then you’re spending too much time in your office.

If you’ve never missed a flight, then you don’t know what it’s like to show up at the airport, stand in the wrong line for 20 minutes, be denied a checkin, and then be told that there is nothing available for the next 5 days (through Christmannukah), and then only with a 7-hour layover. So how about this one: If you’ve ever missed a flight, you’re spending too much time in airports. Thank you for the advice, Umesh Vazirani.

As you may have noticed, a large proportion of entries are actually ironic commentaries on the Umeshism concept. But in the end, a simple focus on the high-order bits took the cake:

If you’ve never had children, then you’re spending too much time using protection. –Peter Brooke

Thanks to everyone who entered, and Happy New Year from your procrastinating, narcissistic friends here at Shtetl-Optimized!

If you’ve never missed a flight, you’re spending too much time in airports.

When I was a grad student at Berkeley, my advisor, Umesh Vazirani, liked to repeat this nugget of wisdom to students, friends, and colleagues. In a single sentence, Umesh was communicating an entire philosophy of life: concentrate on the high-order bits. The squash player who runs back and forth to attempt every shot, the student who’s never late with an assignment, the researcher who stalks an unimportant problem like Captain Ahab: all have succumbed to the tyranny of the low-order bit. They need to realize that, as in a randomized algorithm, occasional failures are the inevitable byproduct of a successful strategy. If you always win, then you’re probably doing something wrong.

On the other hand, having dropped Umesh off at 8PM for an 8:30 international flight, I can attest from personal experience that he was talking about actual air travel as well.

I thought about Umesh’s “Airport Law” on my way to Australia, after I nearly missed my flight out of Heathrow, and then did miss the connection from Sydney to Brisbane, after waiting for an hour in customs so that my luggage could be searched for any contraband fruit or vegetables. I wondered: what other “Umeshisms” are waiting to be discovered? Here are the first four I came up with:

If you never cut yourself while shaving, you’re not shaving close enough.

If you’ve never been robbed, you’re spending too much time locking doors.

If you’ve never been rejected, you’re not asking enough. (The easiest to state, the hardest to practice.)

If you’ve never regretted a blog entry, your blog is boring.

As a tribute to Umesh, I hereby open the comments section to a Best Umeshism Contest. The winner (as chosen by me) earns the right to ask any question, and then have me answer it on this blog, possibly after consulting with Umesh about the high-order bits. The deadline is December 28, 2005, 11:59PM EST. Limit three entries per person. Include your name and/or email.