技術要約：人員ロースタリングのための制約保存型QAOA

問題提起

人員ロースタリングは、日次の充足要件や連続勤務制限といった厳しい運用上の制約を特徴とする組合せ最適化問題である。古典的な手法（整数計画法、メタヒューリスティクス）は成功を収めてきたが、システム規模の増大に伴う探索空間の指数関数的な拡大により、量子アルゴリズム、特に量子近似最適化アルゴリズム（QAOA）の活用が動機付けられている。

制約付き問題に対する標準的なQAOA定式化は、通常、ペナルティベースのアプローチに依存している。この枠組みでは、硬い制約を位相ハミルトニアンへのエネルギーペナルティ項として追加することで強制される。このアプローチには以下のような重大な欠点がある：

1. キャリブレーションの感度: パフォーマンスがペナルティ係数の選択に強く依存する。
2. ランドスケープの歪み: 大きなペナルティは最適化のランドスケープを歪ませる可能性がある。
3. 実行不可能な領域へのアクセシビリティ: 変分進化の過程で実行不可能な構成が動的にアクセス可能な状態のままとなり、たとえエネルギー的にペナルティが課されていても、本来禁止されるべき領域に量子振幅が蓄積してしまう。

本論文は、硬い制約をミキサー・ハミルトニアンに直接埋め込み、量子進化を厳密に実行可能部分空間内に閉じ込める制約保存型QAOAフレームワークの必要性に対処するものである。

手法

1. 数学的定式化

著者らは、$N$人の作業員と$D$日間のバイナリ人員ロースタリング問題を定式化している。状態はバイナリ行列 $q \in \{0,1\}^{N \times D}$ で表され、$q_{n,d}=1$ は作業員 $n$ が日 $d$ に割り当てられたことを示す。
この問題は、以下の2つの硬い制約の下で、割り当てコスト $C(q)$ を最小化することである：

• 日次充足（Daily Coverage）: $\sum_{n} q_{n,d} = W_d$ （各日における固定された労働力）。
• 連続勤務禁止（No-Consecutive-Duty）: $q_{n,d} q_{n,d+1} = 0$ （作業員が2日連続で勤務しない）。

構成空間は階層的に構造化されている：

• $\mathcal{H}$: 完全なバイナリ・ヒルベルト空間。
• $\mathcal{F}_{cov}$: 充足制約のみを満たす部分空間。
• $\mathcal{F}_{full}$: 両方の制約を満たす部分空間（完全な実行可能多様体）。

2. ミキサーの構築

論文では、実行可能セクターに対応する一連のミキサー・ハミルトニアンを提案している：

• Penalty-X (ベースライン): 標準的な横磁場ミキサー ($\sum X_{n,d}$) を使用し、両方の制約を位相ハミルトニアン内のエネルギーペナルティを通じて強制する。
• Coverage-XY: 各日の励起数（作業員数）を保存するXYミキサーを使用する。これは $\mathcal{F}_{cov}$ を動的に保持するが、連続勤務禁止制約については依然としてペナルティ項を必要とする。
• Guarded-XY (提案手法): 両方の制約をミキサーに直接埋め込んだ**ガード付き遷移演算子（guarded transition operator）**を導入する。
  • ガード機構: 日 $d$ における作業員 $u$ と $v$ の間の提案された交換に対し、演算子は「ガード射影器」 $\hat{G}$ を含む。この射影器は隣接する日（$d-1, d+1$）の状態を評価し、その交換が連続勤務違反を引き起こす場合に消失する。
  • 結果: ミキサー $\hat{H}_{M}^{guard}$ は、$\mathcal{F}_{full}$ 内でのみ遷移を生成する。その結果、位相ハミルトニアンは目的関数のみ（$\hat{H}_C = \hat{H}_{obj}$）へと簡略化され、硬い制約のペナルティ・キャリブレーションを排除できる。

3. 到達可能性とタイト・パターン拡張

著者らは、厳密な実行可能性の保存が到達可能性（実行可能グラフの連結性）を保証するわけではないことを指摘している。「飽和」したワークロード・セグメントにおいて、$W_d + W_{d+1} = N$ である場合、連続勤務禁止制約は相補的な割り当てを強制し、実行可能グラフを断片化して非連結なコンポーネントに分割する可能性がある。

• 解決策: **タイト・パターン拡張（tight-pattern extension）**が導入される。これは、飽和セグメント全体にわたって交互の割り当てパターンを入れ替える集団交換演算子を追加し、制約を破ることなく $\mathcal{F}_{full}$ 内の連結性を回復させる。

4. シミュレーション・プロトコル

研究では、ベンチマーク・インスタンス（$N=4, D=4$, ワークロード $W=[2,1,2,1]$）を用いた厳密な状態ベクトル・シミュレーションを使用している。

• 比較: Penalty-X、Coverage-XY、および（タイト・パターン拡張を含む/含まない）Guarded-XY。
• 最適化: 期待値および条件付き期待値（CVaR, $\alpha=0.2$）の双方の目的関数の下で評価。
• キャリブレーション: ベースライン手法のペナルティ係数は、公平な比較のために厳密に校正されたが、Guarded-XYはこのような校正を必要としなかった。
• 初期化: 実行可能セクター上の一様重ね合わせ状態と、局所的な実行可能開始状態の両方のテストを行った。

主な結果

1. ペナルティ・キャリブレーションの排除

Guarded-XYアプローチは、硬い制約のペナルティ係数を調整する必要性を排除することに成功した。位相ハミルトニアンには割り当てコストのみが含まれ、変分ランドスケープが単純化される。

2. 出力分布の質の向上

• 実行可能性: Guarded-XYは、その構成により $P_{full} = 1$ (100%の実行可能状態の確率) を維持する。対照的に、Coverage-XYおよびPenalty-Xは、最適化されたペナルティを用いても、実行不可能領域へのリーク（$P_{full} < 1$）を示す。
• 最適解への集中: CVaR最適化の下で、Guarded-XYは他の手法と比較して、厳密な最適スケジュールのサンプリング確率（$P_{opt}$）を一貫して最も高く提供する。
• 解の質: Guarded-XYは、最も高い平均近似比（$\langle r \rangle$）を達成する。論文では、部分的な制約保存手法（Coverage-XY）は、人工的に低い生のコストを持つ実行不可能なスケジュールにかなりの確率を割り当てることがあり、それが真の実行可能最適解からの最適化を妨げる可能性があると述べている。

3. 構造的感度と初期化

• 飽和ワークロード: タイト・パターン拡張は、高度に飽和したワークロードのシナリオにおいて、実行可能グラフが断片化するのを防ぎ、連結性を維持するために必要であることが示された。
• 初期化: いくつかの「拡散」ミキサー層を適用すれば、単一の局所的な実行可能スケジュールから初期化した場合でも、フレームワークは有効である。これは、ハードウェアフレンドリーな初期化戦略を示唆している。
• スケーラビリティ: 様々な量子ビット数（12, 16, 20）を持つインスタンスを用いたテストでは、探索空間が大きくなるため生の最適確率自体は低下するものの、最適状態の濃縮度（$\eta_{opt}$）は高いまま維持されており、アルゴリズムが一貫して一様サンプリングに対して最適解を増幅させていることが示された。

意義と主張

本論文は、両方の硬いスケジューリング制約がミキサー・ハミルトニアンに直接埋め込まれた、人員ロースタリングのための初の体系的な制約保存型QAOA定式化を提示していると主張している。

主な貢献は以下の通りである：

1. 制約処理の転換: 制約の強制をエネルギー的な位相ハミルトニアンから動的なミキサーへと移行させ、進化を実行可能多様体内に確実に閉じ込める。
2. 設計原理の分離: 実行可能性の保存（ミキサーが実行可能集合内に留まることを保証する）と、到達可能性のデザイン（実行可能集合が連結であることを保証する）を区別している。Guarded-XYミキサーは前者を扱い、タイト・パターン拡張は後者を扱う。
3. 汎用性: 著者らは、遷移グラフのフレームワークとガード付き遷移の原理が、実行可能性が局所的な遷移ルールによって特徴付けられる広範な制約付き量子最適化問題（スケジューリング、ルーティング、リソース割り当てなど）に適用可能であると主張している。

本研究は、制約保存型のミキサーが、ペナルティベースの手法と比較して、ペナルティ係数の校正に対する感度なしに、より高品質な出力分布と最適解への強い集中を実現できることを実証している。