• English

整数集合分割問題

[mathjax]

整数集合分割問題は、整数の集合 S を要素の総和が等しい2つの集合に分割する問題である。

$$S = \left\{ 1, 2, 3, 4 \right\} \rightarrow S_{1} = \left\{ 1, 4 \right\},
S_{2} = \left\{ 2, 3 \right\}$$

Hamiltonian:

$${\cal H} = A \left( \sum _{i=1} ^{N} n_{i} \sigma _{i} \right) ^{2} , \quad
\sigma _{i} \in \left\{ -1, 1 \right\}$$

 

具体的な解法

例) N=4(以下の集合)のケースを具体的に解いてみる。

$$S = \left\{ 1, 2, 3, 4 \right\} \rightarrow S_{1} = \left\{ 1, 4 \right\},
S_{2} = \left\{ 2, 3 \right\}$$

 

以下の手順を踏む。

  1. \( \sigma = \{ -1, 1 \}\)を\(q = \{ 0, 1 \}\)に置き換えて、QUBO形式に変換する
  2. QUBO形式を、一般的なHamiltonianの形式に変換する
  3. qsolvを使って解く

$${\cal H} = A \left( \sum _{i=1} ^{N} n_{i} \sigma _{i} \right) ^{2}
\rightarrow{}(\sigma_{1} + 2\sigma _{2} + 3\sigma _{3} + 4\sigma _{4}) ^{2}$$ $$N = 4, \quad n_{i} \in \left\{ 1, 2, 3, 4 \right\}$$ $$\sigma _{i} = 2q_{i} – 1$$

 

計算過程

Hamiltonianが最小値を取るスピン配置を求めることが目的なので、定数項(下式の場合は最後の”+100”)は無視する。

$${\cal H} = (\sigma _{1} + 2\sigma _{2} + 3\sigma _{3} + 4\sigma _{4})^{2}$$ $$= \left[ (2q_{1} – 1) + 2(2q_{2} – 1) + 3(2q_{3} – 1) + 4(2q_{4} – 1)\right]^{2}$$ $$= 4q_{1} ^{2} + 16q_{1}q_{2} + 24q_{1}q_{3} + 32q_{1}q_{4} – 40q_{1}$$ $${55pt}+ 16q_{2} ^{2} + 48q_{2}q_{3} + 64q_{2}q_{4} – 80q_{2}$$ $$+ 36q_{3} ^{2} + 96q_{3}q_{4} – 120q_{3}$$ $$+ 64q_{4} ^{2} – 160 q_{4} + 100$$ $$= 4\left( 4q_{1}q_{2} + 6q_{1}q_{3} + 8q_{1}q_{4} + 12q_{2}q_{3} +
16q_{2}q_{4} + 24q_{3}q_{4} \right)$$ $$ – 4\left( 9q_{1} + 16q_{2} + 21q_{3} + 24q_{4} \right)$$ $$ + 100$$

$$q_{i}^{2} = q_{i} , \quad q_{i} \in \left\{ 0, 1 \right\}$$

QUBO input file

qbsolv実行結果

期待する結果(以下)になっている。
※D-Waveを使っているわけではなく、シミュレータによる計算結果が出力される。

$$S = \left\{ 1, 2, 3, 4 \right\} \rightarrow S_{1} = \left\{ 1, 4 \right\},
S_{2} = \left\{ 2, 3 \right\}$$

整数集合分割問題(量子コンピューティング)に関するお問い合わせについてはこちらをご覧ください。
PAGETOP
Copyright © 株式会社メタテクノ All Rights Reserved.