Quantum gravity computation: you, too, can be an expert in this field
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,000th 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:
- 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.
- 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.
Follow
Comment #1 March 30th, 2007 at 6:16 am
To jumpstart this excellent topic, I will contribute a quote by Wiener that is taken from this page of mathematical quotes. This quote is so fine as to be somewhat suspect of being a modern fabrication:
Nowadays, physicists pray too that their formalism will prove P=NP. 🙂
Comment #2 March 30th, 2007 at 6:58 am
I will also try to contribute to this excellent debate by asking a bunch of doofus questions:
I am keying off your quoted statement that “It’s hard to come up with any plausible way to make quantum computers more powerful that wouldn’t make them absurdly more powerful.”
As I understand the no cloning and no erasing theorems , they imply the nonexistence of a quantum erase gate or a quantum clone gate.
So if quantum gravity (QG) created an erase gate, that would be more powerful than a standard quantum computer (SQC).
Likewise a clone gate, and a “robust nonlinear or gate” (NLO) which you mentioned in a previous thread.
I can understand the contention that SQC plus an NLO is absurdly more powerful, given that it implies P=NP.
Do you also claim that an SQC plus an erase gate would also be absurdly more powerful?
If so why?
Does this also imply P=NP, or some other strong result?
Best,
Jim Graber
Comment #3 March 30th, 2007 at 7:04 am
Not a mathematician? Come on! Scott, I don’t want to ruin your chances of being hired by a CS department, but that’s what you are. A mathematician is someone who proves theorems (or tries to), and this is what you do for a living.
All right, this does not prevent you from being a computer scientist, too.
Comment #4 March 30th, 2007 at 7:08 am
“General relativity says that the causal structure can vary, and quantum mechanics says that anything that can vary can be in superposition…”
There is more assumption before one concludes there is something like superposition of causal structures- that the metric and its features are fundamental variables to be quantized. If one thinks that geometry is a collective excitation of something more fundamental, as is the case for all well-understood models of quantum gravity, then this would be the ultimate macroscopic superposition, making Schrodinger cats seem like an everyday occurrence.
Comment #5 March 30th, 2007 at 7:24 am
Violating the no-clone theorem seems to good to be true… I bet no future theory will allow that.
Comment #6 March 30th, 2007 at 7:56 am
Future, and current and past, theories certainly can violate the no-cloning theorem. It’s just these theories don’t seem to correspond to our world!
Comment #7 March 30th, 2007 at 8:21 am
James, a quantum computer with an erase gate could also solve NP-complete problems in polynomial time. Challenge for commenters: see if you can figure out why, while I go and eat lunch!
(Incidentally, I’m sure you know this, but saying that you can solve NP-complete problems efficiently in the physical world is very different from saying P=NP.)
Comment #8 March 30th, 2007 at 8:33 am
Scott: Incidentally, I’m sure you know this, but saying that you can solve NP-complete problems efficiently in the physical world is very different from saying P=NP.
That was my bad … forgot the html entity “≠” in P≠NP.
Comment #9 March 30th, 2007 at 8:53 am
>>”It’s just these theories don’t seem to correspond to our world!”
Oh, well, I was assuming implicitly “theories that work”, but thanks.
Comment #10 March 30th, 2007 at 10:54 am
“It’s hard to come up with any plausible way to make quantum computers more powerful that wouldn’t make them absurdly more powerful.”
I don’t find this very convincing. If you didn’t know quantum mechanics, it would have been hard to imagine a quantum computer, as well. The difference between a classical and a quantum computer is a lot more than just adding an erasure gate or adding a time-loop gate. It requires a whole different way of thinking about computation.
Comment #11 March 30th, 2007 at 11:09 am
If you didn’t know quantum mechanics, it would have been hard to imagine a quantum computer, as well.
I completely agree with you — that’s why I didn’t say “impossible,” I said “hard”!
Comment #12 March 30th, 2007 at 11:22 am
Not a mathematician? Come on!
Pascal, I think it’s the mathematicians who get to decide. 🙂
Comment #13 March 30th, 2007 at 11:34 am
Scott says: “It’s hard to come up with any plausible way to make quantum computers more powerful that wouldn’t make them absurdly more powerful.”
To extend Scott’s remark, we notice that:It’s hard to modify “Mike and Ike’s quantum postulates”—as carefully defined in Ch. 2 of Nielsen and Chuang—without violating causality.It’s similarly hard to modify them without making P=NP.It’s similarly hard to modify them without violating the no-cloning theory.It’s similarly hard to violate them without without destroying the transparency of the boundary between the classical and quantum worlds.All of the above have their mathematical origin in Choi’s Theorem, as indexed by Mike and Ike under “theorem: unitary freedom in the operator-sum representation.”
To stimulate discussion, I will suggest that Nature is giving us a big hint about how the universe works, by arranging quantum mechanics such that Choi’s Theorem is the only mathematical invariance of the quantum postulates of Chapter 2 of Mike and Ike.
Gauge invariance? Rotational invariance? Relativistic invariance? General relativistic invariance?
Bah. Those come later, and likely, are merely derivative.
Choi’s Theorem comes first. 🙂
Comment #14 March 30th, 2007 at 11:41 am
Bah … it’s similarly hard to post an html list on this blog! The above list was nicely formatted on the preview … oh well.
In any case, posts about the “unitary freedom in the operator-sum representation” would be very welcome. For engineering, it is the most useful and fundamental of all quantum invariances.
Comment #15 March 30th, 2007 at 12:18 pm
Scott, you must be right that it’s the mathematicians who get to decide. But it may be not be in the best interest of mathematics, or of science in general, to restrict mathematics to those research topics that already existed in the 19th century.
Fortunately, it seems that things are slooowly changing…
Comment #16 March 30th, 2007 at 1:43 pm
Scott:
1. Not only do you prove theorems, but you write up your proofs in LaTeX.
2. The central problem of your field (P vs. NP) is a Clay Millenium Prize Problem, and the person who solves it is guaranteed a Fields Medal provided they’re not too old.
3. You and your colleagues have a pecuniary incentive to deny that you are mathematicians (funding is better for “computer science” than for “mathematics”, is it not? cf. the “late” Lance Fortnow’s final “complexitycast”, where this is mentioned).
The fact is: you are a mathematician! It’s nothing to be ashamed of–really!
Comment #17 March 30th, 2007 at 1:52 pm
Thanks for the link, Scott. I have been discussing such things on my blog.
Comment #18 March 30th, 2007 at 2:25 pm
All about rule breaking:
Scott and others,
Thanks very much for answering my elementary questions.
I have a whole bunch more, but will try to suppress all but the ones I think are germane.
It still boggles my mind that erasing is as powerful as cloning,
but I had at least heard that one before.
I had not heard that they were enough ‘to compute NP efficiently”
(Am I saying that right now?)
I have no idea how to prove this.
On the other hand, I do think that I understand the difference between “P=NP” and “efficiently compute NP”.
In my mind, the difference is as follows;
P=?NP is a statement to be proved based on certain rules.
On the other hand, the whole idea of the new speculations is that quantum gravity or something else comes along and breaks those old rules, thus allowing NP computations under the new rules to be almost as fast as P computations.
It is, to me, mind boggling, how little those old rules must be broken to get what is apparently a very large gain..
Perhaps I should stop here.
But let me say one more thing:
I have heard for many years that GR and QM are “incompatible”.
(In fact both Brian Greene and Michael Turner used almost exactly these words at the Greene-Krause debate last night.)
This would seem to guarantee that gravity would “break” the QM rules,
at least a little bit,
unless of course, it were GR that got “broken”.
However as I understand the String Theory claim, it is to have managed, for the first time, to reproduce GR without breaking any of the QM rules.
If this is true, I would see this as strong support for Scott’s position.
But to me it seems clear that both Roger Penrose and Lucien Hardy
are supporting this older idea that GR or gravity “breaks” QM, at least enough to allow greater computational power.
Comment #19 March 30th, 2007 at 3:04 pm
James: You’ve bitten off quite a big chunk! Alright, let me take your questions in the order I remember them.
1. Yes, you’ve correctly understood the difference between P=NP and NP-complete problems being tractable in the physical world. One of them is strictly a math question (i.e., about the power of a certain model); the other is also a physics question (i.e., about which model is the right one).
2. Most people who’ve thought about quantum gravity assume that, between GR and QM, GR is the one that has to break down. One reason is that we know that GR breaks down at singularities anyway, whereas we don’t know of any situation where QM breaks down. Also, it seems hard to make even a tiny change to QM without leading to inconsistency, whereas there are many ways to change GR. Having said that, there are certainly prominent doubters (like Penrose and ‘t Hooft and Smolin) who think that QM will break down as well.
3. If QM broke down, that would certainly give us more room to imagine quantum gravity computing models that were qualitatively different from quantum computing. However, John Preskill has pointed out that, even if QM doesn’t break down, it’s still conceivable that QG could lead to a stronger model of computation — if (for example) the unitary operations that could be applied in unit time no longer had to act locally on qubits.
4. Why would an erasure gate let us solve NP-complete problems in polynomial time? The short answer is, because it would be non-unitary, and non-unitary gates let us “postselect” on measurement outcomes!
In more detail, suppose we have an erasure gate that maps |0〉 to |0〉 and |1〉 to |0〉. Then presumably that gate has to map |0〉-|1〉 to |0〉-|0〉 = … nothing! Therefore, we now have the ability simply to “kill off” any branch of the wavefunction that we don’t like. So in superposition, we can just guess every possible solution to an NP-complete problem, then kill off all the branches that lead to wrong answers!
Comment #20 March 30th, 2007 at 3:15 pm
The fact is: you are a mathematician! It’s nothing to be ashamed of–really!
Don’t do it Scott. We all know you’re a physicist anyways (and today’s physicists use LaTeX and prove theorems…err well they write down the word theorem and then errr…)
I actually have a test for whether you are a mathematician. Place yourself and a large potted plant in a huge room together. If you get tangled up in the plant, you are a mathematician. I draw this test from careful observation of the MSRI in Berkeley.
Comment #21 March 30th, 2007 at 3:31 pm
Moshe: Yes, geometry might be a “collective excitation” of something more fundamental. But then presumably we’d have to talk about superpositions of the more fundamental whatever-it-was — and is there any reason to think that wouldn’t lead to all the same conceptual difficulties as a superposition over geometries themselves?
Comment #22 March 30th, 2007 at 4:31 pm
Not sure precisely which problems you refer to, up to issues to do with Lorentz invariance we can think about a semiclassical geometry as being analogous to a solid, enormously complicated state when written in terms of the fundamental constituents. Superposing two semiclassical geometries is just like any other macroscopic superposition, no more or less mysterious or likely to appear in nature (actually much less likely given the numbers involved…).
\
Superpositions of the microscopic degrees of freedom, say the tensor products of single electron state, are already part of any self respecting many body state, nothing exotic in that.
Comment #23 March 30th, 2007 at 5:41 pm
The fact is: you are a mathematician! It’s nothing to be ashamed of–really!
Oh, all right — if you insist, I guess I’ll come out of the closet, and into the connected open set ℜ3\Closet.
Comment #24 March 30th, 2007 at 6:37 pm
Steve Jobs re-defined our field. As of his Jan 9, 2007 keynote, we are all
iTheorists
“i” for Information, natch. That can get you hired in CS, Math, Physics, and even—according to Richard Karp in John Sidles’ first comment to the TCS breakthroughs item you linked above—in biology.
(That was going to be part of the “Speaking Truth to Lubos” item I mused about privately.)
Comment #25 March 30th, 2007 at 8:23 pm
Apologies for not sticking to the non-deterministically more interesting topics of quantum-gravity-based computation, and whether Scott is a mathematician, for generally contributing a negative amount of intellectual information to this thread.
I wanted to point out that Shtetl-Optimized, being the 25,190th ranked blog in the Technorati universe, is quite an accomplishment, putting it squarely in the 99.14608549th percentile of all such blogs. Dave, yours is in the 98.85926648th percentile. Nice work guys!
And, Dave, if the plant-test is how you determine if someone is a mathematician, how do you determine if someone is a physicist?
Comment #26 March 31st, 2007 at 6:04 am
Aaron: how do you determine if someone is a physicist?
Gee, it’s another Letterman challenge — countdown begins:
(10) Hearing the word “engineering” causes a skin rash.
Next?
Comment #27 March 31st, 2007 at 6:05 am
(9) Writes “a”, says “b”, means “c”, but it should be “d” (Polya)
Comment #28 March 31st, 2007 at 6:21 am
(8) Frequently begins sentences with “As a physicist…” (as in “As a physicist, I care about the real world, not the logical consequences of the assumption I just made”)
Comment #29 March 31st, 2007 at 8:52 am
(7) When told he is _actually_ a mathematician he thinks: “LOL” and all the mathematician go: “OMFG”.
Comment #30 March 31st, 2007 at 1:16 pm
(6) They think that, since walking forwards gets them from their house to work, walking backwards in the opposite direction must have the same outcome. (Re: the replica method)
Comment #31 March 31st, 2007 at 1:48 pm
Scott, could you give us a review of the following book?
http://www.amazon.com/Geometry-Information-Retrieval-van-Rijsbergen/dp/0521838053
Comment #32 March 31st, 2007 at 4:23 pm
(5) Is interested in creating just one job.
Comment #33 March 31st, 2007 at 4:29 pm
Having been caught in a large, plastic, potted plant before, I died laughing at the plant-test for mathematicians.
But Dr. Aaronson: I don’t want QM to break down! We desperately need it for statistical mechanics 🙁 I guess we could make do with anything that wasn’t full-blown continuum mechanics, but for purely egotistical reasons I’d much rather have GR break than QM. It’s not often I need to worry about microstates with relativistic mean velocities or having relativistic masses.
Comment #34 March 31st, 2007 at 8:29 pm
Scott, could you give us a review of the following book?
No.
Comment #35 April 1st, 2007 at 2:27 am
Has anyone here looked at this paper?
http://arxiv.org/abs/quant-ph/0701033
They claim to be able to do graph isomorphism in polynomial time using quantum random walks
Comment #36 April 1st, 2007 at 2:37 am
anonymous: Yes, I did read that paper. In the abstract they state pretty unequivocally that they solve graph isomorphism in BQP. But by the conclusion, they’ve retreated, physicist-like, to “we conjecture that this is a necessary and sufficient condition…” and “for all graphs that we have tested…” As Monty Burns would say, release the hounds!
Comment #37 April 1st, 2007 at 4:01 am
Wait, you think the universe is R^3?!? You’re not a mathematician or a physicist — you’re a freshman.
Comment #38 April 1st, 2007 at 4:44 am
Nope, computer scientist. 🙂 For me, R3 is already an incredibly exotic space — I prefer to think of the universe as {0,1}*.
Comment #39 April 1st, 2007 at 5:10 am
(4) Considers chemists to be underqualified physicists, and biologists to be overqualified philatelists.
Comment #40 April 4th, 2007 at 9:10 am
Another problem with the graph isomorphism problem algorithm posted by anonymous above is that they distinguish different graphs by whether the amplitudes are different for walks on different graphs (see page 4 of the paper.) If we get to use such an amplitude oracle, graph isomorphism would be a very very small result in comparison to all the other problems which would admit efficient quantum algorithms.
Some day I want to write a pdf only paper that is valid and correct. In fact if anyone ever does discover some awesome new quantum algorithm, I think they should only submit the pdf only.