Comparing Qubit and Qudit Encodings for EV Charging and Trip Assignment Problems

本論文は、現実的な電気自動車 fleet 管理問題において、変分量子アルゴリズムに従来の量子ビット（2 値）符号化の代わりに量子 d 値（整数）符号化を使用することで、同等または優れた最適化性能を達成しつつ、リソース要件とシミュレーション実行時間を大幅に削減できることを実証する。

要約

あなたが小さな電気タクシーの車隊の管理者だと想像してください。毎日、あなたは 2 つの大きな仕事をこなさなければなりません。

1. 車の充電: 節約のために、いつ車を充電（プラグを挿す）するか、あるいは電力をグリッドに戻す（放電）かを決める必要があります。
2. 移動の割り当て: どの車がどの顧客の移動を担当するかを決める必要があります。

これはパズルです。間違った車に移動を割り当てたり、間違った時間に充電したりすると、バッテリーが切れたり、電力グリッドの規則に違反したりする可能性があります。このパズルを完璧に解くことは、特に量子物理学の規則を組み合わせると、コンピューターにとって非常に困難です。

この論文は、ホンダ研究所とライデン大学の研究者たちからの報告であり、彼らは単純な問いを投げかけました。「このパズルを量子コンピューターの言語に翻訳する『方法』が重要なのか？」

彼らは、量子コンピューターが問題をより速く、より良く解くのを助けるのはどちらかを確認するために、2 つの異なる「言語」（符号化）をテストしました。

2 つの言語：「キュービット」対「キューディット」

彼らの実験を理解するには、ロボットに移動のリストを説明しようとしていると想像してください。

1. 古い方法：「キュービット」言語（オン・オフのスイッチ）
電灯のスイッチを想像してください。それはオンかオフのどちらかです。

• この方法では、研究者たちは車と移動のあらゆる可能な組み合わせごとに、個別の電灯スイッチを使用しました。
• 車が 3 台、移動が 2 つあれば、スイッチは 6 個必要になります。スイッチがオンの場合、「車 1 が移動 A を担当する」ことを意味し、オフの場合はそうではありません。
• 問題点: これにより、スイッチでいっぱいの巨大で散らかった部屋が生まれます。コンピューターは、無意味な組み合わせ（例：「車 1 が移動 A を担当する」かつ「車 2 も同時に移動 A を担当する」など）の数百万通りをチェックしなければならず、不可能なシナリオの確認に時間を浪費します。

2. 新しい方法：「キューディット」言語（多位置のダイヤル）
0 または 1 だけでなく、多くの数字を指し示せる調光スイッチやダイヤルを想像してください。

• この方法では、多くのスイッチを使う代わりに、移動ごとに1 つのダイヤルを使用しました。
• ダイヤルが「1」を指せば、「車 1 がこの移動を担当する」ことを意味します。「2」を指せば「車 2」です。「0」を指せば「どの車もこの移動を担当しない」ことを意味します。
• 利点: これははるかに直接的です。2 台の車が同じ移動を奪い合っているかどうかを確認する必要はありません。ダイヤルは物理的に同時に 2 台の車を指すことができないからです。これにより、コンピューターが探索しなければならない「部屋」のサイズが縮小されます。

実験：時間との競争

研究者たちは、これらの 2 つの言語のパフォーマンスを確認するために、量子コンピューター（「状態ベクトルシミュレーション」、つまり完璧でノイズのない練習走行のようなもの）のシミュレーションを実行しました。彼らは、車、移動、時間枠の数が異なる多くのランダムなシナリオを設定しました。

彼らが発見したことは以下の通りです。

• 探索空間の縮小: 「キューディット（ダイヤル）」法は、探索空間のサイズを指数関数的に削減しました。干し草の山から針を探すことを想像してください。キュービット法は、山ほどの大きさの干し草の山を与えます。一方、キューディット法は、靴箱ほどの大きさの干し草の山を与えます。
• 結果の高速化: 「靴箱」がはるかに小さかったため、シミュレーションははるかに高速に実行されました。キューディット法は、解を見つけるのに著しく少ない時間を要しました。
• 品質の向上: 驚くべきことに、キューディット法は単に高速に実行されただけでなく、より良い、あるいは同等の解を見つけました。見つかった解は完璧な答えに近く、結果はより一貫性があり（「ジッター」やランダム性が少ない）、安定していました。
• 「深さ」の問題: 彼らは、アルゴリズムに層（深さ）を追加することで量子コンピューターに「より深く」考えさせようと試みました。通常、深く考えることは役立ちます。しかしここでは、キュービット法は混乱し、深くなるにつれてパフォーマンスが低下しました。これは、おそらく制御すべき変数が多すぎ、コンピューターが最適化を早期に停止してしまったためです。一方、キューディット法は、問題が複雑になるにつれてさえも、安定し、堅牢さを保ちました。

結論

この論文は、スケジュール管理や割り当て（電気タクシーを移動に割り当てるなど）に関する問題については、従来の**キュービット（スイッチ）**アプローチよりも、**キューディット（ダイヤル）**アプローチを使用する方がはるかに賢明な選択であると結論付けています。

旅行の荷造りに例えれば以下のようになります。

• キュービット: 1 枚ずつ個別の靴下をスーツケースに詰め込み、箱に収めようとします。スペースと時間を無駄にします。
• キューディット: 1 つの整然と折りたたまれた靴下の束を持ちます。完璧に収まり、スペースを占有せず、すぐに掴むことができます。

研究者たちは、多くの選択肢を伴う現実世界のスケジューリング問題において、これらの「多値」量子ダイヤル（キューディット）を使用することが、時間と計算能力の両方を節約する実用的かつ効率的な道であると提案しています。

技術概要

技術的サマリー：EV 充電および_trip 割り当て問題におけるキュービットとクディット符号化の比較

問題定義
本論文は、電気自動車（EV）の車隊管理に関する制約付き最適化問題を取り扱っている。これには、離散時間区間 $T$ において $N_{EV}$ 台の車両の双方向（または単方向）充電をスケジューリングし、これら車両を $R$ 件の顧客トリップ要求に割り当てるという、2 つの結合した意思決定プロセスが含まれる。目的は、バッテリーの充電状態（SOC）制限、トリップの重複、グリッド電力の限界、および車両がトリップのサービス中は充電できないという要件など、厳格な運用制約を満たしつつ、充電コストを最小化することである。

調査された核心的な課題は、トリップ割り当て変数の符号化の選択が、変分量子アルゴリズム（VQA）、特に量子近似最適化アルゴリズム（QAOA）のリソース要件と最適化行動にどのように影響するかである。著者は、2 つの異なる表現を比較する。

1. 二値（キュービット）符号化: 各 EV-トリップのペアに対して 1 つの二値変数（$r_{n,i} \in \{0,1\}$）を使用する。これには、各トリップが最大 1 台の EV によってのみサービスされ、重複するトリップが同一の車両に割り当てられないことを保証するための明示的な制約が必要となる。
2. 整数（クディット）符号化: トリップあたり 1 つの整数変数（$q_i \in \{0, \dots, N_{EV}\}$）を使用し、その値は直接割り当てられた EV（または未サービス状態）を指定する。この符号化は本質的に「トリップあたり 1 台の EV」という制約を満たすため、割り当てに関する明示的な二値制約を不要にする。

手法
著者は QAOA を用いて問題を定式化する。両方の符号化は充電電力レベル（$l_{n,t}$）に対してクディット変数を使用するが、トリップ割り当ての計算基底において異なる。

• ハミルトニアンの構築: 古典的なコスト関数と制約は、計算基底における対角演算子へと昇格される。制約（例：SOC 制限、トリップ中の充電禁止）は、コストハミルトニアンに追加される非線形ペナルティ項を通じて強制される。
• シミュレーション: 本研究は、アルゴリズムのベンチマーク評価に正確な状態ベクトルシミュレーションを採用する。現実的なハードウェアの制限を模倣するため、コスト関数の期待値は、正確な計算ではなく、有限数の測定ショット（$M=256$）を用いて推定される。
• 最適化: 古典的オプティマイザ（Powell 法）が、QAOA パラメータ（$\gamma, \beta$）を変化させることでコスト関数を最小化する。本研究は、各問題クラスに対して 10 件のランダムなインスタンスを実行し、各インスタンスに対して 10 回の最適化実行を行い、内部オプティマイザの反復回数を 200 回に固定して実施した。
• テストケース: 2 つの問題クラスが分析される。
  • 双方向充電: EV 3 台、時間ステップ 2、トリップ 2、充電レベル 3（$d=3$）。
  • 単方向充電: EV 2 台、時間ステップ 3、変動するトリップ数（$R=2,3,4$）、充電レベル 2（$d=2$）。

主要な貢献と結果
本論文は、いくつかの指標にわたる 2 つの符号化の比較分析を提供する。

1. ヒルベルト空間の削減: 整数（クディット）符号化は、二値（キュービット）符号化と比較して、ヒルベルト空間の次元を指数関数的に削減する。構成の比率は $N_{int}/N_{bin} \approx 2^{-R N_{EV} + R \log_2(N_{EV}+1)}$ で与えられる。テストされたインスタンスでは、これにより探索空間が数万から数千の状態へと削減された。
2. 最適化性能:
   • 平均エネルギーギャップ: クディット符号化は、一貫してキュービット符号化と同等か、わずかに優れた平均エネルギーギャップを達成する。
   • 分散: クディットの結果は、異なる実行間でのエネルギーギャップの分散が著しく低い。
   • 成功確率: 大域的最適解を見つける実行の割合と、サンプリングされた実行可能状態の割合は、一般的にクディット符号化の方が高いか、より安定している。
3. 実行時間と収束:
   • シミュレーション実行時間: ヒルベルト空間が小さいため、クディット符号化は、回路の深さに比例するが係数がはるかに小さい、実質的に短いシミュレーション実行時間を必要とする。
   • レイヤー深度の挙動: QAOA の深度（$L$）が増加するにつれて、キュービット符号化の性能は、クディット符号化よりも著しく低下する。著者はこれを、固定された反復予算内で最適化の景観をナビゲートすることが難しくなる変分パラメータ数の増加に起因すると帰属させる。クディット符号化は、古典的オプティマイザの早期終了に対してより頑健である。
4. コスト景観: キュービット符号化のコスト景観は、クディット符号化と比較して、実行不可能な状態の割合が大きい（これらは高いペナルティコストを課す）ため、より大きなエネルギー規模と高い振動周波数を示す。

意義と主張
本論文は、クディットネイティブな符号化が、変分量子最適化における整数および多値スケジューリング問題を解決するための実用的な道筋を提供すると主張している。主な意義は、離散多値変数を二値キュービットに展開するのではなく、クディットを介して直接表現することが、以下の結果をもたらすことを実証している点にある。

• ヒルベルト空間の次元における指数関数的なリソース節約。
• 古典的シミュレーションにおける計算オーバーヘッドの削減（表現の複雑さの代理として機能）。
• 実行可能解が希薄な高度に制約された領域において特に顕著な、最適化プロセスにおける改善された頑健性。

著者は、本研究が状態ベクトルシミュレーションを使用しているものの、このコンパクトな表現は、制約処理と論理変数のマッピングのオーバーヘッドを削減することにより、ハードウェア実装において潜在的な利益をもたらす可能性を示唆していると指摘する。彼らは、制約付きスケジューリング問題に対して、クディット符号化はリソース要件を劇的に削減しつつ、最適化性能を維持または向上させる優れた選択であると結論づける。本論文は控えめに、将来の研究では、これらの傾向をより大規模なインスタンスおよび実際の量子ハードウェアでテストし、シミュレーションを超えて利点が維持されるかどうかを検証すべきであると示唆している。