本記事では Classiq の Qmod を用いて、量子近似最適化アルゴリズム QAOA (Quantum Approximate Optimization Algorithm) により ナップサック問題（Knapsack Problem） を解く方法を紹介します。
ナップサック問題とは
ナップサック問題は古典的な NP 完全問題であり、以下のように定義されます。
-
複数の品物があり、それぞれ
- 重み $ w_i $
- 価値 $ v_i $
- 選択できる個数の上限 $d_i$
これらを組み合わせて、ナップサック容量 $C$ を超えないようにしつつ、価値の合計を最大化したいという最適化問題になります。
数式で表すと：
$$
\text{maximize} \quad \sum_i v_i x_i
$$
$$
\text{subject to} \quad \sum_i w_i x_i \le C, \quad x_i\in[0,d_i]
$$
となります。今回は具体例として次の問題を解きます：
ここでは、小さなおもちゃのインスタンスを選びます：
-
2 種類のアイテム：
- $a \in [0, 7]$ with $w_a=2$, $v_a=3$
- $b \in [0, 3]$ with $w_b=3$, $v_b=5$
-
$C=12$
今回のケースでは最適解は $a = 3$, $b = 2$となります。これは後でQAOAの結果と比較します。
アルゴリズムの概要
QAOA は、目的関数をエネルギーに対応させたコストハミルトニアンと、探索性能を高めるミキサーハミルトニアンを交互に適用することで、最適解を確率的に高い出現率へ押し上げる方式です。
Classiq の Qmod では、こうした最適化ハイブリッドアルゴリズムを簡潔に記述できます。
実装
ライブラリの読み込み
from classiq import *
問題設定
QmodのQStructを使用して、複数の量子変数を一つの変数として定義します。今回は、ナップザック変数$a,b$はそれぞれ、3量子ビット、２量子ビットでエンコードできます。
from classiq import *
class KnapsackVars(QStruct):
a: QNum[3]
b: QNum[2]
目的関数および制約関数はQmodでそのまま記述可能です。上記の問題設定から以下のように記述可能です。
def objective(v: KnapsackVars):
return v.a * 3 + v.b * 5
def constraint(v: KnapsackVars):
return v.a * 2 + v.b * 3 <= 12
@qfunc
def cost(v: KnapsackVars):
return -objective(v) if constraint(v) else 0
次に、QAOAで必要なコスト演算子を定義します。今回のケースでは制約問題を充足する場合にコスト関数を適用し、充足しない場合はコストを０にするアプローチにします。そうすると、満たす場合はマイナスの値に移行し、充足しない入力状態は０と相対的にエネルギーが高くなるように設定できます。
$$
\begin{eqnarray}
|x\rangle \xrightarrow{U_{\text{o}}(\theta)}
&&e^{i\theta f_{\text{obj}}(x)} |x\rangle \quad \text{constraint}(x)=1
\end{eqnarray}
$$
$$
\begin{equation}
|x\rangle \xrightarrow{U_{\text{o}}(\theta)} |x\rangle \quad \text{constraint}(x)=0
\end{equation}
$$
@qfunc
def apply_cost(gamma: CReal, v: KnapsackVars) -> None:
aux = QBit("aux")
within_apply(
within=lambda: assign(
constraint(v), aux
),
apply=lambda: control(aux, lambda: phase(-objective(v), gamma)),
)
QAOA の実行設定
最後に、以下でQAOAが定義できます。ミキサー演算子は単純なRxゲートを使用します。
NUM_LAYERS = 1
@qfunc
def main(params: CArray[CReal, NUM_LAYERS * 2], v: Output[KnapsackVars]):
allocate(v.size, v)
hadamard_transform(v)
repeat(
NUM_LAYERS,
lambda i: [
apply_cost(params[2 * i], v),
apply_to_all(lambda q: RX(params[2 * i + 1], q), v), # mixer layer
],
)
qprog = synthesize(main)
show(qprog)
上記を実行すると回路が自動生成されます。
それぞれのブロックをクリックするとゲート情報がみれます。
上記の生成された回路を使用して古典最適化処理を行うと、以下のように最適化処理に対する収束度合いが見れます。
最適化後のパラメータを使用して量子回路を実行すると下記のように$a=3,b=2$が最も振幅増幅されていることがわかり、厳密解と一致していることがわかります。
参考文献
- E. Farhi, J. Goldstone, S. Gutmann, “A Quantum Approximate Optimization Algorithm”, arXiv:1411.4028
- Knapsack problem – Wikipedia
- Knapsack problem – Qmod
まとめ
- 本記事では Classiq の Qmod を使用して、 QAOA を用いたナップサック問題を量子最適化として解く方法を紹介しました
- Qmod によって、最適化問題の記述・制約設定・目的関数設定を非常に直感的に書けることが確認できたと思います
- より高度な設定（別のミキサー、p の増加、他の制約付き整数最適化など）にも応用可能です