QUBO++で数学パズルを解く：各桁の積が252の3桁の奇数 | TechDistill

> Source: Zenn_Python

// Problem

従来のQUBO（2次形式）では、変数の積（高次項）を扱う際に、補助変数を用いた複雑な2次形式への変換が必要となる。また、整数変数をバイナリ変数へ変換するエンコーディング作業は、定式化の難易度と実装コストを増大させる要因となっていた。

// Approach

PyQBPPライブラリを活用し、整数変数の範囲指定による自動エンコーディングと、高次項を直接扱えるHUBO（Higher-order Unconstrained Binary Optimization）としての定式化を採用。制約条件をエネルギー関数として記述し、Exhaustive Solverを用いて最適解を探索する。

// Result

各桁の積が252となる3桁の奇数（479, 497, 667, 749, 947）の5つの解を、重複なく正確に列挙することに成功した。定式化の容易さと、制約充足問題に対する強力な記述力を実証した。

Senior Engineer Insight

> 本記事が示す「数学的記述と実装の距離の近さ」は、プロトタイピングの速度を劇的に向上させる。特に整数変数のエンコーディングをライブラリ側に隠蔽する設計は、開発者の認知負荷を下げ、定式化ミスを防ぐ観点で極めて優秀である。しかし、本件で使用されているExhaustive Solverは計算量が指数関数的に増大するため、実務における大規模な組合せ最適化問題への適用には、近似解法や量子アニーリングデバイスへのスケーラビリティを考慮した設計が不可欠である。