⚛️ 量子物理学

Solving the traveling salesman problem on $\lceil \log_2 (N-1)! \rceil$ qubits with a variational quantum Kolmogorov--Arnold network: exact-gradient CVaR training and generalization over time-dependent graphs

本論文は、厳密な勾配CVaRおよびベイシン・ホッピングによる再起動を用いた変分量子コルモゴロフ・アーノルド・ネットワークが、わずか $\lceil \log_2 (N-1)! \rceil$ 量子ビットのみで、時変グラフ上の巡回セールスマン問題を解くことができることを実証しており、従来のワンホット・エンコーディングと比較して量子ビット要件を大幅に削減しつつ、最大10地点までの最適解を達成している。

原著者： Hikaru Wakaura

公開日 2026-10-15

📖 1 分で読めます🧠 じっくり読む

CC BY 4.0

原著者： Hikaru Wakaura

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

配送ドライバーが、リストにある都市を正確に一度ずつ訪問し、自宅に戻らなければならない場面を想像してください。目的は、移動距離を最短にすることです。これは「巡回セールスマン問題」と呼ばれるもので、物流、スケジューリング、回路設計の核心に位置する古典的なパズルです。数都市の完璧なルートを見つけるのは容易ですが、都市のリストが増えるにつれて難易度は爆発的に高まります。新しい都市が一つ追加されるたびに、可能なルートの数は急速に倍増していくため、最速のスーパーコンピュータであっても最適なルートを見つけようとして行き詰まってしまうことがあります。数十年にわたり、科学者たちはこれらのパズルをより速く解くために、亜原子粒子の奇妙な規則を利用して情報を処理する量子コンピュータに期待を寄せてきました。しかし、大きな障害が残っていました。それは、計算をエラーや不必要な複雑さに溺れさせることなく、いかにして量子コンピュータが理解できる言語に問題を翻訳するかという点です。

QuantScape Inc.の研究者が、最大10都市のマップにおける最短ルートを見事に特定するという、量子コンピュータを迷路へと導く新しい手法を実証しました。この研究は、物理的なマシンではなく量子ハードウェアのシミュレーションに基づいたもので、従来のアプローチよりもはるかに少ない量子ビット（量子コンピュータにおける情報の基本単位）を使用する手法を導入しています。さらに重要なことに、この手法は、一日のうちで変化する交通量のような変化する道路状況に対して、新しいシナリオごとに再学習する必要なく、単一の指示セットで適応できることを示しています。この結果は、適切なエンコーディングとトレーニング技術を用いれば、ハードウェアの継続的な向上を前提として、量子コンピュータが現在手の届かない最適化問題に取り組める可能性があることを示唆しています。

課題の核心は、問題をどのようにマシン用に書き記すかという点にあります。従来の手法では、都市のあらゆる組み合わせとルート内の位置に対して、個別の量子ビットを割り当てます。10都市のマップの場合、このアプローチには81ビットが必要となり、コンピュータは無効なルートを常にチェックして破棄することを強制されるため、ペナルティによる時間とエネルギーを浪費します。今回の研究では、「レーマー・コード（Lehmer code）」と呼ばれる数学的システムに着想を得た異なる戦略を採用しており、これは本質的に、すべての可能なルートをリスト内の順序によってランク付けするものです。この手法では、10都市に対してわずか19ビットしか必要とせず、大幅な削減を実現しました。このコンパクトなコードを使用することで、量子コンピュータのすべての状態が有効なルートを表すようになり、ペナルティチェックの必要性が排除されました。探索を効率的にするために、研究者たちは、コード内の1つのビットを反転させることがルートの小さな論理的な変化に対応するようにこれらの状態を配置し、コンピュータが解空間をスムーズに探索できるようにしました。

量子コンピュータを導くために、研究者たちは「変分量子コルモゴロフ・アーノルド・ネットワーク（variational quantum Kolmogorov–Arnold network）」と呼ばれるハイブリッドシステムを採用しました。これは、マップと時刻を監視し、量子回路の設定ダイヤルを正しい位置に設定するスマートなコントローラーのようなものです。特定のマップごとに設定をハードコーディングする代わりに、このコントローラーは、都市間の距離と現在の時刻に基づいて回路を調整するという一般的なルールを学習します。これにより、電力網やラッシュアワーの交通量がある道路ネットワークのように、移動時間が変化する「時間依存グラフ」を扱うことが可能になります。コントローラーは、長いルートを選択するリスクを最小限に抑えるという特定の目標を用いて訓練されました。単に平均的な長さを探すのではなく、可能性の高い上位数パーセントの結果の中にあるワーストケースのシナリオに焦点を当てることで、最終的な結果が堅牢で信頼できるものになるようにしました。

訓練プロセス自体も厳格であり、コンピュータが最良の答えではなく「十分良い」答えで妥協してしまう「局所解（ローカルミニマム）」に陥るという一般的な罠を回避するように設計されました。研究者たちは、広範な探索から始めて徐々に焦点を絞っていく多段階戦略を用い、さらに設定を意図的に揺さぶって行き止まりから脱出させるテクニックを組み合わせました。また、検索空間における浅い谷からシステムを飛び出させるための「緩やかな揺さぶり」として機能する「ベイシン・ホッピング（basin hopping）」という手法も使用しました。4から10都市のマップ（対称的な形状およびランダムで不規則なネットワークの両方を含む）でテストしたところ、このアプローチは、より小さなマップについてはすべてのケースで完璧なルートを見つけ出しました。10都市のマップは著しく困難ですが、この手法は120回の試行のうち112回で最適ルートを見つけ出し、残りの失敗も完璧な距離からわずか1パーセントの差でした。

決定的なことに、本研究は有望に見えるいくつかの代替案を退けました。研究者たちは、ドライバーのポジションをステップごとに追跡するために、各都市に対して1つずつ計10個のビットを使用するより単純なアプローチをテストしました。しかし、この手法は6都市以上のマップでは、連続する停留所の間の複雑な関係を表現できなかったため、完全に失敗しました。また、2つのセグメントを入れ替えることでルートを改善する「2-opt」として知られる標準的な古典的アルゴリズムとも比較を行いました。2-optは効果的ですが、量子回路はより優れた初期値を提供し、両者を組み合わせることで、どちらか一方のメソッド単独よりも優れた性能を発揮しました。研究は、成功が量子回路自体のパワーによるものではなく、問題の特定のエンコーディング方法とコントローラーの高度な訓練によるものであることを確認しました。

また、本研究の結果は、測定に関する効率性についても強調しています。実際の量子コンピュータでは、明確な信号を得るためにプロセスを何度も繰り返して回答を読み取る必要があります。シミュレーションによれば、わずか100回の読み取りであっても、システムは最適なルートを確実に特定できることが示されました。これは、十分なビットを持つ物理的な量子コンピュータが利用可能になったとき、この手法が何百万回もの反復を必要とせずに迅速に結果を提供できることを示唆しています。研究者たちは、現在の作業は量子的な振る舞いをシミュレートする古典的なコンピュータ上で行われたものの、技術自体は実際のハードウェアでも動作するように設計されていると述べています。次のステップは、実際の機械のノイズの多い条件下でのテストと、手作業でチェックするにはルートの数が膨大すぎる、より大きなマップへのスケールアップです。

この研究は、量子最適化を実用的なものにするための重要な一歩となります。エンコーディングの問題を解決し、異なるマップや時刻にわたって汎用化できるコントローラーを作成することで、研究者たちは複雑なルーティング問題を効率的に解決できるマシンへの道筋を示しました。単一のパラメータで時間依存の変化を扱える能力は、条件が決して静的ではない現実世界のアプリケーションにおいて特に有望です。完全な機能を持つ量子オプティマイザへの道のりは続いていますが、この研究は、複雑な世界の中を最短経路で見つけるために、これらのマシンをどのように訓練すべきかという明確なブループリントを提供しています。

技術要約：Lehmerコードを用いたVQKANによるTSPの解決

問題提起
巡回セールスマン問題（TSP）は、基本的なNP困難な組合せ最適化問題である。古典的な厳密解法は指数関数的にスケールアップするが、変分量子アルゴリズム（VQA）は、ノイズのある中規模量子（NISQ）デバイスに向けた潜在的な経路を提供する。しかし、標準的な量子エンコーディングは、TSPに対して大きな障壁に直面している：

ワンホット・エンコーディング（One-hot encoding）： $N$ 個のサイトに対して $(N-1)^2$ 個の量子ビットを必要とする。ほとんどの基底状態が無効なツアー（経路）であり、コスト景観を支配し調整を困難にするペナルティ項が必要となる。
バイナリ・エンコーディング（Binary encoding）： 量子ビット数を $(N-1)\lceil \log_2 N \rceil$ に削減できるが、依然としてペナルティや修復を必要とする無効な文字列が残る。
置換エンコーディング（Lehmerコード）： ツアーを $(N-1)!$ 個の置換の中でのランクによってラベル付けし、わずか $n = \lceil \log_2(N-1)! \rceil$ 個の量子ビットのみを必要とする。決定的なのは、すべての基底状態が有効なツアーに対応するため、ペナルティ項を排除できる点である。しかし、このエンコーディングを用いた従来の変分ソルバーは、ランクの景観における局所性の欠如と成功率の低下により、6サイトを超えるスケーリングに苦慮してきた。

手法
著者は、コンパクトなLehmerコード・エンコーディングと、変分量子コルモゴロフ・アーノルド・ネットワーク（VQKAN）、および特殊なトレーニング・レジメンを組み合わせたパイプラインを提案している。

エンコーディングと読み出し：
- ツアーは、 $n = \lceil \log_2(N-1)! \rceil$ 個の量子ビットに格納されたLehmerコードによって表現される。
- ランクの景観における非局所性に対処するため、量子ビットから読み取られた整数は**バイナリ反射グレーコード（binary-reflected Gray code）**として解釈される。これにより、1ビットの反転で異なる状態が、連続するLehmerコード（最後に訪問したサイトの順序のみが異なる状態）に対応することが保証される。
- 回路は、単一量子ビットの $R_y$ 回転と近傍 $CZ$ ゲートからなる、浅いハードウェア効率的なアンサンブル（深さ $d=2$ ）である。
VQKANによる角度生成：
- 各インスタンスに対して回路の角度を直接最適化する代わりに、回転角はVQKANによって生成される。
- 各角度は、入力特徴量（時間 $t$ および距離行列 $D$ の行平均を最大値で正規化したもの）の学習可能な二次スプラインである。
- これにより、単一のパラメータセットを用いて、グラフの特性が時間とともに変化する（例：交通量や電力網のルーティング）一連のグラフに対して汎用化が可能となり、インスタンスごとの再学習を不要にする。
損失関数とトレーニング：
- 回路は、ツアー長の**条件付きバリュー・アット・リスク（CVaR）**を最小化するように訓練される。CVaRは確率質量を最短ツアーに集中させ、「ベスト・オブ・ショッツ（best-of-shots）」型の読み出し戦略と整合させる。
- 勾配は**随伴法（adjoint method）**を用いて正確に計算される（回路が実数振幅を使用しているため実行可能）。
- 最適化アルゴリズムは、CVaRの景観をナビゲートし、局所解を回避するために以下の4つの特定の戦略を採用する：
  - マルチスタート（Multi-start）： 異なるランダムシードからの複数の独立した実行。
  - リスクレベル・スケジュール（Risk-level schedule）： 初期段階では $\alpha=0.5$ から開始し、 $\alpha=0.02$ へと減少させるカリキュラム学習アプローチであり、初期には景観を滑らかにし、後に最適解へと集中させる。
  - 小角初期化（Small-angle initialization）： バリエン・プラトー（barren plateaus）を避けるため、パラメータを単位行列付近に初期化する。
  - ベイシン・ホッピング再起動（Basin-hopping restartss）： 収束後、パラメータを摂動させて残留する局所解から脱出させる。
読み出しと後処理：
- 状態を $M$ 回（例： $10^2$ から $10^5$ ショット）サンプリングする。最も短いサンプリングされたツアーを返す。
- オプションの古典的後処理として、上位20個のサンプリングされたツアーに2-optを適用し、解を精緻化する。

主な結果
本手法は、対称多角形および非対称ランダムグラフに対して $N=4, 6, 8, 10$ で評価された。

成功率： フル・オプティマイザ（すべてのトレーニング戦略を含む）は、 $N=4$ から $10 $の3回実行プロトコルにおいて、**すべてのケース（36/36組）**で最適ツアーを返した。より厳格な$ N=10$ における30回反復テストでは、**120ケース中112ケース（93.3%）**で最適解を見つけ、残りの失敗も最適長から1%以内であった。
量子ビット効率： $N=10$ の場合、本手法は19個の量子ビットを使用する。これは、ワンホット・エンコーディングの81個と比較して大幅に少ない。
測定効率： 最適なツアーは、わずか $10^2$ 回の測定ショットで見つけられた。 $N=10$ における最適解の未発見は、サンプリングノイズではなく、状態ベクトルに最適ツアーが含まれていなかったこと（トレーニングの限界）に起因していた。
汎用性： 時間依存グラフにおいて、距離特徴量と時間のみで訓練されたネットワークは、未知の時間点に対しても正常に汎用化した。一方で、時間のみで訓練されたネットワークは効果的な補間ができなかった。
アブレーション研究（構成要素解析）：
- ベイシン・ホッピングが、 $N=10$ における残留局所解を取り除くための決定的な要素であることが特定された。
- **より深い回路（深さ4）**は、深さ2の回路よりも性能を向上させず、より多くのパラメータを必要とした。
- グレーコード読み出しおよび距離特徴量は、高い成功率と汎用性に不可欠であった。
- 古典的制御： 「 $N$ 量子ビットのワンホット・ウォーク」（ $N$ 個の量子ビットを使用してセールスマンをステップごとに移動させる手法）は、 $N \ge 6$ で有効なツアーを見つけることができず、 $N$ 個の量子ビットではツアーの分布を表現するには不十分であることを裏付けた。訓練された回路は、ランダムなツアーから開始した2-optよりも優れた初期解を提供した。

意義と主張
本論文は、置換エンコードされたTSPソルバーが6サイトを超えると失敗するという、従来の置換エンコードにおける最適化のボトルネックを解決したと主張している。コンパクトなLehmerコードと、グラフの特徴量から回路パラメータへのマッピングを学習するVQKANを組み合わせることで、以下のことを実証した：

スケーラビリティ： 標準的なエンコーディングよりも大幅に少ない量子ビットを使用して、 $N=10$ までのTSPインスタンスを確実に解決する。
汎用性： 単一のパラメータセットを用いて、時間依存グラフを扱うことができる。
最適化戦略： 置換ランクの非局所的な景観を克服するために、特定の最適化コンポーネント（ベイシン・ホッピング、リスクレベル・スケジューリング）が必要であることを特定した。

著者は、このシミュレーションはエンコーディングとオプティマイザの実現可能性を確立するものであり、大規模な $N$ に対して最先端の古典的ヒューリスティックに対する量子優位性をまだ示しているわけではなく、また、勾配推定におけるショットノイズも考慮していないことを明記している。本研究は、NISQハードウェア上での置換エンコードされたVQAのスケーリングに関する概念実証（プルーフ・オブ・コンセプト）として機能する。

関連論文