組合せ最適化問題とは

組合せ最適化問題とは、有限個の選択肢の中から、特定の制約条件を満たしながら、目的関数を最適化(最大化または最小化)する組合せを見つける問題です。

があります。問題の規模が大きくなると計算時間が指数関数的に増加するため、実用的な時間で近似解を得るためのアルゴリズムが求められています。

組合せ最適化問題の難しさとは

組合せ最適化問題の本質的な難しさは、以下の要因から生じています。

基本的な難しさは、可能な組合せの数が入力サイズに対して指数関数的に増加すること
- 例. n個の都市を巡回するセールスマン問題では、可能な経路の数は(n-1)!通りとなり、都市数が増えるとすぐに全探索が現実的ではなくなる

NISQ (Noisy Intermediate-Scale Quantum) の量子コンピュータで取り組むべき組合せ最適化問題について。現在のNISQデバイスの制約（50-100量子ビット程度、ノイズの存在）の中でも、有意義な結果を得られる可能性が高い問題を選定しています。

問題タイプ	問題の特徴	実装上の課題
ポートフォリオ最適化	- 資産配分の最適化 - 制約条件が明確 - リスク・リターンのトレードオフ	- リスク制約の量子表現 - 市場データの更新頻度への対応
配送ルート最適化	- 巡回セールスマン問題の部分問題 - 距離と時間の最小化 - 動的な制約条件	- 動的な制約の組込み - リアルタイム性の確保
グラフ分割問題	- ネットワーク構造の最適化 - 明確な評価指標 - スケーラブルな問題設定	- グラフ構造の量子表現 - 分割数の最適化
施設配置問題	- 地理的制約が明確 - 複数目的の最適化 - 離散的な決定変数	- 地理的制約の表現 - 多目的最適化の実装