Shtetl-Optimized

What better way to procrastinate than to hear an Australian radio show interview me about the quantum query complexity of the collision problem, public-key cryptography, interactive proofs, computational intractability as a law of physics, and my great love for my high school? The first part of the program is about Australia’s population of cane toads (or rather, “tie-oads”). Then at 32:40, they start in with a report on the FQXi conference in Iceland, and interviews with Max Tegmark, Fred Adams, and Simon Saunders. I’m from 39:10 to 46:50.

A few comments/corrections:

• The interviewer, Pauline Newman, asks me about the practical implications of the collision lower bound, and then cuts to me talking about how quantum computers could break the RSA cryptosystem. Of course, the connection is only an indirect one (the collision lower bound is what gives hope that one could design collision-resistant hash functions that, unlike RSA, are secure even against quantum attacks).

• I said that, when trying to solve jigsaw puzzles or schedule airline flights, there doesn’t seem to be anything one can do that’s fundamentally better than trying every possibility. I should have added, “in the worst case.”

• The reason I mentioned how old I was when IP=PSPACE was proved is not that I’m a narcissist (though I am), but because in a section that was cut, Pauline asked me if I proved IP=PSPACE, and I was trying to make it clear that I didn’t. The theorem was proved by Shamir, building on work of Lund, Fortnow, Karloff, and Nisan.

• Pauline’s assertion that I “took off on a snowmobile without [my] passenger” and “left a distinguished physicist stranded on a glacier” is a gross exaggeration. What happened was, I waited and waited for someone — anyone — to climb onto my snowmobile. When no one did (maybe because everyone was scared by my abysmal driving ability), I figured I should just go.

Anyway, at least the um’s and uh’s seem to have been under control, compared to my interview with Lance two years ago.

Several readers have now written to me independently, asking for my reaction to the following paper:

An Optical Solution For The Traveling Salesman Problem
Tobias Haist and Wolfgang Osten

Abstract: We introduce an optical method based on white light interferometry in order to solve the well-known NP–complete traveling salesman problem. To our knowledge it is the first time that a method for the reduction of non–polynomial time to quadratic time has been proposed. We will show that this achievement is limited by the number of available photons for solving the problem. It will turn out that this number of photons is proportional to N^N for a traveling salesman problem with N cities and that for large numbers of cities the method in practice therefore is limited by the signal–to–noise ratio. The proposed method is meant purely as a gedankenexperiment.

Look, this is really not hard. You really don’t need a world CompuCrackpotism expert to tell you what to think of this. If you read carefully, the authors were actually kind enough to explain themselves, right in the abstract, why their proposal doesn’t scale. (This, of course, is entirely to their credit, and puts them above ~98% of their colleagues in the burgeoning intersection of computer science, physics, and non-correctness.)

Hint: If the number of photons scales exponentially with N, and the photons have high enough energies that you can detect them, then the energy also scales exponentially with N. So by the Schwarzschild bound, the volume also scales exponentially with N; therefore, by locality, so does the time.

A commenter on my previous post writes:

What all these scientists who are crying about the teaching of evolution should do is propose bets to creationists based on the outcomes of experiments … You think that these D-wave guys won’t be able to do something they’re claiming to be able to do? It might be a good exercise to make that statement precise … If someone has a conjecture of the form “There should exist a theory that explains X”, people roll their eyes, essentially because there’s no way of deciding the implicit bet.

Alright, imagine the following conversation:

Layperson: I just heard on the radio about this new Yood d’Shnood Theory of the Universe. What do you think the odds are that it’ll turn out to be true?

Scientist: Well, so far I haven’t seen any good evidence that…

Layperson: Sure, but what’s your prediction?

Scientist: As I said, the evidence seems to be explained a lot more easily by…

Layperson: But what if you had to bet?

Scientist: Well, there are two ways to think about this. What the Yood d’Shnood proponents argue is that…

Layperson: No, don’t give me a dissertation, just give me a number!

Here’s the thing: when my PhD diploma arrived in the mail, it didn’t imbue me with some sort of supernatural power to predict the outcomes of future quantum computing experiments, unmediated by the evidence and arguments of the temporal world. (This despite the fact that my diploma was signed by a time-travelling cyborg, in his official capacity as Governor of California and Regent of the UC system.)

Of course, the reason scientists worry about evidence is that ultimately, we want our theories to cohere with reality and our predictions to come out right. The experience of the last four centuries suggests this hope is far from futile. The trouble is that, once you’ve decided to adopt the evidence-centric strategy that’s worked so well in the past, you have to forget temporarily about betting odds. For the mindset of the scientist toying with rival explanations, and that of the Bayesian handicapping horses in a race, are (at least in my experience) simply too incompatible to inhabit the same brain at the same time.

If you’ll forgive the metaphor, asking for gambling odds on every scientific question is like asking a woman to sleep with you on the first date. Of course it’s in the back of your mind (and possibly not only yours), but it tends to be counterproductive even to bring it up. If you’re ever going to reach the summit, then you have to act like all that really matters to you is the climb, and the only reliable way to act like it is to remake yourself into the sort of person for whom it’s true. Such is the paradox of science and of life.

So, did D-Wave succeed in using the quantum adiabatic algorithm to solve Sudoku puzzles in fewer steps than those same puzzles would be solved with classical simulated annealing? I don’t know. To repeat, I don’t know. What I know is that I haven’t seen the evidence, and that the burden of providing such evidence rests with the people making the claim.

I know I promised no more posts about D-Wave and its “commercial” “quantum” computer for a while. But will you look at the bait that D-Wave founder Geordie Rose has been dangling in front of me on his blog?

People tend to approach problems and form opinions through the lens of their expertise. This happens all the time when disciplines are close … but it also happens in wierder [sic] situations, where the area of expertise is entirely disjoint from the situation being analyzed — like when theoretical computer scientists have opinions about real computers for example.

In Geordie’s comments section, the message is clearer still. One commenter writes that “the Professors didn’t get there first and they are angry; all truth must first come from them.” Another imagines “the Aaronsons of the world” fervently hoping that “their fragile self-created self-contained ecosystem can be re-built just the way they like it.”

For commenters like these, it would seem that the issue has nothing to do with decoherence rates or scalability, or with what the evidence is that D-Wave is actually harnessing quantum effects to obtain a computational speedup. So in this post, I want to step back and try to understand what the real issue is.

I propose that more than a few technology enthusiasts — not just the D-Wave supporters quoted above — are in the thrall of The Myth of the Ivory Tower. According to this Myth, the basic function of academic scientists is to sit around in their armchairs, pompously declaring to be impossible what plucky inventors like Thomas Edison or the Wright Brothers then roll up their sleeves and do. Now, I might be an academic myself, but I’m also a proud American (currently residing in the 51^st state), and I won’t deny that this most American of myths has a certain resonance even for me. In the end, though, I believe that the Myth tells us more about our Zeitgeist, or our collective psyche, or something like that, than it does about the actual history of technology.

The “evidence” for the Myth (when such is offered) usually consists of famous last words from distinguished scientific authorities. You know the sort of thing I’m talking about:

Heavier-than-air flying machines are impossible.
Radio has no future.
X-rays will prove to be a hoax.
-William Thomson (Lord Kelvin)

I think there is a world market for maybe five computers.
-Thomas Watson

There is no reason anyone would want a computer in their home.
-Ken Olsen

(Watson and Olsen were of course CEO’s, but for the purposes of the Myth they stand in here as “academics.”)

However, as soon as we think about these predictions and what they’re supposed to demonstrate, we notice some glaring problems. The first one is confirmation bias. No one compiles lists of pessimistic technological forecasts made by experts that turned out to be right — where would you even start?

The second problem is that many of the juiciest predictions come from a single individual: Lord Kelvin. Furthermore, they come from the twilight of his career, when he was considered to have lost his vortices even by most of his colleagues. Seeking to better understand this great physicist of the 19^th century who was so wrong about the technologies of the 20^th, I just read an excellent biography called Degrees Kelvin. One thing I learned is that, if the selective historians chose to focus on the first half of Kelvin’s career rather than the second, they could find equally exquisite anecdotes illustrating the reliability of academic opinions.

In the laying of the first transatlantic telegraph cable in the 1850′s, there were two colorful personalities: Kelvin and Wildman Whitehouse. Whitehouse, the “practical” man, detested any math or physics he couldn’t understand, and insisted that a transatlantic cable would just be a longer version of existing cables. Kelvin, the “theorist,” said that while a transatlantic cable was certainly possible, it would need thicker insulation, a different kind of receiver, etc. than previous cables to work reliably, and that more testing and research was needed. As it happened, after laying a cable that was every bit as unreliable as Kelvin said it would be, Whitehouse (1) had to use Kelvin’s receiver to get any signal through at all, (2) faked the transcripts to make it look like he used his own receiver, (3) fatally damaged the cable by sending 2,000 volts through it in a desperate attempt to get it to work properly, and then (4) insisted the cable was still fine after it had permanently gone silent. Eventually the cable companies learned their lesson.

Despite this and other successes (e.g., the Second Law of Thermodynamics), Kelvin’s doofus predictions in later life do illustrate two important points. The first is that, if you’re going to make skeptical pronouncements, you’d better distinguish clearly between the provably impossible, the presumably impossible, and the merely difficult and not yet achieved. The second is that, if you’re going to claim something’s impossible, you’d better have an argument, and you’d better understand what assumptions it rests on.

Alright, so let’s move on to Watson and Olsen’s predictions about the computer industry. The funny thing is, these predictions weren’t nearly as stupid as they sound! Why? Because there’s nothing inevitable about the concept of a personal computer. Instead of billions of home PC’s, we could just as easily imagine most of the world’s computing power concentrated in a few servers, accessible remotely to anyone who wanted it. In this alternate universe, your desktop PC would be little more than a glorified information portal — a “browser,” if you will — while most of the actual application software (email, calendars, maps, etc.) ran elsewhere. I admit that this is just a fanciful, hypothetical scenario, but what does that matter to a theorist like me?

Speaking of which, the Internet was of course the child of DARPA and NSF, raised to adolescence in university CS departments. (DARPA has since reoriented itself toward projects with shorter-term payoff, its previous funding model having failed so disastrously.) The Web was created by Tim Berners-Lee at CERN, and the first popular web browser by Marc Andreessen at the University of Illinois. (And yes, Al Gore had a nontrivial role in funding this work.) R, S, and A were all at MIT. If you’re going to argue for the irrelevance of academic research, the Internet is not the place to start.

But what about some of the other spectacular inventions of the last fifty years: the laser, the transistor, the fiber-optic cable, the communications satellite? Didn’t those come from the private sector? As it happens, they came from Bell Labs, which is interesting as the sort of mammoth exception that proves the rule. Because of AT&T’s government-sanctioned monopoly, for much of the 20^th century Bell Labs was able to function like the world’s largest university, devoting billions of dollars to “irrelevant” research. So in the 1980′s, when Congress decided to deregulate the phone system, many people predicted that Bell Labs would die a slow, agonizing death — a prediction that’s been borne out over the last 25 years.

But surely other companies must have picked up the slack? No, not really. While Microsoft, IBM, NEC, Xerox, and a few others all provide welcome support for basic research, none of them do so on the old Ma Bell’s scale. From a CEO’s perspective, the problem with basic research is obvious: a rising tide lifts all boats, your competitors’ as well as yours. (The famous cautionary example here is Xerox PARC, which made the “mistake” of giving the world the windowing system, the mouse, and the laser printer.)

For those who adhere to the religion of capitalism, have the Arrow-Debreu Theorem tattoed across their chests, etc., it might be difficult to understand how a system based on peer review rather than the free market could lead so consistently to technological breakthroughs. I mean, all those ivory-tower academics growing fat off government grants: what incentive could they possibly have to get the right answers? Without picky customers or venture capitalists breathing down their necks, what’s the penalty for being wrong?

I’m lucky enough to be friends with Robin Hanson, a brilliant economist and futurist who starts where Ayn Rand would’ve suffered a loss of nerve and keeps going from there. Robin has long argued that the scientific peer review process is broken, and ought to be supplanted by a futures market that would reward scientists for making correct predictions. As he writes:

The pace of scientific progress may be hindered by the tendency of our academic institutions to reward being popular, rather than being right … Academia is still largely a medieval guild, with a few powerful elites, many slave-like apprentices, and members who hold a monopoly on the research patronage of princes and the teaching of their sons …

Imagine that academics are expected to “put up or shut up” and accompany claims with at least token bets, and that statistics are collected on how well people do. Imagine that funding agencies subsidize pools on questions of interest to them, and that research labs pay for much of their research with winnings from previous pools. And imagine that anyone could play, either to take a stand on an important issue, or to insure against technological risk.

Personally, I hope that Robin’s science futures market gets tried on a significant scale, and I can’t wait to see the results. (Naturally, even the marketplace of ideas has to compete in the marketplace of ideas!) I agree with Robin that academic science is often tradition-bound to the point of absurdity, and that its institutions ought to be as open to scrutiny and replacement as its theories. But I don’t go as far as he apparently does in the direction of the Myth of the Ivory Tower. For me, the interesting thing about science is not that it’s broken, but rather that it’s about the least broken enterprise in the whole sorry history of our species.

On Thursday NEC put out a press release announcing the “world’s first controllably coupled qubits.” See here for the abstract of the accompanying Science paper by Niskanen et al. (unfortunately the full text requires a subscription). NEC’s announcement led to the usual fluffified popular articles; see here, here, and here for example. But to satisfy Geordie Rose’s curiosity, my hype-o-meter has not yet reached D-Wave levels, for three reasons.

1. These claims haven’t garnered nearly as much ‘quonfusion’ as D-Wave’s in the popular press.
2. In this case there is a peer-reviewed paper.
3. There’s no claim here about solving NP-complete problems, or indeed about asymptotic complexity at all. The sole claim to originality has to do with “tunable two-qubit couplings,” and I’m not at all well-placed to evaluate it.

Anyway, I thought I should at least mention this work, in the hope that commenters more knowledgeable than I am will weigh in on its significance. Eternal vigilance is the price of quantum computing research.

OK, on to the second breakfast link. Bill Gasarch has reviewed my blog for SIGACT News (scroll down to page 15), together with Lance Fortnow’s and Luca Trevisan’s. Favorite quotes:

Lance is Walter Cronkite. Scott is Stephen Colbert.

The name of the blog, ‘Shtetl-Optimized’ does not really say what it is about. With this in mind one can never say Scott has gone ‘off topic’ since its [sic] not clear what the topic should be.

Incidentally, an uncharitable person might suspect a slight conflict of interest in Bill reviewing Lance’s blog, seeing as Bill now writes Lance’s blog. But Bill assures us that he reviewed the blog before taking it over.

Theorem: Suppose NP-complete problems are efficiently solvable by quantum computers. Then either the polynomial hierarchy collapses, or else BQP ⊄ AM (that is, quantum computations can’t be efficiently simulated by Arthur-Merlin protocols).

Proof: Suppose NP ⊆ BQP and BQP ⊆ AM. Then coNP ⊆ BQP ⊆ AM, and hence the polynomial hierarchy collapses to the second level by a result of Boppana, Håstad, and Zachos.

Note: If only we could delete the weasel phrase “or else BQP ⊄ AM” from my Most Trivial Theorem, we would’ve achieved a long-sought breakthrough in quantum computing theory. In particular, we would’ve shown that any fast quantum algorithm to solve NP-complete problems would imply an unlikely collapse of classical complexity classes. But while the weasel phrase is weaselly enough to make the Most Trivial Theorem a triviality, I don’t think it’s infinitely weaselly. The reason is my growing suspicion that BQP ⊆ AM in the unrelativized world.

Second Note: When I call this my “Most Trivial Theorem,” obviously I’m excluding homework exercises.

Look, I promise this will be the last D-Wave post in a while. But there have been two developments that, as Planet Earth’s primary D-Wave skepticism clearinghouse, I feel a duty to report.

First, Jason Pontin’s article in the Sunday New York Times has appeared. It’s not perfect, but to get in a description of quantum computing that was even somewhat accurate required a long, word-by-word and phrase-by-phrase battle with the editors of the business section.

Second, Umesh Vazirani sent me a document summarizing the skeptical case against D-Wave, which anyone coming to this blog from the Tech Review or New York Times might find helpful. (Hey, as long as you’re here, stick around for a bit!) I’ve posted Umesh’s criticisms below.

Finally, Happy Easter from all of us here in the shtetl!

Reasons To Be Skeptical About D-Wave’s Claims

by Guest Blogger Umesh Vazirani

1. An Unconvincing Demo: D-wave’s demo consisted of a computer in a box that could solve simple problems. We have no way of knowing whether the computer in the box was an ordinary classical computer or a quantum computer. For the problem the computer solves — finding ground states for 16 bit Ising problems — a classical computer would work just as quickly. This demo is the only public evidence D-wave has presented in support of its claims.

2. A Physics Breakthrough?: Achieving 16 coherent superconducting quantum bits would be quite a breakthrough. Physicists working on superconducting qubits have not been able to achieve more than two coherent quantum bits in the lab. In the absence of evidence from D-Wave that their 16 qubits are coherent, scientists are understandably skeptical. If D-Wave’s qubits are not coherent, as many scientists suspect, their computer would be classical, not quantum. This would still be consistent with the results of the demo, since the decohering qubits would act like classical random bits, and the adiabatic computer would act like a classical computer implementing simulated annealing, which would be quite fast for a small 16 bit Ising problem. It is possible to test the quantum states of D-Wave’s computer for coherence, but Geordie Rose’s statements suggest that no such tests have been made.

3. Claims of Big Algorithmic Breakthrough Without Evidence: 16-bit quantum computers are useless from a practical standpoint because they can only solve very small problems that could just as easily be solved using a classical computer. Thus, D-Wave’s demo, even if it really was a quantum computer, will only be practically useful if the technology will scale to the larger problems that cannot be solved with a classical computer. Unless D-Wave has made a major algorithmic breakthrough as well as a major practical one, however, D-Wave’s computer, even if implemented with thousands of qubits, will not provide a speedup over classical computers. D-Wave does not implement a general purpose quantum computer, only one that can implement adiabatic optimization. They wish to use it to solve the Ising model, which is thought to be beyond the reach of classical computers, but there is no known efficient algorithm for solving the Ising model using this adiabatic approach. It is possible to achieve a quadratic speedup for unstructured search problems using adiabatic optimization, but that result requires an ability to tune the rate of the adiabatic process — something which appears to researchers to be extremely hard if not impossible for the Ising problem. Geordie Rose’s public statements suggest that he doesn’t understand this issue, which makes computer scientists skeptical that any breakthrough has been made.

To summarize: For D-Wave to achieve a practically useful quantum computer using their technology, they would have to have made a breakthrough in physics, as well as a breakthrough in the design of their algorithm. Scientists are skeptical both because D-Wave has failed to provide any supporting evidence, and also because their public statements suggest a lack of understanding of the issues involved.

You might ask why researchers are putting so much energy into debunking the D-Wave hype. One reason is that QC researchers feel a responsibility to the public to not overhype quantum computers. Quantum computing is an exciting field that has caught the imagination of the public. This is a good thing. But if the quantum computing effort starts to mingle fact with fiction, then the entire effort loses its credibility.

Another reason is that D-Wave’s unsupported claims are undermining the efforts of the researchers who are working very hard on these problems. It’s as if there was a new biotech company claiming to be at the brink of a revolutionary cure for cancer. If it is true, it is great, but if it’s not, then it undermines the efforts of the legitimate cancer researchers.

Last night Jason Pontin, the Editor-in-Chief of MIT’s Technology Review, published a hard-hitting article about D-Wave, the Vancouver startup that claims to have built “the world’s first commercial quantum computer.” A condensed (and, alas, considerably mangled and dumbed-down) version of his article will appear in Sunday’s New York Times.

Jason wrote to me a couple weeks ago and said that, while he knew that most journalists had gotten the D-Wave story wrong, he was determined to get it right, and wanted my help in understanding the computer-science issues. He didn’t have to ask me twice.

Since I come across as pretty harsh on D-Wave in the article, I think it’s worth recalling how we got to this point. When the D-Wave story broke, my first reaction was to give them some benefit of the doubt (as you can see from the mild tone of my “Orion Anti-Hype FAQ”). So what changed? Well, four things:

1. I asked Geordie Rose (the founder of D-Wave and sometime commenter on this blog) twice for actual information about the speedup D-Wave claimed to be seeing over classical algorithms, and he never provided any.
2. Instead of answering my and others’ technical questions, D-Wave decided to attack academic science itself. Here’s what Herb Martin, the CEO of D-Wave, told an interviewer from ITworld: “Businesses aren’t too fascinated about the details of quantum mechanics, but academics have their own axes to grind. I can assure you that our VCs look at us a lot closer than the government looks at the academics who win research grants.” The track record of companies that engage in this sort of behavior is not good.
3. I read article after article claiming that quantum computers can solve NP-complete problems in polynomial time. I reflected on the fact that a single one of these articles will probably reach more people than every quantum complexity paper ever written.
4. It became clear, both from published interviews and from talking to Jason, that D-Wave was doing essentially nothing to correct journalists’ misconceptions about what sorts of problems are believed to be efficiently solvable by quantum computers.

Update (4/6): Geordie Rose has responded to me. A few responses to his response:

• I apologize for getting the CEO’s name wrong. I’d originally written Herb Martin, but then noticed that the ITworld article referred to him as “Ed Martin” and therefore changed it. This seems like another case where D-Wave has to work harder to correct journalists’ misconceptions!

• In a discussion with Geordie on my blog, following my Orion Anti-Hype FAQ, I asked:
  

  You say you’re seeing a speedup in your experiments — but (1) how big of a speedup, and (2) do you mean compared to the best-known classical algorithms (like simulated annealing), or compared to brute-force search?

  Then, in another discussion with Geordie following my Speaking truth to parallelism post, I asked him again:

  I’m certainly glad that you’re not claiming an exponential speedup. But at least based on the evidence I know about, whether you’re seeing a quadratic speedup — or indeed any asymptotic speedup — is very much open to question. Hence the question I asked you earlier: have you compared the empirical scaling for your adiabatic algorithm to the empirical scaling for the best classical algorithms like simulated annealing? If so, what were the results?

• Geordie now says that “the only way scaling can be extracted is empirically, and we can’t build big enough systems (yet) to answer scaling questions.” Thanks; that’s actually extremely helpful to me. I must have gotten a wrong impression from some of D-Wave’s previous statements. For example, here’s from D-Wave’s recently-released “Introduction to Orion” document (which now seems to be available for “premium subscribers” only):
  

  Q: Are D-Wave processors quantum computers?
  A: Yes. We have determined that quantum effects are being harnessed to accelerate computation in our processors.

  And here’s from a comment on Dave Bacon’s blog (blog comments seem to be D-Wave’s preferred venue for announcing scientific results):

  While the jury is still not in, our studies of these systems seem to indicate that AQCs, in the presence of thermal and spin bath environments, can still provide O(sqrt(N)) scaling even though the central QC system is definitely NOT a “system that’s globally phase coherent over the entire calculation”.

• The core of Geordie’s response is the following paragraph:
  

  This is worth emphasizing, because I thought it was obvious, but it turns out alot of people don’t get this. Most of the poorly thought out comments related to what we’re trying to do have come from theoretical computer scientists, who assume that the things they hold dear are likewise treasured by everyone else. Because they worship efficiency, they have assumed that’s the objective of our projects, when I have repeatedly said it’s not.

  When I read this to Umesh Vazirani over the phone, he sardonically replied, “it will be interesting to find out what’s left of this field after you’ve removed the notion of efficiency…”

I am, I’m slightly embarrassed to admit, quoted pretty extensively in the cover story of this week’s New Scientist magazine (alas, only available to subscribers or those willing to shell out $4.95). The story, by Michael Brooks, is about an interesting recent paper by Lucien Hardy of Perimeter Institute, on the power of “quantum gravity computers.” Lucien’s paper considers the following question: by exploiting quantum fluctuations in the causal structure of spacetime, can one efficiently solve problems that are not efficiently solvable with a garden-variety quantum computer?

As I told Brooks, I really do think this is a hell of a question, one that’s intimately related to the challenge of understanding quantum gravity itself. The trouble is that, until an actual quantum theory of gravity chooses to make itself known to us, almost everything we can say about the question is pure speculation.

But of course, pure speculation is what New Scientist gobbles up with french fries and coleslaw. And so, knowing what kind of story they were going to run, I did my best to advocate giving reality at least a few column inches. Fortunately, the end result isn’t quite as bad as I’d feared.

(Full disclosure: recently New Scientist asked me to write an article for them on theoretical computer science breakthroughs of the last 30 years. Remembering some of the steamers NS has unloaded in the recent past, I faced a moral dilemma for approximately five minutes. I then wrote back to them and said I’d be delighted to do it.)

Anyway, here are a few relevant excerpts from the article. If New Scientist wants me to take these down, then of course I’ll have to comply — though I imagine that being linked to from the 25,000^th most popularest blog on the entire Internet could only boost their sales.

A NEW computer is always welcome, isn’t it? It’s always faster than your old one, and it always does more stuff. An upgrade, the latest model with all the bells and whistles is an exciting prospect.

And when it comes to the kind of machine physicists are hoping for, you really are looking at something special. No ordinary upgrade for them: this will be the ultimate computer, and radically different from anything we have ever seen. Not only might it be supremely powerful, defying the logic of cause and effect to give instantaneous answers, it might also tell us exactly how the universe works. It might even tell us how our minds produce the phenomenon we call consciousness. Clear a space on your desk, then, for the quantum gravity computer.

Of course, there’s a chance it may not fit on your desktop because we don’t yet know what the machine will look like. Neither do we know how to build it, or even whether it will do all that its proponents hope. Nevertheless, just thinking about how this processor works could improve our understanding of the universe. “The power of quantum gravity computers is one of the deepest problems in physics,” says Scott Aaronson, a mathematician based at the University of Waterloo in Ontario, Canada.

…

Put [quantum theory and general relativity] together to make a quantum theory of gravity and it is almost inevitable that we are going to have trouble with notions of cause and effect: the logic of tock following tick or output following input just won’t apply in the quantum-gravity universe.

…

Aaronson agrees with Hardy. “General relativity says that the causal structure can vary, and quantum mechanics says that anything that can vary can be in superposition,” he says. “So to me, an indefinite causal structure seems like the main new conceptual feature.”

…

The big question is how powerful [a quantum gravity computer] could be: will it be the ultimate processor?

It turns out this is a hard question to answer. Traditionally, a computer’s power is rated by the number of computations it can do in a given time. IBM’s Blue Gene computer currently tops the world rankings for classical computers: it can do 280 trillion calculations per second. In theory, a quantum computer can do even better. It will be able to crack the world’s toughest codes in the blink of an eye.

The quantum gravity computer, on the other hand, can’t compete under these rules because “quickly” doesn’t mean anything in a scheme where space and time can’t be separated. Or, as Aaronson puts it: “It would be nice if the quantum gravity theorists could at least tell us what they mean by ‘time’.”

Nevertheless, Hardy thinks there is good reason to suppose the quantum gravity computer would indeed be a more powerful machine than anything we have so far envisioned. The fact that it might glimpse its results without running a computation hints at this, he says — though he admits this is just speculation.

What’s more convincing, he says, is the difficulty of simulating a quantum gravity computer on a quantum computer. The fact that we have no algorithm for simulating quantum systems on classical computers highlights the gulf between a classical computer and a quantum computer. If a quantum computer cannot simulate a quantum gravity computer, then that implies there might be another huge leap in computing power waiting to be exploited.

…

It is a controversial conclusion, though. Seth Lloyd of the Massachusetts Institute of Technology thinks there is no reason to invoke a discontinuity that separates quantum gravity from more familiar processes … Aaronson’s money is on the Lloyd camp: quantum gravity computers can’t be more powerful than quantum computers, he says. In his view, it is a short step from ultra-powerful quantum gravity computers to total cosmic anarchy. If, as Hardy suggests, a quantum gravity computer might be able to see its result without having to run its algorithms, it is essentially no different to having a quantum computer strapped to a time machine. As we all know, time machines don’t make sense: they would enable us to do things like travel back in history to kill our grandparents and thereby cease to exist. “It’s hard to come up with any plausible way to make quantum computers more powerful that wouldn’t make them absurdly more powerful,” he says.

…

Whatever the truth, this is why investigating the characteristics of the quantum gravity computer is so valuable. It ties theories to the real world, Aaronson says, and stops the important issues, such as a link with observable facts or staying within the bounds of what’s physically possible, from being swept under the carpet. After all, a computer has to produce an observable, measurable output based on an input and a known set of rules. “The connection to observation is no longer a minor detail,” Aaronson says. “It’s the entire problem.”

Two obvious corrections:

1. I certainly don’t think that quantum gravity computers “can’t” be more powerful than ordinary quantum computers. What I think is that, at the moment, there’s no good evidence that they would be.
2. I am not a mathematician.

Update: Six months ago, New Scientist ran a credulous, uncomprehending story about a rocket propulsion system that flagrantly violates conservation of momentum (!). This led to interesting discussions here, here, and here about what can be done to improve the magazine’s standards. If you enjoyed the D-Wave fiasco, you’ll also like the spectacle of commenters rushing to defend the article against those elitist, ivory-tower academics with their oh-so-sacred conservation laws. In a world of Homer Simpsons, it’s not easy being a Lisa.

You’ve waited for weeks. You’ve pestered me for it. Now here it is.

For those who liked my Shor’s algorithm post but are ready for the next level: brace yourself for BQP ⊆ PP, Recursive Fourier Sampling, and so much more. And for dessert, a brief discussion of quantum computing and the many-worlds interpretation.

Suggestions and bugfixes welcome; I’ll continue revising over the next few days as time permits.