ペトリネットの振舞いに基づく組合せ最適化問題のQUBOモデル定式化

摘要

本稿では，量子アニーリングによる最適化計算に必要なイジングモデルもしくはQUBOモデルを，対象の問題を表現したペトリネットの振舞いから生成する手法を提案する．最初にペトリネットの振舞いに関連する発火条件，状態方程式，可達問題，保存性のQUBOモデルを整理した後，巡回セールスマン問題，およびジョブショップスケジューリング問題の定式化を行う．これにより，これらの最適化問題のQUBOモデルの定式化がペトリネットの振る舞いにおける基本的な制約と問題独自の制約を組み合わせることで容易に定式化できることを示す．