Shtetl-Optimized

Grudgingly offered for your reading pleasure, and in the vain hope of forestalling further questions.

Q: Thanks to D-Wave Systems — a startup company that’s been in the news lately for its soon-to-be-unveiled “Orion” quantum computer — is humanity now on the verge of being able to solve NP-complete problems in polynomial time?

A: No. We’re also not on the verge of being able to build perpetual-motion machines or travel faster than light.

Q: But couldn’t quantum computers try all possible solutions in parallel, and thereby solve NP-complete problems in a heartbeat?

A: Yes, if the heart in question was beating exponentially slowly.

Otherwise, no. Contrary to widespread misconception, a quantum computer could not “try all possible solutions in parallel” in the sense most people mean by this. In particular, while quantum computers would apparently provide dramatic speedups for a few “structured” problems (such as factoring integers and simulating physical systems), it’s conjectured that they couldn’t solve NP-complete problems in polynomial time.

Q: But isn’t factoring an NP-complete problem?

A: Good heavens, no! While factoring is believed to be intractable for classical computers, it’s not NP-complete, unless some exceedingly unlikely things happen in complexity theory. Where did you get the idea that factoring was NP-complete? (Now I know how Richard Dawkins must feel when someone asks him to explain, again, how “life could have arisen by chance.”)

Q: How could the people at D-Wave not understand that quantum computers couldn’t solve NP-complete problems in polynomial time?

A: To his credit, Geordie Rose (the founder of D-Wave) does understand this; see here for example. And yet, essentially every article I’ve read about D-Wave gives readers exactly the opposite impression. The charitable explanation is that the D-Wave folks are being selectively quoted or misquoted by journalists seeking to out-doofus one another. If so, one hopes that D-Wave will try harder in the future to avoid misunderstandings.

Q: But even if it gave only polynomial speedups (as opposed to exponential ones), couldn’t the adiabatic quantum computer that D-Wave built still be useful for industrial optimization problems?

A: D-Wave’s current machine is said to have sixteen qubits. Even assuming it worked perfectly, with no decoherence or error, a sixteen-qubit quantum computer would be about as useful for industrial optimization problems as a roast-beef sandwich.

Q: But even if it wasn’t practically useful, wouldn’t a 16-qubit superconducting quantum computer still be a major scientific advance?

A: Yes, absolutely.

Q: So, can D-Wave be said to have achieved that goal?

A: As Dave Bacon pointed out earlier, it’s impossible to answer that question without knowing more about how their machine works. With sixteen qubits, a “working demo” doesn’t prove anything. The real questions are: how high are the fidelities, and what are the prospects for scalability?

Q: But clearly D-Wave isn’t going to give away its precious trade secrets just to satisfy some niggling academics! Short of providing technical specifics, what else could they do to make computer scientists take them seriously?

A: Produce the prime factors of

1847699703211741474306835620200164403018549
3386634101714717857749106516967111612498593
3768430543574458561606154457179405222971773
2524660960646946071249623720442022269756756
6873784275623895087646784409332851574965788
4341508847552829818672645133986336493190808
4671990431874381283363502795470282653297802
9349161558118810498449083195450098483937752
2725705257859194499387007369575568843693381
2779613089230392569695253261620823676490316
036551371447913932347169566988069.

Q: Alright, what else could they do?

A: Avoid talking like this:

The system we are currently deploying, which we call Trinity, is a capability-class supercomputer specifically designed to provide extremely rapid and accurate approximate answers to arbitrarily large NP-complete problems … Trinity has a front-end software interface, implemented in a combination of Java and C, that allows a user to easily state any NP-complete problem of interest. After such a problem has been stated the problem is compiled down to the machine language of the processors at the heart of the machine. These processors then provide an answer, which is shuttled back to the front end and provided to the user. This capability can of course be called remotely and/or as a subroutine of some other piece of software.

Or to translate: “Not only have we built a spaceship capable of reaching Pluto in a few hours, our spaceship also has tinted windows and deluxe leather seats!” If I were them, I’d focus more on the evidence for their core technological claims, given that those claims are very much what’s at issue.

Q: While Dave Bacon also expressed serious doubts about the Orion quantum computer, he seemed more enthusiastic than you are. Why?

A: Generous and optimistic by nature, Dave strives to give others the benefit of the doubt (as the Chinese restaurant placemat would put it). Furthermore, as Quantum Pontiff, he’s professionally obligated to love the quantum sinner and forgive the wayward quantum sheep. And these are all wonderful qualities to have. On the other hand, when the hype surrounding some topic crosses a certain threshold, arguably a pricklier approach becomes called for.

Q: If D-Wave fizzles out, will many journalists and policymakers then conclude that quantum computing is bunk?

A: It doesn’t seem unlikely.

Q: What would it take to get these people to recognize the most elementary distinctions?

A: That’s the question, isn’t it?

Update (2/13): Lawrence Ip, my friend from Berkeley who now works at Google, went to the D-Wave “launch” in person and kindly provided the following report.

I just came back from the D-Wave announcement. Unfortunately I had to leave at the start of the Q&A session.

Here’s what I took away from it (minus the marketing fluff):

– They claim to solve integer programming problems on their system. Geordie Rose was careful to explicitly say that they are only hoping to see a quadratic speedup. Herb Martin (the CEO) wasn’t quite as careful in his opening remarks but then he’s the “suit”. Geordie said that their current chip is not a universal QC (presumably because their space of Hamiltonians is limited) but with some work they expect to be able to make it universal.

– Geordie said compared their approach to the efforts in academia as similar to Celera and the Human Genome Project. He said they were trying to get something that would scale fast and worry about about the quality of the qubits later. He contrasted this to the academic community’s efforts to achieve fine control over qubits before scaling up. They say that they hope to reach 1024 qubits by the end of 2008.

– They demoed 3 “real-world” problems where they used their system as essentially a blackbox IP solver.
– Searching for protein matches. Given a protein try to find the closest match in a protein database. They serially fed all the items from the database to the chip and asked it to score the match against the given protein. They said it was solving a maximum independent set problem.
– Finding the best seating arrangement at a wedding reception. Given constraints on which people can’t be seated together and who wants to sit together, find the optimal arrangement.
– Solving a Sudoku puzzle.

– At one point Geordie quoted you. He excerpted a paragraph from your SIGACT article (the one where you talk about generating Shakespeare’s 38th play) and mentioned your proposal of the inability to solve NP-hard problems as a physical law. As far as I can remember, the only other computer scientist he quoted was Gordon Moore so you’re in good company. 🙂

Follow

In today’s quant-ph we find a report of a truly dramatic experiment — one that detected entanglement between Baton Rouge, Louisiana and Givarlais, France. How, you ask: by fiber-optic cable? Satellite? Neither: by postal mail! The authors don’t say if it was FedEx, UPS, or some other carrier that managed to ship half an EPR pair across the Atlantic without decohering it — but whoever it was, that’s who I’m using from now on.

(Note: On close reading, it appears that when the authors use the word “entanglement,” they actually mean “classical correlation.” However, this is a technical distinction that should only matter for experts.)

Follow

Here’s a heartwarming story of religious reconciliation in Israel, one that puts the lie to those cynics who thought such ecumenism impossible. It seems that large portions of Jerusalem’s Orthodox Jewish, Muslim, and Christian communities have finally set aside their differences, and joined together to support a common goal: threatening the marchers in a Gay Pride parade with death.

Follow

Let this man’s face serve as a reminder to all my American friends, to haul your respective asses to your respective polling places with no excuses accepted. Keep in mind that this year the Democratic voting day is Tuesday November 7^th, while the Republican voting day is Wednesday November 8^th.

(Me? I couldn’t find a precinct station in Waterloo for some strange reason, so I mailed an absentee ballot back to New Hope, PA.)

Follow

According to my usage statistics, of the people who come to scottaaronson.com via a search engine, about 5% do so by typing in one of the following queries:

biggest number in the world
the biggest number in the world
what is the largest number
largest number in the world
what is the biggest number

These people are then led to my big numbers essay, which presumably befuddles them even more.

So, let me satisfy the public’s curiosity once and for all: the biggest number in the world is a million billion gazillion. But stay tuned: even as I write, Space Shuttle astronauts are combing the galaxy for an even bigger number!

Follow

An anonymous indie-cinema-loving hermit friend from Amsterdam sends me an article in this week’s Economist entitled “Poison Ivy: Not so much palaces of learning as bastions of privilege and hypocrisy” (unfortunately, only available to subscribers). The article is a summary of an excellent Wall Street Journal series by Daniel Golden (again, unfortunately, only available to subscribers), which I’ve been following with great interest. Golden has also put out a book about this topic, called The Price of Admission (“How America’s Ruling Class Buys Its Way into Elite Colleges — and Who Gets Left Outside the Gates”), which I just ordered from Amazon. In the meantime, I’ll simply quote a few passages from the Economist piece:

Mr Golden shows that elite universities do everything in their power to admit the children of privilege. If they cannot get them in through the front door by relaxing their standards, then they smuggle them in through the back. No less than 60% of the places in elite universities are given to candidates who have some sort of extra “hook”, from rich or alumni parents to “sporting prowess”. The number of whites who benefit from this affirmative action is far greater than the number of blacks…

Most people think of black football and basketball stars when they hear about “sports scholarships”. But there are also sports scholarships for rich white students who play preppie sports such as fencing, squash, sailing, riding, golf and, of course, lacrosse. The University of Virginia even has scholarships for polo-players, relatively few of whom come from the inner cities…

What is one to make of [Senate Majority Leader Bill] Frist, who opposes affirmative action for minorities while practising it for his own son?

Two groups of people overwhelmingly bear the burden of these policies — Asian-Americans and poor whites. Asian-Americans are the “new Jews”, held to higher standards (they need to score at least 50 points higher than non-Asians even to be in the game) and frequently stigmatised for their “characters” (Harvard evaluators persistently rated Asian-Americans below whites on “personal qualities”). When the University of California, Berkeley briefly considered introducing means-based affirmative action, it rejected the idea on the ground that “using poverty yields a lot of poor white kids and poor Asian kids”.

The article ends with the hope that “America’s money-addicted and legacy-loving universities can be shamed into returning to what ought to have been their guiding principle all along: admitting people to university on the basis of their intellectual ability.”

I harped about this issue in one of my very first posts, almost a year ago. I don’t know what else to say. If idealism won’t goad us Americans (yes, I’m still an American) into overhauling our crooked, anti-intellectual admissions system, then maybe it will help to see just how absurd that system looks to the rest of the world.

Follow

My friend Alex Halderman is now after bigger fish than copy-“protected” music CD’s. Watch this video, in which he, Ed Felten, and Ariel Feldman demonstrate how to rig a Diebold voting machine (and also watch Alex show off his lock-picking skills). Reading the group’s paper, one becomes painfully aware of a yawning cultural divide between nerds and the rest of the world. Within the nerd universe, that voting machines need to have a verifiable paper trail, that they need to be open to inspection by researchers, etc., are points so obvious as to be scarcely worth stating. If a company (Diebold) refuses to take these most trivial of precautions, then even without a demonstration of the sort Alex et al. provide, the presumption must be that their machines are insecure. Now Alex et al. are trying to take what’s obvious to nerds into a universe — local election boards, the courts, etc. — that operates by entirely different rules. Within this other universe, the burden is not on Diebold to prove its voting machines are secure; it’s on Alex et al. to prove they’re insecure. And even if they do prove they’re insecure — well, if it weren’t for those pesky researchers telling the bad guys how to cheat, what would we have to worry about?

So, how does one bridge this divide? How does one explain the obvious to those who, were they capable of understanding it, would presumably have understood it already? I wish I had an easy answer, but I fear there’s nothing to do but what Alex, Ed, and Ariel are doing already — namely, fight with everything you’ve got.

Follow

The most important research question in astronomy, to judge from the news websites, is neither the nature of dark matter and energy, nor the origin of the Pioneer anomaly or gamma-ray bursts beyond the GZK cutoff, nor the possible existence of Earth-like extrasolar planets. No, the big question is whether Pluto is “really” a planet, and if so, whether Charon and Ceres are “really” planets, and whether something has to be round to be a planet, and if so, how round.

I was going to propose we bring in Wittgenstein to settle this. But I guess the astronomers have already “ruled.”

Richard Dawkins often rails against what he calls the “tyranny of the discontinuous mind.” As far as I know, he’s not complaining about those of us who like our Hilbert spaces finite-dimensional and our quantum gravity theories discrete. Rather, he’s complaining about those who insist on knowing, for every humanoid fossil, whether it’s “really” human or “really” an ape. Ironically, it’s often the same people who then complain about the “embarrassing lack of transitional forms”!

Can anyone suggest a word for a person obsessed with drawing firm but arbitrary lines through a real-valued parameter space? (“Lawyer” is already taken.) I’ve already figured out the word for a debate about such lines, like the one we saw in Prague: chasmgasm.

Follow

A commenter on a previous post writes:

A lot of great discoveries came from non-scientific losers. E=MCC. Airplanes. America. Someone discovered how to make an airplane by playing with a box. Physics is mostly theoretical. America, I guess, is the most scientific discovery. They applied the scientific method to determine its existence, but they used no control group, and no placebo. For that, America’s existence is not yet proven. There seem to be other ways of establishing truth than just the scientific method. Scientists are contemporary soothsayers. They should use every means possible of proving a fact.

Despite its insightfulness and coherence, the above argument raises some immediate questions:

1. What does it have to do with anything I said?
2. E=MCC?
3. What would mean to use a placebo or control group to test America’s existence? Would it mean sending a ship in a different direction, and checking that it didn’t also reach America? Would it mean verifying that America can’t be reached from Europe by foot — since if it could, then it wouldn’t be America, but rather part of Eurasia?
4. Has England’s existence been scientifically proven? What about France’s?
5. Where do so many people get the cockamamie idea that there’s such a thing as a “scientific method” — that science is not just really, really, really careful thinking? (I blame the school system.)

Follow

A commenter on my last post — who, since he or she chose not to provide a name, I’ll take the liberty of calling Dr. Doofus McRoofus — offers the following prediction about quantum computing:

[U]nless quantum computing can deliver something practical within the next five to ten years it will be as popular then as, say, PRAMs are today.

Four reactions:

1. String theory has been immensely popular for over 20 years, among a much larger community, with zero prospects for delivering anything practical (or even any contact with experiment, which — ahem — some of us have had for a decade). Reasoning by analogy, if quantum computing became popular around 1995, that should at least put us in the upper range of McRoofus’s “five to ten years.”
2. For better or worse, the funding outlook for quantum computing is much less depressing right now than for classical theoretical computer science. Many of us have been making the case to DARPA and NSF that classical complexity should continue to be funded in part because of its relevance for quantum computing.
3. The right analogy is not between quantum computing and PRAM’s; it’s between quantum computing and parallel computing. Specific architectures, like linear optics and PRAM’s, have gone in and out of fashion. Modes of computation, like nondeterminism, randomness, parallelism, and quantumness, have instead just gotten agglomerated onto the giant rolling snowball of complexity. As long as the snowball itself continues to tumble down the hill (shoot — bad metaphor?), I don’t see any reason for this to change.
4. I’m no good at predicting social trends, so perhaps time will prove me wrong and Dr. McRoofus right. But speaking for myself, I’d go insane if I had to pick research topics based on popularity. I became interested in quantum computing because of a simple trilemma: either (i) the Extended Church-Turing Thesis is false, (ii) quantum mechanics is false, or (iii) factoring is in classical polynomial time. As I put it in my dissertation, all three possibilities seem like wild, crackpot speculations, but at least one of them is true! The question of which will remain until it’s answered.

Follow