Intellectual whack-a-mole
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 OstenAbstract: 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 NN 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.
Follow
Comment #1 August 9th, 2007 at 12:06 pm
Your hint strikes me as strange, you really need quantum gravity here? are you saying that their argument is valid in a world where Newton’s constant is zero?
Comment #2 August 9th, 2007 at 12:25 pm
I liked the soap-bubble solution better.
Comment #3 August 9th, 2007 at 12:25 pm
I saw this the other day. They seem to get the complexity wrong: the algorithm using O(N^2) iterations of an experiment (eq. 3), but each experiment involves optical delays scaling as 2^N (eq. 1) – in what sense isn’t this exponential time? Their unit of computational time is not a constant, but scales exponentially in physical time. It’s strange.
Great, now I’m late to a quantum computing seminar. Thanks Scott.
Comment #4 August 9th, 2007 at 12:27 pm
Thomas: Always happy to help!
Comment #5 August 9th, 2007 at 12:37 pm
Moshe: Great question! Of course, quantum gravity is what gives upper bounds on the number of bits in a finite volume, which means it’s going to come up all the time in discussions of the limits of computation.
But was I really using QG? I thought the Schwarzschild bound was just classical GR.
In any case, maybe you can give a more “elementary” argument for the impossibility of cramming 2N detectable photons into a box of size N (in the limit N→infinity), one that doesn’t rely on the Schwarzschild bound? I thought about it briefly and couldn’t, but that doesn’t mean anything.
Comment #6 August 9th, 2007 at 12:58 pm
Energy collapsing to form a black hole is classical gravity, the fact that the resulting black hole has finite entropy is quantum gravity, the BH entropy goes to infinity in the classical limit.
But, my point is that if mathematical truth cannot be disproven by physical experiment, that should be true in any physical universe, not just our own. Their experiment can be performed in a world with no gravity, so there should be a resolution in such a world. I have no doubt one exists, but I have to go to a seminar now…
Comment #7 August 9th, 2007 at 1:15 pm
Energy collapsing to form a black hole is classical gravity, the fact that the resulting black hole has finite entropy is quantum gravity
Right, that’s what I thought. The argument I gave uses only classical gravity.
Their experiment can be performed in a world with no gravity, so there should be a resolution in such a world.
Certainly. In a world where arbitrarily many photons could be crammed into a region of bounded size, it would not at all surprise me if NP-complete problems were solvable in polynomial time.
On the other hand, it could be that the experiment doesn’t scale for some completely separate, non-gravitational reason. Physicists: any suggestions?
Comment #8 August 9th, 2007 at 1:51 pm
You used an asymptotic argument. But it is good to look at fixed-n behavior, especially if you want to explain the problem to laymen. The paper states that n=20 might be feasible, and Fig 4. tells that they understand perfectly that it does not scale. From an insightful slashdot comment:
“To solve a 50-point traveling salesman using their algorithm would require on the order of 50^50 photons (about 10^85). For comparison, the Sun emits roughly 10^45 photons per second.”
I’d love to see Sun-sized SAT-solvers.
Comment #9 August 9th, 2007 at 1:51 pm
Hi Scott,
I’m not sure why it would be surprising that you can solve an NP-complete problem given a sufficiently large number of photons and linear optics.
Since photons don’t interact, it’s equivalent to having a series of computers equal to the photon number, each performing the same calculation. You can use beam splitters to effectively give you random seeds if you want to do classical computing. For a large enough number of photons you could be extremely confident that all possibilities were being performed in parallel.
If you have enough computers you can explore all the paths in the travelling salesman problem in parallel, so why would it be surprising that you can do it with photons? A single photon which can be in any of 2^N modes, together with linear optics is equivalent to a quantum computer after all. Sure, they’d be indistinguishable computers, but I can’t see that causing too much trouble.
For what it’s worth, I think there might be a loophole in your argument (although one rather impractical to exploit). If you are aloud to choose an arbitrary spacetime geometry, couldn’t you add Einstein-Rosen bridges to make every where within some fixed distance of a central point? the fact that blackholes evaporate might also constitute a loophole.
Comment #10 August 9th, 2007 at 3:28 pm
Not to mention that non-polynomial time provably doesn’t reduce to quadratic time…
Comment #11 August 9th, 2007 at 3:37 pm
Joe:
I’m not sure why it would be surprising that you can solve an NP-complete problem given a sufficiently large number of photons…
It’s not.
If you are aloud to choose an arbitrary spacetime geometry, couldn’t you add Einstein-Rosen bridges to make every where within some fixed distance of a central point?
Wouldn’t Einstein-Rosen bridges give us closed timelike curves? Those also let us solve NP-complete problems in polynomial time, but for different reasons… 🙂
the fact that blackholes evaporate might also constitute a loophole.
No, it doesn’t. I only used the Schwarzschild bound, which is not affected by the fact that black holes evaporate.
To put it differently: if you squeeze photons into too small a space they’ll collapse to a black hole. And while the information encoded by the photons will eventually radiate out, if you try to collect that information into too small a space again, you’ll just get another black hole!
Comment #12 August 9th, 2007 at 3:41 pm
Not to mention that non-polynomial time provably doesn’t reduce to quadratic time…
Or that TSP isn’t proven to be non-polynomial time … but this is less like whack-a-mole than like popping bubble-wrap.
Comment #13 August 9th, 2007 at 5:33 pm
Scott,
I’m still not convinced about the Schwarzchild argument. Sure, you can’t recollect all the information from the black hole in one spot, but you don’t need all the information. You only need a one bit answer, or a bit more if you need to know the shortest route. Mightn’t it be possible to simply localise the information containing your answer, and let the rest radiate away?
Comment #14 August 9th, 2007 at 6:12 pm
The trouble is that not only do the photons collapse to a black hole, but a black hole formed from exponentially many photons will have an exponentially large Schwarzschild radius (since the radius is proportional to the energy). So even forming the black hole takes exponential time.
Comment #15 August 9th, 2007 at 7:04 pm
GR is not an intuitive theory: when collapsing matter the horizon forms long before that matter is concentrated in the Schwarzchild radius. Keep in mind that the horizon is not a physical object, just an imaginary line we draw, where inside objects will never escape to infinity. That’s the reason why I usually find the punchline “then a black hole forms” a little anti-climactic, not very convincing or at least needing a little elaboration.
Comment #16 August 9th, 2007 at 8:21 pm
Let’s see if I understand the hinted at argument.
Photons, being bosons, can be clumped together into relatively small volumes (compared to fermions at least), but there is still a useful limit. Photons have energy, and trying to cram too many into too small of a space can cause a black hole to form, which is, needless to say, not a desirable trait for an optical computer. Since photons need a certain amount of energy to be usefully detected, this means that the energy of a ball of photons is linear (or worse) in the number of photons.
A useful measure of how much small an area we can cram photons into is the Schwartzchild radius of a (nonrotating, uncharged) black hole. The exact details don’t really matter, but it suffices to know that the radius scales as the mass/energy of the photon ball — twice as many photons, twice (at least) as much energy, twice the size of the radius. And since we don’t want the optical computer to collapse into a black hole, it means, asymptotically, our computer must have a linear measure at least proportional to the number of photons.
The next bit is that the minimum time for an optical computer (or any physical system, optical or otherwise, computational or otherwise) is proportional (at least) to the linear distance between interacting components. The components can only interact at the speed of light — especially if the components are photons. So if two components are a light-second apart, it’ll take at least a second for one component to affect the other.
So the time necessary for a ball of photons to interact enough to do a computation is proportional to the linear scale of the ball of photons, which greater than the schwartzchild radius of the ball of photons, which is proportional to the energy of the photons, which is at least proportional to the number of photons. In otherwords, T = Omega(p), where p is the number of photons.
The paper says that p = O(NN), which means that T = Omega(NN), which I’d call exponential time if I treat “exponential time” as “anything greater than polynomial time”. It seems greater than exponential time to me. With an incredibly small constant, of course.
Comment #17 August 9th, 2007 at 9:54 pm
Scott,
Does that necessarily hold for non-spherically symmetric distributions? I wasn’t sure that was the case.
The Margolus-Levitin theorem certainly seems to imply that they can’t avoid using an exponential amount of energy. Perhaps you can avoid use of the Schwarzchild limit be making a thermodynamic arguement about the rate at which energy could be transfered to the device. As the any device must be built from pre-existing materials, you could assume that there is some maximum initial value for the energy density. In order to increase the energy density it would be necessary to transfer energy from the environment. However energy cannot be transfered at greater than the speed of light. As the energy increases exponentially, you need to draw in energy from an exponentially large volume. For any finite dimensional space, the volume of a hypershere will increase polynomially with radius. Hence the time taken to draw enough power into the device to perform the calculation must also be exponential. Or something similar…
Comment #18 August 9th, 2007 at 10:12 pm
So I’m puzzled – are we saying that you can solve an NP-complete problem in polynomial time just so long as the power of your computer scales exponentially with N? That wouldn’t surprise me either 🙂
Comment #19 August 10th, 2007 at 2:14 am
So I’m puzzled – are we saying that you can solve an NP-complete problem in polynomial time just so long as the power of your computer scales exponentially with N?
I don’t know if I misunderstood Scott. He mentioned that the time also scales exponentially with N in his last sentence. I think he was saying that the time needed to solve the TS problem scales with N. If that is true, the method may not be superior to other algorithms.
Comment #20 August 10th, 2007 at 2:32 am
The point I was trying to get across is that, if the energy scales exponentially with N, then well-established laws of physics imply that the time scales exponentially with N as well. So in our universe, it doesn’t even make sense to talk about “polynomial time but exponential energy” — though in some other universe with different laws of physics it might.
Comment #21 August 10th, 2007 at 4:37 am
I think I’ve misunderstood something important – but do we even need GR here? Their scheme uses exponentially long O(2^N) fiber delays, so shouldn’t just using the finite speed of light be enough to show that it requires exponential time? I don’t see any way around the difficulty – the proposal definitely needs either exponentially long optical paths, or exponentially short wavelengths (together with exponentially precise optical alignments). This wouldn’t work even in a GR-free universe.
Comment #22 August 10th, 2007 at 4:39 am
Off topic, why is this blog giving timestamps in Alaska time?
Comment #23 August 10th, 2007 at 8:56 am
I don’t know — I set it correctly a while ago, so it might be a WordPress bug. In any case, it’s fixed now. Thanks. 🙂
Comment #24 August 10th, 2007 at 8:57 am
Their scheme uses exponentially long O(2^N) fiber delays, so shouldn’t just using the finite speed of light be enough to show that it requires exponential time?
Ah — if that’s the case, then yes.
Comment #25 August 10th, 2007 at 9:26 am
Keep in mind that the horizon is not a physical object, just an imaginary line we draw, where inside objects will never escape to infinity.
Moshe: We had this discussion a while ago (see also here), and as I explained there, I don’t really buy this picture of the horizon as “just an imaginary line we draw.” I’ll give three arguments, trusting that you’ll correct me where I’m wrong.
(1) At least to a faraway observer, the horizon appears as a manifestly physical object: one that slows down incoming objects, heats them to the Planck scale, conducts electricity, etc.
(2) The horizon can be defined purely locally, in terms of the trapping of light rays.
(3) If we pass to quantum gravity, it seems likely that the horizon “stores” a vast amount of entropy, O(1) bits per Planck area, in a way we don’t yet understand.
Now, I admit that the location of the horizon is observer-dependent — but then again, in GR one can’t give absolute, observer-independent coordinates for anything!
Comment #26 August 10th, 2007 at 10:20 am
Scott,
The existence of the event horizon is also observer dependent via the Kruskal extension. Horizons can generally be removed through some coordinate transformation, unlike curvature singularities.
Comment #27 August 10th, 2007 at 11:16 am
If one just wants to find the length of the tour then the claim appears to have little to do with optics and to be an attempted reduction from TSP to a shortest path problem. It seems that about all that optics are used for can be done using conevntional algorithms by replacing linear search with binary search!
The construction seems essentially the following: Split each vertex into two copies with a high weight edge between them where the weight of this edge for vertex i is 2^i times a big number (e.g. > the total original weight ) plus a low order term that is much (even exponentially) smaller than
the granularity of the original weights. Now look for the shortest path from vertex v to itself that is > the sum of the new vertex weights but has a low order contribution that is the number of vertices (so that the path must go through N oriignal vertices). Then use optics to do a linear search through the possible exponential number of weights to find the smallest.
It seems that assuming that the construction is correct would yield a polynomial-time classical algorithm by doing binary search on these weights and repeatedly solving the path problem: Is there a cycle (not necessarily simple) on v with N high weight edges and total weight at most B?
Comment #28 August 10th, 2007 at 11:39 am
Thanks Scott, not sure that discussion is related, I recall I was just trying to understand to what degree (if any) LQG is holographic, I now understand I am not alone in that…
To your point regarding the horizon, I have some sympathy to this viewpoint, but it mutilates general covariance…but my point was more modest- just forming a black hole does not necessarily mean all hell breaks loose, we may well be crossing the horizon of a large black hole right now. So when that punchline is used I am often left with the “then what” feeling.
(more immediate point also- formation of black hole is not Lorentz invariant, so the time for formation does not necessarily scale like the size; I am now curious exactly how it scales, my feeling is probably much slower)
Comment #29 August 10th, 2007 at 11:44 am
Hi Scott
See http://www.walrusmagazine.com/articles/2007.08.10-quantum-conundrum/
For a discussion in The Walrus about quantum computing (related to an article about quantum computers in the Sept 2007 edition of The Walrus), and the nature of science research. The discussion just went live 10 minutes ago, and mentions your work.
Cheers
~Pat, digital editor
Comment #30 August 10th, 2007 at 11:56 am
The Walrus article says, “The old saw (disputed by University of Waterloo computer scientist Scott Aaronson, formerly of M.I.T.) is that…”
Scott, are you sure you weren’t in the “arrow-of-time” lagoon group in Reykjavik? 🙂
Comment #31 August 10th, 2007 at 12:00 pm
> Horizons can generally be removed through some coordinate transformation
this is wrong. the coordinate singularity on a horizon can be removed by choosing different coordinates, but in general not the horizon itself, e.g. event horizons are global features of a given space-time.
Comment #32 August 10th, 2007 at 12:27 pm
Pat: The essay you linked to falls into the same trap as almost all previous press coverage of D-Wave. That is, it takes D-Wave’s claims to have built a “commercial quantum computer” essentially at face value, and then frames the issue as whether or not their achievement should “count” if they don’t follow “ivory tower rules.”
In reality, whether or not D-Wave achieved anything at all is very much in question — and conventions like peer review are not ends in themselves; the point of them is to let people decide what’s been achieved. In this case, it’s not just that D-Wave went directly to the press without a paper. It’s that since then, they’ve refused to answer extremely basic technical questions when asked — like how noisy their qubits are, how they encoded a Sudoku puzzle into 16 qubits, how much of the computational work is done in the classical control, what classical algorithm they’re comparing against when they claim a speedup, etc.
As Ken Regan pointed out, a much more minor error is that I’m of MIT and formerly of Waterloo, not the reverse. 🙂
Comment #33 August 10th, 2007 at 1:58 pm
Bad assumption: nonrotating black hole.
Correct general case: Reissner-Nordstrom black hole.
http://www.pnas.org/cgi/content/abstract/83/7/1978
arxiv.org/abs/gr-qc/0605104
So I say: charge up that black hole, spin it up, then build the Optical Solution For The Traveling Salesman Problem.
That’s what all the advanced civilizations do…
Comment #34 August 10th, 2007 at 2:55 pm
Okay, so never mind that this does not challenge any of our fundamental ideas about computational complexity.
Is it useful?
I mean, optical computing seems pretty useful, even if it does scale the same way as any other kind of computer. Does having an example of an optical way to solve TSP further that any?
Comment #35 August 10th, 2007 at 3:22 pm
Without my having time to examine the paper enough to answer Coin’s question, here’s an analogy that may help give perspective. Haist-Osten’s conclusions section begins misleadingly:
“We have shown that the complexity of TSP can be dramatically reduced from N! to N^2 by optical means.”
Now the Cai-Furst paper “PSPACE survives 3-bit bottlenecks” (online followup paper here) could have concluded analogously:
“We have shown that the space complexity of TSP can be dramatically reduced from N to 3 by Bud-Light means.”
Of course the steps between the bottlenecks need space (more than) N, just as the reduction here needs exp-many photons, so the sentence would be equally misleading and in need of whacking.
But, this does not preclude the possibility that the Haist-Osten paper may say something interesting about the “shape” of computations, as Cai-Furst (building on Barrington’s NC^1 = width-5 BP work) certainly does. No time to look now, though. [The only other thing I’ve had time to check is that they do cite Johnson-McGeoch 2003—I’m adding that and some other refs on exact solvers for small instances of NP-complete problems to revised book chapters right now.]
Comment #36 August 10th, 2007 at 8:40 pm
Indeed. I seem to be having trouble expressing myself lately. It is the coordinate singularity to which I was refering, rather than the horizon itself. The point was that for some observers the horizon does not actually stop information reaching them, albeit rather poorly expressed.
Comment #37 August 11th, 2007 at 11:41 am
Coin asks: “so never mind that this does not challenge any of our fundamental ideas about computational complexity.
Is it useful?”
Since the main use of optics in the paper is to replace binary search over an exponential-sized ordered domain (which is already efficient with ordinary computation!) by a physically implausible parallel (actually linear) search over all exponentially many points of this ordered domain, the short answer is NO.
Comment #38 August 12th, 2007 at 7:51 am
This idea is not so new. It has been arround since 2006.
See here:
http://www.cs.ubbcluj.ro/~moltean/optical
Comment #39 August 12th, 2007 at 9:02 am
Indeed, variations have been around since the 70’s. It’s the perpetuum mobile of the digital age.