ソース
概要
- 巡回セールスマン問題におけるこれまでのベストアルゴリズムを上回るアルゴリズムが発見された。
www.quantamagazine.org
[2007.01409] A (Slightly) Improved Approximation Algorithm for Metric TSP
- 上回った値は、「0.2 billionth of a trillionth of a trillionth of a percent(0.0000000000000000000000000000000002％)」だけ。
- 従来のベストは、1976年に発見された「クリストフィード」のアルゴリズムである。
- わずかな進歩だが、長年突破できなかった壁が破られたことから、心理的な壁も突破できると期待されている。
所感
巡回セールスマン問題は量子コンピュータの話題でよく出てきます。
量子アニーリングでは、「焼きなまし法」というアルゴリズムが用いられますが、これはさまざまなアルゴリズムの一つに過ぎないということです。
今回言及されいているクリストフィードのアルゴリズムは、
「最良の経路よりも最大で50％しか長くならない近似解」を求めることが可能
とのことで、非常に精度の高いアルゴリズムであることがわかります。
実際、量子アニーリングを含む量子コンピュータは、古典コンピュータに勝ったことがありません。 巡回セールスマン問題の計算量は、単純計算をすると非常に膨大になると言われますが、実際はこのような優れたアルゴリズムがあるため、単純比較はできないということがわかります。
量子コンピュータによる量子超越、量子加速はまだまだ先になりそうです。