Tensor-Network Formulation of the Traveling Salesman Problem and Variants

本論文は、ボルツマン重み付け層とカウントフィルタを用いて逐次周辺規則により最適巡回経路を特定する、巡回セールスマン問題およびそのバリエーションに対するテンソルネットワーク定式化を導入するものであり、これは専門的な古典ソルバーに代わる優位な代替手段というよりも、小規模な産業応用に対するヒューリスティックとして機能するものである。

要約

以下は、この論文を平易な言葉と創造的な比喩を用いて解説したものです。

全体像：新しい種類の計算機で「巡回セールスマン」のパズルを解く

あなたが巡回セールスマンだと想像してください。地図には 10 個、20 個、あるいは 100 個もの都市が描かれています。あなたはすべての都市をちょうど 1 回ずつ訪れて自宅に戻らなければなりませんが、ガソリンと時間を節約するために、可能な限り最短の距離でそれを完了したいと考えています。これが有名な**巡回セールスマン問題（TSP）**です。

問題点は、都市の数を増やすと、考えられる経路の数が爆発的に増加することです。それは、宇宙の年齢よりも長い時間をかけてもすべての鍵をチェックしきれないほど急速に増え続ける鍵の山から、完璧な鍵を見つけようとするようなものです。これが、コンピューターがこの問題に苦労する理由です。

この論文は、テンソルネットワークを用いてこの問題に取り組む新しい方法を提示しています。テンソルネットワークをコンピュータープログラムではなく、巨大な多層フィルタリングシステムとして考えてみてください。

比喩：「金粉」のふるい

あなたが金粉が混ざった巨大な砂の袋を持っていると想像してください。

• 砂： 悪い、長く、非効率な経路を表します。
• 金： 完璧で最短の経路を表します。
• 目標： 一粒一粒を個別に調べることなく、砂から金を分離することです。

著者たちはこれを行うための機械（テンソルネットワーク）を構築しました：

1. 初期の混合（重ね合わせ）： まず、機械は「重ね合わせ」を作成します。それは魔法のように、すべての可能な経路の複製を同時に作り出すようなものです。まるで、それぞれが異なる経路を辿る自分自身の百万ものバージョンを持っているようなものです。
2. 重み付け（熱）： 次に、機械は「温度」（$\tau$ と呼ばれます）を適用します。これを熱ランプだと考えてください。
   • 長く非効率な経路（砂）は熱くなって光に変化し、消え去ります。
   • 短く効率的な経路（金）は涼しく、重く留まります。
   • 機械は数学（ボルツマン因子）を用いて、悪い経路が良い経路よりも速く消え去るようにします。
3. フィルタ（規則）： ここが最も重要な部分です。どのような経路でも良いわけではありません。同じ都市を 2 回訪れることはできません。著者たちは特別な数え上げフィルタを構築しました。
   • 各都市に警備員がいると想像してください。旅行者がすでに行った都市を訪れようとした場合、その警備員はその特定の経路に対して扉を閉ざします。
   • これらのフィルタは「疎」であり、すべての可能性を手動でチェックする必要なく、間違った経路を非常に効率的にブロックすることを意味します。
4. 結果（周辺分布）： 熱とフィルタを通過した後、機械はすべてを絞り込みます。「最初の都市を見ると、勝つ経路の一部である可能性が最も高いのはどれか？」と問いかけます。それを選び、確定させ、次に 2 番目の都市に対して同じプロセスを繰り返し、経路全体が構築されるまで続けます。

実際に行われたこと（実験）

著者たちは、この方法がすべての問題を瞬時に解決する魔法の弾丸であると主張したわけではありません。その限界について非常に正直でした。

• 小規模テスト： 彼らはこの方法を小規模な地図（5 都市から 12 都市）でテストしました。
• 較正： 「温度」設定（$\tau$）が重要であることを発見しました。低すぎると、悪い経路は十分に消え去りません。高すぎると、コンピューターは小さな数学的誤差に混乱します。彼らは地図のサイズごとにこの設定を慎重に調整する必要がありました。
• 結果：
  • 設定を完璧に調整したとき、彼らの方法はこれらの小規模な地図において、約 95% の確率で完璧な経路を見つけました。
  • 標準的なコンピューター手法（「貪欲法」や「シミュレーテッド・アニーリング」など）と比較した際、彼らの方法は完璧な経路を見つける点でしばしば優れていました。
  • しかし、非常に大規模な地図については、数学が依然として重くなりすぎ（指数関数的複雑性）、古い手法と同じであると認めました。これは「多項式時間」の奇跡ではなく、単に数学を行う別の、非常に構造化された方法に過ぎません。

実世界でのテスト：ジョブ再割り当て問題

理論の外でこれが機能するかどうかを確認するために、彼らはONCE（スペインの盲人支援団体）のための実際の産業問題にこれを適用しました。

• 問題： 彼らには仕事に割り当てられた労働者と空いている仕事がありました。労働者を新しい仕事に移動させることで、チーム全体の生産性が向上するかどうかを確認する必要がありました。
• ひねり： これは厳密には「巡回」問題ではありませんが、似ています。重複予約することなく、ユニークな人をユニークな仕事に割り当てなければなりません。
• 結果： 彼らはテンソルネットワーク法を、量子アニーラーとデジタルアニーラーという 2 つの強力なツールと比較しました。
  • 総生産性向上の点では、結果は同一でした。
  • 唯一の違いは、2 つの選択肢が数学的に等しい「同点決着」の状況において、機械がランダムに異なる方を選んだという点でした。
  • 結論： これは、彼らの方法が実世界で機能し、特定のタスクで専門ツールに勝てないとしても、産業用ソフトウェアに統合できることを証明しました。

結論

この論文は、経路探索や割り当てのパズルを解決するための新しい数学的ツールキットを提示しています。

• 良い点： 複雑な規則（「同じ都市を 2 回訪れない」など）を処理する非常に明確でモジュール化された方法を提供し、小規模な問題では完璧な解を見つけることができます。それは、制約条件のチェックに疲れ知らずの、非常に整理整頓された規則順守のアシスタントを持っているようなものです。
• 悪い点： 巨大な問題を魔法のように簡単にするわけではありません。問題が大きくなるにつれて、数学は依然として指数関数的に難しくなります。うまく機能させるには、慎重な調整（較正）が必要です。
• 教訓： これらの問題について考えるための強力な新しい方法であり、特定の小規模な産業タスクのための確実なツールですが、現時点では既存のすべての超高速ソルバーを代替するものではありません。

要約すると：彼らは悪い経路をフィルタリングし、最良の経路を見つけることができる高度なふるいを構築しましたが、金を得るためには、まだ適切な設定を入力する必要があります。

技術概要

技術的概要：巡回セールスマン問題およびその変種に対するテンソルネットワーク定式化

問題定義
本論文は、巡回セールスマン問題（TSP）およびそのいくつかの一般化、すなわち時間依存型 TSP（TDTSP）、ジョブ再割り当て問題（JRP）、非反復制約、順序付け規則、グループ制約、ボトルネック目的関数を含む変種を取り扱っている。TSP は、$N$個のノードを正確に 1 回ずつ訪問し、出発点に戻る最短経路を見つける問題として定義され、既知の NP 困難問題である。Held-Karp 法（$O(N^2 2^N)$）や分枝限定法のような厳密アルゴリズムが存在するが、それらは指数関数的な複雑さに直面しており、産業応用におけるスケーラビリティを制限している。一方、遺伝的アルゴリズムや局所探索などのヒューリスティックは、最適性の保証なしに近似解を提供する。著者らは、新興の量子アルゴリズム（QAOA、VQE）が現在、ハードウェアのノイズ（NISQ 時代）によって制限されていると指摘し、量子系の特性を模倣する古典的手法の探求を動機づけている。

手法
中核的な貢献は、候補となる巡回路をテンソル積空間内の状態として表現するテンソルネットワーク（TN）定式化である。この手法は、以下の 3 つの主要なメカニズムを通じて動作する。

1. テンソルネットワークの構築:

   • 初期化（'+'）: 各時間ステップにおけるすべての可能なノード割り当ての均一な重ね合わせを作成する。
   • 最適化（'S'）: 減衰因子 $\tau$ と巡回路コスト $C(\vec{y})$ を用いた虚時間進化演算子 $U = e^{-\tau C(\vec{y})}$ を適用する。これは高コスト構成を指数関数的に抑制し、量子系における基底状態の発見に類似している。
   • 制約フィルタリング（'F'）: 制約を強制するために行列積演算子（MPO）層を導入する。標準的な TSP において、これらの層は各ノードが正確に 1 回現れることを保証するカウントフィルタとして機能する。フィルタは、特定のノードが訪問されたかどうかを追跡するバイナリ結合インデックスを利用し、実質的に Levi-Civita 記号の制約 $|\epsilon_{y_0, \dots, y_{\hat{N}-1}}|^2$ を実装する。
   • 抽出（'+'）: トレース層が振幅を合計して周辺重みを生成する。

2. 逐次周辺抽出:
   解は反復的に抽出される。巡回路の固定された接頭辞に対して、アルゴリズムは次の位置における各候補ノード $a$ に対する周辺重み $Z_p(a; \tau)$ を計算する。$\tau \to \infty$ の極限かつ厳密な算術において、この重みを最大化するノードは、最適巡回路の一部であることが保証される（命題 3.2）。アルゴリズムは、最大化するノードを選択し、接頭辞を更新し、巡回路が完了するまでこれを繰り返す。

3. 一般化:
   この枠組みは、フィルタ層と進化層を変更することで、さまざまな TSP 変種に適応される。

   • DNSNN（ステップ数/ノード数の異なる場合）: フィルタは、ノードが $N^0$ 回から $N^f$ 回の間で現れることを許可する。
   • NMTSP（非マルコフ型）: $K$ 個の直前のステップに依存するコストを処理するために、高次 MPO を使用する。
   • BTSP（ボトルネック）: コスト進化を、遭遇した最大エッジコストを追跡する層に置き換える。
   • PTSP（グループ制約）: フィルタは、各クラスから正確に 1 つのノードを訪問することを強制する。
   • TSPP（順序付け）: 必要な先行ノードがまだ現れていない場合、ローカル射影演算子がノードを抑制する。
   • JRP（ジョブ再割り当て）: 「移動なし」状態が反復可能で、特定の欠員が一意である線形割り当て問題としてモデル化される。

4. 近似と複雑性:
   完全なテンソルネットワークの厳密な縮約は指数関数的であり、密な層別縮約の場合 $O(\hat{N}^4 2^{\hat{N}})$ としてスケーリングする。より大規模なインスタンスに対処するために、著者らは以下を提案する。

   • 層アブレーション: 複雑性を低減するために制約層のサブセットのみを適用し、結果をヒューリスティックとして扱う。
   • 疎局所縮約: 局所フィルタテンソルの決定論的かつ疎な性質を利用し、多項式係数を削減する（例：$O(\hat{N}^4 2^{\hat{N}})$ から $O(\hat{N}^3 2^{\hat{N}})$ へ）、ただし指数関数的スケーリングは変更しない。
   • 有限-$\tau$ ヒューリスティック: 数値的コントラストと縮退が解の品質に影響を与えることを認めつつ、ゼロ温度極限を近似するために有限精度と有限 $\tau$ を使用する。

主要な貢献

• 明示的な周辺式: 厳密算術におけるゼロ温度極限において、逐次周辺規則を通じて最適実行可能巡回路を特定するテンソルネットワーク周辺方程式の導出。
• 制約符号化: さまざまな組み合わせ問題に適用可能なカウント制約（非反復）のための MPO 層の定義。
• 一般化枠組み: 特定のテンソル層を変更することで、TSP 変種（TDTSP、JRP、BTSP など）に TN 形式法を適応させるモジュール型構築。
• ヒューリスティック実装: 数値的コントラストと縮退に関するその挙動の分析を伴う、較正されたヒューリスティックとして機能する有限精度・有限-$\tau$ 実装。

結果
実験研究は、専用ソルバーに対する計算上の優位性を主張するのではなく、手法の正しさと数値的挙動を検証するために、小規模な合成インスタンス（$N \in \{5, \dots, 12\}$）に焦点を当てている。

• 較正: 虚時間パラメータ $\tau$ はサイズ依存性を持つ。較正スイープ（$\tau \in \{1, \dots, 40\}$）は、評価セットにおける最適解率を $\tau=1$ 時の 55.56% から 95.56% まで大幅に向上させた。
• ソルバー比較: 小規模インスタンスにおいて、較正された TN ソルバーは 95.24% の最適性率を達成し、NetworkX の貪欲法（26.67%）やシミュレーテッド・アニーリング（59.05%）を上回ったが、厳密な Held-Karp 参照（100%）には及ばなかった。
• 層アブレーション: 制約層を除去すると解の品質が低下し、高精度には完全なフィルタセットが必要であることを確認した。
• 産業事例（JRP）: ONCE ジョブ再割り当て問題の概念実証において、TN 手法は Azure Digital Annealer と累積コストが同一の解を生成し、複数の最適割り当てが存在する縮退する場合のみで異なった。

意義と主張
著者らは、手法の計算能力に関して明確に謙虚さを示している。一般的な TSP に対して、Held-Karp 法、分枝限定切断法、または割り当て固有のアルゴリズムなどの専用古典ソルバーに対する一般的な計算上の優位性を主張するものではない。

• 形式的表現: 本作業は、「厳密算術における指数時間表現」と「制御された近似および拡張のためのプラットフォーム」として提示されている。
• ヒューリスティック性: 有限-$\tau$ 実装は、その挙動が数値的コントラストと縮退に依存する「較正された有限精度ヒューリスティック」として特徴付けられる。
• 有用性: 主要な価値は、多様な制約（順序付け、グループ、非マルコフ型コスト）の体系的な統合と、統一的な形式法内での近似手法（層の除去、疎縮約）の適用を可能にするモジュール型テンソルネットワーク枠組みにある。
• 限界: 最悪の場合、この手法は指数関数的スケーリングを保持する。数値的安定性の問題（アンダーフロー、縮退事例におけるコントラストの喪失）およびサイズ依存の較正の必要性が、重要な限界として特定されている。

要約すると、本論文は TSP およびその変種に対する厳密なテンソルネットワーク形式法を提供し、小規模インスタンスでの最適解の回復と産業制約の統合能力を実証しつつ、問題の根本的な指数関数的複雑さを克服しないことを認めている。