巡回セールスマン問題の物理学的解法

おとといの輪講内容。slashdotでの記事から。
http://science.slashdot.org/article.pl?sid=07/08/09/1535231
http://www.opticsexpress.org/abstract.cfm?id=140598
原理はすごく簡単。光の干渉を利用して距離の一致を見るという手段。光をファイバーで分けまくって全部の都市を回し、ハーフミラーで分けた光と干渉させ、干渉すればその距離のルートがある、というやり方。
ラベリングの方法は情報工学っぽいが、それ以外は古典物理の範疇。
これはコロンブスの卵かもしれない。

計算時間が一定な代わり、必要なエネルギーが指数関数的に増えてくのが問題で、増えすぎると核爆発級のエネルギーが必要になってしまうが、全探索で１６の都市を回る問題（16の階乗≒2.1 × 10^13）が、書いてあるとおり1ジュールで解けるなら、かなり素晴らしい