整數(shù)分割問題：
QUBO建模最重要的就是，把建模對(duì)象中的變量映射為binary（0/1 或者 -1/+1）的變量。我先從簡單的問題開始說明，讓大家有些直觀感受。整數(shù)分割問題就是一個(gè)非常簡單，并容易理解的例子。此文參考了日本NTT公司的量子計(jì)算指南文檔[*1]。
- 整數(shù)分割問題定義：
判斷能否將一個(gè)N 個(gè)整數(shù) a 1 , ??? a N a_1,???a_N a1?,???aN? 的整數(shù)集合分割成兩個(gè)子集合，并且這兩個(gè)子集合里的元素之和相等。
- 例子：
我們可以看到，上面??的例子，分割后的兩個(gè)子集合A和B的元素之和都等于6，所以該集合是可以滿足整數(shù)分割的。
轉(zhuǎn)化為組合優(yōu)化問題：
之前講的QUBO的例子里，用的變量都是0或1。其實(shí)，還可以是-1或+1，這時(shí)候也叫ising模型。求解變量什么時(shí)候用0/1，什么用-1/+1，這個(gè)之后用例子給大家解釋。
這次的問題，是把求解的兩個(gè)子集合的標(biāo)簽作為-1/+1的變量。如下圖所示。
我們的優(yōu)化目標(biāo)就成為了，最小化兩個(gè)子集合的差值的平方和。大家可以思考一下，如果使用0/1作為子集合A和B的標(biāo)簽，我們要怎么定義最小化的目標(biāo)函數(shù)。
- 目標(biāo)集合為{ 1, 5, 6 }時(shí)的目標(biāo)函數(shù)就是：
我們來枚舉一下，所有 x i x_i xi? 從-1或+1取值的組合結(jié)果：
我們可以看到，目標(biāo)函數(shù)值為0時(shí)，我們得到了正確的整數(shù)分割結(jié)果。
目標(biāo)函數(shù)轉(zhuǎn)化為QUBO：
因?yàn)橐呀?jīng)獲得了目標(biāo)函數(shù)，那我們先把多項(xiàng)式展開就好了。展開結(jié)果如下圖所示：
因?yàn)椤?span id="n5n3t3z" class="katex--inline">
x
i
x_i
xi? 從-1或+1取值】這個(gè)設(shè)定，下面??的式子是成立的：
?
x
i
2
=
1
?x_i^{2} = 1
?xi2?=1
所以我們可以得到下面的QUBO結(jié)果：
最后獻(xiàn)上Python代碼。
PyQUBO實(shí)現(xiàn)Ising模型：
之前的目標(biāo)函數(shù)都是展開后的二次多項(xiàng)式，大家可以直接計(jì)算出QUBO矩陣。這次使用PyQUBO直接定義目標(biāo)函數(shù)，大家就不用手動(dòng)求解QUBO矩陣了。
import pyqubo
import neal
x = pyqubo.Array.create('x', shape=(3), vartype='SPIN') # 'SPIN' 就表示目標(biāo)變量是從{-1, 1}取值。目標(biāo)變量需要從{0, 1}中取值時(shí)，就設(shè)定為 'BINARY'
objective_function = (1 * x[0] + 5 * x[1] + 6 * x[2]) ** 2
model = objective_function.compile()
bqm = model.to_bqm()
print("我們可以將bqm轉(zhuǎn)為ising或qubo輸出")
print(bqm.to_ising())
sa = neal.SimulatedAnnealingSampler()
sampleset = sa.sample(bqm, num_reads=10)
samples = model.decode_sampleset(sampleset)
best_sample = min(samples, key=lambda s: s.energy)
print("求解時(shí)，pyqubo內(nèi)部已經(jīng)將ising模型轉(zhuǎn)換為qubo的0或1，所以輸出結(jié)果為0或1")
print(best_sample.sample)
運(yùn)行結(jié)果如下：文章來源：http://www.zghlxwxcb.cn/news/detail-427392.html
我們可以將bqm轉(zhuǎn)為ising或qubo輸出
({'x[2]': 0.0, 'x[0]': 0.0, 'x[1]': 0.0}, {('x[0]', 'x[2]'): 12.0, ('x[1]', 'x[2]'): 60.0, ('x[1]', 'x[0]'): 10.0}, 62.0)
求解時(shí)，pyqubo內(nèi)部已經(jīng)將ising模型轉(zhuǎn)換為qubo的0或1，所以輸出結(jié)果為0或1
{'x[2]': 1, 'x[0]': 0, 'x[1]': 0}
以上就是一個(gè)簡單建模的例子。下篇講旅行商問題的建模。文章來源地址http://www.zghlxwxcb.cn/news/detail-427392.html
- 參考文獻(xiàn)：[*1] : https://www.nttdata.com/jp/ja/-/media/nttdatajapan/files/news/services_info/2021/012800/012800-01.pdf
到了這里，關(guān)于量子退火算法入門（3）：整數(shù)分割問題的QUBO建模的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
